16 Nov 2021 10850字 37分

通过蚁群算法求解TSP问题

实验内容

通过蚁群算法求解TSP问题。

实验原理

蚁群算法

定义

蚁群系统(Ant System(AS)或Ant Colony System(ACS))是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中，发现蚁群整体会体现一些智能的行为，例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。后经进一步研究发现，这是因为蚂蚁会在其经过的路径上释放一种可以称为“信息素(pheromone)”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。

由上述蚂蚁找食物模式演变来的算法，即是蚁群算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。最近几年，该算法在网络路由中的应用受到越来越多学者的关注，并提出了一些新的基于蚂蚁算法的路由算法。同传统的路由算法相比较，该算法在网络路由中具有信息分布式性、动态性、随机性和异步性等特点，而这些特点正好能满足网络路由的需要。

人工蚁群与真实蚁群相比

相同点	不同点
1. 都存在个体相互交流的通信机制	1. 人工蚂蚁具有记忆能力
2. 都要完成寻找最短路径的任务	2. 人工蚂蚁选择路径时不是完全盲目的
3. 都采用根据当前信息进行路径选择的随机选择策略	3. 人工蚂蚁生活在离散时间的环境中

基本原理

蚂蚁在路径上释放信息素。
碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信息素。
信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高路径。
最优路径上的信息素浓度越来越大。
最终蚁群找到最优寻食路径。

信息素更新模型

蚁周模型

单只蚂蚁所访问路径上的信息素浓度更新规则为：

$Δ𝜏_𝑘{(i, j)} = Q/L_K$ 若第 K 只蚂蚁在本次循环中从 X 到 Y，

否则，$Δ𝜏_𝑘{(i, j)} = 0$。

其中：$𝜏{(i, j)}$ 为当前路径上的信息素。

$Δ𝜏_𝑘{(i, j)}$ 为第k只蚂蚁留在路径（x, y）上的信息素的增量。

$Q$ 为常数 Lk 为优化问题的目标函数值。

$L_k$ 表示第k只蚂蚁在本次循环中所走路径的长度,是 $R_k$ 中所有边的长度和。

蚁量模型

$Δ𝜏_𝑘{(i, j)} = Q/d_{xy}$ 若第 K 只蚂蚁在本次循环中从 X 到 Y，

否则，$Δ𝜏_𝑘{(i, j)} = 0$。

其中， $d_{xy}$ 表示元素（城市）。

蚁密模型

$Δ𝜏_𝑘{(i, j)} = 0$ 若第 K 只蚂蚁在本次循环中从 X 到 Y，

否则，$Δ𝜏_𝑘{(i, j)} = 0$。

不同模型之间的比较

	信息素增量不同	信息素更新时刻不同	信息素更新形式不同
蚁周模型	信息素增量为 $Q / L_k$ , 它只与搜索路线有关，与具体的路径 $(i, j)$ 无关	在第 $k$ 只蚂蚁完成一次路径搜索后，对线路上所有路径进行i信息素的更新	信息素增量与本次搜索的整体路线有关，因此属于全局信息更新
蚁量模型	信息素增量为 $Q / d_{ij}$ ，与路径 $(i, j)$ 的长度有关	在蚁群前进过程中进行，蚂蚁每完成一步移动后更新该路径上的信息素。	利用蚂蚁所有的路径 $(i, j)$ 上的信息进行更新，因此属于局部信息更新。
蚁密模型	信息素增量为固定值 $Q$	在蚁群前进过程中进行，蚂蚁每完成一步移动后更新该路径上的信息素。	利用蚂蚁所有的路径 $(i, j)$ 上的信息进行更新，因此属于局部信息更新。

主要参数的选择

	定义	参数影响分析	理想取值范围
