Genetic Algorithm for Solving Optimization Problems in C++

The genetic algorithm (GA) is a metaheuristic algorithm inspired by Charles Darwin’s theory of natural selection and belongs to the class of evolutionary algorithms (EA). The algorithm was pioneered by John Holland (the 1960s and 1970s).

Genetic algorithms have a number of advantages over conventional optimization techniques. GA can handle complex fitness (objective) functions that can be linear or nonlinear, continuous or discontinuous, or subject to random noise.
Since the algorithm is parametrized, regarding the population size, chromosomes (here considered as the size of the subgroup) taken to elitism, crossover, and mutation require tuning. The author of the following article did not face problems since the solve problem is complex (robot path planner).

As we can assume the GA is based on biological principles whereby natural selection we can initial population (in our case robot positions or generally initially chosen values of objective functions) and apply genetic operations (choice of the best solution/robot positions), crossover (vide swapping) or mutation we can approach optimal solution for the given problem.

Please note, in the following article, I do use biological nomenclature.

Genetic Operations

The genetic algorithm uses three leading genetic operators: crossover,
mutation, and selection.

Deployed GA in C++ starting from (please note that before the algorithm launches we need to divide the whole population into the subgroups. For each subgroup we apply only one operation):

• Selection, or elitism. The use of solutions with high fitness to pass
  on to the next generations is often carried out in terms of some form of a selection of the best solutions. In our case, we are looking for a minimum value.

Elitism in GA (by author)

• Crossover. Swapping parts of the solution with another in chromosomes or solution representations. The main role is to provide an exchange of the part of the randomly chosen chromosomes. In our case, the chromosome is considered a solution in a certain space (XY or XYZ).
  See the below figure.

CrossOver in GA (by author)

• Mutation. The change of parts of one solution randomly increases the diversity of the population and provides a mechanism for escaping from a local optimum.
  See the below figure.

Mutation in GA (by author)

For the path planer (XY) we can depict the genetic algorithm and applicable operations as follows.

Genetic Algorithm and operations (by author).

As it was mentioned above I used the GA to solve problems related to robot path planners 2D and 3D. Before I started with path planners I verified the performance of the algorithm running for simple objective function (quadratic). You are encouraged to apply for your specific. Source code with implementations in C++ you will find on my GitHub.

In the path planner case, the GA algorithm optimizes the position of the robot in order to find collision-free (path 2D or 3D space) between the start and the goal. As I mentioned in my previous article, path planning for 3D space is applicable mainly for drones or other robots “without” kinematics. Generally, for manipulators, we are looking solutions in joint space.

Pseudo-code can be depicted as follows,

Pseudo-code of GA (by author)

The objective function of the robot path planner

Similarly to my previous article, I applied the same objective (cost) function. The cost function that the algorithm is trying to optimize (compute minimum) can be defined as follows,

where,

distance firefly — obstacle,

• for 2D path planner

• for 3D path planner

distance firefly — goal,

• for 2D path planner

• for 3D path planner

K1 and K2 are coefficients taken from the article.

The optimal values of all constants depicted in the above formulas are taken from the article I refer to.

Performance of a discussed algorithm for different parameter setups. Please note it was not possible to plot in 3D the obstacle.

Run 1. 3D

Run 2. 3D

Run 1. 2D

Run 2. 2D

Plotting requires incorporating the header file which has to be in the same folder as your cpp (a file you can clone from my repository).
Your program can be compiled as follows,

//compile
g++ my_prog.cpp -o my_prog -I/usr/include/python3.8 -lpython3.8//

 //run
./my_prog

//folder tree

├── my_prog
├── my_prog.cpp
├── matplotlibcpp.h

Thank you for reading.