Algoritmos

ALGORITMOS GENÉTICOS
Arranz de la Peña, Jorge
Universidad Carlos III 100025106@alumnos.uc3m.es

Parra Truyol, Antonio
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 1962 asientalas 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 para finalmenteobtener la siguiente generación de individuos que estarán más adaptados que la anterior generación.

ESTRUCTURA DE UN ALGORITMO GENÉTICO SIMPLE (AGS)

Cromosomas Codificación Codificación Soluciones 1100101010 1011101110 0011011001 1100110001 Selección Selección

110010 101110

1010 1110

Cruce Cruce

1100101110

0011011001 0011011001 0011001001 0011001001

Mutación MutaciónEvaluación Evaluación
1100101110 1100101110 1011101010 1011101010 0011001001 0011001001

Cálculo Aptitud Cálculo Aptitud
Soluciones Soluciones

Rueda de la Ruleta Rueda de la Ruleta

Decodificación Decodificació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 lo suficientemente 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óngenerada. 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.

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 realizarreproducciones 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 mayor velocidad en la resolución del problema.

• •

3.2 Probabilidad de Cruce
Indicala 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 probabilidad de cruce es del 100% el hijo se crea totalmente por cruce, no porpartes.

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 última opción suele ser la más habitual. Veamos el esquema general de un algoritmo genético simple:

3.3 Probabilidad de Mutación...