Differential Evolution Using Opposite Point for Global Numerical Optimization

Affiliation(s)

School of Computer and Information, Anqing Teachers College, Anqing, China.

College of Information, Mechanical and Electrical Engineering, Shanghai Normal University, Shanghai, China..

School of Computer and Information, Anqing Teachers College, Anqing, China.

College of Information, Mechanical and Electrical Engineering, Shanghai Normal University, Shanghai, China..

ABSTRACT

The Differential Evolution (DE) algorithm is arguably one of the most powerful stochastic optimization algorithms, which has been widely applied in various fields. Global numerical optimization is a very important and extremely dif-ficult task in optimization domain, and it is also a great need for many practical applications. This paper proposes an opposition-based DE algorithm for global numerical optimization, which is called GNO2DE. In GNO2DE, firstly, the opposite point method is employed to utilize the existing search space to improve the convergence speed. Secondly, two candidate DE strategies “DE/rand/1/bin” and “DE/current to best/2/bin” are randomly chosen to make the most of their respective advantages to enhance the search ability. In order to reduce the number of control parameters, this algorithm uses an adaptive crossover rate dynamically tuned during the evolutionary process. Finally, it is validated on a set of benchmark test functions for global numerical optimization. Compared with several existing algorithms, the performance of GNO2DE is superior to or not worse than that of these algorithms in terms of final accuracy, convergence speed, and robustness. In addition, we also especially compare the opposition-based DE algorithm with the DE algorithm without using the opposite point method, and the DE algorithm using “DE/rand/1/bin” or “DE/current to best/2/bin”, respectively.

The Differential Evolution (DE) algorithm is arguably one of the most powerful stochastic optimization algorithms, which has been widely applied in various fields. Global numerical optimization is a very important and extremely dif-ficult task in optimization domain, and it is also a great need for many practical applications. This paper proposes an opposition-based DE algorithm for global numerical optimization, which is called GNO2DE. In GNO2DE, firstly, the opposite point method is employed to utilize the existing search space to improve the convergence speed. Secondly, two candidate DE strategies “DE/rand/1/bin” and “DE/current to best/2/bin” are randomly chosen to make the most of their respective advantages to enhance the search ability. In order to reduce the number of control parameters, this algorithm uses an adaptive crossover rate dynamically tuned during the evolutionary process. Finally, it is validated on a set of benchmark test functions for global numerical optimization. Compared with several existing algorithms, the performance of GNO2DE is superior to or not worse than that of these algorithms in terms of final accuracy, convergence speed, and robustness. In addition, we also especially compare the opposition-based DE algorithm with the DE algorithm without using the opposite point method, and the DE algorithm using “DE/rand/1/bin” or “DE/current to best/2/bin”, respectively.

Cite this paper

Y. Ao and H. Chi, "Differential Evolution Using Opposite Point for Global Numerical Optimization,"*Journal of Intelligent Learning Systems and Applications*, Vol. 4 No. 1, 2012, pp. 1-19. doi: 10.4236/jilsa.2012.41001.

Y. Ao and H. Chi, "Differential Evolution Using Opposite Point for Global Numerical Optimization,"

References

[1] V. Cutello, G. Narzisi, G. Nicosia and M. Pavone, “An Immunological Algorithm for Global Numerical Optimization,” Artificial Evolution: 7th International Conference, Evolution Artificielle, Lecture Notes in Computer Science Vol. 3871, 2006, pp. 284-295. doi:10.1007/11740698_25

[2] W. Gong, Z. Cai and L. Jiang, “Enhancing the Performance of Differential Evolution Using Orthogonal Design Method,” Applied Mathematics and Computation, Vol. 206, No. 1, 2008, pp. 56-69. doi:10.1016/j.amc.2008.08.053

[3] R. Storn and K. Price, “Differential Evolution—A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces,” Journal of Global Optimization, Vol. 11, No. 4, 1997, pp. 341-359. doi:10.1023/A:1008202821328

[4] J. Sun, Q. Zhang and E. P. K. Tsang, “DE/EDA: A New Evolutionary Algorithm for Global Optimization,” Information Sciences, Vol. 169, No. 3-4, 2005, pp. 249-262.

[5] M. M. Ali, C. Storey and A. Torn, “Application of Some Recent Stochastic Global Optimization Algorithms to Practical Problems,” TUCS Technical Report No. 47, Turku Centre for Computer Science, Turku, 1996.

[6] H. P. Schwefel, “Numerical Optimization of Computer Models,” John Wiley & Sons, Chichester, 1981.

[7] J. H. Holland, “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, 1975.

[8] I. Rechenberg, “Evolution Strategy: Optimization of Technical Systems by Means of Biological Evolution,” Fromman-Holzboog, Stuttgart, 1973.

