Algoritmos xenéticos en busca da solución máis adecuada

2008/01/01 Galarraga Aiestaran, Ana - Elhuyar Zientzia Iturria: Elhuyar aldizkaria

• Eboluzioa
• Matematika

Na natureza, a poboación inicialmente existente cambia co tempo. De xeración en xeración, algúns factores fan que os individuos que peor se adaptan desaparezan, mentres que os que mellor se adaptan perviven. Por tanto, dentro da poboación aumenta a proporción de mellores. Con todo, é posible que algún que non parece tan bo continúe por ter una estratexia diferente ou por azar. E podería cruzarse cos demais, como se cruzan os demais. Por tanto, é posible que a característica do individuo, supostamente mala, apareza na próxima xeración noutros membros.

De cando en vez aparece outra variable: a mutación. Aínda que non é moi frecuente, inflúe nas características dos membros da poboación. Debido ás cruces, mutacións e axentes que apostan polos mellores, una vez transcorrido o tempo, a poboación está formada polos membros mellor adaptados á contorna.

Así o explicou, máis ou menos, Darwin na teoría da evolución das especies, e é o que fan os algoritmos xenéticos. A poboación inicial está constituída polas posibles solucións a un problema. Estas posibles solucións selecciónanse aleatoriamente e denomínanse cromosomas. Os diferentes aspectos de cada cromosoma denomínanse xenes.

En caso de ser candidatos, aplícaselles una función que mide a súa idoneidade. Como é normal, a maioría dos candidatos son inadecuados, pero outros, dalgunha maneira, funcionan e mantéñense.

Os candidatos que avanzaron multiplícanse e crúzanse. Por tanto, na seguinte xeración, algúns teñen varias copias e outras se equivocaron. Ademais, uns poucos non son exactamente iguais aos anteriores: mutáronse, é dicir, modificáronse aleatoriamente algún xene.

A xeración resultante é diferente á anterior e mídese a idoneidade destes candidatos. Así, os candidatos que non son mellores que os anteriores se descartan, os que quedan son mellores solucións que os iniciais. Eles reprodúcense e prodúcense cruces e mesmo mutacións. Avalíanse os novos candidatos e vólvese a elixir aos mellores, o proceso repítese cada cen ou mil veces. A poboación resultante está formada por moi boas solucións ao problema.

Números, letras e árbores

Paira empezar a traballar os algoritmos xenéticos é necesario codificar as posibles solucións do problema para que o computador poida procesalo. Una opción é codificar en cadeas binarias: Son cadeas formadas por 1 e 0 e o díxito que hai en cada lugar da cadea representa o valor dun aspecto da resolución.

Outra forma de codificar é mediante cadeas de números enteiros ou decimais. Como no caso anterior, o número que hai en cada lugar indica o valor dun aspecto concreto da resolución. Obtense maior precisión e complexidade que co código binario, xa que limita menos que usar dous números. Doutra banda, os números pódense substituír por letras paira codificar os candidatos.

Con este tres métodos é moi fácil definir as operacións que realizarán ao azar cruces e mutacións entre os candidatos; é fácil pór un 1 onde hai un 0 ou viceversa; engadir ou quitar un valor a un número; ou substituír una letra por outra.

Ademais, existen outras formas de codificar, como a que se realiza con árbores. Os datos represéntanse ramificados e os cambios realízanse cambiando o valor dos parches ou substituíndo algunhas ramas da árbore por outras.

Selección e modificación

Codificar dunha maneira ou outra, programar a elección dos individuos a copiar paira a seguinte xeración. A selección pódese realizar de diversas formas e normalmente utilízanse varias delas á vez. Una delas é a selección elitista, é dicir, a selección dos mellores de cada xeración. Outra forma depende da capacidade: a maior capacidade, máis posibilidades de elección.

Ademais, paira garantir a diversidade da poboación, pódese utilizar una roda de ruleta: a cada candidato correspóndelle una parte da ruleta; a maior capacidade, maior parte adáptase ao candidato. Virando a roda, os que teñen una parte grande teñen máis posibilidades de ser elixidos, pero poida que adáptese a un candidato con pouca capacidade paira ser elixido paira a seguinte xeración. Isto garante que a seguinte xeración non sexa demasiado igualitaria.

