Estado del arte Proyecto Algoritmos Genéticos Incrementales Año 2003 Federico Dominioni Pablo Musso



Descargar 1,08 Mb.
Página1/10
Fecha de conversión10.04.2017
Tamaño1,08 Mb.
  1   2   3   4   5   6   7   8   9   10

Proyecto Algoritmos genéticos incrementales

Federico Dominioni - Pablo Musso





Estado del arte

Proyecto Algoritmos Genéticos Incrementales
Año 2003
Federico Dominioni - Pablo Musso




ÍNDICE

1 INTRODUCCIÓN 4

1.1 Objetivo 4

1.2 Definiciones y Siglas 4

1.3 Avances 4

1.4 Algoritmos Genéticos 5

1.4.1 Introducción 5

1.4.2 Computación evolutiva: 5

1.4.3 Algoritmo Genético Simple 7

1.4.4 Operadores de Selección 10

1.4.5 Operadores de Cruzamiento y Mutación 10

1.4.6 Otros Operadores Genéticos Operadores de Ordenamiento e Inversión 12

1.4.7 La base de su funcionamiento: Definiciones Previas 14

1.4.8 El Teorema de los Esquemas 15

1.4.9 Paralelismo Implícito y Desventajas de la Teoría 17

1.4.10 Como hacer para resolver mi problema con un AG 18

1.4.11 Dominancia y Diploides 19

2 Paralelismo 20

2.1 ¿Porqué paralelizar? 20

2.2 Modelo Maestro – Esclavo 21

2.3 Modelos de grano grueso 22

2.4 Modelos celulares 25

2.5 Modelos particulares 26

2.5.1 Adaptive Hierarchical Fair Competition Model for Parallel Evolutionary Algorithms: 26

2.5.2 Algoritmos genéticos incrementales: 26

2.5.3 Otros modelos 27

2.6 Conclusión final: 27

3 Bibliotecas de algoritmos genéticos 28

3.1 Introducción 28

3.2 GALLOPS 29

3.2.1 Presentación 29

3.2.2 Funcionalidades 29

3.2.3 Ventajas y desventajas 30

3.3 EO 30

3.3.1 Presentación: 30

3.3.2 Funcionalidades: 31

3.3.3 Ventajas y desventajas: 34

3.4 Galib 34

3.4.1 Presentación: 34

3.4.2 Funcionalidades: 34

3.4.3 Ventajas y desventajas: 35

3.5 PGAPACK 35

3.5.1 Presentación: 35

3.5.2 Funcionalidades: 35

3.5.3 Ventajas y desventajas: 36

3.6 GECO 36

3.6.1 Presentación: 36

3.6.2 Funcionalidades 36

3.6.3 Ventajas y desventajas: 37

3.7 SUGAL 38

3.7.1 Presentación: 38

3.7.2 Funcionalidades: 38

3.7.3 Ventajas y desventajas: 38

3.8 MALLBA 38

3.8.1 Presentación: 38

3.8.2 Funcionalidades: 39

3.8.3 Ventajas y desventajas: 39

3.9 Conclusiones finales: 39

4 Referencias 40






  1. INTRODUCCIÓN



    1. Objetivo

El documento presenta los conceptos básicos acerca de algoritmos evolutivos y en particular (y con mayor profundidad) presenta conceptos acerca de los algoritmos genéticos con el objetivo de comprender su utilidad y funcionamiento así como también familiarizarse con el vocabulario el cual es utilizado en los sucesivos documentos del proyecto. Además se presentarán a los algoritmos genéticos paralelos junto con una clasificación, lo cual es fundamental para comprender el problema planteado a resolver en este proyecto. También se presentan bibliotecas que existen actualmente en la comunidad científica para la utilización así como desarrollo de algoritmos genéticos.


Por lo cual este documento podría ser de utilidad para aquellos lectores que sin tener un gran conocimiento en el área de computación evolutiva quisieran interiorizarse en la misma así como también para aquellos lectores experimentados que quisieran informarse acerca de las actuales posibilidades reales de implementación a la hora de abordar un trabajo utilizando algoritmos evolutivos.

    1. Definiciones y Siglas







