Algoritmos 20Gen E9ticos

Algoritmos Genéticos
Idea:

Técnicas de búsqueda que simulan la evolución

Características:
⇒ Basadas en la Selección Natural
⇒ Mecanismos de Búsqueda por intercambio aleatorizado de
información
⇒ Explotación eficiente de la información histórica
⇒ Idea desarrollada originalmente por John Holland de la Univ.
Michigan (1962)

Surgen del establecimiento de una analogía con ideas de la genética yla
selección natural, donde:
2 Los individuos compiten por la oportunidad de reproducirse
2 Se introducen en la población individuos con nuevas
características cuando:

: los individuos existentes intercambian material genético
durante la reproducción
: ocurren mutaciones

Finalidad

Supervivencia del más apto

Modo de conseguirlo

Adaptación al Entorno

En resumen: los más aptos tienen másposibilidades de sobrevivir y, como

resultado, más oportunidades de transmitir sus características a las
generaciones siguientes.

Terminología:

Mezcla de informática y genética

Supuesto:

La “estructura genética”, o
información de un individuo (útil a
efectos de su transmisión) puede
describirse como una estructura de
datos: cadena de bits representada
como una lista de ceros y unos, o
caracteres uotras más complejas

Cadena que codifica a un individuo
Bit/caracter
Cadena asociada a un individuo

Cromosoma
Alelo
Genotipo

Los algoritmos genéticos operan sobre poblaciones que evolucionan
denominadas generaciones.
Fundamento del proceso de selección Basado en la aptitud (fitness) de los
individuos, expresada como una
cierta medida de evaluación

Componentes de un Algoritmo Genético:Representaciones & Operadores

Representación mediante espacio de
estados
Espacio de búsqueda
Porción del espacio de búsqueda a
examinar en cada iteración
Estado

Representación mediante
estructuras genéticas
Colección de individuos (poblaciones)
Población

Individuo representado como una
cadena de caracteres denominada
cromosoma, donde cada elemento se
denomina gen y cada valor del gen,
alelo.
Operadoresque transforman estados Operadores que alteran la
composición de los hijos que se
producen en las siguientes
generaciones por combinación de los
padres
Búsqueda de trayectorias entre
Mecanismos que “acercan” la
estados inicial y final
población inicial hacia las posibles
soluciones (normalmente aleatorios)
Objetivo: encontrar el estado final o Objetivo: encontrar individuos en el
la trayectoriaentre el inicial y el
espacio de búsqueda que posean el
final
“mejor material genético” para su
supervivencia en el nicho, es decir,
buscar los individuos mejor
adaptados
Medida de calidad: función objetivo Medida de calidad: función de
evaluación.

Para poder emular el proceso de evolución se debe disponer de:
1) Una población de posibles soluciones representadas a través de
individuos
2) Unprocedimiento de selección basado en la aptitud de los
individuos

3) Un procedimiento de transformación, esto es, de construcción de
nuevas soluciones a partir de las disponibles actualmente

Definición de Algoritmo Genético
(John Koza, 1982)

"El algoritmo genético es un algoritmo matemático
altamente paralelo que transforma un conjunto (población) de
objetos matemáticos individuales (típicamentecadenas de
caracteres de longitud fija que se ajustan al modelo de las
cadenas de cromosomas), cada uno de los cuales se asocia con una
aptitud, en una población nueva (es decir, la siguiente generación)
usando operaciones modeladas de acuerdo al principio Darwiniano
de reproducción y supervivencia del más apto y tras haberse
presentado de forma natural una serie de operaciones genéticas(notablemente la recombinación sexual)."

Dada una población de individuos de una generación, el algoritmo simula la
evolución natural y la reproducción para obtener la siguiente generación.
La actividad básica desarrollada por un algoritmo genético son
1) La generación de una población inicial
2) Un bucle principal de evolución de poblaciones hasta que se cumple
alguna condición (pe: alcanzar un nº de...