Metaheuristics optimizations:

Setup

Run on python 3.7

pip install -r requirements.txt

Discrete Optimization:

TSP problems:

National Traveling salesman problems from math.uwaterloo.ca

Djibouti:

• 38 cities
• optimal tour: 6656

Qatar:

• 194 cities
• optimal tour: 9352

Algorithm used:

• Genetic algorithm, well suited for this kind of problem: each chromosome represent a route through all cities. Each gene represent a city. All chromosomes are permutation of the genes.

Comments:

• For Djibouti, GA shows good results in a relatively short computational time.

• For Qatar, I was not able to get good results with applying GA right away. Jmetalpy library was slow, so I decided to switch to DEAP library. Results were better and faster but still far from optimal route.

  I found some interesting reading on how to initialize population here: the idea is to:

  • create clusters of cities using simple k-means

  • find the optimal path between clusters (using GA)

  • for each cluster find optimal path (using GA)

    example Djibouti:

    

  • link clusters together by disconnecting one edge of the cluster and linking it to next one randomly to create initial population

  • run a GA on this new suboptimal population.

Comparison results in table below for Djibouti:

jmetalpy	DEAP	Kmean + DEAP
notebook	notebook	notebook

Comparison results in table below for Qatar:

jmetalpy	DEAP	Kmean + DEAP
notebook	notebook	notebook

Continuous Optimization:

Target is to optimize benchmark functions (F1 to F6) from CEC2008: description here

Optimization done in dimension 50 and 500.

Library used: Scipy / Pygmo

Note on the use CEC functions and data:

Data and functions code have been provided in C. In order to use it easily with Python, I extracted data to csv file using this notebook, and recoded the function evaluation in python. To speed up the execution of the code, I used the Numba library which basically recompile the functions at execution time, making execution much faster.

Dimension 50 Results:

I used Pygmo for optimizing all functions except shifted sphere that i did using scipy.

For dimension 50, most of the algorithm are able to converge to global optimum with some parameters finetuning. I decided to try most of them to compare.

	F1	F2	F3	F4	F5	F6
	Shifted Sphere	Schwefel pb 2.21	Shifted Rosenbrock	Shifted Rastrigin	Shifted Griewank	Shifted Ackley
	notebook	notebook	notebook	notebook	notebook	notebook
Algo used	BFGS	sa-DE1220	DE	SGA	PSO	ABC
Fitness	0	~0	~0	~0	~0	~0
Nb of func eval	520	500 100	273 450	1 250 000	1 250 000	750 000
Comp Time (sec)	0.22	1.94	1.15	6.93	7.63	4.33

Dimension 500 Results:

Much more difficult in dimension 500, PSO shows good results. I have not been able to reach global optimum for Schwefel problem and Rosenbrock within a limit of 5.000.000 of function evaluations.

	F1	F2	F3	F4	F5	F6
	Shifted Sphere	Schwefel pb 2.21	Shifted Rosenbrock	Shifted Rastrigin	Shifted Griewank	Shifted Ackley
	notebook	notebook	notebook	notebook	notebook	notebook
Algo used	BFGS	SGA	sa-DE1220	saDE	PSO	PSO
Fitness	0	5.83	865	~0	~0	~0
Nb of func eval	5 522	5 000 000	5 000 000	555 400	750 000	500 000
Comp Time (sec)	0.28	96.08	44	9.7	37.95	22.68

F1: Shifted Sphere

Simple function, using a BFGS algorithm (Quasi Newton family) can solve it fast: less than 1 sec in dimension 500.

Dimension 50	Dimension 500
notebook	notebook

F2: Schwefel problem 2.21

Dimension 50	Dimension 500
notebook	notebook

F3: Shifted Rosenbrock

Dimension 50	Dimension 500
notebook	notebook

F4: Shifted Rastrigin

Dimension 50	Dimension 500
notebook	notebook

F6: Shifted Griewank

Dimension 50	Dimension 500
notebook	notebook

F6: Shifted Ackley

Dimension 50	Dimension 500
notebook	notebook