基本蚁群算法的python实现

# -*- 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
        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
                pheromoneDeltaList.append(0)            # init pheromone delta list to const 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  select:
                select = cityProb
        threshold = select * random.random()
        for (cityNum, cityProb) in self.TransferProbabilityList:
            if cityProb >= threshold:
                return (cityNum)
        return (0)
    def MoveToNextCity(self, alpha, beta):
        """move the ant to next city"""
        nextCity = self.SelectNextCity(alpha, beta)
        if nextCity > 0:
            self.AddCity(nextCity)
    def ClearTabu(self):
        """clear tabu list and set"""
        self.TabuCityList = []
        self.TabuCitySet.clear()
        self.AllowedCitySet = CitySet - self.TabuCitySet
    def UpdatePathLen(self):
        """sum up the path length"""
        for city in self.TabuCityList[0:-1]:
            nextCity = self.TabuCityList[self.TabuCityList.index(city)+1]
            self.CurrLen = self.CurrLen + CityDistanceList[city-1][nextCity-1]
        lastCity = self.TabuCityList[-1]
        firstCity = self.TabuCityList[0]
        self.CurrLen = self.CurrLen + CityDistanceList[lastCity-1][firstCity-1]
    def AddCity(self,city):
        """add city to tabu list and set"""
        if city