Da hormiguería aos computadores

2001/02/04 Roa Zubia, Guillermo - Elhuyar Zientzia

• Patenteak/Asmakizunak
• Multimedia
• Ingurumena

Este tipo de problemas xorden non só nas formigoneiras, senón tamén na macromunda humana. Como se pode facer o camiño máis curto dunha maneira eficaz? Uns científicos deixan de pensar e céntranse nas formigas reais. Atoparon una boa solución.

Sen coñecer o camiño máis directo, todas as formigas parten á vez. Cada individuo, guiado pola súa intuición, avanzará desde onde queira. Desta forma traballaranse todos e cada un dos camiños, incluíndo o máis adecuado e o peor. A estratexia das formigas é marcar a mellor vía para que a partir dun momento todos os transportistas utilícena. Nas cruces emítense feromonas (compostos químicos) paira marcar o camiño. En principio marcarán todos os camiños, claro. Como saber cal é o mellor? Os que foron polo camiño máis curto collen o azucre e fan o camiño a casa máis rápido que os demais. Este camiño será, por tanto, o primeiro que marque dúas veces. Os que veñen de atrás só teñen que seguir o camiño máis marcado paira acelerar o desprazamento. Os primeiros "exploradores" atoparon a solución ao problema da volta. Non é mala idea.

A voltas no laboratorio

Paira analizar o método, os científicos levaron os formigueiros ao laboratorio e realizaron numerosos ensaios por diferentes vías artificiais. Con todo, o método ás veces falla. E é que paira conseguir un éxito seguro, o camiño máis longo ten que ser polo menos o dobre que o resto. Si son similares, as formigas non sempre decidirán ben. Ademais, si por casualidade queda marcado o camiño máis longo, toda a colonia aceptarao.

Os científicos inventaron outro tipo de probas. Ás formigas escóndeselles o camiño máis curto ata que terminan as primeiras exploracións. Neste caso as formigas marcan o camiño máis longo e considérano definitivo. Aínda que os científicos presentan un camiño máis curto, as formigas cambian o seu comportamento.

Pero hai outra cousa que hai que ter en conta. Os sinais químicos emitidas non duran paira sempre, xa que as feromonas se evaporan. Cando se produce una rápida evaporación, a colonia debe actualizar frecuentemente o camiño cara á comida. Nestes casos é difícil ter marcados continuos longos e aos poucos elíxese o camiño máis curto. Esta proba é una estratexia moi útil na natureza, xa que a aparencia do terreo de xogo pode ter moitos cambios.

Formigas teóricas

A aplicación directa da estratexia das colonias de formigas é un problema coñecido do vendedor. O vendedor debe vender o seu produto en varias cidades. Nada máis entrar no coche ten que organizar ben a viaxe, que cidade vai visitar ao principio, onde irá e como completará a viaxe sen pasar dúas veces pola mesma cidade. A última condición da viaxe é que debe finalizar na cidade de inicio.

As formigas do computador deseñan senllas viaxes coas feromonas cibernéticas vertidas nas cruces tomados. Paira completar a viaxe, as formigas tenden a elixir a dirección máis marcada nas cruces. Desta forma descártanse oportunidades aos poucos efectivas. Ademais, o computador elimina as feromonas deixadas nas cruces para que os esforzos non se fortalezan por casualidade.

Hai programas informáticos que cando se empeza a detectar una solución cambian as condicións iniciais e fan máis sesións. Isto deu lugar a métodos moi rápidos e competitivos no estudo deste tipo de problemas. De feito, estes programas tamén son útiles en sistemas en continua evolución. Aínda que sexa dunha solución despreciable, todas as direccións das cruces teñen polo menos un pequeno nivel de feromona. Esta é a capacidade de adaptación da metodoloxía.

O método das formigas ten importantes aplicacións na vida real. Por exemplo, na rexión de Suíza en italiano utilízase paira indicar a procedencia dos camións que transportan gasolina e, en xeral, paira tratar problemas relacionados cos medios de transporte.

Outros trucos de formigas

Existen moitos problemas reais coas características adecuadas paira utilizar a procura do camiño máis curto. Ademais, pódense traducir á linguaxe dos computadores. Con todo, nalgúns casos esta metodoloxía falla, sobre todo cando as opcións son similares. A base deste tipo de métodos é a procura estatística. Por exemplo, no método visto utilízase a estatística de concentracións de feromonas.

Pero na vida real xorden imprevistos. Repasemos as formigas que están a traer comida. Atoparon o camiño máis curto e están a traballar de forma eficaz. Pero, de súpeto, comeza una tormenta e a choiva converte o camiño máis curto en perigoso. Cada pinga de auga caída do ceo pode matar un par de formigas. Os que se atopan na zona sen protección hanse estancado e hai una gran confusión. As formigas traseiras han empezado a empuxar e alguén está a traballar no camiño inicialmente descartado.

Co paso do tempo, o camiño máis longo é protexido, polo que as feromonas proliferaron e a colonia optou por este camiño. Adaptación da estratexia. Una vez alí, a maioría das formigas dirixiranse ao camiño máis curto. Non ten a mesma aparencia que os problemas do tráfico?

O principal recurso é a información que cada individuo traslada ás cruces da rede deste sistema de encaminamiento. A experiencia de cada un é pequena, pero é reflexo da tendencia xeral. Aínda que no caso do tráfico, é imprescindible ter en conta a evaporación das feromonas. Pola contra, existe o risco de que a información quede obsoleta. Este tipo de estratexias resultan de gran utilidade paira o control do tráfico urbano. Tamén se utilizan algoritmos que consideran que a información contida nas cruces pode estar deteriorada. Ademais do tráfico, son sistemas moi adecuados paira xestionar o transporte de información nas redes informáticas.

Publicado no suplemento Natura de Gara