IA17 - T4 CL1 AGeneticos 1

Vista previa del material en texto

1 
ALGORITMOS GENÉTICOS I 
C
on
te
ni
do
 
• Concepto. 
• Introducción y 
propiedades. 
• Contexto general. 
• Esquema conceptual. 
• Esquema operativo. 
• Función de adaptación. 
• Operadores genéticos. 
• Algoritmo genético 
canónico. 
• Esquemas. 
• Bibliografía. 
B
ibliografía 
Gestal M. et al., 
Introducción a los 
Algoritmos Genéticos y la 
Programación Genética, 
2010. 
García Martínez R. et al. 
Sistemas Inteligentes. 
2003. 
[Coley-99] An Introduction 
To Genetic Algorithms For 
Scientists And 
Engineers.pdf 
[Matworks] Optimization 
function toolbox.pdf 
Apuntes de clases. 
2 
T4-1 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-1 ALGORITMOS GENÉTICOS 
 INTRODUCCIÓN 
Los principios básicos de los Algoritmos 
Genéticos fueron establecidos por John 
Holland (fotos) de la Universidad de 
Michigan, a principio de los años 60’. Se 
destaca como la primera publicación 
relevante en 1975 titulada “Adaptation in 
Natural and Artificial System”. 
Los principios básicos de los Algoritmos Genéticos fueron establecidos 
por John Holland de la Universidad de Michigan, a principio de los años 
60’. Se destaca como la primera publicación relevante en 1975 titulada 
“Adaptation in Natural and Artificial System”. 
Están basados en el proceso genético de evolución de los organismos 
vivos postulados por Darwin, bajo los principios de selección natural y 
supervivencia de los más fuertes. 
Por imitación de este proceso, los Algoritmos Genéticos son capaces 
de ir buscando soluciones matemáticas para problemas del mundo 
real, de forma totalmente diferente a las tradicionales. 
La importancia de estos sistemas es la posibilidad de encontrar 
soluciones –al azar-, con un alto grado de precisión, aunque no se 
garantice la obtención de un resultado exacto. 
John H. Holland John H. Holland 
http://edge.org/memberbio/john_h_holland
4 
T4-1 ALGORITMOS GENÉTICOS 
 PROPIEDADES 
 Utilizan un modelo con analogía directa al método 
de selección natural. 
 Es una técnica robusta aplicable al tratamiento de 
problemas de cualquier campo. 
 La eficacia de un AG depende en gran medida de 
la codificación de sus datos. 
 Se utilizan básicamente para resolver problemas 
de búsqueda y optimización. 
 Está demostrado que pueden alcanzar la solución 
óptima de un problema, pero sin limitación 
temporal, por lo tanto puede no llegarse a la 
solución en un tiempo razonable. 
 La existencia de técnicas especializadas y 
exclusivas para resolver un problema pueden ser 
más eficientes que los algoritmos genéticos. 
5 
T4-1 ALGORITMOS GENÉTICOS 
 CONTEXTO GENERAL 
6 
T4-1 ALGORITMOS GENÉTICOS 
 ESQUEMA CONCEPTUAL 
Individuos (Población inicial) Solución 
Situación inicial 
7 
T4-1 ALGORITMOS GENÉTICOS 
 ESQUEMA CONCEPTUAL 
Individuos 
(Nueva generación) 
Solución 
Óptimo local 
(solución aparente) 
Evolución hasta un máximo local 
8 
T4-1 ALGORITMOS GENÉTICOS 
 ESQUEMA CONCEPTUAL 
Solución 
Individuos 
(Generación final) 
Óptimo global 
(individuo que representa 
la solución) 
Evolución hasta la solución 
9 
T4-1 ALGORITMOS GENÉTICOS 
 ESQUEMA OPERATIVO 
10 
T4-1 ALGORITMOS GENÉTICOS 
 PROCEDIMIENTO OPERATIVO 
 Definición del problema. 
 Codificación. 
 Función de adaptación. 
 Población inicial. 
 Operadores genéticos. 
 Selección para reproducción. 
