Abstract
The vast majority of the practical problems that can be formulated as the optimisation problems are NP-Hard. It is therefore crucial finding efficiently at least a suboptimal solution for them as exact solutions may not be possible to compute in reasonable time with today’s computer. Therefore, the main objective of this thesis is to unlock the potential of Metaheuristics for NP-Hard problems by developing robust strategies tailored to real life challenges, obtaining practical solutions, and contributing practical insights for algorithm selection (or novel ones) and configuration. More precisely, the methodology involved the development and application of high-level problem-solving strategies, i.e., Metaheuristics or heuristically driven reinforcement learning. These strategies, whether single or population-based, were tailored to ad- dress specific challenges in problems (single or multi objective optimization ones) like VEHICLE ROUTING, OPEN SHOP SCHEDULING, SYSTEM-ON-CHIP SCHEDULINGor HYBRID BUILT IN SELF TEST SCHEDULING, as well as some problems from graph theory such as MAX-CLIQUE and MINIMUM DOMINATING SET problems, and the SUBSET SUM PROBLEM. The validation against benchmarks ensured the correctness of the approach. Moreover, the development of new robust Metaheuristics for solving large-scale instances of optimization problems is an important step to tackle NP- Hardness from practical point of view.
In fact, general findings are very promising, in many cases the proposed approaches managed to get better results than the currently best known and in a few cases the obtained results were optimal. More explicitly, for the CAPACITATED VE- HICLE ROUTING PROBLEM the multi objective Strength Pareto Evolutionary Algorithm (SPEA2) hybridized with hill climbing yielded a ≃ 40% improvement over main steam method using Solomon’s benchmark. For the OPEN SHOP SCHEDULING PROB- LEM bio inspired algorithms, Ant Colony optimization, Cuckoo Search, and Genetic Algorithm, obtained in ≃67% of the cases the currently best solutions applied to the Taillard benchmark. A more sophisticated solution for solving the SYSTEM ON CHIP (SOC) SCHEDULING PROBLEM (adapted also to a hierarchical version) was based on SPEA2 scheduling combined with simple heuristics such as Simulating Annealing and Best Fit Decreasing. The applied solution to ITC’02 benchmark suite for SOC had a ≃80% improvement within an acceptable timing. A new Cuckoo Search method to solve for the POWER CONSTRAINT TEST SCHEDULING IN CONCURRENT HYBRID
BIST MODE WITHOUT PREEMPTION for the d5018 benchmark schedule was found promising. As for NP-Hard graph problems, namely the MAXIMUM CIQUE PROBLEM (Max-CP), and MINIMUM DOMINATING SET (Min-DS) and its variants, the work re- lied on a relatively fast Hybrid Cuckoo Search with Hill Climbing algorithm and a Heuristically Driven (Hill Climbing) Reinforcement Learning respectively. The graph problem relied on the DIMACS suite benchmark. For the Max-CP, the algorithm reached ≃54% the best known values for this benchmark. For the Min-DS, the novel Heuristically Driven RL ≃ 30% of the cases were optimal solutions based on the theory of finding the lower bound values. Also, for large sparse graph DIMACS 10 benchmark, combining a greedy method with preprocessing was very promising. Lastly, the SUBSET SUM PROBLEM (SSP) was tackled using a novel Heuristically Driven (HC) RL more precisely HC with restart using proposed hard benchmark instances which yielded preliminary good results.
In this direction, one can conclude that when deployed to a specific problem, an experience was gathered regarding the choice of the algorithm (including new ones or adapted ones: hybridization choices, initialization methods, evolutionary operators, . . . ), the simplicity of the configuration (tuning parameters), and the performance – quality of solution and speed of convergence.
| Date of Award | 25 Jan 2024 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Janka Chlebikova (Supervisor) & Mohamed Bader-El-Den (Supervisor) |