corridor

package module
v0.0.0-...-8d2889e Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 21, 2016 License: BSD-3-Clause Imports: 14 Imported by: 0

README

#Introduction#

corridor is library containing Go language functions for the implementation of a concurrent genetic algorithm for the multi-objective corridor location problem. This problem involves finding the least cost connected pathway through a discrete search domain in which each location is characterized by one or more measures of cost. The library requires that the user provide a predefined search domain, objective function(s), and input parameters specifying the nature of the problem (i.e. desired start and destination locations).

#Installation#

The project is hosted as a publicly available GitHub repository. Providing that your local client GOPATH and GOROOT variables have been previously defined, the repository can be cloned and built using the following single shell command:

$ go get github.com/ericdfournier/corridor

#Description#

The work contained in this library is based upon the MOGADOR algorithm that was first introduced by Zhang & Armstrong (2008) in: http://www.envplan.com/abstract.cgi?id=b32167 . It also contains additional modifications to the initialization routine introduced by Fournier (2015) in: http://epb.sagepub.com/content/early/2015/11/30/0265813515618562.abstract .

#Input Format#

All inputs must be formatted as comma delimited value (CSV) files.

##Example Search Domain##

The search domain should be encoded in a binary format with cells in the feasible search domain set to a value of 1 and cells outside of the feasible search domain set to a value of 0 as below. The user need not generate a "buffer zone" of zero encoded cells surrounding the feasible search domain as this is done automatically by the algorithm at runtime.

$ cat searchDomain.csv

0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 1, 1, 1, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0;

##Example Search Objectives##

The user should note that the objective values for cells that are outside of the search domain will be automatically set to be equal to an arbitrarily high value. Specifically, the objective scores for the locations which are outside of the feasible search domain values are set to be equal to the total number of cells (feasible and otherwise) contained within the entire search domain. For an example illustration of how this work, please see below.

$ cat objective1.csv

25, 25, 25, 25, 25,
25,  2,  3,  3, 25,
25,  1,  2,  5, 25,
25,  1,  1,  4, 25,
25, 25, 25, 25, 25;

$ cat objective2.csv

25, 25, 25, 25, 25,
25,  4,  1,  3, 25,
25,  5,  3,  6, 25,
25,  2,  1,  3, 25,
25, 25, 25, 25, 25;

##Example Source and Destination Subscripts##

The source and destination subscript files should be formatted to contain, separately, the row and column subscripts corresponding to the location of the either the source or the destination within the context of the input search domain grid. These subscripts should be stored as two comma separated values on a single line of the input .csv file as below.

$ cat sourceSubs.csv

1,1

$ cat destinationSubs.csv

3,3

#Output Format#

If the Algorithm fails to converge upon a solution within the given iteration limit, an error message will be printed to the console and a basic log.cv file will be written to the local directory. This log file contains information about the computational runtime and the total number of evolutionary iterations that were executed (which in this case will be equal to the maximum number of evolutions specified by the user).

If the Algorithm successfully converges upon a solution within the given iteration limit, a success message will be printed to the console and two files will be written to the local directory. The first is a log.csv file which contains information about the same information quoted previously. The second is an output solution file which contains the row and column subscripts for each step along the solution corridor. Additionally, subsequent rows within this output file will contain the individual, stepwise, objective scores for each of the objectives, for each step along the solution corridor.

##Example Output##

A possible output solution file for the previously constructed example problem is illustrated below.

[Line #1: Solution #1 Corridor Row Subscripts] 1, 1, 1, 2, 3;
[Line #2: Solution #1 Corridor Column Subscripts] 1, 2, 3, 3, 3;
[Line #3: Solution #1 Objective 1 Scores] 2, 3, 3, 5, 4;
[Line #4: Solution #1 Objective 2 Scores] 4, 1, 3, 6, 3;
[Line #5: Solution #2 Corridor Row Subscripts] ...
[Line #6: Solution #2 Corridor Column Subscripts] ...
[Line #7: Solution #2 Objective 1 Scores] ...
[Line #8: Solution #2 Objective 2 Scores] ...
...

This pattern is repeated for each output solution requested from the final population by the user. Solutions are automatically sorted by fitness score such that the first solution is the best, the second is the second best, etc.

#Benchmarking#

Two benchmark suites have been developed for this package. The first is a single run benchmark which evaluates the performance of the algorithm for a contrived problem specification on a particular machine given a single set of evolutionary runtime parameters. This "Single" suite is usefull for getting a feel for the scaling relationships between population size, runtime, and solution quality. The second benchmark suite is a Monte Carlo based simulation which takes are particular population size setting and uses repeated solution runs. This "MonteCarlo" suite is useful for generating an estimate of the expected variation in average solution qaulity between runs due to the stochastic nature of the evolutionary optimization process. Sample usage of both benchmark suites are provided below.

##Single Benchmark Examples##

The "Single" sample test suite allows the user to benchmark both the runtime performance of the algorithm as well as the output solution quality under various parameter settings. This is done in the following set of examples using a contrived problem specification in which there is a single known, globally optimal solution, set amidst a decision space containing randomly distributed costs. This globally optimal solution, relative to the start (S) and destination (D) points, is plotted below:

Globally Optimal Solution, F = [0.0, 0.0, 0.0]:

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 S 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 D 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

###Small Population Size###

Running the benchmark with a "Small" population size [P = 1,000], as in the following command, will deliver the following output. Note the characteristics of the population at convergence reveals that a near optimal solution was found.

$ go test -bench=.SingleSmall

Final Population Distribution at Convergence [Small Population]:

[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0 1000    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0 1000    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0 1000    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0 1000    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0    0 1000    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0    0    0 1000    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0    0    0 1000    0    0    0    0    0    0    0    0    0    0    0    4    3    0    0    0    0    0]
[   0    0    0    0    0    0 1000 1000  998 1000 1000 1000 1000 1000 1000 1000 1000  996  997 1000    2    0    0    0]
[   0    0    0    0    0    0    0    0    2    0    0    0    0    0    0    0    0    0    1    0  998    2    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0  998    2    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0  998    2    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0 1000    0    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0 1000    2    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0  998    2    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0 1000    0    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0 1000    0    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0 1000    0    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0 1000    0    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0]

For this particular Small sized benchmark run, the mean fitness values for all of the individual solutions in the final output population were:

F = [8.235, 39.484, 83.719]

56 Evolutions were required to achieve convergence and the elapsed runtime, on this particular machine, was 3.84 seconds.

Medium Population Size###

Running the benchmark with a "Medium" population size [P = 10,000], as in the following command, will deliver something like the following output. Here, the quality of the output solution has improved, and in some cases may deliver the globally optimal solution.

$ go test -bench=.SingleMedium

Final Population Distribution at Convergence [Medium Population]:

[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0 10000     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0 10000     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0  9997     3     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0 10000     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0  9996     4     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0  9996     4     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0     0 10000     1     1     0     0     0     0     0     0     1     0     0     0     1     1     0     0     0     0     0]
[    0     0     0     0     0  9999  9998  9996 10000 10000 10000 10000 10000 10089 10000 10000 10000  9999  9999 10905  6410     0     0     0]
[    0     0     0     0     0     0     1     4     0     0     0     0     0     0     0     1     1     0     0     4  9997     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 10000     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 10000     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     4  9996     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     4  9995     1     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 10000     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 10000     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0  9999     1     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 10000     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 10000     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]
[    0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0]

For this particular Medium sized benchmark run the mean fitness values for all of the individual solutions in the final output population were:

F = [4.0409, 6.09, 23.1304]

48 Evolutions were required to achieve convergence and the elapsed runtime, on this particular machine, was 34.305 seconds.

###Large Population Size###

Finally, running the benchmark with a "Large" population size [P = 100,000], as in the following command, will deliver something like the following output. Here, the quality of the output solution has improved to the point in which it will nearly guarantee the delivery of the globally optimal solution for this problems specification.

$ go test -bench=.SingleLarge

Final Population Distribution at Convergence [Large Population]:

[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0      0 100000      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0      0 100000      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0      5  99994      1      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0      2  99992      6      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0     11  99985      4      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0      0  99991      9      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0      0  99989     17      2      2      2      2      4      4      3      1      1      2      3      2      5      1      3      0      0      0      0]
[     0      0      0      2  99993  99998  99996 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000  99992  99996 100000  73873      0      0      0]
[     0      0      0      0      1      0      2      3     11      1      2      1      3      2      3      6      4      3      3     22 100000      0      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      1  99998      1      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      7  99988      5      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      5 100000      1      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      3 100000     13      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      1 100000      0      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      3 100000      1      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0 100000     12      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0 100000      0      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0 100000      0      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]
[     0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0      0]

For this particular Large sized benchmark run the mean fitness values for all of the individual solutions in the final output population were:

F = [0.01451, 0.02635, 0.04418]

58 Evolutions were required to achieve convergence and the elapsed runtime, on this particular machine, was 375.358 seconds.

###Comments###

With these three single benchmark run examples, note the roughly linear scaling of runtime with increased population size relative to the roughly linear improvement in mean output solution quality with population size. This is an explicit tradeoff of the genetic algorithm approach: larger populations take longer to achieve convergence yet are more likely to deliver globally optimal solutions.

##Monte Carlo Benchmark Example##

The "MonteCarlo" sample test suite allows the user to evaluate the expected distribution of runtimes between multiple separate solution runs for the same problem specification. The Monte Carlo benchmark suite repeats the single benchmark solution process described below for a fixed number of [N = 100] simulation runs. In the process, it compiles statistics about the mean and standard deviation of average fitness values for the set of final solution populations generated during the 100 simulation runs. At conclusions, it prints these descriptive statistics to the terminal.

###Small Population Size###

Monte Carlo simulations take a long time to execute. As a result, only a small population based example is presented below. However, the benchmark code can be modifed to run this type of simulation with any desired number of samples and with a population of any size.

$ go test -bench=.MonteCarloSmall

...
Sample Size (N) = 100
Mean Population Aggregate Fitnesses | Minimum Fitness = 375.8316299999999 | 0.0
Standard Deviation of Aggregate Fitnesses = 145.1107156924006
Mean Runtime in Seconds = 4.0307659093499995
Standard Deviationof Runtimes in Seconds = 0.736894917206145

###Comments###

The Monte Carlo simulations benchmark suite is useful in helping to determine the distribution of the quality of output solutions that can be expected from certain combinations of problem specifications and evolutionary parameter settings. Due the long runtimes however, it is not advocated for use in most basic package testing scenarios.

#Author#

This project was developed by Eric Daniel Fournier [@ericdfournier] as part of his doctoral dissertation research at the University of California, Santa Barbara's Donald Bren School of Environmental Science & Management. The author would like to acknowledge the generous financial support of the Walton Family Foundation's Sustainable Water Markets Fellowship Program in making this development effort possible.

#Contact and Support#

If you have any questions about the usage of this library or would like to discuss the details of its implementation please email me@ericdfournier.com Please submit bug reports and other feature requests as issues via the GitHub repo. Thank you for your interest in this project!

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AllDistance 

func AllDistance(aSubs []int, searchDomainMatrix *mat64.Dense) (allDistMatrix *mat64.Dense)
alldistance computes the distance from each location with the input

search domain and a given point defined by an input pair of row column subscripts

func AllMinDistance 

func AllMinDistance(aSubs, bSubs []int, searchDomainMatrix *mat64.Dense) (allMinDistMatrix *mat64.Dense)
allmindistance computes the distance from each location within the

input search domain and to the nearest subscript located along the line formed by the two input subscripts

func BandMask 

func BandMask(bandValue float64, bandMatrix *mat64.Dense) (binaryBandMat *mat64.Dense)
bandmask selects the elements in a distance band matrix

corresponding to a specified input band identification number and outputs a binary matrix of the same dimensions as the distance band matrix with the values at those locations encoded as ones and all other locations encoded as zeros

func Bresenham 

func Bresenham(aSubs, bSubs []int) (lineSubs [][]int)
bresenham generates the list of subscript indices corresponding to the

euclidean shortest paths connecting two subscript pairs in discrete space

func ChromosomeCrossover 

func ChromosomeCrossover(chrom1Ind, chrom2Ind []int, chrom1Subs, chrom2Subs [][]int) (crossoverChrom [][]int)
crossover operator performs the single point crossover

operation for two input chromosomes that have previously been selected from a source population

func ChromosomeIntersection 

func ChromosomeIntersection(subs1, subs2 [][]int) (subs1Indices, subs2Indices []int)
intersection determines whether or not the subscripts

associated with two input chromosomes share any in values in common and reports their relative indices

func ChromosomeToString 

func ChromosomeToString(inputChromosome *Chromosome) (outputRawString [][]string)
function to write the values from an input

chromosome structure to an output csv file

func CsvToSubs 

func CsvToSubs(inputFilepath string) (outputSubs []int)
function to write an input comma separated value

file's contents to an output domain structure

func DigitCount 

func DigitCount(input int) (digits int)
function to count the number of digits in an input integer as

its base ten logarithm

func DirectedWalk 

func DirectedWalk(sourceSubs, destinationSubs []int, searchDomain *Domain, searchParameters *Parameters, basisSolution *Basis) (subs [][]int)
directedwalk generates a new directed walk connecting a source subscript to a

destination subscript within the context of an input search domain

func Distance 

func Distance(aSubs, bSubs []int) (dist float64)

compute euclidean distance for a pair of subscript indices

func DistanceBands 

func DistanceBands(bandCount int, distanceMatrix *mat64.Dense) (bandMatrix *mat64.Dense)
distancebands recodes a distance matrix computed from a single

source location to ordinal set of bands of increasing distance

func EliteSetToCsv 

func EliteSetToCsv(inputEliteSet []*Chromosome, outputFilepath string)
function to write the values from an input elite set

to an output csv file

func FindSubs 

func FindSubs(inputValue float64, inputMatrix *mat64.Dense) (foundSubs [][]int)
findsubs returns a 2-D slice containing the row column indices

of all of the elements contained wihtin a given input matrix that are equal in value to some provided input value

func FixMultiVariateNormalRandom 

func FixMultiVariateNormalRandom(rndsmp *mat64.Dense) (fixsmp *mat64.Dense)
fixmultivariatenormalrandom converts an input vector of bivariate normally

distributed random numbers into a version where the values have been fixed to a [-1, 0 ,1] range

func MinDistance 

func MinDistance(pSubs, aSubs, bSubs []int) (minDist float64)
compute the minimum distance between a given input point and

the subscripts comprised of a line segement joining two other input points

func MultiPartDirectedWalk 

func MultiPartDirectedWalk(nodeSubs [][]int, searchDomain *Domain, searchParameters *Parameters) (subs [][]int)
multipartdirectedwalk generates a new multipart directed walk from a given set

of input problem parameters

func MultiVariateNormalRandom 

func MultiVariateNormalRandom(mu *mat64.Dense, sigma *mat64.SymDense) (rndsmp *mat64.Dense)
multivariatenormalrandom generates pairs of bivariate normally distributed

random numbers given an input mean vector and covariance matrix

func MutationLoci 

func MutationLoci(inputChromosome *Chromosome) (previousLocus, mutationLocus, nextLocus []int, mutationIndex int)
mutationLocus to randomly select a mutation locus and return the adjacent

loci along the length of the chromosome

func MutationSubDomain 

func MutationSubDomain(previousLocus, mutationLocus, nextLocus []int, inputDomain *mat64.Dense) (outputSubDomain *mat64.Dense)
mutation sub domain returns the subdomain to be used for the mutation

specific directed walk procedure

func MutationWalk 

func MutationWalk(sourceSubs, destinationSubs []int, searchDomain *Domain, searchParameters *Parameters, basisSolution *Basis) (subs [][]int, tabuTest bool)
mutationwalk generates a new directed walk connecting a source subscript

to a destination subscript within the context of an input mutation search domain

func NeighborhoodSubs 

func NeighborhoodSubs(aSubs []int) (neighSubs [][]int)
function to return the subscript indices of the cells corresponding to the

queens neighborhood for a given subscript pair

func NewMu 

func NewMu(curSubs, dstSubs []int) (mu *mat64.Dense)
newmu generates a matrix representation of mu that reflects the

spatial orentiation between the input current subscript and the destination subscript

func NewNodeSubs 

func NewNodeSubs(searchDomain *Domain, searchParameters *Parameters) (nodeSubs [][]int)
newnodesubs generates an poutput slice of new intermediate destination nodes

that are progressively further, in terms of euclidean distance, from a given input source location and are orientation towards a given destination location

func NewRandom 

func NewRandom(mu *mat64.Dense, sigma *mat64.SymDense) (newRand []int)
newrandom repeatedly generates a new random sample from mvrnd and then fixes

it using fixrandom until the sample is comprised of a non [0, 0] case

func NewSigma 

func NewSigma(iterations int, randomness, distance float64) (sigma *mat64.SymDense)
newsigma generates a matrix representation of sigma that reflects the

number of iterations in the sampling process as well as the distance from the basis euclidean solution

func NewSubs 

func NewSubs(curSubs, destinationSubs []int, curDist float64, searchParameters *Parameters, searchDomain *Domain) (subs []int)
newsubs generates a feasible new subscript value set within the

input search domain

func NonZeroSubs 

func NonZeroSubs(inputMatrix *mat64.Dense) (nonZeroSubs [][]int)
nonzerosubs returns a 2-D slice containing the row column indices

of all nonzero elements contained wihtin a given input matrix

func Orientation 

func Orientation(aSubs, bSubs []int) (orientationVector []int)
orientation accepts as inputs a pair of point subscripts

and returns a binary vector indicating the relative orientation of the first point to the second in binary terms

func OrientationMask 

func OrientationMask(aSubs, bSubs []int, searchDomainMatrix *mat64.Dense) (orientationMask *mat64.Dense)
orientation mask returns a binary encoded matrix for

a given point where all points orientated towards a given second point are encoded as 1 and all points orientated away from the given second point as 0

func PopulationMutation 

func PopulationMutation(inputChromosomes chan *Chromosome, inputParameters *Parameters, inputObjectives *MultiObjective, inputDomain *Domain) (outputChromosomes chan *Chromosome)
function to generate mutations within a specified fraction of an input

population with those chromosomes being selected at random

func PopulationSelection 

func PopulationSelection(inputPopulation *Population, inputParameters *Parameters) (selection chan *Chromosome)
population selection operator selects half of the input

population for reproduction based upon comparative fitness and some randomized input selection fraction

func RuntimeLogToCsv 

func RuntimeLogToCsv(inputEvolution *Evolution, inputRuntime time.Duration, outputFilepath string)
function to write the runtime parameters from an evolution

to an output csv file

func SelectionCrossover 

func SelectionCrossover(inputSelection chan *Chromosome, inputParameters *Parameters, inputObjectives *MultiObjective, inputDomain *Domain) (crossover chan *Chromosome)
selection crossover operator performs a single part

crossover on each of the individuals provided in an input selection channel of chromosomes

func TranslateWalkSubs 

func TranslateWalkSubs(sourceSubs []int, inputWalkSubs [][]int) (outputWalkSubs [][]int)
function to translate the subscript index values for a given slice of input

loci relative to a given offset vector

func ValidateMutationSubDomain 

func ValidateMutationSubDomain(subSource, subDestin []int, subMat *mat64.Dense) bool
function to validate an input sub domain for use in generating

a chromosomal mutation via the random walk procedure

func ValidateTabu 

func ValidateTabu(currentSubs []int, tabuMatrix *mat64.Dense) bool
function validate the tabu neighborhood of an input pair of

row column subscripts

func ViewBasis 

func ViewBasis(basisSolution *Basis)

function to print the properties of a basis solution to the command line

func ViewChromosome 

func ViewChromosome(searchDomain *Domain, searchParameters *Parameters, inputChromosome *Chromosome)

function to print the properties of a chromosome to the command line

func ViewDomain 

func ViewDomain(searchDomain *Domain)

function to print the properties of a search domain to the command line

func ViewPopulation 

func ViewPopulation(searchDomain *Domain, searchParameters *Parameters, inputPopulation *Population)

functions to print the frequency of chromosomes in a search domain to the command line

Types

type Basis 

type Basis struct {
	Matrix *mat64.Dense // basis matrix values
	Subs   [][]int      // basis row column subscripts
	MaxLen int          // maximum length
}
a basis solution is comprised of the subscript indices forming

the euclidean shortest path connecting the source to the dest

func NewBasis 

func NewBasis(sourceSubs, destinationSubs []int, searchDomain *Domain) *Basis

new basis solution initialization function

type Chromosome 

type Chromosome struct {
	Id               uuid.UUID   // globally unique chromosome identification number
	Subs             [][]int     // chromosome row column subscripts
	Fitness          [][]float64 // objective function values
	TotalFitness     []float64   // total fitness values for each objective
	AggregateFitness float64     // total aggregate fitness value for all objectives
}
chromosomess are comprised of genes which are distinct row column

indices to some spatially reference search domain

func ChromosomeFitness 

func ChromosomeFitness(inputChromosome *Chromosome, inputObjectives *MultiObjective) (outputChromosome *Chromosome)
fitness function to generate the total fitness and chromosome

fitness values for a given input chromosome

func ChromosomeMultiMutation 

func ChromosomeMultiMutation(inputChromosome *Chromosome, inputDomain *Domain, inputParameters *Parameters, inputObjectives *MultiObjective) (outputChromosome *Chromosome)
function to generate multiple mutations on multiple separate loci on the same

input chromosome

func ChromosomeMutation 

func ChromosomeMutation(inputChromosome *Chromosome, inputDomain *Domain, inputParameters *Parameters, inputObjectives *MultiObjective) (outputChromosome *Chromosome)
function to generate a mutation within a given chromosome at a specified

number of mutation loci

func ChromosomeSelection 

func ChromosomeSelection(chrom1, chrom2 *Chromosome, selectionProb float64) (selectedChrom *Chromosome)
selection operator selects between two chromosomes with a

probability of the most fit chromosome being selected determined by the input selection probability ratio

func NewChromosome 

func NewChromosome(searchDomain *Domain, searchParameters *Parameters, searchObjectives *MultiObjective) *Chromosome

new chromosome initialization function

func NewEliteFraction 

func NewEliteFraction(inputFraction float64, inputPopulation *Population) (outputChromosomes []*Chromosome)
function to return copies of a user specified fraction of

the individual chromosomes within a population ranked in terms of individual aggregate fitness

func NewEliteSet 

func NewEliteSet(inputCount int, inputPopulation *Population, inputParameters *Parameters) (outputChromosomes []*Chromosome)
function to return copies of a user specified number of

unique individual chromosomes from within a population with each chromosome being ranked in terms of its individual aggregate fitness

func NewEmptyChromosome 

func NewEmptyChromosome(searchDomain *Domain, searchObjectives *MultiObjective) *Chromosome

new empty chromosome initialization function

type Domain 

type Domain struct {
	Rows   int          // row count
	Cols   int          // column count
	Matrix *mat64.Dense // domain matrix values
	BndCnt int          // distance band count
}
domains are comprised of boolean arrays which indicate the

feasible locations for the search algorithm

func CsvToDomain 

func CsvToDomain(inputFilepath string) (outputDomain *Domain)
function to write an input comma separated value

file's contents to an output domain structure

func NewDomain 

func NewDomain(domainMatrix *mat64.Dense) *Domain

new domain initialization function

func NewSampleDomain 

func NewSampleDomain(rows, cols int) *Domain

new sample domain initialization function

func NewSampleMutationDomain 

func NewSampleMutationDomain() *Domain

new sample mutation domain initialization function

func SubDomain 

func SubDomain(sourceLocus, destinationLocus []int, inputDomain *mat64.Dense) (subDomain *Domain, subSourceLocus, subDestinationLocus []int)
function to generate a generic subDomain for an arbitrary set of node

subscripts contained within a given input search domain

type Evolution 

type Evolution struct {
	Populations     chan *Population // population channel
	FitnessGradient []float64        // fitness gradient values
}
evolutions are comprised of a stochastic number of populations.

this number is determined by the convergence rate of the algorithm

func NewEmptyEvolution 

func NewEmptyEvolution(searchParameters *Parameters) *Evolution

new empty evolution initialization function

func NewEvolution 

func NewEvolution(searchParameters *Parameters, searchDomain *Domain, searchObjectives *MultiObjective) *Evolution

new evolution initialization function

type MultiObjective 

type MultiObjective struct {
	ObjectiveCount int          // objective count
	Objectives     []*Objective // individual objective objects
}
multiObjective objects are comprised of a channel of individual

independent objectives that are used for the evaluation of chromosome and population level fitness values

func CsvToMultiObjective 

func CsvToMultiObjective(inputFilepaths ...string) (outputMultiObjective *MultiObjective)
function to write a set of input comma separated value

files' contents to an output multiobjective structure

func NewSampleObjectives 

func NewSampleObjectives(rows, cols, objectiveCount int) *MultiObjective

new sample objective initialization function

type Mutator 

type Mutator struct {
	SearchDomain     *Domain         // local search domain copy
	SearchParameters *Parameters     // local search parameters copy
	SearchObjectives *MultiObjective // local search objectives copy
}
mutators are used to generate point location mutations in

parallel for a subset of chromosomes within a population

func NewMutator 

func NewMutator(searchDomain *Domain, searchParameters *Parameters, searchObjectives *MultiObjective) Mutator

new mutator initialization function

func (Mutator) Start 

func (m Mutator) Start(chr chan *Chromosome, mutationQueue chan bool, wg sync.WaitGroup)

mutator method to initialize a parallel mutation procedure

type Objective 

type Objective struct {
	Id     int          // objective identification number
	Matrix *mat64.Dense // objective matrix values
}
objectives are comprised of matrices which use location

indices to key to floating point fitness values within the search domain

func CsvToObjective 

func CsvToObjective(identifier int, inputFilepath string) (outputObjective *Objective)
function to write an input comma separated value

file's contents to an output objective structure

func NewObjective 

func NewObjective(identifier int, fitnessMatrix *mat64.Dense) *Objective

new objective initialization function

type Parameters 

type Parameters struct {
	SrcSubs []int   // source subscripts
	DstSubs []int   // destination subscripts
	RndCoef float64 // randomness coefficient
	PopSize int     // population size
	SelFrac float64 // selection fraction
	SelProb float64 // selection probability
	MutaCnt int     // muation count
	MutaFrc float64 // muation fraction
	EvoSize int     // evolution size
	ConSize int     // concurrency limit
}
parameters are comprised of fixed input avlues that are

unique to the problem specification that are referenced by the algorithm at various stage of the solution process

func NewParameters 

func NewParameters(sourceSubscripts, destinationSubscripts []int, populationSize, evolutionSize int, randomnessCoefficient float64) *Parameters

new problem parameters function

func NewSampleParameters 

func NewSampleParameters(searchDomain *Domain) *Parameters

new sample parameters initialization function

type Population 

type Population struct {
	Id                   int              // population ordinal identification number
	Chromosomes          chan *Chromosome // chromosome channel
	MeanFitness          []float64        // chromosome mean fitnesses channel
	AggregateMeanFitness float64          // chromosome aggregate fitness channel
}
populations are comprised of a fixed number of chromosomes.

this number corresponds to the populationSize.

func NewEmptyPopulation 

func NewEmptyPopulation(identifier int, searchObjectives *MultiObjective) *Population

new empty population initialization function

func NewPopulation 

func NewPopulation(identifier int, searchDomain *Domain, searchParameters *Parameters, searchObjectives *MultiObjective) *Population

new population initialization function

func PopulationEvolution 

func PopulationEvolution(inputPopulation *Population, inputDomain *Domain, inputParameters *Parameters, inputObjectives *MultiObjective) (outputPopulation *Population)
population evolution operator generates a new population

from an input population using the selection and crossover operators

func PopulationFitness 

func PopulationFitness(inputPopulation *Population, inputParameters *Parameters, inputObjectives *MultiObjective) (outputPopulation *Population)
fitness function generate the mean fitness values for all of the chromosomes

in a given population

type Walker 

type Walker struct {
	Id               uuid.UUID       // globally unique walker identification number
	SearchDomain     *Domain         // local search domain copy
	SearchParameters *Parameters     // local search parameters copy
	SearchObjectives *MultiObjective // local search objectives copy
}
walkers are used in the concurrency model which facilitates

the parallel problem initializations

func NewWalker 

func NewWalker(searchDomain *Domain, searchParameters *Parameters, searchObjectives *MultiObjective) Walker

new walker initialization function

func (Walker) Start 

func (w Walker) Start(chr chan *Chromosome, walkQueue chan bool, wg sync.WaitGroup)

walker method to initialize a parallel pseudo random walk

Source Files

View all Source files

Directories

Path Synopsis
problems
Fresno command
Oxnard command
SanBernadino command
SanBernadinoValidation command
SanDiego command
SantaBarbara command

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.