research-article

A memory efficient and continuous-valued compact EDA for large scale problems

Authors:

Sergio Rojas-Galeano,

Nestor RodriguezAuthors Info & Claims

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

Pages 281 - 288

https://doi.org/10.1145/2330163.2330204

Published: 07 July 2012 Publication History

Abstract

This paper considers large-scale OneMax and RoyalRoad problems with up to 10⁷ binary variables within a compact Estimation of Distribution Algorithms (EDA) framework. Building upon the compact Genetic Algorithm (cGA), the continuous domain Population-Based Incremental Learning algorithm (PBILc) and the arithmetic-coding EDA, we define a novel method that is able to compactly solve regular and noisy versions of these problems with minimal memory requirements, regardless of problem or population size. This feature allows the algorithm to be run in a conventional desktop machine. Issues regarding probability model sampling, arbitrary precision of the arithmetic-coding decompressing scheme, incremental fitness function evaluation and updating rules for compact learning, are presented and discussed.

References

[1]

T. Back and H.-P. Schwefel. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1):1--23, 1993.

Digital Library

[2]

S. Baluja and R. Caruana. Removing the genetics from the standard genetic algorithm. Technical Report Carnegie Mellon University-CS-95--141, Carnegie-Mellon University, Pittsburgh, 1995.

Digital Library

[3]

Y. Cai, X. Sun, H. Xu, and P. Jia. Cross entropy and adaptive variance scaling in continuous EDA. In Proceedings of the 9th annual conference on Genetic and evolutionary computation, GECCO '07, pages 609--616, New York, NY, USA, 2007.

Digital Library

[4]

L. Devroye. Non-Uniform Random Variate Generation. Springer-Verlag, 1986.

[5]

D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, 1 edition, 1989.

Digital Library

[6]

C. Gonzáles, J. A. Lozano, and P. Larranaga. Mathematical modelling of UMDA$_c$ algorithm with tournament selection. International Journal of Approximate Reasoning, 31(3):313--340, 2002.

[7]

J. Grahl and F. Rothlauf. Polyeda: Combining estimation of distribution algorithms and linear inequality constraints. In Proceedings of the 6th Annual Conference on Genetic and Evolutionary Computation, GECCO '04, pages 1174--1185, 2004.

[8]

G. R. Harik and F. G. Lobo. The compact genetic algorithm. IEEE Transactions on Evolutionary Computation, 3:523--528, 1999.

Digital Library

[9]

C. W. Hsu, C. C. Chang, and C. J. Lin. A practical guide to support vector classification. Department of Computer Science and Information Engineering, National Taiwan University, 2003.

[10]

O. Kramer and F. Gieseke. Variance scaling for EDAs revisited. In J. Bach and S. Edelkamp, editors, KI 2011: Advances in Artificial Intelligence, volume 7006 of Lecture Notes in Computer Science, pages 169--178. Springer Berlin / Heidelberg, 2011.

Digital Library

[11]

P. Larranaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Springer, 2001.

Digital Library

[12]

E. Mininno, F. Cupertino, and D. Naso. Real-valued compact genetic algorithms for embedded microcontroller optimization. IEEE Transactions on Evolutionary Computation, 12(3):203--219, 2008.

Digital Library

[13]

M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and ga performance. In Proceedings of the First European Conference on Artificial Life, pages 245--254, 1991.

[14]

H. Mühlenbein. The equation for response to selection and its use for prediction. Evolutionary Computation, 5(3):303--346, 1997.

Digital Library

[15]

M. Pelikan and K. Sastry. Initial-population bias in the univariate estimation of distribution algorithm. In Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, GECCO '09, pages 429--436, New York, NY, USA, 2009. ACM.

Digital Library

[16]

M. Pelikan, K. Sastry, and E. Cantú-Paz, editors. Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.

Digital Library

[17]

S. Rojas-Galeano, E. Hsieh, D. Agranoff, S. Krishna, and D. Fernandez-Reyes. Estimation of relevant variables on high-dimensional biological patterns using iterated weighted kernel functions. PLoS ONE, 3(3), 2008.

[18]

A. Said. Introduction to arithmetic coding - theory and practice. Technical Report HPL-2004-76, Imaging Systems Laboratory, HP Laboratories Palo Alto, 2004.

