Abstract:

This paper will present an overview of ant

algorithms that is algorithms for colony optimization that took insight which

was observed from ant colonies .We are going to discuss about the findings on

real ants and Ant Colony Optimization (ACO) algorithm is applied to wide range

of problems like Travelling Salesman , Job-Shop Scheduling ,Vehicle Routing.

Introduction:

Ant Colony Optimization is a probabilistic technique which is used for

searching optimal path in the graph based on behaviour of ants seeking a path

between their colony and source of food. It is a Meta-heuristic optimization.

It was first proposed by Marco Dorigo in 1992 as a multi-agent approach to

difficult combinatorial optimization problems such as Travelling salesman

problem (TSP), Quadratic assignment problem (QAP).

The ACO metaheuristic consists of group of

artificial ants with the characteristics to search good solutions to discrete

optimization problem. An Ant algorithm was inspired by the observation of real

ant colonies, Ants are social insects (i.e.) insects that lives in colonies and

whose behavior is directed more to the survival of the colony as a whole than

to that of a single individual component of the colony. An important and

interesting behavior of ant colonies is that their behavior and in particular,

how ants can find the shortest paths between food sources and their nest.

While walking from food sources to the

nest and vice versa, ants deposit on the ground a substance called pheromone,

forming in this way a pheromone trail. Ants can smell these this chemical and

when choosing their way tend to choose, in probability paths marked by them and

allows them to travel from food source to their colonies. Other ants from the

colony follow their nestmates to follow their paths to the food source. This is

how shortest path is emerged for their food hunting.

The

?rst ants to arrive at the food source are those that took the two shortest

branches, so that, when these ants start their return trip, more pheromone is

present on the short branch than on the long branch, stimulating successive

ants to choose the short branch.

Ant

Optimization Algorithms:

Ant Colony Optimization Algorithm:

1 procedure ACO Meta heuristic()

2 while (termination criterion not

satisfied)

3 schedule activities

4 ants generation and activity();

5 pheromone evaporation();

6 daemon actions(); foptionalg

7 end schedule activities

8

end while

9 end procedure

10 procedure ants generation and

activity()

11 while (available resources)

12 schedule the creation of a new ant();

13 new active ant();

14 end while

15 end procedure

16 procedure new active ant() fant

lifecycleg

17 initialize ant();

18 M = update ant memory();

19 while (current state 6= target state)

20 A = read local ant-routing table();

21 P = compute transition probabilities(A;

M; problem constraints);

22 next state = apply ant decision

policy(P; problem constraints);

23 move to next state(next state);

24 if (online step-by-step pheromone

update)

25 deposit pheromone on the visited arc();

26 update ant-routing table();

27 end if

28 M = update internal state();

29 end while

30 if (online delayed pheromone update)

31 evaluate solution();

32 deposit pheromone on all visited

arcs();

33

update ant-routing table();

34 end if

35 die();

36 end procedure

Ant

System(AS):

First ACO

algorithm to be proposed (1992) Pheromone values are updated by all the ants

that have completed the tour.

?ij ?

(1 ? ?) · ?ij + Pm k=1 ?? k ij

where ? is the evaporation rate m is the

number of ants ?? k ij is pheromone quantity laid on edge (i, j) by the k th

