CP5602: A Comprehensive Analysis of Ant Colony Optimization Algorithm

This report provides a comprehensive analysis of the Ant Colony Optimization (ACO) algorithm, a probabilistic technique used for solving computational problems and finding optimal paths in graphs. It discusses the inspiration behind ACO, drawing from the pheromone-based communication of biological ants. The report explores ambient networks of intelligent objects, artificial pheromone systems, and the convergence of ACO. It further details the selection of edges, pheromone updates, and applications of ACO in various combinatorial optimization problems, including scheduling and vehicle routing. The challenges faced by ACO and related methods are also discussed. Desklib offers this report along with a wealth of study resources including past papers and solved assignments.

Running head: ADVANCED ALGORITHM ANALYSIS
Advanced Algorithm Analysis
[Name of the Student]
[Name of the University]
[Author note]

1ADVANCED ALGORITHM ANALYSIS
Table of Contents
Introduction:...............................................................................................................................2
Discussion:.................................................................................................................................3
Ambient Networks of Intelligent objects:..................................................................................3
Artificial Pheromone System:................................................................................................4
Convergence of the ACO:......................................................................................................5
Selection of Edge:..................................................................................................................5
Pheromone update:.................................................................................................................6
Application of ACO:..............................................................................................................6
Problems faced by ACO.............................................................................................................7
Scheduling problems faced by ACO......................................................................................7
Vehicles routing problems:....................................................................................................8
Assignment problem..............................................................................................................9
Set problem............................................................................................................................9
Optimization of the Antennas and synthesis:.........................................................................9
Methods related to ACO:...........................................................................................................9
Conclusion:..............................................................................................................................12

2ADVANCED ALGORITHM ANALYSIS
Introduction:
Operation research and Computer science generally consists of the Ant Colony
Optimization or the ACO, which is generally considered to be a probabilistic technique that is
used in order to solve the problems related to computing. This this it can also be used for the
purpose of finding the good paths by making use of the graphs. In this the artificial ants is
multi-agent method that is generally inspired by the behaviours that the real ants are having
(Mohan & Baskaran, 2012). Communication based upon the usage of the pheromone by the
biological ants is often considered to be a paradigm which is used predominantly. The
artificial ants and the local search engines are combined so as to have a better method for
different kind of optimization tasks that also involves the usage of some graphs as well.
Including of the burgeoning activity in this particular field has been associated with
leading towards the conference which are entirely dedicated to the artificial ants as well as to
other commercial applications by companies who are specialized in this field like the
AntOptima. Ant Colony Optimization is also sometimes considered to be a class of
optimization algorithm that has been modelled according to the actions conducted by the ant
colony. The artificial Ants are used for the purpose of locating the optimal solutions. This is
done by moving throughout the entire parameter space by representing the solutions that are
possible (Nishant et al., 2014). Like the real ants, the simulated ants are also associated with
recording the positions and the quality of the solutions. This is done in order to make sure
that the simulation iterations taking place later would help in the process of obtaining better
solutions. Another variety of this approach includes the bees’ algorithm which operates in a
similar fashion like that of another social insect known as the honey bee.

3ADVANCED ALGORITHM ANALYSIS
Discussion:
The Ant Colony Optimization is an algorithm that is generally considered to be a
member of the swarm intelligence method which consists of some metaheuristic
optimizations. This concept was initially proposed by Macro Dorigo in the year of 1992 and
was associated with looking out for a path in the graph that is most optimal. This was done by
depending upon the behaviour that the ants are having while looking out for a path that exists
between the colony and the food source. This idea was further diversified so as to solve
numerous numerical problems which initially lead to various type of problems (Mishra &
Jaiswal, 2012). It can be stated that ACO is a model-based search which is also associated
with sharing similarities with the estimation of the distribution algorithms.
Ambient Networks of Intelligent objects:
There exists the need of new concepts as the term intelligence is no longer centralized
and is implemented across various type of objects, the Anthropocentric concepts is associated
with leading towards an increased rate of IT system production of where it is seen that the
control units, data processing and the forces responsible for calculating are present in
centralized form. All this units which are centralized are associated with increasing their
performance rate and this in turn can be compared with the capabilities that a human brain is
having (Tawfeek et al., 2013). The ultimate vision of the computers is the model of the brain.
the ambient network of intelligent objects along with the new creation of new Information
System that are of diffused nature and are dependent upon the nanotechnology and this is
profoundly going to change the entire concept. Small devices that are generally compared
with the insects are not associated with disposing high intelligence of their own and for this
reason it can be stated that their intelligence is limited. For example it is not possible to
combine the calculator of high performance with the power need to solve any type of
mathematical related problems present in a biochip which is implemented inside a human

4ADVANCED ALGORITHM ANALYSIS
body or are integrated with the intelligent tag that re-designed in order to track the
commercial articles. But whenever the objects gets connected with each other, then they are
associated with disposing a form of intelligence (Jiang, Maskell, & Patra, 2013). It is possible
to compare this intelligence with the colony of ants or bees so as to make those intelligence
become superior in case of certain problems and this much superior than the reasoning
conducted by the centralized system like a brain.
There exists several examples of how the minuscule organisms of the world follow
simple rules and form the collective intelligence in the macroscopic level. This is the model
which is dependent upon the co-operation of the independent units by making use of simple
as well as unpredictable behaviours. They are associated with moving all around so as to
carry out certain tasks and they have a very little information for doing this (Ting & Chen,
2013). They are having the capability of getting adapted to the changes taking place in the
environment along with having an enormous amount of strength so as to deal with various
complex situations. This type of flexibility is very much beneficial for the mobile networks of
various objects that are being developed in a perpetual way.
Artificial Pheromone System:
Pheromone-based Communication is considered to be the way which is most effective
for creating a good quality communication. This type of communication is used on a wide
basis. The pheromone-based communication is generally implemented by various means that
includes the chemical or physical ways. But despite of this the implementation were not
capable of duplicating all the features of the pheromones that are present.
Convergence of the ACO:
There exists some version of the ACO where it is possible to prove that they are
convergent in nature.in the year of 2000 the first evidence of convergence ant colony

5ADVANCED ALGORITHM ANALYSIS
algorithm was provided which was followed by the graph-based ant system algorithm and the
algorithms for the ACS and the NMAS. Estimations regarding the theoretical speed of
convergence I difficult like most of the Metaheuristics. Zlochin and his colleagues in the year
of 2004 were associated with showing the COA-type algorithm which can be assimilated
with the techniques related to stochastic gradient descent present in the cross-entropy and
also made the estimations regarding the distributed algorithms, the performance analysis of
the continuous ant colony algorithm depending upon the various parameters is associated
with suggesting the sensitivity of convergence on the parameter tuning (Putha, Quadrifoglio,
& Zechman, 2012).
Selection of Edge:
Ant is generally considered to be a simple computational agent of the ant colony
optimization algorithm. This is associated with constructing a solution in an iterative way for
the problems. This type of intermediate solutions are generally considered to be the solution
states. Whenever an iteration is taking place in the algorithm each ant from the x state to the y
state which is correspondent with the other intermediate solutions (Lopez-Ibanez & Stutzle,
2012). For this reason each of the ant or k computes a set or Ak(x) of the feasible expansion
to a current state present in each of the iteration and moves to one of the these. For the ant K
the probability Pkxy of moving from the x state to the y state is entirely dependent upon the
combination of two of the values that is the attractiveness ῃxy of the move as they are
computed by some of the heuristic indicating the “a prior” desirability of that particular move
and the trail level or the Txy of the move which indicated how proficient it was in the past so
as make a particular move.
The trail level is associated with representing a later indication of the moves that are
desiered. Updating of the trail is usually done whenever all the ants have completed their

6ADVANCED ALGORITHM ANALYSIS
solutions, by increasing the trail levels or decreasing the trail levels in correspondence to their
move which were part of the solution that were good or bad (Mahi, Baykan, & Kodaz, 2015).
In general the movement of the kth ant from x state to y states is having the
probability provided below:
Pheromone update:
The equation that is used for updating the trail is shown below and this can be
determined once all the ants have completed their solution:
In this the Txy is considered to be the amount of pheromone which has been deposited
for the state transmission xy, ƿ is the pheromone evaporation coefficient.
Application of ACO:
The ant colony optimization algorithm is used so as to apply many problems related to
combinatorial optimization which ranges from the quadratic assignment to protein folding or
routing vehicles (DeléVacq et al., 2013). Along with this there exists an advantage over the
simulated annealing as well as the genetic algorithm approaches regarding similar problems
whenever there is a dynamic change in the graph (Lin et al., 2012). It is possible to run the
ACO continuously and is also having the capability of getting adopted to the real time
environment. This is very important in the network routing and the transport systems as well
(Tabakhi, Moradi, & Akhlaghian, 2014).

7ADVANCED ALGORITHM ANALYSIS
At the initial stage the ACO was applied in the domain of NP-hard combinatorial
optimization problems. It is surprizing that the major section of the ACO research is still
being conducted in this area. Besides this another major application which is included in the
history of ACO is routing in telecommunication networks. One of the successful example of
ACO algorithm in this domain includes the AntNet. The ACO algorithm was firstly used with
the name ant system which was mainly associated with solving the various problems that
were faced by the travelling salesman (Cecilia et al., 2013). The main goal of using this
system was to locate the path that is shortest for completed the round-trip which would
initially result in linking of numerous cities. The over-all form of this algorithm is simple and
besides this it is seen that they are dependent upon a set of ants where the individual ants are
capable of making one round trip along the cities. By following some rules the ant are
associated with moving from a particular city to another city and the rules includes the
following:
 The ant must visit each city exactly once.
 There is less chance of choosing a distinct city
 The edge would be chosen depending upon the intensity of the pheromone trail laid
out at the edges of two cities.
 After completion of the journey the ants are associated with depositing more
phenomenon on all the edges it has gone across in case if the journey is to short.
 Once the iteration is completed the trail of the pheromones evaporates.
Problems faced by ACO
Scheduling problems faced by ACO
Some of the scheduling problems faced by the ACO have been listed below:
 Job-Shop scheduling problem

