A multi-population algorithm for multi-objective knapsack problem
| Autor: | Imen Ben Mansour, Matthieu Basseur, Frédéric Saubion |
|---|---|
| Přispěvatelé: | École Nationale des Sciences de l'Informatique [Manouba] (ENSI), Université de la Manouba [Tunisie] (UMA), Laboratoire d'Etudes et de Recherche en Informatique d'Angers (LERIA), Université d'Angers (UA) |
| Rok vydání: | 2018 |
| Předmět: |
Computer science
media_common.quotation_subject Population 0211 other engineering and technologies 02 engineering and technology Knapsack 0202 electrical engineering electronic engineering information engineering [INFO]Computer Science [cs] Quality (business) Local search (optimization) education Cooperative framework media_common education.field_of_study Multi-objective 021103 operations research business.industry Process (computing) Pareto principle Local search Multi-population Knapsack problem Multi population 020201 artificial intelligence & image processing Focus (optics) business Algorithm Software |
| Zdroj: | Applied Soft Computing Applied Soft Computing, Elsevier, 2018, 70, pp.814-825. ⟨10.1016/j.asoc.2018.06.024⟩ |
| ISSN: | 1568-4946 |
| Popis: | International audience; Local search algorithms constitute a growing area of interest to approximate the Pareto sets of multi-objective combinatorial problem instances. In this study, we focus on the multi-objective knapsack problem and its optimization thanks to a multi-population based cooperative framework. The proposed approach, Wϵ-CMOLS, uses a multi-objective local search algorithm based on quality indicator (IBMOLS), initially presented by Basseur and Burke in 2007, and integrates it into a cooperative model. The idea is to optimize the overall quality of a Pareto set approximation by evolving several sub-populations in parallel, each population executing a different configuration of IBMOLS. The algorithm uses a weighted version of the epsilon quality indicator by means of different weight vectors. The populations cooperate through sharing a non-dominated archive, which stores the best compromises found during the optimization process, and which is used to re-initialize regularly each sub-population. Wϵ-CMOLS is compared with state-of-the-art algorithms such as IBEA, NSGA-II and SPEA2. Experiments highlight that the use of a cooperative model as well as a weighted indicator to guide the search toward different directions, can lead to interesting results for the multi-objective knapsack problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect