Dic07062022

Darrera actualitzacióDiv, 01 Jul 2022 11pm

Back Estàs aquí:Inicio Tecnologies físiques Històries d'èxit Christian Blum: “El nostre algorisme híbrid resol problemes d’optimització de la vida real”

Christian Blum: “El nostre algorisme híbrid resol problemes d’optimització de la vida real”

Christian Blum, investigador de l'IIIA-CSIC, ha estat guardonat amb el premi SEIO-Fundación BBVA, pel desenvolupament d'un algorisme híbrid que combina les metaheurístiques  i la investigació operativa (IO) d’una manera innovadora  per resoldre problemes complexos, on hi ha moltes variables i moltes possibles solucions. Es pot aplicar, per exemple, a sectors industrials i educatius.

Christian Blum, investigador de l'IIIA-CSIC, ha estat guardonat amb el premi SEIO-Fundación BBVA.Un estudi realitzat per investigadors de l'Institut d'Investigació en Intel·ligència Artificial (IIIA-CSIC), Universitat de la Concepció, Universitat de Manchester i Universitat del País Basc, ha desenvolupat un nou algorisme general per a l'optimització combinatòria.

Aquesta investigació guardonada ha desenvolupat un algorisme híbrid que combina components algorítmics del camp metaheurístic amb tècniques exactes del camp de la investigació operativa (IO) d’una manera nova.

D’una banda, una metaheurística és un concepte algorítmic general, semblant a un conjunt d’instruccions per a una recepta, per resoldre problemes d’optimització. D’altra banda, IO és una branca de la Matemàtica Aplicada. La innovació d’aquesta investigació s’explica precisament per la hibridació d’ambdues tècniques.

L’objectiu d’aquesta nova tècnica és dissenyar millors motors d’optimització combinatòria per resoldre problemes, cosa clau en molts entorns industrials i educatius.

Un exemple en què això pot ser útil són els problemes per establir rutes de vehicles: imagineu una empresa de logística amb una o més cotxeres per a la seva flota de vehicles i un o més magatzems per a la mercaderia. Cada dia s’ha de lliurar mercaderia als clients en funció de les comandes que hagin fet. Això vol dir que s’han d’assignar lliuraments als vehicles i que s’han de trobar rutes òptimes per tal d’estalviar combustible i temps.

Com que sovint no és possible trobar la millor solució vàlida respecte a la qualitat, les tècniques  metaheurístiques tenen com a objectiu trobar solucions "prou bones" en un temps de càlcul raonable. A més, algunes  comencen amb algunes solucions vàlides i apliquen repetidament petits canvis amb l'objectiu d'obtenir solucions millorades.

Pel que fa a l'optimització, gran part dels esforços en IO s'han dedicat al desenvolupament de tècniques exactes, és a dir, tècniques matemàtiques d'optimització que poden derivar solucions òptimes demostrades.

No obstant això,  a mida que el problema a resoldre es va fent més gran, i en funció de les característiques del problema, aquestes tècniques arriben al límit de la seva capacitat. És en aquest moment quan els investigadors i els professionals solen recórrer a algorismes aproximats com les heurístiques o les metaheurístiques , que es desenvolupen no només en IO sinó també, per exemple, en Intel·ligència Artificial. Poden donar molt bones solucions (encara que no sempre són òptimes) en un temps de càlcul més curt.

Christian Blum (IIIA-CSIC), un dels investigadors guardonats, afirma que “fa uns 20 anys els investigadors van començar a estudiar combinacions o hibridacions d’algorismes de diferents tipus. La tècnica d’optimització per la qual hem rebut el premi SEIO-Fundació BBVA -anomenat CMSA- és un algorisme híbrid entre la metaheurística i les tècniques IO. Té la intenció de combinar el millor de ambdues tècniques  per fer un procés d’optimització més fiable. És just dir que, avui en dia, les tècniques metaheurístiques (híbrides) són d’última generació per a molts problemes d’optimització de la vida real”.

El premi de la Fundació SEIO-BBVA

En guanyar aquest premi, Christian Blum diu que “provoca una enorme satisfacció professional. Com a investigador estàs acostumat al fracàs. Això és bastant natural, perquè sovint entrem en territoris desconeguts i no sabem prèviament com sortiran les coses. Des d’aquest punt de vista, valorem especialment aquelles ocasions en què tenim èxit. El desenvolupament de l'algorisme CMSA és sens dubte un èxit".

Els premis de la Fundació SEIO-BBVA es van crear el 2020 i són els únics premis a nivell nacional dedicats específicament a les contribucions de l’IO i de l’àmbit estadístic. Per aquest motiu, es consideren "entre els premis més importants" d'aquest tipus per a tots els investigadors que treballen en IO i / o estadístiques.

Juntament amb Christian Blum, altres investigadors que han participat en aquesta investigació són Pedro Pinacho (Universitat de la Concepció, Xile), Manuel López-Ibáñez (Universitat de Manchester, Regne Unit) i José A. Lozano (Universitat del País Basc).