Plan Max Manfrin
History (past work)
http://iridia.ulb.ac.be/wiki/index.php/History_Max_Manfrin
Plan (future work)
- Investigate the effect of parallelization on Ant Colony Optimization algorithms
Goals
- Acquire practical experience in parallelization on ACO algorithms (both explicit and implicit parallelism)
- Submit paper to ANTS 2006 (on explicit parallelism - MPI)
Things to do
| Description | Start date | Deadline | Time required | status | Real deadline |
|---|---|---|---|---|---|
| Study MPI | Nov 14, 2005 | ongoing process | In progress | ||
| Explicit parallelization of ACOTSP using MPI | Nov 14, 2005 | Jan 8, 2006 | ~9 weeks | done | Jan 24, 2006 |
| Synch version of "One colony - many LS (3-opt)" | Nov 14, 2005 | Dec 5, 2005 | ~26 days | done | Jan 24, 2006 |
| Synch version of "Many homogeneous colonies - all-all" | Dec 10, 2005 | Dec 22, 2005 | ~13 days | done | Jan 24, 2006 |
| --= DISCUSSION WITH MARCO, MAURO, THOMAS =-- | Jan 30, 2006 | ||||
| Profile sequential ACOTSP code with instaces (1000 < size < 2000) | Jan 30, 2006 | 1 day | done | ||
| Add # iterations as stopping criterion | |||||
| Asynch version of "Many homogeneous colonies - ring" | Feb 1, 2006 | 4 days | done | ||
| Implement cube topology | Feb 6, 2006 | in progress | |||
| Implement synch version of "Many heterogeneous colonies - all-all/ring/cube | |||||
| Patch ILK-H for MPI usage | |||||
| Implement asynch version of "One colony - many LS" | |||||
| Implement asynch version of "Many homogeneous colonies - all-all/ring/cube" | |||||
| Implement asynch version of "Many heterogeneous colonies - all-all/ring/cube" | |||||
| Tuning of parallel parameters with F-Race | |||||
| Experiments on TSP instances (1000 < size < 6000) | Feb 26, 2006 | ||||
| Abstract submission for ANTS 2006 | Mar 12, 2006 | ||||
| Submission of paper for ANTS 2006 | Mar 19, 2006 |
| Description | Start date | Deadline | Time required | status |
|---|---|---|---|---|
| Study OpenMP | Jan 9, 2005 | ongoing process | In progress | |
| Implicit parallelization of ACOTSP using OpenMP | - | - | - | Need a compiler |
Weekly planning
| Description | Start date | Deadline | Completion date | status | Note |
|---|---|---|---|---|---|
| 1. Patch the algorithms in such a way that they use only globabl best in pheromone update and they use quadrant nearest neighbour | Feb 16 | Feb 21 | in progress | ||
| 1.1 Sync - Multicolony - all-all | Feb 16 | Feb 21 | Feb 19 | completed | experiments running |
| 1.2 Sync - Multicolony - ring | |||||
| 1.3 Sync - Multicolony - replace-worst | |||||
| 1.4 Sync - MultiLS | |||||
| 2.1 Send to Thomas and Mauro a list of all paper that deals with Parallel ACO for TSP that contains experimental results in order to check what the others have been doing | |||||
| 2.2 2.2 Read the paper
@article{MidReiSch02tsp_qap, Abstract = {In multi colony ant algorithms several colonies of ants cooperate in finding good solutions for an optimization problem. At certain time steps the colonies exchange information about good solutions. If the amount of exchanged information is not too large multi colony ant algorithms can be easily parallelized in a natural way by placing the colonies on different processors. In this paper we study the behaviour of multi colony ant algorithms with different kinds of information exchange between the colonies. Moreover we compare the behaviour of different numbers of colonies with a multi start single colony ant algorithm. As test problems we use the Traveling Salesperson problem and the Quadratic Assignment problem. }, Address = {Amsterdam, The Netherlands}, Author = {Middendorf, M. and Reischle, F. and Schmeck, H.}, Date-Added = {2004-12-01 11:54:23 +0100}, Date-Modified = {2005-03-09 10:21:33 +0100}, Journal = {Journal of Heuristics}, Local-Url = {file://localhost/Users/mmanfrin/Library/texmf/bibtex/bib/documents/MidReiSch02tsp_qap.pdf}, Month = {May}, Number = {3}, Pages = {305--320}, Publisher = {Kluwer Academic Publishers}, Title = {Multi Colony Ant Algorithms}, Volume = {8}, Year = {2002}} |
Seminars participation
| Title | Author | Location | Dates |
|---|---|---|---|
| 2nd BEGrid tutorial | - | ULB | Feb 21, 2006 |
Events participation
| Event | Location | Dates |
|---|---|---|
| Matinée Jeunes Chercheurs | Building U - Solbosch Campus | Feb 17, 2006 - from 10:00 to 14:00 |
| prepare poster on ACO | done | |
| prepare demo for ACOTSP | before Feb 15, 2006 |
Papers to write
| Title | Journal/Conference targeted | Start date | Submission deadline |
|---|---|---|---|
| A Survey of Parallel ACO algorithms | N.A. | N.A. | N.A. |
| Process-level parallelization of ACOTSP | Ants 2006 international workshop | N.A. | Mar 12, 2006 |
| Thread-level parallelization of ACOTSP | N.A. | N.A. | N.A. |
Referee activities
International journals
| Journal | # papers | paper received on | review to submit before |
|---|---|---|---|
| European Journal of Operational Research | 1 | Dec 21, 2005 | Jan 31, 2006 |
International conferences
| Conference | # papers | paper received on | review to submit before |
|---|---|---|---|
| GECCO 2006 | 5 | Feb 6, 2006 | Mar 20, 2006 |
| WSC11 | 3-4 (estimation) | May/June 2006 | 30 Jun 2006 |
IRIDIA chores
| Chore | assigned | status |
|---|---|---|
| Update Dorigo website with Master, DEA, and PhD thesis data | Feb 2, 2006 |