$α$	信息启发式因子	$α$ 值越大，蚂蚁选择之前走过的路径可能就越大，搜索路径的随机性减弱， $α$ 越小，蚁群搜索范围就会减少，容易陷入局部最优	$[0, 5]$
$β$	期望启发式因子	$β$ 值越大，蚁群就越容易选择局部较短路径，这时算法的收敛速度是加快了，但是随机性缺不高，容易得到局部的相对最优	$[0, 5]$
$m$	蚁群数量	$m$ 数目越多，得到的最优解就越精确，但是会产生不少重复解，随着算法接近最优值的收敛，信息正反馈的作用降低，大量的重复工作，消耗了资源，增加了时间复杂度	$[10, 10000]$
$ρ$	信息挥发因子， $1 - ρ $表示残留因子	$ρ$ 过小时，在各路径上残留的信息素过多，导致无效的路径继续杯搜索，影响到算法的收敛速率；$ρ$ 过大，无效的路径虽然可以被排除搜索，但是不能保证有效的路径也会被放弃搜索，影响到最优值的搜索	$[0.1, 0.99]$

常见的变异蚁群算法

精英蚂蚁系统

全局最优解决方案在每个迭代以及其他所有的蚂蚁的沉积信息素。

最大最小蚂蚁系统（MMAS）

添加的最大和最小的信息素量[ τmax，τmin ]，只有全局最佳或迭代最好的巡逻沉积的信息素。所有的边缘都被初始化为τmax并且当接近停滞时重新初始化为τmax。

蚁群系统

蚁群系统已被提出。

基于排序的蚂蚁系统（ASrank）

所有解决方案都根据其长度排名。然后为每个解决方案衡量信息素的沉积量，最短路径相比较长路径的解沉积了更多的信息素。

连续正交蚁群（COAC）

$COAC$ 的信息素沉积机制能使蚂蚁协作而有效地寻解。利用正交设计方法，在可行域的蚂蚁可以使用增大的全局搜索能力和精度，快速、高效地探索他们选择的区域。正交设计方法和自适应半径调整方法也可推广到其他优化算法中，在解决实际问题施展更大的威力。

不同蚁群模型的系统特征比较

系统	真实蚁群	蚁群优化模型	简单阈值模型	仿生制造模型
元素	蚂蚁个体行为	单个人工蚂蚁求解	个体完成任务	单元体拾取与堆积
结构	个体相互影响	通过轨迹间接影响	激励与阈值的关系	空间单元体分布情况
系统环境	自然界	待求解的优化问题	任务分配问题	数据分析问题
行为和功能	群体行为	自组织优化求解	自组织任务分配	自组织数据分析
系统的演化	生存、繁衍	朝最优解方向前进	动态任务分配	完成数据分析

模拟退火算法

可以通过模拟退火算法来对最后结果的选择进行优化,具体操作略。

实验代码

变量的初始化。

CITY_NUMBERS = 31       #城市数量
ANT_NUMBERS = 20        #蚂蚁数量
ALPHA = 1               #信息素启发因子
BETA = 5                #启发函数因子
RHO = 0.10               #信息素挥发速度
Q = 10                  #常数Q
ITERATION_NUMBERS = 75  #迭代次数

建立 $Ant$ 类，$ID$ 用来唯一标识每一个对象，$path$ 用来记录蚂蚁走过的路径，$distance$ 用来记录蚂蚁走过的总距离，$staying_place$ 表示该蚂蚁现在所在的地方，$next_city$ 表示蚂蚁的下一个目的地。

class Ant():
    __slots__ = "ID", "path", "distance","staying_place", "next_city"

对象的初始化，并无新鲜。

  def __init__(self, id):
        self.ID = id
        self.path = []
        self.distance = 0
        self.staying_place = -1
        self.next_city = -1
        pass

函数用于完成下一个要走的城市的选择。

    def select_city(self):

        #
        if self.staying_place == -1:##刚刚开始！
            self.next_city = random.randint(0, CITY_NUMBERS - 1)
            #self.next_city = 0          #固定起点， 测试性能变化！！！！！！

            return

        select_city_probability = [0 for i in range(0, CITY_NUMBERS, 1)]
        total_probability = 0

        for i in range(0, CITY_NUMBERS, 1):
            if i not in self.path:
                select_city_probability[i] = pow(arr_pheromone[self.staying_place][i], ALPHA) *\
                                            pow(1 / arr_distance[self.staying_place][i], BETA)
                # 注意可能会存在数组越界的问题，可以考虑用 TRY 包裹来解决
                total_probability += select_city_probability[i]

        if total_probability > 0:
            temp_probability = random.uniform(0, total_probability)      #生成 0 - 1 的随机数~
            #temp_prob = random.uniform(0.0, total_prob)

            #self.roulette()
            for i in range(0, CITY_NUMBERS, 1):
                if i not in self.path:
                    temp_probability -= select_city_probability[i]
                    if temp_probability < 0:
                        self.next_city = i
                        break                   #找到目标城市，跳出

        if self.next_city == -1:
            self.next_city = random.randint(0, CITY_NUMBERS - 1)
            while self.next_city in self.path:
                self.next_city = random.randint(0, CITY_NUMBERS - 1)
        #print(self.next_city)

用于计算该蚂蚁走过的总的距离。

    def calculate_pass_distance(self):
        total_distance = 0

        for i in range(1, len(self.path), 1):
            start = self.path[i - 1]
            end = self.path[i]
            total_distance += arr_distance[start][end]

        start = self.path[len(self.path) - 1]
        end = self.path[0]          #回家了再计算一次噢~
        total_distance += arr_distance[start][end]

        self.distance = total_distance

        pass

 def is_passed(self, i, j):

        for index in range(1, CITY_NUMBERS, 1):
            start = self.path[i - 1]
            end = self.path[i]

            if i == start and j == end:         #经过不论先后顺序~
                return True
            elif i == end and j == start:
                return True

        start = self.path[len(self.path) - 1]
        end = self.path[0]                      #最后一个回路

        if i == start and j == end:             #同理：经过不论先后顺序~
            return True
        elif i == end and j == start:
            return True

        return False

完整代码如下：

# -*-coding:UTF-8 -*-
import random
import sys
#reload(sys)
from scipy.interpolate import make_interp_spline
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import pylab
import matplotlib as mpl
CITY_NUMBERS = 31       #城市数量
ANT_NUMBERS = 20        #蚂蚁数量
ALPHA = 1               #信息素启发因子
BETA = 5                #启发函数因子
RHO = 0.10               #信息素挥发速度
Q = 10                  #常数Q
ITERATION_NUMBERS = 75  #迭代次数

#--------------------------------ANT 类------------------------------#
class Ant():
    __slots__ = "ID", "path", "distance","staying_place", "next_city"

    def __init__(self, id):
        self.ID = id
        self.path = []
        self.distance = 0
        self.staying_place = -1
        self.next_city = -1
        pass

    def select_city(self):

        #
        if self.staying_place == -1:##刚刚开始！
            self.next_city = random.randint(0, CITY_NUMBERS - 1)
            #self.next_city = 0          #固定起点， 测试性能变化！！！！！！

            return

        select_city_probability = [0 for i in range(0, CITY_NUMBERS, 1)]
        total_probability = 0

        for i in range(0, CITY_NUMBERS, 1):
            if i not in self.path:
                select_city_probability[i] = pow(arr_pheromone[self.staying_place][i], ALPHA) *\
                                            pow(1 / arr_distance[self.staying_place][i], BETA)
                # 注意可能会存在数组越界的问题，可以考虑用 TRY 包裹来解决
                total_probability += select_city_probability[i]

        if total_probability > 0:
            temp_probability = random.uniform(0, total_probability)      #生成 0 - 1 的随机数~
            #temp_prob = random.uniform(0.0, total_prob)

            #self.roulette()
            for i in range(0, CITY_NUMBERS, 1):
                if i not in self.path:
                    temp_probability -= select_city_probability[i]
                    if temp_probability < 0:
                        self.next_city = i
                        break                   #找到目标城市，跳出

        if self.next_city == -1:
            self.next_city = random.randint(0, CITY_NUMBERS - 1)
            while self.next_city in self.path:
                self.next_city = random.randint(0, CITY_NUMBERS - 1)
        #print(self.next_city)

    def calculate_pass_distance(self):
        total_distance = 0

        for i in range(1, len(self.path), 1):
            start = self.path[i - 1]
            end = self.path[i]
            total_distance += arr_distance[start][end]

        start = self.path[len(self.path) - 1]
        end = self.path[0]          #回家了再计算一次噢~
        total_distance += arr_distance[start][end]

        self.distance = total_distance

        pass


    def roulette(self):
        #
        pass

    def is_passed(self, i, j):

        for index in range(1, CITY_NUMBERS, 1):
            start = self.path[i - 1]
            end = self.path[i]

            if i == start and j == end:         #经过不论先后顺序~
                return True
            elif i == end and j == start:
                return True

        start = self.path[len(self.path) - 1]
        end = self.path[0]                      #最后一个回路

        if i == start and j == end:             #同理：经过不论先后顺序~
            return True
        elif i == end and j == start:
            return True

        return False

    def reset(self):
        #经过了一轮的努力，蚂蚁要休息了
        self.path = []
        self.distance = 0
        self.staying_place = -1
        self.next_city = -1

        return

    def make_move(self):
        if self.next_city != -1:
            self.staying_place = self.next_city
            self.path.append(self.next_city)
            #self.distance +=
            self.next_city = -1

        return

    def do_circle(self):
        for i in range(0, CITY_NUMBERS, 1):
            self.select_city()
            #self.path.append(self.next_city)
            self.make_move()
            #print(self.path)
        self.calculate_pass_distance()
#-----------------------------------------------------------------#


def update_pheromone(arr_ant):
    #
    for i in range(0, CITY_NUMBERS, 1):
        for j in range(0, CITY_NUMBERS, 1):
            if i == j:
                pass
            else:
                temp_pheromone = 0
                for ant in arr_ant:
                    if ant.is_passed(i, j):         #如果蚂蚁有走过这条路的话
                        temp_pheromone += 1 / ant.distance

                arr_pheromone[i][j] = (1 - RHO) * arr_pheromone[i][j] + temp_pheromone
                # 与计算路径同理， 也会存在重复计算的问题，但暂不理会
    return

#
# def reset():
#     #
#     pass




def get_optimal_solution():
    #可以考虑使用模拟退火来求最优而不是设置一个迭代次数
    pass



def calculate_distance():

    for i in range(0, CITY_NUMBERS, 1):
        for j in range(0, CITY_NUMBERS, 1):
            if i == j:
                arr_distance[i][j] = 10000000       #0?
            else:
                arr_distance[i][j] = pow(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2), 0.5)
                #arr_distance[i][j] = pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2)
                #暂时不考虑去除重复计算的问题
                #取根号可能没有必要，其具体影响待测试     no!????

    return


def calculate_shortest_length():
    #通过贪心算法来计算最短路径以在程序开始时对信息素数组进行初始化
    passed = []
    start = 0
    total_distance = 0
    passed.append(start)
    while True:
        #start = 0
        if len(passed) == CITY_NUMBERS:         #已全部遍历 进行一个跳的出
            break
        temp_distance = 1000000
        temp_j = 0
        for j in range(0, CITY_NUMBERS, 1):
            if j != start:                  #不计算自己（虽然可能影响不大
                if temp_distance > arr_distance[start][j]:
                    temp_j = j
                    temp_distance = arr_distance[start][j]

        total_distance += temp_distance
        passed.append(temp_j)

        start = temp_j

    return total_distance


def init():
    # 一切都才刚刚开始~
    for i in range(0, ANT_NUMBERS, 1):
        arr_ant.append(Ant(i))              #蚂蚁数组的初始化

    calculate_distance()                                #距离数组的初始化
    shortest_length = calculate_shortest_length()       #初始的信息素都一样
    initial_pheromone = ANT_NUMBERS / shortest_length
    for i in range(0, CITY_NUMBERS, 1):
        for j in range(0, CITY_NUMBERS, 1):
            if i == j:
                pass
            else:
                arr_pheromone[i][j] = initial_pheromone

    """
    ALPHA = 
    BETA = 
    """
    pass


