【人工智能】蚁群算法(密恐勿入)（三）

2023-05-24 121

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 假设有一位邮递员，他从初始城市（任意一城市）出发，途径所有城市并回到初始城市，利用蚁群算法求得最短路径

4. TSP问题—蚁群算法实现（python版本）

问题背景：

假设有一位邮递员，他从初始城市（任意一城市）出发，途径所有城市并回到初始城市，利用蚁群算法求得最短路径

数据：

以下是10个城市的坐标数据：

城市
X坐标
Y坐标

A
5
10

B
6
15

C
10
15

D
14
14

E
20
10

F
16
5

G
8
5

H
4
8

I
8
12

J
12
12

准备阶段

首先，将数据存储在Graph中，并且计算各个城市之间的距离distances。
```python
class Graph(object):
def init(self, city_location, pheromone=1.0, alpha=1.0, beta=1.0):

 self.city_location = city_location
 self.n = len(city_location)
 # phernmone矩阵
 self.pheromone = [[pheromone for _ in range(self.n)] for _ in range(self.n)]
 self.alpha = alpha
 self.beta = beta
 # 城市之间的距离矩阵
 self.distances = self._generate_distances()

欧式距离作为图的权重

def _generate_distances(self):

 distances = []
 # 遍历行
 #   遍历列
 #       如果行值=列，比如（1,1）(2,2)，这样就是相同的城市，则距离为零
 #       如果行值<列,比如（1，2）（2，3）,这样就是不同的城市，距离按欧拉距离公式来算
 #       否则，将矩阵的斜对称位置上的距离来补（原因：城市之间距离矩阵是一个distances[i][j] = distances[j][i]特点的矩阵,这样的目的就是减少至少一半的计算）
 for index_i, _i in enumerate(self.city_location):
     row = []
     for index_j, _j in enumerate(self.city_location):
         if _i == _j:
             row.append(0)
         elif _i < _j:
             x1, y1 = self.city_location[str(_i)]
             x2, y2 = self.city_location[str(_j)]
             row.append(np.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2))
         else:
             row.append(distances[index_j][index_i])
     distances.append(row)
 return distances

- 属性
    - `city_location`: 城市位置的字典
    - `n`: 城市的数量
    - `pheromone`: 蚂蚁留下的信息素的矩阵
    - `alpha`: 信息素强度的影响因子
    - `beta`: 启发式因子的影响因子
    - `distances`: 城市之间距离的矩阵
- 方法
    - `__init__(self, city_location, pheromone=1.0, alpha=1.0, beta=1.0)`: 对象初始化，计算出城市之间的距离矩阵
    - `_generate_distances(self)`: 计算城市之间的距离矩阵


 2. 那么，我们将各项能力赋予蚂蚁

    ```python
    class Ant(object):
        def __init__(self, graph, start_city):
            self.graph = graph
            self.start_city = start_city
            self.curr_city = start_city
            self.visited = [False for _ in range(graph.n)]
            self.visited[start_city] = True
            self.tour_length = 0
            self.tour = [start_city]

        def choose_next_city(self):
            # calculate probabilities of all cities
            probs = []
            total_prob = 0
            for i in range(self.graph.n):
                if not self.visited[i]:
                    prob = self.graph.pheromone[self.curr_city][i] ** self.graph.alpha * \\
                           (1.0 / self.graph.distances[self.curr_city][i]) ** self.graph.beta
                    probs.append((i, prob))
                    total_prob += prob
            # select the next city randomly based on the probabilities
            r = random.uniform(0, total_prob)
            upto = 0
            for i, prob in probs:
                if upto + prob >= r:
                    self.curr_city = i
                    self.visited[i] = True
                    self.tour.append(i)
                    self.tour_length += self.graph.distances[self.tour[-2]][i]
                    return
                upto += prob

        def tour_complete(self):
            return len(self.tour) == self.graph.n

