In this article, we propose a novel and effective evolutionary algorithm for the challenging combinatorial optimization problem known as Multidimensional Two-Way Number Partitioning Problem (MDTWNPP). Since the MDTWNPP has been proven to be NP-hard, in the recent years, it has been increasingly addressed by means of meta-heuristic approaches. Nevertheless, previous proposals in literature do not make full use of critical problem information that may improve the effectiveness of the search. Here, we bridge this gap by designing an improved Memetic Algebraic Differential Evolution (iMADEB) algorithm that incorporates critical information about the problem. In particular, iMADEB evolves a population of candidate local optimal solutions by adopting three key design concepts: a novel non-redundant bit-string representation which maps population individuals one-to-one to MDTWNPP solutions, a smoother local search operator purposely designed for the MDTWNPP landscapes, and a self-adaptive algebraic differential mutation scheme built on the basis of the Lévy flight concept which automatically regulates the exploration-exploitation trade-off of the search. Computational experiments have been conducted on a widely accepted benchmark suite for the MDTWNPP with a twofold purpose: analyzing the robustness of iMADEB and compare its effectiveness with respect to the state-of-the-art approaches to date for the MDTWNPP. The experimental results provide important indications about iMADEB robustness and, most importantly, clearly show that iMADEB is the new state-of-the-art algorithm for the MDTWNPP.

An improved memetic algebraic differential evolution for solving the multidimensional two-way number partitioning problem

Santucci, Valentino
;
2021

Abstract

In this article, we propose a novel and effective evolutionary algorithm for the challenging combinatorial optimization problem known as Multidimensional Two-Way Number Partitioning Problem (MDTWNPP). Since the MDTWNPP has been proven to be NP-hard, in the recent years, it has been increasingly addressed by means of meta-heuristic approaches. Nevertheless, previous proposals in literature do not make full use of critical problem information that may improve the effectiveness of the search. Here, we bridge this gap by designing an improved Memetic Algebraic Differential Evolution (iMADEB) algorithm that incorporates critical information about the problem. In particular, iMADEB evolves a population of candidate local optimal solutions by adopting three key design concepts: a novel non-redundant bit-string representation which maps population individuals one-to-one to MDTWNPP solutions, a smoother local search operator purposely designed for the MDTWNPP landscapes, and a self-adaptive algebraic differential mutation scheme built on the basis of the Lévy flight concept which automatically regulates the exploration-exploitation trade-off of the search. Computational experiments have been conducted on a widely accepted benchmark suite for the MDTWNPP with a twofold purpose: analyzing the robustness of iMADEB and compare its effectiveness with respect to the state-of-the-art approaches to date for the MDTWNPP. The experimental results provide important indications about iMADEB robustness and, most importantly, clearly show that iMADEB is the new state-of-the-art algorithm for the MDTWNPP.
Algebraic Differential Evolution, Combinatorial optimization, Memetic Algorithm, Multidimensional Two-Way Number Partitioning
File in questo prodotto:
File Dimensione Formato  
eswa2021.pdf

non disponibili

Descrizione: Versione editoriale
Tipologia: Versione Editoriale (PDF)
Licenza: NON PUBBLICO - Accesso chiuso
Dimensione 746.24 kB
Formato Adobe PDF
746.24 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
_ESWA_2020__Number_Partitioning.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 450.83 kB
Formato Adobe PDF
450.83 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12071/25765
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact