Plan Max Manfrin
From IridiaWiki
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
Parallelization of ACO algorithms
Milestone I: Jan - Mar 2006
- Acquire practical experience in explicit parallelization on ACO algorithms
- Start from sequential ACOTSP and implement various MPI variants
- Sync
- Multicolony - completly-connected
- each colony identifies the best bsf and grab it
- the colony with the worst bsf grab the best bsf
- Multicolony - ring
- Multicolony - hypercube
- Single colony, multi local search
- Multicolony - completly-connected
- Async
- Multicolony - completly-connected
- each colony identifies the best bsf and grab it
- the colony with the worst bsf grab the best bsf
- Multicolony - ring
- Multicolony - hypercube
- Single colony, multi local search
- Multicolony - completly-connected
- Sync
- Start from sequential ACOTSP and implement various MPI variants
- Paper submission to ANTS 2006 of "explicit parallelization of ACOTSP"
Milestone II : Apr - Jun 2006
- Evolve practical experience in explicit parallelization on ACO algorithms
- Start from sequential ILK-H and parallelize it with MPI, calling it within parallel ACOTSP
- Acquire practical experience in implicit parallelization on ACO algorithms
- Start from sequential ACOTSP and implement various OpenMP variants
- Sync ( i.e. implicit barrier in for directives)
- Async (i.e use of the nowait clause)
- Start from sequential ACOTSP and implement various OpenMP variants
Milestone III : Jul - Sep 2006
- Transfer the knowledge and experience on TSP to other problems
- Move to Vehicle Routing Problem
- Collaboration with Marco Caserta on parallel ACO for Set Covering Problem
Milestone IV : Oct - Dec 2006
- Add complexity to the VRP problem moving into Rich VRP
Milestone V : Jan - Mar 2007
Milestone VI : Apr - Jun 2007
Milestone VII : Jul - Sep 2007
- Write PhD thesis
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 | ||
| Implement Asynch versions | |||||
| Experiments on TSP instances (1000 < size < 6000) | Feb 26, 2006 | in progress | |||
| 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 | Feb 21 | ||||
| 1.3 Sync - Multicolony - replace-worst | Feb 19 | Feb 21 | Feb 19 | completed | test before launching experiments |
| 1.3 Sync - Multicolony - 3D hypercube | Feb 21 | ||||
| 1.4 Sync - MultiLS | Feb 19 | Feb 21 | Feb 19 | completed | test before launching experiments |
| 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 | Feb 19 | Feb 21 | Feb 19 | done | |
| 2.2 Read the paper: M. Middendorf, F. Reischle, and H. Schmeck. Multi colony ant algorithms. Journal of Heuristics, 8(3):305â320, May 2002. | Feb 21 | ||||
| 3 Implement async versions | In case of problem try to get help from Anders | ||||
| 3.1 Async - Multicolony - all-all | |||||
| 3.2 Async - Multicolony - ring | |||||
| 3.3 Async - Multicolony - 3D hypercube | |||||
| 3.4 Asynch - MultiLS |
Seminars participation
| Title | Author | Location | Dates |
|---|---|---|---|
| 2nd BEGrid tutorial | - | ULB | Feb 21, 2006 |
Events participation
| Event | Location | Dates |
|---|
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 | |
| Update Dorigo website with new portoguese interview | Feb 19, 2006 |
