A Novel Binary Differential Evolution for Discrete Optimization

Abstract:

Differential evolution （DE） is an evolutionary algorithm that is based on the individual differential reconstruction idea. It is proposed by Stom and Price in 1997, and is very suitable to solve optimization problem over continuous spaces. First of all, with the introduction of concepts of differential operator （DO）, etc., the concise description of DE is given and the analysis of its main features is advanced. For solving discrete optimization problem using DE, a new operator, mapping operator, in the new algorithm was used to ensure the original mutation operator still effective. Then a new S operator, with sigmoid function, was used to keep the result of the mutation operator falls in the interval [0, 1]. The algorithm not only has the advantages of DE, but also is very suitable to solve discrete optimization problems. Calculations of 0/1 knapsack problem show that algorithm has better convergence capability and stability.

• Periodical: Key Engineering Materials (Volumes 439-440)
• Pages: 1493-1498
• DOI: https://doi.org/10.4028/www.scientific.net/KEM.439-440.1493
• Online since: June 2010
• Authors: Guo Ping Hou, Xuan Ma
• Keywords: Binary Differential Evolution, Discrete Optimization, Inverse Mapping Operator

References

[1] Storn, R. and K. Price, Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal Global Optimization, 1997, 11, pp.241-354.

[2] Liu B , Wang L , Jin Y H , et al, Designing neural networks using hybrid particle swarm optimization, Lecture Notes in Computer Science, Berlin : Springer , 2005 : pp.391-397.

DOI: 10.1007/11427391_62

[3] Rogalsky T., Derksen R.W. and Kocabiyik, Differential evolution in aerodynamic optimization, Proc. Of 46th annual conf. of Canadian Aeronautics and Space Institute, 1999, pp.29-36.

[4] Das S. and Konar A., Design of two dimensional IIR filters with modern search heuristics: a comparative study, International Journalof Computational Intelligence and Applications, 2006, 6(3): pp.329-355.

DOI: 10.1142/s1469026806001848

[5] Wang F-S and Jang H-J, Parameter estimation of a bio-reaction model by hybrid differential evolution, in Proc. Of the IEEE congress on Evolutionary Computation 2000, pp.410-417, IEEE, Press, USA (2000).

[6] Omran M., Engelbrecht, and Konar A. Differential evolution methods for unsupervised image classification, Proc . Seventh Congress on Evolutionary Computation. IEEE Press. (2005).

DOI: 10.1109/cec.2005.1554795

[7] Versterstrom J, Thomsen R. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithm on numerical benchmark problems , Evolutionary Computation, CEC2004. Portland OR: IEEE press, 2004, 2: 1980-(1987).

DOI: 10.1109/cec.2004.1331139

[8] Koziel, S and Michalewicz, Z., Evolutionary Algorithms, Homomorphous Mappings, and Constrained Parameter Optimization, Evolutionary Computation, Vol. 7, No. 1, 1999, pp.19-44.

DOI: 10.1162/evco.1999.7.1.19

[9] Kiefer J, On large deviations of the empirical of vector chance variables and a law of the iterated logarithm,. Pacific J Math, 1961, 11 (3) , pp.649-660.

DOI: 10.2140/pjm.1961.11.649

[10] Zhang Ling and Zhang Bo, Good point set based genetic algorithm,. Chinese Journal of Computers, 2001, 24(9), pp.917-922.

[11] Gao Tian and WangMengguang, The research for the reductive dimension and replacive variable algorithm of special restrict 0-1 ILP,. Systems Engineering Theory Methodology Applicaions, 2002, 11(2), pp.125-130.