neural networks research group
areas
•
people
•
projects
•
demos
•
publications
•
software/data
•
Utilizing Symmetry and Evolutionary Search to Minimize Sorting Networks (2011)
Vinod K. Valsalam
and
Risto Miikkulainen
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 comparators for a given number of inputs is a challenging optimization problem. This paper presents a two-pronged approach called Symmetry and Evolution based Network Sort Optimization (SENSO) that makes it possible to scale the solutions to networks with a larger number of inputs than previously possible. First, it utilizes the symmetry of the problem to decompose the minimization goal into subgoals that are easier to solve. Second, it minimizes the resulting greedy solutions further by utilizing an evolutionary algorithm to learn the statistical distribution of comparators in minimal networks. The final solutions improve upon half-century of results published in patents, books, and peer-reviewed literature, demonstrating the potential of the SENSO approach for solving difficult combinatorial problems.
View:
PDF
Citation:
Technical Report AITR-11-09, Department of Computer Sciences, The University of Texas at Austin, Austin, TX, 2011.
Bibtex:
@techreport{valsalam:utcstr11, title={Utilizing Symmetry and Evolutionary Search to Minimize Sorting Networks}, author={Vinod K. Valsalam and Risto Miikkulainen}, number={AITR-11-09}, address={Austin, TX}, institution={Department of Computer Sciences, The University of Texas at Austin}, url="http://nn.cs.utexas.edu/?valsalam:utcstr11", year={2011} }
People
Risto Miikkulainen
Faculty
risto [at] cs utexas edu
Vinod Valsalam
Ph.D. Alumni
vkv [at] alumni utexas net
Projects
Learning Strategic Behavior in Sequential Decision Tasks
2009 - 2014
Utilizing Symmetry in Evolutionary Design
2007 - 2010
Software/Data
Sorting Networks
This package contains software utilizing an approach based on symmetry and evolution to minimize the number of comparato...
2010
Areas of Interest
Evolutionary Computation
Control