蚁群算法：

概要：

主要过程：

  1. 状态转移

  2. 信息素更新

主要公式：

  1. 状态转移阶段：

为了避免残留信息素过多而淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后，要对残留信息进行更新处理。

由此，t+n时刻在路径(i,j)上的信息量可按如下规则进行调整：

逻辑模型：

信息素更新模型：

pic

Python代码实现：

蚁群类：

蚁群类：初始化 init(self,ID)

1
2
3
4
def __init__(self, ID):

    self.ID = ID  # ID
    self.__clean_data()  # 调用函数初始化所有信息 随机初始化出生点

蚁群类：初始化数据信息__clean_data()

1
2
3
4
5
6
7
8
9
10
11
12
13
# 初始数据
def __clean_data(self):
    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 = random.randint(0, city_num - 1)  # 随机初始出生点
    self.current_city = city_index
    self.path.append(city_index)  # 添加初始城市到蚂蚁路径当中
    self.open_table_city[city_index] = False  # 记录初始城市已经被纳入 禁忌表True=》false
    self.move_count = 1  # 移动次数+1

蚁群类：选择下一个城市（）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 选择下一个城市（input self output= nextcity）
def __choice_next_city(self):

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

    # 获取去下一个城市的概率
    for i in range(city_num):
        if self.open_table_city[i]: # 查询禁忌表
            try:    # 异常处理 try - except
                # 计算概率：与信息素浓度成正比，与距离成反比
                # select_citys_prob[i] ：对应算式中的分子
                select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) * pow(
                    (1.0 / distance_graph[self.current_city][i]), BETA)
                # total_prob 分母
                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 total_prob > 0.0:
        temp_prob = random.uniform(0.0, total_prob) # 在 0~total_prob 生成一个随机数（浮点）
        for i in range(city_num):
            if self.open_table_city[i]: # 如果城市i在禁忌表中
                # 采用轮次相减法选择城市
                temp_prob -= select_citys_prob[i]
                if temp_prob < 0.0: # 选择城市i 退出for循环
                    next_city = i   # 下一个城市（next_city）： i
                    break

    # 未从概率产生，顺序选择一个未访问城市(应该不会出现此情况)
    if (next_city == -1):
        next_city = random.randint(0, city_num - 1)
        while ((self.open_table_city[next_city]) == False):  # if==False,说明已经遍历过了
            next_city = random.randint(0, city_num - 1)

    # 返回下一个城市序号
    return next_city

蚁群类：计算路径距离

1
2
3
4
5
6
7
8
9
10
11
12
def __cal_total_distance(self):

    temp_distance = float(0.0) #用于计算和

    for i in range(1, city_num):
        start, end = self.path[i], self.path[i - 1]
        temp_distance += distance_graph[start][end]

    # 回路
    end = self.path[0]
    temp_distance += distance_graph[start][end]
    self.total_distance = temp_distance # 保存最终值

蚁群类： 移动操作

1
2
3
4
5
6
7
def __move(self, 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    # 移动次数+1

蚁群类：主函数：迭代一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 主函数：迭代一次
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()