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