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

research-article

Dual-population genetic algorithm for nonstationary optimization

Authors:

Kwang Ryel RyuAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1025 - 1032

https://doi.org/10.1145/1389095.1389286

Published: 12 July 2008 Publication History

Abstract

In order to solve nonstationary optimization problems efficiently, evolutionary algorithms need sufficient diversity to adapt to environmental changes. The dual-population genetic algorithm (DPGA) is a novel evolutionary algorithm that uses an extra population called the reserve population to provide additional diversity to the main population through crossbreeding. Preliminary experimental results on various periods and degrees of environmental change have shown that the distance between the two populations of DPGA is one of the most important factors that affect its per-formance. However, it is very difficult to determine the best popu-lation distance without prior knowledge about the given problem. This paper proposes a new DPGA that uses two reserve populations (DPGA2). The reserve populations are at different distances from the main population. The information inflow from the reserve populations is controlled by survival selection. Experimental results show that DPGA2 shows a better performance than other evolutionary algorithms for nonstationary optimization problems without relying on prior knowledge about the problem.

References

[1]

J. Branke, T. Kaubler, C. Schmidt, and H. Schmeck. A multi-population approach to dynamic optimization problems. In Adaptive Computing in Design and Manufacturing 2000. Springer, 2000.

[2]

J. Branke. Evolutionary approaches to dynamic optimization problems-updated survey. GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pages 134--137, 2001.

[3]

H. G. Cobb. An investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuous, time-dependent nonstationary environments. Technical Report AIC-90-001, Naval Research Laboratory, Washington, USA, 1990.

[4]

J. J. Grefenstette. Genetic algorithms for changing environments. In R. Maenner and B. Manderick, editors, Parallel Problem Solving from Nature 2, pages 137--144, 1992.

[5]

B. S. Hadad and C. F. Eick. Supporting polyploidy in genetic algorithms using dominance vectors. In 6th Intl. Conf. on Evolutionary Programming, volume 1213 of LNCS, pages 223--234, Springer, 1997.

Digital Library

[6]

M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms: fitness landscapes and GA performance. In Proc. of the 1st European Conf. on Artificial Life, pages 245--254, 1992.

[7]

K. P. Ng and K. C. Wong. A new diploid scheme and dominance change mechanism for non-stationary function optimization. In 6th Intl. Conf on Genetic Algorithms, pages 159--166, 1955.

Digital Library

[8]

T. Park and K. R. Ryu. A dual population genetic algorithm with evolving diversity. In IEEE Congress on Evolutionary Computation (CEC2007), pages 3516--3522, 2007.

[9]

T. Park, R. Choe, and K. R. Ryu. Adjusting population distance for the dual-population genetic algorithm. In Australian Conference on Artificial Intelligence (AI 2007) (LNCS 4830), pages 171--180, 2007.

Digital Library

[10]

S. Tsutsui, Y. Fujimoto, and A. Chosh. Forking genetic algorithms: GAs with search space division schemes. Evolutionary Computation, 5(1):61--80, 1997.

Digital Library

[11]

