Los algoritmos genéticos, son metaheurísticas inteligentes de búsquedas y optimización
basadas en la evolución . Según los postulados de Darwin a lo largo de las generaciones,
los individuos evolucionan según los principios de selección natural y la supervivencia de
los más fuertes.
Los fundamentos de los algoritmos genéticos fueron introducidos por John Holland,en
1970. Estos establecen una similitud entre el conjunto de posibles soluciones de un
determinado problema y el conjunto de individuos de una población natural,
representando la información de cada solución en un vector binario, denominado
cromosoma.La idea básica en la que se basan los algoritmos genéticos es que durante la
evolución es que los individuos mejores adaptados tienen mayor posibilidad de sobrevivir
y reproducirse, mientras que los peores adaptados son eliminados.Los Algoritmos
genéticos simulan esta conducta tomando en cuenta una población inicial de soluciones
(cromosomas o individuos) y una función de adaptación, generalmente asociada a una
función objetivo. Mediante algunas técnicas de selección y la aplicación y la aplicación de
operadores genéticos, esta población es sustituida por otra nueva cuyos individuos poseen
mayor calidad.Todo este mecanismo se va repitiendo hasta encontrar una ”buena”
solución.
Los Algoritmos genéticos han sido aplicados en muchos problemas y en muy diversas
áreas.Generalmente se aplican a problemas de optimización combinatoria, problema cuya
NP-completitud hace que la aplicación de metaheurística sea en la mayoría de los casos la
elección más acertada para su resolución.
Los algoritmos genéticos mantienen una población de soluciones potenciales. Cada
individuo se evalúa según una función, de adaptación de acuerdo con el problema a
resolver. A continuación se aplica el proceso de selección y se eligen o se seleccionan los
individuos atendiendo a su calidad para formar parte de la nueva población. Continúan con
el proceso de cruzamiento, se elige dos padres y se cruzan para formar uno o dos hijos,
dependiendo de la selección efectuada, cambiando las correspondientes partes de cada
padre. La idea del cruzamiento se basa en el intercambio de información entre distintas
soluciones potenciales para generar mejores soluciones.
La mutación se aplica alternando aleatoriamente una posición de algunos cromosomas con
una cierta probabilidad, esta suele ser pequeña. La alteración sufrida por el cromosoma al
aplicar la mutación hace aumentar la diversidad en la población.
Algunos de sus principios más aceptados por los biólogos
- Los procesos de evolución operan sobre los cromosomas, elementos orgánicos que
codifican las estructuras de los seres vivientes. - La selección natural es la unión entre los cromosomas y la actuación de las
estructuras decodificadas. Los procesos de selección natural permiten que se
reproduzcan más aquellos cromosomas que codifican estructuras más exitosas de
las que no son. - El proceso de reproducción ocurre cuando la evolución toma lugar, bien a través de
mutaciones, donde los cromosomas de los hijos difieren ligeramente a los de los
padres, o por procesos de recombinación(cruce) en los cuales los cromosomas de
los hijos varían significativamente respecto a los padres mediante la combinación
del material genético de los padres.
Estructura general de un algoritmo genético:
- Elegir parámetros iniciales: tamaño de la población, número de generaciones,
probabilidades de aplicación de operadores. - Generación de una población inicial de soluciones potenciales.
- Evaluación de cada individuo de la población.
- Mientras no se cumpla una condición de parada:
a. Proceso de selección: seleccionar elementos de la población
b. Cruzamiento
c. Mutación
d. Evaluación de los nuevos individuos y elegir la nueva población - Devolver la mejor solución encontrada
A la hora de resolver un problema en particular utilizando algoritmos
genéticos, éste debe tener los siguientes elementos:
- Una representación genética(cromosómica) para las soluciones potenciales.
- Un procedimiento para crear una población inicial de soluciones potenciales.
- Una función de adaptación (calidad) que evaluará cada individuo de la población.
- Operadores genéticos que alteren la composición de los hijos.
- Valores para diferentes parámetros utilizados en los algoritmos genéticos como
pueden ser:tamaño de la población,número de generaciones.
Referencias
Cerrolaza, M., & Annicchiarico, W. (1996). Algoritmos de optimización estructural
basados en simulación genetica. Universidad Central de Venezuela.
Reina, G. V., & García, E. M. (2004). Sistemas evolutivos y selección de indicadores.
Universidad de Sevilla.