Índice de contenidos  

1. Applets. 4

1.2 Algoritmos genéticos. 4

1.2.1. Problema del viajante. 4

Planteamiento del problema.. 4

Descripción de la Aplicación.. 4

Funcionamiento.. 7

1.2.2 Empleo de algoritmos genéticos para resolver el problema del viajante. 8

Introducción:. 8

Modo de ejecución:. 8

1.2.3 Hola mundo. 10

Descripción:. 10

Funcionamiento:. 12

1.2.4 Algoritmos genéticos: una introducción intuitiva. 12

Consejos:. 13

Funcionamiento del applet. 14

Algoritmos Genéticos:. 15

Paisaje fractal. 15

Genitor.. 15

Recombinación.. 16

Selección.. 16

Condición de parada.. 16

1.2.5 problema del viajante. 12

Funcionamiento.. 17

1.3 Programación genética. 18

1.3.1 Aterrizando en la luna.. 18

1.3.2 Función de regresión usando programación genética.. 20

Introducción.. 20

El panel principal. ¡Error!Marcador no definido.

Ajustes para el programa genético:. 22

1.3.3 Un Applet Interactivo de camiones. 25

Descripción del problema:. ¡Error!Marcador no definido.

1.4 Teoría de juegos. 28

1.4.1. Dilema del prisionero. 28

1.4.1.1 El conteo de monedas (the coin tally). 28

Funcionamiento.. 28

1.4.1.2 co-operate (C) or defect (D):. 30

Descripción.. 30

Funcionamiento.. 30

1.4.2 Contenidos adicionales:. 31

1.5 ACO (colonia de hormigas) 33

¿Qué es?.. 33

Cómo funciona.. 33

¿Qué hace que un agente pueda elegir entre bajo, medio o alto?.. 33

Cómo usarlo... 35

1.6 ES (estrategias evolutivas) 39

¿En qué consiste?.. 39

¿Cómo utilizarlo?.. 39

Detener el proceso de evolución... 41

Botones de control. 41

Mostrar fenotipo... 42

Mostrar fenotipo... 44

1.6.1.1 Evolución de una lente de un prisma – Información del problema:. 45

Cromosoma (representación genotipo).. 46

Dibujando el cromosoma (representación fenotipo).. 47

La función de calidad... 47

Parámetros del applet.. 48

1.6.1.2 Evolución de un cuadrado mágico - Información del Problema.. 49

Dibujando el cromosoma (representación del fenotipo).. 50

Función de calidad.. 50

Parámetros del applet.. 51

Cuadrado mágico de 10x10.. 51

1.6.1.3 Evolución de un sistema de tuberías - Información del Problema.. 51

Cromosoma (Representación del genotipo).. 52

Dibujando el cromosoma (representación del fenotipo).. 53

Función de calidad.. 53

1.6.2 Animaciones de los applets anteriores. 54

1.6.3 Evolución de la mona lisa.. 57

1.7 Swarm Intelligence y SPO.. 59

1.7.1 Swarm Intelligence: Simulador del comportamiento en grupo.. 59

Funcionamiento... 61

1.7.2 Particle Swarm Optimization (PSO) Visualisation (or "PSO Visualization"). 63

Particle Swarm Optimization, una breve introducción.. 63

Acerca de este applet. 63

¿En qué consiste este applet?.. 63

Cómo usar el applet. 64

Cosas a probar.. 64

1.7.3 PSO – 3D... 66

Breve introducción de Optimización de Partículas Swam (PSO). 66

Funcionamiento del Applet:. 68

Controles:. 68

Características:. 68

Funciones de fitness disponibles:. 70

1.8 Vida Artificial 71

1.8.1 Selección Natural. 71

1.9 Metaheurísticas: 74

 

 


 

1. applets

1.2 Algoritmos genéticos

1.2.1. problema del viajante

http://www.cs.unibo.it/babaoglu/courses/cas/resources/tutorials/ga/index.html

En el menú de la izquierda, seleccionando el enlace de GA Example (TSP), podemos encontrar un ejemplo sencillo sobre la distancia más corta.

Planteamiento del problema

En el problema del viajante, conocido con las siglas “TSP”, el viajante tiene que visitar una serie de ciudades. Esta tarea realmente consiste en encontrar entre todas las ciudades por las que tiene que viajar, una secuencia que le permita recorrerlas todas de forma que reduzca al mínimo la distancia recorrida. En otras palabras, consiste en buscar un recorrido hamiltoniano mínimo en un grafo completo de N nodos.

 

descripción de la Aplicación

           En la aplicación implementada se utiliza una población con 16 cromosomas. Para la codificación de los mismos se emplea la permutación de los cromosomas. El problema del viajante (TSP) se resuelve sobre el gráfico completo (es decir, todos los nodos los nodos están conectados entre sí), con distancias euclídeas. Hay que tener en cuenta que después de añadir y borrar cualquier ciudad es necesario crear nuevos cromosomas y reiniciar el algoritmo genético conjunto.

 

Como puede verse, se puede seleccionar tanto el tipo de cruce como el tipo mutación. La descripción de su significado es la siguiente:

 

 

·      Crossover – Cruce –

 




·       Un punto – se copia la parte del primer padre (por ejemplo, el orden de las ciudades) y el resto de las ciudades se toma en el mismo orden que en el segundo padre.

 

·       Dos puntos – Se copian dos partes del primer padre y el resto de entre estas dos partes se toman en el mismo orden que en el segundo padre.

 

·       Ninguno – No se produce ningún tipo de cruce, la descendencia es una copia exacta de los padres.



·      Mutación

 



 

·       Aleatorio (random) normal – Unas pocas ciudades son elegidas e intercambiadas

 

·       Aleatorio, sólo para mejorar la mutación - algunas ciudades son elegidas al azar e intercambiadas únicamente si la solución mejora (aumenta el valor de fitness)

 

·       Sistemática, sólo para mejorar la mutación - las ciudades son elegidas de forma sistemática e intercambiadas solo si la solución mejora (aumenta el valor de la función fitness)

 

·       Mejora aleatoria - igual que la anterior, realizando previamente el primer tipo de mutación.

 

·       Mejora sistemática - lo mismo que "sistemática, sólo para mejorar la mutación", pero realizando antes el primer tipo de mutación.

 

·       Ninguno – No se emplea ningún tipo de mutación.


Funcionamiento 

 

El applet que se está describiendo emplea algoritmos genéticos para optimizar el problema del viajante. El botón “Change View” (Cambiar Vista) permite, como su propio nombre indica, visualizar la ejecución y resultados de toda la población, o bien, únicamente, la que mejores resultados obtiene. En este último modo se aprecia mejor las características y funcionamiento del algoritmo. Se ofrece la posibilidad de agregar o quitar ciudades haciendo clic en el gráfico (independientemente de que la aplicación se encuentre parada o en ejecución). Después de añadir o eliminar ciudades se mostrará un recorrido aleatorio, con la menor distancia posible, que una todas ellas. Además se creará una población aleatoria con nuevos cromosomas. Hay que tener en cuenta que se está resolviendo un algoritmo de TSP sobre un grafo completo. Es recomendable ejecutar el algoritmo genético modificando los parámetros (diferentes tipos de cruce y mutación), y observar los cambios en el rendimiento (así como en la velocidad – añadir ciudades para comprobarlo).

 

 

Para comenzar a ejecutar la aplicación, basta con pulsar el botón “Start”, si se quiere que la aplicación realice toda la ejecución ininterrumpidamente, o el botón “Step” si se quiere ir paso a paso (habrá que pulsarlo de manera reiterada hasta encontrar una solución, por lo que esta opción es menos práctica de cara a ver los resultados). En un recuadro a la derecha se muestra el número de generaciones necesarias para resolver el algoritmo. Para finalizar la ejecución basta con pulsar “Stop”. Si se pulsa nuevamente el botón “Start” la aplicación continuará la ejecución en el mismo punto en que se detuvo. Si se desea reiniciar el algoritmo, será necesario pulsar el botón “Restart”, que organizará las ciudades y sus caminos de manera aleatoria, manteniendo el mismo número de ciudades que hubiere antes de ejecutar la acción.

La opción “Numbers” permite mostrar los números que identifican las ciudades. Así sabremos la cantidad de ciudades existentes en el problema, proporcional a la complejidad de resolución del mismo.

 

Software requerido para su ejecución:

 

Se requiere disponer de una versión relativamente actualizada de Java en el navegador, con independencia del sistema operativo empleado.



o   Fallo conocido: Si está utilizando versiones antiguas de Java en Netscape, por favor presione el botón "Cambiar vista" antes de realizar cualquier otra cosa, para comprobar si puede visualizar correctamente los gráficos. Si no aprecia una visualización correcta en este punto, algunos gráficos no responderán.

 

1.2.2 empleo de algoritmos genéticos para resolver el problema del viajante

http://www.heatonresearch.com/articles/65/page1.html

 

introducción:

Los algoritmos genéticos simulan la genética y la evolución. La solución a un problema es visto como una "forma de vida", o "cromosomas". A partir de entonces, se crean muchas soluciones. Las mejores soluciones para vivir se emparejan con otras soluciones óptimas. Por lo tanto, toda la población evoluciona gradualmente a una solución ideal.

El "Problema del viajante" (TSP) es un problema común aplicado a la inteligencia artificial. El “TSP” presenta un número de ciudades que obliga al ordenador a calcular la ruta óptima entre ellas (entre las ciudades). En esta aplicación se utiliza un algoritmo genético para producir una solución al clásico “Problema del Viajante”.

 

modo de ejecución:

1.     Introducir el número de ciudades que el viajante debe atravesar.

2.     Introducir el tamaño de la población. Una población de 1000 individuos es buena para 50 ciudades. Introduzca una población demasiado reducida no permitirá encontrar solución.

3.     Introducir el porcentaje de mutación, esto es, el porcentaje de la población que será mutada, siendo éste un número aleatorio introducido en la estructura genética.

4.     Hacer clic en el botón “Start”, y ver al algoritmo genético tratar de encontrar el camino óptimo.

 

A continuación se muestra un ejemplo de ejecución, habiendo modificado algunos parámetros. En la segunda imagen, se muestra la solución alcanzada al problema planteado, mostrando sobre la interfaz el número de generaciones, coste y mutaciones.

 

 

1.2.3 hola mundo

 

Descripción:

En este applet se emplean algoritmos genéticos para resolver varios tipos de problemas;  una ecuación diofántica, una evolución de la frase "Hello World!" y el problema del vendedor ambulante. El applet lista el mejor miembro de la  población actual, así como dibujar un gráfico del mejor y de la media de la adecuación del GA: http://www.generation5.org/jdk/demos/gaApplet.html

 

Hello world

Consiste en evolucionar la frase “Hello World”, comenzando por una frase aleatoria (este es un ejemplo obtenido durante la ejecución del programa: “<V}~w:O?`}d/”), que por lo general no tiene significado, formada por un conjunto de 12 caracteres de cualquier tipo. Esta frase irá evolucionando hasta conseguir formar las palabras citadas.

A continuación pueden verse algunos ejemplos de la salida (se muestra el mejor miembro de la población, precedidos por el número de la generación en la que se encuentra). En el ejemplo mostrado han sido necesarias 280 generaciones para conseguir las palabras bien formadas.

 

1: <V}~w:O?`}d/

5: Jcb~w:ih`<l'

7: Jcb~w:i`}d#

9: Jcb~w:Oh`}d/

10: Jcbuw:Oh`}d/

