蚁群算法求解TSP
蚁群算法
蚁群算法是一种经典的传统人工智能算法，早在上个世纪90年代就提出了。网络中已经有不少教材与教程，这里再也不复述。
推荐《人工智能导论》（第四版），王万良编著，其6.7章节将蚁群算法讲的很是简单清楚。
网上也有不少matlab版本，java版本的蚁群算法模板。
笔者周日为了练习编码能力，完成了python版本的蚁群算法。文末附上github开源代码网址，项目中有测试样例与实验数据。java
参数
self.Maximum = np.inf # 设定最大值 self.readCitMapfromTxt() self.citymap = np.array(np.full((self.mapSize,self.mapSize),self.Maximum)) # citymap[i][j] 表示 城市i，j的距离 self.visionDistsnce = np.array(np.full((self.mapSize, self.mapSize),0)) # 能见度 是 距离的倒数 self.antNumber = 50 # 蚁群规模 self.initialInfomationRemain = 100 # 初始化的信息素 self.informationMap = np.array(np.full((self.mapSize, self.mapSize), self.initialInfomationRemain)) self.alpha = 1 # a值，a越大，说明该蚂蚁更倾向于走其余蚂蚁走过的路径 self.beta = 5 # b值，b越大，说明该蚂蚁更倾向于局部信息做出判断，达成局部最优解 self.rho = 0.9 # Rho值，信息素残留常数 self.heuristicRate = 1 # 启发式的比例 self.infomationFadeOutRate = 1 - self.rho # 信息素挥发率，越大，以前搜索过的路径再被搜索的几率也大， # 越小，提升随机性与全局搜索能力，可是算法收敛程度下降 self.Q = 100 # Q值，为一圈下来，一只蚂蚁能释放出的信息素的数量 self.iterateNumber = 30 # 设计迭代次数 self.antLoopDistance = [0 for i in range(self.antNumber)] # 蚂蚁跑完一圈后的路程 self.minDistance = 1e9 # 最短路径的长度 self.minDistanceTrace = [] # 存最短路径的序列 self.ant = [] # 记录蚂蚁的轨迹
初始化蚂蚁
随机放置蚂蚁python
# 初始化蚂蚁的位置 def setAnt(self): for i in range(self.antNumber): startCity = random.randint(0,self.mapSize-1) # 闭区间 self.ant.append([startCity])
信息素
信息素褪去
每次迭代，信息素会褪去git
# 信息素褪去 def informationFadeOut(self): for i in range(len(self.informationMap)): for j in range(len(self.informationMap[i])): self.informationMap[i][j] *= self.rho
信息素更新
在信息素褪去后再根据每只蚂蚁的路劲来更新信息素地图github
# 更新信息素 def updateInformationMap(self): # 计算第i只蚂蚁更新的信息素 for i in range(self.antNumber): informationAllocation = np.array(np.full((self.mapSize, self.mapSize), float(0))) for j in range(len(self.ant[i])): # 起始城市与末位城市相连 if j == 0: self.informationMap[self.ant[i][j]][self.ant[i][-1]] += self.Q * self.citymap[self.ant[i][j]][self.ant[i][-1]] / self.antLoopDistance[i] self.informationMap[self.ant[i][-1]][self.ant[i][j]] += self.Q * self.citymap[self.ant[i][-1]][self.ant[i][j]] / self.antLoopDistance[i] else: self.informationMap[self.ant[i][j]][self.ant[i][j-1]] += self.Q * self.citymap[self.ant[i][j]][self.ant[i][j-1]] / self.antLoopDistance[i] self.informationMap[self.ant[i][j-1]][self.ant[i][j]] += self.Q * self.citymap[self.ant[i][j-1]][self.ant[i][j]] / self.antLoopDistance[i]
重要参数更新
每次迭代，要清理历史路径等重要参数web
# 更新重要信息 def updateAntInformation(self): for i in range(self.antNumber): startCity = self.ant[i][0] del self.ant[i][:] self.ant[i].append(startCity) self.antLoopDistance[i] = 0 # print(self.ant[i])
选择函数
此函数根据此公式来让蚂蚁按权重地随机选择
算法
# 蚂蚁作路径选择 def antChoice(self,antNumber): curruntCity = self.ant[antNumber][-1] visitedCity = set(self.ant[antNumber]) allowedCity = set(range(0,self.mapSize)) - visitedCity # 计算启发式参数，距离越近几率越大 distanceSum = float(0) for city in allowedCity: distanceSum += self.citymap[curruntCity][city] # 启发式初始为0 heuristic = np.array(np.full((self.mapSize), float(0))) for city in allowedCity: heuristic[city] = self.heuristicRate * distanceSum / self.citymap[curruntCity][city] # 计算该蚂蚁全部可能性 posibility = [float(0) for i in range(self.mapSize)] posibilitySum = float(0) for city in allowedCity: posibility[city] = np.power(self.informationMap[curruntCity][city],self.alpha) * np.power(heuristic[city],self.beta) posibilitySum += posibility[city] # 计算最后可能性 finalPosibility = [float(0) for i in range(self.mapSize)] for city in allowedCity: finalPosibility[city] = posibility[city] / posibilitySum # 最后根据可能性中随机选择 # 此处存在问题 anchor = random.random() psum = float(0) for choiceCity in range(self.mapSize) : if psum < anchor and ( psum + finalPosibility[choiceCity] ) > anchor : return choiceCity psum += finalPosibility[choiceCity] return allowedCity.pop()
主要函数
此函数按照迭代次数要求，整合了上诉各个功能网络
# 蚁群算法主要函数 def doACO(self): self.setAnt() for l in range(self.iterateNumber): print("In "+str(l)+" iteration!") # 蚂蚁i开始依次搜索 for i in range(self.antNumber): # 蚂蚁i没有跑圈就继续搜索 while len(self.ant[i]) < self.mapSize: # 蚂蚁根据信息素和启发式选择下一个城市 choiceCity = self.antChoice(i) self.antLoopDistance[i] += self.citymap[self.ant[i][-1]][choiceCity] self.ant[i].append(choiceCity) # 蚂蚁i已经走到了一圈 self.antLoopDistance[i] += self.citymap[self.ant[i][0]][self.ant[i][-1]] if self.antLoopDistance[i] < self.minDistance : self.minDistance = self.antLoopDistance[i] print("min ant " + str(i)+ " trace as :" ,self.ant[i]) self.minDistanceTrace = self.ant[i].copy() # 全部蚂蚁搜索完了，信息素褪去 self.informationFadeOut() # 蚂蚁搜索完了要留下，新的信息素 self.updateInformationMap() # 更新重要信息 self.updateAntInformation() print("Finish search!") print("Min distance is :", self.minDistance) # print("Trace is :",self.minDistanceTrace) print("Trace is :") for i in self.minDistanceTrace: print(self.cityNumber[i], end=' ')
测试