Introduction to Ant Colony Algorithm
Ant Clony Optimization (ACO) is a kind of swarm intelligence algorithm, which is a group of unintelligent or slightly intelligent individuals (Agent) through mutual collaboration to show intelligent behavior, thus providing a new possibility for solving complex problems. Ant colony algorithm was firstly proposed by Italian scholars Colorni A., Dorigo M. and so on in 1991. After more than 20 years of development, the ACO algorithm has made great progress in theoretical as well as applied research.
Ant colony algorithm is a bionic algorithm that is inspired by the behavior of ants foraging for food in nature. In nature, during ants' foraging process, the colony is always able to follow to find an optimal path from the nest and the food source. The following figure shows such a foraging process.
In figure (a), there is a colony of ants, suppose A is the nest and E is the food source (and vice versa). The group of ants will travel along a straight path between the nest and the food source. If an obstacle suddenly appears between A and E (Fig. (b)), the ants at point B (or D) will have to make a decision whether to travel to the left or to the right. Since at first there are no ants left on the road in front of thePheromones The probability of an ant traveling in two directions is equal. But when an ant walks by, it will release pheromone on its way and this pheromone will be emitted at a certain rate. Pheromone is one of the tools of communication between ants. The ants behind it use the concentration of pheromone on its path to make a decision whether to go left or right. Obviously, the pheromone will be more and more concentrated on the path along the short side (Figure (c)), which attracts more and more ants to travel along this path.
TSP Problem Description
Ant colony algorithm was firstly used to solve the TSP problem and showed great superiority because of its distributed characteristics, robustness and easy to be combined with other algorithms, but at the same time there are also shortcomings such as slow convergence speed and easy to fall into the local optimal (local optimal).
The TSP problem (Travel Salesperson Problem or known as the Chinese Postman Problem), is a kind of NP-hard problem, this kind of problem is very difficult to get the optimal solution with general algorithms, so it is usually necessary to solve it with the help of some heuristic algorithms, such as Genetic Algorithm (GA), Ant Colony Algorithm (ACO), Particle Swarm Algorithm (PSO) and so on. PSO) and so on.
The TSP problem (Traveler's Problem) is a problem in which a traveler has to travel n cities, requires that each city be experienced and experienced only once and then returns to the starting city, and requires that the distance traveled be the shortest.
A TSP problem can be expressed as follows: solve the problem of traversing the graph G=(V,E,C) with all the nodes at once and returning to the starting node such that the path cost to connect these nodes is minimized.
Principles of Ant Colony Algorithm
If the number of all ants in the colony is m, and the pheromone between all cities is represented by a matrix pheromone, with the shortest path being the bestLength and the best path being the bestTour, each ant has its own memory, which is used to store the cities that the ant has already visited in a Tabu, which means that the ant will not be able to visit these cities in future searches, and another Allowed table to store the cities that it can still visit, and a Delta to store the cities that it can visit in a loop or iteration, and a Delta to store the cities that it can visit in a loop or iteration. cities; another table of allowed cities (Allowed) to store the cities it can still visit; a matrix (Delta) to store the pheromones it releases to the paths it passes through in a loop (or iteration); and other data, such as some control parameters (α, β, ρ, Q), the total cost of the ant's walk to play the whole game or distance (tourLength), and so on. tourLength), and so on. Assume that the algorithm is run MAX_GEN times in total, and the running time is t.
The ACO algorithm is calculated as follows:
(1) Initialization.
(2) Select the next node for each ant.
(3) Updating the pheromone matrix.
(4) Checking termination conditions
If the maximum number of generations MAX_GEN is reached, the algorithm terminates and goes to step (5); otherwise, re-initialize the Delt matrix of all ants all elements are initialized to 0, the Tabu table is emptied, and all city nodes are added to the Allowed table. Randomly select their starting positions (can also be specified manually). Add the starting node in Tabu, remove that starting node in Allowed, and repeat steps (2), (3),(4).
(5) Output the optimal value
code implementation
# -*- coding: utf-8 -*-
import random
import copy
import time
import sys
import math
import tkinter #//GUI module
import threading
from functools import reduce
# Parameters
'''
ALPHA: information heuristic factor, the larger the value, the greater the possibility that the ants will choose the previously traveled paths
ALPHA:Information Heuristic Factor, the larger the value, the more likely the ants will choose the path they have taken before.
BETA: The larger the value of Beta, the easier it is for the colony to choose a shorter path, and the algorithm will converge faster, but the randomness is not high.
The algorithm convergence speed will be accelerated, but the randomness is not high, and it is easy to get the local relative optimization.
The algorithm will converge faster, but the randomness is not high, and it is easy to get the local relative optimization.''
(ALPHA, BETA, RHO, Q) = (1.0,2.0,0.5,100.0)
# City counts, ant colonies
(city_num, ant_num) = (50,50)
distance_x = [
178,272,176,171,650,499,267,703,408,437,491,74,532,
416,626,42,271,359,163,508,229,576,147,560,35,714,
757,517,64,314,675,690,391,628,87,240,705,699,258,
428,614,36,360,482,666,597,209,201,492,294]
distance_y = [
170,395,198,151,242,556,57,401,305,421,267,105,525,
381,244,330,395,169,141,380,153,442,528,329,232,48,
498,265,343,120,165,50,433,63,491,275,348,222,288,
490,213,524,244,114,104,552,70,425,227,331]
# Urban distances and pheromones
distance_graph = [ [0.0 for col in range(city_num)] for raw in range(city_num)]
pheromone_graph = [ [1.0 for col in range(city_num)] for raw in range(city_num)]
#----------- ants -----------
class Ant(object):
# Initialization
def __init__(self,ID):
= ID # ID
self.__clean_data() # Randomly initialized birth points
# Initial data
def __clean_data(self):
= [] # The path of the current ant
self.total_distance = 0.0 # Total distance of current path
self.move_count = 0 # Number of moves
self.current_city = -1 # Current city of stay
self.open_table_city = [True for i in range(city_num)] # Explore the state of the city
city_index = (0,city_num-1) # Randomized initial point of birth
self.current_city = city_index
(city_index)
self.open_table_city[city_index] = False
self.move_count = 1
# Choose the next city
def __choice_next_city(self):
next_city = -1
select_citys_prob = [0.0 for i in range(city_num)] #Store the probability of going to the next city
total_prob = 0.0
# Get the probability of going to the next city
for i in range(city_num):
if self.open_table_city[i]:
try :
# Calculated probability: proportional to pheromone concentration, inversely proportional to distance
select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) * pow((1.0/distance_graph[self.current_city][i]), BETA)
total_prob += select_citys_prob[i]
except ZeroDivisionError as e:
print ('Ant ID: {ID}, current city: {current}, target city: {target}'.format(ID = , current = self.current_city, target = i))
(1)
# Roulette wheel to choose the city
if total_prob > 0.0:
# Generate a random probability,0.0-total_prob
temp_prob = (0.0, total_prob)
for i in range(city_num):
if self.open_table_city[i]:
# of rounds
temp_prob -= select_citys_prob[i]
if temp_prob < 0.0:
next_city = i
break
# Not generated from probability, sequential selection of an unvisited city
# if next_city == -1:
# for i in range(city_num):
# if self.open_table_city[i]:
# next_city = i
# break
if (next_city == -1):
next_city = (0, city_num - 1)
while ((self.open_table_city[next_city]) == False): # if==False, indicating that it has already been traversed
next_city = (0, city_num - 1)
# Return to next city serial number
return next_city
# Calculate the total distance of the path
def __cal_total_distance(self):
temp_distance = 0.0
for i in range(1, city_num):
start, end = [i], [i-1]
temp_distance += distance_graph[start][end]
# Loop
end = [0]
temp_distance += distance_graph[start][end]
self.total_distance = temp_distance
# Move the action
def __move(self, next_city):
(next_city)
self.open_table_city[next_city] = False
self.total_distance += distance_graph[self.current_city][next_city]
self.current_city = next_city
self.move_count += 1
# Search path
def search_path(self):
# Initialize data
self.__clean_data()
# Search paths until all cities have been traversed.
while self.move_count < city_num:
# Move to the next city
next_city = self.__choice_next_city()
self.__move(next_city)
# Calculate the total length of the path
self.__cal_total_distance()
#----------- TSP Issues -----------
class TSP(object):
def __init__(self, root, width = 800, height = 600, n = city_num):
# Create a canvas
= root
= width
= height
# of cities initialized to city_num
= n
#
= (
root,
width = ,
height = ,
bg = "#EBEBEBEB", # Background white
xscrollincrement = 1,
yscrollincrement = 1
)
(expand = , fill = )
("TSPACO algorithm(n:initialization e:Start searching s:Stop searching q:opt-out program)")
self.__r = 5
self.__lock = () # Thread locks
self.__bindEvents()
()
# Calculate distances between cities
for i in range(city_num):
for j in range(city_num):
temp_distance = pow((distance_x[i] - distance_x[j]), 2) + pow((distance_y[i] - distance_y[j]), 2)
temp_distance = pow(temp_distance, 0.5)
distance_graph[i][j] =float(int(temp_distance + 0.5))
# Key Response Program
def __bindEvents(self):
("q", ) # Exit the program
("n", ) # Initialization
("e", self.search_path) # Start searching
("s", ) # Stop searching
# Change title
def title(self, s):
(s)
# Initialization
def new(self, evt = None):
# Stop the thread
self.__lock.acquire()
self.__running = False
self.__lock.release()
() # Clear the message
= [] # Node coordinates
self.nodes2 = [] # Node objects
# Initialize city nodes
for i in range(len(distance_x)):
# Randomize initial coordinates on the canvas
x = distance_x[i]
y = distance_y[i]
((x, y))
# Generate node ellipse with radius self.__r
node = .create_oval(x - self.__r,
y - self.__r, x + self.__r, y + self.__r,
fill = "#ff0000", # Fill with red
outline = "#000000", # Outline white
tags = "node",
)
self.(node)
# Display coordinates
.create_text(x,y-10, # Use the create_text method to draw text at coordinates (302, 77)
text = '('+str(x)+','+str(y)+')', # Content of drawn text
fill = 'black' # The color of the drawn text is gray
)
# Sequentially connected cities
#(range(city_num))
# Distance and pheromones between initial cities
for i in range(city_num):
for j in range(city_num):
pheromone_graph[i][j] = 1.0
= [Ant(ID) for ID in range(ant_num)] # Initial colony
self.best_ant = Ant(-1) # Initial optimal solution
self.best_ant.total_distance = 1 << 31 # Initial maximum distance
= 1 # Initialize the number of iterations
# Connect the nodes in order
def line(self, order):
# Delete the original line
("line")
def line2(i1, i2):
p1, p2 = [i1], [i2]
.create_line(p1, p2, fill = "#000000", tags = "line")
return i2
# order[-1] is the initial value
reduce(line2, order, order[-1])
# Clear the canvas
def clear(self):
for item in .find_all():
(item)
# Exit the program
def quite(self, evt):
self.__lock.acquire()
self.__running = False
self.__lock.release()
()
print (u"\n program has exited...")
()
# Stop searching
def stop(self, evt):
self.__lock.acquire()
self.__running = False
self.__lock.release()
# Start searching
def search_path(self, evt = None):
# Start a thread
self.__lock.acquire()
self.__running = True
self.__lock.release()
while self.__running:
# Iterate over every ant
for ant in :
# Search for a path
ant.search_path()
# Comparison with current optimal ants
if ant.total_distance < self.best_ant.total_distance:
# Update the optimal solution
self.best_ant = (ant)
# Update pheromones
self.__update_pheromone_gragh()
print (u"Number of iterations:",,u"Total distance of optimal path:",int(self.best_ant.total_distance))
# Connecting the dots
(self.best_ant.path)
# Setting the title
("TSPACO algorithm(n:stochastic initial e:Start searching s:Stop searching q:opt-out program) Number of iterations: %d" % )
# Update the canvas
()
+= 1
# Update pheromones
def __update_pheromone_gragh(self):
# Get the pheromones each ant leaves in its path #
temp_pheromone = [[0.0 for col in range(city_num)] for raw in range(city_num)]
for ant in :
for i in range(1,city_num):
start, end = [i-1], [i]
# Pheromones left between every two neighboring cities on the path, inversely proportional to the total distance of the path
temp_pheromone[start][end] += Q / ant.total_distance
temp_pheromone[end][start] = temp_pheromone[start][end]
# Update pheromone between all cities, old pheromone decay plus new iteration pheromone
for i in range(city_num):
for j in range(city_num):
pheromone_graph[i][j] = pheromone_graph[i][j] * RHO + temp_pheromone[i][j]
# Main loop
def mainloop(self):
()
#----------- entry point to the program -----------
if __name__ == '__main__':
TSP(()).mainloop()
summarize
That's all for this post, I hope it helped you and I hope you'll check back for more from me!