Ant Colony Optimization

Ant Colony Optimization

ZHOU Qiang

B0907119

Email:zhouqiang2000@gmail.com

Presentation Outline

⏹ Background

⏹ The concept of ant algorithms

⏹ Application of Ant Colony Algorithms

⏹ Conclusion

the first picture describes the activities of birds

the second picture describes the activities of fish

the third picture describes the activities of ants

We can see from the above biological activities is not difficult to find, they have some of the same nature

We can Summarized as follows

Inherent features

⏹ Inherent parallelism

⏹ Stochastic nature

⏹ Adaptivity

⏹ Use of positive feedback

Swarm intelligence Background

Swarm intelligence (SI) is a type of artificial intelligence based on the collective behavior of decentralized, self-organized systems. Bionics algorithms are attentioned gradually in recent years, especially for non-decisive problem solving ,such as Traveling Salesman Problem(TSP), Ant foraging behavior of the numerical simulation can be widely used in non-decisive problem and will find the optimal solution to some problems.

Ant colony algorithm mimics the behavior of insect colonies completing their activities

How to implement in a program

He activities of real ant extract and computer activities to match the behavior

In the real world Abstract into

⏹ 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

Ant colony algorithm

Ant colony looking for food < == > Solving a problem

N Individual ants < == > N Solutions

Each time the colony goes to < == > Population of N solutions

look for food and returns to the nest

Ants from the real activities of an algorithm to extract the structure of Figure

Ant System (Ant Cycle) Dorigo 1991

As a result of the powerful ant colony algorithm, it will be applied to all areas of its

Applications

⏹ Traveling Salesman Problem

⏹ Quadratic Assignment Problem

⏹ Network Model Problem

⏹ Vehicle routing

Conclusions

⏹ ACO is a recently proposed metaheuristic approach for solving hard combinatorial optimization problems.

⏹ Artificial ants implement a randomized construction heuristic which makes probabilistic decisions.

⏹ The a 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 extremely important to obtain good results.

Thank you

Ants (blind) navigate from nest to food source,Shortest path is discovered via pheromone trails ,each ant moves at random,pheromone is deposited on path,ants detect lead ant’s path, inclined to follow more pheromone on path increases probability of path being followed,Virtual “trail” accumulated on path segments, Path selected at random,based on amount of “trail” present on possible paths from starting node,higher probability for paths with more “trail”,Ant reaches next node, selects next path ,Finished “tour” is a solution,Ant Colony Algorithms are typically use to solve minimum cost problems. The AlgorithmThe ants evaluate the cost of the paths they have traversed. An evaporation rule will be tied with the pheromones, which will reduce the chance for poor quality solutions.

algorithm is based on a series of random decisions (by artificial ants)

probability of decisions changes on each iteration

Ant Algorithms Inspired by observation of real ants

Ant Colony Optimization (ACO)Inspiration from ant colonies’ foraging behavior (actions of the colony finding food)

本文来源：https://www.2haoxitong.net/k/doc/3262ae94daef5ef7ba0d3c9c.html