Sigla

Significado

EA

Algoritmo evolutivo

AG

Algoritmo genético

AGP

Algoritmo genético paralelo

AGS

Algoritmo Genético Simple



    1. Avances

Este documento esa estructurado en 3 capítulos, en el cual en los dos primeros capítulos se explican los conceptos más relevantes de los AG así como también sus ventajas y desventajas a la hora de paralelizar dichos modelos estableciendo una clasificación para los mismos (decimos una clasificación debido a que actualmente no existe una clasificación universal) ; finalmente en el tercer capitulo se presentan diferentes bibliotecas para trabajar con algoritmos genéticos


En el capítulo 1 introducimos al lector en los algoritmos genéticos secuenciales, de dónde provienen, la justificación de su uso, problemas ,e tc.

En el capítulo 2 nos centramos en los algoritmos genéticos paralelos. Damos una descripción de los modelos más importantes de paralelismo y algunos modelos particulares.

En el capítulo 3 nos centramos en la caracterización y descripción de diferentes paquetes (bibliotecas) de algoritmos genéticos, comentando sus ventajas y desventajas.

    1. Algoritmos Genéticos



      1. Introducción

En el presente capitulo se presentaran aquellos conceptos fundamentales sobre los algoritmos genéticos así como también se explicará mediante un poco de teoría la base de su funcionamiento.


Cabe destacar que todos los conceptos tratados en este capítulo son referidos a algoritmos genéticos secuenciales, la paralelización de dichos modelos será tratada en el capitulo siguiente



      1. Computación evolutiva:

El hombre se ha maravillado desde siempre con la naturaleza de la vida. En particular, ha sido de interés el estudio de conceptos tales como:




  • evolución de la especie

  • supervivencia del mas apto

  • competitividad

  • herencia y conformación de la descendencia.

  • Aprendizaje

Por otro lado, existe en el hombre un deseo profundo de poder reproducir la habilidad cognoscitiva por medios artificiales. El interés del hombre por comprender y estudiar como se desarrolla la inteligencia con fines de poder reproducirla con ayuda de la computadora, ha despertado la aparición de toda una rama íntegra de estudio científico llamada “Inteligencia Artificial”.


Cabe destacar que la inteligencia es solo parte del resultado del proceso de evolución de las especies. Han ocurrido cambios físicos notorios desde el primer organismo unicelular hasta el hombre.
Si bien hoy en día la teoría de Darwin es casi indiscutida en el ámbito científico, existen divergencias acerca de cómo interpretar la manera en que evolucionó la vida. La Hipótesis Pro Evolución Acumulativa es en la que se basan todos los algoritmos evolutivos. Aquí la vida se desarrolla a partir de las mejoras introducidas por la naturaleza en las generaciones pasadas, por lo que las capacidades adquiridas de generación en generación se acumulan.
De todas maneras se acepta que mutación al azar existe y ésta es tomada en cuenta , sin embargo se concuerda que ella es causante solo de pequeños cambios y que las grandes variaciones evolutivas están dadas a través de la descendencia de los individuos mas aptos, por lo cual la siguiente generación obtiene una acumulación de sus características sumadas a las propias.
El gráfico 1 muestra el patrón típico de la evolución acumulativa, como se puede apreciar algunos ejemplares heredarían las características de los padres; la evolución de éstas a largo del tiempo semejarán a una función creciente con intervalos de fuerte crecimiento e intervalos aproximadamente constantes de estancamiento relativo.

Figura 1: Patrón de la evolución acumulativa

