research-article

On measuring and improving the quality of linkage learning in modern evolutionary algorithms applied to solve partially additively separable problems

Authors:

Michal W. Przewozniczek,

Marcin M. KomarnickiAuthors Info & Claims

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Pages 742 - 750

https://doi.org/10.1145/3377930.3390242

Published: 26 June 2020 Publication History

Abstract

Linkage learning is frequently employed in modern evolutionary algorithms. High linkage quality may be the key to an evolutionary method's effectiveness. Similarly, the faulty linkage may be the reason for its poor performance. Many state-of-the-art evolutionary methods use a Dependency Structure Matrix (DSM) to obtain linkage. In this paper, we propose a quality measure for DSM. Based on this measure, we analyze the behavior of modern evolutionary methods. We show the dependency between the linkage and the effectiveness of the considered methods. Finally, we propose a framework that improves the quality of the linkage.

References

[1]

Peter A.N. Bosman, Ngoc Hoang Luong, and Dirk Thierens. 2016. Expanding from Discrete Cartesian to Permutation Gene-pool Optimal Mixing Evolutionary Algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (GECCO '16). ACM, 637--644.

Digital Library

[2]

Ping-Lin Chen, Chun-Jen Peng, Chang-Yi Lu, and Tian-Li Yu. 2017. Two-edge Graphical Linkage Model for DSMGA-II. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '17). ACM, 745--752.

Digital Library

[3]

David E. Goldberg, Kalyanmoy Deb, and Jeffrey Horn. 1992. Massive Multimodality, Deception, and Genetic Algorithms. Urbana (1992).

[4]

Brian W. Goldman and William F. Punch. 2014. Parameter-less Population Pyramid. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO '14). ACM, 785--792.

[5]

Georges R. Harik and Fernando G. Lobo. 1999. A Parameter-less Genetic Algorithm. In Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1 (GECCO'99). 258--265.

[6]

Shih-Huan Hsu and Tian-Li Yu. 2015. Optimization by Pairwise Linkage Detection, Incremental Linkage Set, and Restricted / Back Mixing: DSMGA-II. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO '15). ACM, 519--526.

Digital Library

[7]

Marcin M. Komarnicki and Michal W. Przewozniczek. 2017. Parameter-less Population Pyramid with Feedback. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '17). ACM, 109--110.

[8]

Marcin M. Komarnicki and Michal W. Przewozniczek. 2019. Parameter-Less, Population-Sizing DSMGA-II. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '19). Association for Computing Machinery, New York, NY, USA, 289--290.

[9]

M. N. Omidvar, X. Li, Y. Mei, and X. Yao. 2014. Cooperative Co-Evolution With Differential Grouping for Large Scale Optimization. IEEE Transactions on Evolutionary Computation 18, 3 (2014), 378--393.

[10]

M. N. Omidvar, M. Yang, Y. Mei, X. Li, and X. Yao. 2017. DG2: A Faster and More Accurate Differential Grouping for Large-Scale Black-Box Optimization. IEEE Transactions on Evolutionary Computation 21, 6 (Dec 2017), 929--942.

Digital Library

[11]

M. W. Przewozniczek. 2017. Problem Encoding Allowing Cheap Fitness Computation of Mutated Individuals. In 2017 IEEE Congress on Evolutionary Computation (CEC). 308--316.

[12]

Michal W. Przewozniczek and Marcin M. Komarnicki. 2018. The Influence of Fitness Caching on Modern Evolutionary Methods and Fair Computation Load Measurement. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '18). ACM, 241--242.

[13]

Michal Witold Przewozniczek and Marcin Michal Komarnicki. 2020. Empirical Linkage Learning. IEEE Transactions on Evolutionary Computation (2020), (in press).

Digital Library

[14]

Dirk Thierens. 2010. The Linkage Tree Genetic Algorithm. In Parallel Problem Solving from Nature, PPSN XI: 11th International Conference, Kraków, Poland, September 11-15, 2010, Proceedings, Part I. 264--273.

[15]

Dirk Thierens and Peter A.N. Bosman. 2013. Hierarchical Problem Solving with the Linkage Tree Genetic Algorithm. In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation (GECCO '13). ACM, 877--884.

[16]

L. Darrell Whitley, Francisco Chicano, and Brian W. Goldman. 2016. Gray Box Optimization for Mk Landscapes Nk Landscapes and Max-Ksat. Evol. Comput. 24, 3 (Sept. 2016), 491--519.

Digital Library

[17]

Adam M. Zielinski, Marcin M. Komarnicki, and Michal W. Przewozniczek. 2019. Parameter-less Population Pyramid with Automatic Feedback. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '19). ACM, New York, NY, USA, 312--313.

Digital Library

Cited By

Tinós RPrzewozniczek MWhitley DChicano F(2024)Iterated Local Search with Linkage LearningACM Transactions on Evolutionary Learning and Optimization10.1145/36511654:2(1-29)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3651165
Tulczyjew LPrzewozniczek MTinós RWijata ANalepa JLi XHandl J(2024)CANNIBAL Unveils the Hidden Gems: Hyperspectral Band Selection via Clustering of Weighted Variable Interaction GraphsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654203(412-421)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654203
Komarnicki MPrzewozniczek MKwasnicka HWalkowiak K(2023)Incremental Recursive Ranking Grouping for Large-Scale Global OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.321696827:5(1498-1513)Online publication date: Oct-2023
https://doi.org/10.1109/TEVC.2022.3216968
Show More Cited By

Index Terms

On measuring and improving the quality of linkage learning in modern evolutionary algorithms applied to solve partially additively separable problems
1. Computing methodologies
  1. Artificial intelligence

Recommendations

Hybrid linkage learning for permutation optimization with Gene-pool optimal mixing evolutionary algorithms
GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Linkage learning techniques are employed to discover dependencies between problem variables. This knowledge can then be leveraged in an Evolutionary Algorithm (EA) to improve the optimization process. Of particular interest is the Gene-pool Optimal ...
Direct linkage discovery with empirical linkage learning
GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

Problem decomposition is an important part of many state-of-the-art Evolutionary Algorithms (EAs). The quality of the decomposition may be decisive for the EA effectiveness and efficiency. Therefore, in this paper, we focus on the recent proposition of ...
Empirical linkage learning
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion

Linkage learning is employed by many state-of-the-art evolutionary methods designed for solving problems in discrete domains. The effectiveness of these methods is dependent on linkage quality. The linkage may suffer to two different inaccuracy types. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

June 2020

1349 pages

ISBN:9781450371285

DOI:10.1145/3377930

General Chair:
Carlos Artemio Coello Coello
CINVESTAV-IPN

Copyright © 2020 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: 26 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

the statutory funds of the Department of Computational Intelligence
NCN

Conference

GECCO '20

Sponsor:

SIGEVO

GECCO '20: Genetic and Evolutionary Computation Conference

July 8 - 12, 2020

Cancún, Mexico

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
83
Total Downloads

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

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tinós RPrzewozniczek MWhitley DChicano F(2024)Iterated Local Search with Linkage LearningACM Transactions on Evolutionary Learning and Optimization10.1145/36511654:2(1-29)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3651165
Tulczyjew LPrzewozniczek MTinós RWijata ANalepa JLi XHandl J(2024)CANNIBAL Unveils the Hidden Gems: Hyperspectral Band Selection via Clustering of Weighted Variable Interaction GraphsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654203(412-421)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654203
Komarnicki MPrzewozniczek MKwasnicka HWalkowiak K(2023)Incremental Recursive Ranking Grouping for Large-Scale Global OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.321696827:5(1498-1513)Online publication date: Oct-2023
https://doi.org/10.1109/TEVC.2022.3216968
Przewozniczek MKomarnicki M(2021)Fitness Caching - From a Minor Mechanism to Major Consequences in Modern Evolutionary Computation2021 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC45853.2021.9504686(1785-1791)Online publication date: 28-Jun-2021
https://doi.org/10.1109/CEC45853.2021.9504686
Wozniak SPrzewozniczek MKomarnicki M(2020)Parameter-Less Population Pyramid for Permutation-Based ProblemsParallel Problem Solving from Nature – PPSN XVI10.1007/978-3-030-58112-1_29(418-430)Online publication date: 31-Aug-2020
https://doi.org/10.1007/978-3-030-58112-1_29

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