La natura, una rica font d’inspiració per la informàtica

El Dr.  Christian Blum del grup de recerca ALBCOM ha estat guardonat amb el IEEE Transactions on Evolutionary Computation Outstanding Paper Award pel seu article "Search bias in ant colony optimization: On the role of competition-balanced systems" Aquest important premi reportarà pel Dr. Blum, un bon reconeixement, una petita compensació econòmica i molta visibilitat dins la comunitat de recerca. Avui estem contents de poder compartir el seu reconeixement i que podem passar una mica de temps preguntant-li sobre el premi i sobre la seva recerca.

Christian Blum porta quatre anys al departament de LSI, per tant, la primera pregunta hauria de ser...
Vaig néixer a Alemanay. Ara bé, he passat els darrers nou anys en diversos llocs d’Europa. Vaig treballar a Londres, a l’Imperial Cancer Research Fund (ICFR). Vaig obtenir el meu doctorat a Brussel·les i ara sóc aquí a Barcelona. Sóc un investigador "Ramon y Cajal" i estic al grup ALBCOM de la Universitat Politècnica de Catalunya (UPC). Vaig rebre el meu Diploma (equivalent a un Master of Science) el 1998 a la Universitat de Kaiserlautern, Alemanya. Després vaig obtenir el doctorat en Ciència Aplicada el 2004 a la Université Libre de Bruxelles, a Bèlgica. La meva tesi versava sobre optimització de colònies de formigues.

Actualment treballo més que res en mètodes metaheurístics per resoldre problemes d'optimització combinatòria com el que apareixen en la gestió de les xarxes de telecomunicacions o en la creació de xarxes ad’hoc.

Formigues computacionals

The IEEE Transactions on Evolutionary Computation

Matemàtiques, computació... i formigues? Em considero un matemàtic aplicat. Podrem dir que hi ha un gran solapament entre les matemàtiques i la computació. En la meva opinió tant les matemàtiques com la informàtica són al mateix temps una eina i un llenguatge per a solucionar problemes. Allò que és molt atractiu de barrejar matemàtiques, ordinadors i formigues és que la natura t’inspira i  en transportes tot el coneixement que n’extreus cap a la tecnologia. Podria dir que desenvolupo algoritmes basant-me en els fenòmens d’intel·ligència col·lectiva que s’anomenen “intel·ligència d’eixam”  (“Swarm intelligence”). L’optimització de colònies de formigues (“Ant colony optimization”, ACO) va començar com a tècnica d’optimització combinatòria als primers anys noranta. El que inspira aquesta tècnica és la conducta de recol·lecció i cerca de les colònies de formigues que realment existeixen a la natura. En el cor d’aquesta conducta col·lectiva es la comunicació indirecta que es dóna entre les formigues gràcies als camins que formen deixant anar feromones químiques, que els hi permet trobar camins molt curts entre el formigues i la font d’alimentació. Aquesta característica dels formiguers de veritat és la que s’explota en els algoritmes ACO per resoldre, per exemple, problemes d’optimització continus o discrets i per gestionar tasques com les de encaminament de paquets en xarxes de comunicacions o balanceig de càrrega en xarxes de telecomunicació (el que fa que els missatges arribin a temps per Internet o que una xarxa no es col·lapsi). Més recentment s’estan utilitzant per xarxes mòbils ad-hoc com les xarxes de sensors. En que se centra la teva recerca? El principal interès de la meva recerca esta en els mètodes de intel·ligència d’eixam aplicats a la optimització, així com en la hibridació de metaheurístiques per a altres tècniques, més clàssiques, d’optimització. Em centro més que res en les tècniques d’optimització de colònies de formigues (ACO) que, com he dit, s’inspiren en el comportament de les formigues per trobar el camí més curt del formiguer al menjar. Pel que fa a aplicacions, el meu interès està en els problemes d’optimització en les telecomunicacions i en la bioinformàtica. Per què uses aquestes tècniques metaheurístiques híbrides? Els éssers humans saben més i més coses. Ens organitzem de manera més complexa. Desenvolupem idees més complexes i millors. Tot això fa que els problemes es facin més i més grans. El nombre de possibilitats augmenta i augmenta. Els mètodes tradicionals de càlcul i l‘organització ja no ens són suficients Las tècniques tradicionals (o “exactes”) són precises. Ara bé, això normalment significa que comporten uns temps de càlcul enormes. D’altra banda, les tècniques metaheurístiques ens poden donar ràpidament una solució aproximada. Combinant ambdues tècniques es pot reduir el temps de càlcul i incrementar la precisió. I la lògica no s’utilitza també per resoldre aquesta mena de problemes? És veritat que hi ha investigadors que utilitzen la lògica per problemes d’scheduling o, en general, d’optimització. De totes maneres, les situacions de les que ells parteixen són una mica diferents de les que partim nosaltres. En general, ells treballen amb moltes condicions restrictives i han de trobar una solució que satisfaci totes les restriccions. Nosaltres no podrien tenir una solució correcta per aquestes situacions, doncs nosaltres afavorim un estil de solució més aproximat. Ara bé, de la mateixa manera que nosaltres combinem tècniques exactes amb metaheuristiques també és veritat que hi ha investigadors basats en lògica que han començat ha combinar metaheurístiques amb lògica. L’encerto si dic que veig una certa relació entre la teva recerca i la Intel·ligència Artificial? I tant! Totes aquestes maneres d’enfocar els problemes tenen estructures comunes. Nosaltres també fem ús d’alguns mètodes clàssics de la Intel·ligència Artificial o Investigació Operativa. Per exemple, els mètodes de Branch & Bound o la Programació Dinàmica.

