Download Ant Colony Optimization Mathematical Sciences PowerPoint Presentation

Iframe embed code :

Unable to generate embed code for this presentation.request for embed code @ mail[at]slidesfinder.com

Presentation url :

Home / Science & Technology / Science & Technology Presentations / Ant Colony Optimization Mathematical Sciences PowerPoint Presentation

Ant Colony Optimization Mathematical Sciences PowerPoint Presentation

PowerPoint is the world's most popular presentation software which can let you create professional Ant Colony Optimization Mathematical Sciences powerpoint presentation easily and in no time. This helps you give your presentation on Ant Colony Optimization Mathematical Sciences 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 Mathematical Sciences powerpoint presentation slides, to share his/her useful content with the world. This ppt presentation uploaded by worldwideweb in Science & Technology 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

worldwideweb

Description : PowerPoint presentation on Ant Colony Optimization Mathematical Sciences, download now ppt of Ant Colony Optimization Mathematical Sciences

Tags : Ant Colony Optimization Mathematical Sciences

Published on : Jan 08, 2015
Views : 1330 | Downloads : 0

Download Now

Share on Social Media

Slide 1 -

Ant Colony Optimization 22c: 145, Chapter 12

Slide 2 -

ppt slide no 2 content not found

Slide 3 -

Outline Introduction (Swarm intelligence) Natural behavior of ants First Algorithm: Ant System Improvements to Ant System Applications

Slide 4 -

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

Slide 5 -

http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf

Slide 6 -

http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf

Slide 7 -

http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf

Slide 8 -

http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf

Slide 9 -

Inherent features Inherent parallelism Stochastic nature Adaptivity Use of positive feedback Autocatalytic in nature

Slide 10 -

Natural behavior of an ant Foraging modes Wander mode Search mode Return mode Attracted mode Trace mode Carry mode

Slide 11 -