Definición del problema. 
11 
T4-1 ALGORITMOS GENÉTICOS 
 DEFINICIÓN DEL PROBLEMA 
Si bien los AG pueden aplicarse en cualquier 
campo, no siempre son aptos para cualquier tipo de 
problema. 
El éxito operativo de un AG depende en gran 
medida de una adecuada formulación y codificación 
de los parámetros que definen el problema. 
Suelen ser bastante eficientes cuando se aplican a 
problemas con grandes espacios de búsqueda, o a 
problemas con muchas restricciones, o con 
problemas con formulaciones matemáticas muy 
complejas y/o no lineales. 
Los tipos de problemas característicos para 
resolver con AG son los de búsqueda en espacios 
definidos y los de optimización en cualquier campo. 
12 
T4-1 ALGORITMOS GENÉTICOS 
 PROCEDIMIENTO OPERATIVO 
 Definición del problema. 
 Representación / Codificación. 
 Función de adaptación. 
 Población inicial. 
 Operadores genéticos. 
 Selección para reproducción. 
Representación / Codificación. 
13 
T4-1 ALGORITMOS GENÉTICOS 
 REPRESENTACIÓN / CODIFICACIÓN 
Es el proceso por el cual, los parámetros de definición del 
problema se representan como una cadena de caracteres, 
en un determinado código –usualmente el binario-. 
Cada conjunto de parámetros codificado representará a un 
individuo de la población del AG, denominado cromosoma, y 
a la estructura genérica de los individuos se la conoce como 
fenotipo. 
Por ejemplo 
Fenotipo [Valor1 Valor2 … ValorN] 
 
Individuo [100101 010010 … 101011] 
 
 
Fenotipo [Valor1 Propied1 … ValorN Propied.N] 
Individuo [236 -1,006 … 324 -4.256] 
Individuo o cromosoma 
cromosoma 
Gen (bit) Alelo (valor bit) Locus (posición bit) 
14 
T4-1 ALGORITMOS GENÉTICOS 
 PROCEDIMIENTO OPERATIVO 
 Definición del problema. 
 Representación / Codificación. 
 Función de adaptación. 
 Población inicial. 
 Operadores genéticos. 
 Selección para reproducción. 
Función de adaptación. 
15 
T4-1 ALGORITMOS GENÉTICOS 
 FUNCIÓN DE ADAPTACIÓN 
También llamada función de ajuste, función de encaje, 
función de evaluación, función objetivo, función de 
aptitud, fitness function. 
Mide la adaptación de cada individuo de la población a 
las condiciones del problema (medio ambiente). 
Cuando la función de adaptación evalúa a un individuo, 
le asigna un valor –usualmente real–, para medir el 
grado de adaptación. 
ƒadapt(individuo) = VR con VR ∈ 
La función de adaptación en los algoritmos 
genéticos juega el mismo papel que el medio 
ambiente en la evolución natural. 
Ver (Gestal, 2010) pág. 26 – Evaluación. 

16 
T4-1 ALGORITMOS GENÉTICOS 
 FUNCIÓN DE ADAPTACIÓN 
En general se requiere que la función de adaptación 
(ƒadapt) sea positiva y que el A.G. evolucione 
maximizando esta función. 
Para cierto tipo de problemas, se puede definir una 
función objetivo (gobj), que si requiere ser maximizada 
se puede considerar 
ƒadapt = gobj 
Pero cuando la función objetivo deba ser minimizada, 
se puede redefinir la función de adaptación 
ƒadapt(x)= gmax – gobj(x) 
con gmax ≥ gobj(x) ∀ x 
 
Ver (García, 2003) pág. 175. 
17 
T4-1 ALGORITMOS GENÉTICOS 
 PROCEDIMIENTO OPERATIVO 
 Definición del problema. 
 Representación / Codificación. 
 Función de adaptación. 
 Población inicial. 
 Operadores genéticos. 
 Selección para reproducción. 
Población inicial. 
18 
T4-1 ALGORITMOS GENÉTICOS 
 POBLACIÓN INICIAL 