- 属性：
    - `graph`: 图对象，表示要在其上运行蚁群算法的图
    - `start_city`: 整数，表示蚂蚁的起始城市
    - `curr_city`: 整数，表示蚂蚁当前所在城市
    - `visited`: 布尔列表，表示城市是否已被访问
    - `tour_length`: 浮点数，表示蚂蚁的路径长度
    - `tour`: 整数列表，表示蚂蚁的路径
- 方法：
    - `choose_next_city()`: 计算所有城市的概率，根据概率随机选择下一个城市
    - `tour_complete()`: 检查蚂蚁是否已经遍历完所有城市

算法构造

通过上面的准备，我们现阶段有了蚂蚁和城市图，那么，我们来规划一下算法的流程。把：

初始化蚂蚁和信息素矩阵。
蚂蚁根据信息素浓度和启发函数选择下一个节点。
蚂蚁在路径上释放信息素。
重复步骤2和3，直到所有蚂蚁都找到了解。
评估每条路径的适应度，并更新信息素矩阵。
重复步骤2到5，直到达到预设的迭代次数或者找到最优解。

这里要考虑选择哪一种更新策略、更新时机：

静态规则（这里我选的这个）
在每个迭代周期结束后进行更新，即在所有蚂蚁完成当前迭代周期后，根据其路径长度和信息素更新信息素浓度。

def ant_colony(graph, num_ants, num_iterations, evaporation_rate=0.5, q=500):
    shortest_tour = None  # 最短路径
    shortest_tour_length = float('inf')  # 最短路径长度
    for i in range(num_iterations):
        ants = [Ant(graph, random.randint(0, graph.n - 1)) for _ in range(num_ants)]  # 随机生成蚂蚁
        for ant in ants:
            while not ant.tour_complete():
                ant.choose_next_city()  # 选择下一个城市
            ant.tour_length += graph.distances[ant.tour[-1]][ant.start_city]  # 计算路径长度
            if ant.tour_length < shortest_tour_length:
                shortest_tour_length = ant.tour_length
                shortest_tour = ant.tour[:]
        for i in range(graph.n):
            for j in range(graph.n):
                if i != j:
                    graph.pheromone[i][j] *= (1 - evaporation_rate)  # 更新挥发信息素
                for ant in ants:
                    if (i, j) in zip(ant.tour, ant.tour[1:]):
                        graph.pheromone[i][j] += q / ant.tour_length  # 更新释放信息素
        return shortest_tour, shortest_tour_length

注释：
- shortest_tour：最短路径，初始化为 None。
- shortest_tour_length：最短路径长度，初始化为正无穷。
- ants：蚂蚁集合，随机生成。
- ant：蚂蚁，从 graph 中随机选择一个起始城市开始走。
- choose_next_city：选择下一个城市。
- tour_length：路径长度，初始化为 0。
- pheromone：信息素。
- evaporation_rate：信息素挥发率。
- q：信息素强度。
- zip(ant.tour, ant.tour[1:])：将 ant.tour 中的相邻两个元素组成一个二元组 (i, j)，便于后续计算。
- 更新信息素时，需要更新挥发信息素和释放信息素。挥发信息素是指信息素随时间的推移而逐渐消失；释放信息素是指蚂蚁在路径上释放信息素，增强这条路径的吸引力。
- 返回最短路径和最短路径长度。
  测试：

将数据和流程带入：

city_location = {
   
   
    'A': (5, 10),
    'B': (6, 15),
    'C': (10, 15),
    'D': (14, 14),
    'E': (20, 10),
    'F': (16, 5),
    'G': (8, 5),
    'H': (4, 8),
    'I': (8, 12),
    'J': (12, 12)
}

# 创建Graph对象
g = Graph(city_location)
shortest_tour, shortest_tour_length = ant_colony(graph=g, num_ants=500, num_iterations=1000)
print(shortest_tour,shortest_tour_length)

# 城市索引
city_index = {
   
   city: i for i, city in enumerate(sorted(city_location))}
# 城市索引
city_index = {
   
   city: i for i, city in enumerate(sorted(city_location))}
# 城市名称列表
shortest_tour = [list(city_index.keys())[i] for i in shortest_tour]
# 打印结果
print(shortest_tour)
g.plot_path(shortest_tour)

参考代码：

import math
import random

class Graph(object):
    def __init__(self, n, pheromone=1.0, alpha=1.0, beta=1.0):
        self.n = n
        self.pheromone = [[pheromone for _ in range(n)] for _ in range(n)]
        self.alpha = alpha
        self.beta = beta
        self.distances = self._generate_distances()

    def _generate_distances(self):
        # randomly generate distances between cities
        distances = []
        for i in range(self.n):
            row = []
            for j in range(self.n):
                if i == j:
                    row.append(0)
                elif j > i:
                    row.append(random.uniform(1, 10))
                else:
                    row.append(distances[j][i])
            distances.append(row)
        return distances

class Ant(object):
    def __init__(self, graph, start_city):
        self.graph = graph
        self.start_city = start_city
        self.curr_city = start_city
        self.visited = [False for _ in range(graph.n)]
        self.visited[start_city] = True
        self.tour_length = 0
        self.tour = [start_city]

    def choose_next_city(self):
        # calculate probabilities of all cities
        probs = []
        total_prob = 0
        for i in range(self.graph.n):
            if not self.visited[i]:
                prob = self.graph.pheromone[self.curr_city][i] ** self.graph.alpha * \\
                       (1.0 / self.graph.distances[self.curr_city][i]) ** self.graph.beta
                probs.append((i, prob))
                total_prob += prob
        # select the next city randomly based on the probabilities
        r = random.uniform(0, total_prob)
        upto = 0
        for i, prob in probs:
            if upto + prob >= r:
                self.curr_city = i
                self.visited[i] = True
                self.tour.append(i)
                self.tour_length += self.graph.distances[self.tour[-2]][i]
                return
            upto += prob

    def tour_complete(self):
        return len(self.tour) == self.graph.n

def ant_colony(graph, num_ants, num_iterations, evaporation_rate=0.5, q=500):
    shortest_tour = None
    shortest_tour_length = float('inf')
    for i in range(num_iterations):
        # initialize ants
        ants = [Ant(graph, random.randint(0, graph.n-1)) for _ in range(num_ants)]
        # have each ant choose a path
        for ant in ants:
            while not ant.tour_complete():
                ant.choose_next_city()
            ant.tour_length += graph.distances[ant.tour[-1]][ant.start_city]
            # check if this ant found a shorter tour
            if ant.tour_length < shortest_tour_length:
                shortest_tour_length = ant.tour_length
                shortest_tour = ant.tour[:]
        # update pheromones
        for i in range(graph.n):
            for j in range(graph.n):
                if i != j:
                    graph.pheromone[i][j] *= (1 - evaporation_rate)
                    for ant in ants:
                        if (i, j) in zip(ant.tour, ant.tour[1:]):
                            graph.pheromone[i][j] += q / ant.tour_length
    return shortest_tour, shortest_tour_length

# generate a 11-city TSP problem and solve it using the ant colony algorithm
graph = Graph(11)
shortest_tour, shortest_tour_length = ant_colony(graph, num_ants=10, num_iterations=50)

# print the shortest tour and its length
print("Shortest tour:", shortest_tour)
print("Shortest tour length:", shortest_tour_length)

写在最后，第二次上热门，流量还可以，我也是认真对待了这篇文章，写这篇博客的原因就是顺便把老师的作业也写了，作业你们也看到了，就是用代码实现蚁群算法去解决TSP问题，对于蚁群算法，我也是第一次去学习，并不是你们所认识的“佬”，说是博客，其实更像一篇记录我学习过程的日记，对于人工智能，说实话，挺有意思的，但考虑到本身实力情况，只能当作暂时的兴趣，大概这门课结课的时候，人工智能系列估计就不更了，唉毕竟是兴趣，不能吃饭，我的实力也不可能达到那些“佬”级别，下一篇估计也快了，应该是神经网络（泛泛而谈），有像了解的可以期待一下，我尽量把正确的，易懂的，可能老师考虑不到的方面给你们讲清楚，现学现卖的优势就是能将难点给它点出来。