Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/2330163.2330232acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

Effects of discrete objective functions with different granularities on the search behavior of EMO algorithms

Published: 07 July 2012 Publication History

Abstract

Objective functions in combinatorial optimization are discrete. The number of possible values of a discrete objective function is totally different from problem to problem. Optimization of a discrete objective function is often very difficult. In the case of multiobjective optimization, a different objective function has a different number of possible values. This means that each axis of the objective space has a different granularity. Some axes may have fine granularities while others are coarse. In this paper, we examine the effect of discrete objective functions with different granularities on the search behavior of EMO (evolutionary multiobjective optimization) algorithms through computational experiments. Experimental results show that a discrete objective function with a coarse granularity slows down the search of EMO algorithms along that objective. An interesting observation is that such a slow-down along one objective often leads to the speed-up of the search along other objectives. We also examine the effect of adding a small random noise to each discrete objective function in order to increase the number of possible objective values.

References

[1]
Korte, B., and Vygen, J. Combinatorial Optimization: Theory and Algorithms (Fourth Edition). Springer, Berlin (2010).
[2]
Beume, N., Naujoks, B., and Emmerich, M. SMS-EMOA: multiobjective selection based on dominated hypervolume. European Journal of Operational Research 181, 3 (2007) 1653--1669.
[3]
Blum, C., and Roli, A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35, 3 (2003) 268--308.
[4]
Coello, C. A. C., and Lamont, G. B. Applications of Multi-Objective Evolutionary Algorithms. World Scientific, Singapore (2004).
[5]
Coello, C. A. C., Van Veldhuizen, D. A., and Lamont, G. B. Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer, Boston (2002).
[6]
Deb, K. Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons, Chichester (2001).
[7]
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation 6, 2 (2002) 182--197.
[8]
Giel, O., and Lehre, P. K. On the effect of populations in evolutionary multi-objective optimisation. Evolutionary Computation 18, 3(2010) 335--356.
[9]
Harvey, I., and Thompson, A. Through the labyrinth evolution finds a way: A silicon ridge. Lecture Notes in Computer Science 1259: ICES 1996, 406--422.
[10]
Horoba, C., and Neumann, F. Benefits and drawbacks for the use of epsilon-dominance in evolutionary multi-objective optimization. Proc. of 2008 Genetic and Evolutionary Computation Conference (2008) 641--648.
[11]
Jansen, T., and Wegener, I. Evolutionary algorithms - How to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Trans. on Evolutionary Computation 5, 6 (2001) 589--599.
[12]
Jaszkiewicz, A. On the performance of multiple-objective genetic local search on the 0/1 knapsack problem - A comparative experiment. IEEE Trans. on Evolutionary Computation 6, 4 (2002) 402--412.
[13]
Jaszkiewicz, A. On the computational efficiency of multiple objective metaheuristics. The knapsack problem case study. European Journal of Operational Research 158, 2 (2004) 418--433.
[14]
Katada, Y., and Ohkura, K. Analysis on topologies of fitness landscapes with both neutrality and ruggedness based on neutral networks. Proc. of 2009 Genetic and Evolutionary Computation Conference (2009) 1855--1856.
[15]
Nojima, Y., Narukawa, K., Kaige, S., and Ishibuchi, H. Effects of removing overlapping solutions on the performance of the NSGA-II Algorithm. Lecture Notes in Computer Science 3410: EMO 2005, 341--354.
[16]
Papadimitriou, C. H., and Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity. Dover, Mineola (1998).
[17]
Wagner, T., Beume, N., and Naujoks, B. Pareto-, aggregation-, and indicator-based methods in many-objective optimization. Lecture Notes in Computer Science 4403: EMO 2007, 742--756.
[18]
Zhang, Q., and Li, H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation 11, 6 (2007) 712--731.
[19]
Zitzler, E., Brockhoff, D., and Thiele, L. The hypervolume indicator revisited: On the design of Pareto-compliant indicators via weighted integration. Lecture Notes in Computer Science 4403: EMO 2007, 862--876.
[20]
Zitzler, E., and Künzli, S. Indicator-based selection in multiobjective search. Lecture Notes in Computer Science 3242: PPSN VIII (2004) 832--842.
[21]
Zitzler, E., Laumanns, M., and Thiele, L. SPEA2: Improving the strength Pareto evolutionary algorithm, TIK-Report 103, Computer Engineering and Networks Laboratory (TIK), ETH, Zurich (2001).
[22]
Zitzler, E., and Thiele, L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Trans. on Evolutionary Computation 3, 4 (1999) 257--271.

Cited By

View all
  • (2019)Effects of Discretization of Decision and Objective Spaces on the Performance of Evolutionary Multi-objective Optimization Algorithms2019 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI44817.2019.9002906(1826-1833)Online publication date: Dec-2019
  • (2018)Efficient search techniques using adaptive discretization of design variables on real-coded evolutionary computationsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205636(697-704)Online publication date: 2-Jul-2018
  • (2016)Effects of discrete design-variable precision on real-coded Genetic Algorithm2016 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2016.7850230(1-8)Online publication date: Dec-2016
  • Show More Cited By

Index Terms

  1. Effects of discrete objective functions with different granularities on the search behavior of EMO algorithms

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation
    July 2012
    1396 pages
    ISBN:9781450311779
    DOI:10.1145/2330163
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 07 July 2012

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. combinatorial optimization
    2. discrete objective functions
    3. evolutionary multiobjective optimization (emo)
    4. genetic algorithms

    Qualifiers

    • Research-article

    Conference

    GECCO '12
    Sponsor:
    GECCO '12: Genetic and Evolutionary Computation Conference
    July 7 - 11, 2012
    Pennsylvania, Philadelphia, USA

    Acceptance Rates

    Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)3
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 27 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)Effects of Discretization of Decision and Objective Spaces on the Performance of Evolutionary Multi-objective Optimization Algorithms2019 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI44817.2019.9002906(1826-1833)Online publication date: Dec-2019
    • (2018)Efficient search techniques using adaptive discretization of design variables on real-coded evolutionary computationsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205636(697-704)Online publication date: 2-Jul-2018
    • (2016)Effects of discrete design-variable precision on real-coded Genetic Algorithm2016 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2016.7850230(1-8)Online publication date: Dec-2016
    • (2015)Unwanted Feature Interactions Between the Problem and Search Operators in Evolutionary Multi-objective OptimizationEvolutionary Multi-Criterion Optimization10.1007/978-3-319-15934-8_2(19-33)Online publication date: 18-Mar-2015
    • (2013)Difficulty in Evolutionary Multiobjective Optimization of Discrete Objective Functions with Different GranularitiesEvolutionary Multi-Criterion Optimization10.1007/978-3-642-37140-0_20(230-245)Online publication date: 2013

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media