Algoritmi Metaeuristici per il Multidimensional Multiple-choice Knapsack Problem

The Multidimensional Multiple-Choice Knapsack Problem (MMKP) is an NP-hard combinatorial optimization problem with numerous applications in resource allocation, planning, and decision support systems. The objective is to select exactly one item from each group while maximizing the total profit and satisfying a set of multidimensional resource constraints. This thesis presents the design and implementation of a memetic algorithm for solving the MMKP, developed in Java. The proposed approach combines the exploration capabilities of genetic algorithms with local improvement strategies to effectively navigate the search space. In particular, the initial population is generated using a Greedy Randomized Adaptive Search Procedure (GRASP), designed to produce high-quality and diverse initial solutions. Candidate solutions are evaluated through a penalized fitness function, allowing both feasible and infeasible solutions to be explored during the evolutionary process. The algorithm is evaluated on benchmark instances available in the literature, investigating the influence of the main algorithmic parameters and comparing different strategies for population initialization. The experimental results show that the proposed approach is effective in generating high-quality initial populations and provides a solid foundation for the subsequent evolutionary phases of the memetic algorithm

Il Multidimensional Multiple-Choice Knapsack Problem (MMKP) è un problema di ottimizzazione combinatoria appartenente alla classe NP-hard, con numerose applicazioni in ambiti quali l’allocazione delle risorse, la pianificazione e il supporto alle decisioni. L’obiettivo consiste nel selezionare un elemento da ciascun gruppo massimizzando il profitto complessivo, nel rispetto di un insieme di vincoli multidimensionali sulle risorse disponibili. In questa tesi viene progettato e implementato un algoritmo memetico per la risoluzione del MMKP, sviluppato in linguaggio Java. L’algoritmo combina operatori evolutivi tipici degli algoritmi genetici con procedure euristiche di miglioramento locale. In particolare, la popolazione iniziale viene costruita mediante una procedura GRASP (Greedy Randomized Adaptive Search Procedure), progettata per generare soluzioni iniziali di elevata qualità mantenendo un adeguato livello di diversità. La valutazione delle soluzioni è basata su una funzione di fitness penalizzata, in grado di gestire sia soluzioni ammissibili sia non ammissibili durante il processo evolutivo. L’algoritmo è stato validato utilizzando istanze benchmark presenti in letteratura, analizzando l’influenza dei principali parametri di configurazione e confrontando differenti strategie di inizializzazione della popolazione. I risultati sperimentali evidenziano l’efficacia dell’approccio proposto nella costruzione di popolazioni iniziali di elevata qualità e costituiscono una solida base per l’applicazione delle successive fasi evolutive del memetico.