Analista

Algoritmos Genéticos

ABSTRACT
El presente trabajo hace una breve introducción a los conceptos básicos referidos a los Algoritmos Genéticos, y luego explica, por medio de una aplicación, un ejemplo denominado Traveling Salesman Problem – TSP (problema del viajante de comercio), en el cual se aplica la metodología desarrollada.

ALGORITMOS GENÉTICOS
LOS ORÍGENES La evolución se produce comoresultado de dos procesos primarios: la selección natural y la reproducción sexual. La primera determina qué miembros de la población sobrevivirán hasta reproducirse; la segunda garantiza la mezcla y combinación de sus genes entre la descendencia. En la fusión del óvulo y el espermatozoide, los cromosomas homologados se estiran y adosan uno al otro, y luego se entrecruzan en zonas intermedias,intercambiando así material genético. Esta es la teoría de la evolución, especies naturales que van evolucionando para adaptarse al medio que las rodea y aquellos individuos que tengan más éxito en tal adaptación tendrán mejor probabilidad de sobrevivir hasta la edad adulta y probablemente un número mayor de descendientes, por lo tanto, mayores probabilidades de que sus genes sean propagados a lolargo de sucesivas generaciones. La combinación de características de los padres bien adaptados, en un descendiente, puede producir muchas veces un nuevo individuo mucho mejor adaptado que cualquiera de sus padres a las características de su medio ambiente. Este proceso no debe verse en ningún momento como un proceso determinista, sino como un proceso con la fuerte componente estocástica. Es decir,si un individuo se adapta al entorno, lo más que se puede afirmar es que ese individuo tendrá mayor probabilidad de conservar sus genes en la siguiente generación que sus congéneres. Pero solo es una probabilidad, no es un hecho absolutamente seguro. Siempre existirá la posibilidad de que a pesar de estar muy dotado por alguna razón no consiga reproducirse. Pero en cuanto a la especie como unconjunto o población, si puede afirmarse que irá adaptándose al medio. La idea surgió cuando el profesor J. H. Holland consciente de la importancia de la selección natural introdujo la idea de los Algoritmos Genéticos en los años sesenta y al final de esta década desarrolló una técnica que permitió incorporarla en un programa de computadora. Su principal objetivo era lograr que las computadorasaprendieran por sí mismas. A la técnica inventada por Holland se le llamó inicialmente Planes Reproductivos pero se hizo popular bajo el nombre de Algoritmos Genéticos. ¿QUÉ SON LOS ALGORÍTMOS GENÉTICOS? Una definición bastante completa de un Algoritmo Genético es la propuesta por Jhon Kosa: “Es un algoritmo matemático que transforma un conjunto de objetos matemáticos con respecto al tiempo usandooperaciones 2

Metodología de la Investigación

Algoritmos Genéticos

modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas de entre las que destaca la recombinación sexual y la mutación”. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres (letras o números) delongitud fija que se ajusta al modelo de las cadenas de cromosomas, y se asocian con una cierta función matemática que refleja su aptitud. Los Algoritmos Genéticos utilizan una analogía directa del fenómeno de evolución en la naturaleza. Trabajan con una población de individuos, donde cada uno representa una posible solución a un problema dado. A cada individuo se le asigna una puntuación deadaptación, dependiendo de que tan buena fue la respuesta al problema. A los más adaptados se les da la oportunidad de reproducirse mediante cruzamientos con otros individuos de la población, produciendo descendientes con características de ambos padres. Los miembros menos adaptados poseen pocas probabilidades de que sean seleccionados para la reproducción, y desaparecen. El evaluar esta adaptación...