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

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 经典优化算法 | 蚁群算法解析

蚁群算法基本思想


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

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

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

蚁群算法数学模型


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

对于TSP问题,为不失一般性,设整个蚂蚁群体中蚂蚁的数量为m,城市的数量为n,城市i与城市j之间的距离为 (i,j=1,2,…,n),t时刻城市i与城市j连接路径上的信息素浓度为(t)。初始时刻,蚂蚁被放置在不同的城市里,且各城市间连接路径上的信息素浓度相同,不妨设(0)=(0)。然后蚂蚁将按一定概率选择线路,不妨设为t时刻蚂蚁k从城市i转移到城市j的概率。我们知道,“蚂蚁TSP”策略会受到两方面的左右,首先是访问某城市的期望,另外便是其他蚂蚁释放的信息素浓度,所以定义:

image.png

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

image.png

蚁群算法流程


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

  • 步骤1:对相关参数进行初始化,包括蚁初始化群规模、信息素因子、启发函数因子、信息素、挥发因子、信息素常数、最大迭代次数等,以及将数据读人程序,并对数据进行基本的处理,如将城市的坐标位置,转为城市间的矩阵。
  • 步骤2:随机将蚂蚁放于不同的出发点,对每个蚂蚁计算其下一个访问城市,直至所更新信息素表有蚂蚁访问完所有城市。
  • 步骤3:计算各个蚂蚁经过的路径长度,记录当前迭代次数中的最优解,同时对各个城市连接路径上的信息素浓度进行更新。
  • 步骤4:判断是否达到最大迭代次数,若否,则返回步骤2,否则终止程序。
  • 步骤5:输出程序结果,并根据需要输出程序寻优过程中的相关指标,如运行时间、收敛迭代次数等。

cce4ff0c987f070c63ad82f88cb30501.png

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

输出:

8d2f272bd010896583eb779c0359084e.png

88d418f60d01d34d4244b8bb0ba2f041.png

参考文献


[1]https://www.cnblogs.com/xxhbdk/p/9177423.html

[2]《matlab在数学建模中的应用》

相关文章
|
10天前
|
存储 算法 安全
.NET 平台 SM2 国密算法 License 证书生成深度解析
授权证书文件的后缀通常取决于其编码格式和具体用途。本文档通过一个示例程序展示了如何在 .NET 平台上使用国密 SM2 算法生成和验证许可证(License)文件。该示例不仅详细演示了 SM2 国密算法的实际应用场景,还提供了关于如何高效处理大规模许可证文件生成任务的技术参考。通过对不同并发策略的性能测试,开发者可以更好地理解如何优化许可证生成流程,以满足高并发和大数据量的需求。 希望这段描述更清晰地传达了程序的功能和技术亮点。
65 13
.NET 平台 SM2 国密算法 License 证书生成深度解析
|
3天前
|
数据采集 人工智能 编解码
算法系统协同优化,vivo与港中文推出BlueLM-V-3B,手机秒变多模态AI专家
BlueLM-V-3B是由vivo与香港中文大学共同研发的多模态大型语言模型,专为移动设备优化。它通过算法和系统协同优化,实现了高效部署和快速生成速度(24.4 token/s),并在OpenCompass基准测试中取得优异成绩(66.1分)。模型小巧,语言部分含27亿参数,视觉编码器含4000万参数,适合移动设备使用。尽管如此,低端设备可能仍面临资源压力,实际应用效果需进一步验证。论文链接:https://arxiv.org/abs/2411.10640。
21 9
|
1天前
|
机器学习/深度学习 存储 算法
量子算法的设计与优化:迈向量子计算的未来
量子算法的设计与优化:迈向量子计算的未来
20 3
|
4天前
|
机器学习/深度学习 数据采集 算法
基于GA遗传优化的CNN-LSTM-SAM网络时间序列回归预测算法matlab仿真
本项目使用MATLAB 2022a实现时间序列预测算法,完整程序无水印。核心代码包含详细中文注释和操作视频。算法基于CNN-LSTM-SAM网络,融合卷积层、LSTM层与自注意力机制,适用于金融市场、气象预报等领域。通过数据归一化、种群初始化、适应度计算及参数优化等步骤,有效处理非线性时间序列,输出精准预测结果。
|
3天前
|
算法 数据安全/隐私保护 索引
基于GWO灰狼优化的多目标优化算法matlab仿真
本程序基于灰狼优化(GWO)算法实现多目标优化,适用于2个目标函数的MATLAB仿真。使用MATLAB2022A版本运行,迭代1000次后无水印输出结果。GWO通过模拟灰狼的社会层级和狩猎行为,有效搜索解空间,找到帕累托最优解集。核心步骤包括初始化狼群、更新领导者位置及适应值计算,确保高效探索多目标优化问题。该方法适用于工程、经济等领域复杂决策问题。
|
6天前
|
数据采集 机器学习/深度学习 人工智能
静态长效代理IP利用率瓶颈解析与优化路径
在信息化时代,互联网已深度融入社会各领域,HTTP动态代理IP应用广泛,但静态长效代理IP利用率未达百分百,反映出行业结构性矛盾。优质IP资源稀缺且成本高,全球IPv4地址分配殆尽,高质量IP仅占23%。同时,代理服务管理存在技术瓶颈,如IP池更新慢、质量监控缺失及多协议支持不足。智能调度系统也面临风险预判弱、负载均衡失效等问题。未来需构建分布式IP网络、引入AI智能调度并建立质量认证体系,以提升资源利用率,推动数字经济发展。
21 2
|
10天前
|
存储 算法 数据可视化
Weevil-Optimizer象鼻虫优化算法的matlab仿真实现
本项目实现了Weevil-Optimizer(象鼻虫优化算法)的MATLAB仿真,展示算法在不同适应度函数下的优化收敛曲线。程序通过智能搜索策略模拟象鼻虫觅食行为,在解空间中寻找最优解。核心代码包括排序、选择、更新操作,并绘制结果图示。测试环境为MATLAB 2022A,支持Ackley、Beale、Booth、Rastrigin和Rosenbrock函数的对比分析。 虽然Weevil-Optimizer是一个虚构的概念,但其设计思路展示了如何基于自然界生物行为模式开发优化算法。完整程序运行后无水印,提供清晰的可视化结果。
|
5天前
|
机器学习/深度学习 自然语言处理 算法
生成式 AI 大语言模型(LLMs)核心算法及源码解析:预训练篇
生成式 AI 大语言模型(LLMs)核心算法及源码解析:预训练篇
|
6天前
|
存储 算法 安全
基于 Go 语言的公司内网管理软件哈希表算法深度解析与研究
在数字化办公中,公司内网管理软件通过哈希表算法保障信息安全与高效管理。哈希表基于键值对存储和查找,如用户登录验证、设备信息管理和文件权限控制等场景,Go语言实现的哈希表能快速验证用户信息,提升管理效率,确保网络稳定运行。
18 0
|
7天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
本研究基于MATLAB 2022a,使用GRU网络对QAM调制信号进行检测。QAM是一种高效调制技术,广泛应用于现代通信系统。传统方法在复杂环境下性能下降,而GRU通过门控机制有效提取时间序列特征,实现16QAM、32QAM、64QAM、128QAM的准确检测。仿真结果显示,GRU在低SNR下表现优异,且训练速度快,参数少。核心程序包括模型预测、误检率和漏检率计算,并绘制准确率图。
80 65
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM

推荐镜像

更多