11: Jcb~w:Oh`b^#

57: Jcgtt5Wkced#

58: Iegtt5Xkbed#

117: Hellp4Wofid!

120: Hellp4Wofjd!

246: Hello#World!

263: Hello"World!

268: Hello!World!

282: Hello World!

 

Podemos encontrar más información sobre este algoritmo – tanto en inglés como en castellano- , así como un ejemplo de su codificación, en esta otra página:

http://vidaartificial.com/index.php?title=%22Hello_World!%22_un_ejemplo_de_Algoritmo_Genetico_%28Generation5.org%29

 

Solución a la ecuación diofántica:

Se llama ecuación diofántica a cualquier ecuación algebraica, generalmente de varias variables, planteada sobre el conjunto de los números enteros \mathbb{Z}o los números naturales \mathbb{N}, es decir, se trata de ecuaciones cuyas soluciones son números enteros. Utilizando un algoritmo genético se tratará de llegar a una solución que resuelva la ecuación.

A continuación explicamos un ejemplo obtenido de una de las ejecuciones. Como puede verse, el problema trata de solucionar la ecuación 5a + 3b + c - d + 2e + 6f = 124, donde a, b, c, d, e y f son números enteros tanto positivos como negativos. La solución mostrada tras la ejecución es la siguiente:

 

1: 5(65) + 3(396) + 1(136) + -1(-10) + 2(243) + 6(-364)

2: 5(-145) + 3(-105) + 1(369) + -1(-225) + 2(259) + 6(1)

3: 5(-120) + 3(-394) + 1(312) + -1(176) + 2(-88) + 6(323)

7: 5(-120) + 3(-394) + 1(312) + -1(176) + 2(-88) + 6(324)

13: 5(-120) + 3(-395) + 1(312) + -1(176) + 2(-86) + 6(324)

18: 5(-120) + 3(-394) + 1(312) + -1(178) + 2(-86) + 6(324)

 

Puede verse más información en esta página:

http://www.generation5.org/content/1999/gaexample.asp

 

Problema del viajante:

El último de los algoritmos que pueden seleccionarse es el del problema del viajante. Si tenemos en cuenta el primer punto de este documento, no puede apreciarse bien el funcionamiento del mismo. Simplemente se muestran las ciudades por las que pasa y la distancia entre ellas. Además, la ejecución del mismo nunca termina.

A continuación puede verse una traza de un ejemplo de ejecución:

 

1: 9 -> 10 -> 8 -> 5 -> 3 -> 12 -> 15 -> 14 -> 13 -> 11 -> 7 -> 0 -> 6 -> 1 -> 4 -> 2 -> [length=630.9925734957264].

2: 8 -> 3 -> 9 -> 5 -> 6 -> 4 -> 10 -> 12 -> 13 -> 0 -> 14 -> 15 -> 11 -> 1 -> 7 -> 2 -> [length=619.1181160193219].

3: 8 -> 2 -> 3 -> 15 -> 4 -> 14 -> 11 -> 13 -> 10 -> 5 -> 9 -> 7 -> 12 -> 1 -> 6 -> 0 -> [length=554.8650486925985].

4: 8 -> 2 -> 9 -> 5 -> 3 -> 4 -> 15 -> 14 -> 13 -> 11 -> 10 -> 0 -> 6 -> 1 -> 12 -> 7 -> [length=550.9939631506631].

574: 11 -> 10 -> 9 -> 3 -> 5 -> 8 -> 2 -> 0 -> 7 -> 15 -> 14 -> 4 -> 6 -> 1 -> 12 -> 13 -> [length=396.04387571553013].

575: 11 -> 10 -> 9 -> 3 -> 2 -> 8 -> 5 -> 0 -> 7 -> 15 -> 14 -> 4 -> 6 -> 1 -> 12 -> 13 -> [length=382.2726365813494].

583: 12 -> 10 -> 9 -> 3 -> 8 -> 2 -> 5 -> 0 -> 7 -> 15 -> 14 -> 4 -> 6 -> 1 -> 11 -> 13 -> [length=381.6784807357226].

594: 11 -> 10 -> 9 -> 3 -> 8 -> 2 -> 5 -> 0 -> 7 -> 15 -> 14 -> 4 -> 6 -> 1 -> 12 -> 13 -> [length=379.5010179313449].

 

Funcionamiento:

Se selecciona el problema que se pretende resolver de la lista desplegable y, tras pulsar el botón “start”, comienza la ejecución del programa. La mejor aptitud se representa en verde, la aptitud promedio en rojo. Hay que tener en cuenta que, en el problema del Viajero no tiene solución, por lo que continuará indefinidamente. Para finalizar la ejecución basta con pulsar el botón “stop”.

 

1.2.4       algoritmos genéticos: una introducción intuitiva

http://www.glauserweb.ch/gentore.htm

 

Este applet de Java muestra el principio de un algoritmo genético (GA).


           En primer lugar, se construye un paisaje fractal. Se puede iniciar este paisaje pulsando el botón Landschaft (= paisaje, en alemán). Los algoritmos genéticos tratan de encontrar el punto más alto del paisaje evaluando el menor número de puntos posible, es decir, intentan medir la altura del paisaje con tan solo unos pocos puntos. Esto se hace con una población de unos 100 bugs (individuos/insectos) distribuidos al azar en el paisaje (pulsar el botón de Population. El lugar donde se situará el insecto (las coordenadas) está en su código genético (los individuos permanecen inmóviles), la altura del lugar que ocupan en el paisaje es su función de fitness.


           Es en este momento cuando se realizan, alternativamente, los dos pasos de los Algoritmos Genéticos, la recombinación y la selección: la recombinación selecciona aleatoriamente dos individuos como padres, prefiriendo los que tienen alta aptitud. En algún lugar del paisaje en el que se sitúan los padres, nace la descendencia y se añade a la población. La selección elimina de la población el individuo con menor, para volver al número original de individuos.

 

      La evolución puede ejecutarse en un solo paso (single-step-mode) o en el modo de ejecución normal: al presionar el botón de Rekombination / Selektion (que cambia su etiqueta después de cada paso) se dispara el siguiente paso, que es animado. El botón Go inicia la ejecución. En este modo de ejecución, los nuevos descendientes se destacan en seguida. Se puede cancelar el modo de ejecución pulsando el botón Abbrechen (Cancelar).


           El algoritmo genético finaliza cuando todos los individuos se sitúan a la misma altura. Su resultado es la altura alcanzada por los individuos de la población, en comparación con la altura máxima absoluta del paisaje. El recuento de medidas llevados a cabo (el número total de individuos durante la ejecución) tiene que realizarse teniendo en cuenta el número de puntos del paisaje, 120.000.

 

Consejos:

            * El applet puede mostrar la altura de los paisajes sólo hasta 255. Las cumbres más altas simplemente son truncadas, lo que conduce a las zonas blancas. Si en el paisaje se ha construido una gran cantidad de áreas blancas, se debe construir uno nuevo con el botón Landschaft. (Si la construcción del paisaje está todavía en curso, tiene que cancelar primero pulsando el botón “Abbrechen”).

            * La población tiende hacia el centro: debido a que las nuevas crías nacen siempre entre sus padres, nunca se toca el área más allá de los límites de la población. Las cumbres en las fronteras del paisaje son, por lo tanto, más difíciles de encontrar por los algoritmos genéticos que aquellas situadas en el centro. Una solución sería que no existiesen las fronteras. (Por supuesto, esto sólo funciona de forma virtual. No hay modo de sobrevivir a tal tratamiento.) De esta manera, son posibles las recombinaciones sobre los límites del paisaje. El inconveniente sería una pérdida de la simplicidad (y la necesidad de algún tipo de animación).

             * Los algoritmos genéticos son sensibles al tamaño de la población, difícil de definir en los paisajes de formas desconocidas. Si se comienza con una población muy pequeña, las individuos se concentran en un único punto, antes incluso de haber encontrado la altura de la cumbre más alta (convergencia prematura). Se puede ejecutar poblaciones de diferentes tamaños en el mismo paisaje y comparar los resultados. El tamaño de la población se puede modificar en el campo situado a la izquierda del botón Population, donde se puede insertar el número que se considere más adecuado.

funcionamiento del applet

Landschaft (=paisaje )

 

Construye un nuevo paisaje. Se descarta una población que sea eventualmente existente. Sólo funciona si el paisaje no se está construyendo en ese momento.

 

Abbrechen (=cancelar)

Cancela la construcción de un paisaje o la ejecución de la evolución, respectivamente.

 

Población

Crea una nueva población con el tamaño indicado en el campo de la izquierda del botón. Se considera un tamaño razonable el rango comprendido entre los 20 y 200 individuos. Con poblaciones más grandes, el cálculo se hace demasiado pesado, conlleva demasiado tiempo (pues también depende del hardware, se puede introducir un tamaño alto y cancelar la ejecución para encontrar el tamaño razonable para su equipo).

Rekombination / Selektion

El botón cambia su etiqueta dependiendo del próximo paso. Al presionar el botón realiza y anima el paso.

Go

Comienza la ejecución. Con la barra de desplazamiento se permite controlar la velocidad de cálculo.

Statusline (parte izquierda)

Contiene la información sobre el paisaje: x e y son las coordenadas del puntero del ratón, h es la altura del paisaje en este punto, el máximo es el punto más alto del paisaje.

 

Statusline (parte central)

Contiene la información sobre la población: N es el número de individuos = tamaño de la población, máx. la altura de individuo con máxima altura, Gen (generaciones) el recuento de los individuos. Para ser claros, resume el tamaño de la población inicial más todos los descendientes calculados desde el principio.

Statusline (parte derecha)

Indica el estado del applet y muestra una sugerencia de qué hacer a continuación.

 

 


          

 

 

 

 

 

 

 

 

 

Algoritmos Genéticos:

Los algoritmos genéticos (AG) son una técnica matemática, basada en la teoría de la evolución de la naturaleza. Ayuda a encontrar soluciones para problemas que no se pueden calcular exactamente, y tiene que buscarse por prueba y error.

 

  Paisaje fractal

La construcción del paisaje fractal se basa en la teoría de Benoît Mandelbrot, ver La geometría fractal de la naturaleza, WH Freeman and Company, Nueva York.

El applet permite visualizar la altura de un punto por su color: del negro sobre verde y azul a blanco, cuanto más brillante sea el color más alto será el punto.

Para producir paisajes interesantes, se comienza por poner 128 pirámides de dos alturas diferentes en un área de 400 por 300 puntos. Por cada paso consecutivo, la altura de las pirámides se reducen a la mitad, y su número es multiplicado por cuatro. Eso hace que para el segundo paso haya 8 pirámides de una altura de 64. Esto continúa hasta que las pirámides tienen una altura de 1 en el último paso. Después de cada paso, el paisaje se vuelve a dibujar y así consiguen cada vez más detalles.

 

Genitor

El tipo de algoritmos genéticos empleado fue descrito por primera vez por Whitley (1988, 1989) y recibe el nombre de “Genitor”. Es muy adecuado para paisajes con fractales. La descendencia nacida de padres con elevados valores de fitness (situados en lugares altos en el paisaje), da lugar a áreas con una mayor lucha entre sus individuos. Al comienzo, los algoritmos genéticos realizan su búsqueda sobre todo el paisaje, pero a medida que avanza la ejecución, ésta se centra en puntos elevados, cercanos a las colinas, donde se concentran los individuos con mejor fitness.


           Existen muchos tipos de algoritmos genéticos.
La mayoría de ellos tienden a sustituir a todos los padres de las crías en cada generación. En comparación con los algoritmos, el generador es simple de programar. Hay un gran número de posibilidades para seleccionar a los padres para la recombinación. Los diferentes tipos de recombinación (uno o dos puntos de cruce, con o sin mutaciones espontáneas) y muchas posibilidades para seleccionar a los individuos a suprimir.


           La analogía entre nuestro modelo y la evolución es evidente: Las coordenadas de un error corresponde a su código genético. Se compone de dos genes, que van de 0 a 299 y 0 a 399, respectivamente. El código genético de la descendencia es una combinación aleatoria de los de sus padres. Toda la evolución de nuestro modelo se basa, pues, en la recombinación de una población inicial generada aleatoriamente. Como se indicó anteriormente, podría construirse fácilmente un mecanismo de mutación que crearía nuevas marcas distintivas.

 

Recombinación

           Para la recombinación, todos los insectos están ordenados en una lista de alturas ascendentes. En la selección de la recombinación, el ranking de esta lista tiene más valor que la función de fitness. Por tanto, la presión de la selección se mantiene incluso si la población está situada en una colina y la diferencia de las alturas de los individuos disminuye.

           La nueva descendencia se distribuye de manera uniforme en algún lugar del paisaje, donde también se encuentran sus progenitores. La probabilidad de haber nacido en una casilla arbitraria es de 1/100, y del rectángulo entero es siempre 1 / 100, independientemente de la ubicación real de la celda dentro del rectángulo.

 

Selección

La probabilidad de que un insecto dado se quede fuera de la población seleccionada es inversamente proporcional a su fitness. En este paso, se considera la aptitud el fitness a alcanzar.

Condición de parada

 

1.2.5       problema del viajante

Descripción del problema: Encontrar la distancia más corta que recorra todas las ciudades (camino hamiltoniano). Se puede encontrar en el siguiente enlace: http://www.insisoc.org/problema_del_viajante__algoritmos_geneticos_-_ox_.html

 

 

Funcionamiento

Antes de comenzar a ejecutar la aplicación, podemos ajustar los parámetros de los algoritmos genéticos, tales como el tamaño de la población, que puede variar de 0 a 1000, el factor de mutación (con valores comprendidos entre 0 y 1), la probabilidad de cruce (también entre 0 y 1, obviamente) y el número de iteraciones, con 10000 valores posibles a elegir. Para fijar estos parámetros, basta con desplazar la barra de desplazamiento roja situada en la parte derecha de la aplicación, sobre cada uno de dichos parámetros. También

1.3 programación genética

 

1.3.1 ATERRIZANDO EN LA LUNA

La programación genética se puede utilizar para encontrar programas de ordenador inspirados en la evolución biológica. Es una máquina de aprendizaje de la técnica que utiliza un algoritmo evolutivo para optimizar una población de programas de ordenador de acuerdo con una función de fitness. En el proceso de búsqueda se utilizan el cruce y la mutación para generar nuevos programas.

            En resumen, el proceso comienza con una población aleatoria de programas. Cada programa es evaluado y convertido en puntuación. De esta población se generan nuevos programas mediante cruce y mutación. Los nuevos programas son evaluados y reemplazan programas existentes si el nuevo programa resuelve mejor el problema.

          La demo encuentra soluciones para aterrizar en la luna. Inicialmente, el astronauta está flotando a 100 metros sobre la superficie. La gravedad de la luna tira hacia abajo de la nave, por lo que dando impulso se puede aterrizar de manera controlada. Hay que tener en cuenta que sólo se dispone de una cantidad disponible de combustible.


           Para verlo en acción, primero hay que seleccionar los parámetros de ejecución. Al hacer click en “nuevo”, se genera una población aleatoria. Puede verse la salida de cada programa al pulsar en el botón “show”. La búsqueda real comienza al pulsar el botón “Go”. Y continuará hasta pulsar el botón “Pause”.

 

Los parámetros de ejecución existentes permiten las siguientes opciones:

·      Minimizar la velocidad de aterrizaje.

·      Reducir al mínimo la velocidad de aterrizaje (si v>5) y ahorrar combustible. Siendo v la velocidad de la nave.

·      Reducir al mínimo la velocidad de aterrizaje (si v>5) y quemar tanto combustible como sea posible.

·      Reducir al mínimo la velocidad de aterrizaje (si v>5), pero aterrizar rápidamente.

·      Maximizar la velocidad de aterrizaje.

 

Los parámetros genéticos son:

·      Population: tamaño de la población. Se permite un tamaño de 10, 20, 50 o 100 individuos.

·      Los operadores permitidos son: la combinación de los operadores básicos (suma, resta, multiplicación y división) y la combinación de estos mismos operadores con el seno, logaritmo, exponencial, y raíz cuadrada.

·      Mostrar altura: permitiendo como valores máximos el 5, 10 y el 20.

 

A continuación mostramos una captura de la aplicación, tras haber seleccionado una población de 100 individuos, con un top de 20, todos los operadores posibles y la opción de maximizar la velocidad de aterrizaje. Puede verse la puntuación y la fórmula empleada en la función de fitness.

 

 

 

1.3.2 función de regresión usando programación genética

Se puede descargar el applet y obtener información técnica sobre él y su funcionamiento en http://alphard.ethz.ch/gerber/approx/technical.htm

 

Introducción

 

 

 

Ajustes para el programa genético:

           Es posible inspeccionar o cambiar algunos parámetros del programa genético en el cuadro de diálogo Settings. Basta con pulsar dicho botón para abrir una ventana que permita la configuración de estos parámetros.

Hay que tener en cuenta que no se podrá cambiar la configuración del programa mientras éste se encuentre en ejecución. Por tanto, dicho botón únicamente cuando se detiene el programa.

 

 

·       Nota: La información que se va a mostrar a continuación puede encontrarse en inglés al seleccionar la opción ayuda (help) situada en la parte superior izquierda de la interfaz del applet, además de información técnica q se precise en la opción (Technical information) situada a la derecha del anterior.


 

Breve explicación de los ajustes de configuración

Tamaño de la población

Número de individuos (por ejemplo, los programas de síntesis) en la población. Cada generación tiene el mismo número de individuos.

Max. profundidad para nuevos individuos

La profundidad máxima de los árboles del programa para nuevos individuos.

Función de cruce

Función de reproducción

Función de mutación

 

Cuando se produce una nueva generación, se generan nuevos individuos a partir de la población anterior, mediante tres métodos diferentes:

    * Cruce de dos padres, produciendo una descendencia de dos crías.
    * Reproducción de un solo padre, que produzca una descendencia.
    * Mutación de un solo padre, que produzca una descendencia.
El ratio de los números de fracción determina el ratio de los métodos elegidos.

Max. profundidad de los individuos después del cruce.

Es el árbol de profundidad máxima para los programas producidos por el cruce. Si un descendiente supera este límite, se elegirá a uno de los padres.

Max. profundidad para los nuevos subárboles en las mutaciones.

La profundidad máxima de los subárboles que se obtienen en la mutación.

Método de generación

Determina el método de la forma de generación de los árboles de programa en la población inicial:

    * Crecer produce árboles aleatorios tupidos que no excedan una profundidad máxima. La distancia desde la raíz hasta los nodos terminales varía de forma aleatoria.

    * Completo produce árboles totalmente equilibrados. La distancia desde la raíz a cualquier nodo terminal es la misma.

    * Rampa media y la otra mitad es una mezcla entre el Progreso y el método completo. La mitad de los árboles están bien equilibrados y la otra mitad se crean tupidos. La profundidad máxima varía entre un mínimo (normalmente 2) y el valor máximo que se establece con Max. de profundidad para los individuos por encima de nuevo.

Método de selección

Determina el método de cómo los padres se seleccionan para criar una nueva generación:

·      Proporción de Fitness prefiere los individuos más competidores como padres. El individuo más competidor es el más probable que sea elegido como padre.

·      El torneo se selecciona el padre más apto, más competidor (s) de entre un grupo de individuos elegidos al azar.

Casos de Fitness

Estas son las muestras de la función objetivo que estamos tratando de aproximar. Los casos de fitness son una serie de pares de valores x-y (x es la variable independiente, e y es el valor de la función).

Para introducir cualquier otro caso de fitness, será necesario teclear los nuevos valores o pegarlos desde el portapapeles.

También es posible integrar líneas de comentarios. Las líneas de comentario comienzan con "//".

Debe introducir al menos 10 pares de valores x-y.

Establecer la función

Las funciones son los nodos internos de los árboles del programa.

El algoritmo utiliza sólo las funciones que se han seleccionado de la lista.

Se debe seleccionar al menos un elemento.

Establecer el terminal

Los terminales son las hojas de los árboles del programa.

El algoritmo utiliza únicamente las terminales que se han seleccionado de la lista.

Se debe seleccionar al menos un elemento.

 


 

1.3.3. Un Applet Interactivo de camiones 

La tarea del problema del camión puede ser descrita como sigue: Un camión se posiciona en una posición arbitraria (x,y) sobre una superficie con un ángulo arbitrario de la cabina cabt y un ángulo arbitrario del trailer trailert (como se muestra en la figura de abajo). El camión se mueve a una velocidad constante hacia atrás. La meta es determinar un controlador que procese el ángulo de dirección del camión u teniendo en cuenta la posición actual, de manera que el camión se dirija al muelle de carga en la posición (0,0). Por lo tanto, se busca una dependencia funcional de la función: u = g(x,y,cabt,trailert): http://www.handshake.de/user/blickle/Truck/index.html

 

truck

Las funciones que se pueden usar para el controlador de la dirección son:

PLUS(a,b) 

devuelve a+b

MINUS(a,b) 

devuelve a-b

MUL(a,b) 

devuelve a*b

DIV(a,b) 

devuelve a/b, si b <> 0, entonces 1

ATG(a,b) 

devuelve atan2(a,b), si a<> 0, entonces 0

IFLTZ(a,b,c) 

devuelve b, si a<0, Entonces devuelve c

 

Existen varias aproximaciones para resolver el problema. La primera solución se presenta en [2] utilizando redes neuronales. Koza describió los primeros experimentos con Programación Genética para solucionar esta tarea [1].

Applet de un camion interactivo

Una simple demostración del problema del camión con una función de control que deriva del método de optimización de programación genética se encuentra en la parte de la izquierda de la imagen.

El panel de control permite variar el tamaño del step y la velocidad de la simulación. Además muestra la función que dirige el camión. Actualmente esta fórmula no es editable (a lo mejor en el futuro se permite al usuario introducir la que quiera). Se puede hacer click donde se quiera y el camión iniciará el movimiento desde esa posición. Manteniendo el botón pulsado puedes ajustar el ángulo de comienzo.

Obsérvese que ésta es solo una solución al problema, probada solo para un pequeño número de posiciones en la rejilla. Es la primera solución que el sistema de Programación Genética encontró.

 

A continuación mostramos un ejemplo de la ejecución:

 

 


 

Y finalmente un ejemplo una vez encontrada la solución:

 

 

 

 

 

 

 

 

 

 

Si se elige una posición inicial del camión cercana a los límites del grid, puede no encontrarse solución, pudiendo provocar un accidente el camión:

 

 

 

 

 

 

 


 

1.4 TEORÍA DE JUEGOS

1.4.1. dilema del prisionero

http://serendip.brynmawr.edu/cgi-bin/pdilemma.perl

1.4.1.1 el conteo de monedas (the coin tally)

El “dilema del prisionero” es un juego que ha sido y continúa siendo estudiado por las personas en una variedad de disciplinas, que van desde la biología, así como la sociología y la política pública. Entre sus características interesantes se puede citar que es un juego de tipo "no-suma-cero": la mejor estrategia para un jugador determinado es a menudo uno que aumenta la rentabilidad de la pareja también. Además se ha demostrado que no hay una única "mejor" estrategia: cómo maximizar nuestra propia ganancia depende de la estrategia adoptada por la pareja. Serendip utiliza una estrategia particular (llamada "ojo por ojo"), que se cree que es óptima en el conjunto más amplio posible de las estrategias de los socios.

Una excelente introducción al dilema del prisionero, incluyendo tanto los estudios originales de las estrategias y la discusión en un significado más amplio del juego es el libro de Robert Axelrod en La Evolución de la Cooperación (Basic Books, NY, 1984). A debate popular más reciente es el dilema de W. Poundstone presos Anchor Books, Doubleday, NY, 1993). Aún más reciente es "La aritmética de Ayuda Mutua", de Martin Nowak, Robert M. May, y Karl Sigmund, publicado en Scientific American (junio, 1995, pp 76-81).

Hay también una referencia de Internet en el dilema del prisionero ', de los Principios Cibernéticos y una exploración Web más elaborada de las opciones de interacción social en el Encuentro de Pat juego.

También está disponible en la web un libro de texto abreviado en la teoría de juegos, que incluye una descripción del dilema del prisionero.

 

Funcionamiento

El funcionamiento del juego se basa en las siguientes reglas:

1) En cada turno del juego, el jugador y Serendip deberán elegir, sin conocer la elección del otro, entre cooperar mutuamente o tratar de sacar provecho el uno del otro.

2) Después de cada cambio de turno, el jugador y Serendip recibirán, respectivamente, un cierto número de monedas de oro. Este número dependerá de cada una de las decisiones tomadas por ambos.

3) En caso de que ambos decidan cooperar, cada uno recibirá 3 monedas de oro.


           4) Si alguno se decide a cooperar, pero el otro ha optado por la competencia, el competidor exitoso recibirá 5 monedas de oro y el cooperador no ganará ninguna.

5) Finalmente, si ambos deciden superarse unos a otros, cada uno recibirá solamente una moneda de oro.

Las posibilidades de sobrevivir al jugar en el siguiente turno están estrechamente relacionadas con el número promedio de monedas que se han recibido en los turnos anteriores.

Para jugar al juego, basta simplemente con seleccionar uno de los dos comportamientos descritos previamente (cooperar o competir, y pulsar el botón de “Play it” para jugar una ronda.

Cooperate, or Compete



 

1.4.1.2 co-operate (C) or defect (D):

 

http://www.economicsnetwork.ac.uk/archive/poulter/pd1.htm

descripción

 

         El Dilema del Prisionero es un juego donde en el que se puede jugar con otro jugador al mismo tiempo, eligiendo entre dos comportamientos: cooperar (C) o retirarse (D). Esto da lugar a cuatro posibles resultados, cada uno con un pago diferente, como se muestra en la tabla (los números de superíndice son los pagos del oponente).

 

 

Other Player

C

D

You

C

3 3

0 5

D

5 0

1 1

 

 

funcionamiento


• Nadie quiere obtener la puntuación de cero puntos; que tienen su cooperación explotada por el otro jugador.

 

• Si ambos seleccionan el comportamiento Retirarse, ninguno de los dos es tonto, pero ninguno de los dos obtiene el beneficio de la cooperación (1 pt).


• Si ambos cooperan, ambos pueden ganar una cantidad razonable (3 puntos). Esta opción es la mejor para el bien común, pero no para quien juega.


• Sin embargo, la mejor opción para uno mismo es seleccionar el comportamiento Retirarse, y hacer que el otro jugador coopere: esto permite obtener una puntuación de 5 puntos.


         El objetivo del juego es maximizar el número de puntos que se pueden obtener. Si se quiere vencer al otro jugador, o tratar de maximizar el número total de puntos ganados, lo convierte, efectivamente, en un juego diferente. El dilema del prisionero es más interesante cuando se trata de un juego entre egoístas. La ganancia de 3 puntos de la cooperación puede ser agradable, pero no es tan tentador como obtener los 5 puntos de la tabla en el botón de la izquierda de la pantalla.

 

Cada persona tiene varias oportunidades para cooperar respectivamente, de manera que se podrá jugar al juego un número consecutivo de veces; por ejemplo 20 rondas. De la tabla de pagos, debe quedar claro que la puntuación más alta que se puede obtener en 20 rondas de este juego es de 100 puntos, pero a menos que el otro jugador sea “total y absolutamente imbécil” , es prácticamente imposible que esto ocurra.

ejemplo

 

 

Mirando otra vez a la tabla de pagos, es posible darse cuenta de que si otro jugador coopera, será mejor “retirarse”, haciéndole a él imbécil. Entonces otra vez si el otro jugador se retira, será mejor volver a seleccionar el comportamiento “retirarse”, para evitar ser el imbécil. Por lo que siempre será mejor jugar con 'D', sin importar lo que suceda. Esa es la estrategia que conllevará a la más alta puntuación en el juego.

 

La razón para seleccionar el comportamiento “Defecto” parece clara y sencilla. El problema es que ambos jugadores vean este racionamiento, pues ambos se retirarán, obteniendo un punto por ronda; mucho menos que si hubieran cooperado.

 

Aquí hay un rompecabezas que exige un vistazo más en profundidad; si lo lógico es retirarse siempre, ¿por qué el razonamiento nos llevaría a cooperar?

 

Hacer un símil con la vida real: si se rompe una promesa, aprovechándose siempre de la gente cuando se tiene oportunidad, pronto se perderán todos los amigos, lo que restringirá seriamente las cosas que se podrán hacer. Retirarse en la vida real no sería razonable, porque el resto de la gente responde a tus acciones, y no responderán bien a la retirada.

1.4.2 Contenidos adicionales:

http://www.gametheory.net/resources.html
http://www.gametheory.net/applets/evolution.html

 

En este último enlace podemos encontrar los siguientes contenidos:

 

Evolution of cooperation (Evolución de la cooperación)
Simula el éxito obtenido mutando a una población jugando al dilema del prisionero contra la población establecida.

Eric Klopfer

Spatial iterated prisoner's dilemma (Dilema del Prisionero)
Simula la evolución de la cooperación o deserción debido a la interacción local entre jugadores en un grid.

Serge Helfrich

Evolutionary Approach to Norms (Aproximación evolutiva de las normas)
Una simulación personalizable de la evolución del modelo las normas socials de Axelrod con una discusión relatada y clases en Java.

Luis R. Izquierdo, José M. Galán

Multiplayer iterated prisoner's dilemma (Dilema del prisionero multijugador)
Simula la evolución de la cooperación o deserción en varias estrategias basadas en la población inicial.

Uri Wilensky

Game of Life  (Juego de la vida)
Un simulador muy simple del Juego de la vida de Conway.

Andreas Ehrencrona

Game of Life (Juego de la vida)
Simulación del juego de Conway que incluye varias configuraciones iniciales interesantes.

Edwin Martin

Game of Life (Juego de la vida)
Un personalizable simulador del juego de la vida.

Dan Freeland

Fire experiment (Experimento de fuego)
Una simulación especial de contagio mediante la demostración de la propagación de los incendios forestales.

Kyle Siegrist

Ecological evolution  (Evolución ecológica)
Representa gráficamente la evolución de diferentes estrategias que se seleccionan cuando se juega arbitrariamente a juegos de 2x2

© LIFL

Hawks vs. doves evolution (Evolución de los halcones vs. Palomas)
Un applet que simula la relaiones sociales entre halcones (que lucha por los recursos) y palomas (que no). Altamente personalizable.
Kenneth N. Prestwich

Evolutionary Network Traffic Simulator (Evolucionando un simulador de la red de tráfico).
Un applet para la simulación de la evolución y las características del tráfico y los atascos.

Simon Fischer

 

 

1.5 aco (colonia de hormigas)

¿QUÉ ES?

    Este ejemplo es una réplica del modelo desarrollado por Robert Axtell, Joshua M. Epstein y H. Peyton Young el modelo AEY de aquí en adelante) en el que dos jugadores demandan una parte del mismo pastel, y la porción de pastel que reciben depende de la parte exigida por su oponente.

CÓMO FUNCIONA

    Como ya se ha dicho, en el modelo de AEY, dos jugadores demandan una porción de un pastel. Se podría exigir tres porciones posibles: pequeña, mediana y grande. Mientras que la suma de las dos demandas no supere el 100% del pastel, cada jugador obtiene lo que exige. En caso contrario, si supera dicha cantidad, ninguno de ellos recibirá nada.


           Hay una población de n agentes que son emparejados aleatoriamente para jugar.
Cada agente tiene una memoria en la que se mantiene la decisión adoptada por sus adversarios en los juegos/partidas anteriores. El agente utiliza la información almacenada en su memoria para la demanda de la parte del pastel que maximiza sus beneficios (con una probabilidad de 1- épsilon) y aleatoriamente (probablemente con épsilon), donde épsilon representa el nivel de ruido en el sistema.


¿Qué hace que un agente pueda elegir entre bajo, medio o alto?

En este modelo hay dos reglas de decisión posibles:


> PRIMERA DECISIÓN DE LA REGLA: LA DEMANDA DE LA OPCIÓN que maximiza el beneficio esperado

    Un agente comprobará su memoria para encontrar la frecuencia de cada una de las opciones elegidas por sus oponentes. Entonces, el agente considera que la probabilidad de que su oponente actual elija L (pequeño) - por ejemplo - sea igual a la aparición relativa de L en su memoria. De la misma manera, se calcula que tan probable es que el oponente pueda elegir M ó H. Una vez que el agente conoce esta información, el agente estima que el beneficio para las tres posibles opciones es como sigue:


- El promedio de beneficio que se puede obtener si se elige L es L, multiplicado por la probabilidad de que mi oponente elija L, M o H.

- El promedio de beneficio que se puede obtener si elige M es M multiplicado por la probabilidad de que mi oponente elija L o M.

- El promedio de beneficio se puede obtener si se elige H es H multiplicado por la probabilidad de que mi oponente elija H.

 


> SEGUNDA DECISIÓN DE LA REGLA: Elige la mejor respuesta contra los opositores MÁS FRECUENTES DE LA DEMANDA

           En este caso, los agentes demandan la porción del pastel que maximiza sus beneficios en contra de la opción más probable adoptada por sus oponentes en los juegos anteriores (es decir, el modo de su memoria). O sea, un agente asume que la opción de su oponente será el modo del contenido de su memoria.

           Un agente elegirá H si L ha sido la decisión que ha sido adoptada más frecuentemente por sus rivales en los partidos anteriores; si el valor que más se repite en su memoria es M, el jugador elegirá M. Si los partidos anteriores muestran que H es la decisión adoptada con una mayor frecuencia, entonces el agente elegirá L.


           Hay que tener en cuenta que la decisión de alguno de estos "comportamientos racionales" (en la primera o segunda decisión) tienen lugar con una probabilidad de 1-epsilon. Sin embargo, la decisión se toma aleatoriamente con una probabilidad Épsilon.


           La matriz de pagos (es decir, la combinación de premios) se puede elegir también por cambiar el valor asignado a la baja en la interfaz de la pantalla. Los valores utilizados para baja, media y alta en el modelo de AEY son, respectivamente, 30, 50 y 70.

           Por último, se pueden elegir tres tipos de configuración de la memoria:

           • Norma de memoria: un tamaño de memoria M (m se define en la interfaz de la pantalla). Todos los agentes se inicializan con m valores aleatorios en sus memorias.

           •Memoria progresiva: Las memorias de los agentes se inicializan con un solo elemento (aleatoriamente). Después de la primera iteración, cada una de las puntuaciones obtenidas por los agentes influyen en la decisión adoptada por su oponente, aumentando el tamaño de la memoria a dos, después de la segunda iteración, provocará que cada agente almacene la decisión adoptada por su rival, generando un tamaño de memoria = 3. Este proceso permite que se continúe durante un número de iteraciones, hasta que el tamaño de la memoria alcanza el valor de m'. En este punto, los agentes comenzarán a eliminar su recuerdo más antiguo de modo que el tamaño de la memoria permanece constante e igual a m.

            • Memoria endorsada: En el modelo de AEY, todos los elementos de la memoria de los agentes tienen el mismo peso que cuando tienen que tomar una decisión. Esto significa que los valores más antiguos en la memoria (es decir, las decisiones tomadas anteriormente por los opositores de varios agentes) tienen la misma importancia que las más recientes. Cuando se selecciona la opción "memoria endorsada", la estructura de la memoria se modifica de forma que las decisiones más recientes tienen un mayor peso que las anteriores.


          
El peso que hemos asignado a cada posición de memoria sigue una progresión aritmética: por ejemplo, si la diferencia común de la progresión aritmética se establece en 3, el mayor valor de la memoria tendrá un peso de 1, al segundo valor más antiguo se le da un peso de 4 (1 +3), el tercer valor más antiguo tendrá un peso de 7 (4 +3), y así sucesivamente. Suponiendo que el tamaño de la memoria es m, el valor más reciente en la memoria tendrá un peso de [1+ (tamaño de la memoria -1) *3].

 

CÓMO USARLO

1.     Seleccione los parámetros para ejecutar la simulación. Se encuentran por debajo de la cara:


- N: número de agentes.

- M: tamaño de la memoria.

- Número de iteraciones.

- Épsilon: nivel de ruido.


           Si desea que los agentes muestren una etiqueta con su identificación, seleccione la opción 'label-on-agents’.


           Si desea detener la simulación cuando el sistema alcanza un equilibrio equitativo o un Estado fraccionado, encienda el interruptor de "stop-si-equilibrio '. De lo contrario, la simulación sigue corriendo hasta que se alcanza el número especificado de iteraciones (esto es útil para observar cómo el sistema deja en equilibrio equitativo o el estado fragmentado cuando hay ruido en el sistema - épsilon> 0).


2. Seleccione la matriz de pagos para la elección de un valor para la demanda más baja. Observe que el modelo original AEY usa 30 como la demanda más baja.


3. Elija una regla de decisión.

4. Seleccione una configuración de memoria.

5. Haga clic en el programa de instalación al iniciar el sistema con los parámetros seleccionados y luego ir a ejecutar la simulación.         

 

 


 


1.6 ES (estrategias evolutivas)

 

¿En qué consiste?

Las estrategias evolutivas fueron propuestas por Ingo Rechenberg y Hans-Paul Schwefel en la década de 1970. Su principal objetivo era el de optimizar de parámetros. Se trata de métodos computacionales que trabajan con una población de individuos que pertenecen al dominio de los números reales, y mediante los procesos de mutación y de recombinación evolucionan para alcanzar el óptimo de la función objetivo.

 

Cada individuo de la población es un posible óptimo de la función objetivo; la representación de cada individuo de la población consta de 2 tipos de variables: las variables objeto y las variables estratégicas. Las variables objeto son los posibles valores que hacen que la función objetivo alcance el óptimo global y las variables estratégicas son los parámetros mediante los que se gobierna el proceso evolutivo o, en otras palabras, las variables estratégicas indican de qué manera las variables objeto son afectadas por la mutación.

 

Haciendo una analogía más precisa, el genotipo en las estrategias evolutivas es el conjunto formado por las variables objeto y las variables estratégicas. Y el fenotipo son las variables objeto, ya que conforme se da la variación de éstas, se percibe un mejor o peor desempeño del individuo.

 

¿Cómo utilizarlo?


           El objetivo de este problema en particular, es optimizar la forma de la lente de tal manera, que los rayos paralelos que caen sobre el objetivo se centren en un solo punto. La forma se optimiza mediante la modificación del espesor de los segmentos de la lente "

 

estrategia de elección


           Seleccione una estrategia para el proceso de evolución. La estrategia decide cómo los padres "generarán" a sus hijos y cómo influye la elección de los padres en la próxima generación.

           La siguiente tabla muestra las características de las estrategias:

 

 

 

estrategia

Selección del más adecuado

Niños generados por

 

p+c

Padres

mutación

 

p,c

Padres e hijos

mutación

 

p/r,c

Padres

mutación y recombinación

 

p/r+c

Padres e hijos

mutación y recombinación

 

 


•Scroller para los padres



           Seleccione el número de padres. Los cambios en esta opción también se aplican a los hijos. Puesto que el número de padres debe ser menor o igual al número de hijos, el valor inicial de los hijos será fijado al número de padres.


• Scroller para los hijos

 

           Seleccione el número de hijos. No deberá seleccionar un valor menor que el número de padres (ver: "scroller de los padres ').

 



•Elección de recombinación:

 

La estrategia de evolución utiliza básicamente dos formas diferentes en la generación de hijos. La primera de ellas es la mutación, que emplea cambios aleatorios en el valor (o valores) del genotipo de los individuos. La segunda de ellas es la recombinación, que combina dos (o más) padres para generar un hijo. Esta opción se aplica para el tipo de recombinación utilizado. Los tipos se diferencian en el número de padres utilizados y la manera en que los genotipos de estos padres se combinan. La elección de recombinación se establece insensible cuando se selecciona una estrategia que no utiliza la recombinación (véase: estrategia de elección).

 

Sea AX, BX el valor de x-ésimo en el genotipo de los padres A y B; y Zx el valor x-ésimo en el genotipo de los hijos Z. Entonces la siguiente tabla muestra los posibles tipos de recombinación y sus características:

 

 

 

Recombinación

discreta

intermedia

Global discreta

global intermedia

Número de padres usados en la recombinación

2

2

r >= 2

r >= 2

Resultado

Zx=Ax or Bx

Zx=1/2*(Ax+Bx)

Zx=Ax or Bx or ...

Zx=1/r(Ax+Bx+...)




• scroller de recombinación

 

Seleccione el número de recombinaciones, es decir, el número de padres utilizados en la recombinación. El scroller se establece insensible cuando se selecciona una estrategia que no utiliza la recombinación (véase la "estrategia de elección ') y cuando el tipo de recombinación que es seleccionado utiliza exactamente dos recombinaciones, es decir, dos padres (ver "elección del tipo de recombinación”).

 

 

• Alfa

 

En la estrategia de la evolución el genotipo se divide en dos partes. La primera de ellas, los parámetros de objeto, es un vector de los números reales que contiene el individuo pintado de azul (sus genes). El segundo, los parámetros de la estrategia, es también un vector de números reales (con la misma longitud que el primer vector) que con establecen el si una entrada correspondiente en el vector de parámetros objeto debe ser modificado (es decir, mutado), y cómo. Sea O un parámetro objeto, y S es el parámetro de la estrategia correspondiente. Entonces, si está mutado O, esta mutación se da por EN (0, S), donde N (0, S) es la distribución Gaussiana con valor medio-0 y el nivel de desviación S (especialmente un valor de 0 para S no cambia O).

 

El valor alfa indica cómo los parámetros de la estrategia del vector de cambios durante el proceso de evolución. Por lo tanto, son conocidos como parámetros de estrategia de adaptación del valor”). Si el individuo es mutado, entonces cada parámetro de la estrategia es adaptado multiplicándose por un valor escogido de forma aleatoria a partir de alfa y 1/alfa. Esto significa que la mutación “paso-tamaño” se adaptará en el proceso de evolución.

 

Rechenberg [ "Evolución de la Estrategia", 1994, capítulo 14] recomienda un valor alfa de 1,3]

 

 

Detener el proceso de evolución

http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/evolution_help_gui3.gif


 
•scroller para detener las generaciones.

 

Seleccione la máxima generación. El proceso de evolución se detiene cuando se llega a esta generación. Puede continuarse si se incrementa el valor.

 

•Botón de activación de Óptimo:

 

Detiene el proceso de evolución cuando se alcanza el valor óptimo. Hay que tener en cuenta que debe especificarse una función que devuelva el valor de fitness óptimo que alcance para los fenotipos de un problema específico. Si se especifica esto, este botón será sensible. Sin embargo, para la mayoría de los problemas, no se conoce el valor óptimo.

Botones de control

 

http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/evolution_help_gui5.gif

 

 

• Botón de la calidad gráfica:

Abre una ventana que muestra la gráfica de los valores de fitness. Al pulsar el botón de nuevo, se cierra la ventana.

 

• Botón de edición:


           Abre una ventana para crear / editar un fenotipo (sin embargo, sólo se proporciona un editor de ventana con el problema de aplicación). El proceso de evolución se puede reiniciar con el genotipo correspondiente. Usted (debería) encontrar más información siguiendo un enlace en la página principal del problema.


•Botón de inicio

 

Inicia el proceso de evolución.



• Botón de parada

 

Detiene el proceso de evolución.



• Botón “continuar”

 

Continuación de un proceso de evolución que fue detenido.

 

 

Mostrar fenotipo

 

http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/evolution_help_gui1.gif


          

 

Muestra el mejor individuo de la generación actual, junto con el número de generación y su fitness (los valores de fitness son mejores cuanto más pequeños sean, pues se está pretendiendo minimizar).

 

 

 

 

 

 

 

 

 

 

 

 

Ejemplo del funcionamiento de la aplicación:

 

 

           Este mismo problema puede resolverse con algoritmos genéticos. A continuación explicaremos las diferencias en los parámetros de la interfaz a manejar, para concluir realizando una comparación entre ambas estrategias:

 

 

A continuación, explicaremos los parámetros de la interfaz al aplicar algoritmos genéticos para la resolución del mismo problema, así como la salida del fenotipo mostrado, que difieren con respecto al empleo de estrategias evolutivas. Una vez explicadas las diferencias en el manejo de la interfaz, daremos paso a explicar en qué consiste el problema a resolver, así como el objetivo a alcanzar, y destacaremos las diferencias más importantes con respecto a resolverlo empleando algoritmos genéticos o estrategias evolutivas.

 

 

• Selección de la estrategia:

 

Selecciona una estrategia para el proceso de evolución. La estrategia decide desde donde son seleccionados los padres para las próximas estrategias.

Élite: Selección de los padres y los hijos de esta generación.

Canónico: Selección de los hijos de esta generación.

• Scroller para los padres:

Selecciona el número de padres.

• Scroller para los hijos.

Selecciona el número de hijos. 

Scroller para el cruce:

 

Selecciona de uno a m puntos de cruce.


'cp (cruce de probabilidad) por persona' scroller:

 

Los hijos son generados a partir de los padres usando crossover y mutación. Hay que seleccionar la probabilidad del cruce por individuo 1.0: para el 100% la totalidad de los hijos se generan mediante el cruce.

0.0: No utiliza el cruce.

 

 

•Alternancia del uso de la mutación:

 

Los hijos son generados a partir de los padres usando cruce y mutación. Alternar el uso de la mutación permite mutaciones usando parámetros mp por individuo o mp por parámetro y máximo m-bits por p.

 

•Scroller para individuos: "(MP-mutación de probabilidad):

 

Seleccione la probabilidad de mutación por individuo: 

1.0: El 100% de los hijos se generan utilizando mutación. 0.0: No utiliza la mutación; 


•scroller por parámetro: '(MP mutación de probabilidad):

 

Seleccione la probabilidad de mutación para un único parámetro del individuo. 1.0: El 100% de los hijos se generan utilizando mutación. 0.0: No utiliza la mutación; 



•Scroller 'm Max-bits por P. (número máximo de bits mutado 
por parámetro)

 

Seleccione el número máximo de bits que quiere mutar en un solo parámetro.

 

Mostrar fenotipo

 

http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/genetic_help_gui1.gif

 

 

Muestra el mejor individuo de la generación actual, junto con el número de generación y su fitness (los valores de fitness son mejores cuanto más pequeños sean, pues se está pretendiendo minimizar).

 

Ejemplo del funcionamiento de la aplicación:

 

 

1.6.1.1 Evolución de una lente de un prisma – Información del problema:

 

A continuación se describe la información referida al problema, una vez descritos los parámetros que permiten manejar la interfaz de la aplicación.

 

Este primer problema se basa en la evolución de una lente de un prisma:

 

El objetivo es optimizar la forma de la lente de tal manera que los rayos paralelos que caen sobre el objetivo se centrarán en un único punto. La forma se optimiza mediante la modificación del espesor de los segmentos de la lente.

 

 

http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/ea_prism_problem.gif

 

De izquierda a derecha: 10 segmentos por lente (refracción proporción 1,0), 15 segmento por lente (refracción proporción 1,4), 20 segmentos por lente (refracción proporción 0,75).

Cromosoma (representación genotipo)

 

Estrategia de evolucióN


           Los segmentos de la lente se codifican con 3 valores de tipo double por segmento: la posición x (la mitad del segmento), la posición y (su posición de arriba) y su espesor * ½.


   / / 9 piezas de lente: 10 valores de espesor.

op double [] = (40, 30, 10, / / x, y, el espesor * 1 / 2
                      40, 40, 10,
                     40, 50, 10,
                     40, 60, 10,
                     40, 70, 10,
                     40, 80, 10,
                     40, 90, 10,
                     40.100, 10,
                     40.110, 10,
                     40.120, 10);


   SP double [] = (0, 0, .1,
                     
0, 0, .1,
                      0, 0, .1,
                      0, 0, .1,
                      0, 0, .1,
                      0, 0, .1,
                     
0, 0, .1,
                      0, 0, .1,
                      0, 0, .1,
                      0, 0, .1);


        Como se desea optimizar espesor de las lentes de todos los segmentos, los parámetros de estrategia deben ser 0;

 


Algoritmos genéticos

La altura de las lentes de las piezas y la posición se fija, similar a la del genotipo de las estrategias evolutivas. El genotipo contiene n +1 15-Bit piezas para N+ 1 valores de espesor, si n es el número de piezas de la lente.


  / / 9 piezas de lente: 10 valores de espesor.

[[011100111000000]
   [010010110100110]
   [100101101000011]
   [110001011000001]
   [100100011111101]
   [111101001010100]
   
[011101011100011]
   [010001011111001]
   [010111001100001]
   [010110010111011]]

 

Dibujando el cromosoma (representación fenotipo)

Al principio, se dibujan las piezas de las lentes junto con los rayos entrantes. Para cada rayo entrante se calcula un rayo refractado en la frontera de la lente izquierda. Por este rayo refractado se calcula el punto de intersección con el borde derecho de la lente. Se extrae el rayo de la frontera de la lente izquierda hasta el punto de intersección con la frontera de la lente derecha y se utiliza para calcular el rayo saliente refractado en la frontera de la lente derecha. Por último, se calcula el punto de intersección de los rayos de salida con el enfoque del plano y se dibuja el rayo desde el punto de intersección con el borde derecho de la lente y el punto de intersección con el plano de enfoque.

 

La función de calidad


           Para cada rayo entrante, 2 rayos son refractados y se calculan 3 puntos de intersección:


1.Intersección: rayo entrante y la lente del borde izquierdo.

1.Rayo refractado: rayo entrante en 1.intersección.

2.Intersección: 1.Rayo refractado con lente en el borde derecho.

2.Rayos refractados: Rayos de salida en 2.Intersección.

3.Interseccción: 2.Rayo refractado con un enfoque plano



           Para cada rayo entrante i, sea di la distancia del tercer punto de intersección y con respecto al foco en el plano de enfoque. Entonces, la calidad de una lente de prisma se calcula sumando las distancias al cuadrado (di ^ 2) para cada rayo:

 

http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/prism_problem_quality1.gif

           Calculando la calidad de la lente del prisma es algo así como hacer el trazado de los rayos. Tenemos que calcular los rayos refractados y los puntos de intersección.
Dada una línea (la frontera de la lente) y un rayo incidente, se puede calcular el rayo refractado T de la siguiente manera (Ref.: Glassner, Ray Tracing, p.291ff):


http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/prism_problem_quality2.gif

 



T = -p * I (p * C1-C2) * N
con
N = normal del borde de la lente
p = proporción de refracción r2/r1 (Lens / medio)
c1 =-I * N = cos (ángulo entre I y N)
c2 = sqrt (1-p ^ 2 (1-c1 ^ 2)) = cos (ángulo entre T y N)

 

Parámetros del applet


    * Nombre del parámetro = "piezas" valor = "10"
      número de piezas de lentes
    * Nombre del parámetro = "refracción" valor = "0.75"
      proporción de refracción R1/R2 (medio / lente)
    * Nombre del parámetro = "dmax" valor = "20" (¡¡¡Solamente para los algoritmos genéticos!!!)
      Máxima anchura de una pieza de lentes /2.

    * Nombre del parámetro = "maxdif" valor = "8" (¡¡¡Solamente para los algoritmos genéticos!!!)
      Diferencia máxima del ancho de dos piezas de lentes sucesivas.

 

 

1.6.1.2 Evolución de un cuadrado mágico - Información del Problema

Este segundo problema se basa en la evolución de un cuadrado mágico.

 

El objetivo es encontrar un cuadrado mágico de verdad. Estos son los números del 1 al n ^ 2 (n != 2) que estarán dispuestos en una cuadrícula de n* n, de tal manera que la suma de todas las filas y la suma de toda las columnas y la suma de las diagonales del el mismo valor S.

 

http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/ea_magic_problem.gif

 

 

 

 Estrategia de evolución 

 

// cuadrado mágico de tamaño 4x4

double parametros_objeto[] = { 1 ,2 ,3 ,4,

5 ,6 ,7 ,8,

9 ,10,11,12,

13,14,15,16 };

double parametros_estrategia[] = { 2,2,2,2,

2,2,2,2,

2,2,2,2,

2,2,2,2};

 

 

Se utiliza un operador de mutación para un problema específico. Este se basa en el intercambio de objetos parámetros. Para cada cromosoma mutado, el proceso siguiente se repite X veces (donde X es el valor de los parámetros de estrategia): Se selecciona un único parámetro objeto al azar de los n^2 parámetros objetos. Este parámetro se intercambia con un segundo. El parámetro de este segundo objeto (de nuevo elegido al azar entre los n^2 objetos parámetros), utilizando para ello la restricción de que su valor debe estar dentro de un rango de +- el primer parámetro de los llamados de estrategia. Todos los parámetros de estrategia son iguales y se adaptan. Con la misma probabilidad se incrementan o decrementan en uno, o se mantienen como están.

 

 

 

Ejemplo:


   Que todos los parámetros de estrategia tienen un valor de 2 => 2 operaciones de intercambio. 
   

1. Swap (intercambio)

   

dejar que el primer parámetro objeto seleccionado sea el número 6;
   buscar un segundo parámetro objeto dentro del rango de 4 .. 8 = (4,5,6,7,8);
   dejar que el segundo parámetro objeto seleccionado sea el número 7;

   => Intercambio del 6 y el 7.



   2. Swap (intercambio)

dejar   que el primer parámetro objeto seleccionado sea el número 16;
   buscar un segundo parámetro objeto dentro del rango de 14 .. 18 = (14,15,16,17,18);
   dejar que el segundo parámetro objeto seleccionado sea el número 15;
   => Intercambio del 16 y 15

  
           Hay que tener en cuenta que al utilizar la recombinación con este ejemplo se van a producir cuadrados mágicos “ilegales” y no debe ser utilizada (ver más abajo: efecto de cruce en la versión con Algoritmos genéticos).

 

Dibujando el cromosoma (representación del fenotipo)

Simple: la representación de parámetros enteros = número correspondiente en el cuadrado mágico.

Función de calidad

La suma mágica S es 0.5*n*(n^2-1). Para cada fila, columna y diagonal, la diferencia al cuadrado de su suma y la suma mágica se añaden a la función de calidad. Sus resultados son los valores de calidad del cromosoma.

 

 

quality=0;

 

for each row

s=get_sum( row )

quality = quality + (S-s)*(S-s)

 

for each column

s=get_sum( column )

quality = quality + (S-s)*(S-s)

 

s=get_sum( first_diagonal )

quality = quality + (S-s)*(S-s)

 

s=get_sum( second_diagonal )

quality = quality + (S-s)*(S-s)

 

Parámetros del applet

Desarrollar un cuadrado mágico de n*n.

 

Cuadrado mágico de 10x10

 

http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/magic_example10.gif

 

 

1.6.1.3 Evolución de un sistema de tuberías - Información del Problema

Este tercer problema se basa en la evolución de un sistema de tuberías

 

El objetivo es optimizar las posiciones de los nodos interiores dado un sistema de tuberías, de tal modo que en el volumen total del sistema, la presión de los nodos finales y la diferencia final de todos los nodos sea mínima.

 

 

http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/ea_pipes_problem.gif

 

CROMOSOMA (REPRESENTACIÓN DEL GENOTIPO)

Evolución de la estrategia:

El sistema de tuberías está codificado con cinco valores de tipo double, por nodo. Así pues, cada cromosoma se compone de 5*n valores de tipo doublé, si n es el total de número de nodos (nodos interiores y nodos finales) del sistema. Solamente se considerarán sistema de tuberías con una topología de árboles binarios. Sin embargo, se podría superar fácilmente esta restricción mediante la extensión de la codificación de los árboles. En el caso de los árboles binarios, sean (x, y d, ln, rn) los 5 valores de tipo doublé usados para codificar un nodo único, donde (x, y) es la posición de los nodos y d es su diámetro. En el número de su sucesor izquierdo (posiblemente -1, si no hay ninguno) y rn es el número de su sucesor derecho (posiblemente -1, si no hay ninguno). Entonces, el siguiente ejemplo muestra cómo se codifica el árbol completo:

 

· // Codificación del árbol completo: para cada nodo ( x,y,r,e1,e2 );

// x,y: posiciones del nodo

// r : radio de la tubería en el nodo

// e1,e2: aristas de salida (-1 si no es arista)

double oopars[]= { 125,140, 8.00, 1, -1, // nodo 0: nodo principal

125,139, 8.00, 2, 9, // nodo 1: nodo interno -> nodo 2 y nodo 9

123,138, 4.00, 3, 6, // nodo 2: nodo interno -> nodo 3 y nodo 6

121,139, 3.18, 4, 5, // nodo 3: nodo interno -> nodo 4 y nodo 5

20,120, 2.52, -1, -1, // nodo 4: nodo final

25,100, 2.52, -1, -1, // nodo 5: nodo final

121,137, 3.18, 7, 8, // nodo 6: nodo interno -> nodo 7 y nodo 8

30, 80, 2.52, -1, -1, // nodo 7: nodo final

40, 70, 2.52, -1, -1, // ...

127,138, 6.34, 10, 21,

125,136, 5.04, 11, 18,

123,135, 4.00, 12, 15,

121,133, 3.18, 13, 14,

60, 50, 2.52, -1, -1,

75, 35, 2.52, -1, -1,

127,133, 3.18, 16, 17,

95, 25, 2.52, -1, -1,

115, 30, 2.52, -1, -1,

128,132, 3.18, 19, 20,

140, 32, 2.52, -1, -1,

155, 25, 2.52, -1, -1,

130,136, 4.00, 22, 25,

130,134, 3.18, 23, 24,

175, 35, 2.52, -1, -1,

190, 40, 2.52, -1, -1,

132,136, 4.00, 26, 29,

132,133, 3.18, 27, 28,

215, 55, 2.52, -1, -1,

225, 65, 2.52, -1, -1,

134,135, 3.18, 30, 31,

240, 80, 2.52, -1, -1,

240,100, 2.52, -1, -1 };

 

double ospars[]= { 0,0,0,0,0, 1,1,0,0,0, 1,1,0,0,0, 1,1,0,0,0,

0,0,0,0,0, 0,0,0,0,0, 1,1,0,0,0, 0,0,0,0,0,

0,0,0,0,0, 1,1,0,0,0, 1,1,0,0,0, 1,1,0,0,0,

1,1,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 1,1,0,0,0,

0,0,0,0,0, 0,0,0,0,0, 1,1,0,0,0, 0,0,0,0,0,

0,0,0,0,0, 1,1,0,0,0, 1,1,0,0,0, 0,0,0,0,0,

0,0,0,0,0, 1,1,0,0,0, 1,1,0,0,0, 0,0,0,0,0,

0,0,0,0,0, 1,1,0,0,0, 0,0,0,0,0, 0,0,0,0,0 };

 

Los parámetros de estrategia son desiguales a 0 sólo para las posiciones de los nodos interiores, ya que sólo se desea optimizar estas posiciones.

La medida del diámetro óptimo para las tuberías está dada por di +1 = di ^ (3 / 2) [Zerbst ", Bionik", p. 138].

Dibujando el cromosoma (representación del fenotipo)

Esto es muy fácil usando la codificación anterior. Para cada nodo del cromosoma simplemente dibujar un círculo en (x, y) con radio d y, a continuación trace líneas a sus sucesores ln y rn (no se dibuja ninguna línea en caso de ln o rn tengan un valor de -1).

 

Función de calidad

El volumen total, las diferencias de presión en los nodos finales y la presión final en los nodos debe ser mínima.

 

http://ls11-www.cs.uni-dortmund.de/people/kursawe/Demos/EvoNet/pipes_problem_quality1.gif

 
Pi es la presión en el nodo final i-ésimo;
PM es la presión media de los nodos finales;
Vtot es el volumen total del sistema de tuberías;

a, b, c son constantes;

 

 

 

1.6.2 Animaciones de los applets anteriores

Todos estos applets pueden verse de una forma más ilustrativa, junto con otros más en las siguientes animaciones: http://www.bionik.tu-berlin.de/institut/xs2anima.html

A continuación explicaremos los parámetros representados en estas animaciones. Hay que mencionar que, puesto que se trata de archivos.exe, solo podrán descargarse y visualizarse para sistemas operativos Windows. Están extraídos de la página Bionik & Evolutionstechnik de Berlín.

Las notaciones (1+1)-ES, (1+l)-ES, (1, l)-ES, (m/r, l)-ES... caracterizan a las estrategias evolutivas con un creciente nivel de imitación de la evolución biológica. La letra m  significa el número total de padres, r marca el número de padres que han sido recombinados y l se utiliza para el número de descendencia. La selección tiene lugar solo entre los hijos (notación Komma) o entre la descendencia y antecesores juntos (además de la notación). El álgebra como expansión del esquema de notación conduce a las Estrategias de Evolución, escritas de la siguiente forma: [m’, l’(ml)g]-ES. Dentro de los corchetes las poblaciones de l se juzgarán de acuerdo con la velocidad de convergencia, después de que cada una de estas poblaciones se haya ejecutado un número g de veces, a través del esquema de selección (ml)- (g = número de aislamiento). Las Estrategias de Evolución constituyen la base para la evolución y autoadaptación de los parámetros estratégicos. Para la propia adaptación del tamaño de una simple mutación en un único paso, el valor (1, l) puede dar resultados adecuados. Las estrategias evolutivas anidadas están calificadas de acuerdo a la optimización multimodal.

Como ejemplo de la salida del programa, pondremos el ejemplo de las lentes, y del cuadrado mágico:

1.6.3 EVOLUCIÓN DE LA MONA LISA

Este programa se inspira en la evolución de la Mona Lista por Roger Alsing (http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/). Trata de encontrar la combinación de 50 polígonos translúcidos que cuya combinación más se aproxime a la Mona Lisa de Leonardo Da Vinci. Esta implementación no es idéntica a la de Roger, utiliza una población de soluciones candidatas y aplica cruce así como varios tipos de mutación.

Este programa también muestra la librería Watchmaker Swing. Esta librería proporciona componentes GUI para la manipulación de parámetros de evolución (incluso cuando la evolución está corriendo). También proporciona el monitor de evolución reusable, componente que permite visualizar el estado de la población en evolución a lo largo del tiempo.

Este programa hace un uso intensivo de la CPU. Cuanto más rápida sea tu máquina, más rápido se aproximará a una imagen reconocible. La evolución parará si no se observan mejoras durante 1000 generaciones (un ejemplo de la condición de terminación de Stagnation). Puede ejecutarse durante horas.

 

Dibujo

 

Los parámetros disponibles para la ejecución son el tamaño de la población, el elitismo y le presión sobre la selección. Además de eso es posible configurar las probabilidades de evolución modificando los siguientes parámetros:

 

- Add Polygon: probabilidad de añadir un nuevo polígono.

- Remove Polgygon: probabilidad de eliminar un polígono.

- Reorder Polygons: probabilidad de reordenación de polígono

- Cross-over: probabilidad de cruce.

- Add vertex: probabilidad de añadir vértice.

- Remove vertex: probabilidad de eliminar vértice.

- Move vertex: probabilidad de mover vértice.

- Change color: probabilidad de cambiar color.

 

El applet dispone de tres pestañas donde seguir la ejecución, en la primera “Fittest individual” podemos ver la imagen buscada (la mona lisa original) y la imagen formada por el individuo actual con el mejor estado, el valor del fitness y el número de polígonos y vértices que lo forman.

 

Dibujo3

 

En la pestaña population fitness se observa una gráfica con el valor del fitness del mejor individuo y la media de todos los individuos. Se puede configurar para ver las últimas 200 generaciones o todas ellas.

 

Dibujo4

 

           En la última pestaña, “JVM Memory” se puede ver una gráfica del consumo de memoria sobre el total disponible en la java virtual machine.

 

Completa el applet una barra de estatus en que se muestra el valor de los parámetros de tamaño de la población y de elitismo, así como el número de generación actual y el tiempo de ejecución.

 

Otros ejemplos

Otros ejemplos similares los podemos encontrar en los siguientes enlaces:

·       The Travelling Salesman

·       Biomorphs

·       Sudoku

 

 

1.7 swarm Intelligence y spo

1.7.1 Swarm Intelligence: Simulador del comportamiento en grupo.

El comportamiento de enjambre es un ejemplo de comportamientos emergentes, donde el comportamiento global complejo puede surgir de la simple interacción de las normas locales.

           

En este ejemplo, las aves siguen tres reglas simples que causan el comportamiento en grupo / del enjambre.

 

 

·       Separación: Dirigir para evitar el amontonamiento de las aves del mismo color

·       Alineación: Dirigir hacia el promedio de la partida de las aves del mismo color.

·       Cohesión: Dirigir para avanzar hacia la posición promedio de las aves del mismo color.

Bird Detection

 

 

Cada ave tiene un rango de detección y separación. El applet tiene la opción de mostrar u ocultar los rangos. El rango de detección es la distancia a la cual las aves pueden detectar depredadores, obstáculos, alimentos y otras aves. El rango de separación es la distancia a la que una bandada de pájaros puede dividirse para evitar un depredador, obstáculo, o un pájaro. Hasta que algo cae dentro de un rango de detección de las aves, éstas no reaccionarán ante esto. No hay que dejarse confundir por los círculos que se superponen en el ejemplo de la izquierda. En este ejemplo, los pájaros no pueden verse unos a otros hasta que el pájaro se inscribe en el círculo de otras aves de detección.

 

 

 

Separation

Las aves son repelidas por las aves de diferentes colores y por los obstáculos. Cuanto más cerca esté el ave, mayor será el efecto de rechazo. Esto hace que las aves tiendan a alejarse de los depredadores, los obstáculos, y las aves de colores diferentes.

Alignment

 

 

 

En una bandada de pájaros del mismo color, cada ave tratará de satisfacer la dirección que puede detectar de las aves que van a su alrededor. Si algunas de las aves de una bandada detectan un obstáculo, todas girarán a su vez. Esto hace que el resto de la manada, que ni siquiera puede detectar el obstáculo, también gire.

 

 

Cohesion

Las aves de una bandada se sienten atraídas entre sí, siempre y cuando estén dentro del rango de detección, pero fuera del rango de separación. Este objetivo pretende tener la bandada de aves juntas, pero no tan cerca que estén unas encima de otras. Si hay demasiados pájaros en la bandada, deberá aumentarse la gama de separación.

 

FUNCIONAMIENTO

A continuación explicamos los parámetros que permitan manejar la interfaz de la aplicación:

 

Como puede verse en la parte superior de la interfaz, todos los parámetros se modifican moviendo el scroll situado a la derecha de sus descripciones, agrupados por los colores de las aves.

De este modo, podemos modificar el número de aves de cada color que aparecerán en el cuadro inferior, así como su velocidad y ángulo de giro. Hay que tener en cuenta que cuanto más rápido es el movimiento, más difícil es volver. Lo mismo sucede si el radio máximo de giro es muy pequeño.

Por otra parte, también se puede modificar la distancia de detección, la separación para evitar, y la cantidad de hambre que tenga el depredador – ave roja-.

Al pinchar con el botón izquierdo sobre el cuadro inferior de la interfaz, añadimos obstáculos que las aves tienen que saltear. Si se pincha con el botón derecho lo que añadimos es comida. Podemos mostrar los rangos de las distancias entre las aves al seleccionar la opción “Show Dist Ranges”.

Para comenzar con otros parámetros nuevos la ejecución del programa basta con modificar los parámetros en cuestión y pinchar sobre el botón “reset”.

 

1.7.2  Particle Swarm Optimization (PSO) Visualisation (or "PSO Visualization")

 

Particle Swarm Optimization, una breve introducción

Particle Swarm Optimization es una aproximación a los problemas cuyas soluciones pueden ser presentadas como un punto en un espacio de solución n-dimensional. Se ponen en marcha un número aleatorio de partículas a través de este espacio. En cada iteración, observan su propio fitness y el de sus vecinos y “emulan” satisfactoriamente vecinos con éxito (aquellos cuya posición actual representa una mejor solución en el problema que la de ellos) al moverse hacia ellos. Pueden utilizarse varios esquemas para la agrupación de partículas en la competición, enjambres semi-independientes o todas las partículas pueden pertenecer a un conjunto global único. Este enfoque extremadamente simple ha sido sorprendentemente efectivo a través de una variedad de dominios del problema.

 

Acerca de este applet 

PSO se suele utilizar para abordar problemas con muchas incógnitas (de muchas “dimensiones”). Esta visualización es extremadamente sencilla y trivial: el enjambre busca a través de dos incógnitas (o “dimensiones”) y el valor de cada punto de estas dos dimensiones es representado en la tercera dimensión.

Este applet ha sido programado por Kent Fitch, y para su ejecución requiere versiones superiores a Java 1.1.

 

¿En qué consiste este applet?

·      Este applet genera un paisaje semialeatorio en 3D. Un enjambre de 12 partículas generado aleatoriamente trata de encontrar el máximo global del paisaje. El enjambre no conoce el máximo. Simplemente está configurado para parar cuando lo encuentre.

 

·      Puede generarse un Nuevo enjambre (con nuevas posiciones de comienzo), así como nuevos paisajes.

 

·      El enjambre de 12 partículas puede trabajar junto como una sola bandada o dividirse en 2, 3 o 4 bandadas semi-autónomas.

 

·      El enjambre puede ejecutarse hasta encontrar la solución (o durante 100 iteraciones), o ejecutarse paso a paso y pausarse.

 

·      Se usan diferentes colores para diferenciar las posiciones de las generaciones actual y anterior, y se marca el movimiento para ayudar a visualizar el progreso.

 

 

Cómo usar el applet

·      Se debe esperar hasta que el applet haya cargado. Como el código solo ocupa 45kB, esto no debería llevar mucho tiempo. Se debería ver un paisaje en 3D en la parte inferior.

 

·      El máximo global (el punto que busca el enjambre) está marcado con una fleche roja.

 

·      Puede rotarse el paisaje usando los botones (Up/Down/Left/Rigth- Arriba, abajo, izquierda y derecha) o haciendo clicks sobre el paisaje y utilizando los botones de fleche. No puede rotarse utilizando el ratón.

 

·      Pulsar el botón de “Step”. Esto inicializará el enjambre sobre el paisaje. La posición inicial de cada partícula se mostrará como una pequeña marca verde. Girar el paisaje para ver la posición de las partículas una respecto a las otras y respecto al máximo.

 

·      Pulsar el botón “Step” nuevamente. Los botones verdes se moverán, normalmente en dirección a la partícula más adecuada. La posición previa de la partícula se señala con una marca amarilla y una línea verde se dibuja desde la posición inicial a la posición final visualizando el movimiento.

 

·      Pulsar el botón “Step” de Nuevo: la generación original está ahora coloreada de magenta, la segunda generación está ahora coloreada de Amarillo y la posición de la generación actual será nuevamente dibujada en verde. Las líneas amarillas marcarán el vector tomado desde la generación original hasta la segunda generación, las líneas verdes muestran el vector desde la posición anterior hasta la posición actual.

 

·      Pulsar “Step” de Nuevo: la generación original está ahora coloreado de azul. Pulsar “Step” de nuevo y se pintarán de negro. Es decir, las generaciones se representan utilizando los siguientes colores: verde, Amarillo, magenta, azul, negro. Las posiciones de las generaciones anteriores a las últimas cuatro se muestran en negro. Los vectores de movimiento se muestran solo para las dos últimas generaciones.

 

·      Los vectores de movimiento siempre se muestran por encima del paisaje, y pueden verse incluso en los casos en los que en la vida real el paisaje taparía los vectores.

 

·      La información de estado en la ventana inferior del applet muestra el número de iteraciones completadas, el máximo valor de enjambres buscando, el máximo valor encontrado en la última iteración y el máximo valor encontrado en cualquier iteración de esta ejecución

 

 

Cosas a probar

·      Primero pulsar el botón de “Step” una vez para conseguir una primera impresión de cómo funciona. Esto es más fácil con solo una bandada al no haber indicación visual de qué partículas están agrupadas en una bandada.

 

·      Entonces ejecutar algunas pruebas para completar, observando cómo se mueve la bandada a través del paisaje.

 

·      Observar cómo volviendo a ejecutar las pruebas en el mismo paisaje produce normalmente diferentes resultados; es decir, cómo las posiciones iniciales de las partículas se encaminan a una rápida solución del máximo global, y cómo otras posiciones llevan a fallo tras 100 iteraciones.

 

·      Probar los resultados utilizando distintos número de bandadas en el mismo paisaje.

 

·      Probar nuevos paisajes. Observar como algunos paisajes son más difíciles, tales como aquellos con un máximo local grande a cierta distancia del máximo global.

 

·      Observar que el enjambre no tiene memoria más que en la actual generación. En ocasiones vuelve a visitar posiciones previas. Si tuviera memoria sabrían que no es el máximo global. Observar también que en otras ocasiones repiten patrones, incluso con múltiples partículas recorriendo los mismos vectores.

1.7.3 PSO– provis applet (3D)

Breve introducción de Optimización de Partículas Swam (PSO)

Para poder ejecutar este applet correctamente, es necesario tener instalado Java 3D. Puede descargarse de esta página: https://cds.sun.com/is-bin/INTERSHOP.enfinity/WFS/CDS-CDS_Developer-Site/en_US/-/USD/ViewProductDetail-Start?ProductRef=java3d-1.5.1-oth-JPR@CDS-CDS_Developer)  

El Applet PsoVis permite la visualización en 3D del proceso de optimización de PSO (Particle Swarm Optmization). Con esta herramienta es posible mirar el movimiento de las partículas de un enjambre de partículas (visualizadas como pequeñas esferas azules) que tienen aquí la tarea de minimizar una función de fitness predefinida que puede ser elegida por el usuario. Las funciones de fitness pueden ser visualizadas y optimizadas en un rango de valores elegido por el usuario. También es posible seleccionar entre dos implementaciones diferentes de PSO y, para variar las propiedades diferentes de randerización, las propiedades de PSO y los parámetros de PSO.

Particle Swarm Optimization (PSO):

PSO es un paradigma de optimización biológica motivado que implica interacciones “sociales” entre individuos de una población. Estos individuos, también llamados partículas, pueden moverse a través de un espacio de búsqueda multidimensional a fin de encontrar un óptimo. Las partículas pueden cambiar sus direcciones de movimiento y velocidades de acuerdo con la información que ellos mismos y el enjambre completo ha reunido hasta ahora en el fitness del paisaje. Cada partícula puede recordar su mejor posición encontrada hasta entonces, mientras que el conjunto de las partículas conocen la mejor posición que han encontrado todas las partículas del enjambre. Partiendo de esta información y del vector de velocidad actual de cada partícula se calculan nuevos vectores y se actualizan las posiciones de las partículas. Distintos ajustes de parámetros pueden influir en el comportamiento de los enjambres como, por ejemplo, su capacidad para converger. En esta implementación PSO la trayectoria de cada partícula se puede calcular de dos maneras:

 

Tipo estándar PSO:

            El vector de velocidad para las partículas se calcula como sigue: 

image008 (1K)

Donde xi y vi  de la posición actual y la velocidad de la i-ésima partícula, pi pb  son las mejores posiciones encontradas por la partícula y-ésima y por la mejor de las partículas del enjambre, n1 n2   son los parámetros que permiten medir la influencia del “individuo” y el “conocimiento social”. Los parámetros individuales y sociales determinan cuánto son influenciadas las partículas por su propio óptimo encontrado y la totalidad de óptimos encontrados por el enjambre; c es un factor de restricción utilizado para amortiguar los movimientos de las partículas, r1 y r2  son los números aleatorios entre 0 y 1 que se añaden a un componente estocástico para el comportamiento del enjambre. En esta implementación estándar de PSO hay un peso i de inercia, que varía linealmente a lo largo del proceso de optimización desde el valor de inicio a un valor final.

Para el PSO de tipo Estándar se puede establecer un límite Vmax para la velocidad, todos los valores de velocidad que excedan este límite se establecen por defecto al máximo valor especificado.

Tipo Constricción PSO:

El vector de velocidad para las partículas se calcula de forma ligeramente diferente: 

 

image004 (1K)

 

donde:

image005 (1K)

y

 

image005 (1K)

 

K recibe el nombre de “Factor de Constricción” e influye en la velocidad de las partículas de amortiguación.

 

 

Actualización de las posiciones: 

En ambas implementaciones de PSO, las posiciones de las partículas se actualizan aplicando Eq.3.: 

 

image010 (1K)

 

 

 

 

 

 

Funcionamiento del Applet:

 

 

 

Controles:

 

·      Botón izquierdo del ratón: Para rotar.

·      Botón del medio del ratón: Para hacer zoom.

·      Botón derecho del ratón: Para mover.

 

Características:

 1:Fitness Functions: Aquí el usuario puede elegir entre cinco funciones de fitness. Las tareas de optimización del enjambre de partículas es encontrar el mínimo de las funciones. Todas las funciones se dibujan con un código de color en el que el rojo representa los mínimos y los amarillos los máximos valores de la función.

 

2: PSO Properties: Estas características afectan tanto a los tipos de PSO (3), el usuario puede elegir de cuántas partículas se compone un enjambre y durante cuántos pasos se ejecutará el proceso de optimización. 

 

3: PSO-Types: Elige uno de los dos tipos de PSO disponibles. El tipo “Constriction” está seleccionado por defecto.

 

4: Estándar PSO Parameters: Parámetros diferentes de PSO pueden ser ajustados para la implementación estándar. Estos parámetros no tienen efecto en el tipo “Constriction”. Se puede experimentar Fuertes efectos en el comportamiento de la partícula asó como en el rendimiento de PSO cuando se varían estos parámetros.

 

5:Optimization Panel: Una vez elegida la función de fitness, el proceso de optimización puede comenzar pulsando el botón de “Start Optmization”. El botón de “Stop/Clear Optimization” detendrá el proceso en ejecución y borrará la función de las partículas así como la ventana de “Optimization Progress” (10).Una optimización en ejecución puede ser pausada y después continuada pulsando los botones correspondientes. 

 

6: Movement Delay: El valor de retard determina cuánto tiempo pasa entre mostrar dos pasos. Este valor no tienen ninguna influencia en el comportamiento del enjambre solo influye en la visualización del movimiento de las partículas.

 

7: Value Range: El rango de valores determina por un lado para qué rango de valores se dibuja la función. Por otro lado, también para qué rango de valores se inicializa el enjambre de partículas. Variar este valor es cómo hacer zoom (acercarse o alejarse).

 

8: Grid Resolution: La resolución de los puntos de la función se puede modificar aquí. Cuantos más altos sean los valores más detallados serán los puntos, pero también afecta negativamente al rendimiento de los gráficos. Resoluciones demasiado altas pueden causar problemas de memoria.

 

9: Rendering Properties:

 

- Show Funcion Minimum: muestra una línea que intersecciona con la función en su mínimo.

 

-Show Path of best Particles: Dibuja una línea donde cada uno de sus vértices representa el major punto visitado por cualquier particular o de todo el enjambre hasta el momento. A veces la mejor manera de ver el camino es al mirar la función desde abajo.

 

- Wireframe Rendering: Elegir entre Wireframe y la función de procesado gráfico

 

- Solid Function Rendering. El procesado gráfico de Wireframe puede tener bugs dependiendo del hardware o drivers utilizados.

 

- Hide outliers: La implementación del PSO permite que las partículas se salgan del rango. Esta opción permite visualizarlas aunque se salga del rango inicial.

 

10: Optimization Progress: Una ventana de texto cada vez que el enjambre ha encontrado el mejor punto en la función de fitness sobre el paisaje el número de pasos y el valor de la función f(x,y) se muestran para este punto. 

 

11: Screenshot Panel: El botón de Captura de Imagen permite al usuario tomar una instantánea del lienzo en formato jpg. La ruta para guardar la imagen puede ser seleccionada por el usuario en un popup que se abrirá.

 

- White Background: Cambia el fondo a blanco. 

 

12: Help Bar: Proporciona información sobre el estado actual del programa, acciones que pueden ser tomadas e información adicional.

 

 

Funciones de fitness disponibles:

Rosenbrock:

rosenbrock (1K)

Mínimo global: f(x)=0; x(i)=1, i=1:n

 

 

Rastrigin:

rastrigin (1K)

Mínimo global: f(x)=0; x(i)=0, i=1:n

 

 

Griewangk:

griewangk (1K)

Mínimo global: f(x)=0; x(i)=0, i=1:n

 

 

De Jongs’s Sphere:

sphere (1K)

Mínimo global: f(x)=0; x(i)=0, i=1:n

  

 

Schaffer F6:

schaffer (1K)

Mínimo global: f(x,y)=0; x=0 y=0;

 

 

 

1.8 Vida Artificial

1.8.1 Selección Natural

Este applet permite explorar la selección natural mediante el control del medio ambiente, permitiendo causar mutaciones en los conejos.

Se trata de un ejemplo que permite entender muy fácilmente en qué consiste la selección natural, haciendo participativo al usuario, quien será el encargado de tratar de conservar la especie y lograr un equilibrio mediante su interacción.

Para su ejecución es imprescindible tener instalado Java, con indiferencia del sistema operativo que se disponga.

A continuación describiremos los parámetros que puede seleccionar el usuario con el fin de mantener la especie:

Mediante el botón situado en la parte superior “Add a friend” se pueden añadir más conejos a la aplicación. Estos se multiplicarán y crecerán de manera exponencial, por lo que para su supervivencia será necesaria la selección de un factor (a la derecha de la interfaz), ya sean lobos o alimentos, que ayuden al equilibrio de la especie. El entorno (soleado – “Equator” – o frío, todo nevado – “Artic” también ayuda al equilibrio de la misma).

Para mejorar la supervivencia de la especie, se pueden añadir mutaciones sobre los conejos, tales como que estos sean de color marrón (como la tierra, cuando el entorno seleccionado es “Equator”, para permitirles camuflarse y pasar desapercibidos ante la presencia de los lobos. Si el entorno es “Artic” son los blancos los que mejor se camuflan), o dispongan de dientes o cola más largos (para comer y defenderse mejor, y para saltar y huir mejor, respectivamente).

También es posible editar los genes disponibles para especificar cuáles se establecen como dominantes y cuáles recesivos: el color del conejo, la longitud de su cola y la de sus dientes.

Es posible seleccionar un conejo, en particular, y obtener su árbol genealógico a través de la opción “Pedigree” en Chart.

Además es posible detener la ejecución, mediante los dos botones inferiores de “Play” y “Pause”, ir observando la gráfica con la evolución a lo largo del tiempo y almacenar la configuración actual para volver a cargarla como configuración inicial en otra ocasión.

Para comenzar de nuevo con los valores predeterminados, basta con seleccionar el botón: “Reset All”.

A continuación vemos un ejemplo de la aplicación en ejecución:

 

1.8.2 Información adicional:

En la siguiente página pueden encontrarse unos cuantos enlaces relacionados con este apartado:

http://www.rennard.org/alife/english/liensgb.html

 

1.9 Metaheurísticas:

El siguiente applet es una sencilla demostración técnica para mostrar el principio de la optimización de rutas. Utiliza una herramienta de optimización comercial llamada Jopt. Esta herramienta es una sofisticada mezcla de meta-heruísticas con algoritmos meméticos..

           A partir de una asignación arbitraria de paradas de los vehículos y viajes, la demostración simula varias generaciones en un proceso en evolución, ordenando cada individuo que no satisface las constantes dadas (por ejemplo intervalos de tiempo y habilidades) mientras que se propagan los candidatos más prometedores. A través de una evolución permanente y una adecuada selección las generaciones se van adpatando progresivamente al problema dado. Mientras las generaciones pasan se percibe una reducción del coste y un encaminamiento hacia la solución óptima en cuanto a los objetivos dados.

Para comenzar la ejecución del applet basta con pulsar el botón “start” situado en la parte inferior. Entre los parámetros iniciales se puede seleccionar una o dos paradas, y dos o cuatro vehículos. Se puede pausar la ejecución para luego volver a continuar (botón “pause”) o reiniciar con nuevos parámetros (“reset”). En la sección izquierda del mapa puede verse el coste total, el número de generaciones, las restricciones y el tiempo total, así como la secuencia de ciudades de Alemania por las que se va pasando.