research-article

On the utility of the population size for inversely fitness proportional mutation rates

Author:

Christine ZargesAuthors Info & Claims

FOGA '09: Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms

Pages 39 - 46

https://doi.org/10.1145/1527125.1527132

Published: 09 January 2009 Publication History

Abstract

Artificial Immune Systems (AIS) are an emerging new field of research in Computational Intelligence that are used in many areas of application, e. g. optimization, anomaly detection and classification. For optimization tasks usually hypermutation operators are used. In this paper, we show that the use of populations can be essential for the utility of such operators by analyzing the runtime of a simple population-based immune inspired algorithm on a classical example problem. The runtime bounds we prove are tight for the problem at hand. Moreover, we derive some general characteristics of the considered mutation operator as well as properties of the population, which hold for a class of pseudo-Boolean functions.

References

[1]

F. M. Burnet. The Clonal Selection Theory of Acquired Immunity. Cambridge University Press, 1959.

[2]

E. Clark, A. Hone, and J. Timmis. A Markov chain model of the b-cell algorithm. In International Conference on Artificial Immune Systems (ICARIS), pages 318--330. Springer, 2005.

Digital Library

[3]

N. C. Cortés and C. A. C. Coello. Multiobjective optimization using ideas from the clonal selection principle. In Genetic and Evolutionary Computation Conference (GECCO), pages 158--170. Springer, 2003.

Digital Library

[4]

V. Cutello, G. Nicosia, and M. Pavone. Exploring the capability of immune algorithms: A characterization of hypermutation operators. In International Conference on Artificial Immune Systems (ICARIS), pages 263--276. Springer, 2004.

[5]

V. Cutello, G. Nicosia, M. Romeo, and P. S. Oliveto. On the convergence of immune algorithms. In IEEE Symposium on Foundations of Computational Intelligence (FOCI), pages 409--415. IEEE Press, 2007.

[6]

D. Dasgupta. Artificial Immune Systems and Their Applications. Springer, 1998.

Digital Library

[7]

L. N. de Castro and J. Timmis. Artificial Immune Systems: A New Computational Intelligence Approach. Springer, 2002.

Digital Library

[8]

L. N. de Castro and F. J. V. Zuben. Learning and optimization using the clonal selection principle. IEEE Transactions on Evolutionary Computation, 6(3):239--251, 2002.

Digital Library

[9]

S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276(1-2):51--81, 2002.

Digital Library

[10]

T. Hagerup and C. Rüb. A guided tour of Chernoff bounds. Information Processing Letters, 33(6):305--308, 1990.

Digital Library

[11]

T. Jansen and I. Wegener. On the utility of populations. In Genetic and Evolutionary Computation Conference (GECCO), pages 1034--1041. Morgan Kaufmann, 2001.

[12]

T. Jansen and I. Wegener. A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation. Theoretical Computer Science, 386(1-2):73--93, 2007.

Digital Library

[13]

J. Kelsey and J. Timmis. Immune inspired somatic contiguous hypermutation for function optimisation. In Genetic and Evolutionary Computation Conference (GECCO), pages 207--218. Springer, 2003.

Digital Library

[14]

T. Storch. On the choice of the population size. In Genetic and Evolutionary Computation Conference (GECCO), pages 748--760. Springer, 2004.

[15]

J. Timmis, A. Hone, T. Stibor, and E. Clark. Theoretical advances in artificial immune systems. Theoretical Computer Science, 403(1):11--32, 2008.

Digital Library

[16]

M. Villalobos-Arias, C. A. C. Coello, and O. Hernández-Lerma. Convergence analysis of a multiobjective artificial immune system algorithm. In International Conference on Artificial Immune Systems (ICARIS), pages 226--235. Springer, 2004.

[17]

C. Witt. Runtime analysis of the (µ+1) EA on simple pseudo-Boolean functions. Evolutionary Computation, 14(1):65--86, 2006.

Digital Library

[18]

C. Witt. Population size versus runtime of a simple evolutionary algorithm. Theoretical Computer Science, 403(1):104--120, 2008.

