Algoritmos Genéticos II: Ejercicio práctico.

 Índice:

1. Introducción al contexto del ejemplo. 

2. Breve descripción de la estructura expuesta

3. Estudio del algoritmo Genético desarrollado. 

   3.1. Objetivo.

   3.2. Solución al problema propuesto. 

   3.3. Funcionamiento del algoritmo. 

   3.4. Ventajas e inconvenientes detectados. 

   3.5. Pruebas y resultados. 

4. Conclusión.  

1. Introducción.

Como breve introducción, se resaltan unas breves pinceladas sobre el trabajo realizado.

En primer lugar, se ha desarrollado e implementado un algoritmo genético, para abarcar de forma concreta los objetivos del ejercicio. Este algoritmo a su vez, se ha intentado mejorar con distintas funciones de cruce y con distintos métodos de mutación, siendo el resultado expuesto en la memoria el que mejor puntuaciones obtenía.

Por último se hablará  de las diferencias entre el algoritmo desarrollado con diferentes funciones de cruce y se obtendrá una conclusión.

2. Breve descripción de la estructura de la memoria.

    A continuación se detalla la estructura que seguirá en el presente ejemplo práctico, para facilitar en la medida de lo posible su comprensión, en cada apartado aparecerá de forma aproximada el siguiente guión:

·  Objetivo: Se comenta brevemente los que se quiere conseguir, y cuál es el algoritmo a desarrollar.

·  Solución al problema propuesto: Es decir, cómo ha sido resuelto el problema desde un punto de vista conceptual y sin entrar en detalles de implementación (si se nombrarán algunas funciones y variables del algoritmo para que sea comprensible).

·   Funcionamiento del algoritmo: Detalles sobre el desarrollo del algoritmo.

· Ventajas e inconvenientes detectados: Antes y después del proceso de implementación.

· Pruebas y resultados: Testeo del funcionamiento del algoritmo con el mayor detalle posible.

Además,  en la descripción de los algoritmos se pretenderá utilizar una notación y un nivel de detalle que  faciliten la comprensión de los mismos.

3. Estudio del algoritmo Genético desarrollado.

     3.1. Objetivo.

    El objetivo principal de este ejemplo es desarrollar un algoritmo genérico para comprender así con un mayor detalle el paradigma de la computación evolutiva en general, y los algoritmos genéticos (AG) en particular. ( Véase: Algoritmos  Genéticos I )

Por tanto los objetivos a cubrir son los siguientes:

· Codificar el problema planteado para su resolución con un AG.

· Implementar un agente PacMan viajante que utilice el algoritmo genético planteado para resolver su problema.

