Introducción a la Sociomática
El Estudio de los Sistemas Adaptables Complejos en
el Entorno Socioeconómico.
Dr. Gonzalo Castañeda
Capítulo 14
De la biología a la computación:
Algoritmos Genéticos
14.0 Introducción
• Computación evolutiva: apela a biología para encontrar
soluciones a problemas con funciones objetivo rugosas
y espacio no bien definido
• Estrategias con buen desempeño se replican,
descendientes combinan componentes exitosos
• Ejemplos: programación evolutiva, estrategias
evolutivas, programación genética, algoritmos
genéticos
• Aplicados en distintos ámbitos: diseño de estrategias
de inversión, modelación de procesos de aprendizaje,
optimización computacional, diseño de equipos
• Ventajas: descubren comportamientos no-lineales que
escapan a mente humana: interacción de diversos
componentes
14.1. Computación evolutiva
• Analogía con el proceso de selección natural
• Soluciones resultado de aprendizaje social: agentes
aprenden a interactuar con entorno
• Proceso de búsqueda para encontrar soluciones:
estrategias de empresas innovadoras no son
convencionales
• Diseños desafían a la mente humana que tiene
preferencia a situaciones simétricas
• Procedimientos básicos: (i) evaluación paralela de
estrategias, (ii) criterio para escoger nuevas
soluciones a evaluar
* Diseño de base para antena satelital
* Aplicaciones de algoritmos evolutivos
• Usos dependen de cual sea el componente
desconocido en el sistema bajo estudio: input →
modelo interno → output.
• Si incógnita es input: problema de optimización
(e.g. problema del viajante)
• Si incógnita es el modelo: problema de
identificación (e.g. mecanismos que explican
volatilidad precios accionarios) → predicción
• Si incógnita es output: problema de emergencia
(e.g. que pasa con actividad económica si cambian
convenciones)
* ¿En que consiste algoritmo evolutivo?
• (i) Creación aleatoria de soluciones-candidato
iniciales
• (ii) Se evalúa su desempeño a través de paisajes de
adaptación
• (III) Mejores candidatos se reproducen a través de
recombinaciones y mutaciones
• (iv) Proceso iterativo hasta alcanzar límite de
eficiencia requerido o llegar a un cierto número de
generaciones
• Elementos clave: fuente de variación y filtros
* Esquema general de un algoritmo
evolutivo
* Un ejemplo: el problema de la mochila
• ¿cómo seleccionar un subconjunto de productos para
maximizar valor de la carga y mantener peso por
debajo de un límite?
• Sean N productos cuya presencia en la mochila se
describe con cadena binaria (2N)
• Función de adaptación
N
Qp 
v
i
.g i
i 1
• Restricción (algunos genotipos inválidos)
N
g
i
 C max
i 1
• Se requiere de un decodificador para eliminar ciertos
cromosomas (i.e. analizar bits izquierda derecha y
checar si carga se excede)
• Selección mediante varios torneos de parejas
• Luego se aplican operadores genéticos
14.2 Paisajes de adaptación
• Describe espacio de búsqueda y valor según
desempeño
• Paisaje: desempeño se caracteriza a través de valles,
picos y colinas
• Maximizar: proceso de escalamiento de picos
• Se explora en la vecindad de candidatos relativamente
exitosos a través de variantes
• Ejemplo: (a f h a a g k l l) y (h f h a a g k l m) son vecinos
de (a f h a a g k l m)
• Eficiencia depende de no quedar en picos locales
• Formas extremas: conos –monte Fuji- hasta muy
rugosas
• Forma rugosa con multiplicidad de óptimos locales
• En ocasiones cambios marginales producen caídas
estrepitosas o mejoras súbitas
• Algoritmo evolutivos adecuados cuando correlación entre
nivel de adaptación y cercanía de candidatos es baja
• En caminata aleatoria si se mejora se da un paso adelante si
se empeora se da paso atrás (óptimos locales)
• Salto aleatorio: se dan brincos al azar por lo que se puede
escapar de óptimos locales, pero no buenos para llegar a
adaptaciones elevadas
• A) Caminata aleatoria
• B) Brinco aleatorio
• Combinar exploración y explotación: caminata
adaptativa que ocasionalmente produce brincos
aleatorios
• Enriquecido con búsquedas paralelas
• Modelo sencillo supone que función de
adaptación es fija
• Capacidad de adaptación de un organismo al
entorno (abundancia relativa) modifica la
adaptabilidad de otros organismos
• Co-evolución entre especies: nivel de adaptación
de uno afecta al del otro
* Paisaje de adaptación en NetLogo
• Disponible en modelos de la comunidad
• Espacio de cromosomas bidimensional, orografía del paisaje =
nivel de adaptación (tono de verde)
• Entre más viejo y menos adaptado más probable que el
agente se muera: edad > número aleatorio e [ 0, nivel de
adaptación]
• Población se mantiene generando clones alrededor de una
vecindad de los sobrevivientes
• Población se dispersa, pero no aleatoria sino que se ubica en
picos (zonas claras)
• Co-existencia con grupos no tan bien adaptados
• Con el tiempo un solo color empieza a dominar (random drift)
por tener más descendencia, a pesar de que otros con mayor
adaptación
• Posibilidad de paisaje dinámico: nivel de adaptación de
manera aleatoria, pero sin cambiar rugosidad
• Paisaje rugoso:
• Paisaje suave y poco escarpado
14.3 Algoritmos Genéticos
• Desarrollado por John Holland (70’s)
• Población de soluciones (cromosomas) y función de
adaptación
• Cromosomas: cadena de símbolos (a f h a a g k l m) o
bien (1 0 0 1 1 1 0 1 1 0 1 0)
• Cada bit define acción a realizar si se presenta
determinada situación (asociada a ubicación del bit)
• Pasos: (i) se genera población inicial
• (ii) se calcula grado de adaptación
• (iii) se seleccionan cromosomas
• (iv) se toman parejas de padres exitosos para generar
variantes
* Estructura del GA estándar
• En versión estándar las poblaciones no se traslapan
• Selección de candidatos relativamente exitosos:
criterio probabilístico conocido como la rueda de la
ruleta (RW)
f
i 
i
N

j 1
f
j
• Función de adaptación estática: independiente del
número de agentes con el mismo programa
• Probabilidad debe ser no-negativa → añadir una
constante positiva para que f i ≥ 0
• Complicaciones: probabilidades tienden a igualarse
• Otras alternativas: usos de torneos, se replican sólo
los mejores; en función de ordenamiento en un
ranking
• Descendientes con variantes a partir de
operadores genéticos: recombinaciones y
mutaciones
• Recombinación en un solo punto elegido al azar
entre el primer bit y el penúltimo
• En cruzamiento uniforme todos los puntos son
elegidos al azar de un padre a partir de mascarilla
• a) De un punto
• B) Uniforme
• Exploración se fomenta mediante tasas de
mutaciones: incorpora variantes que antes no
habían sido utilizadas
• Ayuda a evitar converger rápidamente a óptimo
local
• C/bit modificado con probabilidad muy pequeña:
PM, que suele estar en el rango [10-2 , 10-3].
• Mejor desempeño cuando decrece con tiempo
* 1er ejemplo: secuencia de unos
• Objetivo: encontrar un candidato que se asemeje a
secuencia finita de números unos (1 1 1 1 1 1 1 1)
• Se inicia búsqueda con población de candidatos en donde
los bits elegidos aleatoriamente
• Función de adaptación f(x) = número de bits que presentan
el valor 1 en genes del cromosoma
• Datos: 4 candidatos, probabilidad de mutación PM = 0.001,
probabilidad de recombinación PC = 0.7.
• Punto de cruce uniforme
• Población se replica con criterio de rueda de la ruleta
• B y D cromosomas con mayor probabilidad de ser
replicados
• Si cromosomas elegidos fueron B, D, B, C. Al tomar como
padres a (B, D) y (B, C) se encuentran los cuatro
descendientes con operadores genéticos
• En primera pareja si hay recombinación y en segunda solo
mutación en uno de los padres
• Nivel de adaptación promedio subió (de 12/4 a 14/4)
* Solución al problema de ‘unos’ en NetLogo
• Model Library → Sample Models → Computer Sciences →
Simple Genetic Algorithm.
• Torneos de tamaño 3, algunos de los mejores padres
clonados, demás mediante cruzamiento en un punto
• Cuando tasa de mutación es muy elevada (10%) algoritmo
nunca converge (exploración contraproducente)
• Niveles de adaptación
Diversidad población
*2º ejemplo: el recolector de basura
• Robby busca recolectar latas en un espacio al
menor costo posible
• Retícula 10 x 10 con fronteras, latas esparcidas
aleatoriamente, corto de vista (Von neumann)
• Acciones posibles: moverse N, moverse S, moverse E, moverse O,
aleatorio, quieto y recoger
• Recoger lata = 10, no lata = -1, pared = -5
• Objetivo maximizar recogida de lata, evitando agacharse en falso y
topar pared
• Sesión de limpieza = 200 iteraciones
• Estrategias definen situaciones y como responde
• Situaciones = visión de 5 sitios (N, S, E, O, C) con tres estados (Lata,
vacio, pared) = 35 = 243
• Estrategia o cromosoma = vector con 243
situaciones que señala acciones arealizar
• Estrategia típica: (moverse-norte moverse-este
moverse-aleatorio recoger-lata…..moverseoeste…..quedarse-quieto).
• Se requiere codificar con bits o números reales,
Ejemplo: (0265….3….4).
• Población inicial de 200 estrategias, adaptación con
100 sesiones de limpieza, se siembran latas en cada
sitio con probabilidad ½
• Selección de estrategias: rueda de ruleta
• Cruzamiento genético en un punto, 1000
generaciones
• Estrategia ganadora (G) muestra adaptación = 483 < 500 = máximo
posible (10 x 50)
• M: “si existe una lata en el sitio central levántala, de no ser así
muévete al sitio de la vecindad que tiene una lata, o en su defecto
muévete aleatoriamente”
• Adaptación de M = 365 puntos
• ¿Por qué G funciona?
• En G ante situación (norte = vacío, sur = lata, este = vacío, oeste =
lata, central = lata), Robby debe moverse al oeste sin recoger la lata.
• Estudiar comportamientos observados:
• (i) movimientos en forma circular (no aleatorio) hacia este, norte,
oeste sur: rastreo de latas y evitar chocar con paredes
• (ii) No se levantan latas de un cluster hasta llegar al extremo y luego
levantar latas
• Robby aprende poco a poco: no topar, moverse donde hay latas,
dejar latas en un cluster, moverse en círculos
• Estrategia M
• Estrategia G
14.4 ¿Por qué funcionan los GA?
• Soluciones se construyen a partir de componentes (building blocks)
de padres exitosos
• Schema =cadena de bits que se describe con un templado de unos,
ceros y asteriscos (comodines)
• schema H = 1****1 , instancias (100111 y 110011)
• schema H es de orden 2 (bits definidos), y longitud es de 5 = distancia
entre los bits definidos.
• Capacidad reproductiva de H = incremento en instancias
• m(H, t) = número de instancias de H en la población, y m(H, t)
=adaptación promedio
• Número esperado de instancias en t:
E ( m ( H , t  1)) 

xe H
f ( x ) / f (t ) 
m (H ,t)
m(H ,t)
f (t )
• Si schema exitoso m(H, t) > f(t) → incrementa el número de
descendientes
• Operaciones genéticas = potencial de destruir y construir
cromosomas con templado H
• Cálculo de cota mínima de H teniendo en cuenta efectos destructivos
• pc = probabilidad de que se aplique una recombinación en un punto
de la cadena de bits
• Cota inferior para la probabilidad Sc(H) de que H sobreviva después
de una recombinación:
d (H )


Sc (H )  1  pc 

L

1


• d(h) es la distancia, L = longitud de la cadena
• D(H)/(L-1) = fracción de descendientes que tienen la misma distancia
de las instancias de H.
• Pc D(H)/(L-1) = cota superior que se destruyan instancias (por azar
algunos descendientes pueden tener el templado)
• Supervivencia es más factible en schemas relativamente cortos con
respecto a la dimensión del espacio de búsqueda
• Cálculo del efecto destructivo de la mutación
• Instancia de H sobrevive ante cambios aleatorios en cualquiera de los
bits de un cromosoma con probabilidad Sm(H) = (1-pm)o(H)
• o(H) es el orden (bits definidos) de H y pm = probabilidad de que un
bit sea mutado.
• Cota inferior para número de descendientes que son una instancia de
H en la población:
m (H ,t)
d (H ) 

o(H )
E ( m ( H , t  1)) 
m ( H , t ) 1  p c
 1  p m 
f (t )

L 1 
• ‘Teorema del Schema’ :describe las características que debe tener un
schema para que éste sea exitoso
• Relativamente cortos, de bajo orden y cuyo nivel de adaptación
promedio se mantiene por encima de la media poblacional
• Poder de GA en habilidad para recombinar instancias de buenos
schemas y así construir instancias de schemas de orden mayor que
son al menos tan buenos como sus padres.
• Rol positivo de las mutaciones reside en evitar que se pierda la
diversidad en la población. (schemas con unos en primer bit)
14.5 Diseño de CA con GA
• Aplicación: ¿resolver problemas de acción colectiva cuando
las unidades tienen información limitada que proviene de
su ámbito local?
• Hormigas que interactúan sólo con vecino pero que logran
crear colonia sofisticadas
• Ejemplo: elegir un estado consistente con el sentir
mayoritario a pesar de tener información local
• ¿Quién ganará una elección?
• ´Identificar a la mayoría’ problema complejo cuando sólo se
tiene información de vecinos
• Regla de un CA: voto mayoritario → célula central de una
vecindad elige on (off) cuando el estado de la mayoría de
sus vecinos es on (off), aleatorio con empate.
• Dinámica en una retícula unidimensional periódica
con dos vecinos
• Voto mayoritario no predice sentir mayoritario
(negro o blanco)
• Con un GA se usa cromosomas con 128 bits (27), CA con
vecindades de tamaño 7
• Situación descrita por (0 0 0 0 0 0 0) → bit en la posición
uno se puede identificar con 0 ó 1
• Función de adaptación = fracción de corridas en que regla
produce configuración final correcta: todas las células
toman el valor 1 (on) ó 0 (off) cuando dicho valor constituía
el sentir mayoritario en el sembrado inicial.
• ¿Cuál es razón de éxito de estrategia ganadora? ¿Cómo se
comunican las células?
• En los diagramas espacio-tiempo se muestran tres tipos de
bloques: células negras, blancas e intercaladas
• La naturaleza de los bordes sirve para comunicar
información (líneas verticales, horizontales) ¿qué bordes
desaparecen más rápido?
* Sentir mayoritario con información local
• Mayoría negra
Mayoría blanca
14.6 Aplicación económica de GA
• Atractivo para modelar procesos económicos:
• (i) estrategias de agentes heterogéneos que compiten de
forma paralela
• (ii) Estrategias exitosas se imitan
• (iii) Constantemente surge innovación
• Agentes adaptativos toman decisiones (producción, salirse)
en mercado de telaraña
• Operadores genéticos (i) selección proporcional, (ii)
cruzamiento en un punto, (iii) mutación
• Símil económico (i) en entorno de incertidumbre lo
conveniente es imitar, (ii) se copian componentes de planes
de negocio exitosos, (iii) accidentes o innovación
* Mercado de telaraña con expectativas
racionales
• Demanda depende del precio observado y oferta es función del
precio anticipado
• Competencia con n empresas y costos fijos
e
2
• C/periodo maximizan beneficios  P e , y    p i ,t y i ,t     y i ,t y i ,t
i ,t
• Cantidad óptima:
e
y * ( p i ,t
e

p i ,t

 2

 
)   0,

 

 0


i ,t
p i ,t  2
e
p i ,t  2
e
p i ,t  2
e

0
0
y i ,t  0



n
p t  a  b  y i ,t
• Precio de equilibrio:
• Existe un único equilibrio de RE sólo cuando
• Precios y cantidades de equilibrio: y *  y * ( p t ) 
i 1
a
2  
,
p* 
2
(2    )
2
* Precios de equilibrio con agentes adaptativos
• Expectativas distintas → niveles óptimos diferentes
• Se representan con cadena binaria que codifica un número
real:
ax
10
y (k ) 

,
con
x
 2 k (i )
i
i 1
• Para evitar que el valor de la función de adaptación sea
negativa para una cadena binaria se escala:
a
f k ( )   ( p ( ), y ( k ))      
 
2
• Notar: valor no sólo depende de la cadena de bits
correspondiente sino también del estado de la población,
• Simulación inicial: : a = 5,  = 0.25,  = 1,  = 5
• Producción promedio converge rápido a RE: y* = y*(p*) =
5/7
• Si costos fijos se eleva  = 1 el equilibrio en expectativas
racionales deja de existir.
• GA comportamiento similar pero empresas con beneficios
negativos por altos costos → replantear modelo
• Costos bajos
* ¿Participar o salirse del mercado?
• 1ª etapa: empresas deciden si participar
• 2ª etapa: empresas deciden niveles de producción
• Un nuevo bit a la cadena para identificar si la empresa opta o no por
entrar al mercado
• Sólo si entra ejerce costos fijos
• No se converge a y= 5/7, sino que se fluctúa alrededor de 0.6 (debido
a que un porcentaje salen del mercado y otros producen mucho
• El GA encuentre equilibrio con RA (misma expectativa), peros unos
optan por salirse
* El problema del viajante
• Distancia más corta entre una ciudad de origen (c0) y otra
de destino (cN+1) haciendo un recorrido de ciudades
intermedias sin repetir. (optimización)
• N! recorridos diferentes, si N = 12 → 479,001,600
• Con GA estándar el recorrido de un hijo puede presentar
dos ciudades repetidas
• Si orden no es importante: “A, B, C, D, E, F” es equivalente a
“F, E, D, C, B, A” → N!/2 recorridos
• NetLogo:
14.7 Estrategias mercadológicas en
redes sociales
• Publicidad boca-en-boca más relevante que
tradicional
• Problema: identificar sembrado de productos y
presupuestos a utilizar
• Para red arbitraria en un problema
computacionalmente complicado (NP-hard)
• Redes de internet han disminuido tiempos de
difusión de productos
• Estructura global de la red desconocida
• Solución Problema de mercadotecnia viral local
* Planteamiento del LVMP
• Encontrar una función de ponderación w(i) que determina
la prioridad de c/nodo para sembrar productos
• Hasta que presupuesto (b) se agote, elegido óptimamente
• Función de adaptación:

VPN ( G , S , f ( t )) 
 a ( t )
t
t0
• Ritmo de adopción (variante de Bass) depende de
influencias externas (p) e internas (q):
 n a (t ) 
f (t )  p  q

 n 
* Espacio de interacción y estrategias
• Configuraciones : aleatoria, retícula, mundo
pequeño, vínculos preferenciales y red empírica
(subconjunto conectado de la red de Twitter )
• Estrategias posibles: presupuesto (b), fracción de
nodos de la red que deben ser sembrados (fs) y la
función de ponderación (w(i)).
• No se contempla costo de regalar producto
• Métricas para caracterizar nodos: (1) wd(i)=degree
(i)/ max (degree); (2) wt(i) = twostep(i)/max
(twosteps); (3) wa(i) = [max (apl) – apl (i)]/ max
(apl);(4) wc(i)= [1 – cc(i)]/max (cc); (5) wr(i) = U[0, 1].
• Función de ponderación:
w comb ( i )   d w d ( i )   t w t ( i )   a w a ( i )   c w c ( i )   r w r ( i )
• O bien con estrategia mixta:
 w comb ,1 ( i )
w (i )  
 w comb , 2 ( i )
si x  d
en los demás casos
• Estrategia individual =10 parámetros , un valor d >
0.5 y la fracción fs de nodos sembrados →
cromosomas con 12 genes codificados de manera
binaria
• Se requiere un subconjunto conectado de red
empírica para las métricas
* Simulaciones y resultados
• (i) Con 1000 agentes, 50 estrategias iníciales → se ordenan nodos
según prioridades
• (ii) Fracción fs de nodos que permite presupuesto
• (iii) En c/iteración se registra número de adopciones
• (iv) termina cuando todos nodos tienen producto
• (v) Se calcula VPN promedio con 10 replicaciones
• Aquí se utiliza GA : tasa de mutación del 1%, selección de padres a
partir de torneos de tamaño tres, cruzamiento genético en un punto
con probabilidad del 70%, total de 200 generaciones.
• Búsqueda de parámetros con 30 condiciones iníciales
• Dos escenario: viral alto y medio
• 30 millones de corridas = 2 escenarios x 5 redes x 30 búsquedas x 50
estrategias x 200 generaciones x 10 repeticiones, lo que
indudablemente consume un tiempo de cómputo sumamente
elevado (11,000 horas).
• VPN más elevados para redes con una distribución
de grado más sesgada (Twitter y vínculos
preferenciales).
• Calculo con valores promedio y mejor ajuste
• Presupuesto más reducido se obtiene en redes con
un alto grado de asimetría
• Red de pocos nodos con una gran cantidad de
vínculos → presupuesto asignado será
relativamente pequeño.
• Grado del nodo wd(i) es un factor importante en la
función de ponderación de las cinco redes
• En red de Twitter el GA la combinación de un alto
grado (d) con un bajo valor aglutinamiento, (c) es
el criterio relevante
• Muchos de los nodos muy vinculados en Twitter
están asociados entre →preferible elegir nodos que
sirvan de enlace con muchas partes de la red pero
no vinculados con estos hubs.
• Sembrado en nodos que poseen un grado elevado y
a la vez forman parte de un entorno de baja
aglutinación
• Estrategia mixta no ofrece beneficios
* Ubicación de nodos prioritarios
• Grado
Aglutinamiento
GA
* Calibración indirecta mediante GA
• Behavior Search con interfaz con Netlogo permite usar
varias heurísticas
• El espacio de parámetros: continuo, discreto, binario,
booleano o una combinación de estos
• GA estándar, búsqueda aleatoria (R) y rutina de
escalamiento con mutación (HC).
• a priori no es posible saber si el método de GA es superior
al de HC
• GA permite exploración paralela, adecuado cuando bloques
de cadena son importantes
• Ejemplo con Flocking (vuelo parvada)
• función de adaptación:agentes ‘vuelen’ en una misma
dirección
• Promedio de funciones de adaptación
• No todos los parámetros inciden de la misma
forma
Descargar

power point