Outra forma de garantir isto é mediante a realización de grupos por nivel de competencia e a elección dos mellores de cada grupo, de forma que o mellor do grupo de baixa capacidade avanzaría. Os equipos tamén se poden facer ao azar e logo pódense obrigar a competir entre eles, os vencedores pasan á seguinte xeración.

Existen outros métodos de selección: selección graduada, xerárquica... En calquera caso, o obxectivo é que os candidatos da seguinte xeración sexan de media mellores que os anteriores. Ademais, aos candidatos seleccionados paira a seguinte xeración realízanselles algúns cambios aleatorios coa esperanza de que aparezan mellores individuos.

Existen dúas formas de realizar os cambios: mutación e cruzamento. A mutación é cambiar un aspecto concreto, un xene. O cruzamento consiste en trocar parte do código por outro candidato. O "neno" así formado ten en común as características dos dous "pais". Trátase, por tanto, dunha recombinación entre os cromosomas paternos e maternos na reprodución sexual.

A favor e en contra

Mediante a selección, a mutación e o cruzamento, de xeración en xeración, os algoritmos xenéticos van achegándose á solución do problema. En moitos casos, o algoritmo xenético non será suficiente paira soltar o problema, pero pode dar solucións razoablemente boas, e aplicando os métodos habituais a esta poboación final pódese obter a mellor solución.

Una das vantaxes dos algoritmos xenéticos é que son “cegos”, é dicir, que non saben nada do problema que teñen que resolver. Poida que máis que una vantaxe pareza una desvantaxe, pero é moi boa, xa que non rexeita desde o principio a ningún candidato con mal aspecto. Ademais, o cruceiro e a mutación crean sorprendentes solucións. Dalgunha maneira, os prexuízos non afectan aos algoritmos xenéticos, só lles importa avanzar.

Ademais, traballan en paralelo, é dicir, por diferentes vías á vez. A maioría dos algoritmos traballan en serie e só poden avanzar nunha dirección en cada ocasión. Cando se dan conta de que tomaron o camiño equivocado, teñen que abandonar todo o traballo e empezar de novo. Con todo, os algoritmos xenéticos non teñen este problema e son especialmente eficaces na resolución de problemas con moitas solucións posibles.

Teñen máis vantaxes pero tamén algúns inconvenientes. A primeira é a dificultade de escribir a definición do problema. A codificación dos candidatos non é sinxela e ás veces custa moito escribir a función que mide a capacidade. O tamaño da poboación, a frecuencia de mutacións e cruces, así como o tipo e a forza da selección, son factores moi importantes nos algoritmos xenéticos, que se non se deseñan ben, non avanzan.

Apps

A pesar das súas limitacións, utilízanse paira resolver problemas como acústica, enxeñaría aeroespacial, astronomía e astrofísica, química, mercado financeiro, xogos, geofísica, enxeñaría de materiais, matemáticas, bioloxía molecular, telecomunicacións, etc.

Por exemplo, en 2002 investigadores da Universidade Kobe de Xapón utilizaron algoritmos xenéticos paira deseñar una sala de música. Partiron dunha sala en forma de caixa de zapatos e definiron os parámetros que debía ter paira conseguir a mellor acústica. O algoritmo deu dous resultados, ambos en forma de host, que parecen ter una acústica espectacular. Segundo os investigadores, son como o Grosser Musikvereinsaal de Viena, o mellor do mundo.

Pola súa banda, a NASA utilizounos no deseño de envases, pero tamén no estudo de ananas brancas e no deseño de horarios. De feito, os algoritmos xenéticos son moi eficaces paira a realización de horarios tanto en empresas, aeroportos e escolas.

Nas escolas, por exemplo, é un problema o horario adecuado. Requírese un profesor por aula e un profesor non pode estar en dúas aulas simultaneamente. Por suposto, cada profesor ten que dar o seu tema e, talvez, algúns temas mellor que se dean a unha hora e non a outra (non convén pór a última hora as matemáticas, a física, etc.). Ademais, hai que ter en conta as preferencias ou necesidades do profesorado. Dado que hai que ter en conta tantos factores, nos grandes centros é moi difícil conseguir un bo programa horario. Pois ben, os algoritmos xenéticos son perfectos.

Os expertos non teñen dúbida de que, a pesar de que son relativamente novos (os primeiros apareceron na década de 1960), tiveron un rápido desenvolvemento e, segundo a matemática Mª Teresa Igrexas, "non hai que detelos".