蚁群算法代码

import numpy as np
import matplotlib.pyplot as plt

# 建立“蚂蚁”类
class Ant(object):
    def __init__(self, path):
        self.path = path  # 蚂蚁当前迭代整体路径
        self.length = self.calc_length(path)  # 蚂蚁当前迭代整体路径长度

    def calc_length(self, path_):  # path=[A, B, C, D, A]注意路径闭环
        length_ = 0
        for i in range(len(path_) - 1):
            delta = (path_[i].x - path_[i + 1].x, path_[i].y - path_[i + 1].y)
            length_ += np.linalg.norm(delta)
        return length_

    @staticmethod
    def calc_len(A, B):  # 静态方法,计算城市A与城市B之间的距离
        return np.linalg.norm((A.x - B.x, A.y - B.y))


# 建立城市类
class City(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y


##建立路径类
class Path(object):
    def __init__(self, A):  #A为起始路径
        self.path = [A, A]

    def add_path(self, B):  #追加路径信息,方便计算整体路径长度
        self.path.append(B)
        self.path[-1], self.path[-2] = self.path[-2], self.path[-1]
        ##path = [A,B,C,D,A]

# 构建“蚁群算法”的主体
class ACO(object):
    def __init__(self, ants_num=50, maxIter=300, alpha=1, beta=5, rho=0.1, Q=1):
        self.ants_num = ants_num  ##蚂蚁个数
        self.maxIter = maxIter  ##蚁群最大迭代次数
        self.alpha = alpha  ##信息启发因子
        self.beta = beta  ##期望启发因子
        self.rho = rho  ##信息素挥发速度
        self.Q = Q  ##信息素强度
        #########################
        self.deal_data("coordinates.dat")  ##提取所有城市的坐标信息
        #########################
        self.path_seed = np.zeros(self.ants_num).astype(int)  # 记录一次迭代过程中每个蚂蚁的初始城市下标
        self.ants_info = np.zeros((self.maxIter, self.ants_num))  ##记录每一次迭代后的所有蚂蚁的路径长度信息
        self.best_path = np.zeros(self.maxIter)  # 记录每次迭代后整个蚁群的“历史”最短路径长度
        ###########################
        self.solve()  # 完成算法的迭代更新
        self.display()  # 数据可视化展示

    def deal_data(self, filename):
        with open(filename, 'rt') as f:
            temp_list = list(line.split() for line in f)  # 临时存储提取出来的坐标信息
        self.cities_num = len(temp_list)  # 1. 获取城市个数
        self.cities = list(City(float(item[0]), float(item[1])) for item in temp_list)  # 2. 构建城市列表
        self.city_dist_mat = np.zeros((self.cities_num, self.cities_num))  # 3. 构建城市距离矩阵
        for i in range(self.cities_num):
            A = self.cities[i]
            for j in range(i, self.cities_num):
                B = self.cities[j]
                self.city_dist_mat[i][j] = self.city_dist_mat[j][i] = Ant.calc_len(A, B)
        self.phero_mat = np.ones((self.cities_num, self.cities_num))  ##4.初始化信息素矩阵,(信息素初始化不能为零)

        self.eta_mat = 1 / (self.city_dist_mat + np.diag([np.inf] * self.cities_num))  ##5.初始化启发函数矩阵

    def solve(self):
        iterNum = 0  ##当前迭代次数
        while iterNum < self.maxIter:
            self.random_seed()  ##使整个蚁群产生随机的起始点
            delta_phero_mat = np.zeros((self.cities_num, self.cities_num))  ##初始化每次迭代后的信息素增量
            ######################################################
            for i in range(self.ants_num):
                city_index1 = self.path_seed[i]  #记录每只蚂蚁访问的第一个城市下标
                ant_path = Path(self.cities[city_index1])  #记录每只蚂蚁访问过的城市
                tabu = [city_index1]  #记录每只蚂蚁访问过的城市下标,禁忌城市下标列表
                non_tabu = list(set(range(self.cities_num)) - set(tabu))
                for j in range(self.cities_num - 1):  ##对余下的城市进行访问
                    up_proba = np.zeros(self.cities_num - len(tabu))  ##初始化状态迁移概率的分子
                    for k in range(self.cities_num - len(tabu)):
                        up_proba[k] = np.power(self.phero_mat[city_index1][non_tabu[k]], self.alpha) * np.power(
                            self.eta_mat[city_index1][non_tabu[k]], self.beta)
                    proba = up_proba / sum(up_proba)  ##每条可能子路径的状态迁移概率
                    while True:  # 提取出下一城市的下标
                        random_num = np.random.rand()
                        index_need = np.where(proba > random_num)[0]
                        if len(index_need) > 0:
                            city_index2 = non_tabu[index_need[0]]
                            break
                    ant_path.add_path(self.cities[city_index2])
                    tabu.append(city_index2)
                    non_tabu = list(set(range(self.cities_num)) - set(tabu))
                    city_index1 = city_index2
                self.ants_info[iterNum][i] = Ant(ant_path.path).length
                if iterNum == 0 and i == 0:  ##完成对最佳路径的记录
                    self.best_cities = ant_path.path
                else:
                    if self.ants_info[iterNum][i] < Ant(self.best_cities).length:
                        self.best_cities = ant_path.path
                tabu.append(tabu[0])  ##每次迭代完成之后,使禁忌城市下标列表形成完整闭环
                for l in range(self.cities_num):
                    delta_phero_mat[tabu[l]][tabu[l + 1]] += self.Q / self.ants_info[iterNum][i]

            self.best_path[iterNum] = Ant(self.best_cities).length

            self.update_phero_mat(delta_phero_mat)  ##更新信息素矩阵
            iterNum += 1  ##更新迭代次数

    def update_phero_mat(self, delta):
        self.phero_mat = (1 - self.rho) * self.phero_mat + delta

    def random_seed(self):  # 产生随机的起始点表,尽量保证所有蚂蚁的起始点不同
        if self.ants_num <= self.cities_num:  # 蚂蚁数<=城市数
            self.path_seed[:] = np.random.permutation(range(self.cities_num))[:self.ants_num];
        else:  #蚂蚁数 > 城市数
            self.path_seed[:self.cities_num] = np.random.permutation(range(self.cities_num))
            temp_index = self.cities_num
            while temp_index + self.cities_num <= self.ants_num:
                self.path_seed[temp_index:temp_index + self.cities_num] = np.random.permutation(range(self.cities_num))
                temp_index += self.cities_num
            temp_left = self.ants_num % self.cities_num
            if temp_left != 0:
                self.path_seed[temp_index:] = np.random.permutation(range(self.cities_num))[:temp_left]

    def display(self):  ##数据可视化
        plt.figure(figsize=(6, 10))
        plt.subplot(211)
        plt.plot(self.ants_info, 'g.')
        plt.plot(self.best_path, 'r-', label='history_best')
        plt.xlabel("Iteration")
        plt.ylabel("length")
        plt.legend()
        plt.subplot(212)
        plt.plot(list(city.x for city in self.best_cities), list(city.y for city in self.best_cities), 'g-')
        plt.plot(list(city.x for city in self.best_cities), list(city.y for city in self.best_cities), 'r.')
        plt.xlabel("x")
        plt.ylabel("y")
        plt.savefig("Ant.png", dpi=500)
        plt.show()
        plt.close()
    
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,456评论 5 477
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,370评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,337评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,583评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,596评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,572评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,936评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,595评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,850评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,601评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,685评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,371评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,951评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,934评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,167评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 43,636评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,411评论 2 342

推荐阅读更多精彩内容