Logic Gate-based Evolutionary Algorithm for the multidimensional knapsack problem-wireless sensor network application

¹ Electrical Engineering Department, National Engineering School of Monastir, Monastir, Tunisia.
ayetferjani@gmail.com; Noureddine.Liouane@enim.rnu.tn
² École Centrale de Lille, BP 48, 59651 Villeneuve d’Ascq cedex, France.
pierre.borne@ec-lille.fr

Received: 11 May 2015
Accepted: 30 August 2016

Abstract

Evolutionary algorithms (EAs) are predominantly employed to find solutions for continuous optimization problems. As EAs are initially presented for continuous spaces, research on extending EAs to find solutions for binary spaces is in growing concern. In this paper, a logic gate-based evolutionary algorithm (LGEA) for solving some combinatorial optimization problems (COPs) is introduced. The proposed LGEA has the following features. First, it employs the logic operation to generate the trial population. Thereby, LGEA replaces common space transformation rules and classic recombination and mutation methods. Second, it is based on exploiting a variety of logic gates to search for the best solution. The variety among these logic tools will naturally lead to promote diversity in the population and improve global search abilities. The LGEA presents thus a new technique to combine the logic gates into the procedure of generating offspring in an evolutionary context. To judge the performance of the algorithm, we have solved the NP-hard multidimensional knapsack problem as well as a well-known engineering optimization problem, task allocation for wireless sensor network. Experimental results show that the proposed LGEA is promising.