IA17 - T4 CL2 AGeneticos 2

Vista previa del material en texto

1 
ALGORITMOS GENÉTICOS II 
C
on
te
ni
do
 • Concepto. 
• Ejemplo 1 – Maximización de 
 función. 
• Ejemplo 2 - Optimización. 
• Aplicaciones en MatLab. 
[García Martínez et al.] Sistemas Inteligentes. 
Cap. 3 – Algoritmos genéticos. 2003. 
[RELLO R. M.] Algoritmos genéticos. Introducción métodos 
de búsqueda y optimización. 
[MathWorks] Global Optimization Toolbox User’s Guide. 
2010. 
[García G., 2010] Introducción a la Resolución de 
Problemas con AG. 
R
ef
er
en
ci
as
 
2 
T4-2 ALGORITMOS GENÉTICOS 
 CONCEPTO / DEFINICIÓN 
Los Algoritmos Genéticos (AG’s) son 
métodos matemáticos adaptivos que 
aplican estrategias de búsqueda 
estocástica en un espacio de 
soluciones potenciales del 
problema, basándose en 
modelos de la evolución natural 
de organismos vivos. 
3 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 1 
Determinar el valor que maximiza la función 
f(x) = x2 en el intervalo natural [0 , 31]. 
Para el intervalo dado, un individuo debe tener como 
mínimo 5 bits, para poder representar todos los valores 
del intervalo. 
Esquema → [* * * * *] 
Individuo ejemplo → [1 0 1 1 0] → representa al 20. 
 
Como función de adaptación se utiliza la misma función 
a evaluar. 
 
