ALGORITMOS GENÉTICOS ´ 

1 Introducci´on 

Los Algoritmos Gen´eticos (AGs) son metodos adaptados que pueden usarse para resolver problemas de busqueda ´ y optimizacion. Est´an basados en el proceso gen´etico de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la seleccion natural y la supervivencia de los m´as fuertes, postulados por Darwin (1859). Por imitaci´on de este proceso, los Algoritmos Geneticos son capaces de ir creando soluciones para problemas del mundo real. La evolucion de dichas soluciones hacia valores optimos ´ del problema depende en buena medida de una adecuada codificacion de las mismas. Los principios b´asicos de los Algoritmos Gen´eticos fueron establecidos por Holland (1975), y se encuentran bien descritos en varios textos – Goldberg (1989), Davis (1991), Michalewicz (1992), Reeves (1993) – . En la naturaleza los individuos de una poblacion compiten entre s´ı en la busqueda ´ de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en la busqueda ´ de un companero. ˜ Aquellos individuos que tienen m´as ´exito en sobrevivir y en atraer companeros ˜ tienen mayor probabilidad de generar un gran numero ´ de descendientes. Por el contrario individuos poco dotados produciran un menor numero ´ de descendientes. Esto significa que los genes de los individuos mejor adaptados se propagar´an en sucesivas generaciones hacia un numero ´ de individuos creciente. La combinacion de buenas caracterısticas provenientes de diferentes ancestros, puede a veces producir descendientes “superindividuos”, cuya adaptaci´on es mucho mayor que la de cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando unas caracter´ısticas cada vez mejor adaptadas al entorno en el que viven. Los Algoritmos Geneticos usan una analogıa directa con el comportamiento natural. Trabajan con una poblaci´on de individuos, cada uno de los cuales representa una soluci´on factible a un problema dado. A cada individuo se le asigna un valor o´ puntuacion, relacionado con la bondad de dicha solucion. En la naturaleza esto equivaldrıa al grado de efectividad de un organismo para competir por unos determinados recursos. Cuanto mayor sea la adaptacion de un individuo al problema, mayor ser´a la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material gen´etico con otro individuo seleccionado de igual forma. Este cruce producir´a nuevos individuos – descendientes de los anteriores – los cuales comparten algunas de las caracterısticas de sus padres. Cuanto menor sea la adaptacion de un individuo, menor ser´a la probabilidad de que dicho individuo sea seleccionado para la reproduccion, y por tanto de que su material gen´etico se propague en sucesivas generaciones. De esta manera se produce una nueva poblaci´on de posibles soluciones, la cual reemplaza a la anterior y verifica la interesante propiedad de que contiene una mayor proporcion de buenas caracter´ısticas en comparaci´on con la poblaci´on anterior. As´ı a lo largo de las generaciones las buenas caracter´ısticas se propagan a trav´es de la poblaci´on. Favoreciendo el cruce de los individuos mejor adaptados, van siendo exploradas las areas ´ m´as prometedoras del espacio de busqueda. ´ Si el Algoritmo Genetico ha sido bien disenado, ˜ la poblaci´on converger´a hacia una soluci´on optima ´ del problema. El poder de los Algoritmos Gen´eticos proviene del hecho de que se trata de una t´ecnica robusta, y pueden tratar con ´exito una gran variedad de problemas provenientes de diferentes areas, ´ incluyendo aquellos en los que otros m´etodos encuentran dificultades. Si bien no se garantiza que el Algoritmo Gen´etico encuentre la soluci´on optima ´ del problema, existe evidencia emp´ırica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimizaci´on combinatoria. En el caso de que existan t´ecnicas especializadas para resolver un determinado problema, lo m´as probable es que superen al Algoritmo Gen´etico, tanto en rapidez como en eficacia. El gran campo de aplicaci´on de los Algoritmos Gen´eticos se relaciona con aquellos problemas para los cuales no existen t´ecnicas especializadas. Incluso en el caso en que dichas t´ecnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas hibrid´andolas con los Algoritmos Gen´eticos. La estructura de este cap´ıtulo es como sigue: en la siguiente secci´on se introduce por medio de 1 un ejemplo el denominado Algoritmo Gen´etico Simple, tambi´en conocido como Algoritmo Gen´etico Can´onico, para a continuaci´on, mostrar distintas extensiones y modificaciones del mismo, relativas a los operadores de selecci´on, cruce, mutaci´on y reducci´on, as´ı como a la hibridaci´on del Algoritmo Gen´etico con otros algoritmos de busqueda ´ local, y a diversos modelos de Algoritmos Gen´eticos Distribuidos. En la siguiente secci´on nos preguntamos el motivo por el cual funcionan los Algoritmos Gen´eticos, demostr´andose el teorema de los esquemas, y referenci´andose algunos trabajos te´oricos relacionados con las condiciones suficientes para garantizar la convergencia de dichos algoritmos hacia el optimo ´ global. Finalizamos el cap´ıtulo, mostrando operadores de cruce y mutaci´on espec´ıficos