Digital Library

[19]

C. Zarges. Rigorous runtime analysis of inversely fitness proportional mutation rates. In International Conference on Parallel Problem Solving from Nature (PPSN), pages 112--122. Springer, 2008.

Cited By

Lehre PLi XHandl J(2024)Runtime Analysis of Population-based Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648428(903-927)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648428
Lehre POliveto PSilva SPaquete L(2023)Runtime Analysis of Population-based Evolutionary Algorithms - Part I: Steady State EAsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595056(1271-1300)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595056
Lehre POliveto PWagner M(2022)Runtime analysis of population-based evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533658(1398-1426)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533658
Show More Cited By

Index Terms

On the utility of the population size for inversely fitness proportional mutation rates
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching
  2. Randomness, geometry and discrete structures

Recommendations

The choice of the offspring population size in the (1,λ) EA
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log₁₀ n between exponential and polynomial running times on ...
The choice of the offspring population size in the (1,λ) evolutionary algorithm

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,@l) EA. We establish a sharp threshold at @l=log"e"e"-"1n~5log"1"0n between exponential and polynomial running times on OneMax. For ...
Population size versus runtime of a simple evolutionary algorithm

Evolutionary algorithms (EAs) find numerous applications, and practical knowledge on EAs is immense. In practice, sophisticated population-based EAs employing selection, mutation and crossover are applied. In contrast, theoretical analysis of EAs often ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA '09: Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms

January 2009

204 pages

ISBN:9781605584140

DOI:10.1145/1527125

General Chairs:
Ivan Garibay
University of Central Florida
,
Thomas Jansen
Technische Universität Dortmund
,
R. Paul Wiegand
University of Central Florida
,
Annie S. Wu
University of Central Florida

Copyright © 2009 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 January 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '09

Sponsor:

FOGA '09: Foundations of Genetic Algorithms X

January 9 - 11, 2009

Florida, Orlando, USA

Acceptance Rates

FOGA '09 Paper Acceptance Rate 18 of 30 submissions, 60%;

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
181
Total Downloads

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

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lehre PLi XHandl J(2024)Runtime Analysis of Population-based Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648428(903-927)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648428
Lehre POliveto PSilva SPaquete L(2023)Runtime Analysis of Population-based Evolutionary Algorithms - Part I: Steady State EAsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595056(1271-1300)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595056
Lehre POliveto PWagner M(2022)Runtime analysis of population-based evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533658(1398-1426)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533658
Lehre POliveto PKrawiec K(2021)Runtime analysis of population-based evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461423(856-880)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461423
Taneja SGupta SJaiswal ABansal DBansal A(2021)Identity Verification Using Age Progression & Machine Learning2021 IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT)10.1109/CONECCT52877.2021.9622683(1-6)Online publication date: 9-Jul-2021
https://doi.org/10.1109/CONECCT52877.2021.9622683
Lehrexwid POliveto PCoello Coello C(2020)Runtime analysis of population-based evolutionary algorithmsProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389890(458-494)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389890
Lehre PSudholt D(2020)Parallel Black-Box Complexity With Tail BoundsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2019.295423424:6(1010-1024)Online publication date: Dec-2020
https://doi.org/10.1109/TEVC.2019.2954234
Cutello VOliva MPavone MScollo R(2020)A Hybrid Immunological Search for the Weighted Feedback Vertex Set ProblemLearning and Intelligent Optimization10.1007/978-3-030-38629-0_1(1-16)Online publication date: 22-Jan-2020
https://doi.org/10.1007/978-3-030-38629-0_1
Lehre POliveto PAuger AStützle T(2019)Runtime analysis of evolutionary algorithms: basic introductionProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323394(662-693)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323394
Cutello VOliva MPavone MScollo R(2019)An Immune Metaheuristics for Large Instances of the Weighted Feedback Vertex Set Problem2019 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI44817.2019.9002988(1928-1936)Online publication date: Dec-2019
https://doi.org/10.1109/SSCI44817.2019.9002988
Show More Cited By

View Options

Get Access

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