La población inicial P0, dada las características del 
problema, no requiere de gran cantidad de individuos. 
Se definen cuatro en este caso, creados al azar. 
P0 = [01101] , [11000] , [01000] , [10011] 
4 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 1 
Se determina la probabilidad de selección 
de los individuos, con algún criterio, 
por ejemplo la probabilidad proporcional 
a la adaptación 
Para I1 = [01101] = 1310 → f(I1) = (I1)2 = 16910 
Σ(f(Ii) = 1170 
 → p(I1) = 169/1170 = 0,144 = 14,4% 
 → p(I2) = 576/1170 = 0,492 = 49,2% 
 → p(I3) = 64/1170 = 0,055 = 5,5% 
 → p(I4) = 361/1170 = 0,309 = 30,9% 
j
j n
j
1
(I )
p
(I )
=
∑
f
f
Determinar el valor que maximiza la función f(x) = x2 en el intervalo natural 
[0 , 31] (continuación) 
5 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 1 
Determinar el valor que maximiza la función f(x) = x2 en el intervalo natural 
[0 , 31] (continuación) 
# Población inicial P(0) x 
f(x) 
(fn. ajuste) f(x)/Σf(x) 
Probabilidad 
selecc. acum 
1 01101 13 169 0,14 0,14 
2 11000 24 576 0,49 0,63 
3 01000 8 64 0,06 0,69 
4 10011 19 361 0,31 1,00 
Suma .................................................... 1170 
Media ................................................... 293 
Mejor .................................................... 576 
 
Se seleccionan aleatoriamente los individuos para 
reproducción en base a su adaptación acumulada 
 Probabilidad de selección (uniforme) 
 [r1 r2 r3 r4] = [0.58 0.84 0.11 0.43] 
 En la ruleta → 4 tiros 
6 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 1 
Por aproximación con las probabilidades de adaptación 
(acumulada) de los individuos en P0, y con los 4 tiros de 
ruleta, se determinan los candidatos a reproducción: 
Si …………… PAAC(Ij-1) < ri < PAAC (Ij) ….. se elije → Ij 
 PAAC(I1)=0,14 < r1=0,58 < PAAC(I2)=0,63 …..…. elige a I2 
PAAC(I3)=0,69 < r2=0,84 < PAAC(I4)=1,00 ………. elige a I4 
 PAAC=0 < r3=0,11 < PAAC(I1)=0,14 ………. elige a I1 
PAAC(I1)=0,14 < r4=0,43 < PAAC(I2)=0,63 ………. elige a I2 
 Se puede renombrar → I2 = I’1 I4 = I’2 I1 = I’3 I2 = I’4 
Determinar el valor que maximiza la función f(x) = x2 en el intervalo natural 
[0 , 31] (continuación) 
7 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 1 
Se obtiene: 
 
Población inicial 
P0 = { [01101] , [11000] , [01000] , [10011] } 
Candidatos seleccionados para reproducción 
C = {I’1 (I2 de P0) ; I’2 (I4 de P0) ; 
 I’3 (I1 de P0) ; I’4 (I2 de P0) } 
 
C = { [11000] , [10011] , [01101] , [11000] } 
 
Determinar el valor que maximiza la función f(x) = x2 en el intervalo natural 
[0 , 31] (continuación) 
8 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 1 
Determinar el valor que maximiza la función f(x) = x2 en el intervalo natural 
[0 , 31] (continuación) 
Para el proceso de reproducción se establece la 
probabilidad de reproducción (ej. 80%), se asignan 
nuevos nros. aleatorios a los individuos candidatos y 
se eligen las parejas que tengan valores aleatorios 
menores o iguales a 0,8 (puede ser en orden) 
 Probabilidad de 
 cruza [R1 R2 R3 R4] = [0.63 0.25 0.07 0.13] 
Primera pareja 
 {I’1(0,63) con I’2(0,25)} → { [11000] , [10011] } 
Segunda pareja 
 {I’3(0,07) con I’4(0,13)} → { [01101] , [11000] } 
Si no quedan todos emparejados se puede eliminar el 
último. 
9 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 1 
Determinar el valor que maximiza la función f(x) = x2 en el intervalo natural 
[0 , 31] (continuación) 
Para aplicar el 
operador de cruza 
se determina 
aleatoriamente 
 el punto 
de cruce 
 (entre 1 y la 
longitud del 
individuo – 1) 
para cada pareja 
(por ej. 2 y 3). 
10 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 1 
Determinar el valor que maximiza la función f(x) = x2 en el intervalo natural 
[0 , 31] (continuación) 
Seguidamente se aplica el operador de mutación que 
tiene probabilidad muy baja (menor que el 1%). En este 
caso se elige PRm=0,01. Se genera un número aleatorio 
entre [0 , 1] para cada bit de cada individuo. Si el valor 
asignado es menor o igual que PRm, el bit se invierte. 
P0-1 = { [11000] [10011] [01101] [11000] 
 [11011] [10000] [01100] [11001] } 
Mutación 
⇒ cambia 
a 1 
La población intermedia ha quedado con 8 individuos. 
Se debe redimensionar a la cantidad original (4). Se 
pueden eliminar los padres originales; se pueden elegir 
desde el ranquin de adaptación acumulada; se pueden 
seleccionar a azar. 
11 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 1 
Determinar el valor que maximiza la función f(x) = x2 en el intervalo natural 
[0 , 31] (continuación) 
Apareado Punto de cruce Hijos 
Hijos 
mutados x f(x) 
11000 2 11011 11011 27 729 
10011 2 10000 10000 16 256 
01101 3 01100 11100 28 784 
11000 3 11001 11101 29 841 
Suma .................................................................................................................. 2610 
Media ................................................................................................................. 652 
Mejor .................................................................................................................. 841 
 
Comparación de resultados para un paso de iteración: 
# Población inicial P(0) x 
f(x) 
(fn. ajuste) f(x)/Σf(x) 
Probabilidad 
selecc. acum 
1 01101 13 169 0,14 0,14 
2 11000 24 576 0,49 0,63 
3 01000 8 64 0,06 0,69 
4 10011 19 361 0,31 1,00 
Suma .................................................... 1170 
Media ................................................... 293 
Mejor .................................................... 576 
 
12 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 2 
Problema del viajante: Una persona debe recorrer 
varias ciudades distintas, con la condición de pasar 
solamente una vez por cada una y volver a la ciudad de 
origen, recorriendo la menor distancia posible. 
Extraído de RELLO R. M. “Algoritmos genéticos. Introducción 
métodos de búsqueda y optimización”. Dpto. Electrónica I+D, 
Orbis Tecnología Eléctrica. 
13 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 2 
Problema del viajante → DESCRIPCIÓN 
El viajante parte inicialmente de la ciudad A y puede ir 
hacia cualquiera de las restantes ciudades. En la figura 
se muestran todas las posibles combinaciones que 
puede realizar el viajante. 
Como puede 
verse, las 
soluciones 
óptimas son la 
1ª y la 2ª pues 
en ambas se 
recorren todas 
las ciudades 
una vez con la 
menor 
distancia. 
14 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 2 
Problema del viajante → CODIFICACIÓN 
Para la formulación de los individuos se ha optado por 
codificar la existencia de tramos recorridos. Los tramos 
posibles son 6: AB, BC, CD, DA, AC y BD, los individuos 
pueden representarse como cadenas binarias de 6 bits.Si bi = 1 ⇒ tramo se recorre 
Si bi = 0 ⇒ tramo no se recorre 
wi = [b5 b4 b3 b2 b1 b0] = [AB BC CD DA AC BD] 
wi = [1 1 1 1 0 0] 
wi = [1 0 1 0 1 1] 
Dist=4 Dist=4 
15 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 2 
Problema del viajante → CODIFICACIÓN 
Se pueden generar representaciones incorrectas: 
wi = [1 1 1 0 0 0] 
No vuelve al origen 
wi = [1 1 1 1 1 0] 
Pasa 2 veces por la misma ciudad 
wi = [b5 b4 b3 b2 b1 b0] = [AB BC CD DA AC BD] 
Estos individuos deberían tener menos posibilidades 
de evolucionar a siguientes generaciones. 
16 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 2 
Problema del viajante → EVALUACIÓN 
Requerimientos de la 1º función de evaluación: 
• El número de tramos recorridos debe ser igual a 4. 
 Requiere que se maximice la ecuación: 
donde C es el número de ciudades, L es la longitud de 
la cadena de bits y bi es el bit i-ésimo de la cadena de 
bits. De esta forma los individuos que recorran sólo 
cuatro tramos obtendrán el valor máximo de la 
función de evaluación, es decir: 
 
Fitness1(wi)1 = 1 
∑
L-1
i
i=0
i
C ― b
Fitness1(w )=1 ― 
C
17 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 2 
Problema del viajante → EVALUACIÓN 
 Requerimiento de la 2º función de evaluación: 
• La distancia recorrida debe ser mínima. En este 
 caso la ecuación a minimizar es: 
donde L es la longitud de la cadena de bits y bi es el 
bit i-ésimo de la cadena de bits, Ti es la distancia del 
tramo i. Para i = 5, T5 es la distancia del tramo AB y 
para i = 0, T0 es la distancia del tramo BD. 
∑
∑
L-1
i i
i=0
L-1
i
i=0
b .T
Fitness2(w)= 
b
18 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 2 
Problema del viajante → EVALUACIÓN 
La aptitud depende 10 veces más de la primera 
condición que de la segunda; esto es así porque es 
indispensable que se recorran sólo 4 tramos, mientras 
que la segunda condición da idea de qué individuo es el 
mejor dentro de los seleccionados como válidos con la 
primera opción. 
Para satisfacer ambas condiciones, se configura una 
función combinada que represente la aptitud de cada 
individuo: 
Fitness(wi) = Fitness1(wi) – 0,1*Fitness2(wi) 
CONDICIÓN DE PARADA: se ha supuesto que un 
individuo es la solución óptima si durante cinco 
generaciones su aptitud es la mayor de la población 
y además no cambia. 
19 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 2 
Problema del viajante → POBLACIÓN INICIAL 
• 6 individuos iniciales elegidos de forma aleatoria. 
• La probabilidad de cruce PRcruce es del 40%. 
• La probabilidad de mutación PRmut es del 1%. 
• La selección de los individuos se realiza por selección 
 estocástica (dependiente de la aptitud relativa). 
• Cruce monopunto. 
FitTOT = 4,8638 
20 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 2 
Problema del viajante → EVOLUCIÓN 
21 
T4-2 ALGORITMOS GENÉTICOS 
 EJEMPLO 2 
Problema del viajante → CONCLUSIÓN 
Se llega a la conclusión de que la 5º 
generación es más apta que la anterior 
puesto que el valor de FitTOT actual 
(5,5936) es mayor que el inicial (4,8638). 
Si se deja evolucionar esta población 
durante 15 ciclos más, se llega a la 
condición de parada ya que el individuo 
w3 tiene una cadena (111100) 
constante durante 5 ciclos seguidos. 
22 
T4-2 ALGORITMOS GENÉTICOS 
 APLICACIONES EN MATLAB 
 Desde la línea de comando: 
>> [x fval] = ga(@fitnessfun, nvars, options) 
donde 
• @fitnessfun: función de ajuste. 
• nvars: número de variables independientes de la 
función de ajuste. 
• options: estructura que contiene las opciones 
operativas del algoritmo. Si no se especifica usa 
las opciones por defecto. 
Produce los siguientes resultados 
• x: Punto correspondiente al valor final. 
• fval: Valor final de la función objetivo. 
Ref. [MathWorks] Global Optimization Toolbox User’s Guide. 2010. 
23 
T4-2 ALGORITMOS GENÉTICOS 
 APLICACIONES EN MATLAB 
 Variantes desde la línea de comando: 
[x,fval] = ga(fitnessfcn,nvars) 
[x,fval] = ga(fitnessfcn,nvars,A,b) 
[x,fval] = ga(fitnessfcn,nvars,A,b,Aeq,beq) 
[x,fval] = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB) 
Fitnessfcn = función de ajuste. 
 nvars = número de variables. 
 A , b = parámetros de desigualdad lineal ⇒ A*x ≤ b 
 Aeq , beq = parámetros de igualdad lineal ⇒ Aeq*x = beq 
 LB = límite inferior ⇒ x ≥ LB 
 UB = límite superior ⇒ x ≤ LB 
 x = valor de la variable en el mínimo. 
 fval = valor de la función en el mínimo. 
24 
T4-2 ALGORITMOS GENÉTICOS 
 APLICACIONES EN MATLAB 
 Ejemplo desde la línea de comando. Encontrar el 
mínimo: 
mínimo local 
f(0)= –1 
mínimo global 
f(21)= –1.37 
 >> [x,fval]=ga(@two_min,1) 
 Optimization terminated: average change in the fitness value 
less than options.TolFun. 
 x = 0.0028 
 fval = -1.0000 (Parámetros por defecto) 
 No encuentra mínimo global porque no hay 
suficiente diversidad de individuos → x ∈ [0,1] 
function two_min.m 
25 
T4-2 ALGORITMOS GENÉTICOS 
 APLICACIONES EN MATLAB 
 Ejemplo desde la línea de comando. Encontrar el 
mínimo: 
mínimo local 
f(0)= –1 
mínimo global 
f(21)= –1.37 
 >> [x,fval] = ga(@two_min,1,[ ],[ ],[ ],[ ],5,30) 
 Optimization terminated: average change in the fitness value 
less than options.TolFun. 
 x = 21.0000 
 fval = -1.3679 
 Reconfigurando los límites encuentra el mínimo 
global → x ∈ [5,30] 
function two_min.m 
26 
T4-2 ALGORITMOS GENÉTICOS 
 APLICACIONES EN MATLAB 
 Con la interfaz optimtool(‘ga’) 
Elegir solver 
ga 
Restricciones 
Ejecución 
Resultados 
fitness(x) 
Punto x 
Columna 
de 
opciones 
y gráficas 
Ayuda 
	ALGORITMOS GENÉTICOS II
	T4-2 ALGORITMOS GENÉTICOS�	CONCEPTO / DEFINICIÓN
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 1
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 1
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 1
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 1
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 1
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 1
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 1
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 1
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 1
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 2
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 2
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 2
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 2
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 2
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 2
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 2
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 2
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 2
	T4-2 ALGORITMOS GENÉTICOS�	EJEMPLO 2
	T4-2 ALGORITMOS GENÉTICOS�	APLICACIONES EN MATLAB
	T4-2 ALGORITMOS GENÉTICOS�	APLICACIONES EN MATLAB
	T4-2 ALGORITMOS GENÉTICOS�	APLICACIONES EN MATLAB
	T4-2 ALGORITMOS GENÉTICOS�	APLICACIONES EN MATLAB
	T4-2 ALGORITMOS GENÉTICOS�	APLICACIONES EN MATLAB