La población es el conjunto de 
individuos que se establece para 
que interactúen en el espacio 
de soluciones. El tamaño de la 
población resulta una decisión crítica. 
Según Goldberg la población óptima crece 
exponencialmente con la longitud de los individuos. 
Alander, sugiere empíricamente una población entre K 
y 2K para individuos de longitud K, es apropiada para 
la mayoría de los problemas. 
Espacio de búsqueda
Individuos
Poblaciones muy densas generan un 
costo computacional muy grande. 
Poblaciones muy pequeñas NO pueden 
cubrir adecuadamente el espacio de 
búsqueda. 
19 
T4-1 ALGORITMOS GENÉTICOS 
 POBLACIÓN INICIAL 
Típicamente, la población inicial se establece 
generando individuos al azar, dentro del espacio de 
búsqueda, con una probabilidad uniforme. 
En ciertos 
casos se ha 
comprobado 
que cuando 
se utiliza una 
heurística 
válida para 
generar la 
población, 
la evolución 
del AG 
converge más 
rápidamente. 
Cuandola 
convergencia 
es 
demasiado 
rápida, 
quizás se 
está 
tendiendo 
hacia un 
mínimo local, 
lo cual puede 
redundar en 
una solución 
no 
aceptable. 
Evolución (Nº poblac iones)
C o n v e r g e n c i a n o r m a l
C o n v e r g e n c i a
p r e m a t u r a
C o n v e r g e n c i a
o s c i l a n t e
Valores generados por algún 
parámetro de medición de la 
función de ajuste 
20 
T4-1 ALGORITMOS GENÉTICOS 
 PROCEDIMIENTO OPERATIVO 
 Definición del problema. 
 Representación / Codificación. 
 Función de adaptación. 
 Población inicial. 
 Operadores genéticos. 
 Selección para reproducción. 
Operadores genéticos. 
21 
T4-1 ALGORITMOS GENÉTICOS 
 OPERADORES GENÉTICOS (OpG) 
Producen las transformaciones que sufren los 
individuos de una población (evolución) con el fin 
de generar nuevos individuos (descendientes) 
que ofrezcan nuevas características para 
acercarse o alcanzar la solución. 
Los operadores clásicos son 
 Operador de selección 
 Operador de cruza. 
 Operador de mutación. 
 Operador de inversión. 
 Otros operadores. 
22 
T4-1 ALGORITMOS GENÉTICOS 
 PROCEDIMIENTO OPERATIVO 
 Definición del problema. 
 Representación / Codificación. 
 Función de adaptación. 
 Población inicial. 
 Operadores genéticos. 
 Selección para reproducción. Selección para reproducción. 
23 
T4-1 ALGORITMOS GENÉTICOS 
 OpG - SELECCIÓN 
Operador de selección: Los individuos elegidos 
aportarán sus genes a la nueva generación, por lo 
tanto deberían ser los mejores. 
1. Selección por ruleta: A cada individuo de la 
 población se le asigna una cantidad de ranuras 
 proporcional a su aptitud. 
 
 
2. Selección por control de número esperado: intenta 
minimizar el error de la ruleta. 
 
 
i
i
ƒc =
ƒ
Copias para 
individuo i 
Aptitud de 
individuo i 
Aptitud promedio 
De la población 
∑
i
i
i
ƒc =
ƒ
n
i=1
24 
T4-1 ALGORITMOS GENÉTICOS 
 OpG - SELECCIÓN 
3. Selección elitista: en los métodos estándares, los 
mejores individuos no se preservan. Los reemplazan 
sus hijos. El método elitista selecciona los mejores m 
individuos y los incluye en la siguiente generación. 
4. Selección por ranking: un súper-individuo puede 
llegar a dominar la población rápidamente 
(convergencia prematura). Rankear los individuos sin 
asignarles peso por aptitud. Una forma de asignación 
lineal sería 
 
 
n = tamaño de la población. 
i = posición del individuo en el ranking. 
Rmin ∈ (0,1) = número mínimo de copias esperadas. 
min
i min
(n - i).(1-R )c =R +2.
(n -1)
Ver (García, 2003) pág. 157. 
25 
T4-1 ALGORITMOS GENÉTICOS 
 OpG - CRUZA 
