蚁群算法实现网络拓扑最短路径

import random
import copy
import sys
import mini.settings as sets  #在mini.method_all中有相同的可以实现功能的方法。
import mini.method_all as ma
import numpy as np
# 参数
(ALPHA, BETA, RHO, Q) = (1.0, 2.0, 0.5, 100.0)
# 城市数，蚁群
(city_num, ant_num) = (10, 10)

_ = float("inf")

#赋初值为0.0，长度均未0
distance_graph = [[0.0 for col in range(city_num)] for raw in range(city_num)]
#赋初值为1.0，信息素均为1
pheromone_graph = [[1.0 for s in range(city_num)] for a in range(city_num)]

class Ant(object):

    # 初始化
    def __init__(self, ID,src,dst):

        self.ID = ID  # ID
        self.src = src
        self.dst = dst
        self.pathss = []
        self.__clean_data()  # 随机初始化出生点(计算最短路径要固定源和目的)

    # 初始数据
    def __clean_data(self):
        self.pathss=[]
        self.pathss.append(self.src)
        self.path = []  # 当前蚂蚁的路径
        self.total_distance = 0.0  # 当前路径的总距离
        self.move_count = 0  # 移动次数
        self.current_city = -1  # 当前停留的城市
        self.open_table_city = [True for i in range(city_num)]  # 探索城市的状态

        city_index = self.src #random.randint(0, city_num - 1)  # 随机初始出生点
        self.current_city = city_index
        self.path.append(city_index)
        self.open_table_city[city_index] = False
        self.move_count = 1

    # 选择下一个城市
    def __choice_next_city(self):

        next_city = -1
        select_citys_prob = [0.0 for i in range(city_num)]  # 存储去下个城市的概率
        total_prob = 0.0

        # 获取去下一个城市的概率
        for i in range(city_num):
            if self.open_table_city[i] and distance_graph[self.current_city][i] != 0:
                # print(self.current_city)
                try:
                    # 计算概率：与信息素浓度成正比，与距离成反比
                    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=self.ID,
                                                                                                current=self.current_city,
                                                                                                target=i))
                    sys.exit(1)
        #选取最优的下一跳
        if sum(select_citys_prob)>0:
            prob = max(select_citys_prob)
            next_city = select_citys_prob.index(prob)
        elif next_city == -1:
            temp = 0
            while next_city == -1:
                j = (temp + 1) * (-1)
                temp += 1
                try:
                    self.current_city = self.path[j]
                except:
                    break
                ss = 0
                for i in range(city_num):
                    if self.open_table_city[i] and distance_graph[self.current_city][i] != 0:
                        try:
                            #选取最优的那个下一跳
                            select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) * pow(
                                (1.0 / distance_graph[self.current_city][i]), BETA)
                            if select_citys_prob[i]>ss:
                                ss = select_citys_prob[i]
                                if self.dst not in self.pathss:
                                    k = self.path.index(self.current_city) + 1
                                    self.pathss = self.path[0:k]
                                next_city = i
                        except ZeroDivisionError as e:
                            print('Ant ID: {ID}, current city: {current}, target city: {target}'.format(ID=self.ID,
                                                                                                        current=self.current_city,
                                                                                                        target=i))
                            sys.exit(1)
        # 返回下一个城市序号
        return next_city

    # 计算路径总距离
    def __cal_total_distance(self):
        temp_distance = 0.0
        for i in range(1, city_num):
            try:
                start, end = self.path[i], self.path[i - 1]
                temp_distance += distance_graph[start][end]
            except:
                break

    # 移动操作
    def __move(self, next_city):
        self.pathss.append(next_city)
        self.path.append(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

    # 搜索路径
    def search_path(self):
        # 初始化数据
        self.__clean_data()

        # 搜素路径，遍历完所有城市为止
        while self.move_count < city_num:
            # 移动到下一个城市
            next_city = self.__choice_next_city()
            self.__move(next_city)

        # 计算路径总长度
        self.__cal_total_distance()

class getpath():
    def __init__(self,src,dst,maps, n=city_num,itorators = 100 ):

        # 城市数目初始化为city_num
        self.n = n
        #迭代次数
        self.itorator = itorators
        self.new(src,dst)
        # 计算城市之间的距离
        map = np.zeros((10,10))
        map = maps
        self.kkmap = map
        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)
                if map[i][j] != _:
                    distance_graph[i][j] = maps[i][j]
                else:
                    distance_graph[i][j] = 0
        # print(distance_graph)

    def new(self,src,dst):
        for i in range(city_num):
            for j in range(city_num):
                pheromone_graph[i][j] = 1.0

        self.ants = [Ant(ID,src,dst) for ID in range(ant_num)]  # 初始蚁群
        self.best_ant = Ant(-1,src,dst)  # 初始最优解
        self.best_ant.total_distance = 1 << 31  # 初始最大距离

    def search_path(self):
        i= 0
        # 开始
        while i<self.itorator:
            # 遍历每一只蚂蚁
            for ant in self.ants:
                # 搜索一条路径
                k = ant.search_path()
                # 与当前最优蚂蚁比较
                if ant.total_distance < self.best_ant.total_distance:
                    # 更新最优解
                    self.best_ant = copy.deepcopy(ant)
            # 更新信息素
            self.__update_pheromone_gragh()
            i+=1
        return self.best_ant.pathss
    # 更新信息素
    def __update_pheromone_gragh(self):

        # 获取每只蚂蚁在其路径上留下的信息素
        temp_pheromone = [[0.0 for col in range(city_num)] for raw in range(city_num)]
        for ant in self.ants:
            for i in range(1, city_num):
                start, end = ant.path[i - 1], ant.path[i]
                # 在路径上的每两个相邻城市间留下信息素，与路径总距离反比
                temp_pheromone[start][end] += Q / ant.total_distance
                temp_pheromone[end][start] = temp_pheromone[start][end]

        # 更新所有城市之间的信息素，旧信息素衰减加上新迭代信息素
        for i in range(city_num):
            for j in range(city_num):
                pheromone_graph[i][j] = pheromone_graph[i][j] *(1-RHO) + temp_pheromone[i][j]
def getresult(src,dst,map):
    list = getpath(src, dst, map).search_path()
    list1 = getpath(dst, src, map).search_path()
    path = []
    path1 = []
    if dst in list:
        for i in list:
            if i == dst:
                path.append(i)
                break
            path.append(i)
    if src in list1:
        for i in list1:
            if i == src:
                path1.append(i)
                break
            path1.append(i)
    if len(path) <= len(path1) and len(path)>0 and len(path1)>0:
        results = path
    else:
        path1 = path1[::-1]
        results = path1
    return results

if __name__ == '__main__':
    path = getresult(0,9,sets.setting().initmap)
    # print(path)
    map = sets.setting().initmap
    allpath = []
    while len(path)>2:
        allpath.append(path)
        temp = path
        map = ma.method_all(nodenum=10).dellink(path,map)
        path = getresult(0, 9, map)
    print(allpath)