Algoritmos Genéticos

Algoritmos Gen ́eticos

20 de Abril de 2012

“En lugar de envidiar la naturaleza debemos emularla”. John Henry Holland.

Hablar de algoritmos gen ́eticos es hablar, inevitablemente, de Charles Darwin. La teor ́ıa de la evoluci ́on de Darwin habla sobre la seleccio ́n natural, que establece el mecanismo del cambio evolutivo. El grado de adaptacio ́n al medio ambiente que tienen las distintas especies que habitan nuestro planeta se ha logrado gracias a un proceso de selecci ́on natural. En esto penso ́ John Hollan junto a sus colegas de la universidad de M ́ıchigan. Buscaba abstraer y explicar rigurosamente el proceso adaptativo de los sistemas naturales, y disen ̃ar sistemas artificiales que retuvieran los mecanismos ma ́s importantes de los sistemas naturales.

Holland estableci ́o los principios ba ́sicos de estos algoritmos en 1975, y de ah ́ı en mas se han estado desarrollando hasta el d ́ıa de hoy de una forma exponencial. La gran gama de posibilidades que trae consigo los algoritmos gen ́eticos han dado pie al desarrollo de innumerables aplicaciones en los dis- tintos campos de las ciencias.

Los algoritmos gen ́eticos usan una analog ́ıa directa con el comportamiento natural. Trabajan con una poblaci ́on de individuos, los cuales representan una solucio ́n factible a un problema dado. A cada individuo se le asigna un valor, relacionado con la bondad de dicha solucio ́n. Cuanto mayor sea la adaptacio ́n 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 producira ́ nuevos individuos, los cuales son descendientes de los anteriores, es decir, comparten algunas caracter ́ısticas de sus padres. Mientras menor sea la adaptacio ́n de un individuo, menor sera ́ la probabilidad de que este sea seleccionado para la

1

reproduccio ́n, y por tanto, que su material gen ́etico se propague en sucesivas generaciones. Adema ́s, la informacio ́n gen ́etica va sufriendo cambios a trav ́es del tiempo, los cuales en algunos casos son beneficiosos para la especie y en otros perjudiciales. A este u ́ltimo se le conoce como mutaci ́on.

Los primeros ejemplos de lo que hoy llamamos algoritmos gen ́eticos, apa- recen a finales de los 50 y principios de los 60, programados por bi ́ologos que necesitaban expl ́ıcitamente realizar modelos de la evoluci ́on natural. A ninguno de ellos se les ocurrio que esta estrategia podr ́ıa aplicarse de manera mas general a problemas de otra ́ındole. Fue John Henry Holland en los an ̃os 60 quien en su estudio sobre sistemas adaptativos establecio las bases para desarrollos posteriores.

En 1962, Holland ley ́o un libro titulado “La teor ́ıa gen ́etica de la selecci ́on natural”, de R.A. Fisher, y con esto comenzo ́ a descubrir los medios para llevar a cabo su propo ́sito de comprencion de la naturaleza.

Mientras, en la Universidad de Michigan, Holland impartia un curso lla- mado “Teor ́ıa de los sistemas adaptativos”, y con la participaci ́on activa de sus estudiantes, creo ́ las ideas que mas tarde se convertir ́ıan en los algorit- mos gen ́eticos. Por tanto, cuando Holland se enfrento a los algoritmos, sus objetivos fueron: imitar los procesos adaptativos de los sistemas naturales y disen ̃ar sistemas artificiales que retengan los mecanismos importantes de los sistemas naturales.

Unos 15 an ̃os despu ́es, David Goldber conocio a Holland, y se convirtio ́ en su estudiante. Hoy en dia es el m ́aximo exponente de los algoritmos gen ́eticos. Ya vamos viendo que, ba ́sicamente, los algoritmos gen ́eticos son utiliza- dos como un motor de bu ́squeda basado en la seleccio ́n y gen ́etica natural. Se combina la supervivencia de los m ́as compatibles con una estructura de in- formacio ́n ya aleatorizada. La idea es explotar eficientemente la informaci ́on histo ́rica para especular sobre nuevos puntos de bu ́squeda, esperando el ma ́s o ́ptimo de los resultados. Un punto importante a tener en cuenta, es que si el algoritmo a sido bien disen ̃ado, la poblacio ́n va a converger a la solucio ́n

o ́ptima del problema.

La estructura de los algoritmos gen ́eticos la podemos dividir en siete par-

tes, las cuales son: individuos, poblaci ́on inicial, funcio ́n de ajuste, seleccio ́n, cruce, mutacio ́n y elitismo.

Los individuos, como mencionamos previamente, representan una posi- ble solucio ́n del problema. Esta soluci ́on debe ser codificada en un elemento que la represente, el cual es denominado cromosoma. Cuando el espacio de soluciones factibles puede ser representado por una permutaci ́on, la codifica-

2

cio ́n ma ́s adecuada es en base 10.

La poblaci ́on inicial de individuos puede ser generada a trav ́es de un

proceso aleatorio o bien mediante alguna heur ́ıstica. Con una heur ́ıstica existe el riesgo de considerar un subconjunto del espacio de soluciones, es decir, se perder ́ıan posibles soluciones y no tendr ́ıamos la seguridad de obtener la m ́as o ́ptima. Sin embargo, podr ́ıamos obtener soluciones en un tiempo menor. Quedara ́ a juicio del desarrollador si desea efectividad ante rapidez.

La funci ́on de ajuste corresponde a una forma de medir qu ́e tan bien un individuo se adapta al medio, o bien, cu ́al es el valor de dicho individuo. La funcio ́n de ajuste debe tener en consideraci ́on dos aspectos: la calidad de la funci ́on objetivo y la infactibilidad del individuo. La infactibilidad del individuo debe ser penalizada en la funci ́on de ajuste proporcionalmente al grado de infactibilidad del mismo.

Luego de conocer la aptitud de cada individuo, se procede, mediante la selecci ́on, a elegir los individuos que sera ́n cruzados. Los individuos con mejor aptitud tienen mayor probabilidad de ser seleccionados. La t ́ecnica m ́as utilizada para la seleccio ́n de individuos es la de Rueda de Ruleta, esquema en el cual cada individuo tiene una probabilidad de ser seleccionado proporcional a la bondad de su ajuste.

El cruce consiste en el intercambio de material gen ́etico entre dos indivi- duos (a veces m ́as). El cruce es el principal operador gen ́etico, hasta el punto que se puede decir que no es un algoritmo gen ́etico si no tiene cruce, y, sin embargo, puede serlo perfectamente sin mutacio ́n, segu ́n descubrio ́ Holland.

Para aplicar el cruce, se escogen aleatoriamente dos miembros de la pobla- cio ́n. No pasa nada si se emparejan dos descendientes de los mismos padres, de hecho, ello garantiza la perpetuacio ́n de un individuo. Sin embargo, si esto sucede muy a menudo, puede crear algunos problemas.

Este intercambio gen ́etico se puede llevar a cabo

...