Parallel multi-objective evolutionary algorithms on graphics processing units

ABSTRACT

Most real-life optimization problems or decision-making problems are multi-objective in nature, since they normally have several (possibly conflicting) objectives that must be satisfied at the same time. Multi-Objective Evolutionary Algorithms (MOEAs) have been gaining increasing attention among researchers and practitioners. However, they may execute for a long time for some difficult problems, because several evaluations must be performed. Moreover, the non-dominance checking and the non-dominated selection procedures are also very time consuming. From our experiments, more than 99% of the execution time is used in performing the two procedures. A promising approach to overcome this limitation is to parallelize these algorithms. In this paper, we propose a parallel MOEA on consumer-level Graphics Processing Units (GPU). We perform many experiments on two-objective and three-objective benchmark problems to compare our parallel MOEA with a sequential MOEA and demonstrate that the former is much more efficient than the latter.

REFERENCES

• 1: Darren M. Chitty, A data parallel approach to genetic programming using programmable graphics hardware, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277274]
• 2: C. A. Coello Coello, G. Toscano Pulido, and M. Salazar Lechuga. Handling Multiple Objectives With Particle Swarm Optimization. IEEE Transactions on Evolutionary Computation, 8(3):256--279, June 2004.
• 3: Carlos A. Coello Coello , Gary B. Lamont , David A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: D. W. Corne, N. R. Jerram, J. D. Knowles, and M. J. Oates. PESA-II: Region-based Selection in Evolutionary Multiobjective Optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'2001), pages 283--290, 2001.
• 5: Kalyanmoy Deb, Multi-objective genetic algorithms: Problem difficulties and construction of test problems, Evolutionary Computation, v.7 n.3, p.205-230, Fall 1999 [doi>10.1162/evco.1999.7.3.205]
• 6: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 7: K. Deb, M. Mohan, and S. Mishra. Towards a Quick Computation of Well-Spread Pareto-Optimal Solutions. In C. M. Fonseca, P. J. Fleming, E. Zitzler, K. Deb, and L. Thiele, editors, Evolutionary Multi-Criterion Optimization. Second International Conference, EMO 2003, pages 222--236, April 2003.
• 8: K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182--197, April 2002.
• 9: K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable Multi-objective Optimization Test Problems. In Proceedings of the 2002 Congress on Evolutionary Computation (CEC'2002), pages 825--830, May 2002.
• 10: J. E. Fieldsend, R. M. Everson, and S. Singh. Using Unconstrained Elite Archives for Multiobjective Optimization. IEEE Transactions on Evolutionary Computation, 7(3):305--323, June 2003.
• 11: Ka-Ling Fok , Tien-Tsin Wong , Man-Leung Wong, Evolutionary Computing on Consumer Graphics Hardware, IEEE Intelligent Systems, v.22 n.2, p.69-78, March 2007 [doi>10.1109/MIS.2007.28]
• 12: Carlos M. Fonseca , Peter J. Fleming, Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization, Proceedings of the 5th International Conference on Genetic Algorithms, p.416-423, June 01, 1993
• 13: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 14: S. Harding and W. Banzhaf. Fast Genetic Programming on GPUs. In Proceedings of the 10th European Conference on Genetic Programming (EuroGP'2007), pages 90--101, April 2007.
• 15: J. Horn, N. Nafpliotis, and D. E. Goldberg. A Niched Pareto Genetic Algorithm for Multiobjective Optimization. In Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, volume 1, pages 82--87, June 1994.
• 16: L. Howes and D. Thomas. Efficient Random Number Generation and Application Using CUDA. In H. Nguyen, editor, GPU Gems 3, pages 805--830. Addison Wesley, 2007.
• 17: P. Kipfer and R. Westermann. Improved GPU Sorting. In M. Pharr, editor, GPU Gems 2, pages 733--746. Addison Wesley, 2005.
• 18: Joshua D. Knowles , David W. Corne, Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy, Evolutionary Computation, v.8 n.2, p.149-172, June 2000 [doi>10.1162/106365600568167]
• 19: J. D. Knowles and D. W. Corne. Properties of an Adaptive Archiving Algorithm for Storing Nondominated Vectors. IEEE Transactions on Evolutionary Computation, 7(2):100--116, April 2003.
• 20: W. B. Langdon and W. Banzhaf. A SIMD Interpreter for Genetic Programming on GPU Graphics Cards. In Proceedings of the 11th European Conference on Genetic Programming (EuroGP'2008), pages 73--85, April 2008.
• 21: Marco Laumanns , Lothar Thiele , Kalyanmoy Deb , Eckart Zitzler, Combining convergence and diversity in evolutionary multiobjective optimization, Evolutionary Computation, v.10 n.3, p.263-282, Fall 2002 [doi>10.1162/106365602760234108]
• 22: nVidia. NVIDIA CUDAtm Programming Guide Version 2.1. http://developer.nvidia.com/object/cuda.html, 2008.
• 23: W. M. Pang, T. T. Wong, and P. A. Heng. Generating Massive High-quality Random Numbers Using GPU. In Proceedings of the 2008 Congress on Evolutionary Computation (CEC'2008), pages 841--847, June 2008.
• 24: N. Srinivas , Kalyanmoy Deb, Muiltiobjective optimization using nondominated sorting in genetic algorithms, Evolutionary Computation, v.2 n.3, p.221-248, Fall 1994 [doi>10.1162/evco.1994.2.3.221]
• 25: K. Tan, T. Lee, and E. Khor. Evolutionary Algorithms with Dynamic Population Size and Local Exploration for Multiobjective Optimization. IEEE Transactions on Evolutionary Computation, 5(6):565--588, December 2001.
• 26: G. Wilson and W. Banzhaf. Linear Genetic Programming GPGPU on Microsoft's Xbox 360. In Proceedings of the 2008 Congress on Evolutionary Computation (CEC'2008), pages 378--385, June 2008.
• 27: M. L. Wong, T. T. Wong, and K. L. Fok. Parallel Evolutionary Algorithms on Graphics Processing Unit. In Proceedings of the 2005 Congress on Evolutionary Computation (CEC'2005), pages 2286--2293, September 2005.
• 28: M. L. Wong, T. T. Wong, and K. L. Fok. Parallel Hybrid Genetic Algorithms on Consumer-level Graphics Hardware. In Proceedings of the 2006 Congress on Evolutionary Computation (CEC'2006), pages 10330--10337, July 2006.
• 29: X.Yao and Y.Liu. Fast Evolutionary Programming. In Evolutionary Programming V: Processdings of the 5th Annual Conference on Evolutionary Programming. Cambridge, MA:MIT Press, 1996.
• 30: G. G. Yen and H. Lu. Dynamic Multiobjective Evolutionary Algorithm: Adaptive Cell-Based Rank and Density Estimation. IEEE Transactions on Evolutionary Computation, 7(3):253--274, June 2003.
• 31: E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. In K. Giannakoglou, D. Tsahalis, J. Periaux, P. Papailou, and T. Fogarty, editors, EUROGEN 2001. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, pages 95--100, 2002.
• 32: E. Zitzler and L. Thiele. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation, 3(4):257--271, November 1999.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
graphic processing units, multi-objective evolutionary algorithms, parallel programming