PDF de programación - Algoritmos Genéticos

“ Con la Ciencia por la Humanidad “



INTEGRANTES DEL EQUIPO:



01100186 HÉCTOR COSS GARCIA

01100240 ENRIQUE JARA PEQUEÑO

01100298 DAMIAN PEREA CENICEROS

01100285 FILIBERTO QUEBEDO CORTAZAR

TRABAJO: ALGORITMOS GENETICOS (EXPOSICION –

EQUIPO 5)

MATERIA: INTELIGENCIA ARTIFICIAL

MAESTRO: ING. BRUNO LÓPEZ TAKEYAS

CARRERA: ING. EN SISTEMAS COMPUTACIONALES

Nuevo Laredo, Tamaulipas a 2 de septiembre de 2005



Algoritmos Genéticos



INDICE



Introducción......................................................................... 1
Definición......................................................................... 1
Forma de Proceder................................................................ 2
Ventajas y Desventajas......................................................... 3
Limitaciones.......................................................................... 4
Como Saber si es Posible usar un Algoritmo Genético............ 5
Nacimiento de los Algoritmos Genéticos................................ 6
Codificación de los Datos....................................................... 8
Selección............................................................................... 11
Cross-Over............................................................................ 12
Mutación............................................................................... 13
Aplicaciones Reales de los Algoritmos Genéticos................... 14
Acústica............................................................................ 14
Ingeniería Aeroespacial.................................................... 14
Astronomía y Astrofísica................................................... 14
Química............................................................................ 14
Ingeniería Eléctrica.......................................................... 14
Mercados Financieros....................................................... 15
Juegos.............................................................................. 15
Geofísica.......................................................................... 15
Ingeniería de Materiales................................................... 15
Matemáticas y Algoritmia................................................. 15
Ingeniería de Sistemas..................................................... 15
Aplicaciones de Búsqueda y Optimización......................... 15
Aprendizaje Automático................................................... 15
Bibliografía y Anexos............................................................. 16





Definición

Introducción



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
cuales de ellos deben generar descendencia para la nueva generación.

Una definición bastante completa de un algoritmo genético es la propuesta
por John Koza:

(( Es un algoritmo matemático altamente paralelo que transforma un
conjunto de objetos matemáticos individuales con respecto al tiempo usando
operaciones modeladas de acuerdo al principio Darwiniano de reproducción y
supervivencia del mías apto, y tras haberse presentado de forma natural una
serie de operaciones genéticas de entre las que destaca la recombinación
sexual. Cada uno de estos objetos matemáticos suele ser una cadena de
caracteres (letras o números) de longitud fija que se ajusta al modelo de las
cadenas de cromosomas, y se les asocia con una cierta función matemática
que refleja su aptitud. ))


Versiones mas 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 en los que se requiere una gran interacción
humana para definir el modus operandi del programa.



1





Forma de proceder


Dado un problema especifico a resolver, la entrada del AG es un conjunto de
soluciones potenciales a ese problema, codificadas de alguna manera, y una
métrica llamada función de aptitud que permite evaluar cuantitativamente a
cada candidata. Estas candidatas pueden ser soluciones que ya se sabe que
funcionan, con el objetivo de que el AG las mejore, no obstante de forma
experimental se suelen generar aleatoriamente.

Luego el AG evalúa cada candidata de acuerdo con la función de aptitud. En
un acervo de candidatas generadas aleatoriamente, por supuesto, la mayoría
no funcionarían en absoluto, y serán eliminadas. Sin embargo, por puro azar,
unas pocas pueden ser prometedoras (pueden mostrar actividad), aunque
sólo sea actividad débil e imperfecta, hacia la solución del problema.

Estas candidatas prometedoras se conservan y se les permite reproducirse.
Se realizan múltiples copias de ellas, pero las copias no son perfectas; se
introducen cambios aleatorios durante el proceso de copia. Luego, esta
descendencia digital prosigue con la siguiente generación, formando un
nuevo acervo de soluciones candidatas, y son sometidas a una ronda de
evaluación de aptitud.

Las candidatas que han empeorado o no han mejorado con los cambios en su
código son eliminadas de nuevo; pero, de nuevo, por puro azar, las
variaciones aleatorias introducidas en la población pueden haber mejorado a
algunos individuos, convirtiéndolos en mejores soluciones del problema, más
completas o más eficientes. De nuevo, se seleccionan y copian estos
individuos vencedores hacia la siguiente generación con cambios aleatorios, y
el proceso se repite. Las expectativas son que la aptitud media de la
población se incrementara en cada ronda y, por tanto, repitiendo este
proceso cientos o miles de rondas, pueden descubrirse soluciones buenas del
problema.



2



Ventajas y Desventajas



• No necesitan conocimientos específicos sobre el problema que intentan

resolver.



• 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 probabilisticos, en vez de los típicos operadores

deterministicos 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,

numero de generaciones, etc.

• Pueden converger prematuramente debido a una serie de problemas

de diversa índole.

3



Limitaciones



El poder de los Algoritmos Genéticos proviene del hecho de que se trata de
una técnica robusta, y pueden tratar con sexito una gran variedad de
problemas provenientes de diferentes careas, incluyendo aquellos en los que
otros métodos encuentran dificultades. Si bien no se garantiza que el
Algoritmo Genético encuentre la solución óptima, del problema, existe
evidencia empírica de que se encuentran soluciones de un nivel aceptable, en
un tiempo competitivo con el resto de algoritmos de optimización
combinatoria. En el caso de que existan técnicas especializadas para resolver
un determinado problema, lo más probable es que superen al Algoritmo
Genético, tanto en rapidez como en eficacia. El gran campo de aplicación de
los Algoritmos Genéticos se relaciona con aquellos problemas para los cuales
no existen técnicas especializadas. Incluso en el caso en que dichas técnicas
existan, y funcionen bien, pueden efectuarse mejoras de las mismas
hibridándolas con los Algoritmos Genéticos.



4



Como Saber si es Posible usar un Algoritmo Genético



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