[19]

K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Technical report, 2002.

[20]

K. Sastry, D. E. Goldberg, and X. Llora. Towards billion-bit optimization via a parallel estimation of distribution algorithm. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO '07, pages 577--584, 2007.

Digital Library

[21]

M. Sebag and A. Ducoulombier. Extending Population-Based incremental learning to continuous search spaces. Lecture Notes in Computer Science, 1498, 1998.

Digital Library

[22]

W. Suwannik and P. Chongstitvatana. Solving one-billion-bit noisy onemax problem using estimation distribution algorithm with arithmetic coding. In IEEE Congress on Evolutionary Computation, pages 1203--1206, 2008.

Cited By

Khalfi SCaraffini FIacca G(2023)Metaheuristics in the BalanceInternational Journal of Intelligent Systems10.1155/2023/57080852023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1155/2023/5708085
Merelo JLaredo JCastillo PGarcía-Valdez JRojas-Galeano S(2019)Scaling in Concurrent Evolutionary AlgorithmsApplied Computer Sciences in Engineering10.1007/978-3-030-31019-6_2(16-27)Online publication date: 9-Oct-2019
https://doi.org/10.1007/978-3-030-31019-6_2
Jezewski SDlugosz R(2017)Selected aspects and tradeoffs in transistor level implementation of genetic algorithms2017 IEEE 30th International Conference on Microelectronics (MIEL)10.1109/MIEL.2017.8190110(235-238)Online publication date: Oct-2017
https://doi.org/10.1109/MIEL.2017.8190110
Show More Cited By

Index Terms

A memory efficient and continuous-valued compact EDA for large scale problems
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Solving large scale optimization problems by opposition-based differential evolution (ODE)

This work investigates the performance of Differential Evolution (DE) and its opposition-based version (ODE) on large scale optimization problems. Opposition-based differential evolution (ODE) has been proposed based on DE; it employs opposition-based ...
Disturbed Exploitation compact Differential Evolution for limited memory optimization problems

This paper proposes a novel and unconventional Memetic Computing approach for solving continuous optimization problems characterized by memory limitations. The proposed algorithm, unlike employing an explorative evolutionary framework and a set of local ...
Hybrid evolutionary algorithms for large scale continuous problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Evolutionary Algorithms (EAs) are powerful metaheuristics that can be applied to almost any optimization problem. However, different Evolutionary Algorithms own different search capabilities that make them more suitable for one or another optimization ...

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

Editor:
Terence Soule
University of Idaho, USA
,
General Chair:
Jason H. Moore
Dartmouth College, USA

Copyright © 2012 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: 07 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '12

Sponsor:

SIGEVO

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

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
101
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Khalfi SCaraffini FIacca G(2023)Metaheuristics in the BalanceInternational Journal of Intelligent Systems10.1155/2023/57080852023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1155/2023/5708085
Merelo JLaredo JCastillo PGarcía-Valdez JRojas-Galeano S(2019)Scaling in Concurrent Evolutionary AlgorithmsApplied Computer Sciences in Engineering10.1007/978-3-030-31019-6_2(16-27)Online publication date: 9-Oct-2019
https://doi.org/10.1007/978-3-030-31019-6_2
Jezewski SDlugosz R(2017)Selected aspects and tradeoffs in transistor level implementation of genetic algorithms2017 IEEE 30th International Conference on Microelectronics (MIEL)10.1109/MIEL.2017.8190110(235-238)Online publication date: Oct-2017
https://doi.org/10.1109/MIEL.2017.8190110
Garzón-Rodriguez LDiosa HRojas-Galeano SEsparcia-Alcázar A(2015)Deconstructing GAs into Visual Software ComponentsProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2768466(1125-1132)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2768466
Garzon LRodriguez NOrjuela HRojas-Galeano S(2015)Component-based visual evolutionary computation2015 10th Computing Colombian Conference (10CCC)10.1109/ColumbianCC.2015.7333451(392-399)Online publication date: Sep-2015
https://doi.org/10.1109/ColumbianCC.2015.7333451
Rojas-Galeano SRodriguez NAlba E(2013)GoldenberryProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2482712(1325-1332)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2464576.2482712

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.

Figures

Tables

Media

View Table of Conten