ACO

is a relatively novel meta-heuristic based technique which has been

successfully applied for combinatorial optimization problems. ACO algorithm

model is based upon real ant behavior in colonies in establishing the shortest

path between food sources and nests. Ants communicate with one another through

pheromones – a chemical. The ants discharge pheromone on their way while

walking from their nest to food and then follow it back to the nest. The ants

move conferring to the amount of pheromones discharges, it is more likely that

the ants will be following the denser the pheromone trail. So a shorter path

has a higher amount of pheromone in probability, hence resultantly ants will

tend to pick out a shorter path. Through this apparatus, ants will ultimately end

up with a shortest path. Artificial ants imitate the behavior of real ants, but

are capable of solving more complex problems.

Various

combinatorial optimization problems such as Traveling Salesman Problem (TSP),

Job-shop Scheduling Problem (JSP), Vehicle Routing Problem (VRP), Quadratic

Assignment Problem (QAP), etc has been effectively solved through ACO. Although

it has an influential capacity to discover solutions to combinational

optimization problems, it faces stagnation and premature convergence; moreover,

the convergence speed of ACO is very slow. These problems are to be more noticeable

when the problem size increases. Therefore, several allowances and enhanced

versions of the original ACO algorithm were presented over the past years.

Various adaptations: dynamic control of solution construction 4, mergence of

local search 3, 13, a strategy is to partition artificial ants into two

groups: scout ants and common ants 11 and new pheromone updating strategies

1, 3, 14, using candidate lists strategies 2, 16, 17 are studied to improve

the quality of the final solution and lead to speedup of the algorithm. All

these studies have resulted in the upgrading of the ACO to some extent, but

they have little obvious effect on increasing the convergence speed and

obtaining the global optimal solution. In the proposed system, the main modifications

introduced by ACO is firstly, to evade search stagnation and ACO is more functional

if ants are initially placed on different cities. Second, algorithm’s

parameters are adjusted in information entropy. Additionally, the best

performing ACO algorithms for the TSP improve the solutions generated by the

ants using local search algorithms.