F. Vavak, K. Jukes, and T. C. Fogarty. Learning the local search range for genetic optimisation in nonstationary environments. In IEEE Intl. Conf. on Evolutionary Computation (ICEC'97), pages 355--360, 1997.

[12]

L. D. Whitley. Fundamental principles of deception in genetic search. In Foundations of Genetic Algorithms 1, pages 221--241, 1991.

[13]

D. Whitley, S. Rana, and R. B. Heckendorn. The island model genetic algorithm: on separability, population size, and convergence. In Journal of Computing and Information Technology, volume 7, pages 33--47, 1999.

[14]

S. Yang. Non-stationary problem optimization using the primal-dual genetic algorithm. In IEEE Congress on Evolutionary Computation (CEC2003), pages 2246--2253, 2003.

[15]

S. Yang and X. Yao. Experimental study on population-based incremental learning algorithm for dynamic optimization problems, In Soft Computing, volume 9, pages 815--834, 2005.

Digital Library

Cited By

Umbarkar ASheth P(2022)GPGPU based Dual Population Genetic Algorithm for solving Constrained Optimization ProblemInternational Journal of Electrical Engineering and Computer Science10.37394/232027.2022.4.34(15-18)Online publication date: 4-Jun-2022
https://doi.org/10.37394/232027.2022.4.3
Ismkhan H(2018)Black box optimization using evolutionary algorithm with novel selection and replacement strategies based on similarity between solutionsApplied Soft Computing10.1016/j.asoc.2017.12.00664:C(260-271)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.asoc.2017.12.006
Umbarkar AJoshi MHong W(2016)Comparative study of diversity based parallel dual population genetic algorithm for unconstrained function optimisationsInternational Journal of Bio-Inspired Computation10.5555/2995373.29953818:4(248-263)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.5555/2995373.2995381
Show More Cited By

Index Terms

Dual-population genetic algorithm for nonstationary 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

A dual-population genetic algorithm for adaptive diversity control

A variety of previous works exist on maintaining population diversity of genetic algorithms (GAs). Dual-population GA (DPGA) is a type of multipopulation GA (MPGA) that uses an additional population as a reservoir of diversity. The main population is ...
A dual-population multi operators harmony search algorithm for dynamic optimization problems
Highlights
- We propose dual population for exploring and exploiting the search space.
- We ...
Abstract
Dynamic optimization problems (DOPs) have been widely researched in recent years. This is due to its numerous practical applications in real-life conditions. To solve DOPs, the optimizer should be able to track the changes and ...
Adjusting population distance for the dual-population genetic algorithm
AI'07: Proceedings of the 20th Australian joint conference on Advances in artificial intelligence

A dual-population genetic algorithm (DPGA) is a new multipopulation genetic algorithm that solves problems using two populations with different evolutionary objectives. The main population is similar to that of an ordinary genetic algorithm, and it ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 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: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
281
Total Downloads

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

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Umbarkar ASheth P(2022)GPGPU based Dual Population Genetic Algorithm for solving Constrained Optimization ProblemInternational Journal of Electrical Engineering and Computer Science10.37394/232027.2022.4.34(15-18)Online publication date: 4-Jun-2022
https://doi.org/10.37394/232027.2022.4.3
Ismkhan H(2018)Black box optimization using evolutionary algorithm with novel selection and replacement strategies based on similarity between solutionsApplied Soft Computing10.1016/j.asoc.2017.12.00664:C(260-271)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1016/j.asoc.2017.12.006
Umbarkar AJoshi MHong W(2016)Comparative study of diversity based parallel dual population genetic algorithm for unconstrained function optimisationsInternational Journal of Bio-Inspired Computation10.5555/2995373.29953818:4(248-263)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.5555/2995373.2995381
Umbarkar AJoshi MHong W(2014)Multithreaded Parallel Dual Population Genetic Algorithm (MPDPGA) for unconstrained function optimizations on multi-core systemApplied Mathematics and Computation10.1016/j.amc.2014.06.033243(936-949)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.1016/j.amc.2014.06.033
Umbarkar AJoshi MSheth P(2014)Diversity-Based Dual-Population Genetic Algorithm (DPGA): A ReviewProceedings of Fourth International Conference on Soft Computing for Problem Solving10.1007/978-81-322-2217-0_19(219-229)Online publication date: 25-Dec-2014
https://doi.org/10.1007/978-81-322-2217-0_19
Bravo YLuque GAlba E(2013)Migrants Selection and Replacement in Distributed Evolutionary Algorithms for Dynamic OptimizationDistributed Computing and Artificial Intelligence10.1007/978-3-319-00551-5_19(155-162)Online publication date: 2013
https://doi.org/10.1007/978-3-319-00551-5_19
Umbarkar AJoshi M(2012)Serial DPGA vs. Parallel Multithreaded DPGA: Threading AspectsProceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011) December 20-22, 201110.1007/978-81-322-0487-9_5(39-50)Online publication date: 15-Apr-2012
https://doi.org/10.1007/978-81-322-0487-9_5
Fernandes CMerelo JRosa A(2011)A comparative study on the performance of dissortative mating and immigrants-based strategies for evolutionary dynamic optimizationInformation Sciences: an International Journal10.1016/j.ins.2011.05.022181:20(4428-4459)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1016/j.ins.2011.05.022

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