research-article

An Algorithm for Many-Objective Optimization With Reduced Objective Computations: A Study in Differential Evolution

Authors:

Sanghamitra Bandyopadhyay,

Arpan MukherjeeAuthors Info & Claims

IEEE Transactions on Evolutionary Computation, Volume 19, Issue 3

Pages 400 - 413

https://doi.org/10.1109/TEVC.2014.2332878

Published: 01 June 2015 Publication History

Abstract

In this paper we have developed an algorithm for many-objective optimization problems, which will work more quickly than existing ones, while offering competitive performance. The algorithm periodically reorders the objectives based on their conflict status and selects a subset of conflicting objectives for further processing. We have taken differential evolution multiobjective optimization (DEMO) as the underlying metaheuristic evolutionary algorithm, and implemented the technique of selecting a subset of conflicting objectives using a correlation-based ordering of objectives. The resultant method is called α-DEMO, where α is a parameter determining the number of conflicting objectives to be selected. We have also proposed a new form of elitism so as to restrict the number of higher ranked solutions that are selected in the next population. The α-DEMO with the revised elitism is referred to as α-DEMO-revised. Extensive results of the five DTLZ functions show that the number of objective computations required in the proposed algorithm is much less compared to the existing algorithms, while the convergence measures are competitive or often better. Statistical significance testing is also performed. A real-life application on structural optimization of factory shed truss is demonstrated.

References

[1]

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, Apr. 2002.

Digital Library

[2]

D. W. Corne, J. D. Knowles, and M. J. Oates, “The Pareto envelope-based selection algorithm for multiobjective optimization,” in Proc. Parallel Problem Solving Nature VI Conf., Berlin, Germany, 2002, pp. 839–848.

[3]

E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization,” in Evolutionary Methods for Design, Optimisation, and Control. Barcelona, Spain: CIMNE, 2002, pp. 95–100.

[4]

D. W. Corne and J. D. Knowles, “Techniques for highly multiobjective optimisation: Some nondominated points are better than others,” in Proc. 9th Annu. Conf. Genet. Evol. Comput., London, U.K., 2007, pp. 773–780.

[5]

M. Farina and P. Amato, “On the optimal solution definition for many-criteria optimization problems,” in Proc. Int. Conf. North Amer. Fuzzy Inf. Process. Soc. (NAFIPS-FLINT), Piscataway, NJ, USA, Jun. 2002, pp. 233–238.

[6]

R. C. Purshouse and P. J. Fleming, “Evolutionary many-objective optimisation: An exploratory analysis,” in Proc. Congr. Evol. Comput. (CEC), vol. 3. 2003, pp. 2066–2073.

[7]

V. Khare, X. Yao, and K. Deb, “Performance scaling of multi-objective evolutionary algorithms,” in Evolutionary Multi-Criterion Optimization. Berlin, Germany: Springer, 2003, pp. 376–390.

[8]

H. Ishibuchi, N. Tsukamoto, and Y. Nojima, “Evolutionary many-objective optimization,” in Proc. 3rd Int. Workshop Genet. Evol. Syst. (GEFS), Witten, Germany, 2008, pp. 47–52.

[9]

E. J. Hughes, “Evolutionary many-objective optimisation: Many once or one many?” in Proc. 2005 IEEE Congr. Evol. Comput., vol. 1. Edinburgh, U.K., pp. 222–227.

[10]

I. Alberto, C. Azcárate, F. Mallor, and P. M. Mateo, “Optimization with simulation and multiobjective analysis in industrial decision-making: A case study,” Eur. J. Oper. Res., vol. 140, no. 2, pp. 373–383, 2002.

[11]

L. V. Santana-Quintero, “A review of techniques for handling expensive functions in evolutionary multi-objective optimization,” in Computational Intelligence in Expensive Optimization Problems. Berlin, Germany: Springer, 2010, pp. 29–59.

[12]

E. J. Hughes, “MSOPS-II: A general-purpose many-objective optimiser,” in Proc. IEEE Congr. Evol. Comput., (CEC), Singapore, 2007, pp. 3944–3951.

[13]

