customkeys

ALGORITMOS GENÉTICOS
Arranz de la Peña, Jorge

Parra Truyol, Antonio

Universidad Carlos III
100025106@alumnos.uc3m.es

Universidad Carlos III
100023822@alumnos.uc3m.es

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 1962asienta 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 de bú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 parafinalmente 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 todo el 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 losuficientemente grande para garantizar la diversidad de
soluciones. Se aconseja que la población sea generada de forma
aleatoria para obtener dicha diversidad. 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 cadauno 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 deiteraciones
antes de finalizar el algoritmo genético o detenerlo cuando no se
produzcan más cambios en la población (convergencia del
algoritmo). Esta última opció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)

Codificación
Codificación
Soluciones

Cromosomas

110010

1100101010

1011101011101110

1010
1110

Cruce
Cruce

1100101110

0011011001
1100110001

0011011001
0011011001

Mutación
Mutación

0011001001
0011001001

Selección
Selección

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

Rueda
Rueda de
de la
la Ruleta
Ruleta

Decodificación
Decodificación

Cálculo
Cálculo Aptitud
Aptitud
SolucionesSoluciones

Figura1. Esquema de un algoritmo genético simple.

3. PARÁMETROS DE LOS ALGORITMOS
GENÉTICOS.
Para el estudio de los algoritmos genéticos hay que 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 otro lado 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 mayorvelocidad 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 haya probabilidad 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...