Sorting networks are networks consisting of wires that carry input values along with a number of interconnections between pairs of these wires, which function as comparators for swapping values on the wires if they are not in a desired order, or leaving them as is if they are. A graphical representation of a simple 4-input sorting network is as follows:
For more information on the theory behind sorting please refer to the following links:
https://en.wikipedia.org/wiki/Sorting_network
Ian Parberry PhD has an interesting page detailing his research into sorting networks:
http://larc.unt.edu/ian/research/sortingnetworks/
This C++ implementation is a simple console application to demonstrate the efficacy of applying a genetic algorithm to a combinatorial optimization problem such as this. C++ classes and methods are introduced to encapsulate the encoding of the sorting networks (“chromosomes”) and the application of standard genetic operators crossover, mutation and selection to the population of sorting networks.
Encoding Sorting Networks
The SortingNetwork class contains the list of CompareSet objects, whereby each CompareSet object represents the set of comparator configurations for each column in the sorting network. So for the sorting network represented by the diagram above, the complete encoding for the sorting network would be:
[0,2] [1,3] [0,1], [2,3] [1,2]
The CompareSet and SortingNetwork C++ classes are detailed as follows:
SortingNetwork.h
typedef std::pair<int,int> CompareIndex;
class CompareSet
{
public:
std::list<CompareIndex> CompareIndexes;
void Add(int x, int y);
bool Contains(int v);
CompareSet& operator=( const CompareSet& sompareSet );
};
class SortingNetwork
{
private:
std::list<CompareSet> Compares;
float fitness;
int inputSize;
void Insert(int x, int y, int index);
void Insert(int x, int y);
void GenerateTestSets();
public:
int Size() const;
SortingNetwork& operator=( const SortingNetwork& sortingNetwork );
SortingNetwork( const SortingNetwork& sortingNetwork );
SortingNetwork(int size, int inputsize);
void CreateRandomCompareSets(std::vector<std::pair<int,int>>& sets);
void Insert(std::vector<std::pair<int,int>>& sets, int index);
void Set(std::vector<std::pair<int,int>>& sets, int index);
void Set(int index1, std::list<CompareSet>::iterator cit);
void Set(int index1, CompareSet& compareset);
std::string Dec2Gray( unsigned n );
float EvaluateComparisonSets(const std::vector<std::pair<std::string, std::string>>& tests);
bool Evaluate(std::vector<int> v);
void Sort(std::vector<int>& v);
void Mutate1(int index);
void Mutate2(int index);
void Mutate3();
void Mutate4();
void Remove(int index);
float Fitness() const;
void Print();
std::list<CompareSet>::iterator GetCompareSet(int setnumber);
};
The Genetic Algorithm
Also presented is the GeneticAlgorithm class.
GeneticAlgorithm.h
class GeneticAlgorithm
{
private:
std::vector<SortingNetwork*> population;
std::vector<bool> changedSet;
SortingNetwork* bestNetwork;
int mutationRate;
int crossoverRate;
int populationSize;
int bestIndividual;
int tournamentSize;
float bestScore;
int testInputSize;
std::vector<std::pair<std::string, std::string>> testInputs;
public:
GeneticAlgorithm( int popSize, int mutation, int crossover, int inputsize, int comparesize,
int tournamentsize, int testinputsize);
void CreateRandomPopulation(int popsize, int inputsize, int comparesize );
void Evaluate();
void Mutation();
void Crossover();
void Selection();
float BestScore();
int BestIndividual();
SortingNetwork* GetBestNetwork();
void GeneticAlgorithm::GenerateTestSets(int inputSize);
};
The population of sorting networks managed by the genetic algorithm is maintained as an STL vector of pointers to SortingNetwork objects.
The GeneticAlgorithm class applies the operators crossover, mutation and selection operators to the population of sorting networks. Crossover arbitrarily selects two different sorting networks and exchanges information between them to produce new ‘child’ sorting networks. The mutation operator is used to change an arbitrarily selected sorting network and alter its structure in some way, such as by changing one of the comparator values, or by randomly inserting or removing new comparators. Crossover and mutation enable the algorithm to discover new and potentially better solutions as the algorithm progresses.
Implementing the crossover operator
The following diagram illustrates pictorially how two new ‘child’ solutions are obtained by re-combining portions of the two ‘parent’ solutions. In this example the first column of the left sorting network is combined with the second column of the right sorting network, producing the two new sorting networks as shown:
Implementing the mutation operator
The next diagram illustrates how the three different mutation operators can be used in this application to modify a sorting network: modify an existing comparator, remove an existing comparator and insert a new comparator. The first column is modified so that input lines 1 to 3 are connected instead of 0 to 3. The second column connecting input lines 1 to 2 is removed completely, shifting columns three and four to the left. A new column is inserted on the end connecting input lines 0 and 2:
Evaluating the fitness of sorting networks
We evaluate the ability of the sorting network to sort a set of integers by comparing the actual result obtained by the sorting network with the desired result that is obtained using a known sorting algorithm. The sum total of the number of test inputs that were correctly sorted by the sorting network is determined, so that the sorting fitness is the sum total of correctly sorted inputs divided by the total number of input combinations. If all test inputs were correctly sorted then the sorting fitness is 1.0.
To encourage the genetic algorithm to find concise solutions, an additional score is calculated and added to solutions whose sorting fitness is 1.0. This additional score is inversely proportional to the number of comparison sets it contains and is added to the sorting fitness so that the overall fitness becomes greater than 1.0. The result is sorting networks whose fitness based is 1.0 (ie correctly sorts all test inputs) but achieved with relatively fewer comparison sets will get a higher fitness score than those that achieve the same but with more comparison sets.
Using the zero-one principle
To further reduce the amount of computation required to evaluate the networks, the zero-one principle is employed. Rather than test combinations of integers, whereby the number of possible permutations is n!, it is equally as valid and more desirable to test combinations of zeros and ones, thus reducing the permutations to 2^n. Even though the amount of computation still rises exponentially with n, it is still significant reduced compared to n!.
Two approaches to evaluating the sorting networks were explored. One way was to exhaustively evaluate all possible input combinations. However, as the size of the problem becomes non-trivial, it becomes clear that an exhaustive evaluation of all possible combinations is computationally intractable.
An approach explored in this post is to evaluate a subset of the total number of possible inputs and calculate the fitness based on these. Experiments were carried out on the size of the test inputs necessary to produce sorting networks that could correctly sort all possible inputs presented to them. The genetic algorithm is run for a set number of iterations in order to ‘train’ the sorting networks, the best solution is obtained, and a final evaluation is completed to see if the best solution obtained is able to sort any combination of input presented to it.
At the beginning of the program we generate a random collection of test inputs at the beginning of the program and see how well each sorting network is able to sort these. Each test consists of an array of numbers, the array size being equal to the number of inputs. We then apply a known sorting algorithm to input array to determine what the expected output for this particular input should be.
While experimenting with this algorithm it was observed that a few hundred test sets were necessary to sufficiently test the ability of the generated sorting networks to sort the inputs presented to them. Perhaps unsurprisingly it was observed that using too few test inputs is likely to result in sub-optimal sorting networks being generated that would fail to sort many of the test inputs.
The following code shows an example main.cpp usage along with the parameters used in the genetic algorithm and test input setup:
#include "GeneticAlgorithm.h"
#include <iostream>
#include <sstream>
#include <iomanip>
#include <iterator>
typedef std::vector<int>::iterator iter_s;
template<typename T, typename InputIterator>
void Print(std::ostream& ostr,
InputIterator itbegin,
InputIterator itend,
const std::string& delimiter)
{
std::copy(itbegin,
itend,
std::ostream_iterator<T>(ostr, delimiter.c_str()));
}
int main()
{
const int popsize = 100;
const int tournamentsize = popsize / 10;
const int mutation = 10;
const int crossover = 45;
const int inputsize = 4;
const int comparesize = inputsize * 2;
const int testInputSize = inputsize * 50;
const int maxIterations = 500;
GeneticAlgorithm ga(popsize, mutation, crossover, inputsize, comparesize, tournamentsize,
testInputSize );
ga.Evaluate();
int iteration = 0;
while (iteration < maxIterations)
{
ga.Selection();
ga.Crossover();
ga.Mutation();
ga.Evaluate();
if ( iteration % 20 == 0 )
{
std::cout << "Iteration: " << std::setw(4) << iteration
<< " Best fitness = " << std::setprecision(4) << std::setw(5) << ga.BestScore()
<< " No. compare sets = " << ga.GetBestNetwork()->Size() << std::endl;
}
iteration++;
}
//int T1[100] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100 };
int T2[] = {5000, 4999, 4998, 4997, 4996, 4995, 4994, 4993, 4992, 4991, 4990, 4989, 4988, 4987, 4986, 4985, 4984, 4983, 4982, 4981, 4980, 4979, 4978, 4977, 4976, 4975, 4974, 4973, 4972, 4971, 4970, 4969, 4968, 4967, 4966, 4965, 4964, 4963, 4962, 4961, 4960, 4959, 4958, 4957, 4956, 4955, 4954, 4953, 4952, 4951, 4950, 4949, 4948, 4947, 4946, 4945, 4944, 4943, 4942, 4941, 4940, 4939, 4938, 4937, 4936, 4935, 4934, 4933, 4932, 4931, 4930, 4929, 4928, 4927, 4926, 4925, 4924, 4923, 4922, 4921, 4920, 4919, 4918, 4917, 4916, 4915, 4914, 4913, 4912, 4911, 4910, 4909, 4908, 4907, 4906, 4905, 4904, 4903, 4902, 4901};
//int T3[] = {-9999, -9995, -9982, -9981, -9975, -9975, -9969, -9968, -9962, -9962, -9961, -9959, -9954, -9954, -9952, -9947, -9946, -9945, -9939, -9936, -9936, -9929, -9928, -9923, -9922, -9918, -9917, -9916, -9914, -9912, -9905, -9904, -9903, -9902, -9900, -9897, -9894, -9891, -9889, -9874, -9873, -9872, -9871, -9853, -9847, -9845, -9844, -9844, -9842, -9834, -9821, -9821, -9816, -9814, -9813, -9813, -9813, -9812, -9808, -9796, -9795, -9795, -9792, -9787, -9785, -9783, -9781, -9781, -9778, -9778, -9776, -9774, -9770, -9770, -9766, -9765, -9761, -9755, -9753, -9746, -9741, -9737, -9730, -9716, -9711, -9708, -9706, -9699, -9694, -9691, -9690, -9687, -9685, -9681, -9677, -9676, -9670, -9670, -9668, -9663};
//int T4[] = {0, 0, 2, 3, 2, 1, 1, 7, 5, 3, 5, 4, 8, 9, 11, 3, 15, 5, 16, 14, 6, 4, 9, 8, 6, 3, 13, 1, 12, 10, 9, 30, 27, 27, 21, 5, 29, 5, 33, 3, 1, 2, 20, 37, 22, 42, 42, 41, 4, 30, 34, 6, 39, 51, 13, 3, 56, 18, 29, 59, 47, 27, 62, 17, 1, 31, 23, 62, 3, 57, 68, 38, 52, 72, 17, 12, 1, 31, 30, 71, 44, 74, 32, 27, 53, 35, 31, 67, 15, 73, 8, 47, 33, 6, 90, 65, 79, 48, 70, 96};
std::vector<int> input( T2, T2 + inputsize);
std::vector<int> output1( T2, T2 + inputsize);
std::cout << std::endl;
std::cout << "Input set:" << std::endl << std::endl;
Print<int, iter_s>( std::cout, input.begin(), input.end(), " " );
SortingNetwork* nw = ga.GetBestNetwork();
nw->Sort( output1 );
std::cout << std::endl << std::endl;
std::cout << "Input set after network sort:" << std::endl << std::endl;
Print<int, iter_s>( std::cout, output1.begin(), output1.end(), " " );
std::cout << std::endl << std::endl;
std::cout << "Sorting network: " << std::endl << std::endl;
nw->Print();
std::cout << std::endl;
std::cout << "Exhaustive evaluation fitness = " << nw->EvaluateNetworkExhaustively() << std::endl;
std::cout << std::endl << std::endl;
std::cout << "Press any key to exit.";
getchar();
return 0;
}
Presented here are results of some initial experiments for using the genetic algorithm to obtain the sorting networks.
Input size = 4
This result shows the how the genetic algorithm could be made to generate an optimal solution for (an albeit trivial) 4-input example. The parameters used in the algorithm are detailed as follows:
const int popsize = 1000; const int tournamentsize = popsize / 10; const int mutation = 5; const int crossover = 50; const int inputsize = 4; const int comparesize = inputsize * 3; const int testInputSize = inputsize * 50; const int maxIterations = 500;
The best sorting network obtained by the genetic algorithm is represented by ‘-‘ characters representing the input lines, while the connections between the input lines are indicated by the ‘X’ characters. As you can see the genetic algorithm managed to produce a sorting network whittled down to a solution containing 5 comparison sets:
To demonstrate the importance of using test input sizes of a sufficient size, let’s drastically reduce the size of the test input and re-run with the remaining parameters intact ie:
const int popsize = 100; const int tournamentsize = popsize / 10; const int mutation = 10; const int crossover = 45; const int inputsize = 4; const int comparesize = inputsize * 2; const int testInputSize = inputsize * 1; const int maxIterations = 500;
The genetic algorithm simply finds solutions that satisfy a much reduced criteria, whereby the sorting ability for large combinations of inputs is much less stringent.
When the best solution obtained is tested exhaustively with all possible input combinations, the final score is less than perfect:
More experiments to follow.
Input size = 5
Algorithm parameters:
const int popsize = 500; const int tournamentsize = popsize / 10; const int mutation = 10; const int crossover = 45; const int inputsize = 5; const int comparesize = inputsize * 3; const int testInputSize = inputsize * 50; const int maxIterations = 500;
This time a sorting network using 7 comparison sets was obtained:
Input size = 6
Algorithm parameters:
const int popsize = 100; const int tournamentsize = popsize / 10; const int mutation = 10; const int crossover = 45; const int inputsize = 6; const int comparesize = inputsize * 2; const int testInputSize = inputsize * 50; const int maxIterations = 500;
Input size = 7
Algorithm parameters:
const int popsize = 100; const int tournamentsize = popsize / 10; const int mutation = 10; const int crossover = 45; const int inputsize = 7; const int comparesize = inputsize * 2; const int testInputSize = inputsize * 50; const int maxIterations = 500;
Input size = 10
const int popsize = 100; const int tournamentsize = popsize / 10; const int mutation = 10; const int crossover = 45; const int inputsize = 10; const int comparesize = inputsize * 2; const int testInputSize = inputsize * 50; const int maxIterations = 500;
As demonstrated by the results shown, using these parameters obtained us an exhaustive fitness score of 0.998, slightly less than the desired score of 1.0:
A score of 1.0 was seen to be achievable by using the following algorithm parameters:
const int popsize = 50; const int tournamentsize = popsize / 10; const int mutation = 10; const int crossover = 45; const int inputsize = 10; const int comparesize = inputsize * 4; const int testInputSize = inputsize * 200; const int maxIterations = 600;
Software downloadable from the following link. Comments and suggestions always welcome.
