社区首页 >专栏 >经典优化算法 | 蚁群算法解析

经典优化算法 | 蚁群算法解析

墨明棋妙27

发布于 2022-09-23 03:16:22

3K00

代码可运行

文章被收录于专栏：19961996

运行总次数：0

代码可运行

蚁群算法基本思想

蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径问题。根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化(如原有路径上有了障碍物)后，自适应地搜索新的最佳路径。蚂蚁是如何做到这一点的呢？

原来，蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物一信息激素一也可称之为信息素，使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，以致信息素强度增大(当然，随时间的推移会逐渐减弱)，所以蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，这种选择过程被称之为蚂蚁的自催化行为。由于其原理是一种正反馈机制.因此，也可将蚂蚁王国理解为所谓的增强型学习系统。

在自然界中，蚁群的这种寻找路径的过程表现为一种正反馈过程，“蚁群算法”就是模仿生物学蚂蚁群觅食寻找最优路径原理衍生出来的。

蚁群算法数学模型

应该说前面介绍的蚁群算法只是一种算法思想，要是想真正应用该算法，还需要针对一个特定问题，建立相应的数学模型。现仍以经典的TSP问题为例，来进一步阐述如何基于蚁群算法来求解实际问题。

对于TSP问题，为不失一般性，设整个蚂蚁群体中蚂蚁的数量为m，城市的数量为n，城市i与城市j之间的距离为

d_{i j}

$d_{ij}$

(i，j=1，2，…，n)，t时刻城市i与城市j连接路径上的信息素浓度为

τ_{i j}

$\tau _{ij}$

(t)。初始时刻，蚂蚁被放置在不同的城市里，且各城市间连接路径上的信息素浓度相同，不妨设

τ_{i j}

$\tau _{ij}$

(0)=

τ

$\tau$

(0)。然后蚂蚁将按一定概率选择线路，不妨设

P_{i j}^{k} (t)

$P_{ij}^{k}(t)$

为t时刻蚂蚁k从城市i转移到城市j的概率。我们知道,“蚂蚁TSP”策略会受到两方面的左右，首先是访问某城市的期望，另外便是其他蚂蚁释放的信息素浓度，所以定义:

其中，

η_{i j}^{t}

$\eta _{ij}^{t}$

为启发函数，表示蚂蚁从城市i转移到城市j的期望程度:

a l l o w_{k}

$allow_{k}$

(k=1， 2， …， m)为蚂蚁k待访问城市集合，开始时，

a l l o w_{k}

$allow_{k}$

中有n一1个元素，即包括除了蚂蚁k出发城市的其他多有城市，随着时间的推移，

a l l o w_{k}

$allow_{k}$

中的元素越来越少，直至为空；a为信息素重要程度因子，简称信息度因子。其值越大，表示信息影响强度越大；

β

$\beta$

为启发函数重要程度因子，简称启发函数因子，其值越大，表明启发函数影响越大。

在蚂蚁遍历城市的过程中，与实际情况相似的是，在蚂蚁释放信息素的同时，各个城市间连接路径上的信息素的强度也在通过挥发等方式逐渐消失。为了描述这一特征，不妨令p(0<p<1)表示信息素的挥发程度。这样，当所有蚂蚁完整走完一遍所有城市之后，各个城市间连接路径上的信息浓度为：

其中，

Δ τ_{i j}^{k}

$\Delta \tau_{ij}^{k}$

为第k只蚂蚁在城市i与城市j连接路径上释放信息素而增加的信息素浓度；

Δ τ_{i j}

$\Delta \tau_{ij}$

为所有蚂蚁在城市i与城市j连接路径上释放信息素而增加的信息素浓度。

一般

Δ τ_{i j}^{k}

$\Delta \tau_{ij}^{k}$

的值可由ant cycle system模型进行计算：

其中，Q为信息素常数，表示蚂蚁循环一次所释放的信息素总量；

L_{k}

$L_{k}$

为第k只蚂蚁经过路径的总长度。

蚁群算法流程

用蚁群算法求解TSP问题的算法流程如下图所示，具体每步的含义如下：

步骤1：对相关参数进行初始化，包括蚁初始化群规模、信息素因子、启发函数因子、信息素、挥发因子、信息素常数、最大迭代次数等，以及将数据读人程序，并对数据进行基本的处理，如将城市的坐标位置，转为城市间的矩阵。
步骤2：随机将蚂蚁放于不同的出发点，对每个蚂蚁计算其下一个访问城市，直至所更新信息素表有蚂蚁访问完所有城市。
步骤3：计算各个蚂蚁经过的路径长度

L_{k}

$L_{k}$

，记录当前迭代次数中的最优解，同时对各个城市连接路径上的信息素浓度进行更新。

步骤4：判断是否达到最大迭代次数，若否，则返回步骤2，否则终止程序。
步骤5：输出程序结果，并根据需要输出程序寻优过程中的相关指标，如运行时间、收敛迭代次数等。

python简单实现

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('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.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()