Download Algoritmo Evolutivo Multiobjetivo

Computación Evolutiva: un repaso
a las técnicas más utilizadas y su
aplicación en MASS.
Carlos Cervigón
Contenidos
Orígenes y antecedentes biológicos
Estructura general de un algoritmo evolutivo AE
Modelos sobre el esquema general
Algoritmo genético simple
Mejoras y alternativas al AGS
Programación genética








Programación automática.
Arte Evolutivo
Extensiones de un AE




1
Algoritmos Evolutivos Multiobjetivo
Algoritmos Evolutivos Paralelos
Algoritmos Evolutivos Meméticos, híbridos
Algoritmos Evolutivos
Contenidos
Vida artificial
Inteligencia colectiva:
 Optimización basada en colonias de hormigas ACO
 Optimización basada en partículas PSO
EC (Evolutionary Computation) y MASS (Multi-Agent
System and Simulaton)





2
Métodos de computación evolutiva aplicados a la simulación
con sistemas multi-agente
Ejemplos ECOMASS
Algoritmos Evolutivos
* What is an Agent ?
External Definition : a real or virtual entity that

evolves in an environment, that is able to perceive
this environment, that is able to act in this environment,
that is able to communicate with other agents, and that
exhibits an autonomous behaviour


autonomous agents, robots
the autonomy principle
* Purposive Multi-Agent Systems
Yves DEMAZEAU
3
Algoritmos Evolutivos
Orígenes
Los Algoritmos Evolutivos recogen un conjunto de
modelos basados en la evolución de los seres vivos.
Inspirados en la Naturaleza.
Basados en la teoría de la evolución de Darwin: cambio
adaptativo de las especies por el principio de la selección
natural
Se favorece la supervivencia y evolución de aquellas
especies que están mejor adaptadas a las condiciones de
su entorno.




4
Algoritmos Evolutivos
Antecedentes biológicos
5

Cromosoma : cadena
de ADN que se
encuentra en el núcleo
de las células

Gen: sección de ADN

Alelo es cada una de
las formas del gen
Algoritmos Evolutivos
Estructura de un algoritmo evolutivo
Un AE trabaja con una población de individuos, que
representan soluciones candidatas a un problema.
Esta población se somete a ciertas transformaciones y a
un proceso de selección, que favorece a los mejores,
según su aptitud. En la población tiene que haber
diversidad.
Cada ciclo de transformación y selección constituye una
generación.
Se espera que después de cierto número de generaciones
el mejor individuo de la población esté cerca de la
solución buscada.




6
Algoritmos Evolutivos
Estructura de un algoritmo evolutivo
Población inicial
Selección
Cruce
Mutación
7
Algoritmos Evolutivos
Esquema general
8
Algoritmos Evolutivos
Esquema Algoritmo Genético Simple
Inicializar aleatoriamente una población P con soluciones candidatas
Evaluar cada individuo de P
Mientras no se cumpla condición de parada
1. Seleccionar progenitores S de P
2. Recombinar progenitores seleccionados obteniendo descendencia D
3. Mutar descendencia D
4. Evaluar nuevos candidatos
¿Selección = Competencia ?
¿Recombinación = Cooperación ?
9
Algoritmos Evolutivos
Modelos sobre el esquema general

Algoritmos Genéticos:


Estrategias Evolutivas:


Población de individuos como valores con codificación real
Programas Evolutivos:


Población de individuos como cadenas binarias.
Población de individuos representados mediante estructuras
de datos
Programas Genéticos:

10
Población de individuos como programas o expresiones
Algoritmos Evolutivos
Modelos sobre el esquema general

De Jong dice que estas variantes son realmente instancias
concretas de un Sistema Evolutivo General que incluye:




11
Una o más poblaciones de individuos compitiendo por
recursos limitados.
Poblaciones cambiantes por el nacimiento y muerte de
individuos
El concepto de fitness (aptitud) que refleja la capacidad de un
individuo de sobrevivir y reproducirse
El concepto de herencia modificada: los descendientes se
parecen a sus padres pero no son idénticos
Algoritmos Evolutivos
Aspectos implicados

Búsqueda

Optimización: El objetivo es encontrar un conjunto de
parámetros tales que maximicen o minimicen cierto
criterio de calidad.


12
Optimización Numérica
Optimización Combinatoria
Algoritmos Evolutivos
AG simple: operadores genéticos


Hacen evolucionar a la población y permiten la convergencia
Se aplican con una determinada probabilidad




Selección : Ruleta, Torneo, Ranking …
Cruce: Un punto,Varios …
Mutación: Fija , Variable …
Parámetros típicos de un Algoritmo genético:
Criterio de terminación, número máximo de generaciones
 Tamaño de la población
 Probabilidad de cruce, Pc
 Probabilidad de mutación, Pm
 Política de reemplazo
...

13
Algoritmos Evolutivos
Operadores genéticos

Operador de cruce: actúa sobre parejas de individuos y los
descendientes combinan características de los progenitores.

Operador de mutación: operador básico de alteración y se
aplica a algunos individuos realizando una pequeña
modificación en alguno de sus genes o en el conjunto.
14
Algoritmos Evolutivos
Otras mejoras y alternativas

Asegurar diversidad de aptitudes e individuos

Mecanismos de selección mejorados
Desplazamiento o escalado de la aptitud

Elitismo:


se reservan los k mejores individuos de la
generación anterior. Mecanismo fundamental para alcanzar el
valor óptimo y acelerar la convergencia
Inclusión de conocimiento específico del problema




15
Codificación adaptada al problema
Introducción de restricciones a las soluciones
Construcción de nuevos operadores
Creación de algoritmos híbridos con otras técnicas heurísticas
Algoritmos Evolutivos
Codificación adaptada al problema


Representación TSP: Enumeración de las ciudades en orden.
Para un problema con nueve ciudades el recorrido
7  8  3 1  6  4  2  5
Se representa con el individuo:
7

8
3
1
6
4
2
5
Los operadores de cruce son más complejos y son específicos
de cada representación:


16
PMX, OX, CX, ERX, ordinal. . .
Intercambio, inserción, heurístico…
Algoritmos Evolutivos
Programación genética



Hacer evolucionar programas o instrucciones
representadas en forma de árbol
Aplica un proceso evolutivo a una población de
programas
Los individuos se almacenan en un árbol



los nodos representan funciones
Las hojas representan símbolos terminales
Todos los programas en la población inicial han de ser
sintácticamente correctos (ejecutables) y los operadores
genéticos (cruce, mutación, …) también han de producir
programas sintácticamente correctos
17
Algoritmos Evolutivos
Ejemplo : Representación

Representamos cada individuo se representa mediante un
árbol. Por ejemplo:
18
Algoritmos Evolutivos
Operador cruce
19
Algoritmos Evolutivos
Operador mutación
La mutación consiste en generar un nuevo programa a
partir de un único individuo.



20
Mutación terminal
Mutación funcional
Mutación de árbol
Algoritmos Evolutivos
Ejemplo: Apilamiento de bloques (Koza)

El objetivo es encontrar un programa que a partir de una
configuración inicial de bloques los coloque en el orden
correcto en la pila. Objetivo: UNIVERSAL.
21
Algoritmos Evolutivos
Ejemplo: Apilamiento de bloques (Koza)

Terminales:




CP (cima pila):
BS (bloque superior correcto)
SN (siguiente necesario)
Funciones





22
MP <x>(Mover a pila)
MM <x>(Mover a mesa.)
DU(acción, predicado) (“do until”)
NOT(expresión1)
EQ(expresión1, expresión2)
Algoritmos Evolutivos
Ejemplo: Apilamiento de bloques (Koza)

El algoritmo trabaja con árboles que representan
programas construidos con los terminales y funciones
descritos. El programa:
(EQ(MP SN) (EQ (MP SN) (MP SN)))
Mueve el siguiente bloque que se necesite a la pila tres veces:

La aptitud de cada programa es número de casos de
prueba en los que se produce el resultado correcto
23
Algoritmos Evolutivos
Ejemplo: Apilamiento de bloques (Koza)
(EQ (MM CP) SN)

Mover la cima actual de la pila a la mesa, y ver si es igual al
siguiente necesario. Aptitud 0.
(MP BS)

Mover a la pila el bloque más alto correcto de la pila. Aptitud 1
(EQ(MP SN) (EQ (MP SN) (MP SN)))

Mover el siguiente bloque que se necesite a la pila tres veces.
Aptitud 4
(EQ (DU (MM CP) (NOT CP)) (DU (MP SN) (NOT SN)))

24
Vacía la pila sobre la mesa y después mueve el siguiente bloque
que se necesita a la pila hasta que ya no se necesitan más
bloques. Aptitud 166
Algoritmos Evolutivos
Ejemplo: Rastro de Santa Fe

Se trata de buscar la estrategia de movimientos de una hormiga
artificial capaz de encontrar toda la comida situada a lo largo de un
rastro irregular.
25
Algoritmos Evolutivos
Ejemplo: Rastro de Santa Fe
 Terminales:
AVANZA (A)
DERECHA (D)
IZQUIERDA (I)
SIC
PROG2
PROG3

Funciones
SIC (a,b)
PROG2 (a,b)
PROG3 (a,b,c)
A
A
A
A
A
(SIC (PROG3N (AVANZA IZQUIERDA AVANZA))
(PROG2N (IZQUIERDA AVANZA)))
26
Algoritmos Evolutivos
Ejemplo: Rastro de Santa Fe
27
Algoritmos Evolutivos
Arte Evolutivo


La idea es utilizar algoritmos evolutivos para hacer
evolucionar las imágenes, música, etc, sobre una base
estética, en lugar de una función de aptitud estricta.
La función de aptitud la proporciona el usuario que
selecciona sus individuos "favoritos" para la reproducción.
Evolving Assemblages, by Fernando
Graça and Penousal Machado
28
Algoritmos Evolutivos
Arte Evolutivo
1.
2.
3.
4.
29
Se genera una población aleatoria de imágenes
El usuario las evalúa y asigna un valor de aptitud
La selección se realiza según la aptitud o “calidad” : las
imágenes con los valores de aptitud más altos tienen
mayores probabilidades de ser seleccionadas para
reproducción
El programa crea una nueva población de imágenes
mediante el cruce y mutación de los individuos
(imágenes) de la población actual
Algoritmos Evolutivos
Arte Evolutivo





Los individuos son imágenes y el genotipo es un árbol con
funciones y terminales.
Se utilizan funciones simples: operaciones aritméticas,
trigonométricas, lógicas, etc.
El conjunto de terminales serán variables y constantes
La imágenes son representaciones gráficas de expresiones
matemáticas.
Cruce y mutaciones de la imágenes (árboles)
30
Algoritmos Evolutivos
Arte Evolutivo

La expresión

Gráfica 3-d de la expresión f (x) = (x + y) / 2

Imagen generada por la asignación de un
valor de escala de grises a cada valor de
f(x).
f (x) = (x + y) / 2
en formato de árbol
/
+
x
31
2
y
Algoritmos Evolutivos
Arte Evolutivo : ejemplos
32
Algoritmos Evolutivos
Otras extensiones del algoritmo genético
Algoritmos Evolutivos Multiobjetivo
 Algoritmos Evolutivos Paralelos
 Algoritmos meméticos, híbridos
 Algoritmos de Estimación de Distribuciones

33
Algoritmos Evolutivos
Algoritmo Evolutivo Multiobjetivo

Optimizar simultáneamente varias funciones
Optimizar



 sujeto a



(i = 1, , n)
x  X  Rm
El óptimo global ya no es inmediato:


f i ( x)
¿Optimizar una función sacrificando el resto, la media de todas
las funciones …?
Óptimo de Pareto: una solución xX es un óptimo de
Pareto cuando no existe ninguna solución mejor en
ningún objetivo: soluciones no dominadas
34
Algoritmos Evolutivos
Algoritmos evolutivos Multiobjetivo

Algoritmos que no utilizan el concepto de dominancia

Funciones agregativas lineales
f ( x) = w1 f1 ( x)  w2 f 2 ( x)    wk f k ( x)

Algoritmos que sí utilizan el concepto de dominancia
 VEGA: selección proporcional según las funciones a optimizar
 MOGA (Multi-Objective Genetic Algorithm)
 NSGA-II (Elitist Non-Dominated Sorting Genetic Algorithm)
 SPEA, SPEA2, MOMGA, MOMGA-II, PAES. . .

Aplicaciones: Planificación,
empaquetado, diseño de circuitos, diseño de
sistemas de control, detección de ataques en redes, procesamiento de imágenes,
problemas de predicción, optimización de párametros en mercados financieros*,
etc.
* Multiobjective optimization of technical market indicators. Diego J. Bodas-Sagi, Pablo Fernández, José
Ignacio Hidalgo, Francisco J. Soltero, José Luis Risco-Martín.
35
Algoritmos Evolutivos
Algoritmos Evolutivos Paralelos
Paralelización Global
(Misma estructura del AG)
1.
2.
Ejecución de varios AGs en Paralelo
Sólo la Evaluación en paralelo
Grano Grueso
(Islas)
Subpoblaciones que evolucionan
por separado
(Cambia la estructura del AG)
Grano Fino
(AC)
Híbrido
(grano fino y
grueso)
36
Algoritmos Evolutivos
Grano grueso: Modelos de Islas




Se divide la población en subpoblaciones mas pequeñas que
evolucionan independientemente en cada procesador o isla.
En cada procesador se lleva a cabo un Algoritmo Evolutivo
Cada cierto número de generaciones (época) intercambian
individuos entre las poblaciones: migraciones. Esto genera
diversidad genética.
Diferentes topologías que define como se intercambian individuos



37
Anillo
Maestro-esclavo
Todos con todos
Algoritmos Evolutivos
Grano fino: modelo celular

Simula relaciones personales entre individuos de una misma localidad.
 Los individuos se disponen en una parrilla de dos dimensiones
con un individuo en cada una de las posiciones de la rejilla.
 La evaluación se realiza simultáneamente para todos los
individuos
 La selección, reproducción y cruce de forma local con un
reducido número de vecinos.
 Con el tiempo se van formando grupos de individuos que son
homogéneos genéticamente como resultado de la lenta difusión
de individuos.

38
aislamiento por distancia
Algoritmos Evolutivos
Algoritmos meméticos

Memes: unidades de información cultural (que se pueden
transmitir entre individuos), que engloban los conceptos, las
modas y las tradiciones de una sociedad. Rol análogo a los
genes en evolución cultural. (Dawkins, R. 1979 The Selfish Gene)




39
Algorítmo híbrido con operadores de búsqueda local que permite
a los individuos “cambiar” antes de crear la nueva población.
Los individuos pueden copiar o imitar “parte” de los genes de
otros individuos para mejorar su fitness
Nuevos operadores de búsqueda o incluir la información
memética en los operadores tradicionales de cruce y mutación
Lamarckiano, Baldwiniano
Algoritmos Evolutivos
Algoritmos de Estimación de
Distribuciones

EDA: variante del AE en la que las operaciones de cruce y mutación
se sustituyen por operadores que muestrean a partir de la
distribución de probabilidad de los mejores individuos.
Se reduce el número de parámetros

Pasos:






Partiendo de M individuos al azar, seleccionar un número N (N≤M) de
individuos, normalmente los de mejores valores de función objetivo.
Estimar la distribución de probabilidad Pi(x) de los individuos seleccionados.
Muestreo: generar al azar M individuos utilizando las distribuciones
obtenidas Pi(x) que constituyen la nueva población.
Individuos: una componente o gen por cada variable del problema
Dificultad: la estimación de la distribución de probabilidad conjunta
de los individuos seleccionados.
40
Algoritmos Evolutivos
Vida artificial




La vida artificial es el estudio, mediante procesos de simulación, de
sistemas artificiales con agentes simples con propiedades similares a
ciertos seres vivos.
Se simulan formas de vida simples y se analiza la aparición de
propiedades de autoadaptación a partir de interacciones locales
Los agentes tiene reglas muy simples y cooperan para resolver un
problema y a la vez compiten por un conjunto limitado de recursos
Pueden encontrarse analogías con los sistemas naturales en diversos
niveles, incluyendo partículas, células, órganos, individuos y
poblaciones:
 Algoritmos evolutivos EA, autómatas celulares CA

Swarm intelligence (Inteligencia colectiva) SI


41
Optimización basada en colonias de hormigas ACO
Optimización basada en grupos (enjambres) de partículas PSO
Algoritmos Evolutivos
Swarm Intelligence (Inteligencia Colectiva)




Se basa en el comportamiento colectivo de sistemas
naturales o artificiales descentralizados y auto
organizados
Suelen utilizar una población de agentes muy simples o
boids que interactúan entre sí y con su entorno.
Los agentes tiene una reglas muy simples y las
interacciones entre los agentes hacen que surja un
comportamiento global “inteligente”
Ejemplos: Colonias de hormigas, termitas, abejas, bandadas de
pájaros, bancos de peces...
42
Algoritmos Evolutivos
Optimización basada en colonias de
hormigas: ACO




Una hormiga se mueve al azar
Si descubre comida la hormiga
vuelve al nido dejando a su paso un
rastro de feromona atractivo para
otras que tenderán a seguir esa pista.
Las hormigas refuerzan la ruta más
corta pues la visitan más hormigas y el
rastro de feromona es mayor.
La ruta larga acaba desapareciendo al
volatilizarse la feromona. Al final todas
las hormigas "eligen" el camino más
corto
http://en.wikipedia.org/wiki/Ant_colony_optimization .
43
Algoritmos Evolutivos
ACO para el TSP







En cada iteración se "lanza" una colonia de m hormigas y cada hormiga
construye una solución al problema.
La regla probabilística para el caso del TSP es:
Probabilidad con la que, en una iteración t del algoritmo, la hormiga k, situada
actualmente en la ciudad i, elige a la ciudad j como próxima parada.
Conjunto de ciudades no visitadas todavía por la hormiga k.
Cantidad de feromona acumulada sobre el arco (i,j) de la red en la iteración t
(se actualiza en cada iteración y para cada arco).
Información heurística para la que, en el caso del TSP, se utiliza la inversa de la
distancia existente entre las ciudades i y j.
 y  son dos parámetros del algoritmo, los cuales hay que ajustar.
44
Algoritmos Evolutivos
Optimización basada en grupos de
partículas: PSO




45
Inspirado en los patrones de vuelo de las aves
Simula los movimientos de una población de aves buscando
comida: la estrategia es seguir al que está más cerca de la
comida
Una población de agentes (partículas), cuyas posiciones
en un espacio multidimensional representan posibles
soluciones, se mueven actualizando la velocidad según la
información recogida por el grupo (llamado enjambre).
En cada iteración, cada partícula está guiada por su mejor
posición anterior y por la mejor posición global.
Algoritmos Evolutivos
Algoritmo: PSO

Inicializa un grupo de partículas al azar (soluciones). En cada iteración, cada
partícula se actualiza según dos "mejores" valores.



pbest : la mejor solución (fitness) lograda hasta ahora por esa partícula.
gbest : el mejor valor obtenido hasta el momento por cualquier partícula de la
población. Mejor global
Cada partícula actualiza su velocidad y posición
Do
Para cada partícula
Calcular el mejor fitness obtenido hasta ahora pBest
Elegir la partícula con mejor fitness de todo el grupo gBest
Para cada partícula
Calcular velocidad según ecuación
v[]=v[] + c1*rand()*(pBest[]-pos[]) + c2*rand()*(gBest[]-pos[])
Actualizar la posición según ecuación
pos[] = pos[] + v[]
While no fin (iteraciones o error)
46
Algoritmos Evolutivos
Ejemplo de simulación con NetLogo

Aplicaciones: procesamiento de imágenes, diseño y optimización de redes,
diseño de antenas, planificación, clustering, clasificación y minería de datos*,
redes neuronales, robótica, diagnóstico de fallos, etc..
D. Martens, B. Baesens, T. Fawcett "Editorial Survey: Swarm Intelligence for Data Mining,"
Machine Learning, volume 82, number 1, pp. 1-42, 2011
47
Algoritmos Evolutivos
MASS

Simulación con Sistemas Multi-agente



Creación de sociedades artificiales en las que se representan los
individuos y las organizaciones con la finalidad de observar los
efectos de sus interacciones y la emergencia
¿Y si empleamos técnicas de Computación Evolutiva (EC)
como ayuda en este proceso?
EC y MASS tratan con poblaciones de agentes.


48
EC: la población de agentes se adapta según la presión selectiva
ejercida por un entorno
MASS analiza la coordinación de las acciones de una población
(posiblemente egoísta) de agentes autónomos que comparten un
entorno para lograr un resultado.
Algoritmos Evolutivos
EC y MASS: puntos de estudio






49
Modelos basados en agentes que utilizan la computación
evolutiva. Optimización.
Modelos de computación evolutiva que se
basan en funciones de fitness definidas por las relaciones
entre agentes.
Evolución de la cooperación e integración de componentes
Representación genotípica de las complejas estrategias
de MASS
Aprendizaje evolutivo dentro de MASS
Fenómenos o comportamiento emergentes en sociedades
como consecuencia de la acción de sus componentes
Algoritmos Evolutivos
Ejemplo de simulación y EC*




Los agentes son hormigas artificiales que se comunican
directamente, no por feromonas.
Objetivo: Buscar comida ...
Las hormigas se preguntan unas a otras por la comida
Las hormigas mienten, se equivocan....


Cuando hay poca comida los agentes compiten y mienten creando
desconfianza. Aumenta el escepticismo.
Si hay mucha comida dejan de mentir y aumenta la confianza y comunicación
entre los agentes.
* Sistemas
multiagente. Juan
de Lara. UA.
50
Algoritmos Evolutivos
Ejemplo de simulación y EC

Cada agente tiene un genotipo que controla su comportamiento.

Mentira:

00: El agente siempre dice la verdad.

01: El agente da una posición aproximada.

10: El agente da una posición aleatoria.

11: El agente da la posición contraria.
51
cruce
Algoritmos Evolutivos
GECCO:
ECOMASS Workshop

Evolutionary Benefits of Evolvable Component Integration (David Malkin
and R. Beau Lotto)

Infection-Based Self-Configuration in Agent Societies (Salazar, RodriguezAguilar, Arcos)

Multiobjective evolutionary optimization of agent based models.” (Narzisi,
Mysore, Mishra)

Towards Incremental Social Learning in Optimization and Multiagent
Systems (Montes de Oca, Stutzle)
52
Algoritmos Evolutivos
GECCO:
ECOMASS Workshop

Asynchronous Collaborative Search using Adaptive Co-Evolving Subpopulations
(Chira, Gog and Dumitrescu)

Emergence of Cooperative Societies in Evolutionary Games (Kan-Leung Cheng,
Inon Zuckerman, Ugur Kuter, and Dana Nau)

Integrating Complex Adaptive System Simulation and Evolutionary Computation
to Support Water Infrastructure Threat Management (Emily M. Zechman)

An Agent-Based Collaborative Evolutionary Model for Multimodal Optimization
(Lung, Chira, Dumitrescu)

Autonomous Agent Behavior Generation Using Multiobjective Evolutionary
Optimization (Nowak, Lamont)
53
Algoritmos Evolutivos
Ejemplo 1: Evolución de la integración
“Evolutionary Benefits of Evolvable Component Integration” (David
Malkin; R. Beau Lotto)



La calidad de la función de aptitud depende de la fuerza en la interacción
de los componentes de un sistema
Estudio de la relación entre la interacción entre los componentes de un
sistema, la capacidad de evolución y la aptitud o fitness
Sistema artificial:
 Población 100 agentes: Cada agente 8 componentes
 Objetivo: moverse los más cerca posible de dos líneas ortogonales
 fitness de un componente: depende de su distancia a las líneas.
 fitness del agente: suma de la aptitudes de los componentes
54
Algoritmos Evolutivos
Ejemplo 1: Evolución de la integración



El agente tiene sensores “rojos" y "azules", para percibir la distancia a la
línea roja y a la azul. Los agentes intentan ir al punto de intersección de las
dos líneas. La orientación va rotando para no "memorizar" la intersección.
Cada componente sólo conoce la distancia a una de las líneas y no
intercambian información ni tienen memoria: un solo componente no
puede determinar cuál es la dirección adecuada.
Los componentes sólo encuentran la intersección de las dos líneas si
interactúan entre sí.
55
Algoritmos Evolutivos
Ejemplo 1: Evolución de la integración

Si aumenta la interacción de los componentes la población se va acercando
a los óptimos. Si no se hace evolucionar la intensidad de
la interacción entre componentes no se encontrará el óptimo global.

La dirección y velocidad de cualquier componente en un instante se
caracteriza por tres vectores de movimiento diferentes:

Vector de movimiento interno

Vector de movimiento externo: suma escalada de los vectores internos de las demás
componentes


56
S es la intensidad de la interacción entre componentes
Vector de movimiento absoluto: suma de los vectores de movimiento externo e interno
Algoritmos Evolutivos
Ejemplo 1: Evolución de la integración
Cuatro casos de prueba:
1. La intensidad de interacción entre componentes se fija a 1 (S = 1 en toda
la evolución)
2. S se codifica con un bit para representar integración total o nula
3. S se codifica con 2 bits para valores de integración de 0, 0.33, 0.66 y 1
4. S se codifica con 5 bits para que el nivel de la integración entre los
componentes sea {0,1 / 31,2 / 31, ..., 1}
57
Algoritmos Evolutivos
Ejemplo 2: Contagio de normas
“Infection-Based Self-Configuration in Agent Societies (Salazar,
Rodriguez-Aguilar, Arcos)




Las normas regulan el comportamiento de los agentes.
Sistema que facilita a los agentes evolucionar normas de forma
colaborativa, y auto configurarse para adaptarse a nuevas
condiciones.
Explota el concepto de infección positiva basándose en el
fenómeno de contagio social: Los agentes con buen
comportamiento se vuelven infecciosos para
difundir sus normas en la sociedad
Las normas siguen un proceso evolutivo ¿AE?
58
Algoritmos Evolutivos
Ejemplo 2: Contagio de normas
a) Un agente sondea los de alrededor para obtener información sobre sus normas,
b) Los agentes vecinos responden al sondeo
c) Se selecciona un agente (B) y se infecta
d) Cambian las normas del agente B
59
Algoritmos Evolutivos
Ejemplo 2: Contagio de normas


Se implementa con un algoritmos evolutivo distribuido.
El agente representa un individuo que codifica en su genotipo
reglas, normas, políticas. El fitness es el rendimiento del agente
repeat
shuffle the agents in the multi-agent system
if (tTincubation) then
foreach ag do
ag.evaluate()
ag’  ag.selection()
ag.infection(ag’, pinfection)
ag.mutation(pmutation)
end for
end if
until fin
60
Algoritmos Evolutivos
Ejemplo 2: Contagio de normas



Contagio de normas en un modelo que simula el tráfico
Cada coche aprenderá normas para minimizar los choques y
los atascos.
Cada agente evolutivo ai tiene dos acciones : avanzar, esperar
N0i : IF (car IN junction) AND (car-direction = north-to-south)
AND (othercar AT right) THEN X0i

Se busca la función de transición que nos lleva a
los valores de Xi que maximizan el bienestar social:

61
Factor del número de accidentes y tiempo de espera en un atasco.
Algoritmos Evolutivos
Ejemplo 3: Optimización de parámetros
“Multiobjective evolutionary optimization of agent based
models.” (Narzisi, Mysore, Mishra)

Objetivo: calibrar y ajustar los parámetros de los modelos
basados en agentes que se usan en simulación.
 Con herramientas como Netlogo podemos jugar con los
parámetros, pero es poco práctico en muchos sistemas
 Uso de un buscador que recorre los valores de los
parámetros en busca del valor que proporciona mejor
aptitud
 Se propone hacerlo con un algoritmo evolutivo multiobjetivo
(NSGA-II) en un sistema que simula un plan de
emergencia en la gestión de desastres urbanos.
62
Algoritmos Evolutivos
Ejemplo 4: Optimización de parámetros

Plan de emergencia en la gestión de
desastres urbanos.

Es un problema de ajuste de
parámetros de la interacción entre
diferentes clases de
agentes (hospitales, personas, ambulan
cias, etc) y los recursos disponibles para
reducir al mínimo las consecuencias
negativas de una catástrofe

OUTBREAK: modelo multi-agente
para simular desastres urbanos a
gran escala
63
Algoritmos Evolutivos
Ejemplo 4: Aprendizaje social incremental
Towards Incremental Social Learning in Optimization and
Multiagent Systems (Montes de Oca, Stutzle)

Aprendizaje social: mecanismo que permite a los individuos aprender
de los demás sin el coste de aprender solos

Aprendizaje social incremental: se parte de una pequeña
población de agentes que van aprendiendo socialmente al ir
formando parte de la población principal (de uno en uno) y luego
aprenden individualmente (niños-adultos).
Experimentos:
1.
Efectos del aprendizaje social incremental en un algoritmo de
optimización basado en partículas (PSO).
2.
Efectos del aprendizaje social incremental en un SMA donde los
agentes son capaces de aprender individualmente mediante algoritmos de
Q-learning (un agente i aprende una función acción-valor Qi(a, s) que
representa el valor realizar una acción en un determinado estado)
64
Algoritmos Evolutivos
Ejemplo 3: Aprendizaje social incremental
t ← 0
Initialize environment Et
Initialize primogenial population of agents Xt
while Stopping criteria not met do
if Agent addition schedule or criterion is not met then
Xt+1 ← ilearn(Xt,Et) /* Individual learning */
else
Create new agent anew
slearn(anew,Xt) /* Social learning */
Xt+1 ← Xt ∪ {anew}
end if
Et+1 ← update(Et) /* Update environment */
t ← t + 1
end while
65
Algoritmos Evolutivos
MUCHAS
GRACIAS