ericdfournier / mogador

Multi-Objective Genetic Algorithm for Corridor Location Problems

#MOGADOR

MOGADOR is genetic algorithm that can be used to generate good solutions to multi-objective corridor location problems. Within this repository, the algorithm has been implmented in the MATLAB intepreted programming environment for ease of use and inspection. It should primarily be considered of value in a teaching/learning context due to its single threaded execution and modest runtime performance. A newer, faster, and fully parallelized version of the algorithm has been implemented by the author using the Go programming language. This version should should be preferred for use in all serious real world corridor planning applications.

The Go version of the algorithm is hosted at: github.com/ericdfournier/corridor

INSTALLATION

• Clone Git Repository: cd into a working directory of choice and clone the git repository via the following shell commands (on mac)

$ cd ~
$ git clone https://github.com/ericdfournier/MOGADOR.git

• Download and Unpack Zipped Git Repository: cd into a working directory of choice and unzip the zipped version of the repository downloaded from the project github page via the following shell commands (on mac)

$ mkdir ~/MOGADOR
$ cd ~/MOGADOR
$ unzip MOGADOR.zip

DESCRIPTION

(MOGADOR) Multiobjective Genetic Algorithm for Corridor Location Problems

PLATFORM

• MATLAB Version: 8.1.0.604 (R2013a)

DEPENDENCIES

• Image Processing Toolbox Version 8.2

• Mapping Toolbox Version 3.7

• Statistics Toolbox Version 8.2

• Note: The GUI elements have been developed for use in a Mac OS X environment

REFERENCES

• Zhang, X., & Armstrong, M. P. (2008). Genetic algorithms and the corridor location problem: multiple objectives and alternative solutions. Environment and Planning B: Planning and Design, 35(1), 148–168. doi:10.1068/b32167

DETAILS

• Corridor planning often falls into the domain of multiobjective evaluation. MOGADOR is a multiobjective genentic algorithm for corridor location problems which produces a wide range of feasible corridor alternatives to help decision makers understand tradeoffs among competing objectives.

mogador's Issues

Create a non-point mutation routine using the pseudo random walk procedure

It may be useful to have a non-point mutation routine to generate mutated path sections in those instances where the initial population has been generated using the multi-part euclidean shortest path population initiation procedure. Such a method might introduce valuable non-linear variations into these paths in a limited manner so as to reduce the locality of the final solutions.

main.m - Develop Convergence Criteria for GA

Need to develop a set of convergence criteria to determine the stopping condition for the GA

• Convergence criteria should be based on the derivative of the aggregate fitness of successive generations of populations

Modify convergence criteria to be based upon fitness z-score

Right now the convergence criteria is based upon the first and second derivative of the raw average fitness scores from each population generated in the model epochs. This may or may not be the most efficient way to do this as the z-score may prevent issues having to do with the scaling of mean fitness scores for problems of different size.

Need to implement screening procedure to eliminate violating individuals

There are instances where, for a number of reasons, individuals are generated within populations which have one or more of the following attributes:

1. Closed cycles
2. Discontinuities
3. Exit the search domain
   These individuals need to be located and eliminated from within the population at each generation so that their non-viable genetic material is not inherited and thus computational time and resources wasted in their propagation.

Optimize epigenetic smoothing function using the douglas-peuker algorithm.

initPopFncDEV.m - Begin Transition to Production Version

Need to functionalize the following four components:

• Single Part Convex
• Single Part Concave
• Multi-Part Convex
• Multi-Part Concave

PARALLELIZE THE POPULATION INITIATION PROCEDURE

The population initialization procedure can be parallelized significantly (1 individual per thread). Investigate this further.