A Differential Evolution Algorithm for Generic Combinatorial Optimization Problems

Abstract

Combinatorial optimization problems (COPs) are well-known NP-hard realistic ones. Due to the drawbacks of existing approaches, many researchers proposed different evolutionary algorithms (EAs) for solving them. Differential evolution (DE) is primarily used to solve continuous-based optimization problems and has been considered unsuitable for solving many permutation-based combinatorial ones. However, several efforts to design an efficient discrete DE algorithm have been made in recent years. In this thesis, to efficiently solve COPs, an algorithmic framework involving DE and multiple methodologies is introduced. Firstly, a new best-matched value (BMV) mapping method consisting of a new heuristic for converting solutions with continuous variables to ones with discrete/binary variables and directing the mapped solution towards optimality is developed. Secondly, a complete DE incorporating the BMV and problem-specific components for solving knapsack problems (KPs) is proposed. Also, a new fitness evaluation for calculating and repairing knapsack solutions is introduced. Then, an improved complete DE that uses 1) an improved BMV, 2) a k-means clustering repairing method, 3) an ensemble of mutation and 4) two well-known local searches is developed to solve discrete traveling salesman problems (TSPs). Finally, motivated by the promising performances of the proposed versions of DE, a discrete-binary DE (DBDE) algorithm that uses the good search features of the BMV and most effective introduced components to solve the complex traveling thief problem (TTP) which consists of a TSP and KP is proposed. All the proposed DE versions are tested on three sets of well-known COPs, namely, KPs, TSPs and TTPs. It is found that: 1) the BMV improves the solution quality of the traditional DE by 45.04% and saves 66.56% of the times required to solve them; 2) using extra functions in DE to solve KPs leads to define new better solutions and 98.38% faster performances; 3) adopting a repairing method and ensemble of mutations improves the quality of solutions; 4) the DBDE algorithm exhibits a promising performance for solving generic COPs (TTPs). Finally, as the experimental results discussed in this thesis confirm the suitability of the DBDE algorithm for tackling generic COPs, it is expected that it will significantly advance knowledge of DE by extending the research work previously undertaken on it in the continuous domain to developing DEs that can solve complex COPs.