[9] J. R. Koza, “Genetic Programming: On the Programming of Computers by Means of Natural Selection,” The MIT Press, Cambridge, 1992.

[10] D. B. Fogel, “Applying Evolutionary Programming to Selected Traveling Salesman Problems,” Cybernetics and Systems, Vol. 24, No. 1, 1993, pp. 27-36. doi:10.1080/01969729308961697

[11] K. E. Parsopoulos and M. N. Vrahatis, “Recent Approaches to Global Optimization Problems through Particle Swarm Optimization,” Natural Computing, Vol. 1, No. 2-3, 2002, pp. 235-306. doi:10.1023/A:1016568309421

[12] J. Kennedy and R. C. Eberhart, “Particle Swarm Optimization,” Proceedings of the 1995 IEEE International Conference on Neural Networks, Vol. 4, Perth, 27 November-1 December 1995, pp. 1942-1948. doi:10.1109/ICNN.1995.488968

[13] D. Karabo?a and S. ?kdem, “A Simple and Global Optimization Algorithm for Engineering Problems: Differential Evolution Algorithm,” Turk Journal of Electrical Engineering, Vol. 12, No. 1, 2004, pp. 53-60.

[14] J. Vesterstrom and R. Thomsen, “A Comparative Study of Differential Evolution, Particle Swarm Optimization, and Evolutionary Algorithms on Numerical Benchmark Problems,” 2004 IEEE Congress on Evolutionary Computation, Vol. 2, Portland, 19-23 June 2004, pp. 19801987.

[15] J. J. Liang, A. K. Qin, P. N. Suganthan and S. Baskar, “Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multi-Modal Functions,” IEEE Transactions on Evolutionary Computation, Vol. 10, No. 3, 2006, pp. 281-295. doi:10.1109/TEVC.2005.857610

[16] R. Storn and K. Price, “Differential Evolution—A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces,” Technical Report TR-95-012, International Computer Science Institute, Berkeley, 1995.

[17] K. Price, R. Storn and J. Lampinen, “Differential Evolution: A Practical Approach to Global Optimization,” Springer-Verlag, Berlin, 2005.

[18] J. Brest, S. Greiner, B. Boskovic, M. Mernik and V. Zumer, “Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems,” IEEE Transactions on Evolutionary Computation, Vol. 10, No. 6, 2006, pp. 646-657. doi:10.1109/TEVC.2006.872133

[19] A. K. Qin and P. N. Suganthan, “Self-Adaptive Differential Evolution Algorithm for Numerical Optimization,” Proceedings of the 2005 IEEE Congress on Evolutionary Computation, Vol. 2, 2005, pp. 1785-1791. doi:10.1109/CEC.2005.1554904

[20] S. Das, A. Abraham, U. K. Chakraborty and A. Konar, “Differential Evolution Using a Neighborhood-Based Mutation Operator,” IEEE Transactions on Evolutionary Computation, Vol. 13, No. 3, 2009, pp. 526-553. doi:10.1109/TEVC.2008.2009457

[21] S. Rahnamayan and G. G. Wang, “Solving Large Scale Optimization Problems by Opposition-Based Differential Evolution (ODE),” WSEAS Transactions on Computers, Vol. 7, No. 10, 2008, pp. 1792-1804.

[22] S. Rahnamayan, H. R. Tizhoosh and M. M. A. Salama, “Opposition-Based Differential Evolution,” IEEE Transactions on Evolutionary Computation, Vol. 12, No. 1, 2008, pp. 64-79. doi:10.1109/TEVC.2007.894200

[23] S. Rahnamayan, H. R. Tizhoosh and M. M. A. Salama, “Opposition versus Randomness in Soft Computing Techniques,” Elsevier Journal on Applied Soft Computing, Vol. 8, No. 2, 2008, pp. 906-918. doi:10.1016/j.asoc.2007.07.010

[24] H. R. Tizhoosh, “Opposition-Based Reinforcement Learning,” Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 10, No. 4, 2006, pp. 578585.

[25] H. A. Abbass, R. Sarker and C. Newton, “PDE: A Paretofrontier Differential Evolution Approach for Multi-Objective Optimization Problems,” 2001 IEEE Congress on Evolutionary Computation, Vol. 2, Seoul, 27-30 May 2001, pp. 971978.

[26] M. Ali, M. Pant and V. P. Singh, “Two Modified Differential Evolution Algorithms and Their Applications to Engineering Design Problems,” World Journal of Modelling and Simulation, Vol. 6, No. 1, 2010, pp.72-80.

[27] Z. Y. Yang, K. Tang and X. Yao, “Self-Adaptive Differential Evolution with Neighborhood Search,” 2008 Congress on Evolutionary Computation, Hong Kong, 1-6 June 2008, pp. 1110-1116.

