Learning Sorting Networks By Grammars

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Student Abstracts

We use a genetic algorithm(GA) to search for CMPX-nets which are SNets or MNets. The GA repeatedly samples the space of potential solutions in a series of generations, each using the relative fitness of the previous generation’s samples to apportion more samples in promising regions. Mutation and especially cross-over operators are applied to generate similar but novel new sample points; this process is iterated until some stopping criterion is achieved. Hillis has had encouraging success using a GA to evolve sorting networks( Hillis 1991).