IntroGA

Algoritmo Genético Simple

Fabio González, Ph.D.
Departamento de Ingeniería de Sistemas e Industrial
Universidad Nacional de Colombia

Genotipo y fenotipo

Espacio de Búsqueda y
Espacio delProblema
estructura
computacional que
representa el punto
(cromosoma)

punto en el
espacio del
problema

Espacio de Búsqueda y
Espacio del Problema

Adaptabilidad en la naturaleza
y en los AGsdecodificación

Genotipo

ambiente

Fenotipo
decodificación

cadenas
(cromosomas)

solución

función

del

objetivo

problema
codificación

Adaptabilidad

valor
de la
solución

Solución de Problemas con
AEscodificación de
soluciones
función objetivo
Problema

búsqueda
genética

Solución

operadores genéticos
conocimiento
específico

asignación de
adaptabilidad
selección
mutación

búsqueda
genéticareplicación
recombinación
cruce

Ciclo Generacional de un GA

Algoritmo Genético
Inicializar
población

Crear descendientes a
través de variación
aleatoria
Evaluar la adaptabilidad de
cada solución candidataAplicar selección

NO

Terminar
SI

Política de Reemplazo
selección

Población
no
sobrelapada

cruce
mutación

AG generacional
selección

Población
sobrelapada

cruce
mutación

AG de estado estable(steady state)

Representación
cromosoma
gen
población

selección
cruce
mutación

alelo

Operadores Genéticos (cruce)
cruce de un solo punto

cruce de dos puntos
padre 1

padre 2

hijo 1

+

hijo 2Operadores Genéticos
(mutación)
mutación de un punto

mutación de varios puntos

mutación global

Evaluación de la adaptabilidad
(fitness)
A cada solución (cromosoma) se le
asigna un valor deadaptabilidad
dependiendo de que tan bueno es el
cromosoma solucionando el problema.
F: Cromosomas Æ R+

x

Æ F(x)

Selección por ruleta (1)
• Imagine una ruleta donde se han ubicado todos
los cromosomasen la población, cada uno tiene su
lugar de acuerdo con su función de adaptabilidad

Los miembros más aptos tienen una tajada
más grande
cromosoma1
cromosoma2
cromosoma3
cromosoma4

Para escoger...