Los algoritmos genéticos son unas técnicas de programación que, simulando el mecanismo de evolución de las especies enunciado por Darwin, realizan la búsqueda de una solución óptima a un problema mediante:
– La generación de un conjunto inicial aleatorio de soluciones (población). Cada posible solución en nuestro caso se representa como una secuencia de números enteros.
– Obtención de las siguientes generaciones, o «evolución». Para ello se repite N veces el siguiente proceso:
1. Evaluación de cada solución, y asignación de un valor (fitness) que indique el mayor o menor grado de cumplimiento de los objetivos perseguidos (el grado de bondad de la solución).
2. Selección de parejas de soluciones. Cada solución cuenta con una probabilidad Ps de ser seleccionada, que es mayor cuanto mayor sea su fitness.
3. Cruce de las soluciones elegidas para obtener nuevas soluciones, según una probabilidad Pc de cruce. Esto se lleva a cabo básicamente descomponiendo en dos segmentos cadenas solución «padres», y recombinándolos para obtener dos nuevas cadenas «hijo».
4. Mutación de las nuevas cadenas solución obtenidas, según una probabilidad de mutación Pm, normalmente muy pequeña. Se muta una solución cambiando aleatoriamente el valor de uno de los enteros que forman la secuencia.
La base del funcionamiento de los algoritmos genéticos es que las nuevas generaciones de soluciones encontradas tienen una elevada probabilidad de ser mejores que sus predecesoras. De esta manera, conforme se va repitiendo el ciclo de búsqueda, las cadenas encontradas tienen cada vez un valor fitness superior. Con la selección y el cruce de soluciones se consigue que las características de las secuencias iniciales, principalmente las de aquellas que han resultado ser mejores, se transmitan a las siguientes generaciones. Y la probabilidad de mutación permite explorar nuevas soluciones que nunca se habrían obtenido con tan solo cruzar las secuencias iniciales.
Es evidente que la primera generación, obtenida aleatoriamente, estará siempre compuesta por soluciones no óptimas. Es necesaria la repetición del ciclo de búsqueda un número muy elevado de veces para que las soluciones encontradas sean realmente aceptables. Por eso estos algoritmos requieren un gran tiempo de computación.
