A Metaheuristic Search Algorithm based on Sampling and Clustering

Els problemes d'optimització esdevenen més complicats i extensos, la parametrització esdevé complexa, resultant en una tasca difícil que requereix quantitats significatives de temps i recursos. En aquest article proposem un algorisme de cerca heurística que anomenem MCSA (Algoritme de Cerca per Agrupament Montecarlo), el qual es basa en l'agrupament Montecarlo, i una estratègia d'agrupament que implica dues tècniques. El nostre objectiu és aplicar la MCSA, un mètode inherentment estocàstic, a problemes d'optimització. Per avaluar-ne el rendiment, hem fet servir funcions d'optimització de referència clàssiques. A més, hem aprofitat el conjunt de referències CEC2017 per avaluar l'algoritme exhaustivament, destacant el paper fonamental de la fase d'Exploració en la nostra metodologia. Posteriorment, hem ampliat la nostra metodologia per a resoldre un problema combinatori pràctic, el Problema del Maletí. Aquest problema NP-Hard té aplicacions significatives al món real en assignació de recursos, programació, planificació, logística i més. Les nostres contribucions es basen en la parametrització del Problema del Maletí perquè s'ajusti als paràmetres de l'MCSA per a l'ajust d'indicadors de referència i aconseguir solucions d'alta qualitat que superin el 9ль% en comparació amb mètodes exhaustius com ara els de ramificació i unió