Saturday 3:45 PM–4:30 PM in C11

Generating Sorting Networks using NEAT

Parth Raghav

Audience level:
Intermediate

Description

With this talk I would like to give hands-on experience with what genetic algorithms are: especially, NEAT (Neuroevolution of Augmenting Topologies); what sorting networks are; how NEAT can be used to generate sorting networks By the end of this talk, you'll know how to use NEAT in algorithmic domain.

Abstract

Heap Sort, Quick Sort, Counting Sort, Radix Sort, Bucket Sort are some of the sorting algorithms that you might be aware of, however they are designed for serial computers. Random-access machine model puts a hard limit on the speed of these algorithms since only one operation can be executed at a time. Enter Sorting Networks — parallel circuits comprised of wires and comparators that sort values in a sub-linear runtime. Since Sorting Networks are deterministic, data-oblivious, fixed, and can easily be implemented on hardware, they are really appealing. Especially since on top of merging and sorting, we can use them to make Switching Networks, Multi-Access Memory.

![sorting_network][sorting_network]

We explore construction of such Sorting Networks via NEAT (Neuroevolution of Augmenting Topologies). We start off with generation of random networks, they breed, create crossover children, mutate, and the least-fit children networks are dropped, allowing for only the ‘fitter’ generations to breed. We introduce a new NEAT mutation for our use case: mutate_transfer, wherein we mutate the transfer function of each node to either min(x) or max(x). This would give you a sense how we loosely use NEAT algorithm for generation of Sorting Networks. Since, most networks will generate incorrect permutations in the beginning, instead of using zero-one principle to check the correctness of each network, we measure the fitness of networks by L-1 norms of permutation matrices. This takes into account similar ordered subsequences. After multiple generations, we explore the properties of final sorting network.

Traditionally, a sorting network comprises of modules, namely Half-Cleaners and Bitonic Sorters. We explore how we can potentially generalize this composition using NEAT. Finally, we compare our method to AKS, Batcher odd-even mergesort, and how genetic algorithms been previously used to tackle this problem.

[sorting_network] : https://upload.wikimedia.org/wikipedia/commons/thumb/9/9b/SimpleSortingNetworkFullOperation.svg/1300px-SimpleSortingNetworkFullOperation.svg.png

Subscribe to Receive PyData Updates