X

Download Ant Colony Optimization Wiki PowerPoint Presentation

SlidesFinder-Advertising-Design.jpg

Login   OR  Register
X


Iframe embed code :



Presentation url :

Home / Forest & Animals / Forest & Animals Presentations / Ant Colony Optimization Wiki PowerPoint Presentation

Ant Colony Optimization Wiki PowerPoint Presentation

Ppt Presentation Embed Code   Zoom Ppt Presentation

PowerPoint is the world's most popular presentation software which can let you create professional Ant Colony Optimization Wiki powerpoint presentation easily and in no time. This helps you give your presentation on Ant Colony Optimization Wiki in a conference, a school lecture, a business proposal, in a webinar and business and professional representations.

The uploader spent his/her valuable time to create this Ant Colony Optimization Wiki powerpoint presentation slides, to share his/her useful content with the world. This ppt presentation uploaded by worldwideweb in Forest & Animals ppt presentation category is available for free download,and can be used according to your industries like finance, marketing, education, health and many more.

About This Presentation

Slide 1 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri
Slide 2 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad
Slide 3 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications
Slide 4 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf
Slide 5 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf
Slide 6 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf
Slide 7 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf
Slide 8 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf
Slide 9 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf
Slide 10 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature
Slide 11 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode
Slide 12 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch)
Slide 13 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date
Slide 14 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date
Slide 15 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant
Slide 16 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150
Slide 17 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B
Slide 18 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B
Slide 19 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B
Slide 20 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B
Slide 21 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B
Slide 22 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B
Slide 23 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420
Slide 24 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length)
Slide 25 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 26 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 27 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 28 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 29 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 30 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 31 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 32 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 33 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 34 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 35 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 36 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 37 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 38 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 39 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 40 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 41 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 42 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 43 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 44 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 45 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 46 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 47 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 48 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 49 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 50 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 51 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 52 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 53 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 54 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 55 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 56 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 57 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 58 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 59 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 60 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 61 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 62 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 63 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 64 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 65 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 66 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 67 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 68 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 69 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 70 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 71 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 72 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 73 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 74 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 75 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 76 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 77 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 78 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 79 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 80 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 81 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 82 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 83 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 84 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 85 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 86 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 87 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 88 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 89 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 90 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 91 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 92 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 93 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 94 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 95 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 96 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC
Slide 97 - Ant Colony Optimization Prepared by: Ahmad Elshamli, Daniel Asmar, Fadi Elmasri Presentation Outline Section I (Introduction) Historical Background Ant System Modified algorithms Section II (Applications) TSP QAP Section III (Applications +Conclusions) NRP VRP Conclusions, limitations and Danny Fadi Ahmad Section 1 Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications Swarm intelligence Collective system capable of accomplishing difficult tasks in dynamic and varied environments without any external guidance or control and with no central coordination Achieving a collective performance which could not normally be achieved by an individual acting alone Constituting a natural model particularly suited to distributed problem solving http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch) Work to date Work to date How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the const. solution Pheromone: Memory: MK or TabuK Next move: Use probability to move ant A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150 Iteration 1 A E D C B How to build next sub-solution? A E D C B Iteration 2 A E D C B Iteration 3 A E D C B Iteration 4 A E D C B Iteration 5 A E D C B Path and Pheromone Evaluation L1 =300 L2 =450 L3 =260 L4 =280 L5 =420 End of First Run All ants die New ants are born Save Best Tour (Sequence and length) Ant System (Ant Cycle) Dorigo [1] 1991 t = 0; NC = 0; τij(t)=c for ∆τij=0 Place the m ants on the n nodes Update tabuk(s) Compute the length Lk of every ant Update the shortest tour found = For every edge (i,j) Compute For k:=1 to m do Initialize Choose the city j to move to. Use probability Tabu list management Move k-th ant to town j. Insert town j in tabuk(s) Set t = t + n; NC=NC+1; ∆τij=0 NC