if __name__ == "__main__":
    x = [1304, 3639, 4177, 3712, 3488, 3326, 3238, 4196, 4312, 4386, 3007, 2562, 2788, 2381, 1332, 3715, 3918, 4061,
         3780, 3676, 4029, 4263, 3429, 3507, 3394, 3439, 2935, 3140, 2545, 2778, 2370]

    y = [2312, 1315, 2244, 1399, 1535, 1556, 1229, 1004, 790, 570, 1970, 1756, 1491, 1676, 695, 1678, 2179, 2370, 2212,
         2578, 2838, 2931, 1908, 2367, 2643, 3201, 3240, 3550, 2357, 2826, 2975]


    arr_pheromone = [[0 for i in range(0, CITY_NUMBERS, 1)] for j in range(0, CITY_NUMBERS, 1)]
    arr_distance = [[0 for i in range(0, CITY_NUMBERS, 1)] for j in range(0, CITY_NUMBERS, 1)]
    #arr_city_visited = [[] for i in range(0, ANT_NUMBERS, 1)]
    arr_ant = []


    init()
    arr_shortest_length = []
    arr_avg_length = []
    shortest_length = 0
    for i in range(0, ITERATION_NUMBERS, 1):
        shortest_length = 0
        total_length = 0
        temp_length = 100000000000
        for ant in arr_ant:
            ant.do_circle()
            print(ant.path)
            if temp_length > ant.distance:
                temp_length = ant.distance
            total_length += ant.distance

        shortest_length += temp_length
        update_pheromone(arr_ant)
        arr_shortest_length.append(shortest_length)
        arr_avg_length.append(total_length / ANT_NUMBERS)
        for ant in arr_ant:
            ant.reset()

    np_array1 = np.array(arr_shortest_length)
    np_array2 = np.array(arr_avg_length)
    #plt.plot([1], 1.11111111)      #报错??????????/
    #plt.plot([1], np.array([1]))
    plt.subplot(2, 2, 1)
    plt.plot([i for i in range(1, ITERATION_NUMBERS + 1, 1)], np_array1)
    plt.title("shortest length")
    plt.xlabel("Iteration times")
    plt.ylabel("Length /m")

    plt.subplot(2, 2, 2)
    plt.plot([i for i in range(1, ITERATION_NUMBERS + 1, 1)], np_array2)
    plt.title("average length")
    plt.xlabel("Iteration times")
    plt.ylabel("Length /m")

    # plt.subplot(2, 2, 1)
    # x = np.array([i for i in range(1, ITERATION_NUMBERS + 1, 1)])
    # y = np.array(arr_shortest_length)
    # model = make_interp_spline(x, y)
    # xs = np.linspace(1, ITERATION_NUMBERS + 1, 500)
    # ys = model(xs)
    # plt.plot(xs, ys)
    # plt.title("Smooth")
    # plt.xlabel("X")
    # plt.ylabel("Y")

    plt.subplot(2, 2, 3)      #趋势图
    x = np.array([i for i in range(1, ITERATION_NUMBERS + 1, 1)])
    y = np.array(arr_shortest_length)
    mpl.pylab.plot(x, y, 'ko')
    parameter = np.polyfit(x, y, 2)
    f = np.poly1d(parameter)
    mpl.pylab.plot(x, f(x), "r--")
    plt.xlabel("Ieration times")
    plt.ylabel("Length /m")
    plt.title("Smooth average length")

    plt.subplot(2, 2, 4)  # 趋势图
    x = np.array([i for i in range(1, ITERATION_NUMBERS + 1, 1)])
    y = np.array(arr_avg_length)
    mpl.pylab.plot(x, y, 'ko')
    parameter = np.polyfit(x, y, 2)
    f = np.poly1d(parameter)
    mpl.pylab.plot(x, f(x), "r--")
    plt.xlabel("Ieration times")
    plt.ylabel("Length /m")
    plt.title("Smooth average length")


    plt.suptitle("ANT ALGORITHM")
    plt.show()


    print(np_array1)

实验结果

总结

通过这次实验，使我对蚁群算法有了一个简单的了解，并且对信息素更新模型、参数设置等问题有了更加深入的了解，收获颇丰。