Práctica Algoritmos Genéticos
Bar Attendance Game probabilístico (archivo bam.m)
Este ejemplo es una modificación del BAM tradicional donde las estrategias son probabilísticas: cada agente de 1 a N, tiene una probabilidad p_i de ir al Bar. Los agentes deciden si van o no al mismo tiempo, y se determina cuantos agentes terminan yendo. Si la mayoría fue al Bar, todos los que se quedaron se les suma un punto a su recompensa (payoff), mientras que los que terminaron en en la mayoría pierden un punto de su recompensa, Todos los agentes cuyas recomensas sean negativas, adaptan su estrategia, por lo que eligen un nuevo p_i aleatoriamente dentro de una pequeña ventana.
Vamos a observar cual es la distribución de estrategias y recomensas entre los agentes, como asi también una serie temporal del promedio de agentes que concurrieron al Bar.
Ejercicios:- Modifique la manera de actualizar las probabilidades.
Algoritmo Genético para resolver el problema de Asignación o Partición (partition-ga.zip) (ga_binary_new.m ga_cost.m ga_evolve.m ga_run.m)
Este ejemplo muestra un algoritmo genético para resolver el ‘problema de la asignación o partición’. El problema consiste
en dividir un vector de números enteros en dos subconjuntos cuya suma sea igual
Para ver un artículo interesante sobre el tema vean:
B. Hayes: “The Easiest Hard Problem”, American Scientist March p.113 (2002).
El algoritmo que implementamos hace evolución de una población m de chromosomas. Cada cromosoma está compuesto por un vector de 1 o 0 de dimensión k. Estos cromosomas viven en una estructura llamada genoma, que además contiene el fitness (vector de dimensión m) de cada cromosoma.
La evolución genética incluye crossover simple de un solo punto (se eligen dos cromosomas al azar y se intercambian las porciones que resultan de divir cada cromosoma en un punto). Además hay una mutación para un cromosoma elegido al azar de una bit elegido al azar. La misma consiste en invertirlo.
Problema de optimización de portfolio de inversión (invest-ga.tar.gz)
El problema es decidir en que proyectos de retorno fijo invertir. Suponganse que tenemos
- vector r con los retornos fijos de cada proyecto.
- vector c con los costos de cada proyecto.
- una cantidad w del dinero máximo que se dispone para invertir
- vector binario x que indica si el proyecto se invierte o no.
El problema es maximizar el beneficio r.c dado la restricción c.x <= w
Para una versión usando programación lineal vean invest-lp.m incluida en la carpeta descargada.
TSP Genético (tsp_ga.tar.gz)
ga_evolve.m | ga_perm_new..m | tsp_ga..m |
| tsp_pos_grupos.m |
|---|
Este ejemplo resuelve con un sencillo algoritmo genético el problema del viajante. Implementa un genoma de permutaciones.
Bar Attendance Game Genético (bam-ga.tar.gz)
Este ejemplo es una versión del juego BAM tradicional donde las estrategias son son ‘planes’ de concurrencia/no concurrencia al bar para los próximos m días. La implementacion que se presenta no es sencilla de seguir, asi que recomendamos que estudien este algoritmo en modo debug dentro del Matlab.
Cada agente tiene una población npop de estrategias inicializadas al azar, e iterativamente van eligiendo la mejor estrategia en cada paso de tiempo, para decidir si van o no van al bar. Una vez que todos juegan, se computa si el bar superó el umbral de tolerancia #ocupacion#, para determinar si los agentes que se quedaron en su casa o los que fueron al bar están ‘contentos’. Esto se materializa dándole un punto a cada estrategia de la población de cada agente (de manera de saber si estrategias alternativas, pueden mejorar la vigente actualmente).
Las particularidades del código son:
- con probabilidad #pevol# los agentes actualizan por medio del algoritmo genético las estrategias que estrategia van a elegir para su próxima semana de #m# días.
- el algoritmo genético es super-básico: las estrategias usan una representación binaria, se eligen 2 estrategias para hacer #crossover# (de un punto) y se elige una estrategia al azar para realizar una mutación en solo una posición.
Para correr el algoritmo usar:
st, plan, a = bam(occupation, npop, m, niter, pevol, seed)
Como ejemplo puede usar:
st, plan, a = bam_ga(0.8, 15, 6, 100, 0.15, 134)
Para mostrar la ocupación promedio para el próximo período
mean(plan)
Para plotear la ocupación media:
plot(st.occ_list,’r-‘)
Ejercicios:- Modifique el código para que el algoritmo genéticas preserve un número de estrategias para la próxima generación (‘elitismo’).