ArcPy

使用python实现蚁群算法

by giser · 2019-04-24

此次使用python实现蚁群算法是仿照蚁群优化算法的JAVA实现中的蚁群算法实现方法，使用的也是其中的数据（此处为上传数据），如需更深一步了解蚁群算法原理和具体实现过程，请参考蚁群优化算法的JAVA实现和蚁群算法java实现以及TSP问题蚁群算法求解。

# ants 类
import numpy as np
import random
import math


class ant:
    Tour = 0
    unvisitedcity = 0
    tourlength = 0
    citys = 0
    count = 0
    def RandomSelectCity(self,citycount):
        ant.citys = citycount
        ant.tourlength = 0
        ant.Tour = np.zeros((citycount+1),int)
        ant.unvisitedcity = np.ones((citycount))

        for i in np.arange(citycount):
            ant.Tour[i] = -1
        firstcity = random.randint(0,citycount-1)
        ant.unvisitedcity[firstcity] = 0 #0表示已经访问过
        ant.Tour[0] = firstcity #起始城市

    def SelectNextCity(self,index,tao,distance):
        p = np.zeros((ant.citys))  #citys
        x = 0
        alpha = 1.0
        beta = 2.0
        sum = 0
        currentcity = ant.Tour[index-1]
              # print("curr",ant.Tour)
        # print(ant.unvisitedcity)
        for i in range(ant.citys):
            # print(ant.unvisitedcity[i])
            if ant.unvisitedcity[i] == 1:
                sum += (math.pow(tao[currentcity][i], alpha) * math.pow(1.0/distance[currentcity][i], beta))
        #        计算每个城市被选中的概率
        for i in range(ant.citys):
            if ant.unvisitedcity[i] == 0:
                p[i] = 0.0
            else:
                p[i] = (math.pow(tao[currentcity][i], alpha) * math.pow(1.0/distance[currentcity][i], beta))/sum
        selectp = random.random()
#       轮盘赌选择一个城市
        sumselect = 0.0
        selectcity = -1
        for i in  range(ant.citys):
            sumselect += p[i]
            # print("i",i,"sumselect",sumselect)
            if sumselect >= selectp:
                selectcity = i
                break

        if selectcity == -1:
            print('')
        ant.Tour[index] = selectcity
        # print("selectcity",selectcity)
        ant.unvisitedcity[selectcity] = 0
        # print(ant.Tour)

#         计算蚂蚁获得的路径的长度
#         distance 全局的距离矩阵信息
    def CalTourLength(self,distance):
        ant.Tour[ant.citys] = ant.Tour[0]
        for i in range(ant.citys):
            ant.tourlength += distance[int(ant.Tour[i])][int(ant.Tour[i+1])]

# ACO类
from ACO_implement.ACO_implement import ants
import numpy as np
import math
import sys

class ACO:
    # 定义蚂蚁群
    ants = []
    antcount = 0 # 蚂蚁数量
    distance  = 0 #城市之间的距离
    tao = 0 #信息素矩阵
    citycount = 0 #城市数量
    besttour = 0 #求解的最佳路径
    bestlength = 0 #求解最优解的长度
    def __init__(self,filename,antnum):
        ACO.antcount = antnum
        #读取数据
        x = []
        y = []
        z = []
        str = open(filename).readlines()
        ACO.citycount = int(str[0])
        for i in range(1,ACO.citycount+1):
            strbuff = str[i].split()
            x.append(int(strbuff[1]))
            y.append(int(strbuff[2]))
#        计算距离矩阵，计算的是点之间的距离
        ACO.distance = np.zeros((ACO.citycount,ACO.citycount))
        for i in range(ACO.citycount):
            for j in range(ACO.citycount):
                ACO.distance[i][j] = math.sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2))
#         初始化信息矩阵
        ACO.tao = np.zeros((ACO.citycount,ACO.citycount))
        for i in range(ACO.citycount):
            for j in range(ACO.citycount):
                ACO.tao[i][j] = 0.1
        ACO.bestlength = sys.maxsize #最优路径长度
        ACO.besttour = np.zeros((ACO.citycount)) #最优路径
#         随机放置蚂蚁
#         for i in range(ACO.antcount):
#             ACO.ants.append(ants.ant())
#             ACO.ants[i].RandomSelectCity(ACO.citycount)
    """
    跟新信息素矩阵
    """
    def UpdateTao(self):
        rou = 0.5
        # 信息素挥发
        for i in range(ACO.citycount):
            for j in range(ACO.citycount):
                ACO.tao[i][j] = ACO.tao[i][j] *(1-rou)
        # 信息素更新
        for i in range(ACO.citycount):
            for j in range(ACO.citycount):
                ACO.tao[int(ACO.ants[i].Tour[j])][ACO.ants[i].Tour[j+1]]  += 1.0/ACO.ants[i].tourlength

        """
        ACO的运行过程
        maxgen ACO的最多次循环次数
        """
    def run(self,maxgen):
        # 每只蚂蚁移动的过程
        for runtimes in range(maxgen):
            # 随机放置蚂蚁
            for i in range(ACO.antcount):
                ACO.ants.append(ants.ant())
                ACO.ants[i].RandomSelectCity(ACO.citycount)
                for j in range(1,ACO.citycount):
                    ACO.ants[i].SelectNextCity(j,ACO.tao,ACO.distance)
                # 计算蚂蚁获得的路径的长度
                ACO.ants[i].CalTourLength(ACO.distance)
                if ACO.ants[i].tourlength < ACO.bestlength:
#                     保留最优路径
                    ACO.bestlength = ACO.ants[i].tourlength
                    print("第",runtimes+1,"次,发现解",ACO.bestlength)
                    for j in range(0,ACO.citycount):
                        ACO.besttour[j] = ACO.ants[i].Tour[j]
            ACO.UpdateTao(self)
            for i in range(ACO.antcount):
                ACO.ants[i].RandomSelectCity(ACO.citycount)

    """输出运行结果"""
    def ReportResult(self):
        print("最优路径长度是",ACO.bestlength)
        print("最优路径为：",ACO.besttour+1)

#main类
from ACO_implement.ACO_implement import ACO

aco = ACO.ACO("ant_data",1000)
# aco.init("ant_data",1000)
#点数量为50，蚂蚁数量
aco.run(200)

aco.ReportResult()

转载自：https://blog.csdn.net/ZHIXINGHEYITUOPENG/article/details/80819727

相关推荐

Tags: ArcPy 使用python实现蚁群算法

You may also like...