· Comparativa experimental de la solución del problema con diferentes parámetros.

         3.2. Solución al problema propuesto.

     Al intentar resolver este tipo de problemas, es necesario establecer una serie de pautas que ayudarán a determinar un orden en su resolución. Para ello, se establecerán una serie de simplificaciones, desde un punto de vista conceptual, que serán útiles para dejar las ideas un poco más claras, dejando así, de forma transitoria de lado la parte de implementación del algoritmo, para centrarnos exclusivamente en la idea de resolución del problema.

     Al tratarse de algoritmos genéticos, se establecerá que cada individuo de nuestra población será un vector con los índices de las diferentes ciudades existentes en el tablero, cuya ordenación será exactamente el orden en que serán visitadas. Inicialmente el tamaño de la población será de 100 habitantes y será generada de forma aleatoria.

     Por otro lado, se tendrá una función de evaluación o fitnes, que nos dará como de bueno es nuestro individuo. De este modo, nos basaremos en la distancia total en recorrer todas las ciudades para determinar este aspecto, siendo en cuyo caso una función de evaluación totalmente directa.

     Además de todo lo anterior, se establecerá un método de selección por torneos. Se ha de destacar que se seleccionarán los padres mejores de cada población, basándonos en su función de evaluación detallada anteriormente, desechando así los peores de esta.

   Por otro lado, se especifican además operaciones de cruce, donde se generarán nuevos “hijos” a través de los padres seleccionados anteriormente, este aspecto es relatado de forma detallada en el punto 3.3 de esta entrada, aunque simplemente nos basamos en los primeros  números de ciudades pares y en los últimos impares para realizar este cruce.

     En este contexto se ha de mencionar que se intenta además realizar un cruce que sea más aleatorio, y en el que se obtienen peores resultados.

    Por último, se desarrolla también una mutación para los diferentes individuos. Esta será solo realizada si obtenemos un porcentaje aleatorio de menos del 13%, y consistirá en intercambiar las posiciones de las diferentes ciudades dentro del individuo.

         3.3. Funcionamiento del algoritmo.

       Para empezar se crea una población inicial, llamando a la función generaSolucionInicial, que será del tamaño que  indique  la variable global tamPoblacion. El tamaño de cada individuo de la población viene dado por la variable size, pasada como parámetro a la función getRoute. 

     Lo que hará esta función es crear el número de individuos que se necesiten en la población que definimos, de tal manera que cada parámetro o gen de cada individuo es un número aleatorio entre 1 y (size-1), pero con la restricción de que no se pueda repetir el mismo número en genes distintos de un mismo individuo.

    Una vez que se tiene la población inicial guardada en un array, evaluamos cada individuo y guardamos todas estas puntuaciones en un array, de tal manera que la posición 0 de la lista de individuos, contiene al individuo cuya puntuación está en la posición 0 del array.

     Las puntuaciones en este caso, se corresponden con la distancia recorrida por el PacMan hasta pasar por todas las ciudades. Por tanto, obtendremos mayor puntuación cuanto menor sea esta distancia.

     Ordenamos entonces tanto la población como el array de distancias, de tal manera que los individuos con más puntuación se quedaran en las posiciones más bajas del array. Es decir, se realiza un ordenación por distancias de menor a mayor.

      Con todo esto, ya tenemos la situación inicial que nos permitirá continuar ejecutando el algoritmo. A partir de este momento se comienza con los pasos del algoritmo que irán generando las generaciones sucesivas.

      Esta parte del código se ejecutara tantas veces como número de generaciones máximas establezcamos. El número de generaciones máximas se establece en la variable global llamada maximaGen. En cada ejecución de este bucle se tiene una población y unas distancias asociadas a cada individuo de esta.

      Usamos como método de selección, el método de torneos. Se realizaran en cada iteración una cantidad de torneos igual al tamaño de la población menos el número de padres que se conservaran, pues en cada paso se conservaran los mejores padres que se seleccionen en los torneos.

      Cada uno de los torneos que se realizan “enfrentara” a un número de individuos que se establece en la variable individuosPorTorneo.             A la función que realiza los torneos le pasaremos el array de distancias y la población, de tal manera que el procedimiento que sigue este método será el siguiente:

•  Se generará una cantidad de números aleatorios igual a individuosPorTorneo, siempre comprobando que no se generen números repetidos, el rango de estos números será entre 0 y el tamaño de la población.
• 
  
•      Una vez que tenemos estos números que se corresponden con los índices de los padres que intervendrán en el torneo, seleccionamos el índice de la menor de las distancias del array.
• 
  
•    Este índice será lo que devolverá el método, que dará lugar al padre ganador del torneo.

      Cada padre que sale de un torneo será añadido a un nuevo array llamado padres. Así cuando todos los torneos se hayan realizado tendremos el array de padres que serán combinados para crear la nueva generación.

      Posteriormente, llamamos al método recombinar, pasándole la lista de padres como parámetro. De estos padres seleccionamos a los mejores, estos pasaran a la siguiente generación directamente sin ser cruzados. El número de padres que no se cruzan viene dado por la variable elementosConservados. El resto de individuos restantes hasta completar el tamaño de la población se obtendrás realizando cruces entre los padres. Para ello llamaremos a la  función cruce a la que le pasaremos el array de padres como parámetro.

      La función de cruce selecciona los padres 2 a 2, de forma consecutiva, es decir, primero el 0 con el 1, después el 2 con el 3… etc. Teniendo los dos padres, se generan por cada par de padres dos hijos siguiendo la siguiente operación.

 El cruce se realiza de la siguiente manera:

·     Buscamos el primer número par del padre 1.

·     Obtenemos el índice de la posición donde se encuentra el número anterior en el padre 2.

·     Buscamos el primer número par del padre 2.

·     Obtenemos el índice de la posición donde se encuentra el número anterior en el padre 1.

