Búsqueda Online y Algoritmos Genéticos
- Implementar utilizando algoritmos genéticos una solución para el TSP
- Implementar el algoritmo de Búsqueda DFS-Online, para un problema de exploración
- Algoritmos Genéticos para el Problema del TSP (Agente Viajero)
Veamos el caso de 20 ciudades, en la siguiente figura mostrada, observamos que para ejecutar la aplicación, hemos considerado como número máximo de Iteraciones una cantidad de 6000, como Probabilidad de Mutación de 0.01 (1%), como Probabilidad de Cruzamiento de 0.8 (80%), como tamaño de Población 240, ¿Qué significa lo anterior mencionado?, pues bien como se ha considerado un número máximo de iteraciones, pero ese máximo de iteraciones solo es alcanzado si antes de ese número, nuestro algoritmo no llega a converger, en nuestro ejemplo por ejemplo si convergió y solamente realizó 1176 iteraciones (denominamos itearciones a lo que tambien se le conoce como generaciones). Ahora la probabilidad de mutación tiene que ser muy pequeña (ejemplo 0.01, 0.005), para que no se asemeja al de una búsqueda aleatoria, por otro lado la Probabilidad de Cruzamiento es alta (ejemplo 0.8, 0.9 esto dependiendo el caso), el Tamaño de Población se refiere al número de individuos de una determinada generación, donde un individuo es una posible solución o un camino o ruta de ciudades.
Bueno también podemos observar el Mejor Inicio, es decir el mejor individuo de la población Inicial (el de menor función de evaluación), con su respectivo valor de Función de Evaluación, q en este caso es de 2944.7656396425014; asi mismo la Solución respectiva con su valor de Función de Evaluación de 1718.835770134992, donde vemos que luego de haber evolucionado de generación en generación su Funcion de Evaluación a mejorado. El tamaño de población escogido influye en mejora a través de las generaciones, es decir según nuestras pruebas realizadas, si el tamaño de población es mayor, entonces se llegan a obtener mejores resultados.
Ahora como fue desarrollado el Algoritmo Genético, pues bien, creamos nuestra población aleatoria inicial (del tamaño de población ingresado), es decir, creamos individuos de forma aleatoria, cada uno con su ruta de ciudades respectiva, lo que denominaremos "cromosoma" y su función de evaluación respectivo. Cada individuo es insertad en una cola de Prioridad conforme se vaya generando la población, y donde así tendremos que la cabeza de la cola es la mejor solución :D ...
Luego comenzamos a iterar ("evolucionar"), generando una nueva población a partir de la anterior, donde utilizamos la selección Elitista, es decir los dos mejores de la generacion se preservan, el resto es generado mediante cruzamiento o mutación de los que quedan en la poblacion anterior. Ahora para generar la nueva población se considera también lo siguiente: escogemos un padre una madre (se trata que sea diferente del padre) aleatoriamente, luego escogemos un numero aleatorio (entre 0 y 1) y si ese valor es menor o igual que la probabilidad de cruzamiento, entonces se procede a cruzar (con un punto de cruzamiento aleatorio) padre con la madre (y viceversa: madre con padre) entonces, (para cada uno de los cruzamientos realizados), se procede a escoger otro número aleatorio ( entre 0 y 1) y si sale menor que la probabilidad de mutación entonces se procede a mutar el individuo generado por el cruzamiento, sino éste pasa a la nueva población, por otro lado, si es mayor que la probabilidad de cruzamiento, entonces los padres pasan a la siguiente generación sin ser cruzados ni mutados.
Ahora, sabemos que al momento de cruzarse se pueden generar un individuo con ciudades repetidas y esto según el problema del TSP no puede ser, para ello, lo que se hace es convertir el cromosoma de cada individuo a una forma ordinal, utilizando una forma canónica y luego cruzar, y luego de ello, aplicar la forma inversa de los pasos para obtener el nuevo individuo. Ver lo siguiente para un mejor entendimiento
En la figura anterior se muestra por ejemplo se tiene la ruta actual (tour) con las ciudades: 1 2 5 6 4 3 8 7, y la ruta Canónica (fija): 1 2 3 4 5 6 7 8, donde de acuerdo a la posicion que se encuentra el dato analizado de la ruta actual en la ruta Canonica, esa posicion se pone en la representación ordinal. Ejemplo el 1 de la ruta actual se encuentra en la posicion 1 de la ruta Canonica, entonces se pone 1 en la representacion ordinal y luego se elimina de la ruta canonica el evaluado y se continua con la siguiente de la ruta actual... Ahora veamos el cruzamiento, como ya se mencionó se obtiene un punto de cruce aleatorio, por ejemplo 2, entonces se procede a cruzar ambos padres (en su forma canónica) y se genera un nuevo individuo, donde aplicandole los pasos anteriores en forma inversa a la representación ordinal, se obtiene el individuo generado, sin ciudades repetidas.
Bueno se realizaron varios experimentos intercambiando población, orden incial, etc., los mismos que se encuentran en el informe respectivo al tema, a continuación un gráfico donde se muestra uno de los experimentos realizados, comparando a los algoritmos genéticos con el algoritmo HIll Climbing, donde podemos observar que los algoritmos genéticos nos dieron mejores resultados... :D
- Búsqueda DFS-Online para un pequeño laberinto
Donde se visualiza la interfaz grafica, a traves del cual ingresamos la posicion inicial y la posicion meta, luego pulsamos el boton ejecutar, para realizar la busqueda, a la vez vemos la actualización del estado, tanto desde el inicio hasta cuando llega a la meta, y los pasos realizados para ello:
No comments:
Post a Comment