微信服务号

微信订阅号

2025-5-11- 13
Home > Archive>Volume 26, Issue 5, 2015 >1013-1036. DOI:10.13328/j.cnki.jos.004676
PDF HTML XML Export Cite reminder
Evolutionary Algorithm Based on Information Separation for Many-Objective Optimization
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [58]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Many-Objective optimization refers to optimizing the multi-objective optimization problems (MOPs) where the number of objectives is more than three. Most classical multi-objective evolutionary algorithms (MOEAs) use the Pareto dominance relation to guide the search and thus are hard to perform well in many-objective optimization problems. In this paper, a multi-objective evolutionary algorithm based on information separation (ISEA) is proposed. ISEA rotates the original coordinate system in the objective space, and makes the first axis parallel to the vector (1,1,…,1)T. The first member of the new coordinate is defined as convergence information, and the remaining members are defined as diversity information. Moreover, a neighborhood penalty mechanism based on layered selection is adopted using the information of the neighborhood shape made of two hyper-cones to maintain the diversity of individuals. The first hyper-cone is used to cover neighbors, and the second one to cover extreme individual whose convergence performs significantly worse than others. Additionally, after an individual is selected into the archive set, its neighbors are punished into an inferior layer. From comparative experiments with other representative MOEAs, including NNIA, e-MOEA, MSOPS, AR+DMO, and IBEA, the proposed algorithm is found to be successful in finding well-converged and well-distributed solution set.

    Reference
    [1] Deb K. Multi-Objective Optimization using Evolutionary Algorithms. Chichester: John Wiley & Sons, 2001.
    [2] Zheng JH. Multi-Objective evolutionary algorithms and applications. Beijing: Science Press, 2007 (in Chinese).
    [3] Gong MG, Jiao LC, Yang DD, Ma WP. Research on evolutionary multi-objective optimization algorithms. Ruan Jian Xue Bao/Journal of Softwave, 2009,20(2):271-289 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3483.htm [doi: 10.3724/SP.J.1001.2009.03483]
    [4] Coello CAC, Veldhuizen DAV, Lamont GB. Evolutionary Algorithms for Solving Multi-Objective Problems. New York: Kluwer Academic, 2002.
    [5] Coello CAC, Lamont GB. Applications of Multi-Objective Evolutionary Algorithms. Singapore: World Scientific Publisher, 2004.
    [6] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation, 2002,6(2):182-197. [doi: 10.1109/4235.996017]
    [7] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Proc. of the Evolutionary Methods for Design, Optimisation, and Control. Barcelona: CIMNE, 2002. 95-100.
    [8] Shi C, Li QY, Shi ZZ. A quick multi-objective evolutionary algorithm based on dominating tree. Ruan Jian Xue Bao/Journal of Softwave, 2007,18(3):505-516 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/18/505.htm [doi: 10.1360/jos 180505]
    [9] Li MQ, Yang SX, Zheng JH, Liu XH. ETEA: A euclidean minimum spanning tree-based evolutionary algorithm for multiobjective optimization. Evolutionary Computation, 2014,22(2):189-230. [doi: 10.1162/EVCO_a_00106]
    [10] Farina M, Amato P. On the optimal solution definition for many-criteria optimization problems. In: Proc. of the Annual Meeting of the North American Fuzzy Information Processing Society. IEEE, 2002. 233-238. [doi: 10.1109/NAFIPS.2002.1018061]
    [11] Ishibuchi H, Tsukamoto N, Nojima Y. Evolutionary many-objective optimization: A short review. In: Proc. of the IEEE Congress on Evolutionary Computation. IEEE, 2008. 2424-2431. [doi: 10.1109/CEC.2008.4631121]
    [12] Yang SX, Li MQ, Liu XH, Zheng JH. A grid-based evolutionary algorithm for many-objective optimization. IEEE Trans. on Evolutionary Computation, 2013,17(5):721-736. [doi: 10.1109/TEVC.2012.2227145]
    [13] Li MQ, Yang SX, Liu XH. A test problem for visual investigation of high-dimensional multi-objective search. In: Proc. of the IEEE Congress on Evolutionary Computation. IEEE, 2014. [doi: 10.1109/CEC.2014.6900306]
    [14] Adra SF, Fleming PJ. A diversity management operator for evolutionary many-objective optimisation. In: Proc. of the Evolutionary Multi-Criterion Optimization. Springer-Verlag, 2009. 81-94. [doi: 10.1007/978-3-642-01020-0_11]
    [15] Wagner T, Beume N, Naujoks B. Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In: Proc. of the Evolutionary Multi-Criterion Optimization. Springer-Verlag, 2007. 742-756. [doi: 10.1007/978-3-540-70928-2_56]
    [16] Li MQ, Yang SX, Liu XH. Shift-Based density estimation for Pareto-based algorithms in many-objective optimization. IEEE Trans. on Evolutionary Computation, 2014,18(3):348-365. [doi: 10.1109/TEVC.2013.2262178]
    [17] Hughes EJ. Fitness assignment methods for many-objective problems. In: Knowles J, et al., eds. Proc. of the Multiobjective Problem Solving from Nature. Springer-Verlag, 2008. 307-329. [doi: 10.1007/978-3-540-72964-8_15]
    [18] Purshouse RC, Fleming PJ. On the evolutionary optimization of many conflicting objectives. IEEE Trans. on Evolutionary Computation, 2007,11(6):770-784. [doi: 10.1109/TEVC.2007.910138]
    [19] Li MQ, Yang SX, Liu XH, Shen RM. A comparative study on evolutionary algorithms for many-objective optimization. In: Proc. of the Evolutionary Multi-Criterion Optimization. Springer-Verlag, 2013. 261-275. [doi: 10.1007/978-3-642-37140-0_22]
    [20] Purshouse RC, Fleming PJ. Evolutionary many-objective optimization: An exploratory analysis. In: Proc. of the IEEE Congress on Evolutionary Computation. IEEE, 2003. 2066-2073. [doi: 10.1109/CEC.2003.1299927]
    [21] Hughes EJ. Evolutionary many-objective optimisation: Many once or one many? In: Proc. of the IEEE Congress on Evolutionary Computation. IEEE, 2005. 222-227. [doi: 10.1109/CEC.2005.1554688]
    [22] Hajela P, Lin CY. Genetic search strategies in multicriterion optimal design. Structural and Multidisciplinary Optimization, 1992,4 (2):99-107. [doi: 10.1007/BF01759923]
    [23] Schaffer JD. Multiple objective optimization with vector evaluated genetic algorithms. In: Proc. of the 1st Int'l Conf. on Genetic Algorithms. Lawrence Erlbaum Associates, 1985. 93-100.
    [24] Corne DW, Knowles JD. Techniques for highly multiobjective optimisation: Some nondominated points are better than others. In: Proc. of the Genetic and Evolutionary Computation Conf. ACM, 2007. 773-780. [doi: 10.1145/1276958.1277115]
    [25] Knowles JD, Corne DW. Quantifying the effects of objective space dimension in evolutionary multiobjective optimization. In: Proc. of the Evolutionary Multi-Criterion Optimization. Springer-Verlag, 2007. 757-771. [doi: 10.1007/978-3-540-70928-2_57]
    [26] Mostaghim S, Schmeck H. Distance based ranking in many-objective particle swarm optimization. In: Proc. of the Parallel Problem Solving from Nature. Springer-Verlag, 2008. 753-762. [doi: 10.1007/978-3-540-87700-4_75]
    [27] Hughes EJ. Radar waveform optimisation as a many-objective application benchmark. In: Proc. of the Evolutionary Multi-Criterion Optimization. Springer-Verlag, 2007. 700-714. [doi: 10.1007/978-3-540-70928-2_53]
    [28] Di Pierro F. Many-Objective evolutionary algorithms and applications to water resources engineering [Ph.D. Thesis]. School of Engineering, Computer Science and Mathematics, University of Exeter, 2006.
    [29] Reed PM, Kollat JB. Save now, pay later? Multi-period many-objective groundwater monitoring design given systematic model errors and uncertainty. Advances in Water Resources, 2012,35:55-68. [doi: 10.1016/j.advwatres.2011.10.011]
    [30] Herrero JG, Berlanga A, López JMM. Effective evolutionary algorithms for many-specifications attainment: Application to air traffic control tracking filters. IEEE Trans. on Evolutionary Computation, 2009,13(1):151-168. [doi: 10.1109/TEVC.2008.920677]
    [31] Jaimes AL, Montaño AA, Coello CAC. Preference incorporation to solve many-objective airfoil design problems. In: Proc. of the IEEE Congress on Evolutionary Computation. IEEE, 2011. 1605-1612. [doi: 10.1109/CEC.2011.5949807]
    [32] Sülflow A, Drechsler N, Drechsler R. Robust multi-objective optimization in high dimensional spaces. In: Proc. of the Evolutionary Multi-Crierion Optimization. Springer-Verlag, 2007. [doi: 10.1007/978-3-540-70928-2_54]
    [33] Saxena DK, Duro JA, Tiwari A, Deb K, Zhang QF. Objective reduction in many-objective optimization: Linear and nonlinear algorithms. IEEE Trans. on Evolutionary Computation, 2013,17(1):77-99.
    [34] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, Part I: Solving problems with box constraints. IEEE Trans. on Evolutionary Computation, 2013,18(4):577-601. [doi: 10. 1109/TEVC.2013.2281535]
    [35] Bentley PJ, Wakefield JP. Finding acceptable Pareto-optimal solutions using multiobjective genetic algorithms. Soft Computing in Engineering Design and Manufacturing, 1997,5:231-240. [doi: 10.1007/978-1-4471-0427-8_25]
    [36] Zitzler E, Künzli S. Indicator-Based selection in multiobjective search. In: Proc. of the Parallel Problem Solving from Nature. Springer-Verlag, 2004. 832-842. [doi: 10.1007/978-3-540-30217-9_84]
    [37] Beume N, Naujoks B, Emmerich M. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 2007,181(3):1653-1669. [doi: 10.1016/j.ejor.2006.08.008]
    [38] Jaimes AL, Coello CAC. Study of preference relations in many-objective optimization. In: Proc. of the IEEE Congress on Evolutionary Computation. IEEE, 2009. 611-618. [doi: 10.1145/1569901.1569986]
    [39] Li MQ, Zheng JH, Li K, Yuan QZ, Shen RM. Enhancing diversity for average ranking method in evolutionary many-objective optimization. In: Proc. of the Parallel Problem Solving from Nature. Springer-Verlag, 2010. 647-656. [doi: 10.1007/978-3-642- 15844-5_65]
    [40] Karahan I, Köksalan M. A territory defining multiobjective evolutionary algorithms and preference incorporation. IEEE Trans. on Evolutionary Computation, 2010,14(4):636-664. [doi: 10.1109/TEVC.2009.2033586]
    [41] Bader J, Zitzler E. HypE: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation, 2011, 19(1):45-76. [doi: 10.1162/EVCO_a_00009]
    [42] Deb K, Thiele L, Laumanns M, Zitzler E. Scalable test problems for evolutionary multiobjective optimization. In: Abraham A, et al., eds. Proc. of the Evolutionary Multiobjective Optimization. Springer-Verlag, 2005. 105-145. [doi: 10.1007/1-84628-137-7_6]
    [43] Sato H, Aguirre HE, Tanaka K. Controlling dominance area of solutions and its impact on the performance of MOEAs. In: Proc. of the IEEE Congress on Evolutionary Computation. IEEE, 2007. 5-20. [doi: 10.1007/978-3-540-70928-2_5]
    [44] Zitzler E, Thiele L. Multiobjective optimization using evolutionary algorithms—A comparative case study. In: Proc. of the Parallel Problem Solving from Nature. Springer-Verlag, 1998. 292-301. [doi: 10.1007/BFb0056872]
    [45] Zitzler E. Evolutionary algorithms for multiobjective optimization: Methods and applications [Ph.D. Thesis]. Eidgenössische Technische Hochschule Zürich, Swiss Federal Institute of Technology, 1999.
    [46] Zheng JH, Jiang H, Kuang D, Shi ZZ. An approach of constructing multi-objective Pareto solutions using arena's principle. Ruan Jian Xue Bao/Journal of Softwave, 2007,18(6):1287-1297 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/18/ 1287.htm [doi: 10.1360/jos181287]
    [47] Gong MG, Jiao LC, Du HF, Bo LF. Multiobjective immune algorithm with nondominated neighbor-based selection. Evolutionary Computation, 2008,16(2):225-255. [doi: 10.1162/evco.2008.16.2.225]
    [48] Deb K, Mohan M, Mishra S. Evaluating the e-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions. Evolutionary Computation, 2005,13(4):501-525. [doi: 10.1162/106365605774666895]
    [49] Huband S, Hingston P, Barone L, While L. A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. on Evolutionary Computation, 2006,10(5):477-506. [doi: 10.1109/TEVC.2005.861417]
    [50] Li MQ, Yang SX, Liu XH. Diversity comparison of Pareto front approximations in many-objective optimization. IEEE Trans. on Cybernetics, 2014,44(12):2568-2584. [doi: 10.1109/TCYB.2014.2310651]
    [51] Veldhuizen DAV, Lamont GB. Evolutionary computation and convergence to a Pareto front. In: Proc. of the Late Breaking Papers at the Genetic Programming. Madison: Stanford University Bookstore, 1998. 221-228.
    [52] Bosman PAN, Thierens D. The balance between proximity and diversity in multi-objective evolutionary algorithms. IEEE Trans. on Evolutionary Computation, 2003,7(2):174-188. [doi: 10.1109/TEVC.2003.810761]
    [53] Deb K, Jain S. Running performance metrics for evolutionary multi-objective optimization. In: Proc. of the Asia-Pacific Conf. on Simulated Evolution and Learning. Singapore City: Orchid Country Club, 2002. 13-20.
    [54] Glaser RE. Levene's robust test of homogeneity of variances. In: Proc. of the Encyclopedia of Statistical Sciences, Vol.4. New York: Wiley, 1983. 608-610.
    [55] Tukey JW. A quick, compact, two-sample test to Duckworth's specifications. Technometrics, 1959,1(1):31-48.
    [56] Tamhane AC. Multiple comparisons in model I one-way ANOVA with unequal variances. Communications in Statistics, 1977,A6 (1):15-32. [doi: 10.1080/03610927708827466]
    [57] Inselberg A. The plane with parallel coordinates. The Visual Computer, 1985,1(4):69-91. [doi: 10.1007/BF01898350]
    [58] Inselberg A, Dimsdale B. Parallel coordinates: A tool for visualizing multi-dimensional geometry. In: Proc. of the IEEE Conf. on Visualization. IEEE, 1990. 361-378. [doi: 10.1109/VISUAL.1990.146402]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

郑金华,申瑞珉,李密青,邹娟.一种基于信息分离的高维多目标进化算法.软件学报,2015,26(5):1013-1036

Copy
Share
Article Metrics
  • Abstract:3776
  • PDF: 5886
  • HTML: 1816
  • Cited by: 0
History
  • Received:September 06,2013
  • Revised:July 01,2014
  • Online: May 06,2015
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2043770Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063