neural networks research group
areas
•
people
•
projects
•
demos
•
publications
•
software/data
•
Using Symmetry and Evolutionary Search to Minimize Sorting Networks (2013)
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 uses 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 using 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
,
PS
Citation:
Journal of Machine Learning Research
, 14(Feb):303--331, 2013.
Bibtex:
@article{valsalam:jmlr13, title={Using Symmetry and Evolutionary Search to Minimize Sorting Networks}, author={Vinod K. Valsalam and Risto Miikkulainen}, volume={14}, journal={Journal of Machine Learning Research}, number={Feb}, pages={303--331}, url="http://nn.cs.utexas.edu/?valsalam:jmlr13", year={2013} }
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
Applications