8ADVANCED ALGORITHM ANALYSIS
 Open-Shop scheduling problem
 Permutation flow shop problem (PFSP)
 Resource-constrained project scheduling problem (RCPSP)
 Single machine total weighted tardiness problem (SMTWTP) (Chen & Zhang, 2013)
 Single machine total tardiness problem (SMTTP)
 Multistage flowshop scheduling problem (MFSP) with sequence dependent
setup/changeover times
 Group-shop scheduling problem (GSP)
 Single-machine total tardiness problem with sequence dependent setup times
(SMTTPDST)
Vehicles routing problems:
Some of the vehicle routing problems faced by ACO are listed below:
 Period vehicle routing problem (PVRP)
 Multi-depot vehicle routing problem (MDVRP)
 Vehicle routing problem with time windows and multiple service workers
(VRPTWMS)
 Vehicle routing problem with pick-up and delivery (VRPPD)Stochastic vehicle
routing problem (SVRP)
 Capacitated vehicle routing problem (CVRP)
 Split delivery vehicle routing problem (SDVRP)
 Time dependent vehicle routing problem with time windows (TDVRPTW)

9ADVANCED ALGORITHM ANALYSIS
 Vehicle routing problem with time windows (VRPTW)
Assignment problem
Some of the assignment problems faced by the ACO are listed below:
 Frequency assignment problem (FAP)
 Quadratic assignment problem (QAP)
 Redundancy allocation problem (RAP)
 Generalized assignment problem (GAP)
Set problem
Some of the set problems faced by ACO are listed below:
 Maximum independent set problem (MIS) Partition problem (SPP)
 Multiple knapsack problem (MKP)
 Set cover problem (SCP)
 Arc-weighted l-cardinality tree problem (AWlCTP)
 Weight constrained graph tree partition problem (WCGTPP)
Optimization of the Antennas and synthesis:
The different form of antennas are optimized by making use of the ACO or the ant colony
optimization. For example the antennas based upon the RFID tags makes use of the ACO.
Methods related to ACO:
 Genetic algorithms (GA): This is associated with maintenance of a pool of solutions
instead of just one solution. This process which involves finding of the superior
solution is generally a mimic of the evolution with the solutions that are being

10ADVANCED ALGORITHM ANALYSIS
combined or mutated one so as to alter the pool of solutions along with discarding the
inferior quality solutions (Kabir, Shahjahan, & Murase, 2012).
 An estimation of distribution algorithm (EDA): this is generally considered to be
an evolutionary algorithm that is associated with substituting the traditional
reproduction operators by making use of the operators that are guided by the models.
This type of models are learned from the population and this is generally done by
employment of the machine learning techniques (Liu, Yi, & Ni, 2013). This usages
initially results in representation of the probabilistic graphical models, which can be
used so as to obtain new solutions from guided-crossover.
 Simulated annealing (SA): This is generally considered to be a related global
optimization technique which is associated with traversing the space of search. This is
generally done by generation of the neighbouring solutions. The behaviour which is
superior is always excepted whereas the acceptability of the inferior neighbour is done
probabilistically and is dependent on the difference existing in the quality and the
temperature (Jovanovic & Tuba, 2013). Modification of the temperature parameter is
done in order to obtain the progress of the algorithm needed which would be helping
in altering the nature of the search.
 Reactive search optimization: This optimization technique is associated with
focusing upon the combination of machine learning with the optimization. This is
generally done by addition of an internal feedback loop. Addition is mainly done so as
to obtain a free parameter of an algorithm by self-tuning (Mavrovouniotis & Yang,
2013).
 Tabu search (TS): This is the type of search that is considered to have similar
characteristics like that of the simulated annealing. In this the traversing of the

11ADVANCED ALGORITHM ANALYSIS
solution space is done by testing of the mutations that the individual solutions are
having. Whereas the simulated annealing is associated with generating only a single
mutated solution, and the tabu search is associated with generating numerous
solutions of mutated nature. This initially tends towards the solution which is of
lowest fitness amongst those solutions which has already been generated. For the
purpose of preventing the cycling and for encouraging a greater movement through
the solution space there is a need of maintaining a tabu list which consists of partial or
a complete solutions (Ho et al., 2012). This is initially updated when the solution gets
traversed through the solution space.
 Artificial immune system (AIS): This are the algorithms which are generally
modelled upon the vertebrate immune systems.
 Particle swarm optimization (PSO): This is generally considered to be a swarm
intelligence method.
 Intelligent water drops (IWD): This is a swarm-based optimization algorithm that is
dependent upon the natural water drops which are flowing in the rivers.
 Gravitational search algorithm (GSA): This is also considered to be another swarm
intelligence method (Marzband et al., 2016).
 Ant colony clustering method (ACCM): This is a method which is responsible for
making use of clustering approach, which is associated with extending the ACO.
 Stochastic diffusion search (SDS): this is an agent-dependent probabilistic global
search and optimization technique which is suitable for tackling the various
difficulties, where it is seen that the objectives function are having the probability of
getting decomposed and transform into a multiple independent partial-functions.