SRDE: an improved differential evolution based on stochastic ranking

ABSTRACT

In this paper, we propose a methodology to improve the performance of the standard Differential Evolution (DE) in constraint optimization applications, in terms of accelerating its search speed, and improving the success rate. One critical mechanism embedded in the approach is applying Stochastic Ranking (SR) to rank the whole population of individuals with both objective value and constraint violation to be compared. The ranked population is then in a better shape to provide useful information e.g. direction to guide the search process. The performance of the proposed approach, which we call SRDE (Stochastic Ranking based Differential Evolution) is investigated and compared with standard DE with two variants of mutation strategies. The experimental results show that SRDE outperforms, or at least is comparable with standard DE in both variants in all the tested benchmark functions.

REFERENCES

• 1: Rainer Storn , Kenneth Price, Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, v.11 n.4, p.341-359, December 1997 [doi>10.1023/A:1008202821328]
• 2: Silvio Priem Mendes , Juan A. Gomez Pulido , Miguel A. Vega Rodriguez , Maria D. Jaraiz Simon , Juan M. Sanchez Perez, A Differential Evolution Based Algorithm to Optimize the Radio Network Design Problem, Proceedings of the Second IEEE International Conference on e-Science and Grid Computing, p.119, December 04-06, 2006 [doi>10.1109/E-SCIENCE.2006.3]
• 3: Runarsson T.P., Yao X., 2000. Stochastic Ranking for Constrained Evolutionary Computation. IEEE Trans. Evol. Comput. 4, 3 (Sept. 2000), 284--294
• 4: X. Yao, Y. Liu, and G, Lin, Evolutionary programming made faster. IEEE trans. Evol, Compt. Vol 3, no 2,July 1999.
• 5: Antony W. Iorio , Xiaodong Li, Incorporating directional information within a differential evolution algorithm for multi-objective optimization, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144119]
• 6: Rahnamayan S., Tizhoosh, H.R., Salama M.M.A. Opposition -- based Differential Evolution. Evolutionary Computation, IEEE Transactions on, Vol 12, Issue 1, 2008: 64 -- 79
• 7: Noman, N.; Iba, H. Accelerating Differential Evolution Using an Adaptive Local Search. Evolutionary Computation, IEEE Trans. on Vol 12, Issue 1, :107 -- 125
• 8: Brest J., Zumer V., Maucec M. S., 2006. Self-Adaptive Differential Evolution Algorithm in Constrained Real-Parameter Optimization. IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Center Hotel, Vancouver, BC, Canada, 215--222
• 9: Takahama T., Sakai S., 2006. Constrained Optimization by the Constrained Differential Evolution with Gradient-Based Mutation and Feasible Elites, IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Center Hotel, Vancouver, BC, Canada, 1--8
• 10: Kukkonen S., Lampinen J. 2006. Constrained Real-Parameter Optimization with Generalized Differential Evolution. IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Center Hotel, Vancouver, BC, Canada, 207--214
• 11: Liang J.J., Suganthan P.N., 2006. Dynamic Multi-Swarm Particle Swarm Optimizer with a Novel Constraint-Handling Mechanism, IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Center Hotel, Vancouver, BC, Canada, 9--16
• 12: Mezura-Montes E., Velazquez-Reyes J., Coello C.A.C., 2006. Modified Differential Evolution for Constrained Optimization, IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Center Hotel, Vancouver, BC, Canada, 25--32
• 13: A. K. Qin, V. L. Huang, and P. N. Suganthan, Differential evolution algorithm with strategy adaptation for global numerical optimization", IEEE Trans. on Evolutionary Computations, DOI: 10.1109/TEVC.2008.927706, 2009
• 14: Jianyong Sun , Qingfu Zhang , Edward P. K. Tsang, DE/EDA: a new evolutionary algorithm for global optimization, Information Sciences—Informatics and Computer Science: An International Journal, v.169 n.3-4, p.249-262, 1 February 2005 [doi>10.1016/j.ins.2004.06.009]
• 15: J. J. Liang, Thomas Philip Runarsson, Efren Mezura-Montes, Maurice Clerc, P. N. Suganthan, Carlos A. Coello Coello & K. Deb,"Problem Definitions and Evaluation Criteria for the CEC 2006 Special Session on Constrained Real-Parameter Optimization", Technical Report, Nanyang Technological University, Singapore, March 2006
• 16: J. Lampinen, A constraint handling approach for the differential evolution algorithm, Proceedings of the Evolutionary Computation on 2002. CEC '02. Proceedings of the 2002 Congress, p.1468-1473, May 12-17, 2002
• 17: R. L. Becerra, C. A. C. Coello, Cultured differential evolution for constrained optimization , Computer Methods in Applied Mechanics and Engineering, Vol. 195, No. 33--36, 2006, pp. 4303--4322.
• 18: K. Deb, and H. Gupta, A constraint handling strategy for robust multi-criterion optimization, KanGAL Report No. 2005001, 2005
• 19: Kukkonen, S.; Lampinen, J. Constrained Real-Parameter Optimization with Generalized Differential Evolution. Evolutionary Computation, 2006. CEC 2006. IEEE Congress on Volume, Issue , 0--0 0 Page(s):207 -- 214
• 20: Z. Fan, J. Liu, T, Sørensen, P, Wang. Robust Layout Synthesis of MEMS Components Based on an Improved Differential Evolution Algorithm. IEEE trans. On Industrial Electronics.(accepted)

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms

Keywords:
constrained optimization, differential evolution, stochastic ranking