OGDE3: Opposition-Based Third Generalized Differential Evolution
Farid Bourennani, Shahryar Rahnamayan, and Greg F. Naterer
University of Ontario Institute of Technology (UOIT), 2000 Simcoe Street North, Oshawa, Ontario, Canada L1H 7K4
Multi-Objective Optimization (MOO) metaheuristics are commonly used for solving complex MOO problems characterized by non-convexity, multimodality, mixed-types variables, non-linearity, and other complexities. However, often metaheuristics suffer from slow convergence. Opposition-Based Learning (OBL) has been successfully used in the past for acceleration of single-objective metaheuristics. The most successful example in this regard is Opposition-based Differential Evolution (ODE). However, OBL was not fully explored for MOO metaheuristics. Therefore, in this paper, to the best of our knowledge, for the first time OBL is successfully adapted for a MOO metaheuristic by using a single population (no coevolution). The proposed MOO metaheuristic is based on the GDE3 method and it is called Opposition-based GDE3 (OGDE3). OGDE3 utilizes OBL for opposition-based population initialization and self-adaptive oppositionbased generating jumping. Furthermore, the new algorithm is compared with seven state-of-the-artMOO metaheuristics using the ZDT test suite. OGDE3 outperformed the other algorithms; the results are explained and discussed in detail.
-  C. A. Coello, “Evolutionary Multi-Objective Optimization: Current and Future Research Trends,” Plenary Talk in the 9th Int. Conf. on Intelligent Systems Design and Applications (ISDA09), Pisa, Italy, 2009.
-  J. J. Durillo, A. J. Nebro, C. A. Coello Coello, J. Garcıa-Nieto, F. Luna, and E. Alba, “A Study of Multiobjective Metaheuristics When Solving Parameter Scalable Problems,” IEEE Trans. On Evolutionary Computation, Vol.14, No.4, pp. 618-636, 2010.
-  S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “Opposition versus randomness in soft computing techniques,” Applied Soft Computing J., Vol.8, No.2, pp. 906-918, 2008.
-  E. Zitzler, K. Deb, and L. Thieler, “Comparison of multiobjective evolutionary algorithms: Empirical results,” IEEE Trans. on Evol. Computation, Vol.8, pp. 173-195, 2000.
-  L. Sean, “Essentials of Metaheuristics,” Online Version 0.12, Zeroth Edition, 2010.
-  K. Deb, “Multi-objective Optimization Using Evolutionary Algorithms,” Wiley: New York, 2001. ISBN: 978-0471873396
-  S. Rahnamayan, “Opposition-Based Differential Evolution,” Ph.D. Thesis, Department of Systems Design Engineering, University of Waterloo, Waterloo, Ontario, Canada, May 2007.
-  H. R. Tizhoosh, “Opposition-based learning: A new scheme for machine intelligence,” in Proc. of the Int. Conf. on Computational Intelligence for Modelling, Control and Automation, CIMCA 2005 and Int. Conf. on Intelligent Agents, Web Technologies and Internet, Vol.1, pp. 695-701, 2005.
-  H. R. Tizhoosh and M. Ventresca, “Oppositional Concepts in Computational Intelligence,” Vol.155 of Studies in Computational Intelligence, 2008.
-  S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “Opposition-based differential evolution algorithms,” in IEEE Congress on Evolutionary Computation, pp. 2010-2017, 2006.
-  S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “A novel population initialization method for accelerating evolutionary algorithms,” Computers and Mathematics with Applications, Vol.53, No.10, pp. 1605-1614, 2007.
-  S. Rahnamayan and G. Wang, “Solving large scale optimization problems by opposition-based differential evolution (ODE),” WSEAS Trans. on Computers, Vol.7, No.10, pp. 1792-1804, 2008.
-  S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “Opposition-based differential evolution for optimization of noisy problems,” in IEEE Congress on Evolutionary Computation, CEC, pp. 1865-1872, 2006.
-  S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “Quasioppositional differential evolution,” in IEEE Congress on Evolutionary Computation, CEC 2007, pp. 2229-2236, 2008.
-  S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “Opposition-based differential evolution (ODE) with variable jumping rate,” In Proc. of the 2007 IEEE Symposium on Foundations of Computational Intelligence, FOCI, pp. 81-88, 2007.
-  H. Lin and H. Xingshi, “A novel opposition-based particle swarm optimization for noisy problems,” in Proc. of the Third Int. Conf. on Natural Computation, ICNC, Vol.3, pp. 624-629, 2007.
-  M. G. H. Omran and S. Al-Sharhan, “Using opposition-based learning to improve the performance of particle swarm optimization,” in IEEE Swarm Intelligence Symposium, SIS, St. Louis, MO, 2008.
-  F. S. Al-Qunaieer, H. R. Tizhoosh, and S. Rahnamayan, “Opposition Based Computing – A Survey,” IEEE Int. Joint Conf. on Neural Networks (IJCNN), Barcelona, Spain, pp. 3183-3189, July 18-23, 2010.
-  L. Peng, Y. Wang, and A. G. Dai, “A Novel Opposition-Based Multi-objective Differential Evolution Algorithm for Multiobjective Optimization,” Advances in Computation and Intelligence, pp. 162-170, 2008.
-  R. Storn and K. Price, “Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces,” J. of Global Optimization, Vol.11, pp. 341-359, 1997.
-  K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. on Evolutionary Computation, Vol.6, No.2, pp. 182-197, 2002.
-  J. D. Knowles and D. W. Corne, “The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Multiobjective Optimisation,” In Proc. of the Congress on Evolutionary Computation, Washington D.C., USA, pp. 98-105, 1999.
-  E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the Strength Pareto Evolutionary Algorithm,” EUROGEN 2001, Vol.3242, No.103, pp. 95-100, 2002.
-  H. Ishibuchi, N. Tsukamoto, and Y. Nojima, “Iterative approach to indicator-based multiobjective optimization,” In Proc. of the IEEE Congress on Evolutionary Computation, CEC 2007, Singapore, pp. 3967-3974, 2007.
-  N. Wang and Y. Dong, “Multiobjective Differential Evolution Based on Opposite Operation,” Int. Conf. on Computational Intelligence and Security (CIS ’09), Beijing, China, pp. 123-127, 2009.
-  Q. Zhang, A. Zhou, and Y. Jin, “RM-MEDA: A regularity modelbased multiobjective estimation of distribution algorithm,” IEEE Trans. Evolutionary Computation, Vol.12, No.1, pp. 41-63, 2008.
-  T. G. Teo and J. Tan, “Evolving Opposition-Based Pareto Solutions: Multiobjective Optimization Using Competitive Coevolution,” In H. R. Tizhoosh and M. Ventresca (Eds), Oppositional Concepts in Computational Intelligence, Springer, Vol.155, pp. 161-206, 2008.
-  K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, “Scalable Test Problems for Evolutionary Multiobjective Optimization,” In Evolutionary Multiobjective Optimization. Theoretical Advances and Applications, A. Abraham, L. Jain, and R. Goldberg (Eds.), Springer USA, pp. 105-145, 2005.
-  D. A. Van Veldhuizenand and G. B. Lamont, “On Measuring Multiobjective Evolutionary Algorithm Performance,” In Proc. of the 2000 Congress on Evolutionary Computation, Vol.1, La Jolla, CA, USA, pp. 204-211, 2000.
-  J. R. Schott, “Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization,” Masters thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1995.
-  E. Zitzler, K. Deb, and L. Thiele, “Comparison of Multiobjective Evolutionary Algorithms: Empirical Results,” Evolutionary Computation, Vol.8, No.2, pp. 173-195, 2000.
-  S. Kukkonen and J. Lampinen, “GDE3: the third evolution step of generalized differential evolution,” IEEE Congress on Evolutionary Computation (CEC’2005), Edinbourgh, U.K., pp.443-450, 2005.
-  J. Lampinen, “DE’s selection rule for multiobjective optimization,” Technical report, Lappeenranta University of Technology, Department of Information Technology, 2001.
-  G. Eiben and M. Schut, “New Ways to Calibrate Evolutionary Algorithms,” In P. Siarry and Z. Michalewicz, editors, Advances in Metaheuristics for Hard Optimization, Natural Computing, pp. 153-177. Springer, Heidelberg, Germany, 2008.
-  A. J. Nebro, J. J. Durillo, C. A. Coello Coello, F. Luna, and E. Alba, “A Study of Convergence Speed in Multi-Objective Metaheuristics,” Parallel Problem Solving from Nature (PPSN X), Springer, Lecture Notes in Computer Science, Vol.5199, Dortmund, Germany, pp.763-772, 2008.
-  J. J. Durillo, A. J. Nebro, F. Luna, C. A.Coello Coello, and E. Alba, “Convergence Speed in Multi-Objective Metaheuristics: Efficiency Criteria and Empirical Study,” Int. J. for Numerical Methods in Engineering, Vol.83, No.3, 2010.
-  A. J. Nebro, J. J. Durillo, F. Luna, B. Dorronsoro, and E. Alba, “A cellular genetic algorithm for multiobjective optimization,” In Nature Inspired Cooperative Strategies for Optimization (NICSO 2006), Grenada, Spain, pp. 25-36, 2006.
-  M. Reyes Sierra and C. A. Coello, “Improving PSO-Based Multiobjective Optimization Using Crowding, Mutation and Dominance,” In Evolutionary Multi-Criterion Optimization (EMO 2005), LNCS 3410, Guanajuato, Mexico, pp. 505-519, 2005.
-  A. J. Nebro, F. Luna, E. Alba, B. Dorronsoro, J. J. Durillo, and A. Beham, “AbYSS: Adapting scatter search to multiobjective optimization,” IEEE Trans. on Evolutionary Computation, Vol.12, No.4, pp. 439-457, 2008.
-  J. J. Durillo, A. J. Nebro, and E. Alba, “The jMetal Framework forMulti-Objective Optimization: Design and Architecture,” IEEECEC 2010, pp. 4138-4325, July 2010.
-  E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach,” IEEE Trans. Evol. Comput., Vol.3, No.4, pp. 257-271, November 1999.
-  D. J. Sheskin, “Handbook of Parametric and Nonparametric Statistical Procedures,” 4th ed., New York: Chapman & Hall/CRC Press, 2007.