"""
蚁群算法Python实现
点击:0 发布日期:2007-4-24 7:46:00 进入论坛
"""
# -*- coding: utf-8 -*-
"""
这个是我用python写的基本蚁群算法程序
用的测试数据是从TSPLIB上下载的eil51.tsp(http://www.informatik.uni-heidelberg.de/groups/comopt/software/TSPLIB95/STSP.html)
在TSPLIB的站点上的最好结果是426,我得到的最好结果是463左右,差距还很大哪
PS:用python跑算法实在是太慢了,如果嵌入C又太麻烦,所以偶决定以后还是尽可能用C或者matlab好了.....
在最大运行次数为100次的情况下得到的最的运行结果为:
92 : 463.388150178 : [23, 7, 26, 8, 31, 28, 3, 20, 35, 36, 29, 21, 50, 9, 49, 5,
38, 11, 32, 1, 22, 2, 16, 30, 34, 39, 10, 33, 45, 15, 44, 37, 17, 4, 18, 14, 25
, 13, 41, 19, 40, 42, 47, 12, 46, 51, 27, 48, 6, 24, 43]
93 : 463.388150178 : [23, 7, 26, 8, 31, 28, 3, 20, 35, 36, 29, 21, 50, 9, 49, 5,
38, 11, 32, 1, 22, 2, 16, 30, 34, 39, 10, 33, 45, 15, 44, 37, 17, 4, 18, 14, 25
, 13, 41, 19, 40, 42, 47, 12, 46, 51, 27, 48, 6, 24, 43]
94 : 463.388150178 : [23, 7, 26, 8, 31, 28, 3, 20, 35, 36, 29, 21, 50, 9, 49, 5,
38, 11, 32, 1, 22, 2, 16, 30, 34, 39, 10, 33, 45, 15, 44, 37, 17, 4, 18, 14, 25
, 13, 41, 19, 40, 42, 47, 12, 46, 51, 27, 48, 6, 24, 43]
95 : 463.388150178 : [23, 7, 26, 8, 31, 28, 3, 20, 35, 36, 29, 21, 50, 9, 49, 5,
38, 11, 32, 1, 22, 2, 16, 30, 34, 39, 10, 33, 45, 15, 44, 37, 17, 4, 18, 14, 25
, 13, 41, 19, 40, 42, 47, 12, 46, 51, 27, 48, 6, 24, 43]
96 : 463.388150178 : [23, 7, 26, 8, 31, 28, 3, 20, 35, 36, 29, 21, 50, 9, 49, 5,
38, 11, 32, 1, 22, 2, 16, 30, 34, 39, 10, 33, 45, 15, 44, 37, 17, 4, 18, 14, 25
, 13, 41, 19, 40, 42, 47, 12, 46, 51, 27, 48, 6, 24, 43]
97 : 463.388150178 : [23, 7, 26, 8, 31, 28, 3, 20, 35, 36, 29, 21, 50, 9, 49, 5,
38, 11, 32, 1, 22, 2, 16, 30, 34, 39, 10, 33, 45, 15, 44, 37, 17, 4, 18, 14, 25
, 13, 41, 19, 40, 42, 47, 12, 46, 51, 27, 48, 6, 24, 43]
98 : 463.388150178 : [23, 7, 26, 8, 31, 28, 3, 20, 35, 36, 29, 21, 50, 9, 49, 5,
38, 11, 32, 1, 22, 2, 16, 30, 34, 39, 10, 33, 45, 15, 44, 37, 17, 4, 18, 14, 25
, 13, 41, 19, 40, 42, 47, 12, 46, 51, 27, 48, 6, 24, 43]
99 : 463.388150178 : [23, 7, 26, 8, 31, 28, 3, 20, 35, 36, 29, 21, 50, 9, 49, 5,
38, 11, 32, 1, 22, 2, 16, 30, 34, 39, 10, 33, 45, 15, 44, 37, 17, 4, 18, 14, 25
, 13, 41, 19, 40, 42, 47, 12, 46, 51, 27, 48, 6, 24, 43]
"""
import os
import sys
import sets
import random
import string
from string import *
from math import *
BestTour = [] # store the best path 存储最优路径
CitySet = sets.Set() # city set 城市设置
CityList = [] # city list 城市列表
PheromoneTrailList = [] # pheromone trail list信息素轨迹列表
PheromoneDeltaTrailList = [] # delta pheromone trail list增量信息素轨迹列表
CityDistanceList = [] # city distance list 城市距离列表
AntList = [] # ants 蚂蚁
class BACA:
"implement basic ant colony algorithm"
# following are some essential parameters/attributes for BACA 初始化几个参数:基本的蚁群算法
def __init__(self, cityCount=51, antCount=34, q=80,
alpha=2, beta=5, rou=0.3, nMax=100):
self.CityCount = cityCount
self.AntCount = antCount
self.Q = q #信息素强度,正常数
self.Alpha = alpha
self.Beta = beta
self.Rou = rou #信息素挥发系数,一般为0.5~0.9之间
self.Nmax = nMax #迭代次数
self.Shortest = 10e6
# set random seed
random.seed()
# init global data structure 初始化全局数据结构
for nCity in range(self.CityCount):
BestTour.append(0)
for row in range(self.CityCount):
pheromoneList = []
pheromoneDeltaList = []
for col in range(self.CityCount):
pheromoneList.append(100) # init pheromone list to const 100 初始化信息素列表为100
pheromoneDeltaList.append(0) # init pheromone delta list to const 0 初始化信息素增量列表为0
PheromoneTrailList.append(pheromoneList)
PheromoneDeltaTrailList.append(pheromoneDeltaList)
def ReadCityInfo(self, fileName): #读取城市信息
file = open(fileName)
#print file.readlines()
#CityList = []
for line in file.readlines():
cityN, cityX, cityY = string.split(line)
#print cityN,cityX,cityY
CitySet.add(atoi(cityN)) # add into city set
CityList.append((atoi(cityN),atoi(cityX),atoi(cityY)))
#print cityList
#print CitySet
for row in range(self.CityCount):
distanceList = []
for col in range(self.CityCount):
distance = sqrt(pow(CityList[row][1]-CityList[col][1],2)+pow(CityList[row][2]-CityList[col][2],2))
distanceList.append(distance)
CityDistanceList.append(distanceList)
#print CityDistanceList
def PutAnts(self): #放置蚂蚁
"""randomly put ants on cities"""
for antNum in range(self.AntCount):
city = random.randint(1, self.CityCount)
ant = ANT(city)
AntList.append(ant)
#print ant.CurrCity
def Search(self): #搜索解空间
"""search solution space"""
for iter in range(self.Nmax):
self.PutAnts()
for ant in AntList:
for ttt in range(len(CityList)):
ant.MoveToNextCity(self.Alpha, self.Beta)
ant.UpdatePathLen()
tmpLen = AntList[0].CurrLen
tmpTour = AntList[0].TabuCityList
for ant in AntList[1:]:
if ant.CurrLen < tmpLen:
tmpLen = ant.CurrLen
tmpTour = ant.TabuCityList
if tmpLen < self.Shortest:
self.Shortest = tmpLen
BestTour = tmpTour
print % iter,":",self.Shortest,":",BestTour
self.UpdatePheromoneTrail()
## for ant in AntList:
## city = ant.TabuCityList[-1]
## ant.ClearTabu()
## ant.AddCity(city)
def UpdatePheromoneTrail(self): #更新信息素轨迹
for ant in AntList:
for city in ant.TabuCityList[0:-1]:
idx = ant.TabuCityList.index(city)
nextCity = ant.TabuCityList[idx+1]
PheromoneDeltaTrailList[city-1][nextCity-1] = self.Q/ant.CurrLen
PheromoneDeltaTrailList[nextCity-1][city-1] = self.Q/ant.CurrLen
lastCity = ant.TabuCityList[-1]
firstCity = ant.TabuCityList[0]
PheromoneDeltaTrailList[lastCity-1][firstCity-1] = self.Q/ant.CurrLen
PheromoneDeltaTrailList[firstCity-1][lastCity-1] = self.Q/ant.CurrLen
for (city1,city1X,city1Y) in CityList:
for (city2,city2X,city2Y) in CityList:
PheromoneTrailList[city1-1][city2-1] = ((1-self.Rou)*PheromoneTrailList[city1-1][city2-1] +
PheromoneDeltaTrailList[city1-1][city2-1])
PheromoneDeltaTrailList[city1-1][city2-1] = 0
class ANT:
"implement ant individual" #单个蚂蚁
def __init__(self, currCity = 0):
# following are some essential attributes for ant
self.TabuCitySet = sets.Set() # tabu city set 禁忌城市设置
self.TabuCityList = [] # tabu city list 禁忌城市列表