Unidad 2: Búsqueda

Las técnicas de búsqueda heurística disponen de alguna información sobre la proximidad de cada estado a un estado objetivo, lo que permite explorar en primer lugar los caminos más prometedores.

Las características de las técnicas heurísticas:

• No garantizan que se encuentre una solución, aunque existan soluciones.
• Si encuentran una solución, no se asegura que ésta tenga las mejores propiedades (que sea de longitud mínima o de coste óptimo).
• En algunas ocasiones (que, en general, no se podrán determinar a priori), encontrarán una solución (aceptablemente buena) en un tiempo razonable.

En general, las técnicas heurísticas son preferibles a los métodos no informados en la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los problemas reales que interesan en Inteligencia Artificial.

La información del problema concreto que estamos intentando resolver se suele expresar por medio de heurísticas.

El concepto de heurística es difícil de aprender. Newell, Shaw y Simon en 1963 dieron la siguiente definición: "Un proceso que puede resolver un problema dado, pero que no ofrece ninguna garantía de que lo hará, se llama una heurística para ese problema".

Si nos planteamos seguir concretando como aprovechar la información sobre el problema en sistemas de producción, la siguiente idea consiste en concentrar toda la información heurística en una única función que se denomina función de evaluación heurística. Se trata de una función que asocia a cada estado del espacio de estados una cierta cantidad numérica que evalúa de algún modo lo prometedor que es ese estado para acceder a un estado objetivo. Habitualmente, se denota esa función por h(e).

La función heurística puede tener dos interpretaciones. Por una parte, la función puede ser una estimación de lo próximo que se encuentra el estado de un estado objetivo. Bajo esta perspectiva, los estados de menor valor heurístico son los preferidos. Pero en otros casos puede suceder que lo que convenga sea maximizar esa función.

Los algoritmos genéticos pertenecen a la computación evolutiva, son considerados también una técnica de inteligencia artificial. A través de millones de años, los organismos han evolucionado biológicamente para sobrevivir y crecer en un mundo cambiante.

Los materiales genéticos de todos los organismos vivos consisten de cromosomas que están divididos en genes; su codificación y desarrollo son considerados un proceso clave en la continuación de las especies. El proceso de selección natural y el sobrevivir de los más aptos son considerados elementos importantes en la evolución, que ha sido estudiada desde el siglo XVII. Los Algoritmos Genéticos están basados en estos aspectos de evolución.

Los algoritmos genéticos utilizan ideas de biología como población de cromosomas, selección natural para selección de pareja, cruza para producción de descendencia y mutación para diversidad. El punto importante de los algoritmos genéticos es la representación de un problema-solución que use un cromosoma de longitud constante o cambiante. La variable representada por la posición es un gen, y su valor se conoce como alelo. Una vez que obtenida la representación (codificado), es decir la manera en que el espacio de soluciones potenciales se transforma en el dominio de trabajo, la metodología de Algoritmos Genéticos puede ser aplicada para alcanzar una buena solución del problema. El codificado más popular por su simplicidad es el binario, donde los alelos son los valores de 0 ó 1. De ser necesario, el codificado basado en valor o de caracteres puede ser usado también. A pesar de que el codificado fijo es popular, los investigadores han usado uno que puede adaptarse para algunos problemas para mejorar los resultados.

El uso de los Algoritmos genéticos está relacionado con el concepto de Optimización, por lo que también es abordada, siendo el objetivo, maximizar el beneficio o minimizar el costo. Adicionalmente se muestran algunas aplicaciones de los algoritmos genéticos: escoger el arreglo de trabajos y de máquinas para minimizar el tiempo de producción, el problema del agente viajero, minimizar la cantidad de merma en el corte de madera, vidrio, entre otros; todos ellos problemas combinatorios que pueden modelarse a través de programación matemática pero que conforme crecen el número de variables no son factibles de resolverse en un tiempo computacional razonable; por lo que resulta interesante uso de los algoritmos genéticos.

Para poder explicar la estructura de los algoritmos genéticos voy a introducir primero algunos términos que serán útiles:

Individuo:  los individuos de nuestra población son las posibles soluciones al problema que estamos tratando.

Población: conjunto de individuos (soluciones).

Función fitness o de adaptación: función que evalúa a los individuos y les asigna una puntuación en función de lo buenas soluciones que sean para el problema.

Función de cruce: función que, dados dos individuos, genera dos ‘descendientes’ a partir de la combinación de genes de sus ‘padres’. Esta función se diseña especialmente para el problema que se esté tratando y, por lo general, se encarga de que los hijos sean mejores soluciones que los padres.

Entonces, la estructura de un algoritmo genético es la siguiente:

1. Se genera una población inicial de individuos (soluciones), usualmente de manera aleatoria.
2. Fase de evaluación: se evalúan los individuos de la población con la función fitness.
3. Fase de selección: se seleccionan los mejores individuos.
4. Fase de reproducción: se cruzan los individuos seleccionados mediante la función de cruce, dando lugar a una nueva generación que va a sustituir a la anterior.
5. Fase de mutación: se introducen mutaciones (pequeños cambios) en ciertos individuos de la nueva población de manera aleatoria.
6. Tenemos una nueva generación, generalmente, con soluciones mejores que la anterior. Volvemos al punto 2.

Los algoritmos genéticos finalizan o bien cuando alcanzan un número de generaciones concreto o cuando cumplen una condición de parada (M, Gestal, 2013).

A continuación, para ejemplificar, diagrama de flujo de un algoritmo genético.

El hombre es el sistema del que mejor se conoce el cómo lleva a cabo las tareas con las que estamos familiarizados y por lo tanto tiene sentido fijarse en él para buscar pistas de cómo crear inteligencia artificial. Si lo que se quiere es escribir programas que simulen el comportamiento humano ante una tarea, la forma de medir el éxito está en que el comportamiento del programa corresponda con el humano, así como mediante distintas clases de experimentos y análisis de protocolos. Cuando se quiere diseñar un programa de IA, se debe intentar especificar tan bien como sea posible el criterio de éxito para el funcionamiento del programa en su particular y restringido dominio.

Para construir un sistema que resuelva un problema específico, es necesario realizar estas cuatro acciones:

• Definir el problema con precisión.
• La definición debe incluir especificaciones precisas tanto sobre las situaciones iniciales como sobre las situaciones finales que se aceptarían como soluciones al problema
• Analizar el problema. Algunas características de gran importancia pueden tener un gran efecto sobre la conveniencia o no de utilizar diversas técnicas que resuelvan el problema.
• Aislar y representar el conocimiento necesario para resolver el problema.
• Elegir la mejor técnica de búsqueda que resuelva el problema y aplicarla al problema particular.

Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.

Un algoritmo genético consiste en una función matemática o una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuáles de ellos deben generar descendencia para la nueva generación.

Versiones más complejas de algoritmos genéticos generan un ciclo iterativo que directamente toma a la especie (el total de los ejemplares) y crea una nueva generación que reemplaza a la antigua una cantidad de veces determinada por su propio diseño. Una de sus características principales es la de ir perfeccionando su propia heurística en el proceso de ejecución, por lo que no requiere largos períodos de entrenamiento especializado por parte del ser humano, principal defecto de otros métodos para solucionar problemas, como los Sistemas Expertos.

• Operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales.
• Cuando se usan para problemas de optimización maximizar una función objetivo- resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas tradicionales.
• Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivamente paralelas.
• Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de las otras técnicas.
• Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen tamaño de la población, número de generaciones, etc.-.
• Pueden converger prematuramente debido a una serie de problemas de diversa índole.

La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pudieran ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla:

• Su espacio de búsqueda (i.e., sus posibles soluciones) debe estar delimitado dentro de un cierto rango.
• Debe poderse definir una función de aptitud que nos indique qué tan buena o mala es una cierta respuesta.
• Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora.

El primer punto es muy importante, y lo más recomendable es intentar resolver problemas que tengan espacios de búsqueda discretos aunque éstos sean muy grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de búsqueda continuos, pero preferentemente cuando exista un rango de soluciones relativamente pequeño.

La función de aptitud no es más que la función objetivo de nuestro problema de optimización. El algoritmo genético únicamente maximiza, pero la minimización puede realizarse fácilmente utilizando el recíproco de la función maximizante (debe cuidarse, por supuesto, que el recíproco de la función no genere una división por cero). Una característica que debe tener esta función es que tiene ser capaz de "castigar" a las malas soluciones, y de "premiar" a las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez.

La codificación más común de las soluciones es a través de cadenas binarias, aunque se han utilizado también números reales y letras. El primero de estos esquemas ha gozado de mucha popularidad debido a que es el que propuso originalmente Holland, y además porque resulta muy sencillo de implementar

Como información para completar lo explicado en la secuencia sobre algoritmo genético, el desarrollo de software basados en A.G es importante para terminar de comprender la importancia de este con respecto a las búsquedas y temas anteriores, dirígete a la siguiente presentación en slideshare.

Nombre: Desarrollo de software con algorítmicos genéticos

Link: https://es.slideshare.net/uni_fcys_sistemas/desarollo-de-sofware-con-algoritmos-genticos

El Algoritmo Genético Simple, también denominado Canónico, se necesita una codificación o representación del problema, que resulte adecuada al mismo. Además se requiere una función de ajuste ó adaptación al problema, la cual asigna un número real a cada posible solución codificada. Durante la ejecución del algoritmo de más abajo, los padres deben ser seleccionados para la reproducción, a continuación dichos padres seleccionados se cruzaran generando dos hijos, sobre cada uno de los cuales actuará un operador de mutación.

