ขั้นตอนวิธีเชิงพันธุกรรมสำหรับการหาค่าเหมาะที่สุดวัตถุประสงค์หลายอย่าง
Genetic Algorithms for Multi-objective Optimization
Keywords:
ขั้นตอนวิธีเชิงพันธุกรรม , การหาค่าเหมาะที่สุดAbstract
บทความนี้นำเสนอข้อจำกัดหนึ่งของขั้นตอนวิธีเชิงพันธุกรรมวัตถุประสงค์หลายอย่าง (MOGA) ในการแก้ปัญหาการหาค่าเหมาะที่สุดวัตถุประสงค์หลายอย่างโดยได้นำ MOGA 3 ชนิดคือ NSGA-II, SPEA-II และ COGA-II มาทดลองกับปัญหาวัตถุประสงค์หลายอย่างมาตรฐาน DTLZ2 และ DTLZ6 ที่มีวัตถุประสงค์ 3-6 อย่าง ซึ่งจากผลการทดลองจะพบว่า MOGA ทั้งสามสามารถแก้ปัญหาที่มีวัตถุประสงค์ 3 อย่างได้เป็นอย่างดี COGA-II ดีกว่า NSGA-II และ SPEA2 อย่างชัดเจนสำหรับปัญหาที่มีวัตถุประสงค์ 4 อย่างขึ้นไป นอกจากนี้ NSGA-II และ SPEA2 แก้ปัญหาที่มี 5 วัตถุประสงค์ขึ้นไปได้ไม่ดี ส่วน COGA-II ซึ่งเป็น MOGA ซึ่งพัฒนามาเพื่อแก้ปัญหาดังกล่าวได้แม้ไม่ดีมากดังเช่นปัญหาที่มี 3 วัตถุประสงค์ ซึ่งแสดงถึงข้อจำกัดสำหรับ MOGA ที่มีอยู่ในปัจจุบัน จากผลการทดลองแสดงว่าจำเป็นต้องมีการพัฒนา MOGA เพื่อปัญหาที่มีวัตถุประสงค์จำนวนมากต่อไป This paper presents a limitation of multi-objective genetic algorithm (MOGA) for solving multi-objective optimization problems. The paper investigates 3 MOGAs – NSGA-II, SPEA-II and COGA-II to solve benchmark problems – DTLZ2 and DTLZ6 with 3-6 objectives. The results show that all MOGAs can solve the problems with 3 objectives effectively. COGA-II is obviously better than the others for the problems with 4-or-more objectives. In addition, NSGA-II and SPEA-II cannot well solve the problems with 5-or-more objectives. On the other hand, COGA-II can solve these problems although it is not very good as in the problems with 3 objectives. This shows the limitation of current MOGAs. Thus, it is necessary to develop MOGA for the optimization problems with high number of objectives.References
Boonlong, K. (2010) Improved Compressed Objective Genetic Algorithm (COGA-II). In Proceeding of the International Conference on Evolutionary Computation, (pp.95-103), Valencia, Spain.
Deb, K. (2001) Multi-objective optimization using evolutionary algorithms. Chichester: Wiley.
Deb, K.; Agrawal, S.; Pratap, A.; and Meyarivan T. (2002) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGAII. IEEE Transactions on Evolutionary Computation. 6(2): 182-197.
Deb, K.; Thiele, L.; Laumanns, M; and Zitzler, E. (2005) Scalable test problems for evolutionary multiobjective optimization. Evolutionary Multiobjective Optimization: Theoretical Advances and Applications. Berlin, Germany, Springer.
Fonseca, C. M.; and Fleming, P. J. (1993) Genetic algorithms for multi-objective optimization: Formulation, discussion and generalization. Proceedings of the Fifth International Conference on Genetic Algorithms, 416-423. Urbana-Champaign, IL, USA.
Goldberg, D. E. (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley.
Horn, J.; Nafpliotis, N.; and Goldberg, D. E. (1994) Multiobjective optimization using the niched Pareto genetic algorithm. First IEEE conference on Evolutionary Computations, IEEE Word Congress on Computational Intelligence, Volume 1, 82-87.
Kaya, M. (2011) The effects of two new crossover operators on genetic algorithm performance. Applied Soft Computing, 11(1): 881-890.
Maneeratana, K.; Boonlong, K.; and Chaiyaratana, N. (2006) Compressed-objective genetic algorithm. Lecture Notes in Computer Science. 4193: 473-482.
Marion, R.; Michel, R.; and Faye, C. (2006) Atmospheric correction of hyperspectral data over dark surfaces via simulated annealing. IEEE Transactions on Geoscience and Remote Sensing. 44(6): 1566-1574.
