A Differential Evolution Algorithm for Generic Combinatorial Optimization Problems
type: CreativeWork
description: 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 repairin…
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 repairin…
author: Ali, Ismail
language: EN
keywords: Combinatorial Optimization Problems, Differential Evolution, Mapping Method
license: https://purl.org/coar/access_right/c_abf2
license: https://creativecommons.org/licenses/by-nc-nd/3.0/au/
date published: 2020
date modified: 2026-07-24T05:31:47Z
provider: University of New South Wales
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: UNSW, Sydney

PropertyValue
property ID: Handle
value: http://hdl.handle.net/1959.4/70151

PropertyValue
property ID: DOI
value: 10.26190/unsworks/3968