·     Intercambiamos los valores anteriores.

·     Buscamos el último número impar del padre 1.

·     Obtenemos el índice de la posición donde se encuentra el número anterior en el padre 2.

·     Buscamos el último número impar del padre 2

·     Obtenemos el índice de la posición donde se encuentra el número anterior en el padre 1.

·     Intercambiamos los valores anteriores.

·     Guardamos los nuevos individuos en los arrays hijo0 e hijo1.

También disponemos de otra función de cruce, llamada cruce2, que se asemeja a la anterior, en la que los índices que se cambian son elegidos aleatoriamente, pero aunque genera mayor diversidad de individuos, los resultados obtenidos son peores.

      Al finalizar esta operación tenemos 2 hijos y con cada uno de ellos se llama a la función mutar, para ver si los individuos deben mutar o no.

      La función mutar, recibe como parámetro un hijo, entonces genera un número aleatorio entre 0 y 1 y si este es menor que la variable tope_mutacion el hijo muta, sino se devolverá igual que entro en el método sin modificarle nada.

      Si por el contrario el hijo debe mutar, se intercambian dos genes del hijo aleatoriamente, así nos aseguramos de que el hijo siga siendo válido al no repetirse ningún gen igual en el mismo individuo.        

Se devuelve después el hijo mutado y la función de cruce coge todos los hijos y los va añadiendo a la nueva generación junto a los mejores padres que hemos seleccionado antes.

      De esta manera para la siguiente iteración tendremos como población la nueva generación, la evaluaremos y procederemos igual que antes hasta que se llegue al máximo de generaciones. En la última generación seleccionaremos al mejor hijo.

          3.4. Ventajas e Inconvenientes detectados.

Tras realizar varias pruebas, se detecta que los algoritmos genéticos son realmente rápidos y tiene la ventaja de que siempre encuentran una solución (aunque a veces no sea la óptima).

De otra forma, en el contexto de la práctica no se necesitan conocimientos específicos sobre el problema para intentar resolverlo.

Además, se basan en operadores probabilísticos, en vez de los típicos operadores determinísticos de las otras técnicas.

Por otro lado Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen tamaño de la población, número de generaciones, etc.-. O pueden converger prematuramente debido a una serie de problemas de diversa índole.

          3.5. Pruebas y resultados.

Para comprobar las distintas puntuaciones obtenidas se realizan 5 ejecuciones con el algoritmo genético desarrollado y se compara con la máxima puntuación que se puede obtener en los resultados. Se ha de destacar que cada ejecución consta de 10 niveles. Si se utiliza la función cruce:

Puntuaciones	Alg. Genético.	Puntuación Máxima
Ejecución 1.	2501	2700
Ejecución 2.	2621	2700
Ejecución 3.	2521	2700
Ejecución 4.	2468	2700
Ejecución 5.	2596	2700

Su se usa  la función cruce2:

Puntuaciones	Alg. Genético.	Puntuación Máxima
Ejecución 1.	2099	2700
Ejecución 2.	2194	2700
Ejecución 3.	2123	2700
Ejecución 4.	2106	2700
Ejecución 5.	2197	2700

Como se puede intuir, el algoritmo genético (cruce)  desarrollado obtiene siempre una mayor puntuación que el algoritmo con la función cruce2.

4. Conclusión.

    Tras la realización de las diferentes pruebas y resultados, se llega a la conclusión que tiene una grandísima importancia la elección de un buen mecanismo de cruce y mutación para la resolución de problemas genéticos.

    Además es muy importante establecer cada individuo de la mejor forma posible, ya que esto es un factor que también tiene relación directa en su resolución.

    Se observa que en ningún se alcanza la puntuación máxima, pero si se aproxima bastante a esta pues se ha de recordar que el uso de Algoritmos Genéticos es una técnica robusta, y puede tratar con éxito una gran variedad de problemas provenientes de diferentes áreas, incluyendo aquellos en los que otros métodos encuentran dificultades.

    Si bien no se garantiza que el Algoritmo Genético encuentre la solución óptima, del problema, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimización combinatoria. En el caso de que existan técnicas especializadas o más idóneas para resolver un determinado problema, lo más probable es que superen al Algoritmo Genético, tanto en rapidez como en eficacia.