การประยุกต์ใช้วิธีวิวัฒนาการด้วยผลต่างเพื่อเปรียบเทียบประสิทธิภาพในการแก้ปัญหาหลายวัตถุประสงค์ที่มีค่าต่อเนื่อง
Article Sidebar
เผยแพร่แล้ว:
ส.ค. 31, 2018
คำสำคัญ:
ปัญหาแบบมากวัตถุประสงค์ การจำแนกปัญหา การหาค่าที่เหมาะสมสำหรับปัญหาหลายวัตถุประสงค์ วิธีการเชิงวิวัฒนาการ วิธีวิวัฒนาการด้วยผลต่างแบบปรับตัว
Main Article Content
บทคัดย่อ
การจำแนกปัญหา (Decomposition) เป็นหลักการพื้นฐานในการแก้ปัญหาแบบหลายวัตถุประสงค์ทั่วไป ซึ่งในปัจจุบันเป็นที่สนใจและนิยมใช้ในการหาค่าที่เหมาะสมอย่างแพร่หลาย ในบทความนี้ จึงนำเสนอวิธีการวิวัฒนาการแบบปรับตัวโดยใช้ผลต่างสำหรับปัญหาหลายวัตถุประสงค์โดยยึดหลักการจำแนก (Adaptive MOEA/D hybridized with Differential Evolution: AMOEA/D-DE) ซึ่งมีแนวคิดพื้นฐานจากวิธีการเชิงวิวัฒนาการแบบหลายวัตถุประสงค์โดยยึดหลักการจำแนก (A Multi-Objective Evolutionary Algorithm based on Decomposition: MOEA/D) และวิธีเชิงวัฒนาการโดยใช้ผลต่างแบบปรับตัว (Adaptive Differential Evolution Algorithm: ADE) โดยอัลกอริทึมนี้ จะทำการจำแนกปัญหาออกเป็นปัญหาย่อย (แบ่งปัญหาหลายวัตถุประสงค์ออกเป็นปัญหาวัตถุประสงค์เดียวหลายปัญหา) และทำการหาค่าที่เหมาะสมของทุกปัญหาย่อยไปพร้อม ๆ กัน ร่วมกับการปรับค่าพารามิเตอร์ควบคุมและกลยุทธ์ที่ใช้ในการหาค่าที่เหมาะสม เพื่อให้เกิดทิศทางการค้นหาคำตอบที่ดีและหลากหลาย โดยแต่ละปัญหาย่อยจะพัฒนาคำตอบรุ่นใหม่ด้วยคำตอบเดิมของปัญหาย่อยข้างเคียง ด้วยวิธีนี้ จึงทำให้ AMOEA/D-DE มีความซับซ้อนในการดำเนินงานที่น้อยและสามารถปรับตัวให้เหมาะสมกับสถานการณ์การค้นหาคำตอบได้ ในบทความนี้ ได้นำ AMOEA/D-DE มาเปรียบเทียบกับ MOEA/D และ MODE/D ด้วยการแก้ปัญหามาตรฐานแบบหลายวัตถุประสงค์ที่มีค่าต่อเนื่อง ซึ่งจากการทดลองพบว่า AMOEA/D-DE มีประสิทธิภาพด้านอัตราการลู่เข้าที่ดีกว่าอัลกอริทึมอื่น ๆ แต่ต้องใช้เวลาการดำเนินงานที่มากกว่า เมื่อเทียบจำนวนในการพัฒนาคำตอบที่เท่ากันานอัตราการลู่เข้าที่ดีกว่าอัลกอริทึมอื่น ๆ
Article Details
รูปแบบการอ้างอิง
[1]
เกิดโภคทรัพย์ ต., “การประยุกต์ใช้วิธีวิวัฒนาการด้วยผลต่างเพื่อเปรียบเทียบประสิทธิภาพในการแก้ปัญหาหลายวัตถุประสงค์ที่มีค่าต่อเนื่อง”, sej, ปี 13, ฉบับที่ 2, น. 52–71, ส.ค. 2018.
ประเภทบทความ
บทความวิจัย
ลิขสิทธิ์เป็นของวารสารวิศวกรรมศาสตร์ มหาวิทยาลัยศรีนครินทรวิโรฒ
เอกสารอ้างอิง
[1] Z. He and G. G. Yen, "Many-Objective Evolutionary Algorithm: Objective Space Reduction and Diversity Improvement," IEEE Transactions on Evolutionary Computation, vol. 20, no. 1, pp. 145-160, 2016.
[2] D. Brockhoff and E. Zitzler, "Objective reduction in evolutionary multi-objective optimization: Theory and applications," Evolutionary Computation, vol. 17, no. 2, pp. 135-166, 2009.
[3] Q. Zhang and H. Li, "MOEA/D: A multiobjective evolutionary algorithm based on decomposition," IEEE Transactions on evolutionary computation, vol. 11, no. 6, pp. 712-731, 2007.
[4] H. Li and Q. Zhang, "A multiobjective differential evolution based on decomposition for multiobjective optimization with variable linkages," in Parallel problem solving from nature-PPSN IX: Springer, 2006, pp. 583-592.
[5] K. Miettinen, "Nonlinear Multiobjective Optimization, volume 12 of International Series in Operations Research and Management Science," ed: Kluwer Academic Publishers, Dordrecht, 1999.
[6] M. Ehrgott, "A discussion of scalarization techniques for multiple objective integer programming," Annals of Operations Research, vol. 147, no. 1, pp. 343-360, 2006.
[7] H. Li and Q. Zhang, "Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II," IEEE Transactions on evolutionary computation, vol. 13, no. 2, pp. 284-302, 2009.
[8] Q. Zhang, W. Liu, E. Tsang, and B. Virginas, "Expensive multiobjective optimization by MOEA/D with Gaussian process model," IEEE Transactions on Evolutionary Computation, vol. 14, no. 3, pp. 456-474, 2010.
[9] 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, pp. 341-359, 1997.
[10] S. M. Venske, R. A. Gonçalves, and M. R. Delgado, "ADEMO/D: Multiobjective optimization by an adaptive differential evolution algorithm," Neurocomputing, vol. 127, pp. 65-77, 2014.
[11] K. Price, R. M. Storn, and J. A. Lampinen, Differential evolution: a practical approach to global optimization. Springer Science & Business Media, 2006.
[12] A. K. Qin and P. N. Suganthan, "Self-adaptive differential evolution algorithm for numerical optimization," in Evolutionary Computation, 2005. The 2005 IEEE Congress on, 2005, vol. 2, pp. 1785-1791: IEEE.
[13] 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, pp. 646-657, 2006.
[14] J. Teo, "Exploring dynamic self-adaptive populations in differential evolution," Soft Computing, vol. 10, no. 8, pp. 673-686, 2006.
[15] V. L. Huang, A. K. Qin, and P. N. Suganthan, "Self-adaptive differential evolution algorithm for constrained real-parameter optimization," in Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, 2006, pp. 17-24: IEEE.
[16] X. Yao, Y. Liu, and G. Lin, "Evolutionary programming made faster," IEEE Transactions on Evolutionary computation, vol. 3, no. 2, pp. 82-102, 1999.
[17] C.-Y. Lee and X. Yao, "Evolutionary programming using mutations based on the Lévy probability distribution," IEEE Transactions on Evolutionary Computation, vol. 8, no. 1, pp. 1-13, 2004.
[18] J. Liu and J. Lampinen, "A fuzzy adaptive differential evolution algorithm," Soft Computing, vol. 9, no. 6, pp. 448-462, 2005.
[19] J. Zhang and A. C. Sanderson, "JADE: adaptive differential evolution with optional external archive," IEEE Transactions on evolutionary computation, vol. 13, no. 5, pp. 945-958, 2009.
[20] S. M. S. Venske, R. A. Goncalves, and M. R. Delgado, "ADEMO/D: Adaptive Differential Evolution for Multiobjective Problems," presented at the 2012 Brazilian Symposium on Neural Networks, 2012.
[21] J. Zhang and A. C. Sanderson, Adaptive Differential Evolution: A Robust Approach to Multimodal Problem Optimization. Scientific Publishing Services Pvt. Ltd., Chennai, India., 2009, p. 163.
[22] Q. Lin, Q. Zhu, P. Huang, J. Chen, Z. Ming, and J. Yu, "A novel hybrid multi-objective immune algorithm with adaptive differential evolution," Computers & Operations Research, vol. 62, pp. 95-111, 2015.
[23] E. Zitzler, K. Deb, and L. Thiele, "Comparison of multiobjective evolutionary algorithms: Empirical results," Evolutionary computation, vol. 8, no. 2, pp. 173-195, 2000.
[24] K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, "Scalable multi-objective optimization test problems," in Evolutionary Computation, 2002. CEC'02. Proceedings of the 2002 Congress on, 2002, vol. 1, pp. 825-830: IEEE.
[25] K. Deb, Multi-objective optimization using evolutionary algorithms. John Wiley & Sons, 2001.
[26] E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. Da Fonseca, "Performance assessment of multiobjective optimizers: An analysis and review," IEEE Transactions on evolutionary computation, vol. 7, no. 2, pp. 117-132, 2003.
[27] S. Jiang, Y. S. Ong, J. Zhang, and L. Feng, "Consistencies and contradictions of performance metrics in multiobjective optimization," IEEE Trans Cybern, vol. 44, no. 12, pp. 2391-404, Dec 2014.
[28] A. Ibrahim, S. Rahnamayan, M. V. Martin, and K. Deb, "3D-RadVis: Visualization of Pareto front in many-objective optimization," in Evolutionary Computation (CEC), 2016 IEEE Congress on, 2016, pp. 736-745: IEEE.
[2] D. Brockhoff and E. Zitzler, "Objective reduction in evolutionary multi-objective optimization: Theory and applications," Evolutionary Computation, vol. 17, no. 2, pp. 135-166, 2009.
[3] Q. Zhang and H. Li, "MOEA/D: A multiobjective evolutionary algorithm based on decomposition," IEEE Transactions on evolutionary computation, vol. 11, no. 6, pp. 712-731, 2007.
[4] H. Li and Q. Zhang, "A multiobjective differential evolution based on decomposition for multiobjective optimization with variable linkages," in Parallel problem solving from nature-PPSN IX: Springer, 2006, pp. 583-592.
[5] K. Miettinen, "Nonlinear Multiobjective Optimization, volume 12 of International Series in Operations Research and Management Science," ed: Kluwer Academic Publishers, Dordrecht, 1999.
[6] M. Ehrgott, "A discussion of scalarization techniques for multiple objective integer programming," Annals of Operations Research, vol. 147, no. 1, pp. 343-360, 2006.
[7] H. Li and Q. Zhang, "Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II," IEEE Transactions on evolutionary computation, vol. 13, no. 2, pp. 284-302, 2009.
[8] Q. Zhang, W. Liu, E. Tsang, and B. Virginas, "Expensive multiobjective optimization by MOEA/D with Gaussian process model," IEEE Transactions on Evolutionary Computation, vol. 14, no. 3, pp. 456-474, 2010.
[9] 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, pp. 341-359, 1997.
[10] S. M. Venske, R. A. Gonçalves, and M. R. Delgado, "ADEMO/D: Multiobjective optimization by an adaptive differential evolution algorithm," Neurocomputing, vol. 127, pp. 65-77, 2014.
[11] K. Price, R. M. Storn, and J. A. Lampinen, Differential evolution: a practical approach to global optimization. Springer Science & Business Media, 2006.
[12] A. K. Qin and P. N. Suganthan, "Self-adaptive differential evolution algorithm for numerical optimization," in Evolutionary Computation, 2005. The 2005 IEEE Congress on, 2005, vol. 2, pp. 1785-1791: IEEE.
[13] 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, pp. 646-657, 2006.
[14] J. Teo, "Exploring dynamic self-adaptive populations in differential evolution," Soft Computing, vol. 10, no. 8, pp. 673-686, 2006.
[15] V. L. Huang, A. K. Qin, and P. N. Suganthan, "Self-adaptive differential evolution algorithm for constrained real-parameter optimization," in Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, 2006, pp. 17-24: IEEE.
[16] X. Yao, Y. Liu, and G. Lin, "Evolutionary programming made faster," IEEE Transactions on Evolutionary computation, vol. 3, no. 2, pp. 82-102, 1999.
[17] C.-Y. Lee and X. Yao, "Evolutionary programming using mutations based on the Lévy probability distribution," IEEE Transactions on Evolutionary Computation, vol. 8, no. 1, pp. 1-13, 2004.
[18] J. Liu and J. Lampinen, "A fuzzy adaptive differential evolution algorithm," Soft Computing, vol. 9, no. 6, pp. 448-462, 2005.
[19] J. Zhang and A. C. Sanderson, "JADE: adaptive differential evolution with optional external archive," IEEE Transactions on evolutionary computation, vol. 13, no. 5, pp. 945-958, 2009.
[20] S. M. S. Venske, R. A. Goncalves, and M. R. Delgado, "ADEMO/D: Adaptive Differential Evolution for Multiobjective Problems," presented at the 2012 Brazilian Symposium on Neural Networks, 2012.
[21] J. Zhang and A. C. Sanderson, Adaptive Differential Evolution: A Robust Approach to Multimodal Problem Optimization. Scientific Publishing Services Pvt. Ltd., Chennai, India., 2009, p. 163.
[22] Q. Lin, Q. Zhu, P. Huang, J. Chen, Z. Ming, and J. Yu, "A novel hybrid multi-objective immune algorithm with adaptive differential evolution," Computers & Operations Research, vol. 62, pp. 95-111, 2015.
[23] E. Zitzler, K. Deb, and L. Thiele, "Comparison of multiobjective evolutionary algorithms: Empirical results," Evolutionary computation, vol. 8, no. 2, pp. 173-195, 2000.
[24] K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, "Scalable multi-objective optimization test problems," in Evolutionary Computation, 2002. CEC'02. Proceedings of the 2002 Congress on, 2002, vol. 1, pp. 825-830: IEEE.
[25] K. Deb, Multi-objective optimization using evolutionary algorithms. John Wiley & Sons, 2001.
[26] E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. Da Fonseca, "Performance assessment of multiobjective optimizers: An analysis and review," IEEE Transactions on evolutionary computation, vol. 7, no. 2, pp. 117-132, 2003.
[27] S. Jiang, Y. S. Ong, J. Zhang, and L. Feng, "Consistencies and contradictions of performance metrics in multiobjective optimization," IEEE Trans Cybern, vol. 44, no. 12, pp. 2391-404, Dec 2014.
[28] A. Ibrahim, S. Rahnamayan, M. V. Martin, and K. Deb, "3D-RadVis: Visualization of Pareto front in many-objective optimization," in Evolutionary Computation (CEC), 2016 IEEE Congress on, 2016, pp. 736-745: IEEE.