Apoyados en esta teoría los EA buscan resolver diversos problemas a partir de una población de individuos (cada uno representando una posible solución), donde se imponen a los individuos en una situación de competitividad por su supervivencia, en la cual los ejemplares más adaptados al entorno sobrevivirán (una especie de "ley de la selva" virtual en donde sólo los fuertes sobreviven). A su vez dichos individuos bien adaptados se recombinan con otros (también bien adaptados) para formar nuevos individuos (los cuales podrían llegar a tener las características genéticas distintivas de ambos padres, lo cual

por un efecto sinérgico podría llegar a ser incluso ser mejor que la suma de las partes) quienes pasaran a formar parte de la siguiente generación.
Se impone de esta forma una estructura de generaciones en la cual a través de cada una de las mismas se transfiere el material genético hacia la próxima generación, y por lo cual cada una de las mismas debería estar un paso delante de la anterior en cuanto a su evolución. Por lo tanto en la generación final (determinada por alguna condición de finalización) se encontrarán aquellos individuos mejor adaptados, es decir las mejores soluciones (las cuales pueden ser óptimas o no)
Formalizando un poco lo dicho anteriormente y a modo de resumen, las técnicas de computación evolutiva son métodos heurísticas que sirven para atacar problemas de optimización y búsqueda (útiles cuando dichos problemas son NP) basados en los principios de evolución natural. Dichas técnicas se pueden clasificar en tres grandes categorías que son: Programación Evolutiva, Algoritmos Genéticos y Estrategias de Evolución.

De esta manera un EA basa su funcionamiento en generar aleatoriamente una población inicial de posibles soluciones, la cual a través de diferentes mecanismos irá evolucionando hasta que el algoritmo finalice (el final estará dado por algún criterio en particular, como ser cantidad de iteraciones o pasos de evolución).



Aquí se encontrará una población mas adaptada que la inicial en términos de fitness.
Los EA abarcan tres etapas fundamentales: selección, recombinación y reemplazo.
Durante la etapa de selección, se crean a una población temporal en la cual los individuos más aptos (aquellos con mayores valores de fitness en la población actual) tienen mayor cantidad de copias que el resto de los individuos (selección natural)
En una segunda etapa se aplican operadores de recombinación a los individuos en esta población originándose una nueva población.
Por último, los nuevos individuos creados substituyen a los individuos de la población original. Existen diversas técnicas de reemplazo como veremos más adelante
Cabe destacar que el algoritmo compensa entre la explotación de buenas soluciones (dadas por la selección) y la exploraciones de nuevas zonas del espacio de la búsqueda (reproducción); ya que la política del reemplazo permite la aceptación de las nuevas soluciones que no necesariamente son mejores
Es importante hacer hincapié en este momento en que los EAs son métodos heurísticos y por lo tanto no nos tienen porque brindar la solución optima al problema planteado, es más la bondad de la solución brindada al finalizar el algoritmo depende de muchos factores (como ser condición de finalización que se le impuso al algoritmo, complejidad del espacio de búsqueda, etc)
Las características en común que tienen todas las técnicas evolutivas son:


  1. Basadas en poblaciones: A diferencia de muchas otras técnicas heurísticas, se caracterizan por tener en todo momento una población de individuos




  1. No operan sobre el espacio real: Debemos construirnos un “especio de representaciones” que abstraiga al espacio real del problema a resolver a la hora de trabajar con dichas técnicas




  1. Función de fitness: Utilizan una función de adecuación (o fitness) que evalúa la bondad de cada uno de los individuos en la población, es decir con dicha función podemos saber que tan “adaptado” se encuentra determinado individuo al entorno. Dicha función coincide con la función a optimizar (maximizar o minimizar)




  1. Un mecanismo de selección para simular la supervivencia de aquellos individuos más aptos al entorno e imponer por lo tanto nuestra ley de la selva




  1. Una política de reemplazo, la cual será tomada en cuenta para saber que nuevos individuos generados formarán parte de la nueva generación. Existen muchas políticas distintas como ser generacional (toda la generación se reemplaza), elitista (el mejor individuo siempre es mantenido en la nueva generación), etc




  1. Otros operadores estocásticos, como ser mutación, cruzamiento (típico de algoritmos genéticos), híbridos que utilizan algunos de estos operadores junto con otros operadores dependientes del problema

Por último queremos mencionar que las diferencias entre las técnicas de computación evolutiva mencionadas al comienzo de la sección están dadas fundamentalmente en los operadores utilizados y en la forma en que se ejecutan las etapas de selección, reproducción y reemplazo


  1   2   3   4   5   6   7   8   9   10


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal