María Teresa Iglesias Otero
Departamento de MatemáticasUniversidade da Coruña
Matemáticas Evolutivas: Algoritmos Genéticos
¿Cuál es la mejor forma de ...?
¿cuál es el camino más corto a ...?
¿cuál es la más barata entre ...?
Problemas de Optimización
Encontrar la mejor entre un conjunto de opciones (en un espacio de búsqueda)
¿cómo medir la idea de mejor?
D: Conjunto de posibles soluciones (finito/infinito) números, vectores, grafos, ...
Problemas de Optimización
Encontrar el elemento de D en el que f (≥0) es
máxima
f: D R
f: función objetivo (de coste)
¿Cómo proceder para encontrar el máximo?
Métodos tradicionales
f’ = 0 f’’< 0
{∂f/∂x = 0, ∂f/∂y = 0,...}
f(x)=x²+exp(cos(x))-x, f’(x)=2x-sen(x)exp(cos(x))+1=0
¿Cómo proceder para encontrar el máximo?
Métodos “Alternativos”
Método del alpinista (Hill-climbing)
¿Cómo proceder para encontrar el máximo?
Métodos “Alternativos”
Búsqueda aleatoria Búsqueda exhaustiva: Travelling Salesman Problem (TSP)
Átomos del universo ≈10⁷⁸
N=100→99!≈101⁵⁶
N=5 →4!
a • • •c db• • e
a
be
dc
Definición (Koza, 1993)
El AG es un algoritmo matemático altamente paralelo que transforma un conjunto (población) de objetos matemáticos individuales, cada uno de los cuales se asocia con una aptitud, en una población nueva (la siguiente generación) -usando operaciones modeladas de acuerdo con el principio Darwiniano de reproducción y supervivencia del más apto- y tras haberse utilizado de forma natural una serie de operaciones genéticas (sobre todo la recombinación sexual)
Algoritmos Genéticos
Se inspiran en la teoría de la evolución de Darwin y en las ideas de Mendel
1. Generar aleatoriamente una población de posibles soluciones de un problema, representadas por una estructura de datos adecuada
2. Evaluar cada uno de los individuos de la población, asignándoles una puntuación
3. Escoger de la población aquella parte que tenga una mejor puntuación
4. Mutar (cambiar) y cruzar (combinar) las diferentes soluciones de la parte elegida para reconstruir la población
5. Repetir hasta que se encuentre la solución deseada
Esquema general de un Algoritmo Genético
Población no estática (P ≡ P(t)) Tamaño de la población es fijo (|P|=N)
Se permiten individuos repetidos
f: P R
¿Cómo se modela el fenómeno de la evolución?
f: función de idoneidad
Algoritmos Genéticos
Individuos (cromosomas): datos codificados (cadenas binarias)
f: P ⊂ {0,1}l R
s = 11010(2 = 1·24+1·23+0·22+1·21+0·20(10
Individuos: datos codificados (cadenas binarias)
f: P = {0,1}l R
Ejemplo: s = 11010 ∈ {0,1}⁵
s = 11010(2 = 1·24+1·23+0·22+1·21+0·20(10
0 1 2 3 ... 28 29 30 31
00000 00001 00010 00011 ... 11100 11101 11110 11111
gen
s∈P, s = sl-1sl-2...si...s1s0
alelos
si ∈ {0,1}
Representación del Problema del Viajante
a ➟ c ➟ e ➟ b ➟ d s = acebd
a • • •c db• • e
a
cb
e
d
1 ➟ 3 ➟ 5 ➟ 2 ➟ 4 s = 13524
1. Generar aleatoriamente una población de posibles soluciones de un problema, representadas por una estructura de datos adecuada
2. Evaluar cada uno de los individuos de la población, asignándoles una puntuación
3. Escoger de la población aquella parte que tenga una mejor puntuación
4. Mutar (cambiar) y cruzar (combinar) las diferentes soluciones de la parte elegida para reconstruir la población
5. Repetir hasta que se encuentre la solución deseada
Esquema general de un Algoritmo Genético
Algoritmos Genéticos
w
t
r
s
selección mediante ruleta
prob(s) = f(s)/∑r∈Pf(r)s=0101110
AG: Selección mediante torneo
se baraja la población
se escogen n individuos (normalmente 2)
compiten entre sí: gana el más apto
debe barajarse n(=2) veces para seleccionar N padres
cadena calidad barajar ganador barajar ganador
s1 254 s2s4
s3
s4s1
s3
s1s2 47 s4s3 456 s1 s2s4 195 s3 s3
N=4
s4 y s1
s3 y s3
Operadores genéticos
p1=♣♣♣♣♣♣p2=♤♤♤♤♤♤
h1=♣♣♣♣♤♤h2=♤♤♤♤♣♣
✂
cruce
mutaciónd1=♣♣♣♣♤♤d2=♦♤♤♤♣♣
abcdbacede
¿mutación? abcde ab_de
s = 000|00t = 111|11Cruce: s’ = 00011
t’ = 11100
abc|deace|db¿cruce?
Problema del viajante
Un cruce para el TSP
p1 = 123|4567|89p2 = 452|1876|93
h1 = ###|1876|##h2 = ###|4567|##
h1 = #23|1876|#9h2 = ##2|4567|93
h1 = 423|1876|#9h2 = ##2|4567|93
5
1 8¿mutación?
h2 = 182|4567|93 h’2 = 182|4567|39
Algoritmos Genéticos
begin t←0 iniciar P(t) evaluar P(t) while (condición de parada) do t←t+1 seleccionar P(t-1)’ de P(t-1) aplicar cruce a P(t-1)’ aplicar mutación a P(t-1)’ P(t)←P(t-1)’ endend
Algoritmos Genéticos
f: D = {0, 1}⁵ R s s²
P(0) f01011000010011111110101011010000100111001101010011
12114990044140016784676361
(1/10)∑f(s) = 375
11111(2=31(10 961 máximo
Algoritmos Genéticos
P’(0) P(1) f11110101011110000111100111111011100110100101111110
11101101101111100100101101101111110110010111011011
84148496116484761900625296761
(1/10)∑f(s)=613
f(11111(2)=f(31)=961 ¡¡máximo!!
Algoritmos Genéticos
Poblaciones máximo poblacional
multiplicidad media poblacional
P(0)P(1)P(2)P(3)P(4)
900961
11
375613
Algoritmos GenéticosP(1) P’(1) P(2) f
11101101101111100100101101101111110110010111011011
111|11110|111110|11111|0111|11101|101|10011|10111110|11111|0
11111110111110011111111101011111011111011110011111
961761784961900529761841784961
(1/10)∑f(s)=814
Algoritmos Genéticos
Poblaciones máximo poblacional
multiplicidad media poblacional
P(0)P(1)P(2)P(3)P(4)
900961961
113
375613814
Algoritmos Genéticos
Poblaciones máximo poblacional
multiplicidad media poblacional
P(0)P(1)P(2)P(3)P(4)
900961961961961
11346
375613814840872
1#### es mejor que 0####
P(0) f01011000010011111110101011010000100111001101010011
12114990044140016784676361
Biología: Individuos que presentan semejanzas están emparentados
f(1####)6
∑
¿Por qué funcionan estos algoritmos?
=375593.66= ≥ ∑ f(s)10
¿Por qué funcionan estos algoritmos?
Esquema: Conjunto de cromosomas que siguen un patrón
H = 01##1 ↔ {01001, 01011, 01101, 01111}
|H| = 2l-o(H) = 25-3 = 4
o(H) = 3
☟
☟
δ(H) = 4
Efecto del cruce sobre los esquemas
δ(01##1)=4
0|1##10____
_1##1
01#|#101#__
___#1
δ(1####)=0
1|####1####
_####
δ(H)<< ➮ prob(destrucción) <<
Efecto de la mutación sobre los esquemas
H = 01##1
11##100##101##0
pdestruc(01##1) > pdestruc(1####)
o(H)<< ➮ prob(destrucción) <<
1#### 0####
o(H)=3 o(1####)=1
1#### es mejor que 0####P(0) f01011000010011111110101011010000100111001101010011
12114990044140016784676361
f(1####)6
∑ f(s)10
≥ ∑
¿Por qué funcionan estos Algoritmos?
(=375)
900+441+400+784+676+3616
=593.66
593.66=
¿Por qué funcionan estos Algoritmos?
valor medio de H∩P(t)
valor medio de P(t)
∑q∈H∩P(t)f(q)
n(H,t)☛ f(H,t) =
H buen esquema ⇔
f(P,t) = ∑r∈P(t)f(r)N☛
f(H,t) f(P,t) > 1
Teorema de los esquemas (Holland 1975)
¿Por qué funcionan estos Algoritmos?
α(H,t) = 1- probmut·o(H) - probcruce·δ(H)/(l-1)
n(H,t+1) ≥ n(H,t)· f(H,t)f(P,t)·α(H,t)
Los buenas estructuras presentes en la población incrementan el nº de representantes generación a generación
Algunas aplicaciones
Problema del viajante (NP completo ”NP hard problem”)
Ingeniería aeroespacial: diseño de la forma del ala de un avión supersónico
RoboCup: proyecto internacional para promocionar la robótica, la inteligencia artificial y campos relacionados. (Torneo internacional de fútbol cuyo reto es desarrollar un equipo de robots humanoides autónomos que ganen a los humanos en 2050!) www.robocup.org
Ingeniería de sistemas: diseños de turbinas de molinos de parques eólicos
http://the-geek.org/docs/algen/
Adam Marczyk: Algoritmos genéticos y computación evolutiva (2004)
Algunas aplicaciones
Diseño de una sala de conciertos con propiedades acústicas óptimas, (2002) similar al Grosser Musikvereinsaal de Viena
Reconocimiento de imágenes: Resonancia Magnética
Radioterapia: Optimización de la forma, orientación e intensidad del haz de los emisores de rayos X
Localización de puestos de urgencias
John Deere & Co.: generar programas de montaje en la planta de Moline (Illinois) para la fabricación de maquinaria agrícola pesada
Volvo: OptiFlex para el diseño del montaje de la planta de Dublín (Virginia) de un millón de metros cuadrados
United Distillers and Vintners: para administrar su inventario y sus suministros
Algunas aplicaciones: Elaboración de horarios (NP completo)
Un conjunto de profesores {P1, ..., Pm}Un conjunto de clases {C1, ..., Ck}
Un conjunto de intervalos de tiempo (horas) {H1, ...,Hn}
Restricciones:R. severas
Número predefinido de horas por profesorun sólo profesor por claseun profesor no puede estar en dos clases
R. débiles
Preferencias personales
- Juegos Paralímpicos de 1992 - Aterrizajes en London Heathrow, Toronto, Sydney, Las Vegas, ... - Horarios de centros de enseñanza
Mafalda:
“La vida es linda, pero nadie confunda linda con fácil”
Oscar Wilde:
“La verdad rara vez es pura, y nunca simple”