El resultado de la combinación de las anteriores funciones será un conjunto de individuos (posibles soluciones al problema), los cuales en la evolución del Algoritmo Genético formaran parte de la siguiente población.

BEGIN /* Algoritmo Genético Simple */
  Generar una población inicial.
  Computar la función de evaluación de cada individuo.

  WHILE NOT Terminado DO

  BEGIN /* Producir nueva generación */
    FOR Tamaño población/2 DO

    BEGIN /*Ciclo Reproductivo */

      Seleccionar dos individuos de la anterior generación,
      para el cruce (probabilidad de selección proporcional
      a la función de evaluación del individuo).

      Cruzar con cierta probabilidad los dos
      individuos obteniendo dos descendientes.

      Mutar los dos descendientes con cierta probabilidad.

      Computar la función de evaluación de los dos
      descendientes mutados.

      Insertar los dos descendientes mutados en la nueva generación.

      END
      IF la población ha convergido THEN Terminado:= TRUE
  END
END
            

INICIO
    // Generar población inicial
    Generar una población inicial de individuos.
                  
    // Evaluar población inicial
    Evaluar la función de aptitud (fitness) de cada individuo.
                  
    MIENTRAS NO se cumpla la condición de parada HACER:
                  
        // Iniciar nueva generación
        PARA i = 1 HASTA (Tamaño de la población / 2) HACER:
                  
            // Selección
            Seleccionar dos individuos de la población actual.
            (La probabilidad de selección es proporcional a su aptitud).
                  
            // Cruce
            Con cierta probabilidad, cruzar los dos individuos seleccionados,
            produciendo dos descendientes.
                  
            // Mutación
            Con cierta probabilidad, mutar cada descendiente.
                  
            // Evaluar descendientes
            Evaluar la aptitud de los dos descendientes.
                  
            // Insertar en nueva generación
            Insertar los descendientes en la nueva población.
                  
        FIN PARA
                  
        // Comprobar convergencia
        SI la población ha convergido ENTONCES
            Terminar := VERDADERO
                  
    FIN MIENTRAS
                  
FIN
            

Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.

Un algoritmo genético consiste en una función matemática o una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuáles de ellos deben generar descendencia para la nueva generación.

Versiones más complejas de algoritmos genéticos generan un ciclo iterativo que directamente toma a la especie (el total de los ejemplares) y crea una nueva generación que reemplaza a la antigua una cantidad de veces determinada por su propio diseño. Una de sus características principales es la de ir perfeccionando su propia heurística en el proceso de ejecución, por lo que no requiere largos períodos de entrenamiento especializado por parte del ser humano, principal defecto de otros métodos para solucionar problemas, como los Sistemas Expertos.

• Operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales.
• Cuando se usan para problemas de optimización maximizar una función objetivo- resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas tradicionales.
• Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivamente paralelas.
• Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de las otras técnicas.
• Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen tamaño de la población, número de generaciones, etc.-.
• Pueden converger prematuramente debido a una serie de problemas de diversa índole.

La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pudieran ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla:

• Su espacio de búsqueda (i.e., sus posibles soluciones) debe estar delimitado dentro de un cierto rango.
• Debe poderse definir una función de aptitud que nos indique qué tan buena o mala es una cierta respuesta.
• Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora.

El primer punto es muy importante, y lo más recomendable es intentar resolver problemas que tengan espacios de búsqueda discretos aunque éstos sean muy grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de búsqueda continuos, pero preferentemente cuando exista un rango de soluciones relativamente pequeño.

La función de aptitud no es más que la función objetivo de nuestro problema de optimización. El algoritmo genético únicamente maximiza, pero la minimización puede realizarse fácilmente utilizando el recíproco de la función maximizante (debe cuidarse, por supuesto, que el recíproco de la función no genere una división por cero). Una característica que debe tener esta función es que tiene ser capaz de "castigar" a las malas soluciones, y de "premiar" a las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez.

La codificación más común de las soluciones es a través de cadenas binarias, aunque se han utilizado también números reales y letras. El primero de estos esquemas ha gozado de mucha popularidad debido a que es el que propuso originalmente Holland, y además porque resulta muy sencillo de implementar.

Como información para completar lo explicado en la secuencia sobre algoritmo genético, el desarrollo de software basados en A.G es importante para terminar de comprender la importancia de este con respecto a las búsquedas y temas anteriores, dirígete a la siguiente presentación en slideshare.

Nombre: Desarrollo de software con algorítmicos genéticos

Link: https://es.slideshare.net/uni_fcys_sistemas/desarollo-de-sofware-con-algoritmos-genticos