Algoritmos genéticos

Algoritmos genéticos

Los algoritmos genéticos son algoritmos estocásticos iterativos que operan sobre individuos de una población inicial.

En los algoritmos genéticos, la población evoluciona de la generación k a la generación k+1 utilizando tres operadores:

  • un operador de selección
  • un operador de cruce
  • un operador de mutación.

El proceso proviene de la evolución genética. Comenzamos con una población de soluciones potenciales iniciales elegidas arbitrariamente. Se evalúa su rendimiento relativo (fitness). Con base en estos desempeños, creamos una nueva población de soluciones potenciales usando los operadores. Repetimos este ciclo hasta que tengamos una solución satisfactoria.

Programación genética y algoritmos genéticos.

algoritmos genéticos

  1. Población base generada aleatoriamente: n vectores solución (individuos)
  2. Evaluación de cada individuo, esta evaluación arroja un valor cuantitativo (fitness)
  3. Selección por sorteo de un subconjunto de individuos por rueda sesgada, por rango, por torneo o por eugenesia. Cada individuo tiene una probabilidad de ser elegido proporcional a su evaluación (o adaptación al problema).
  4. Cruces y Mutaciones de individuos seleccionados.

Los cruces y mutaciones de algoritmos genéticos no necesariamente dan soluciones aceptables al problema. Operan alterando, copiando, reemplazando, etc., el vector solución de uno o más individuos para formar uno nuevo.

Ejemplo

Para poder realizar cruces y mutaciones de la forma más sencilla posible, codificaremos los individuos mediante una cadena binaria. El cruce se hará entonces por una subcadena, y la mutación por la modificación de un bit. Este proceso se llama codificación binaria.

Estamos buscando el máximo de f(x)=4x*(1-x) en el intervalo [0,1]. Tomamos una población inicial de 4 elementos codificados en 8 bits (que se convertirán en un valor entre 0 y 1). Las nuevas generaciones siempre incluirán 4 individuos. La tabla de valores de generación inicial es la siguiente:

Elemento
f(x)
% / totales
acumulación
10111010
0.794678
0.79/2.59=0.31
0.31
11011110
0.460693
0.18
0.49
00011010
0.364990
0.14
0.63
01101100
0.9775586
0.37
1.00
2.595947

El elemento representa a los individuos, f(x) el valor de la función objetivo, % / total es el porcentaje del valor de la función objetivo de un elemento en comparación con la suma de los valores de la función objetivo, el acumulado es la suma de los porcentajes. Tenemos por tanto al final la importancia de cada individuo dado el valor de la función objetivo.

Ahora que la evaluación está hecha, necesitamos seleccionar individuos para el cruce. Como tenemos una escala de importancia de cada individuo, podemos aleatorizar a los individuos. De hecho, cuanto mayor sea el valor objetivo de un individuo, más probable es que sea atraído. Se extraen cuatro números aleatorios entre 0 y 1: 0,34, 0,02, 0,64 y 0,77. Por lo tanto, hemos seleccionado a estos individuos: 11011110, 10111010, 01101100, 01101100.

Hemos seleccionado a los padres, ahora nos toca cruzar. Para esto, elegimos un marcador aleatorio en la cadena de bits e intercambiamos la parte derecha de la cadena:

algoritmos genéticos

La población de la próxima generación está compuesta por los cuatro hijos así creados. En general, evitaremos hacer un cruce entre dos individuos idénticos.

Compartir, repartir