%0 Conference Paper %1 juille_icga95 %A Juille, Hugues %B Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95) %C Pittsburgh, PA, USA %D 1995 %E Eshelman, L. %I Morgan Kaufmann %K Networks, Search Sorting Stochastic algorithms, genetic %P 351--358 %T Evolution of Non-Deterministic Incremental Algorithms as a New Approach for Search in State Spaces %U http://www.demo.cs.brandeis.edu/papers/icga95.ps %X Let us call a non-deterministic incremental algorithm one that is able to construct any solution to a combinatorial problem by selecting incrementally an ordered sequence of choices that defines this solution, each choice being made non-deterministically. In that case, the state space can be represented as a tree, and a solution is a path from the root of that tree to a leaf. This paper describes how the simulated evolution of a population of such non-deterministic incremental algorithms offers a new approach for the exploration of a state space, compared to other techniques like Genetic Algorithms (GA), Evolutionary Strategies (ES) or Hill Climbing. In particular, the efficiency of this method, implemented as the Evolving Non-Determinism (END) model, is presented for the sorting network problem, a reference problem that has challenged computer science. Then, we shall show that the END model remedies some drawbacks of these optimization techniques and even outperforms them for this problem. Indeed, some 16-input sorting networks as good as the best known have been built from scratch, and even a 25-year-old result for the 13-input problem has been improved by one comparator. %@ 1-55860-370-0

@inproceedings{juille_icga95, abstract = {Let us call a non-deterministic incremental algorithm one that is able to construct any solution to a combinatorial problem by selecting incrementally an ordered sequence of choices that defines this solution, each choice being made non-deterministically. In that case, the state space can be represented as a tree, and a solution is a path from the root of that tree to a leaf. This paper describes how the simulated evolution of a population of such non-deterministic incremental algorithms offers a new approach for the exploration of a state space, compared to other techniques like Genetic Algorithms (GA), Evolutionary Strategies (ES) or Hill Climbing. In particular, the efficiency of this method, implemented as the Evolving Non-Determinism (END) model, is presented for the sorting network problem, a reference problem that has challenged computer science. Then, we shall show that the END model remedies some drawbacks of these optimization techniques and even outperforms them for this problem. Indeed, some 16-input sorting networks as good as the best known have been built from scratch, and even a 25-year-old result for the 13-input problem has been improved by one comparator.}, added-at = {2008-06-19T17:35:00.000+0200}, address = {Pittsburgh, PA, USA}, author = {Juille, Hugues}, biburl = {https://www.bibsonomy.org/bibtex/2aa36f062c65ecfa490d6ffbda98d7a70/brazovayeye}, booktitle = {Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95)}, editor = {Eshelman, L.}, interhash = {ce68b60865413e08c70798c2c117528c}, intrahash = {aa36f062c65ecfa490d6ffbda98d7a70}, isbn = {1-55860-370-0}, keywords = {Networks, Search Sorting Stochastic algorithms, genetic}, month = {15-19 July}, pages = {351--358}, publisher = {Morgan Kaufmann}, publisher_address = {San Francisco, CA, USA}, timestamp = {2008-06-19T17:42:43.000+0200}, title = {Evolution of Non-Deterministic Incremental Algorithms as a New Approach for Search in State Spaces}, url = {http://www.demo.cs.brandeis.edu/papers/icga95.ps}, year = 1995 }