Què són les  IEEE Transactions on Evolutionary Computation? Les IEEE Transactions on Evolutionary Computation (TEC) és una revista mensual publicada per la Computational Intelligence Society, part de la Computer Society de l’IEEE. Publica articles revisats per parts i d’altres contribucions dins el camp de la computació evolutiva i la computació natural. Està dirigida a investigadors, desenvolupadors, professors i tècniques dins l’àmbit de la Informàtica. Perquè és tan important publicar-hi? Perquè es considera la revista més important d’aquesta àrea. Està situada entre les de més al impacte i les més citades (la número 2 en Informàtica, Teoria i Mètodes i la número 3 en Intel·ligència Artificial), segons el Citation Report del 2007. Essent com és una de les millors revistes i de més impacte, és molt difícil aconseguir veure publicat un article teu. Bé, difícil però possible i ara mateix una realitat per a tu. Perquè penses que els hi va semblar tan bé el teu article? Crec que les tècniques d’optimització basades en intel·ligència d’eixam s’han anat fent cada cop més populars durant la darrera dècada. Es caracteritzen per una manera de treballar completament descentralitzada que imita les conductes dels eixams formats per insectes socials, les bandades d’ocells, o de peixos. L’avantatge principal d’aquestes tècniques respecte a les tradicionals és la seva robustesa i flexibilitat. Aquestes propietat fan a la intel·ligència d’eixam un paradigma de disseny amb molt d’èxit que permet crear bons algoritmes capaços d’enfrontar-se amb problemes més i més complexos. La majoria de les vegades aquests procediments funcionen molt be. Ara be, sempre hi ha unes quantes situacions en que aquestes tècniques no funcionen. El 2005 vaig escriure un article que s’ocupava d’aquestes situacions rares en què no es pot utilitzar aquesta forma de resoldre problemes. S’anomenava Search bias in ant colony optimization: On the role of competition-balanced systems. En la meva opinió, és tan important tenir una teoria potent com saber sota quines condicions es pot utilitzar i sota quines no val la pena. Aquesta és probablement la raó per la que he rebut, dos anys més tard, el premi al millor article. Per cert, què representa aquest premi per a tu? Significa una recompensa econòmica de mil dòlars, el reconeixement de la comunitat científica i força visibilitat. Des d’aquesta perspectiva per on veus que anirà la teva recerca futura? Ara mateix només puc pensar en el futur més immediat. M’agradaria explorar de manera més general les aplicacions de la intel·ligència d’eixam, no només en optimització sinó també en altres tasques com, per exemple, la gestió de xarxes de sensors de gran escala. És una sort, en aquest sentit, que el grup ALBCOM tingui dos projectes europeus centrats en mètodes de sensors i, en general, en artefactes molt petits (a escala “nano”).