algoritmos geneticos

ALGORITMOS GENÉTICOS


En este documento se pretende analizar los algoritmos genéticos
descubriendo su funcionamiento y sus secretos.

1. INTRODUCCION
Cuando hablamos de algoritmos genéticos, hay que hablar de
John Holland que en 1962 asienta las bases para sus posteriores
desarrollos hasta llegar a lo que se conoce hoy por algoritmos
genéticos.
Un algoritmo genético es un método debúsqueda que imita la
teoría de la evolución biológica de Darwin para la resolución de
problemas. Para ello, se parte de una población inicial de la cual
se seleccionan los individuos más capacitados para luego
reproducirlos y mutarlos para finalmente obtener la siguiente
generación de individuos que estarán más adaptados que la
anterior generación.

2. ESQUEMA BÁSICO
En la naturaleza todoel proceso de evolución biológica se hace de
forma natural pero para aplicar el algoritmo genético al campo de
la resolución de problemas habrá que seguir una serie de pasos.
Una premisa es conseguir que el tamaño de la población sea lo
suficientemente grande para garantizar la diversidad de
soluciones. Se aconseja que la población sea generada de forma
aleatoria para obtener dichadiversidad. En caso de que la
población no sea generada de forma aleatoria habrá que tener en
cuenta que se garantice una cierta diversidad en la población
generada. Los pasos básicos de un algoritmo genético son:
•

Evaluar la puntuación de cada uno de los cromosomas
generados.

•

Permitir la reproducción de los cromosomas siendo los
más aptos los que tengan más probabilidad de
reproducirse.•

Con cierta probabilidad de mutación, mutar un gen del
nuevo individuo generado.

•

Organizar la nueva población.

Estos pasos se repetirán hasta que se de una condición de
terminación. Se puede fijar un número máximo de iteraciones
antes de finalizar el algoritmo genético o detenerlo cuando no se
produzcan más cambios en la población (convergencia del
algoritmo). Esta últimaopción suele ser la más habitual.
Veamos el esquema general de un algoritmo genético simple:

ESTRUCTURA DE UN ALGORITMO
GENÉTICO SIMPLE (AGS)

Cromosomas
Codificación
Codificación
Soluciones

110010

1100101010

101110

1011101110

1010
1110

Cruce
Cruce

1100101110

0011011001
1100110001

0011011001
0011011001

Mutación
Mutación

0011001001
0011001001Selección
Selección

Evaluación
Evaluación
1100101110
1100101110
1011101010
1011101010
0011001001
0011001001

Rueda de la Ruleta
Rueda de la Ruleta

Decodificación
Decodificación

Cálculo Aptitud
Cálculo Aptitud
Soluciones
Soluciones

Figura1. Esquema de un algoritmo genético simple.

3. PARÁMETROS DE LOS ALGORITMOS
GENÉTICOS.
Para el estudio de los algoritmos genéticos hayque tener en
cuenta una serie de parámetros:

3.1 Tamaño de la Población
Este parámetro nos indica el número de cromosomas que tenemos
en nuestra población para una generación determinada. En caso de
que esta medida sea insuficiente, el algoritmo genético tiene pocas
posibilidades de realizar reproducciones con lo que se realizaría
una búsqueda de soluciones escasa y poco óptima. Por otrolado si
la población es excesiva, el algoritmo genético será excesivamente
lento. De hecho estudios revelan que hay un límite a partir del
cual es ineficiente elevar el tamaño de la población puesto que no
se consigue una mayor velocidad en la resolución del problema.

3.2 Probabilidad de Cruce
Indica la frecuencia con la que se producen cruces entre los
cromosomas padre es decir, que hayaprobabilidad de
reproducción entre ellos. En caso de que no exista probabilidad de
reproducción, los hijos serán copias exactas se los padres. En caso
de haberla, los hijos tendrán partes de los cromosomas de los
padres. Si la probabilidad de cruce es del 100% el hijo se crea
totalmente por cruce, no por partes.

3.3 Probabilidad de Mutación
Nos indica la frecuencia con la que los genes...