Natural behavior of ant Ant Algorithms – (P.Koumoutsakos – based on notes L. Gamberdella (www.idsia.ch)

Slide 12 -

How to implement in a program Ants: Simple computer agents Move ant: Pick next component in the construction of solution Trace: Pheromone, , a global type of information Memory: MK or TabuK Next move: Use probability to move ant

Slide 13 -

ACO for the Traveling Salesman Problem The TSP is a very important problem in the context of Ant Colony Optimization because it is the problem to which the original AS was first applied, and it has later often been used as a benchmark to test a new idea and algorithmic variants. It is a metaphor problem for the ant colony It is one of the most studied NP-hard problems in the combinatorial optimization it is very easily to explain. So that the algorithm behavior is not obscured by too many technicalities.

Slide 14 -

Ant Colony Optimization (ACO) for TSP Graph (N,E): where N = cities(nodes), E = edges = the tour cost from city i to city j (edge weight) Ant move from one city i to the next j with some transition probability.

Slide 15 -

Each edge is associated a static value based on the edge-cost (r,s) = 1/dr,s. Each edge of the graph is augmented with a trace (r,s) deposited by ants. Initially, 0. Trace is dynamic and it is learned at run-time Each ant tries to produce a complete tour, using the probability depending on (r,s) and (r,s) to choose the next city. Ant Colony Optimization (ACO) for TSP

Slide 16 -

ACO Algorithm for TSP Initialize Place each ant in a randomly chosen city Choose NextCity(For Each Ant) more cities to visit For Each Ant Return to the initial cities Update trace level using the tour cost for each ant Print Best tour yes No Stopping criteria yes No

Slide 17 -

A simple TSP example A E D C B dAB =100;dBC = 60…;dDE =150

Slide 18 -

Iteration 1 A E D C B

Slide 19 -

How to choose next city? A E D C B

Slide 20 -

Iteration 2 A E D C B

Slide 21 -

Iteration 3 A E D C B

Slide 22 -

Iteration 4 A E D C B

Slide 23 -

Iteration 5 A E D C B

Slide 24 -

Path and Trace Update L1 =300 L2 =450 L3 =260 L4 =280 L5 =420

Slide 25 -

End of First Run All ants die New ants are born Save Best Tour (Sequence and length)

Slide 26 -

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 -

Stopping Criteria Stagnation Max Iterations

Slide 28 -

ACO : Ant Colony Optimization for TSP

Slide 29 -

• Algorithm found best solutions on small problems (75 city) • On larger problems converged to good solutions – but not the best • On “static” problems like TSP hard to beat specialist algorithms • Ants are “dynamic” optimizers – should we even expect good performance on static problems • Coupling ant with local optimizers gave world class results…. Performance

Slide 30 -

Parameters of ACO Taken from Dorigo [1] Comparison among three strategies, averages over 10 trials. Other parameters: Q, constant for trace updates, and m, the number of ants

Slide 31 -

Pheromone trail and heuristic function: are they useful? Comparison between ACS standard, ACS with no heuristic (i.e., we set B=0), and ACS in which ants neither sense nor deposit pheromone. Problem: Oliver30. Averaged over 30 trials, 10,000/m iterations per trial.

Slide 32 -

General ACO A stochastic construction procedure Probabilistically build a solution Iteratively adding solution components to partial solutions - Heuristic information - Trace/Pheromone trail Reinforcement Learning reminiscence Modify the problem representation at each iteration

Slide 33 -

General ACO Ants work concurrently and independently Collective interaction via indirect communication leads to good solutions

Slide 34 -

Some inherent advantages Positive Feedback accounts for rapid discovery of good solutions Distributed computation avoids premature convergence The greedy heuristic helps find acceptable solution in the early solution in the early stages of the search process. The collective interaction of a population of agents.

Slide 35 -

Disadvantages in Ant Systems Slower convergence than other Heuristics Performed poorly for TSP problems larger than 75 cities. No centralized processor to guide the AS towards good solutions

Slide 36 -

Applications Traveling Salesman Problem Quadratic Assignment Problem Network Model Problem Vehicle routing

Slide 37 -

Conclusion ACO is a relatively new metaheuristic approach for solving hard combinatorial optimization problems. Artificial ants implement a randomized construction heuristic which makes probabilistic decisions. The cumulated search experience is taken into account by the adaptation of the pheromone trail. ACO shows great performance with the “ill-structured” problems like network routing. In ACO local search is important to obtain good results.

Slide 38 -

References Dorigo M. and G. Di Caro (1999). The Ant Colony Optimization Meta-Heuristic. In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, 11-32. M. Dorigo and L. M. Gambardella. Ant colonies for the traveling salesman problem. BioSystems, 43:73–81, 1997. M. Dorigo and L. M. Gambardella. Ant Colony System: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53–66, 1997. G. Di Caro and M. Dorigo. Mobile agents for adaptive routing. In H. El-Rewini, editor, Proceedings of the 31st International Conference on System Sciences (HICSS-31), pages 74–83. IEEE Computer Society Press, Los Alamitos, CA, 1998. M. Dorigo, V. Maniezzo, and A. Colorni. The Ant System: An autocatalytic optimizing process. Technical Report 91-016 Revised, Dipartimento di Elettronica,Politecnico di Milano, Italy, 1991. L. M. Gambardella, ` E. D. Taillard, and G. Agazzi. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 63–76. McGraw Hill, London, UK, 1999. L. M. Gambardella, ` E. D. Taillard, and M. Dorigo. Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society,50(2):167–176, 1999. V. Maniezzo and A. Colorni. The Ant System applied to the quadratic assignment problem. IEEE Transactions on Data and Knowledge Engineering, 11(5):769–778, 1999. Gambardella L. M., E. Taillard and M. Dorigo (1999). Ant Colonies for the Quadratic Assignment Problem. Journal of the Operational Research Society, 50:167-176.

Frequently Asked Questions

> About SlidesFinder?

Slidesfinder is a website that allows users to upload and share their PowerPoint presentations online. It provides a platform for individuals and businesses to share their ideas and knowledge through presentations, and for others to view and download these presentations for educational or professional purposes.
Slidesfinder offers a wide range of presentation topics and categories, including business, education, science, technology, health, and more. Users can also search for presentations using keywords, tags, or by category. The website provides tools to create professional presentations with rich media, animations, and graphics.

One of the key features of Slidesfinder is its user-friendly interface, which allows users to easily upload, view, and share presentations. Users can also embed their presentations in their websites or blogs using the website's embed code feature.
Slidesfinder also offers premium services, such as the ability to create private presentations and to download presentations in high-quality formats. However, the basic features of Slidesfinder are free to use, making it accessible to anyone who wants to share their ideas and knowledge through presentations.

> How do I register with SlidesFinder?

Go to registration page (you can see signup link on top of website page) https://www.slidesfinder.com/signup . If you have facebook/gmail account them just click on SIGN IN WITH FACEBOOK OR SIGN IN WITH GOOGLE button, by this you will be a registered member of slidesfinder without filling any form, required detail automatically will be fatch from your account. If you do not a Facebook account, then click on "Signup". Fill all required fields and you will be a registered member of slidesfinder.

> Is slidesfinder account confirmation is mandatory?

Yes it is mandetory to active your account to login.

> Do I need to signup/login on SlidesFinder before uploading a PowerPoint presentation?

Yes, you need to login with your account before uploading presentation. Your username will be displayed on your uploaded presentation. Your registered email id is needed for sending your stats of uploaded presentation.

Slidesfinder is a sharing website for PowerPoint presentations search and share. Find your interest in the form of powerpoint presentations on slidesfinder and save your valuable time . On Slidesfinder you get presentations from our huge library of professional ppt presentations. We believe in making your search INFORMATIVE and FUN. Find your best ppt presentation from a pool of PowerPoint presentations stacked under important industry categories like business & management, heath & Wellness,eduction & training etc. We provide unique informative PowerPoint presentation for marketers, presenters and educationists. These professional PowerPoint presentations are uploaded by professionals from across numerous industry segments.These ppt presentations are available for FREE download.

Not just finding your interest, but facilitate you broadcast your interest. We have created this platform for easy sharing of PowerPoint presentations, ensuring that these presentations get maximum exposure. Create your slidesfinder account and upload PowerPoint presentations for free, share on social media platforms and BUILD YOUR CROWD WITH PRESENTATION !!

The Great Buddha says, "Share your knowledge.It’s a way to achieve immortality"! So, start sharing knowledge and we are here to make that immortal !!

Re-productivity of content are not allowed. Without prior written permission from author, commercial use of any content is illegal.