Práctica Algoritmos Genéticos

    Juego de la Minoria probabilístico (archivo minoria.m)


    Este ejemplo es un juego de la minoría en el Bar sobre estrategias 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:

    Algoritmo Genético para resolver el problema de Asignación o Partición (partition-ga.zip) (ga_binary_new.m ga_fitness.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 genomas. Cada genoma está compuesto por un vector de 1 o 0 de dimensión k. Estos genomas viven en una estructura llamada especie, que además contiene el fitness (vector de dimensión m) de cada genoma.

    La evolución genética incluye crossover simple de un solo punto (se eligen dos genomas al azar y se intercambian las porciones que resultan de divir cada genoma en un punto). Además hay una mutación para un genoma 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

    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.zip)

    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 mutado con 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:

    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: