Designing a Novel General Sorting Network Constructor Using Artificial Evolution

Authors: Michal Bidlo, Radek Bidlo, Lukas Sekanina

Abstract:

A method is presented for the construction of arbitrary even-input sorting networks exhibiting better properties than the networks created using a conventional technique of the same type. The method was discovered by means of a genetic algorithm combined with an application-specific development. Similarly to human inventions in the area of theoretical computer science, the evolved invention was analyzed: its generality was proven and area and time complexities were determined.

Keywords: Development, genetic algorithm, program, sorting network.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062354

References:

[1] Knuth, D. E.: The Art of Computer Programming: Sorting and Searching (2nd ed.). Addison Wesley, 1998
[2] Juill'e, H.: Evolution of Non-Deterministic Incremental Algorithms as a New Approach for Search in State Spaces.In: Proc. of 6th Int. Conference on Genetic Algorithms, Morgan Kaufmann, 1995, p. 351-358
[3] Choi, S., Moon, B.: A Hybrid Genetic Search for the Sorting Network Problem with Evolving Parallel Layers. In: Genetic and Evolutionary Computation Conference, San Francisco, 2001, p. 258-265
[4] Hillis, W. D.: Co-evolving Parasites Improve Simulated Evolution as an Optimization Procedure. Physica D 42, 1990, p. 228-234
[5] Choi, S., Moon, B.: More Effective Genetic Search for the Sorting Network Problem. In: Genetic and Evolutionary Computation Conference, New York, 2002, p. 335-342
[6] Koza, J. R. et al.: Genetic Programming III: Darwinian Invention and Problem Solving. Morgan Kaufmann Publishers, San Francisco, CA, 1999
[7] Sekanina, L., Bidlo, M.: Evolutionary Design of Arbitrarily Large Sorting Networks Using Development. Genetic Programming and Evolvable Machines. Vol. 6, Num. 3, 2005, p. 319-347
[8] Lang, H. W.: Algorithmen. Institut f╦Øur medieninformatik und technische informatik. http://www.iti.fh-flensburg.de/lang/algorithmen/algo.htm (March 2006)
[9] Stoica, A. et al.: Polymorphic Electronics. Proc. of International Conferencee on Evolvable Systems: From Biology to Hardware, LNCS 2210, Springer, 2001, p. 291-302
[10] Stoica, A. et al.: On Polymorphic Circuits and Their Design Using Evolutionary Algorithms. Proc. of IASTED International Confernece on Applied Informatics, AI 2002, Innsbruck, AU, 2002
[11] Bidlo, M., Sekanina, L.: Providing Information from the Environment for Growing Electronic Circuits Through Polymorphic Gates. Proc. of Genetic and Evolutionary Computation Conference - Workshops 2005, ACM, New York, US, 2005, p. 242-248