蚁群算法

抽象来源核心思想迭代公式

抽象来源

模仿自然界中蚂蚁的觅食行为。

核心思想

蚁群觅食过程中,每只蚂蚁在所走过的路径上均会释放出一种信息素,该信息素随时间的推移逐渐挥发。因此,每条路径上的信息素同时存在正负反馈两种机制。正反馈:蚂蚁每次经过该路径均会释放信息素使得该路径上的信息素浓度增加;负反馈:每条路径上的信息素随时间推移会逐渐挥发。由此,我们可以判断,在起点与终点之间,当相同数量的蚂蚁初始同时经过两条不同的路径时,路径上初始信息素的浓度是相同的;不过,当路径越短时,信息素挥发时间也越短,残留信息素浓度也将越高。随后的蚂蚁将根据路径上残留信息素浓度的大小对路径进行选择 --- 浓度越高,选择概率越大。最终导致信息素浓度越高的路径上蚂蚁的选择数目越多,而更多的蚂蚁也将同时导致该路径上残留信息素浓度越高(即高者越高,低者越低)。因此,在理想情况下,整个蚁群将逐渐向信息素浓度最高的路径(即最短路径)进行转移。

迭代公式

  • 时刻t,蚂蚁k由节点i向节点j的状态转移概率: pkij(t)=⎧⎩⎨[τij(t)]α⋅[ηij(t)]β∑s∈allowedk[τis(t)]α⋅[ηis(t)]β0 if j∈allowedk if j∉allowedk(1)(1)pijk(t)={[τij(t)]α⋅[ηij(t)]β∑s∈allowedk[τis(t)]α⋅[ηis(t)]β if j∈allowedk0 if j∉allowedk 其中αα为信息启发式因子,ββ为期望启发式因子,ττ为路径残留信息素,ηη为启发函数
  • 残留信息素迭代更新方式(在完成一次迭代后集体进行更新): τij(t+1)=(1−ρ)⋅τij(t)+Δτij(t)(2)(2)τij(t+1)=(1−ρ)⋅τij(t)+Δτij(t) 其中ρρ为信息素挥发速度 --- 负反馈相关,ΔτijΔτij为信息素增量 --- 正反馈相关 信息素增量: Δτij(t)=∑mk=1Δτkij(t)Δτij(t)=∑k=1mΔτijk(t) 每只蚂蚁对信息素增量的贡献: Δτkij(t)={Q/Lk0 if the k_th ant goes through the nodes labeled with i and j on the current iteration else Δτijk(t)={Q/Lk if the k_th ant goes through the nodes labeled with i and j on the current iteration0 else 其中,LkLk代表第k只蚂蚁在当前迭代过程中完整所走过的总路程
  • 启发函数表达式: ηij(t)=1dij(3)(3)ηij(t)=1dij 其中dijdij为节点i至节点j之间的距离
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]


# 构建“蚁群算法”的主体
class ACO(object):
    def __init__(self, ant_num=50, maxIter=300, alpha=1, beta=5, rho=0.1, Q=1):
        self.ants_num = ant_num   # 蚂蚁个数
        self.maxIter = maxIter    # 蚁群最大迭代次数
        self.alpha = alpha        # 信息启发式因子
        self.beta = beta          # 期望启发式因子
        self.rho = rho            # 信息素挥发速度
        self.Q = Q                # 信息素强度
        ###########################
        self.deal_data(r'C:\Users\admin\Desktop\LSTM\emote_score\1.txt')                         # 提取所有城市的坐标信息
        ###########################
        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, 'r') 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.phero_upper_bound = self.phero_mat.max() * 1.2                              ###信息素浓度上限
        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
        # self.phero_mat = np.where(self.phero_mat > self.phero_upper_bound, self.phero_upper_bound, self.phero_mat) # 判断是否超过浓度上限

    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('ACO.png', dpi=500)
        plt.show()
        plt.close()


ACO()
  • .txt文件内容如下:
565.0   575.0
25.0   185.0
345.0   750.0
945.0   685.0
845.0   655.0
880.0   660.0
25.0    230.0
525.0   1000.0
580.0   1175.0
650.0   1130.0
1605.0   620.0
1220.0   580.0
1465.0   200.0
1530.0   5.0
845.0   680.0
725.0   370.0
145.0   665.0
415.0   635.0
510.0   875.0
560.0   365.0
300.0   465.0
520.0   585.0
480.0   415.0
835.0   625.0
975.0   580.0
1215.0   245.0
1320.0   315.0
1250.0   400.0
660.0   180.0
410.0   250.0
420.0   555.0
575.0   665.0
1150.0   1160.0
700.0   580.0
685.0   595.0
685.0   610.0
770.0   610.0
795.0   645.0
720.0   635.0
760.0   650.0
475.0   960.0
95.0   260.0
875.0   920.0
700.0   500.0
555.0   815.0
830.0   485.0
1170.0   65.0
830.0   610.0
605.0   625.0
595.0   360.0
1340.0   725.0
1740.0   245.0
  • 结果展示

本文分享自微信公众号 - 数据科学CLUB(jiji8215),作者:少年吉

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PSO算法代码

    用户3577892
  • 用最小二乘法对多项式进行拟合并可视化

    本篇文章所讲代码是对2018年全国大学生数学建模比赛A题附件的数据进行拟合,代码如下:

    用户3577892
  • 遗传算法求解最值问题并可视化

    用户3577892
  • 搭一个简单的接口测试框架

    可以理解为工具的集合,把日常所需要实现功能的代码,模块进行封装起来结合其他的工具进行测试。得出结论报告。

    赵云龙龙
  • 爆破cobalt strike密码脚本

    无聊的我又来水文了,今天的是爆破cobalt strike密码脚本,最近活脱脱成了一个GITHUB的安(搬)利(运)管(工)。其余时间都是在写作业

    天钧
  • PaddlePaddle版Flappy-Bird—使用DQN算法实现游戏智能

    刚刚举行的 WAVE SUMMIT 2019 深度学习开发者峰会上,PaddlePaddle 发布了 PARL 1.1 版本,这一版新增了 IMPALA、A3C...

    用户1386409
  • Python3.x+pyqtgraph实现数据可视化教程

    1、pyqtgraph库数据可视化效果还不错,特别是窗体程序中图像交互性较好;安装也很方便,用 pip 安装。

    砸漏
  • python第四十二课——__str__(self)函数

    4.__str__(self): 作用: 创建完对象,直接打印对象名/引用名我们得到的是对象的内存信息(十六进制的地址信息), 这串数据我们程序员并不关心...

    hankleo
  • 从PEP-8学习Python编码风格

    Python3中应当总是使用UTF-8。(Python2使用ASCII。)在使用了规定编码后不需要再声明文件编码。

    py3study
  • DBSCAN算法的Python实现

    当我傻傻的用python写DBSCAN,我才突然想起来在scikit-learn中有DBSCAN,可以直接调用啊,我本来想要放弃快完成的代码,但是我想我可以发博...

    张凝可

扫码关注云+社区

领取腾讯云代金券