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

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
    • 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

Milestone II : Apr - Jun 2006

• Acquire practical experience in implicit parallelization on ACO algorithms
  • Start from sequential ACOTSP and implement various OpenMP variants

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