Home

Genetic Algorithm (genetic_algo)

This is a C++ repository which contains generic implementation of Genetic Algorithm and its example applications for solving various constraint-satisfaction and optimization problems. Generality is one of the key features of this repository. It can be used to solve problems in a variety of problem domains. The problem specific parts have been isolated from the class containing the general algorithm. As a problem is selected, these problem specific parts get defined. For most of the common problems, you can use the implementation provided in the example applications.

Overview

• Repository
• Run Demo
• Minimize a function
• Solve a different problem

Repository

• include/ - contains ga header file and should be included in running all demo examples
• src/examples/
  • n_queen/ - contains demo example of solving nqueen problem
  • math_functions/ - contains a general 2-variable function_minimizer_ga and demos of minimizing functions

Run Demo

It uses some C++11 features and would require a C++11 compliant compiler for compilation. If you have already installed such compiler then you can compile the code and run demo as test.

For GNU compiler use -std=c++11 while compiling :

g++ -std=c++11

Use CMake

For compiling all the demos in one go, you can also use CMake to generate a Makefile. For CMake select the root directory genetic_algo as your source directory. After generating Makefile and running make command, you can find the demo executables inside bin folder of your build directory.

Minimize a function

If you have a 2-variable function to minimize then you can use the function_minimizer_ga class. All you need to do is write a main class, define your function and run the function_minimizer_ga for this function.

// in file some_function_min.cpp

# include "function_minimizer_ga.h"    // header for function_minimizer_ga


double some_func(double x, double y)    // your function definition
{
    // define function f_xy

    return f_xy;
}

int main()
{
    function_minimizer_ga some_func_min_ga(&some_func, xmin, ymin, xmax, ymax);

    some_func_min_ga.setParameters(100, 1000, 0.9, 0.02, -1, true);    // tune ga parameters

   // run your GA
   // and display the results

    return 0;
}

Basic Steps

• Add a method some_func that takes x and y and returns the function value at this point.
• In the main method, create an object of function_minimizer_ga
  • Pass the function pointer of some_func function
  • Also pass min and max values of x and y over which you are minimizing the function
• Set and tune your GA parameters by running it

Solve a different problem

If you have a different problem to solve and you want to use Genetic Algorithm, then you have to first decide several key features of the GA that you are going to write.

• select type parameter T that would represent a candidate solution (in common cases it would be vector<int>).

At this point you can extend the simple_ga<T> class (the "ga.h" file contains simple_ga<T> class). In this subclass you have to implement several methods that have not been defined in simple_ga class. Implement these methods:

• define random generation of T (generating a random candidate solution)
• define fitness function for T (fitness of a candidate solution)
• define display of T (displaying of a candidate solution)
• define crossover operator for two T parents to generate another T offspring
• define mutation operator on T

Optionally you can also override

• the stopping criteria of GA