Mohammed Mahrach
Comparison between Single and Multi-Objective Evolutionary Algorithms to Solve the Knapsack Problem and the Travelling Salesman Problem
Mahrach, Mohammed; Miranda, Gara; Le�n, Coromoto; Segredo, Eduardo
Authors
Gara Miranda
Coromoto Le�n
Eduardo Segredo
Abstract
One of the main components of most modern Multi-Objective Evolutionary Algorithms (MOEAs) is to maintain a proper diversity within a population in order to avoid the premature convergence problem. Due to this implicit feature that most MOEAs share, their application for Single-Objective Optimization (SO) might be helpful, and provides a promising field of research. Some common approaches to this topic are based on adding extra—and generally artificial—objectives to the problem formulation. However, when applying MOEAs to implicit Multi-Objective Optimization Problems (MOPs), it is not common to analyze how effective said approaches are in relation to optimizing each objective separately. In this paper, we present a comparative study between MOEAs and Single-Objective Evolutionary Algorithms (SOEAs) when optimizing every objective in a MOP, considering here the bi-objective case. For the study, we focus on two well-known and widely studied optimization problems: the Knapsack Problem (KNP) and the Travelling Salesman Problem (TSP). The experimental study considers three MOEAs and two SOEAs. Each SOEA is applied independently for each optimization objective, such that the optimized values obtained for each objective can be compared to the multi-objective solutions achieved by the MOEAs. MOEAs, however, allow optimizing two objectives at once, since the resulting Pareto fronts can be used to analyze the endpoints, i.e., the point optimizing objective 1 and the point optimizing objective 2. The experimental results show that, although MOEAs have to deal with several objectives simultaneously, they can compete with SOEAs, especially when dealing with strongly correlated or large instances.
Journal Article Type | Article |
---|---|
Acceptance Date | Nov 9, 2020 |
Online Publication Date | Nov 12, 2020 |
Publication Date | Nov 12, 2020 |
Deposit Date | Jan 28, 2021 |
Publicly Available Date | Jan 28, 2021 |
Journal | Mathematics |
Publisher | MDPI |
Peer Reviewed | Peer Reviewed |
Volume | 8 |
Issue | 11 |
Article Number | 2018 |
DOI | https://doi.org/10.3390/math8112018 |
Keywords | multi-objective optimization; single-objective optimization; evolutionary algorithm; knapsack problem; travelling salesman problem |
Public URL | http://researchrepository.napier.ac.uk/Output/2701518 |
Files
Comparison Between Single And Multi-Objective Evolutionary Algorithms To Solve The Knapsack Problem And The Travelling Salesman Problem
(664 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
You might also like
Analysing the performance of migrating birds optimisation approaches for large scale continuous problems
(2016)
Presentation / Conference Contribution
Hybridisation of Evolutionary Algorithms through hyper-heuristics for global continuous optimisation
(2016)
Presentation / Conference Contribution
Hybrid parameter control approach applied to a diversity-based multi-objective Memetic Algorithm for frequency assignment problems
(2016)
Presentation / Conference Contribution
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search