E. J. Hughes, “Multiple single objective Pareto sampling,” in Proc. 2003 Congr. Evol. Comput. (CEC), vol. 4. pp. 2678–2684.

[14]

G. Wang and J. Wu, “A new fuzzy dominance GA applied to solve many-objective optimization problem,” in Proc. 2nd Int. Conf. Innovat. Comput., Inf. Control (ICICIC), Kumamoto, Japan, 2007, p. 617.

[15]

S. Bandyopadhyay, S. K. Pal, and B. Aruna, “Multiobjective gas, quantitative indices, and pattern classification,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 34, no. 5, pp. 2088–2099, Oct. 2004.

Digital Library

[16]

J. Bader and E. Zitzler, “HypE: An algorithm for fast hypervolume-based many-objective optimization,” Evol. Comput., vol. 19, no. 1, pp. 45–76, 2011.

[17]

X. Zou, Y. Chen, M. Liu, and L. Kang, “A new evolutionary algorithm for solving many-objective optimization problems,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 38, no. 5, pp. 1402–1412, Oct. 2008.

Digital Library

[18]

T. Aittokoski and K. Miettinen, “Efficient evolutionary approach to approximate the Pareto-optimal set in multiobjective optimization, UPS-EMOA,” Optim. Methods Softw., vol. 25, no. 6, pp. 841–858, 2010.

Digital Library

[19]

M. Garza-Fabre, G. Toscano-Pulido, and C. A. C. Coello, “Two novel approaches for many-objective optimization,” in Proc. IEEE Congr. Evol. Comput. (CEC), Barcelona, Spain, 2010, pp. 1–8.

[20]

S. F. Adra and P. J. Fleming, “Diversity management in evolutionary many-objective optimization,” IEEE Trans. Evol. Comput., vol. 15, no. 2, pp. 183–195, Apr. 2011.

Digital Library

[21]

K. Deb and H. Jain, “Handling many-objective problems using an improved NSGA-II procedure,” in Proc. 2012 IEEE Congr. Evol. Comput. (CEC), Brisbane, QLD, Australia, pp. 1–8.

[22]

H. Jain and K. Deb, “An improved adaptive approach for elitist nondominated sorting genetic algorithm for many-objective optimization,” in Proc. Evol. Multi-Criterion Optim. (EMO), Sheffield, U.K., 2013, pp. 307–321.

[23]

M. Garza-Fabre, G. Toscano-Pulido, and C. A. C. Coello, “Two novel approaches for many-objective optimization,” in Proc. 2010 IEEE Congr. Evol. Comput. (CEC), Barcelona, Spain, pp. 1–8.

[24]

A. B. de Carvalho and A. Pozo, “The control of dominance area in particle swarm optimization algorithms for many-objective problems,” in Proc. 2010 11th Brazilian Symp. Neural Netw. (SBRN), Sao Paulo, Brazil, pp. 140–145.

[25]

Z. Kang, L. Kang, C. Li, Y. Chen, and M. Liu, “Convergence properties of E-optimality algorithms for many objective optimization problems,” in Proc. (IEEE World Congr. Comput. Intell.) IEEE Congr. Evol. Comput. (CEC), Hong Kong, 2008, pp. 472–477.

[26]

M. Laumanns, L. Thiele, K. Deb, and E. Zitzler, “Combining convergence and diversity in evolutionary multiobjective optimization,” Evol. Comput., vol. 10, no. 3, pp. 263–282, 2002.

Digital Library

[27]

J. Molina, L. V. Santana, A. G. Hernández-Díaz, C. A. C. Coello, and R. Caballero, “g-dominance: Reference point based dominance for multiobjective metaheuristics,” Eur. J. Oper. Res., vol. 197, no. 2, pp. 685–692, 2009.

[28]

R. C. Purshouse and P. J. Fleming, “Conflict, harmony, and independence: Relationships in evolutionary multi-criterion optimisation,” in Evolutionary Multi-Criterion Optimization. Berlin, Germany: Springer, 2003, pp. 16–30.

Digital Library

[29]

R. C. Purshouse and P. J. Fleming, “On the evolutionary optimization of many conflicting objectives,” IEEE Trans. Evol. Comput., vol. 11, no. 6, pp. 770–784, Dec. 2007.

