Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
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
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ómTà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