A Hybrid Differential Evolution Algorithm for Binary CSPs

Abstract:

A novel hybrid elements exchange/electromagnetism meta-heuristic differential evolution algorithm, named EEMDE, is proposed in this paper, avoiding the premature convergence of original DE algorithm. A metric to measure the Simplification of force exerted on a point is defined as the mutation rate F in the EEMDE, which is used to get an adaptive adjustment of F. EEMDE may produce slight disturbance on the original vector for enhancing the exploring capacity and avoid the DE to the "uphill" in the wrong direction forward. Experiments demonstrate that the convergence of EEMDE is faster than DE and simulations based on some CSPs express the effectiveness, efficiency and robustness of it.

• Periodical: Advanced Materials Research (Volumes 108-111)
• Pages: 328-334
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.108-111.328
• Online since: May 2010
• Authors: Hong Jie Fu
• Keywords: CSPs, Differential Evolution (DE), Electromagnetism Mechanism, Elements Exchange

References

[1] R. Storn and K. Price: Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces, Technical report, International Computer Science Institute, Berkley, (1995).

[2] K. V. Pric, R. Storn, J. Lampinen: Differential Evolution: A Practical Approach to Global Optimization, London: Springer-Verlag, UK, (2005).

[3] T. Gong and A. L. Tuson: Differential Evolution of BinaryEncoding, Soft Computing in Industrial Application, vol. ASC 39, (2007), pp.251-262.

[4] L. B. Zhang, C. G. Zhou, M. Ma asn C. T. Sun: A multi-objective differential evolution algorithm based on max-min distance density. Journal of Computer Research and Development, (2007), 44(1): 177−184 (in Chinese with English abstract).

DOI: 10.1360/crad20070125

[5] G.Q. Zhao, X.Y. Peng and N. Sun: A modified differential evolution algorithm with hybrid optimization strategy, ACTA Electronica Sinica, (2006), 34(12): 2402−2405 (in Chinese with English abstract).

[6] N. Noman and H. Iba: Accelerating differential evolution using an adaptive local search, IEEE Trans. on Evolutionary Computation, (2008), 12(1): 107−125.

DOI: 10.1109/tevc.2007.895272

[7] B. Qian, L. Wang, and R. Hu et al: A hybrid differential evolution method for permutation flowshop scheduling, Int J Adv Manuf Technol, (2007).

[8] C. N. Andreas, L. O. Sotiris: Differential evolution for sequencing and scheduling optimization, J Heuristics, vol. 12, (2006), pp.395-411.

[9] E. Marchiori: Combining constraint processing and genetic algorithms for constraint satisfaction problems, Proc. of 7th International Conference on Genetic Algorithms, (1997), pp.330-337.

[10] P. J. M. van Laarhoven, E. H. L. Aarts, and J. K. Lenstra: Job shop scheduling by simulated annealing, Operations Research, vol. 40, (1992), pp.113-125.

DOI: 10.1287/opre.40.1.113

[11] L. Schoofs, B. Naudts: Swarm intelligence on the binary constraint satisfaction problem, Proc. of the IEEE Congress on Evolutionary Computation, Honolulu, Hawaii, USA. (2002), pp.1444-1449.

DOI: 10.1109/cec.2002.1004455

[12] Q. Y. Yang, J. G. Sun, J. Y. Zhang et al: A Hybrid Discrete Particle Swarm Algorithm for Hard Binary CSPs, Proc. of the 2nd International Conference on Natural Computation (ICNC'06) and the 3rd International Conference on Fuzzy Systems and Knowledge Discovery, Xi'an, China, LNCS 4222, (2006).

DOI: 10.1007/11881223_24

[13] C. Solnon: Ants can solve Constraint Satisfaction Problems, IEEETEC, vol. 6(4), (2002), pp.347-357.

DOI: 10.1109/tevc.2002.802449

[14] M-C Riff Rojas: Using the knowledge of the constraint network to design an evolutionary algorithm that solves csp, Proc. of the 3rd IEEE Conference on Evolutionary Computation, IEEE Computer Society Press, (1996), pp.279-284.

DOI: 10.1109/icec.1996.542375

[15] S. L. Birbil and S. C. Fang: An electromagnetism-like mechanism for global optimization, Journal of Global Optimization , (2003) , 25 (3) : 263 - 282.

[16] Debels , Reyck , Leus , et al: A hybrid scatter search/electromagnetism meta-heuristic for project scheduling, European J our2 nal of Operational Research , (2006) , 169 (2) : 638 - 653.

DOI: 10.1016/j.ejor.2004.08.020

[17] Craenen: Solving Constraint Satisfaction Problems with Evolutionary Algorithms, Ph.D. Dissertation, Vrige University, (2005).

[18] B. M. Smith: Phase transition and the mushy region in constraintsatisfaction problems, Proc. of the 11th European Conference onArtificial Intelligence, Wiley, (1994), pp.100-104.

[19] G. Onwubolu and D. Davendra: Scheduling flow shops using differential evolution algorithm, European Journal of Operational Research, vol. 171, (2006), pp.674-692.

DOI: 10.1016/j.ejor.2004.08.043