Digital Library

[30]

K. Deb and D. K. Saxena, “On finding Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems,” Kanpur Genet. Algorithms Lab., Indian Inst. Technol. Kanpur, Kanpur, India, KanGAL Rep. 2005011, 2005.

[31]

Q. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Trans. Evol. Comput., vol. 11, no. 6, pp. 712–731, Dec. 2007.

Digital Library

[32]

H. K. Singh, A. Isaacs, and T. Ray, “A Pareto corner search evolutionary algorithm and dimensionality reduction in many-objective optimization problems,” IEEE Trans. Evol. Comput., vol. 15, no. 4, pp. 539–556, Aug. 2011.

Digital Library

[33]

D. Brockhoff and E. Zitzler, “Objective reduction in evolutionary multiobjective optimization: Theory and applications,” Evol. Comput., vol. 17, no. 2, pp. 135–166, 2009.

Digital Library

[34]

T. Murata and A. Taki, “Examination of the performance of objective reduction using correlation-based weighted-sum for many objective knapsack problems,” in Proc. 2010 10th Int. Conf. Hybrid Intell. Syst. (HIS), pp. 175–180.

[35]

A. L. Jaimes, C. A. C. Coello, and J. E. U. Barrientos, “Online objective reduction to deal with many-objective problems,” in Evolutionary Multi-Criterion Optimization. Berlin, Germany: Springer, 2009, pp. 423–437.

[36]

A. Sinha, D. K. Saxena, K. Deb, and A. Tiwari, “Using objective reduction and interactive procedure to handle many-objective optimization problems,” Appl. Soft Comput., vol. 13, no. 1, pp. 415–427, Jan. 2013.

Digital Library

[37]

T. Robič and B. Filipič, “DEMO: Differential evolution for multiobjective optimization,” in Evolutionary Multi-Criterion Optimization. Berlin, Germany: Springer, 2005, pp. 520–533.

Digital Library

[38]

A. Arias-Montano, C. A. C. Coello, and E. Mezura Montes, “Multiobjective evolutionary algorithms in aeronautical and aerospace engineering,” IEEE Trans. Evol. Comput., vol. 16, no. 5, pp. 662–694, Oct. 2012.

Digital Library

[39]

K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms. New York, NY, USA: Wiley, 2001.

Digital Library

[40]

C. A. C. Coello, G. B. Lamont, and D. A. V. Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems. New York, NY, USA: Springer, 2007.

Digital Library

[41]

C. Buchta, “On the average number of maxima in a set of vectors,” Inf. Process. Lett., vol. 33, no. 2, pp. 63–65, 1989.

Digital Library

[42]

R. Storn and K. Price, “Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces,” J. Global Optim., vol. 11, no. 4, pp. 341–359, 1997.

Digital Library

[43]

K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, “Scalable multi-objective optimization test problems,” in Proc. Congr. Evol. Comput. (CEC), Honolulu, HI, USA, 2002, pp. 825–830.

[44]

E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. Da Fonseca, “Performance assessment of multiobjective optimizers: An analysis and review,” IEEE Trans. Evol. Comput., vol. 7, no. 2, pp. 117–132, Apr. 2003.

Digital Library

[45]

E. Zitzler, D. Brockhoff, and L. Thiele, “The hypervolume indicator revisited: On the design of Pareto-compliant indicators via weighted integration,” in Evolutionary Multi-Criterion Optimization. Berlin, Germany: Springer, 2007, pp. 862–876.

[46]

K. Bringmann and T. Friedrich, “Approximation quality of the hypervolume indicator,” Artif. Intell., vol. 195, pp. 265–290, Feb. 2013.

Digital Library

[47]

J. R. Schott, “Fault tolerant design using single and multicriteria genetic algorithm optimization,” Ph.D. dissertation, Dept. Aeronaut. Astronaut., Massachusetts Inst. Technol., Cambridge, MA, USA, 1995.

[48]

R. Hernández Gómez and C. A. C. Coello, “MOMBI: A new metaheuristic for many-objective optimization based on the R2 indicator,” in Proc. 2013 IEEE Conf. Evol. Comput., vol. 1. pp. 2488–2495.

[49]

D. Brockhoff, T. Wagner, and H. Trautmann, “On the properties of the R2 indicator,” in Proc. 14th Int. Conf. Genet. Evol. Comput. Conf., Philadelphia, PA, USA, 2012, pp. 465–472.

[50]

S. Huband, L. Barone, L. While, and P. Hingston, “A scalable multi-objective test problem toolkit,” in Evolutionary Multi-Criterion Optimization. Guanajuato, Mexico: Springer, 2005, pp. 280–295.

Digital Library

[51]

F. Y. Cheng and D. Li, “Multiobjective optimization design with Pareto genetic algorithm,” J. Struct. Eng., vol. 123, no. 9, pp. 1252–1261, 1997.

[52]

S. Narayanan and S. Azarm, “On improving multiobjective genetic algorithms for design optimization,” Struct. Optim., vol. 18, nos. 2–3, pp. 146–155, 1999.

[53]

W. A. Crossley, A. M. Cook, and D. W. Fanjoy, “Using the two-branch tournament genetic algorithm for multiobjective design,” AIAA J., vol. 37, no. 2, pp. 261–267, 1999.

[54]

C. Dhaenens, J. Lemesre, N. Melab, M. Mezmaz, and E.-G. Talbi, “Parallel exact methods for multiobjective combinatorial optimization,” in Parallel Combinatorial Optimization. Hoboken, NJ, USA: Wiley, 2006, pp. 187–210.

[55]

S. R. Norris and W. A. Crossley, “Pareto-optimal controller gains generated by a genetic algorithm,” in Proc. AIAA 36th Aerospace Sci. Meeting Exhibit, 1998, Art. ID.

[56]

E. Sandgren, “Multicriteria design optimization by goal programming,” in Advances in Design Optimization. London, U.K.: Chapman & Hall, 1994, pp. 225–265.

[57]

S. Yang, M. Li, X. Liu, and J. Zheng, “A grid-based evolutionary algorithm for many-objective optimization,” IEEE Trans. Evol. Comput., vol. 17, no. 5, pp. 721–736, Oct. 2013.

Digital Library

[58]

R. Denysiuk, L. Costa, and I. Espírito Santo, “Many-objective optimization using differential evolution with variable-wise mutation restriction,” in Proc. 15th Annu. Conf. Genet. Evol. Comput. Conf., 2013, pp. 591–598.

[59]

D. Martin, A. Rosete, J. Alcala-Fdez, and F. Herrera, “A new multi-objective evolutionary algorithm for mining a reduced set of interesting positive and negative quantitative association rules,” IEEE Trans. Evol. Comput., vol. 18, no. 1, pp. 54–69, Feb. 2014.

[60]

K. Deb and H. Jain, “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., vol. 18, no. 4, pp. 577–601, Aug. 2014.

[61]

H. Jain and K. Deb, “An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part II: Handling constraints and extending to an adaptive approach,” IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 602–622, Aug. 2014.

[62]

Z. He, G. G. Yen, and J. Zhang, “Fuzzy-based Pareto optimality for many-objective evolutionary algorithms,” IEEE Trans. Evol. Comput., vol. 18, no. 2, pp. 269–285, Apr. 2014.

Digital Library

[63]

H. Karshenas, R. Santana, C. Bielza, and P. Larrañaga Múgica, “Multi-objective estimation of distribution algorithm based on joint modeling of objectives and variables,” IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 519–542, Aug. 2014.

Cited By

Song QLu CSong QJiang HLiu B(2024)Research on extreme obstacle–crossing performance and multi–objective optimization of tracked mobile robotRobotics and Autonomous Systems10.1016/j.robot.2024.104759180:COnline publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1016/j.robot.2024.104759
Li GWang ZZhang QSun J(2023)Offline and Online Objective Reduction via Gaussian Mixture Model ClusteringIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.316883627:2(341-354)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3168836
Gong GDeng QGong XHuang D(2021)A non-dominated ensemble fitness ranking algorithm for multi-objective flexible job-shop scheduling problem considering worker flexibility and green factorsKnowledge-Based Systems10.1016/j.knosys.2021.107430231:COnline publication date: 14-Nov-2021
https://dl.acm.org/doi/10.1016/j.knosys.2021.107430
Show More Cited By

Index Terms

An Algorithm for Many-Objective Optimization With Reduced Objective Computations: A Study in Differential Evolution

Index terms have been assigned to the content through auto-classification.

Recommendations

Approximate non-dominated sorting for evolutionary many-objective optimization

Non-dominated sorting has widely been adopted and shown to be very effective in dominance based evolutionary multi-objective optimization where the number of objectives is two or three. In dealing with many-objective optimization problems, where the ...
Bi-goal evolution for many-objective optimization problems

This paper presents a meta-objective optimization approach, called Bi-Goal Evolution (BiGE), to deal with multi-objective optimization problems with many objectives. In multi-objective optimization, it is generally observed that 1) the conflict between ...
Objective reduction for many-objective optimization problems using objective subspace extraction

Multi-objective evolutionary algorithms (MOEAs) have shown their effectiveness in exploring a well converged and diversified approximation set for multi-objective optimization problems (MOPs) with 2 and 3 objectives. However, most of them perform poorly ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Evolutionary Computation

IEEE Transactions on Evolutionary Computation Volume 19, Issue 3

June 2015

152 pages

ISSN:1089-778X

Issue’s Table of Contents

Copyright © 2014.

Publisher

IEEE Press

Publication History

Published: 01 June 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Song QLu CSong QJiang HLiu B(2024)Research on extreme obstacle–crossing performance and multi–objective optimization of tracked mobile robotRobotics and Autonomous Systems10.1016/j.robot.2024.104759180:COnline publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1016/j.robot.2024.104759
Li GWang ZZhang QSun J(2023)Offline and Online Objective Reduction via Gaussian Mixture Model ClusteringIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.316883627:2(341-354)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3168836
Gong GDeng QGong XHuang D(2021)A non-dominated ensemble fitness ranking algorithm for multi-objective flexible job-shop scheduling problem considering worker flexibility and green factorsKnowledge-Based Systems10.1016/j.knosys.2021.107430231:COnline publication date: 14-Nov-2021
https://dl.acm.org/doi/10.1016/j.knosys.2021.107430
Zhou JZou JYang SZheng JGong DPei T(2021)Niche-based and angle-based selection strategies for many-objective evolutionary optimizationInformation Sciences: an International Journal10.1016/j.ins.2021.04.050571:C(133-153)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1016/j.ins.2021.04.050
Lin JZheng SLong Y(2020)Improved Reference Vector Guided Differential Evolution Algorithm for Many-Objective OptimizationProceedings of the 2020 5th International Conference on Mathematics and Artificial Intelligence10.1145/3395260.3395268(43-49)Online publication date: 10-Apr-2020
https://dl.acm.org/doi/10.1145/3395260.3395268
Mousavirad SRahnamayan S(2020)A Novel Center-based Differential Evolution Algorithm2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185622(1-8)Online publication date: 19-Jul-2020
https://dl.acm.org/doi/10.1109/CEC48606.2020.9185622
Qiao JLi FYang SYang CLi WGu K(2020)An adaptive hybrid evolutionary immune multi-objective algorithm based on uniform distribution selectionInformation Sciences: an International Journal10.1016/j.ins.2019.08.032512:C(446-470)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1016/j.ins.2019.08.032
Ma LWang RChen SCheng SWang XLin ZShi YHuang M(2020)A novel many-objective evolutionary algorithm based on transfer matrix with Kriging modelInformation Sciences: an International Journal10.1016/j.ins.2019.01.030509:C(437-456)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1016/j.ins.2019.01.030
Zhou AWang YZhang J(2020)Objective extraction via fuzzy clustering in evolutionary many-objective optimizationInformation Sciences: an International Journal10.1016/j.ins.2018.11.032509:C(343-355)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1016/j.ins.2018.11.032
Zhao HZhang C(2020)A decomposition-based many-objective artificial bee colony algorithm with reinforcement learningApplied Soft Computing10.1016/j.asoc.2019.10587986:COnline publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1016/j.asoc.2019.105879
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents