PDF de programación - Algoritmos Genéticos (AG)

Inteligencia Artificial Ing. Bruno López Takeyas



ALGORITMOS GENÉTICOS (AG)



• Se basan en la Teoría de la Evolución

de Darwin



• Los individuos más aptos sobreviven
al adaptarse más fácilmente a su
entorno.



• Este proceso se controla por medio



de los genes.



Inteligencia Artificial Ing. Bruno López Takeyas



Características comunes en el

proceso de evolución



• Un

individuo

es

capaz de

reproducirse.

• Existe una población completa de

estos individuos.

• Hay gran variedad o diferencias
individuos que se

entre

los

reproducen.
• Dentro de

la variedad hay

algunas

diferencias

en

la

habilidad para sobrevivir, es

decir, existen

individuos con

mayor habilidad para adaptarse.



Inteligencia Artificial Ing. Bruno López Takeyas

Características de los AG
Características de los AG



• Buscan

soluciones

en

espacios

complejos.

• Se

utilizan

comunmente

en

problemas de optimización.

• Debe poderse definir una función de
aptitud que nos indique que tan

buena o mala es una respuesta.

• Las soluciones deben codificarse de
una forma que resulte relativamente

fácil de

implementar

en una

computadora.



Inteligencia Artificial Ing. Bruno López Takeyas

Esquemas de representación
Esquemas de representación



Ganancia

Señal de salida



Operadores
Operadores



• Selección.
• Cruzamiento.
• Mutación.



Inteligencia Artificial Ing. Bruno López Takeyas



Selección

• Escoge los mejores cromosomas
de la población inicial
• Utiliza una ruleta



2

4

1

3



Inteligencia Artificial Ing. Bruno López Takeyas

Cruzamiento



Suponiendo que se tienen las

siguientes cadenas:



A = 0 1 1 0 1

B = 1 1 0 0 0



Después



A' = 0 1 1 | 0 0



B' = 1 1 0 | 0 1

Antes



A = 0 1 1 | 0 1



B = 1 1 0 | 0 0

Punto de cruza



Fig. 3.4 Operador de cruzamiento con un punto.



Inteligencia Artificial Ing. Bruno López Takeyas



Mutación

Cambia aleatoriamente un gene de un

cromosoma



Caso de estudio
Caso de estudio

generar población inicial, G(0);

evaluar G(0);
t:=0;
repetir

t:=t+1;
generar G(t) usando G(t-1);
evaluar G(t);

hasta encontrar una solución;