ant ?? k i,j = ( 1/Lk if ant k travels on edge i, j 0 otherwise where Lk is the

tour length of the k th ant.

Ant System Algorithm:

1: for each colony do

2:

for each ant do

3: generate route

4: evaluate route

5:

evaporate pheromone in trails

6:

deposit pheromone on trails

7: end for

8: end for

Ant Colony System(ACS):

First major

improvement over Ant System Differences with Ant System:

1 Decision

Rule – Pseudorandom proportional rule

2 Local

Pheromone Update

3 Best only

offline Pheromone Update

Ants in ACS

use the pseudorandom proportional rule Probability for an ant to move from city

i to city j depends on a random variable q uniformly distributed over 0, 1,

and a parameter q0. If q ? q0, then, among the feasible components, the

component that maximizes the product ?il? ? il is chosen, otherwise the same

equation as in Ant System is used. This rule favours exploitation of pheromone

information

Diversifying

component against exploitation: local pheromone update. The local pheromone

update is performed by all ants after each step. Each ant applies it only to

the last edge traversed: ?ij = (1 ? ?) · ?ij + ? · ?0 where ? ? (0, 1 is the

pheromone decay coefficient ?0 is the initial value of the pheromone

Best only

offline pheromone update after construction Offline pheromone update equation

?ij ? (1 ? ?) · ?ij + ? · ?? best ij where ? best ij = ( 1/Lbest if best ant k

travels on edge i, j 0 otherwise Lbest can be set to the length of the best

tour found in the current iteration or the best solution found since the start

of the algorithm.

Ant Colony System Algorithm:

1:

for each colony do

2:

for each ant do

3:

generate route

4:

evaluate route

5: evaporate pheromone in all trails (? rate)

6:

deposit pheromone on all trails

7:

end for

8: evaporate pheromone in best global route (?2 rate)

9:

deposit pheromone on best global route

10:

end for

Max-Min Ant System (MMAS):

Developed

by St¨utzle and Hoos (1996), as another variation for the TSP, the MMAS

algorithm shows di?erences in the steps of pheromone deposition and

evaporation, that occur only after the i-th ant for each colony stablish its

trail.

Differences

with Ant System: 1 Best only offline Pheromone Update 2 Min and Max values of

the pheromone are explicitly limited ?ij is constrained between ?min and ?max

(explicitly set by algorithm designer). After pheromone update, ?ij is set to

?max if ?ij > ?max and to ?min if ?ij < ?min
Max-Min Ant System Algoritm:
1: for each colony do
2: for each ant do
3: generate route
4: evaluate route
5: end for
6: verify for global or local best
7:
evaporate pheromone in all trails
8: deposit pheromone on
best global route
9: end for
Application
of ACO
u Traveling Salesman
u Job-Shop Scheduling
u Vehicle Routing
u Graph Coloring
Travelling
Salesman Problem:
The
Travelling Salesman Problem describes a salesman who must travel between N
cities. The order in which he does so is something he does not care about, as
long as he visits each once during his trip, and finishes where he was at
first. Each city is connected to other close by cities, or nodes, by airplanes, or by road or railway. Each of those links between the cities has
one or more weights (or the cost) attached. The cost describes how
"difficult" it is to traverse this edge on the graph, and may be
given, for example, by the cost of an airplane ticket or train ticket, or
perhaps by the length of the edge, or time required to complete the traversal.
The salesman wants to keep both the travel costs, as well as the distance he travels as low as possible.
The
Traveling Salesman Problem is typical of a large class of "hard"
optimization problems that have intrigued mathematicians and computer
scientists for years. Most important, it has applications in science and
engineering. For example, in the manufacture of a circuit board, it is
important to determine the best order in which a laser will drill thousands of
holes. An efficient solution to this problem reduces production costs for the
manufacturer.
Difficultychange | change source
The
travelling salesman problem is regarded as difficult to solve. If there is a
way to break this problem into smaller component problems, the components will
be at least as complex as the original one. This is what computer scientists call NP-hard problems.
Many people
have studied this problem. The easiest (and most expensive solution) is to
simply try all possibilities. The problem with this is that for N cities you
have (N-1) factorial possibilities.
Job-Shop Scheduling Problem:
In job-shop scheduling a finite set of n
jobs is taken and each job consists of a chain of operations. It also consists
of a finite set of m machines, each machine can handle at most one operation at
a time. Each operation needs to be processed during an uninterrupted period of
a given length on a given machine. Purpose is to find a schedule, that is, an
allocation of the operations to time intervals to machines, that has minimal
length.
The job-shop scheduling problem is the
problem of assigning operations to machines and time intervals so that the
maximum of the completion times of all operations is minimized and no two jobs
are processed at the same time on the same machine. The basic algorithm they
applied was exactly the same as Ant System(AS). Job shop
scheduling or the job-shop problem (JSP) is an optimization problem in computer science and operations research in
which ideal jobs are assigned to resources at particular times. The most basic
version is as follows: We are
given n jobs J1, J2, ..., Jn of varying
processing times, which need to be scheduled on m machines with
varying processing power, while trying to minimize the makespan.
The makespan is the total length of the schedule (that is, when all the jobs
have finished processing). In most practical settings, the problem is presented
as an online problem (dynamic
scheduling), that is, the decision of scheduling a job can only be made online,
when the job is presented to the algorithm.
This problem is one of the best known
combinatorial optimization problems, and was the first problem for which competitive analysis was
presented. Applying machine learning to
job scheduling is an emerging approach. In
this approach, artificial intelligence determines
optimizations without the need for human programmers to create an algorithm for
them or to fully understand the complex causation that drives them.
The name originally came from the
scheduling of jobs in a job shop,
but the theme has wide applications beyond that type of instance
Vehicle routing Problem
The Vehicle
Routing Problem (VRP) dates back to the end of the fifties of the last century
when Dantzig and Ramser set the mathematical programming formulation and
algorithmic approach to solve the problem of delivering gasoline to service
stations. Since then the interest in VRP evolved from a small group of
mathematicians to the broad range of researchers and practitioners, from
different disciplines, involved in this field today. The VRP definition states
that m vehicles initially located at a depot are to deliver discrete quantities
of goods to n customers. Determining the optimal route used by a group of vehicles
when serving a group of users represents a VRP problem. The objective is to
minimize the overall transportation cost. The solution of the classical VRP
problem is a set of routes which all begin and end in the depot, and which
satisfies the constraint that all the customers are served only once. The
transportation cost can be improved by reducing the total travelled distance
and by reducing the number of the required vehicles. The majority of the real
world problems are often much more complex than the classical VRP. Therefore in
practice, the classical VRP problem is augmented by constraints, such as
vehicle capacity or time interval in which each customer has to be served,
revealing the Capacitated Vehicle Routing Problem (CVRP) and the Vehicle Routing
Problem with Time Windows (VRPTW), respectively. In the last fifty years many
real-world problems have required extended formulation that resulted in the
multiple depot VRP, periodic VRP, split delivery VRP, stochastic VRP, VRP with
backhauls, VRP with pickup and delivering and many others.
The vehicle
routing problem lies at the heart of distribution management. It is faced each
day by thousands of companies and organizations engaged in the delivery and
collection of goods or people. Because conditions vary from one setting to the
next, the objectives and constraints encountered in practice are highly
variable. Most algorithmic research and software development in this area focus
on a limited number of prototype problems. By building enough flexibility in
optimization systems one can adapt these to various practical contexts.
Conclusion:
In this article we have discussed about the ant colony optimization (ACO)
metaheuristic and we have given an overview of ACO algorithms. The ant colony algorithms
are explained and they are implemented in different problems like travelling
salesman, job-shop scheduling and vehicle routing.AS is very common in the
practical usage of these heuristics, ACO algorithms often end up at some
distance from their inspiring natural metaphor. ACO algorithms so enriched are
very competitive and in some applications they have reached world-class
performance. For example, on structured quadratic assignment problems AS-QAP,
HAS-QAP, and MMAS-QAP are currently the best available heuristics. In
conclusion, we hope this paper has achieved its goal by implementing the
algorithms like ant algorithm, ant system algorithm, min-max ant system
algorithm in the different problem like travelling salesman, job-shop
scheduling, vehicle routing.