[28] Z. Michalewicz, “Genetic Algorithms + Data Structures = Evolution Programs,” 3rd Edition, Springer, Berlin, 1996.

[29] K. Zielinski, P. Weitkemper, R. Laur and K.-D. Kammeyer, “Examination of Stopping Criteria for Differential Evolution Based on a Power Allocation Problem,” Pro ceedings of the 10th International Conference on Optimization of Electrical and Electronic Equipment, Vol. 3, Brasov, 18-19 May 2006, pp. 149-156.

[30] Y. Ao and H. Chi, “An Adaptive Differential Evolution Algorithm to Solve Constrained Optimization Problems in Engineering Design,” Engineering, Vol. 2, No. 1, 2010, pp. 65-77. doi:10.4236/eng.2010.21009

[31] C. Dai, W. Chen, Y. Song and Y. Zhu, “Seeker Optimization Algorithm: A Novel Stochastic Search Algorithm for Global Numerical Optimization,” Journal of Systems Engineering and Electronics, Vol. 21, No. 2, 2010, pp. 300311.

[32] X. Yao, Y. Liu and G. Lin, “Evolutionary Programming Made Faster,” IEEE Transactions on Evolutionary Computation, Vol. 3, No. 2, 1999, pp. 82-102. doi:10.1109/4235.771163

[33] A.-R. Hedar and M. Fukushima, “Directed Evolutionary Programming: Towards an Improved Performance of Evolutionary Programming,” 2006 IEEE Congress on Evolutionary Computation, Vancouver, 11 September 2006, pp. 1521-1528.

[1] V. Cutello, G. Narzisi, G. Nicosia and M. Pavone, “An Immunological Algorithm for Global Numerical Optimization,” Artificial Evolution: 7th International Conference, Evolution Artificielle, Lecture Notes in Computer Science Vol. 3871, 2006, pp. 284-295. doi:10.1007/11740698_25

[2] W. Gong, Z. Cai and L. Jiang, “Enhancing the Performance of Differential Evolution Using Orthogonal Design Method,” Applied Mathematics and Computation, Vol. 206, No. 1, 2008, pp. 56-69. doi:10.1016/j.amc.2008.08.053

[3] R. Storn and K. Price, “Differential Evolution—A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces,” Journal of Global Optimization, Vol. 11, No. 4, 1997, pp. 341-359. doi:10.1023/A:1008202821328

[4] J. Sun, Q. Zhang and E. P. K. Tsang, “DE/EDA: A New Evolutionary Algorithm for Global Optimization,” Information Sciences, Vol. 169, No. 3-4, 2005, pp. 249-262.

[5] M. M. Ali, C. Storey and A. Torn, “Application of Some Recent Stochastic Global Optimization Algorithms to Practical Problems,” TUCS Technical Report No. 47, Turku Centre for Computer Science, Turku, 1996.

[6] H. P. Schwefel, “Numerical Optimization of Computer Models,” John Wiley & Sons, Chichester, 1981.

[7] J. H. Holland, “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, 1975.

[8] I. Rechenberg, “Evolution Strategy: Optimization of Technical Systems by Means of Biological Evolution,” Fromman-Holzboog, Stuttgart, 1973.

[9] J. R. Koza, “Genetic Programming: On the Programming of Computers by Means of Natural Selection,” The MIT Press, Cambridge, 1992.

[10] D. B. Fogel, “Applying Evolutionary Programming to Selected Traveling Salesman Problems,” Cybernetics and Systems, Vol. 24, No. 1, 1993, pp. 27-36. doi:10.1080/01969729308961697

[11] K. E. Parsopoulos and M. N. Vrahatis, “Recent Approaches to Global Optimization Problems through Particle Swarm Optimization,” Natural Computing, Vol. 1, No. 2-3, 2002, pp. 235-306. doi:10.1023/A:1016568309421

[12] J. Kennedy and R. C. Eberhart, “Particle Swarm Optimization,” Proceedings of the 1995 IEEE International Conference on Neural Networks, Vol. 4, Perth, 27 November-1 December 1995, pp. 1942-1948. doi:10.1109/ICNN.1995.488968

[13] D. Karabo?a and S. ?kdem, “A Simple and Global Optimization Algorithm for Engineering Problems: Differential Evolution Algorithm,” Turk Journal of Electrical Engineering, Vol. 12, No. 1, 2004, pp. 53-60.

[14] J. Vesterstrom and R. Thomsen, “A Comparative Study of Differential Evolution, Particle Swarm Optimization, and Evolutionary Algorithms on Numerical Benchmark Problems,” 2004 IEEE Congress on Evolutionary Computation, Vol. 2, Portland, 19-23 June 2004, pp. 19801987.

