PDF de programación - Algoritmos Genéticos

Algoritmos genéticos

•  1960

– John Holland, en la Universidad de Michigan,

desarrolla AG con los siguientes objetivos:

•  Imitar los procesos adaptativos de los sistemas naturales
•  Diseñar sistemas artificiales (programas) que retengan los

mecanismos importantes de los sistemas naturales.

Propuso el cruzamiento y operadores de recombinación.

•  La programación evolutiva de Fogel, se inició como un intento de
usar la evolución para crear máquinas inteligentes, que pudieran
prever su entorno y reaccionar adecuadamente a él.

•  Estos primeros experimentos demostraron el potencial de la

evolución como método de búsqueda de soluciones novedosas.

Algoritmos genéticos

•  La Evolución
•  La Naturaleza es la base de
inspiración de los algoritmos
genéticos.
–  Darwin predecesor de la

teoría evolutiva.
•  La historia de la vida está
causada por una serie de
procesos que actúan en y
dentro de las poblaciones:
reproducción, mutación,
competición y selección.

•  La evolución son los cambios

en el conjunto genético de
una población.

Sistemas naturales
Cromosoma

Algoritmos genéticos
Individuo o
estructura

Gen

Alelo

Locus

Genotipo

Fenotipo

Característica o
atributo

Valor

Posición en la
estructura

Conjunto de genes

Aptitud del individuo

Algoritmos genéticos

•  Algoritmo genético
resolver problemas

– Imita a la evolución biológica como estrategia para
– Simula la evolución de una población de individuos
– Cada estructura está compuesta de características
que definen la aptitud del individuo en su entorno
– La población evoluciona de generación en generación

mediante la combinación y la selección de las
estructuras más aptas

– Cada generación representa una nueva población.
– Un individuo representa una solución posible a un
– La aptitud es una medida de bondad de la solución
– El objetivo del algoritmo genético es buscar una

problema dado

“buena” solución

Algoritmos genéticos

•  Hoy en día, la computación evolutiva es un campo floreciente, y los

algoritmos genéticos están resolviendo problemas de interés
cotidiano en áreas de estudio tan diversas como:

–  Predicción en la bolsa y la planificación de la cartera de valores
–  Ingeniería aeroespacial
–  Diseño de microchips
–  Bioquímica y biología molecular
–  Diseño de horarios en aeropuertos
–  Líneas de montaje.
–  Minería de datos
–  Sistemas de clasificación
–  Diseño evolutivo
–  Robótica evolutiva

Algoritmos genéticos

Proceso de un AG
•  Inicialmente se debe definir la representación de
las soluciones candidatas en individuos de una
población y la construcción de la función que
medirá la aptitud de cada uno de los individuos.
•  Posteriormente se aplicarán los operadores de
selección, cruza y mutación a dicha población
para crear nuevas generaciones de individuos

Algoritmos genéticos

Población
•  En general los Algoritmos Genéticos trabajan sobre

una población fija de N individuos inicializada
aleatoriamente.

•  El tamaño N de la población afecta al programa

evolutivo.

•  N debe ser un número tal que permita tener diversidad
de individuos, sin sacrificar la eficiencia en la búsqueda.

•  Cada generación debe conservarse el número N de

individuos.

Algoritmos genéticos

Función de Evaluación de Aptitud
• 

Llamada también => Función de Adaptación

•  Es una función que aplicada sobre un individuo

(cromosoma) produce como resultado que mide la
calidad del individuo como solución del problema.

• 

Influye en la complejidad en tiempo del Algoritmo
Genético.
–  Evaluar la función objetivo
–  Convertir el valor de la función objetivo en aptitud.

Minimizar f(x) = x. Sen (10π .x) +1.0

función de aptitud =

Algoritmos genéticos

Selección
•  Sabiendo la aptitud de cada cromosoma, se procede a

la selección de los que se cruzarán en la siguiente
generación (presumiblemente, se escogerá a los
"mejores").

•  Dos son los métodos de selección más comunes:

–  Por ruleta
–  Por torneo

•  Algunos de los individuos seleccionados sobrevivirán

directamente en la siguiente generación (elitismo)

•  Otros participan en la cruza contribuyendo en la

formación de nuevos individuos semejantes

Algoritmos genéticos

Cruza
•  Una vez realizada la selección, se procede a la

reproducción o cruza de los individuos seleccionados.

•  En esta etapa, los sobrevivientes intercambiarán

material cromosómico y sus descendientes formarán la
población de la siguiente generación.

•  Las 2 formas más comunes de reproducción son:

–  Uso de un punto único de cruza .
–  Uso de 2 puntos de cruza.

•  La selección impone un sesgo en la cruza, los mejores

individuos tienden a dominar la población

Algoritmos genéticos

Mutación
•  Además de la selección y la cruza, existe otro operador
llamado mutación, el cual realiza un cambio a uno de
los genes de un cromosoma elegido aleatoriamente.

•  Garantiza que ninguna característica se pierda

irremediablemente en la operación.

•  Toma algunos pocos individuos generados en la nueva

población y les altera algunas características al azar

•  Evita que se pierdan alelos y contribuye a la creación de

•  Existen distintas posibilidades, que producen una mayor o menor

nuevos individuos

alteración en el descendiente:
–  Mutación en un punto.

Algoritmo genético simple

Inicio

Mutación

Generar una

población

Cruza

Evaluar la aptitud

Selección

Condición
de parada

Fin

Algoritmos genéticos

Ventajas
•  Pueden resolver en forma rápida y eficiente problemas

complejos con características como:
–  Alta cardinalidad del espacio de búsqueda
–  Alta dimensionalidad en la función aptitud

•  Utilizan muy poca información del problema, solo
requiere la posibilidad de proponer una solución y
asignar una evaluación

•  Son extensibles, no siempre se puede anticipar todas

las dificultades, pero es fácil modificar o incorporar
conocimiento en los operadores genéticos

•  Pueden ser utilizados para realizar una primera

búsqueda global.

Algoritmos genéticos

cruza

mutación

Programación genética

• 

Algoritmo
1.  Crear al azar una población de P programas compuestos por

los símbolos de los conjuntos de funciones y terminales
• 
Parámetro principal es el tamaño máximo de un programa.
• 
Límite sobre el número de nodos o sobre la profundidad del
árbol.

2.  Hasta cumplir el criterio de terminación

1.  Ejecutar cada programa de la población y obtener su aptitud
2.  Seleccionar los individuos de la población
3.  Crear nuevos individuos (programas) mediante la aplicación de
los siguientes operadores genéticos selección, cruza y mutación
3.  Devolver como resultado el mejor individuo de la población

final

Programación genética

Utiliza símbolos terminales:

•  Variables independientes
•  Funciones con aridad= 0 (sin operandos)
•  Constantes

Conjunto de funciones permitidas junto con la aridad de cada función

Método para evaluar el desempeño de los programas

Programación genética

Programación genética

Programación genética

Cruza

Programación genética

Mutación