Skip to main content

Research Repository

Advanced Search

Comparison between Single and Multi-Objective Evolutionary Algorithms to Solve the Knapsack Problem and the Travelling Salesman Problem


Mohammed Mahrach

Gara Miranda


Eduardo Segredo


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.


Mahrach, M., Miranda, G., León, C., & Segredo, E. (2020). Comparison between Single and Multi-Objective Evolutionary Algorithms to Solve the Knapsack Problem and the Travelling Salesman Problem. Mathematics, 8(11), Article 2018.

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
Keywords multi-objective optimization; single-objective optimization; evolutionary algorithm; knapsack problem; travelling salesman problem
Public URL


Comparison Between Single And Multi-Objective Evolutionary Algorithms To Solve The Knapsack Problem And The Travelling Salesman Problem (664 Kb)

Publisher Licence URL

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

Downloadable Citations