[15] J. J. Liang, A. K. Qin, P. N. Suganthan and S. Baskar, “Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multi-Modal Functions,” IEEE Transactions on Evolutionary Computation, Vol. 10, No. 3, 2006, pp. 281-295. doi:10.1109/TEVC.2005.857610

[16] R. Storn and K. Price, “Differential Evolution—A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces,” Technical Report TR-95-012, International Computer Science Institute, Berkeley, 1995.

[17] K. Price, R. Storn and J. Lampinen, “Differential Evolution: A Practical Approach to Global Optimization,” Springer-Verlag, Berlin, 2005.

[18] J. Brest, S. Greiner, B. Boskovic, M. Mernik and V. Zumer, “Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems,” IEEE Transactions on Evolutionary Computation, Vol. 10, No. 6, 2006, pp. 646-657. doi:10.1109/TEVC.2006.872133

[19] A. K. Qin and P. N. Suganthan, “Self-Adaptive Differential Evolution Algorithm for Numerical Optimization,” Proceedings of the 2005 IEEE Congress on Evolutionary Computation, Vol. 2, 2005, pp. 1785-1791. doi:10.1109/CEC.2005.1554904

[20] S. Das, A. Abraham, U. K. Chakraborty and A. Konar, “Differential Evolution Using a Neighborhood-Based Mutation Operator,” IEEE Transactions on Evolutionary Computation, Vol. 13, No. 3, 2009, pp. 526-553. doi:10.1109/TEVC.2008.2009457

[21] S. Rahnamayan and G. G. Wang, “Solving Large Scale Optimization Problems by Opposition-Based Differential Evolution (ODE),” WSEAS Transactions on Computers, Vol. 7, No. 10, 2008, pp. 1792-1804.

[22] S. Rahnamayan, H. R. Tizhoosh and M. M. A. Salama, “Opposition-Based Differential Evolution,” IEEE Transactions on Evolutionary Computation, Vol. 12, No. 1, 2008, pp. 64-79. doi:10.1109/TEVC.2007.894200

[23] S. Rahnamayan, H. R. Tizhoosh and M. M. A. Salama, “Opposition versus Randomness in Soft Computing Techniques,” Elsevier Journal on Applied Soft Computing, Vol. 8, No. 2, 2008, pp. 906-918. doi:10.1016/j.asoc.2007.07.010

[24] H. R. Tizhoosh, “Opposition-Based Reinforcement Learning,” Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 10, No. 4, 2006, pp. 578585.

[25] H. A. Abbass, R. Sarker and C. Newton, “PDE: A Paretofrontier Differential Evolution Approach for Multi-Objective Optimization Problems,” 2001 IEEE Congress on Evolutionary Computation, Vol. 2, Seoul, 27-30 May 2001, pp. 971978.

[26] M. Ali, M. Pant and V. P. Singh, “Two Modified Differential Evolution Algorithms and Their Applications to Engineering Design Problems,” World Journal of Modelling and Simulation, Vol. 6, No. 1, 2010, pp.72-80.

[27] Z. Y. Yang, K. Tang and X. Yao, “Self-Adaptive Differential Evolution with Neighborhood Search,” 2008 Congress on Evolutionary Computation, Hong Kong, 1-6 June 2008, pp. 1110-1116.

[28] Z. Michalewicz, “Genetic Algorithms + Data Structures = Evolution Programs,” 3rd Edition, Springer, Berlin, 1996.

[29] K. Zielinski, P. Weitkemper, R. Laur and K.-D. Kammeyer, “Examination of Stopping Criteria for Differential Evolution Based on a Power Allocation Problem,” Pro ceedings of the 10th International Conference on Optimization of Electrical and Electronic Equipment, Vol. 3, Brasov, 18-19 May 2006, pp. 149-156.

[30] Y. Ao and H. Chi, “An Adaptive Differential Evolution Algorithm to Solve Constrained Optimization Problems in Engineering Design,” Engineering, Vol. 2, No. 1, 2010, pp. 65-77. doi:10.4236/eng.2010.21009

[31] C. Dai, W. Chen, Y. Song and Y. Zhu, “Seeker Optimization Algorithm: A Novel Stochastic Search Algorithm for Global Numerical Optimization,” Journal of Systems Engineering and Electronics, Vol. 21, No. 2, 2010, pp. 300311.

[32] X. Yao, Y. Liu and G. Lin, “Evolutionary Programming Made Faster,” IEEE Transactions on Evolutionary Computation, Vol. 3, No. 2, 1999, pp. 82-102. doi:10.1109/4235.771163

[33] A.-R. Hedar and M. Fukushima, “Directed Evolutionary Programming: Towards an Improved Performance of Evolutionary Programming,” 2006 IEEE Congress on Evolutionary Computation, Vancouver, 11 September 2006, pp. 1521-1528.