Article

Statistical analysis of heuristics for evolving sorting networks

Authors:

Lee Graham,

Hassan Masum,

Franz OppacherAuthors Info & Claims

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Pages 1265 - 1270

https://doi.org/10.1145/1068009.1068215

Published: 25 June 2005 Publication History

Get Access

Abstract

Designing efficient sorting networks has been a challenging combinatorial optimization problem since the early 1960's. The application of evolutionary computing to this problem has yielded human-competitive results in recent years. We build on previous work by presenting a genetic algorithm whose parameters and heuristics are tuned on a small instance of the problem, and then scaled up to larger instances. Also presented are positive and negative results regarding the efficacy of several domain-specific heuristics.

References

[1]

Sung-Soon Choi and Byung-Ro Moon. A New Approach to the Sorting Network Problem Evolving Parallel Layers. In Proceedings of GECCO-2001. Morgan Kaufmann, 2001, pp. 258--265.

Google Scholar

[2]

Sung-Soon Choi and Byung-Ro Moon. Isomorphism, Normalization and a Genetic Algorithm for Sorting Networks. In Proceedings of GECCO-2002. Morgan Kaufmann, 2002, pp. 327--334.

Digital Library

Google Scholar

[3]

Sung-Soon Choi and Byung-Ro Moon. More Effective Genetic Search for the Sorting Network Problem. In Proceedings of GECCO-2002. Morgan Kaufmann, 2002, pp. 335--342.

Digital Library

Google Scholar

[4]

Harrison, M. L., and Foster, J. A. Co-evolving Faults to Improve the Fault Tolerance of Sorting Networks. In Proceedings of EuroGP 2004. Springer-Verlag, 2004.

Google Scholar

[5]

Danny Hillis. Co-evolving Parasites Improve Simulated Evolution as an Optimization Procedure. In Proceedings of Artificial Life II (1990). Westview Press, 1991.

Google Scholar

[6]

Hugues Juillé. Evolution of Non-deterministic Incremental Algorithms as a New Approach for Search in State Spaces. In Proceedings of ICGA-95. Morgan Kaufmann, 1995, pp. 351--358.

Digital Library

Google Scholar

[7]

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd edition). Addison Wesley, 1998.

Digital Library

Google Scholar

[8]

Sekanina Lukás. Evolving Constructors for Infinitely Growing Sorting Networks and Medians. In SOFSEM: Theory and Practice of Computer Science. Springer, 2004, pp. 314--323.

Google Scholar

[9]

Marek Piotrów. Depth Optimal Sorting Networks Resistant to k Passive Faults. SIAM Journal on Computing, Volume 33, Number 6 (2004), pp. 1484--1512.

Digital Library

Google Scholar

Cited By

View all

Ramasamy VKannan RMuralidharan GSidharthan RAmirtharajan R(2022)Two-tier search space optimisation technique for tuning of explicit plant-model mismatch in model predictive controller for industrial cement kiln processMathematics and Computers in Simulation10.1016/j.matcom.2021.10.015193(385-408)Online publication date: Mar-2022
https://doi.org/10.1016/j.matcom.2021.10.015
Bidlo MDobes M(2020)Evolutionary Development of Growing Generic Sorting Networks by Means of Rewriting SystemsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2019.291821224:2(232-244)Online publication date: Apr-2020
https://doi.org/10.1109/TEVC.2019.2918212
Gong YFukunaga A(2011)Distributed island-model genetic algorithms using heterogeneous parameter settings2011 IEEE Congress of Evolutionary Computation (CEC)10.1109/CEC.2011.5949703(820-827)Online publication date: Jun-2011
https://doi.org/10.1109/CEC.2011.5949703
Show More Cited By

Index Terms

Recommendations

Using symmetry and evolutionary search to minimize sorting networks

Sorting networks are an interesting class of parallel sorting algorithms with applications in multiprocessor computers and switching networks. They are built by cascading a series of comparison-exchange units called comparators. Minimizing the number of ...
Parameter tuning for meta-heuristics
Abstract
These days meta-heuristic algorithms are gaining lot of popularity. The performance of the meta-heuristics depends upon the suitable selection of user dependent parameters. Finding the most suitable values for the parameters (fine ...
Graphical abstract

Display Omitted
Highlights
- A generic parameter tuning methodology for meta-heuristic algorithms is proposed.
Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy Heuristics
GECCO '24: Proceedings of the Genetic and Evolutionary Computation Conference

The target set selection problem (TSS) asks for a set of vertices such that an influence spreading process started in these vertices reaches the whole graph. The current state of the art for this NP-hard problem are three recently proposed randomized ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

June 2005

2272 pages

ISBN:1595930108

DOI:10.1145/1068009

Editor:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
General Chair:
Una-May O'Reilly
CSAIL, MIT

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO05

Sponsor:

GECCO05: Genetic and Evolutionary Computation Conference

June 25 - 29, 2005

Washington DC, 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
306
Total Downloads

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

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ramasamy VKannan RMuralidharan GSidharthan RAmirtharajan R(2022)Two-tier search space optimisation technique for tuning of explicit plant-model mismatch in model predictive controller for industrial cement kiln processMathematics and Computers in Simulation10.1016/j.matcom.2021.10.015193(385-408)Online publication date: Mar-2022
https://doi.org/10.1016/j.matcom.2021.10.015
Bidlo MDobes M(2020)Evolutionary Development of Growing Generic Sorting Networks by Means of Rewriting SystemsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2019.291821224:2(232-244)Online publication date: Apr-2020
https://doi.org/10.1109/TEVC.2019.2918212
Gong YFukunaga A(2011)Distributed island-model genetic algorithms using heterogeneous parameter settings2011 IEEE Congress of Evolutionary Computation (CEC)10.1109/CEC.2011.5949703(820-827)Online publication date: Jun-2011
https://doi.org/10.1109/CEC.2011.5949703
Gong YFukunaga A(2009)Fault tolerance in distributed genetic algorithms with tree topologiesProceedings of the Eleventh conference on Congress on Evolutionary Computation10.5555/1689599.1689727(968-975)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.5555/1689599.1689727
Kubalík JRothlauf F(2009)Solving the sorting network problem using iterative optimization with evolved hypermutationsProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1569944(301-308)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1569944
Gong YFukunaga A(2009)Fault tolerance in distributed genetic algorithms with tree topologies2009 IEEE Congress on Evolutionary Computation10.1109/CEC.2009.4983050(968-975)Online publication date: May-2009
https://doi.org/10.1109/CEC.2009.4983050

View Options

Login options

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

Cited By

Index Terms

Recommendations

Using symmetry and evolutionary search to minimize sorting networks

Parameter tuning for meta-heuristics

Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy Heuristics