Tối ưu hóa nhiều mục tiêu dựa trên phân tách thông tin và chiến lược chọn lựa hình phạt hàng xóm

Soft Computing - Tập 21 - Trang 1109-1128 - 2015
Ruimin Shen1, Jinhua Zheng2,3, Miqing Li2,4, Juan Zou2
1School of Mathematics and Computational Science, Xiangtan University, Xiangtan, China
2Department of Xiangtan University, Institute of Information Engineering, Xiangtan, China
3Key Laboratory of Intelligent Computing and Information Processing, (Xiangtan University) Ministry of Education, Xiangtan, China
4Department of Information Systems and Computing, Brunel University, Uxbridge, United Kingdom

Tóm tắt

Tối ưu hóa nhiều mục tiêu đề cập đến việc tối ưu hóa một bài toán tối ưu hóa nhiều mục tiêu (MOP) trong đó số lượng mục tiêu lớn hơn 3. Hầu hết các thuật toán tối ưu hóa nhiều mục tiêu tiến hóa cổ điển (EMO) sử dụng quan hệ chiếm ưu thế Pareto để hướng dẫn quá trình tìm kiếm, điều này thường hoạt động kém trong các tình huống tối ưu hóa nhiều mục tiêu. Bài báo này đề xuất một thuật toán EMO dựa trên phân tách thông tin và chiến lược chọn lựa hình phạt hàng xóm (ISNPS) để giải quyết các bài toán tối ưu hóa nhiều mục tiêu. ISNPS phân tách hành vi của cá thể trong quần thể thành thông tin hội tụ và thông tin phân bố bằng cách xoay các tọa độ gốc trong không gian mục tiêu. Cụ thể, thuật toán được đề xuất sử dụng một tọa độ để phản ánh sự hội tụ của cá thể và các tọa độ còn lại $$m-1$$ để phản ánh sự phân bố của cá thể, trong đó m là số lượng mục tiêu trong một MOP nhất định. Ngoài ra, một chiến lược hình phạt hàng xóm được phát triển để ngăn cá thể bị chèn chúc. Từ một loạt các thí nghiệm trên 42 trường hợp kiểm tra với 3–10 mục tiêu, ISNPS đã được phát hiện là rất cạnh tranh so với sáu thuật toán đại diện trong lĩnh vực EMO.

Từ khóa

#tối ưu hóa nhiều mục tiêu #thuật toán EMO #chiếm ưu thế Pareto #phân tách thông tin #chọn lựa hình phạt hàng xóm

Tài liệu tham khảo

Adra SF, Fleming PJ (2009) A diversity management operator for evolutionary many-objective optimisation. In: Evolutionary multi-criterion optimization, pp. 81–94. Springer, Nantes, France. doi:10.1007/978-3-642-01020-0_11 Aguirre HE, Tanaka K (2007) Working principles, behavior, and performance of MOEAs on MNK-landscapes. Eur J Oper Res 181(3):1670–1690. doi:10.1016/j.ejor.2006.08.004 Bader J, Zitzler E (2011) HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19(1):45–76. doi:10.1162/EVCO_a_00009 Bentley PJ, Wakefield JP (1997) Finding acceptable Pareto-optimal solutions using multiobjective genetic algorithms. Soft Comput Eng Des Manuf 5:231–240 Beume N, Naujoks B, Emmerich M (2007) SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur J Oper Res 181(3):1653–1669. doi:10.1016/j.ejor.2006.08.008 Bosman PA, Thierens D (2003) The balance between proximity and diversity in multi-objective evolutionary algorithms. IEEE Trans Evol Comput 7(2):174–188. doi:10.1109/TEVC.2003.810761 Cheney W, Kincaid DR (2010) Linear algebra: theory and applications, 2nd edn. Jones & Bartlett Publishers. ISBN 1449613527, 9781449613525 Coello CA, Lamont GB (2004) Applications of multi-objective evolutionary algorithms. World Scientific Publisher, Singapore Corne DW, Knowles JD (2007) Techniques for highly multiobjective optimisation: some nondominated points are better than others. In: Genetic and evolutionary computation conference, pp. 773–780. London, England, UK. doi:10.1145/1276958.1277115 Das I, Dennis JE (1998) Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM J Optim 8(3):631–657. doi:10.1137/S1052623496307510 Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley-interscience series in systems and optimization, 1st edn. Wiley, Chichester, New York Deb K, Agrawal RB (1994) Simulated binary crossover for continuous search space. Complex Syst 9(2):115–148 Deb K, Goyal M (1996) A combined genetic adaptive search (GeneAS) for engineering design. Comput Sci Inform 26(4):30–45 Deb K, Jain H (2004) An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part I: solving problems with box constraints. IEEE Trans Evol Comput 18(4):577–601. doi:10.1109/TEVC.2013.2281535 Deb K, Jain S (2002) Running performance metrics for evolutionary multi-objective optimization. Tech. Rep. Kangal Report No. 2002004, Indian Institute of Technology Deb K, Kumar A (1995) Real-coded genetic algorithms with simulated binary crossover: studies on multimodal and multiobjective problems. Complex Syst 9(6):431–454 Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197. doi:10.1109/4235.996017 Deb K, Thiele L, Laumanns M, Zitzler E (2005) Scalable test problems for evolutionary multi-objective optimization. In: Evolutionary multiobjective optimization, advanced information and knowledge processing, pp. 105–145. Springer, Berlin. doi:10.1007/1-84628-137-7_6 Drechsler N, Drechsler R, Becker B (2001) Multi-objective optimisation based on relation favour. In: Evolutionary multi-criterion optimization, pp. 154–166. Springer, Berlin. doi:10.1007/3-540-44719-9_11 Durillo JJ, Nebro AJ (2011) jMetal: a java framework for multi-objective optimization. Adv Eng Softw 42:760–771. doi:10.1016/j.advengsoft.2011.05.014 Durillo JJ, Nebro AJ, Alba E (2010) The jMetal framework for multi-objective optimization: design and architecture. In: IEEE congress on evolutionary computation, pp. 4138–4325. Barcelona, Spain. doi:10.1109/CEC.2010.5586354 Farina M, Amato P (2002) On the optimal solution definition for many-criteria optimization problems. In: Proceedings of the NAFIPS-FLINT international conference, pp. 233–238. IEEE Serv Center. doi:10.1109/NAFIPS.2002.1018061 Farina M, Amato P (2004) A fuzzy definition of “optimality” for many-criteria optimization problems. IEEE Trans Syst Man Cybern Part A: Syst Hum 34(3):315–326. doi:10.1109/TSMCA.2004.824873 Glaser RE (1983) Levene’s robust test of homogeneity of variances. Encycl Stat Sci 4:608–610 Gómez RH, Coello CA (2013) MOMBI: a new metaheuristic for many-objective optimization based on the R2 indicator. In: IEEE congress on evolutionary computation, pp. 2488–2495. Cancun. doi:10.1109/CEC.2013.6557868 Huband S, Hingston P, Barone L, While L (2006) A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans Evol Comput 10(5):477–506. doi:10.1109/TEVC.2005.861417 Hughes EJ (2003) Multiple single objective Pareto sampling. In: IEEE congress on evolutionary computation, vol. 4, pp. 2678–2684. IEEE, Canberra, Australia. doi:10.1109/CEC.2003.1299427 Hughes EJ (2005) Evolutionary many-objective optimisation: many once or one many? In: IEEE congress on evolutionary computation, vol. 1, pp. 222–227. IEEE Press. doi:10.1109/CEC.2005.1554688 Ikeda K, Kita H (2001) Failure of Pareto-based MOEAs: does non-dominated really mean near to optimal? IEEE Congr Evol Comput 2:957–962. doi:10.1109/CEC.2001.934293 Inselberg A (1985) The plane with parallel coordinates. Vis Comput 1(4):69–91. doi:10.1007/BF01898350 Inselberg A, Dimsdale B (1990) Parallel coordinates: a tool for visualizing multi-dimensional geometry. In: IEEE conference on visualization, pp. 361–378. IEEE Computer Society Press. doi:10.1109/VISUAL.1990.146402 Ishibuchi H, Sakane Y, Tsukamoto N, Nojima Y (2009) Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations. In: IEEE International Conference on Systems, Man, and Cybernetics, pp. 1820–1825. San Antonio, USA. doi:10.1109/ICSMC.2009.5346628 Ishibuchi H, Tsukamoto N, Hitotsuyanagi Y, Nojima Y (2008) Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems. In: Annual conference on genetic and evolutionary computation, pp. 649–656. ACM, New York, USA. doi:10.1145/1389095.1389225 Ishibuchi H, Tsukamoto N, Nojima Y (2008) Evolutionary many-objective optimization: A short review. In: IEEE congress on evolutionary computation, pp. 2424–2431. doi:10.1109/CEC.2008.4631121 Jaimes AL, Quintero LVS, Coello CA (2009) Ranking methods in many-objective evolutionary algorithms. In: Nature-inspired algorithms for optimisation, pp. 413–434. Springer, Berlin Knowles JD, Corne DW (2007) Quantifying the effects of objective space dimension in evolutionary multiobjective optimization. In: Evolutionary multi-criterion optimization, pp. 757–771. Springer, Berlin. doi:10.1007/978-3-540-70928-2_57 Köppen M, Yoshida K (2007) Substitute distance assignments in NSGA-II for handling many-objective optimization problems. In: Evolutionary multi-criterion optimization, pp. 727–741. doi:10.1007/978-3-540-70928-2_55 Laumanns M, Thiele L, Deb K, Zitzler E (2002) Combining convergence and diversity in evolutionary multi-objective optimization. Evol Comput 10(3):263–282. doi:10.1162/106365602760234108 Li M, Yang S, Liu X (2014) Diversity comparison of Pareto front approximations in many-objective optimization. IEEE Trans Cybern 44(12):2568–2584. doi:10.1109/TCYB.2014.2310651 Li M, Yang S, Liu X (2014) Shift-based density estimation for Pareto-based algorithms in many-objective optimization. IEEE Trans Evol Comput 18(3):348–365. doi:10.1109/TEVC.2013.2262178 Li M, Yang S, Liu X, Shen R (2013) A comparative study on evolutionary algorithms for many-objective optimization. In: Evolutionary multi-criterion optimization, lecture notes in computer science, pp. 261–275. Sheffield, UK. doi:10.1007/978-3-642-37140-0_22 Li M, Zheng J, Li K, Yuan Q, Shen R (2010) Enhancing diversity for average ranking method in evolutionary many-objective optimization. In: Parallel problem solving from nature, pp. 647–656. Springer, Berlin. doi:10.1007/978-3-642-15844-5_65 Li M, Zheng J, Shen R, Li K, Yuan Q (2010) A grid-based fitness strategy for evolutionary many-objective optimization. In: Genetic and evolutionary computation conference, pp. 463–470. ACM. doi:10.1145/1830483.1830570 Miller BL, Goldberg DE (1995) Genetic algorithms, tournament selection, and the effects of noise. Complex Syst 9:193–212 Miller RGJ (1981) Simultaneous statistical inference, 2nd edn. Springer, New York Mostaghim S, Schmeck H (2008) Distance based ranking in many-objective particle swarm optimization.In: Parallel problem solving from nature, pp. 753–762. Springer, Berlin. doi:10.1007/978-3-540-87700-4_75 Phan DH, Suzuki J (2013) R2-IBEA: R2 indicator based evolutionary algorithm for multiobjective optimization. In: IEEE congress on evolutionary computation, pp. 1836–1845. IEEE, Cancun, Mexico. doi:10.1109/CEC.2013.6557783 Phan DH, Suzuki J, Hayashi I (2011) BIBEA: boosted indicator based evolutionary algorithm for multiobjective optimization. In: Asia pacific symposium of intelligent and evolutionary systems. Yokosuka, Japan di Pierro F (2006) Many-objective evolutionary algorithms and applications to water resources engineering. Ph.d. thesis, school of engineering, computer science and mathematics, University of Exeter, UK di Pierro F, Khu ST, Savić DA (2007) An investigation on preference order ranking scheme for multiobjective evolutionary optimization. IEEE Trans Evol Comput 11(1):17–45. doi:10.1109/TEVC.2006.876362 Purshouse RC, Fleming PJ (2003) Evolutionary many-objective optimization: an exploratory analysis. IEEE Congr Evol Comput 3:2066–2073. doi:10.1109/CEC.2003.1299927 Purshouse RC, Fleming PJ (2007) On the evolutionary optimization of many conflicting objectives. IEEE Trans Evol Comput 11(6):770–784. doi:10.1109/TEVC.2007.910138 Rice J (1995) Mathematical statistics and data analysis. Duxbury Press Rudolph G, Trautmann H, Sengupta S, Schütze O (2013) Evenly spaced Pareto front approximations for tricriteria problems based on triangulation. In: Evolutionary multi-criterion optimization, pp. 443–458. Springer, Sheffield, UK. doi:10.1007/978-3-642-37140-0_34 Sato H, Aguirre HE, Tanaka K (2007) Controlling dominance area of solutions and its impact on the performance of MOEAs. In: Evolutionary multi-criterion optimization, pp. 5–20. Springer, Berlin. doi:10.1007/978-3-540-70928-2_5 Tamhane AC (1977) Multiple comparisons in model I one-way ANOVA with unequal variances. Commun Stat 6(1):15–32. doi:10.1080/03610927708827466 Veldhuizen DAV, Lamont GB (1998) Evolutionary computation and convergence to a Pareto front. In: Late breaking papers at the genetic programming 1998 conference, pp. 221–228. Stanford University Bookstore, University of Wisconsin, Madison, Wisconsin, USA Wagner T, Beume N, Naujoks B (2007) Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In: Evolutionary multi-criterion optimization, pp. 742–756. Springer, Berlin. doi:10.1007/978-3-540-70928-2_56 Wegman EJ (1990) Hyperdimensional data analysis using parallel coordinates. J Am Stat Assoc 85:664–675 Yang S, Li M, Liu X, Zheng J (2013) A grid-based evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 17(5):721–736. doi:10.1109/TEVC.2012.2227145 Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731. doi:10.1109/TEVC.2007.892759 Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications. Ph.d. thesis, Eidgenössische Technische Hochschule Zürich. Swiss Federal Institute of Technology Zitzler E, Künzli S (2004 Indicator-based selection in multiobjective search. In: Parallel problem solving from nature, pp. 832–842. Springer, Berlin. doi:10.1007/978-3-540-30217-9_84 Zitzler E, Laumanns M, Thiele L (2002) SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization. Evolutionary methods for design., optimisation, and controlCIMNE, Barcelona, Spain, pp 95–100 Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms—a comparative case study. In: Parallel problem solving from nature, pp. 292–301. Springer, Berlin. doi:10.1007/BFb0056872 Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):257–271. doi:10.1109/4235.797969