Operador de cruza: A partir de dos padres 
seleccionados, se determina un punto de corte en 
cada cadena y se intercambian las subcadenas, 
produciendo dos descendientes completos. 
Este operador se puede aplicar utilizando dos o más 
puntos de corte (cruza multipunto), obteniéndose en 
general una mayor amplitud en la exploración del 
espacio de búsqueda. 
10111111 0000000 1Progenitores
Descendientes
corte corte
11 000 10 1 11 000 11 0
corte
monopunto
10111111 0000000 1
1 0 1 1 0 00 0 1 111 0 00 1
Progenitores
Descendientes
c1 c2 c3 c4 c1 c2 c3 c4
corte
multipunto
26 
T4-1 ALGORITMOS GENÉTICOS 
 OpG - MUTACIÓN 
Operador de mutación: Se aplica sobre un solo 
padre. Consiste en mutar un bit seleccionado al azar. 
La aplicación de este operador (y de los restantes) 
debe considerar las restricciones impuestas a los 
fenotipos, es decir, un operador aplicado 
indiscriminadamente puede crear un individuo que 
quede fuera del espacio de búsqueda. 
1 Progenitor
1 Descendiente
MUTACIÓN
11 00 1 0 11
11 000 0 11
Selección
aleatoria
27 
T4-1 ALGORITMOS GENÉTICOS 
 OpG - INVERSIÓN 
Operador de inversión: También se aplica sobre un 
solo padre y produce un descendiente. Consiste en 
intercambiar dos genes seleccionado al azar. La 
probabilidad de aplicación es baja. El operador es de 
uso poco frecuente. 
La aplicación de este operador (y de los restantes) 
debe considerar las restricciones impuestas a los 
fenotipos, es decir, un operador aplicado 
indiscriminadamente puede crear un individuo que 
quede fuera del espacio de búsqueda. 
1111 00001 Progenitor
1 Descendiente
INVERSIÓN selección
aleatoria
01 111 000
28 
T4-1 ALGORITMOS GENÉTICOS 
 PRÓXIMA GENERACIÓN 
Para pasar a una nueva generación, se produce una 
generación intermedia formada por individuos 
ubicados en forma ordenada o aleatoria. 
Se produce la cruza y posteriormente se puede aplicar 
mutación / inversión. 
Selección o duplicación Recombina o cruza 
Generación 
actual (t) 
Generación 
intermedia (t) 
Generación 
siguiente (t+1) 
El uso de una generación/población intermedia no es 
obligatorio. Depende de la estrategia del diseñador. 
29 
T4-1 ALGORITMOS GENÉTICOS 
 AG SIMPLE O CANÓNICO - descripción 
Teniendo el método de codificación de las soluciones 
del problema, como cromosomas, un AG se 
desarrolla como: 
Paso 1 – Inicializar una población. 
Paso 2 – Evaluar cada cromosoma en la población. Si 
está la solución, detener → decodificar. 
Paso 3 – Crear nuevos cromosomas apareando los 
actuales, por cruza de pares. Mutar/invertir. 
Paso 4 – Eliminar los padres u otros, para mantener la 
cantidad inicial de individuos. 
Paso 5 – Evaluar que el nuevo cromosoma esté en el 
universo e insertarlo en la población. 
Paso 6 – Si se alcanza la condición de detención, 
finalizar y presentar el mejor cromosoma. De 
otra forma, volver al paso 3. 
30 
T4-1 ALGORITMOS GENÉTICOS 
 AG SIMPLE O CANÓNICO - pseudocódigo 
31 
T4-1 ALGORITMOS GENÉTICOS 
 ESQUEMAS 
Un esquema es una plantilla que describe un sub-
conjunto de estructuras con similitudes en deter-
minadas posiciones de atributos. 
Un individuo i pertenece a un esquema dado si coinciden 
sus alelos. 
110100 ∈ *10*00
Para todos los individuos de longitud L, sobre alfabetos de 
cardinalidad K, hay (K+L)L esquemas. 
La aptitud de un esquema es el promedio de las aptitudes de 
todas las instancias posibles. 
La posición j de un esquema se dice definida si su alelo vale 
0 ó 1. 
El orden de un esquema H [O(H)] es el número de posiciones 
definidas. 
Ver (García, 2003) pág. 165 
32 
T4-1 ALGORITMOS GENÉTICOS 
 APLICACIONES DE LOS AG 
Considerando que la habilidad principal de los AG es la 
búsqueda y optimización, tienen aplicaciones en los 
más diversos campos. Algunas de estas aplicaciones: 
• Diseño de circuitos VLSI. 
• Optimización del tamaño de enlaces en una red de 
comunicaciones. 
• Optimización del cableado de circuitos eléctricos. 
• Problema del viajante. 
• Minimización/maximización de funciones. 
• Procesamiento de imágenes. 
• Reconocimiento de patrones. 
• Optimización de reglas en una base. 
	ALGORITMOS GENÉTICOS I
	T4-1 ALGORITMOS GENÉTICOS�	CONCEPTO/DEFINICIÓN
	T4-1 ALGORITMOS GENÉTICOS�	INTRODUCCIÓN
	T4-1 ALGORITMOS GENÉTICOS�	PROPIEDADES
	T4-1 ALGORITMOS GENÉTICOS�	CONTEXTO GENERAL
	T4-1 ALGORITMOS GENÉTICOS�	ESQUEMA CONCEPTUAL
	T4-1 ALGORITMOS GENÉTICOS�	ESQUEMA CONCEPTUAL
	T4-1 ALGORITMOS GENÉTICOS�	ESQUEMA CONCEPTUAL
	T4-1 ALGORITMOS GENÉTICOS�	ESQUEMA OPERATIVO
	T4-1 ALGORITMOS GENÉTICOS�	PROCEDIMIENTO OPERATIVO
	T4-1 ALGORITMOS GENÉTICOS�	DEFINICIÓN DEL PROBLEMA
	T4-1 ALGORITMOS GENÉTICOS�	PROCEDIMIENTO OPERATIVO
	T4-1 ALGORITMOS GENÉTICOS�	REPRESENTACIÓN / CODIFICACIÓN
	T4-1 ALGORITMOS GENÉTICOS�	PROCEDIMIENTO OPERATIVO
	T4-1 ALGORITMOS GENÉTICOS�	FUNCIÓN DE ADAPTACIÓN
	T4-1 ALGORITMOS GENÉTICOS�	FUNCIÓN DE ADAPTACIÓN
	T4-1 ALGORITMOS GENÉTICOS�	PROCEDIMIENTO OPERATIVO
	T4-1 ALGORITMOS GENÉTICOS�	POBLACIÓN INICIAL
	T4-1 ALGORITMOS GENÉTICOS�	POBLACIÓN INICIAL
	T4-1 ALGORITMOS GENÉTICOS�	PROCEDIMIENTO OPERATIVO
	T4-1 ALGORITMOS GENÉTICOS�	OPERADORES GENÉTICOS (OpG)
	T4-1 ALGORITMOS GENÉTICOS�	PROCEDIMIENTO OPERATIVO
	T4-1 ALGORITMOS GENÉTICOS�	OpG - SELECCIÓN
	T4-1 ALGORITMOS GENÉTICOS�	OpG - SELECCIÓN
	T4-1 ALGORITMOS GENÉTICOS�	OpG - CRUZA
	T4-1 ALGORITMOS GENÉTICOS�	OpG - MUTACIÓN
	T4-1 ALGORITMOS GENÉTICOS�OpG - INVERSIÓN
	T4-1 ALGORITMOS GENÉTICOS�	PRÓXIMA GENERACIÓN
	T4-1 ALGORITMOS GENÉTICOS�	AG SIMPLE O CANÓNICO - descripción
	T4-1 ALGORITMOS GENÉTICOS�	AG SIMPLE O CANÓNICO - pseudocódigo
	T4-1 ALGORITMOS GENÉTICOS�	ESQUEMAS
	T4-1 ALGORITMOS GENÉTICOS�	APLICACIONES DE LOS AG