GeneticSort

Genetic algorithm applied to sorting shuffled datasets (MATLAB).

View the Project on GitHub jonzia/GeneticSort

Genetic Algorithms

Summary

This MATLAB package serves as a framework for genetic algorithms which may be applied to a variety of use-cases. The provided tutorial applies genetic algorithm to unscramble four channels of data generated by different Gaussian models (similar to a Gausian mixture model) which have been randomly spliced together. In this analogy, each organism has four chromosomes, which are the four channels of the scrambled data stream; the organism’s fitness is determined by the consistency of the data on each chromosome. One or more populations of organisms are bred based on their fitness, with the goal of increasing fitness with each subsequent generation. The goal of this package is to serve as a widely extensible framework for applying genetic algorithms to more complex problems.

How to Use

Tutorial

The tutorial begins by generating the sample data. The length of our data streams will be 500 samples, and we’ll have four streams. We’ll then generate our data streams by randomly sampling a Gaussian distribution with a different mean on each channel and standard deviation of 0.25.

n = 500; m = 4; dataStreams = zeros(m, n);
for i = 1:4; dataStreams(:, i) = normrnd(i, 0.25, 1, n); end

We then mix the vectors by dividing the data streams at random points (these continuous segments are our alleles), randomly shuffling our alleles, and plotting the results. We can have several different populations running in parallel; in this tutorial, we’ll initialize two different populations.

% Population 1
alleles_1 = smart.genetic.generateAlleles(dataStreams, 10);
mixed_1 = smart.genetic.shuffleAlleles(alleles_1);
stream_1 = smart.general.plotCell(mixed_1, false);

% Population 2
alleles_2 = smart.genetic.generateAlleles(dataStreams, 10);
mixed_2 = smart.genetic.shuffleAlleles(alleles_2);
stream_2 = smart.general.plotCell(mixed_2, false);

Now that we have the mixed data streams for each population, we formally create each population of organisms which are generated by shuffling the seeding data stream. Each population has its own set of hyperparameters which can be the same or different. A full description of these hyperparameters can be found by typing help smart.genetic.definePopulation in the command window. These hyperparameters control aspects such as migration between population, the injection of viral vectors, parameters of the fitness function, etc.

% Arguments: stream, B, R, Mu, C, L, P, N, Mi, F, V
Population1 = ...
    smart.genetic.definePopulation(stream_1, 10, 10, 10, 10, 10, 4, 0, 0.02, 'avgstd', 3);
Population2 = ...
    smart.genetic.definePopulation(stream_2, 10, 10, 10, 10, 10, 4, 0, 0.02, 'maxstd', 'none');

Finally, we call the geneticSort() function to sort the data streams. For a full description of all parameters, type help smart.genetic.geneticSort in the command window.

% Arguments: patience, maxGen, Population1, Population2, ...
sortedVectors = smart.genetic.geneticSort(5, 100, Population1, Population2);

Additional Help

For additional help for each of the following functions, type help smart.genetic.<function> in the command window.

Note that the +genetic package is contained within the +smart package for compatibility with other repositories, since they may contain other subpackages of the larger +smart package which rely on +genetic package functions. These other subpackages may be pasted in the +smart folder to add their respective functionality, though they will generally already contain all dependencies when cloned. For the same reason, the +general package may contain functions that are currently unused.

Member Functions

| Function | Purpose | | — | — | | definePopulation() | Define a population for use in geneticSort() | | generateAlleles() | Divide a vector into a cell vector (alleles) | | geneticSort() | Sort a set of scrambled vectors using genetic algorithms | | getFitness() | Obtain the fitness for each organism | | infect() | Introduce genetic variability via viral vectors | | migrate() | Perform genetic crossover between two populations | | mutate() | Introduce genetic variability via mutation | | produceGeneration() | Produce a generation of offspring | | recombine() | Perform genetic recombination | | shuffleAlleles() | Generate a new organism via genetic shuffling |