Skip to content
This repository has been archived by the owner on Jul 16, 2024. It is now read-only.

GSoC 2010 Meta

Jump to bottom
magnific0 edited this page Feb 25, 2014 · 3 revisions

The Implementation of Bio-Inspired State-of-the-Art Meta-Heuristic Algorithms project aims for adding recent developments in the flourishing field of bio-inspired algorithms which clearly indicate the potential of the approach. Monkeys, school of fishes, bees, ants, glow-worms, fireflies, moths are endless source of inspirations to university groups spread all over the world. While of possibly limited effectiveness in some global optimisation problems, these algorithms are undoubtedly very very cool and fascinating, and PaGMO needs them all (especially taking into account the often relatively low entry barrier of their functioning).

Student: Andrea Mambrini

Mentors: Dario Izzo, Francesco Biscani

Previous Work / Context

to be added

**Technical Details:**The implementation of the most recent meta-heuristics as classes derived from pagmo::algorithm is the main aim of this project. These would include bee colony, glowworm, firefly, ant colony, monkey search, Cuckoo search and their extensions (when possible) to integer, multiobjective, constrained optimization. Also the extension of the currently available meta-heuristics in PaGMO (genetic strategies, particle swarm, harmony search, etc.) will be considered. The different algorithms performance should be tuned on selected test sets. All algorithms will be coded in c++ and exposed in python.

Status of the work

All the algorithms compile, run without segfaults and have been checked with valgrind.

Bee Colony Optimization Algorithm

It work properly. It has been tested on some continuous optimization problems. Results have been compared to the ones in paper D. Karaboga, B. Basturk, A powerful and Efficient Algorithm for Numerical Function Optimization: Artificial Bee Colony (ABC) Algorithm and they appear equally good.

Firefly Optimization Algorithm

Implemented and tested. Many performance tests have been done to chose the best way to calculate gamma and the attractiveness to maximize performances. The algorithm still perform worse than bee colony but it provides good solutions on many tests problems (i.e. De Jong, Rosenbrock, Himmelblau)

Cross Entropy Algorithm

Implemented for continuous optimization. Results of tests are good with mono-dimensional problems. They get much worse with multidimensional problems. We are not sure what is the reason. TODO: check implementation for multidimensional problems.

Ant Colony Optimization Algorithm

It has been implemented to solve any combinatorial optimization problem. It has been tested on some instances of the Knapsack Problem and the Travelling Salesman problem and it works properly. TODO: test with large dataset. Many of them can be found in TSPLIB

NSGA-II

It has problems to reproduce the results from the paper A fast and elitist multiobjective genetic algorithm: NSGA-II -- Kalyanmoy Deb et. al.. TODO: check implementation and fix it in order to reproduce test results from the paper.

TSP Gui

It is possible to:

  • Draw a graph and set edge's weight (distances between cities)

  • Load and Save a graph

  • Solve it with Ant Colony Optimization and visualize the solution TODO:

  • improve the usability

  • add the ability to delete edges and nodes

  • ability to visualize cities as point in the space so that the distance between them is the euclidean distance between points in the space

  • import and visualize datasets from TSPLIB

HowTo

TSP GUI

You need to Guide_to_Compilation pagmo with PyGMO support. After that just run the TSP GUI from the pagmo directory as python tools/tsp.py

  • Double left click: add node
  • Right click on a source node and on a destination node: add an edge
  • Left click on an edge: edit edge's weight A screencast is also available.

Python tests

An example of how to use pagmo with python can be found in PyGMO/init.py You need to Guide_to_Compilation pagmo with PyGMO support. The function run_test() test some algorithm on continuous optimization problems. To run the test you just need to open a python shell (i.e. ipython) and then run from PyGMO import * run_test() The function test_aco() test the Ant Colony Optimization algorithm on a simple instance of the Travelling Salesman Problem. CAVEAT: if you edit PyGMO/init.py you need to run make && make install to see the changes. There is also a screencast available.

C++ tests

An example of how to use pagmo with C++ can be found in examples/migrate_or_not.cpp To run this example you just need to Guide_to_Compilation pagmo and run

./build/examples/migrate_or_not

Documentation

Ongoing activities

Improving documentation/wiki. Last fixes in the code.

Have-done list

  • Implemented ZDT1, ZDT2, ZDT3, ZDT4, ZDT6 multiobjectives problems --Amambrini 16:20, 16 August 2010 (UTC)

  • Implemented NGSA-II algorithm --Amambrini 16:20, 16 August 2010 (UTC)

  • Implemented SCH, FON, POL, KUR multi objective optimization problems --Amambrini 09:21, 14 August 2010 (UTC)

  • Ant Colony Optimization algorithm --Amambrini 09:21, 14 August 2010 (UTC)

  • Michalewicz problem -- --Amambrini 14:08, 8 July 2010 (UTC)

  • De Jong's problem -- --Amambrini 14:08, 8 July 2010 (UTC)

  • Travelling salesman problem - Python GUI to instantiate problems -- --Amambrini 14:08, 8 July 2010 (UTC)

  • Cross Entropy method -- --Amambrini 14:08, 8 July 2010 (UTC)

  • Travelling salesman problem -- --Amambrini 14:08, 8 July 2010 (UTC)

  • Implemented python tests --Amambrini 21:34, 7 June 2010 (UTC)

  • Firefly algorithm --Amambrini 21:34, 7 June 2010 (UTC)

  • Artificial Bee Colony Algorithm --Amambrini 10:19, 28 May 2010 (UTC)

  • Python exposition completed for all the algorithms and all the problems --Amambrini 10:19, 28 May 2010 (UTC)

Reports

  • list of reports produced
Clone this wiki locally