More Web Proxy on the site http://driver.im/

research-article

Maximizing population diversity in single-objective optimization

Authors:

Lothar ThieleAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 641 - 648

https://doi.org/10.1145/2001576.2001665

Published: 12 July 2011 Publication History

Abstract

Typically, optimization attempts to find a solution which minimizes the given objective function. But often, it might also be useful to obtain a set of structurally very diverse solutions which all have acceptable objective values. With such a set, a decision maker would be given a choice of solutions to select from. In addition, he can learn about the optimization problem at hand by inspecting the diverse close-to-optimal solutions. This paper proposes NOAH, an evolutionary algorithm which solves a mixed multi-objective problem: Determine a maximally diverse set of solutions whose objective values are below a provided objective barrier. It does so by iteratively switching between objective value and set-diversity optimization while automatically adapting a constraint on the objective value until it reaches the barrier. Tests on an nk-Landscapes problem and a 3-Sat problem as well as on a more realistic bridge construction problem show that the algorithm is able to produce high quality solutions with a significantly higher structural diversity than standard evolutionary algorithms.

References

[1]

J. Bader. Hypervolume-Based Search for Multiobjective Optimization: Theory and Methods. PhD thesis, ETH Zurich, Switzerland, 2010.

[2]

D. Beasley, D. Bull, and R. Martin. A sequential niche technique for multimodal function optimization. Evol. Comput., 1:101--125, 1993.

Digital Library

[3]

L. Bui, J. Branke, and H. Abbass. Multiobjective optimization for dynamic environments. In CEC, 2005.

[4]

W. J. Conover. Practical Nonparametric Statistics. John Wiley, 3rd edition, 1999.

[5]

K. A. de Jong. An Analysis of the Behaviour of a Class of Genetic Adaptive Systems. PhD thesis, 1975.

Digital Library

[6]

K. Deb. Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, 2001.

Digital Library

[7]

K. Deb and D. E. Goldberg. An investigation of niche and species formation in genetic function optimization. In Third international conference on Genetic algorithms, 1989.

Digital Library

[8]

K. Deb and S. Tiwari. Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization. EJOR, 185(3):1062--1087, 2008.

[9]

A. E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. Springer, 2003.

Digital Library

[10]

D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. In Second International Conference on Genetic algorithms and their application, 1987.

Digital Library

[11]

G. Harik. Finding multimodal solutions using restricted tournament selection. In Sixth International Conference on Genetic Algorithms, 1995.

Digital Library

[12]

Y. Jin and J. Branke. Evolutionary optimization in uncertain environments-a survey. Evol. Comput., 9(3):303 -- 317, 2005.

Digital Library

[13]

S. A. Kauffman. Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, 1993.

[14]

S. W. Mahfoud. Crowding and preselection revisited. In PPSN, 1992.

[15]

D. Mitchell, B. Selman, and H. Levesque. Hard and easy distributions of sat problems. In AAAI, 1992. In Tenth National Conference on Artificial Intelligence, 1992.

Digital Library

[16]

A. Petrowski. A clearing procedure as a niching method for genetic algorithms. In IEEE International Conference on Evolutionary Computation, 1996.

[17]

A. Saha and K. Deb. A bi-criterion approach to multimodal optimization: Self-adaptive approach. In SEAL, 2010.

Digital Library

[18]

A. R. Solow and S. Polasky. Measuring bilological diversity. Environmental and Ecological Statistics, 1:95--103, 1994.

[19]

T. Ulrich, J. Bader, and L. Thiele. Defining and optimizing indicator-based diversity measures in multiobjective search. In PPSN, 2010.

Digital Library

[20]

X. Yu and M. Gen. Introduction to Evolutionary Algorithms. Springer, 2010.

Digital Library

Cited By

Nikfarjam ANeumann ANeumann F(2024)On the Use of Quality Diversity Algorithms for the Travelling Thief ProblemACM Transactions on Evolutionary Learning and Optimization10.1145/3641109Online publication date: 17-Jan-2024
https://doi.org/10.1145/3641109
Schmidbauer MOpris ABossek JNeumann FSudholt DLi XHandl J(2024)Guiding Quality Diversity on Monotone Submodular Functions: Customising the Feature Space by Adding Boolean ConjunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654160(1614-1622)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654160
Antipov DNeumann ANeumann FLi XHandl J(2024)A Detailed Experimental Analysis of Evolutionary Diversity Optimization for OneMinMaxProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654082(467-475)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654082
Show More Cited By

Index Terms

Maximizing population diversity in single-objective optimization
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Runtime analysis for maximizing population diversity in single-objective optimization
GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

Recently Ulrich and Thiele [14] have introduced evolutionary algorithms for the mixed multi-objective problem of maximizing fitness as well as diversity in the decision space. Such an approach allows to generate a diverse set of solutions which are all ...
Integrating decision space diversity into hypervolume-based multiobjective search
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Multiobjective optimization in general aims at learning about the problem at hand. Usually the focus lies on objective space properties such as the front shape and the distribution of optimal solutions. However, structural characteristics in the ...
A multi-population evolutionary algorithm with single-objective guide for many-objective optimization
Abstract
This paper develops a multi-population evolutionary algorithm with single-objective guide to tackle many-objective optimization problems. It exploits the merits of both multiple populations and single-objective optimization to balance ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 ACM.

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

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

diversity in decision space

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
352
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)4

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nikfarjam ANeumann ANeumann F(2024)On the Use of Quality Diversity Algorithms for the Travelling Thief ProblemACM Transactions on Evolutionary Learning and Optimization10.1145/3641109Online publication date: 17-Jan-2024
https://doi.org/10.1145/3641109
Schmidbauer MOpris ABossek JNeumann FSudholt DLi XHandl J(2024)Guiding Quality Diversity on Monotone Submodular Functions: Customising the Feature Space by Adding Boolean ConjunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654160(1614-1622)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654160
Antipov DNeumann ANeumann FLi XHandl J(2024)A Detailed Experimental Analysis of Evolutionary Diversity Optimization for OneMinMaxProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654082(467-475)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654082
Zanartu FTreude CWagner MLi XHandl J(2024)Socialz: Multi-Feature Social Fuzz TestingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654033(1445-1453)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654033
Bossek JSudholt D(2024)Runtime Analysis of Quality Diversity AlgorithmsAlgorithmica10.1007/s00453-024-01254-z86:10(3252-3283)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00453-024-01254-z
Do AGuo MNeumann ANeumann F(2024)Evolutionary Multi-objective Diversity OptimizationParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70085-9_8(117-134)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70085-9_8
Antipov DNeumann ANeumann F(2024)Local Optima in Diversity Optimization: Non-trivial Offspring Population is EssentialParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_12(181-196)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_12
Gadea Harder JNeumann ANeumann F(2024)Analysis of Evolutionary Diversity Optimisation for the Maximum Matching ProblemParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_10(149-165)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70071-2_10
Preuß ORook JTrautmann H(2024)On the Potential of Multi-objective Automated Algorithm Configuration on Multi-modal Multi-objective Optimisation ProblemsApplications of Evolutionary Computation10.1007/978-3-031-56852-7_20(305-321)Online publication date: 3-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-56852-7_20
Antipov DNeumann ANeumann F(2023)Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMaxProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607135(3-14)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607135
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents