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

Ferjani, Ayet Allah; Liouane, Noureddine; Borne, Pierre

RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 4-5, pp. 825-843.

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.

Classification : 90C27
Mots clés : Evolutionary algorithm, logic gate, multidimensional knapsack problem, task allocation, wireless sensor network

M.A.K. Azad, A.M.A.C. Rocha and E.M.G.P. Fernandes, Solving multidimensional 0–1 knapsack problem with an artificial fish swarm algorithm. In Proc. 12th Int. Conf. Comput. Sci. and Its Applications (ICCSA 2012), Salvador de Bahia, Brazil. Springer Berlin Heidelberg (2012) 72–86.

J.C. Bansal and K. Deep, A modified binary particle swarm optimization for knapsack problems. Appl. Math. Comput. 218 (2012) 11042–11061. | DOI | MR | Zbl

J.E. Beasley, Or-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41 (1990) 1069–1072. | DOI

M. Chih, C.-J. Lin, M.-S. Chern and T.-Y. Ou, Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem. Appl. Math. Model. 38 (2014) 1338–1350. | DOI | MR | Zbl

L.-Y. Chuang, C.-H. Yang and J.-C. Li, Chaotic maps based on binary particle swarm optimization for feature selection. Appl. Soft Comput. 11 (2011) 239–248. | DOI

M. Dorigo and G.D. Caro, Ant colony optimization: a new meta-heuristic. In Proc. 1999, Congr. Evolutionary Computation (CEC 99), Washington, USA (1999).

R. Eberhart and J. Kennedy, A new optimizer using particle swarm theory. In Proc. of the Sixth Int. Simp. on Micro Machine and Human Science (MHS ’95) (1995) 39–43.

A. Fréville, The multidimensional 0–1 knapsack problem: An overview. European J. Oper. Res. 155 (2004) 1–21. | DOI | MR | Zbl

J. Holland, Genetic algorithms. Sci. Amer. 267 (1992) 66–72. | DOI

Y. Jin, J. Jin, A. Gluhak, K. Moessner and M. Palaniswami, An intelligent task allocation scheme for multihop wireless networks. IEEE Trans. Parallel Distrib. Syst. 23 (2012) 444–451. | DOI

D. Karaboga and B. Basturk, Artificial bee colony (ABC) optimization algorithm for solving constrained optimization. In Proc. of the 12th Int. Fuzzy Syst. Assoc. World Congr. on Foundations of Fuzzy Logic and Soft Computing (IFSA 2007), Cancun, Mexico. Springer Berlin Heidelberg (2007) 789–798. | MR

J. Kennedy and R.C. Eberhart, A discrete binary version of the particle swarm algorithm. In IEEE Int. Conf. Syst., Man, and Cybernetics. Florida, USA (1997) 4104–4108.

M.S. Kiran and M. Gündüz, Xor-based artificial bee colony algorithm for binary optimization. Turkish J. Electr. Eng. Comput. Sci. 21 (2013) 2307–2328. | DOI

H. Li, Y.-C. Jiao, L. Zhang and Z.-W. Gu, Genetic algorithm based on the orthogonal design for multidimensional knapsack problems. In Proc. of Second Int. Conf. Natural Computation (ICNC 2006), Xi’an, China. Springer Berlin Heidelberg (2006) 696–705.

A. Marandi, F. Afshinmanesh, M. Shahabadi and F. Bahrami, Boolean particle swarm optimization and its application to the design of a dual-band dual-polarized planar antenna. In 2006 IEEE Conf. on Evolutionary Computation (CEC 2006), Vancouver, Canada. IEEE Comput. Intell. Soc. (2006) 3212–3218

H. Pirkul, A heuristic solution procedure for the multiconstraint zero-one knapsack problem. Naval Res. Logist. 34 (1987) 161–172. | DOI | Zbl

A.K. Qin, V.L. Huang and P.N. Suganthan, Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans. Evol. Comput. 13 (2009) 398–417. | DOI

M. Sakawa and K. Kato, Genetic algorithms with double strings for 0–1 programming problems. Eur. J. Oper. Res. 144 (2003) 581–597. | DOI | MR | Zbl

R. Shams and F.H. Khan, Solving wireless network scheduling problem by genetic algorithm. Glob. Enginners Technologists Rev. 2 (2012) 10–13.

D. Stefanoiu, P. Borne, D. Popescu, F.G. Filip and A. ElKamel, Optimization in Engineering Sciences: Approximate and Metaheuristic Methods. John Wiley (2014). | Zbl

R. Storn and K. Price, Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11 (1997) 341–359. | DOI | MR | Zbl

L. Wang, S.-Y. Wang and Y. Xu, An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem. Expert Syst. Appl. 39 (2012) 5593–5599. | DOI

L. Wang, X.-L. Zheng and S.-Y. Wang, A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem. Knowledge-Based Syst. 48 (2013) 17–23. | DOI

J. Yang, H. Zhang, Y. Ling, C. Pan and W. Sun, Task allocation for wireless sensor network using modified binary particle swarm optimization. IEEE Sensors J. 14 (2014) 882–892. | DOI