Algoritmo genetic

Tema:

ALGORITMOS GENÉTICOS
Autores:
Katherine Viteri
Christian Salazar
Carlos Paredes
José Luis Muñoz
Abstract
Los algoritmos genéticos son parte de la computación evolutiva, es un área creciente de la inteligencia
artificial que esta basada en la evolución natural biológica, y pueden adaptarse a la resolución de
múltiples problemas.
Como es de esperarse los AG (algoritmos genéticos)están basados en la teoría de la evolución de Darwin,
y son apropiados para resolver problemas donde el dominio de la solución pueda resultar demasiado
extenso. Estos algoritmos buscan generar un conjunto de soluciones para un problema basados en un
nivel de aptitud (fitness), la eficacia del algoritmo será plenamente dependiente de los criterios que se
consideren para la determinación delfitness así como de su representación. Se han aplicado con cierto
éxito algoritmos genéticos al reconocimiento de formas y patrones, a sistemas clasificadores, al
funcionamiento de oleoductos, en aplicaciones financieras, sistemas de información, sistemas de
producción , sistemas de toma de decisiones, etc
Ejemplo del problema del agente viajero(ejecutable)
Ejemplo del problema del agenteviajero(codigo)
Articulo copleto (formato pdf)

Introducción
La Computacion Evolutiva fue introducida en los años sesenta por I. Rechenberg en su trabajo
"Estrategias Evolutivas" (nombre original Evolutionsstrategie) Esta idea fue desarrollada por otros
investigadores, hasta que en 1975 John Holland y sus colegas publican el libro “Adaptación Natural y
Sistemas Artificiales”( Adaption in Naturaland Artificial System) Como una analogía a la codificación
genética de los seres vivos, quienes almacenan sus características físicas en los genes que se disponen
linealmente para formar cromosomas, los problemas de optimización que utilizan algoritmos genéticos
almacenan sus unidades mínimas de información para cada elemento de la población en genes, esta
cadena de longitud finita forma a suvez los cromosomas. La codificación tradicional propuesta por
Holland enmarca cadenas de cromosomas formada por ceros y unos pero se pueden utilizar sinnúmero de
patrones de símbolos para una representación.
Operadores Básicos utilizados en un AG
Durante el proceso de fecundación, el espermatozoide y el óvulo se unen y reconstruyen en el nuevo
organismo la disposición por pares de loscromosomas; la mitad de estos cromosomas procede de cada
padre. Este mismo hecho simulan los algoritmos genéticos con el proceso de cruzamiento donde dos
cromosomas comparten información genética en pos de crear un nuevo individuo.

Las mutaciones son la materia prima de la evolución. No obstante, sin mutaciones las especies no
evolucionarían. La evolución tiene lugar cuando una nueva versión deun gen, que originalmente surge
por una mutación, aumenta su frecuencia y se extiende a la especie gracias a la selección natural. En los
AG, las mutaciones son quienes permiten crear nuevos individuos, escapar de los mininos locales,
abastecernos de nuevo material genético, y en ciertos casos mejorar los procesos de elitismo en busca de
mejores soluciones.
En los procesos evolutivos lashembras seleccionan a los machos mejor dotados que aseguren su
descendencia, por su parte los AG involucran en su desarrollo criterios de elitismo por medio de
penalizaciones para determinar su aptitud; los cromosomas con el menor número de penalizaciones serán
los más aptos. Este criterio se aplica con la finalidad de mantener al mejor individuo de cada población y
copiarlo a la siguiente de estamanera se asegura mantener en cada nueva población al cromosoma con
mejor aptitud.

Desarrollo
Pseudocodigo Algoritmo Genético
1.
2.
3.

4.
5.
6.

[Inicio] Generar una población randomica de n cromosomas
[Fitness] Evaluar el fitness f(x) para cada cromosoma x en la población
[Nueva población] Crear una nueva población repitiendo los siguientes pasos hasta que se
cumpla la...