Algoritmos genéticos

Los algoritmos genéticos fueron creados asimilando el comportamiento de la evolución de los seres vivos la cual plantea que los seres con mejores cualidades o mejor adaptados son los que tienen mayor oportunidad de sobrevivir, y por lo tanto, de generar una mayor y mejor preparada descendencia. Los algoritmos genéticos caben dentro de la rama de la inteligencia artificial.

Los algoritmos genéticos están basados en probabilidad y pueden ayudarnos a encontrar soluciones en problemas que no tienen una función específica para su solución. Y su campo de uso es muy amplio.

El proceso que el algoritmo genético intenta imitar es el de la selección natural en el cual a partir de una muestra aleatoria de una población en donde los ejemplares, que son las posibles soluciones que se pueden dar al problema, con mejores características o mejor ponderados son los que tendrán mayor probabilidad de cruzarse. El resultado del cruce de estos individuos creará una generación con mejores características que sus ancestros, lo que en teoría deberá acercarnos cada vez más a una solución óptima. Este ciclo se repite cierta cantidad de veces hasta que se considere que se llega a una solución óptima. Algunos algoritmos evolutivos más complejos pueden irse mejorando conforme se vayan realizando las iteraciones para cada generación, lo que permite tener un algoritmo inteligente que va aprendiendo de acuerdo a su experiencia.

Es importante hacer notar que debemos de tener una función que nos deberá ponderar de manera efectiva cuales son los ejemplares con mejores cualidades, para que tengan una mejor oportunidad de crear nuevas generaciones. Estas funciones deberán de “castigar” las peores soluciones y “premiar” las mejores.

El algoritmo genético simple tiene la siguiente estructura:

BEGIN

                Generar una población inicial

                Computar la función de evaluación de cada individuo

                WHILE NOT Terminado DO

                BEGIN–producir una nueva generación

                               FOR Tamaño población

                               BEGIN    --ciclo reproductivo

                                    Seleccionar dos individuos de la generación anterior para el cruce

(probabilidad de selección proporcional a la función de evaluación del

individuo

Cruzar con cierta probabilidad los dos individuos obteniendo dos

descendientes

Mutar los dos descendientes con cierta probabilidad

Computar la función de los dos descendientes mutados

Insertar los dos descendientes mutados en la nueva población

                               END

                               IF la población ha convergido THEN

                                               Terminado = True

                               END IF

                END

END

La aplicación de los algoritmos evolutivos tienen las siguientes aplicaciones:

• Diseño automatizado de equipo industrial
• Diseño de sistemas de distribución de agua
• Aprendizaje de comportamiento de robots
• Optimización de estructuras moleculares
• Predicción
• Diseño de topología de redes computacionales
• Problema del viajante
• Etc.