遗传算法与蚁群算法简介课件

路由问题 （RP）
其他问题
Bullnheimer,Hartl,Strauss Gambardella ,Taillard,Agazzi Schoonderwoerd, Bonabeau ,van der put et al White,Pagurek,Oppacher Di Caro,Dorigo Subramanian,Druschel,Chen Heusse et al Navarro Varela,Sinclair 李生红，刘泽民，周正 张素兵，刘泽民 丁建立、陈增强、袁著祉
蚂蚁圈模型调整方法相似；ij(t1)•ij(t) iej
(3)为了避免算法过早收敛非全局最优解，将各路经的信息素浓度
限制在于[min,max] 之间，即 minij ma。x 超出这个范围的值
被强制设为 min 或者 max 。
从实验结果看，MMAS算法在防止算法过早停滞及有效性方面对 AS算法有较大的改进。
Colorni, Dorigo,Maniezzo Stizle Bauer et al DenBesten, Dorigo, Maniezzo 陈义宝、周济等
AS-JSP AS-FSP ACS-SMTTP ACS-SMTWTP 工件排序蚁群算法
1994 1997 1999 1999 2002
表2 蚂蚁算法及其应用（续）
MMAS(Max-Min Ant System)模型
为避免停滞和陷入局部，Stutzle和Hoos 提出了MAX-MIN Ant System（简称MMAS）模型，它对AS进行了三点改进:
(1)为了更加充分地寻优，各路径信息素初值设为最大值 max； (2)一圈中只有最短路径的蚂蚁才进行信息素修改增加，这与AS
V
qq0 qq0

参数优化方法
采用智能优化算法，如遗传算法、粒子群算法等，对算法参数进行 优化，以寻找最优参数组合，提高算法性能。
04
蚁群算法的实现流程
问题定义与参数设定
问题定义
明确待求解的问题，将其抽象为优化 问题，并确定问题的目标函数和约束 条件。
参数设定
根据问题的特性，设定蚁群算法的参 数，如蚂蚁数量、信息素挥发速度、 信息素更新方式等。
动态调整种群规模
根据搜索进程的需要，动态调整参与搜索的蚁群规模，以保持种群 的多样性和搜索的广泛性。
自适应调整参数
参数自适应调整策略
根据搜索进程中的反馈信息，动态调整算法参数，如信息素挥发速 度、蚂蚁数量、移动概率等。
参数动态调整规则
制定参数调整规则，如基于性能指标的增量调整、基于时间序列的 周期性调整等，以保持算法性能的稳定性和持续性。
06
蚁群算法的优缺点分析
优点
高效性
鲁棒性
蚁群算法在解决组合优化问题上表现出高 效性，尤其在处理大规模问题时。
蚁群算法对噪声和异常不敏感，具有较强 的鲁棒性。
并行性
全局搜索
蚁群算法具有天然的并行性，可以充分利 用多核处理器或分布式计算资源来提高求 解速度。
蚁群算法采用正反馈机制，能够实现从局 部最优到全局最优的有效搜索。
强化学习
将蚁群算法与强化学习相结合，利用强化学习中的奖励机制指导 蚁群搜索，提高算法的探索和利用能力。
THANKS
感谢观看
蚂蚁在移动过程中会不断释放新 的信息素，更新路径上的信息素 浓度。
蚂蚁在更新信息素时，会根据路 径上的信息素浓度和自身的状态 来决定释放的信息素增量。
搜索策略与最优解的形成
搜索策略

5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会 随机的选择另一个方向，并且有信息素指引的话，它会按 照觅食的规则行为。
6、播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候 撒发的信息素最多，并随着它走远的距离，播撒的信息素 越来越少。根据这几条规则，蚂蚁之间并没有直接的关系， 但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带， 实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找 到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是 向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就 会感觉到信息素的存在，进而根据信息素的指引找到了食 物。
3、觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物， 如果有就直接过去。否则看是否有信息素，并且比较在能 感知的范围内哪一点的信息素最多，这样，它就朝信息素 多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并 不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样， 只不过它对窝的信息素做出反应，而对食物信息素没反应。
蚁群算法的分析
1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个 参数为速度半径（一般是3），那么它能观察到的范围就是 3*3个方格世界，并且能移动的距离也在这个范围之内。
2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍 物，有别的蚂蚁，还有信息素，信息素有两种，一种是找 到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒 下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境 信息。环境以一定的速率让信息素消失。
蚁群算法的分析
4、移动规则： 每只蚂蚁都朝向信息素最多的方向移，并 且，当周围没有信息素指引的时候，蚂蚁会按照自己原来 运动的方向惯性的运动下去，并且，在运动的方向有Байду номын сангаас个 随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近 刚走过了哪些点，如果发现要走的下一点已经在最近走过 了，它就会尽量避开。

Macro Dorigo
2021/7/1
3
基本原理
Nest
Food
Obstacle
图1 蚂蚁正常行进，突然环境改变，增加了障碍物
2021/7/1
4
基本原理
Nest
Food
Obstacle
图2 蚂蚁以等同概率选择各条路径 较短路径信息素浓度高，选择该路径的蚂蚁增多
2021/7/1
5
基本原理
E
t=0
迭代次数 t_max 4784 1999 806 8950 6665 884 3650 2214 948 1802
程序运行时间 time 99.0466 123.0078 458.4601 148.2777 381.1539 499.8319 88.1896 149.1128 495.0127 134.2481
LumerE和FaietaB通过在Denurbourg的基本分 类模型中引入数据对象之间相似度的概念，提出了 LF聚类分析算法，并成功的将其应用到数据分析中。
2021/7/1
11
基于蚂蚁觅食行为和信息素的聚类分析模型
蚂蚁在觅食的过程中，能够分为搜索食物和 搬运食物两个环节。每个蚂蚁在运动过程中 都将会在其所经过的路径上留下信息素，而 且能够感知到信息素的存在及其强度，比较 倾向于向信息素强度高的方向移动，同样信 息素自身也会随着时间的流逝而挥发，显然 某一路径上经过的蚂蚁数目越多，那么其信 息素就越强，以后的蚂蚁选择该路径的可能 性就比较高，整个蚁群的行为表现出了信息 正反馈现象。
2021/7/1
Z
蚁 群 聚 类 结 果 (R=100,t=1000)
3500
3000
2500
2000

染色休X也称为个体X。
对于每一个个体X，要按照一定的规则确定出其适应度；个体 的适应度与其对应的个体表现型X的目标函数值相关联，X越 接近于目标函数的最优点，其适应度越大；反之，其适应度越 小。
遗传算法中，决策变量X组成了问题的解空间。对问题最优解 的搜索是通过对染色体X的搜索过程来进行的，从而由所有的 染色体X就组成了问题的搜索空间。
根据不同的情况，这里的等位基因可以是一组整数，也可以是 某一范围内的实数值，或者是纯粹的一个记号。
最简单的等位基因是由0和l这两个整数组成的。相应的染色体 就可表示为一个二进制符号串。
14.10.2020
11
这种编码所形成的排列形式X是个体的基因型，与它对应的x值是 个体的表现型。
通常个体的表现型和其基因型是一一对应的，但有时也允许基因 型和表现型是多对一的关系。
14.10.2020
6
14.10.2020
可行解
X R
ห้องสมุดไป่ตู้
基本空间 U
可行解集合
7
对于上述最优化问题，目标函数和约束条件种类繁多，有的是线 性的，有的是非线性的；有的是连续的，有的是离散的；有的是 单峰值的，有的是多峰值的。
随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全 精确地求出其最优解既不可能，也不现实，因而求出其近似最 优解或满意解是人们的主要着眼点之—。
14.10.2020
8
求最优解或近似最优解的方法
(1)枚举法。
枚举出可行解集合内的所有可行解，以求出精确最优解。对于连 续函数，该方法要求先对其进行离散化处理，这样就有可能产生 离散误差而永远达不到最优解。另外，当枚举空间比较大时，该 方法的求解效率比较低，有时甚至在目前最先进的计算工具上都 无法求解。

监控算法已无法改进解的性能时，停止计算 当前最好解
上述几种方法结合
2015/11/10
应用优化技术
15
适应函数
简单适应函数
目标函数的简单变形 max：fitness(x)=f(x) min： fitness(x)=M-f(x) (M>maxf(x)) 可能使算法在迭代过程中出现收敛到一些目标值近 似的不同染色体，难以区别哪个占优
f ( x) f max ——当前最优值 f ( x) f max
适应值 5.376 16.393 25.00 M 概率 5.376/(46.769+M) 16.393/(46.769+M) 25/(46.769+M) M/(46.769+M)
初始迭代时，M同第一大与第二大目标差值的倒数尽量接近， 避免早熟，后期迭代中逐步扩大差距 可以早期迭代中用简单适应函数，后期采用加速适应函数
17
适应函数
非线性加速适应函数
1 fitness( x) f max f ( x) M
x值 1/2 5/8 21/32 23/32 POP(1) 0000 0100 0101 0111 适应值 0.689 0.796 0.817 0.857 概率 0.214 0.248 0.254 0.272
2015/11/10
应用优化技术
22
交配规则
双亲单子
从常规或其他双子法中随机选一个，或优胜劣汰
显性遗传
双亲的基因中，有些具有优超关系，这些基因必将 遗传到下一代 2 在 max f ( x) x 中，在其他位不变的情况下，任何 一位的1永远比同位的0好
1101001 0000010 1101011

总结词
输出最优解和相关性能指标。
详细描述
这一步是将最优解和相关性能指标输出，以 便于对算法的性能进行分析和评估。
04
蚁群算法的性能分析
收敛性分析
收敛速度
蚁群算法在优化问题中的收敛速度取决于初始信息素分布、蚂蚁数量、迭代次数等因素 。
最优解质量
蚁群算法在某些问题上可能找到全局最优解，但在其他问题上可能只能找到近似最优解 。
VS
详细描述
这一步是生成初始解的过程，需要按照设 定的规则，将蚂蚁随机放置在解空间中， 并初始化每条路径上的信息素。
迭代优化
总结词
通过蚂蚁的移动和信息素的更新，不断优化 解的质量。
详细描述
这一步是蚁群算法的核心部分，通过模拟蚂 蚁的移动和信息素的更新机制，不断迭代优 化解的质量，最终找到最优解。
结果
多目标优化问题的蚁群算法
针对多目标优化问题，蚁群算法需要 进行相应的改进。
VS
多目标优化问题要求算法在满足多个 冲突目标的同时找到最优解。这需要 对蚁群算法进行相应的调整，以适应 多目标优化的特性。例如，可以通过 引入权重因子来平衡各个目标之间的 矛盾，或者采用非支配排序方法对解 进行分层处理，以便更好地处理多目 标优化问题。
蚁群算法的优化目标
寻找最短路径
蚁群算法的主要目标是找到起点到终 点之间的最短路径，这在实际应用中 可用于解决如旅行商问题、车辆路径 问题等优化问题。
平衡搜索与探索
蚁群算法需要在搜索和探索之间取得 平衡，以避免陷入局部最优解，提高 算法的全局搜索能力。
03
蚁群算法的实现步骤
问题建模
总结词
将实际问题抽象为蚁群算法能够解决的问题模型。
蚂蚁根据局部信息素浓度选择移动方向，倾向于选择信息素浓度较高的路径。

金融领域
在投资组合优化、风险管理等 方面应用蚁群算法。
蚁群算法的未来研究方向
算法改进
研究如何提高蚁群算法的收敛速度和搜索精 度。
混合算法
将蚁群算法与其他优化算法结合，形成更高 效的混合优化方法。
并行化与分布式实现
研究如何利用多核和分布式计算资源加速蚁 群算法。
理论分析
深入研究蚁群算法的数学性质和理论基础， 为算法改进提供理论支持。
鲁棒性
蚁群算法对初始参数设置不敏感，鲁棒性较强；而遗传算法对初始种群和交叉概率等参 数设置较为敏感。
蚁群算法与粒子群算法的比较
信息共享方式
粒子群算法中的粒子通过自身经验和 群体最佳解进行信息共享，而蚁群算 法中的蚂蚁通过信息素进行信息传递 。
优化目标
并Байду номын сангаас性
粒子群算法中的粒子之间相互独立， 并行性较强；而蚁群算法中的蚂蚁通 过信息素进行间接通信，并行性相对 较弱。
蚁群算法的出现和发展，不仅丰富了人工智能和优化算法的理论体系，也为相关领域的研究和应用提供 了重要的技术支持。
对蚁群算法的总结与评价
01
蚁群算法自提出以来，经过多 年的研究和发展，已经在理论 和应用方面取得了丰硕的成果 。
02
蚁群算法在解决复杂优化问题 方面具有独特的优势，尤其在 处理大规模、非线性、离散型 问题方面表现优异。
03
然而，蚁群算法也存在一些挑 战和限制，如参数设置、收敛 速度、局部最优解等问题，需 要进一步研究和改进。
对未来研究的建议与展望
针对蚁群算法的参数设置问题，建议深入研究蚂蚁数 量、信息素挥发速度等参数对算法性能的影响，寻求
更加有效的参数选择方法。
输标02入题

图像边缘检测
Thank you so much for your time,and have a nice day.
可选路径较少，使种群陷入局部最优。
信息素重要程度因子
蚂蚁选择以前已经走过的路可能性较大， 会使蚁群的搜索范围减小容易过早的收
容易使随机搜索性减弱。
敛,使种群陷入局部最优。
启发函数重要程度因子 虽然收敛速度加快,但是易陷入局部最优
蚁群易陷入纯粹的随机搜索，很难找到 最优解
信息素挥发因子
各路径上信息素含量差别较小，收敛速 信息素挥发较快,容易导致较优路径被排除 度降低
2.并行的算法
每只蚂蚁搜索的过程彼此独立，仅通过信 息激素进行通信。 在问题空间的多点同时开始进行独立的解 搜索，不仅增加了算法的可靠性,也使得算 法具有较强的全局搜索能力。
3
蚁群算法的基本步骤
1）初始化参数；2）构建解空间；3）更新信息素；4）判断终止与迭代。
3 蚁群算法的基本步骤
优化问题与蚂蚁寻找食物的关系
0.04
0.04
0.92 到城市1 到城市3 到城市5
3.3 更 新 信 息 素
蚂蚁访问完所有城市之后，进行信息素的更新。信息素的更新包括挥发和蚂蚁的产生，由以下 公式决定：
第 t+1 次 循 环 后 城 市 i 到 城市j上的信息素含量
信息素残留系数=1-信息素挥发因子
ij (t 1) (1 ) ij (t) ij , (0 1)
2.2 蚁 群 算 法 的 特 点
1.自组织的算法
自组织:组织力或组织指令是来自于系 统的内部。 在抽象意义上讲，自组织就是在没有外 界作用下使得系统嫡减小的过程(即是 系统从无序到有序的变化过程)。

改进算法。
在基于聚类分析的蚁群优化算法中，算 法首先利用聚类分析技术将问题空间划 分为多个子空间，然后将蚂蚁分配到不
同的子空间中进行搜索。
这种算法通过聚类分析技术将问题空间 划分为多个子空间，可以减少蚂蚁搜索
范围，提高算法的寻优效率。
基于粒子群的蚁群优化算法
基于粒子群的蚁群优化算法是 一种将粒子群优化算法与蚁群 优化算法相结合的改进算法。
THANKS
感谢观看
蚁群优化算法课件
目录
• 蚁群优化算法简介 • 蚁群优化算法的基本原理 • 蚁群优化算法的实现细节 • 蚁群优化算法的改进版本 • 蚁群优化算法的实验与分析 • 么是蚁群优化算法
蚁群优化算法是一种启发式优化算法，通过模拟 01 自然界中蚂蚁寻找食物的行为来求解优化问题。
在基于粒子群的蚁群优化算法 中，每只蚂蚁被视为一个粒子 ，每个粒子都有一个位置和一 个速度。
该算法通过粒子的位置和速度 来描述蚂蚁的状态，并利用粒 子群优化算法的优点来指导蚂 蚁的搜索行为。
05
蚁群优化算法的实验与分析
在TSP问题上的应用
总结词
高效、稳定
详细描述
蚁群优化算法在TSP问题上具有高效、稳定的性能表现。通过模拟蚂蚁觅食行为 ，该算法能够在较短的时间内寻找到一条最短路径，并且具有较好的鲁棒性。
果的质量。
02
蚁群优化算法的基本原理
蚂蚁的行为特征
01 蚂蚁具有记忆能力
蚂蚁能够记住之前走过的路径和相关的信息，如 食物的来源、路径的长度等。
02 蚂蚁具有协作能力
在寻找食物的过程中，蚂蚁之间会相互协作，通 过信息素的传递来共享信息。
03 蚂蚁具有适应性
蚂蚁能够根据环境的变化来调整自己的行为和策 略，以适应不同的环境条件。

有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另 辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐 地，更多的蚂蚁被吸引到这条较短的路上来。
最后，经过一段时间运行，就可能会出现一条最短的路径被 大多数蚂蚁重复着。
1.蚁群算法的提出
基本原理
蚁群算法是对自然界蚂蚁的寻径方式进行模似 而得出的一种仿生算法。
（1）其原理是一种正反馈机制或称增强型学习系统；它通过信息素 的不断更新达到最终收敛于最优路径上；
（2）它是一种通用型随机优化方法；但人工蚂蚁决不是对实际蚂蚁 的一种简单模拟，它融进了人类的智能；
（3）它是一种分布式的优化方法；不仅适合目前的串行计算机，而 且适合未来的并行计算机；
（4）它是一种全局优化的方法；不仅可用于求解单目标优化问题， 而且可用于求解多目标优化问题；
若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3 只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后， 两条线路上的信息素单位积累为24和6，比值为4：1。
若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD 路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。
1.蚁群算法的提出
（5）它是一种启发式算法；计算复杂性为 O(NC*m*n2)，其中NC 是 迭代次数，m 是蚂蚁数目，n 是目的节点数目。
2.蚁群பைடு நூலகம்法的特征
下面是对蚁群算法的进行过程中采用的规则进行的一些说明。 范围
蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径 （一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动 的距离也在这个范围之内。 环境
1.蚁群算法的提出
1) 标有距离的路径图 2) 在0时刻，路径上没有信息素累积，蚂蚁选择路径为任意 3) 在1时刻，路径上信息素堆积，短边信息素多与长边，所以蚂蚁更倾向于选择

《蚁群算法整理》ppt课件
目
CONTENCT
录
• 蚁群算法简介 • 蚁群算法的基本原理 • 蚁群算法的实现过程 • 蚁群算法的改进策略 • 蚁群算法的性能评价 • 蚁群算法的应用案例
01
蚁群算法简介
蚁群算法的基本概念
蚁群算法是一种模拟自然界中蚂蚁觅食行为的优化 算法，通过模拟蚂蚁的信息素传递机制来寻找最优 解。
02
蚁群算法的基本原理
信息素的挥发与更新
信息素挥发与更新是蚁群算法中一个重要的过程，它影响着蚂蚁 的移动和信息传递。
在蚁群算法中，信息素是蚂蚁之间传递的一种化学物质，用于标 识路径的优劣。信息素会随着时间的推移而挥发，同时蚂蚁在移 动过程中会释放新的信息素。挥发和更新的过程是动态的，影响 着蚂蚁对路径的选择。
要点一
总结词
信息素更新规则是蚁群算法中的重要环节，通过改进信息 素更新规则，可以提高算法的性能。
要点二
详细描述
在蚁群算法中，信息素更新规则决定了蚂蚁在移动过程中 如何更新信息素。改进信息素更新规则可以提高算法的全 局搜索能力和局部搜索能力。例如，可以采用动态调整策 略，根据蚂蚁的移动路径和状态动态调整信息素的更新量 ，或者采用自适应策略，根据问题的特性和求解结果自适 应地调整信息素更新规则，以提高算法的性能。
详细描述
在蚁群算法中，信息素挥发速度决定了信息素消散的快慢。较慢的挥发速度可以使信息素积累，有利于增强算法 的全局搜索能力；较快的挥发速度则有利于算法的局部搜索。通过调整信息素的挥发速度，可以在全局搜索和局 部搜索之间取得平衡，提高算法的效率和稳定性。
蚂蚁数量与移动规则的调整
总结词
蚂蚁数量和移动规则是蚁群算法中的重要参数，通过调整这些参数，可以改善算法的性 能。

(1)生物的所有遗传信息都包含在其染色休中，染色体决定了生 物的性状。
(2)染色体是由基因及其有规律的排列所构成的，遗传和进化过 程发生在染色体上。
(3)生物的繁殖过程是由其基因的复制过程来完成的：
(4)通过同源染色体之间的交叉或染色体的变异会产生新的物种， 使生物呈现新的性状。
(5)对环境适应性好的基因或染色体经常比适应性差的基因或染 色体有更多的机会遗传到下一代。
(2)启发式算法。
寻求一种能产生可行解的启发式规则，以找到一个最优解或近似 最优解。该方法的求解效率虽然比较高，但对每—个需要求解的 问题都必须找出其特有的启发式规则，这个启发式规则无通用性， 不适合于其他问题。
30.06.2020
9
(3)搜索算法。寻求一种搜索算法，该算法在可行解集合的一个 子集内进行搜索操作，以找到问题的最优解或近似最优解。该方 法虽然保证不了一定能够得到问题的最优解，但若适当地利用一 些启发知识，就可在近似解的质量和求解效率上达到—种较好的 平衡。
这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣
汰的规则将适应度较高的个体更多地遗传到下一代，这样最终 在群体中将会得到一个优良的个体X，它所对应的表现型X将达 到或接近于问题的最优解X*。
生物的进化过程主要是通过染色体之间的交叉和变异来完成的，
遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用 所谓的遗传算子(genetic operators)作用于群体P(t)中，进行下述遗 传操作，从而得到新一代群体P(t+1)。
遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异 等运算都是以一种概率的方式来进行的，从而增加了其搜索过 程的灵活性。
虽然这种概率特性也会使群体中产生—些适应度不高的个体，但 随着进化过程的进行，新的群体中总会更多地产生出许多优良的 个体，实践和理论都已证明了在—定条件下遗传算法总是以概率 1收敛于问题的最优解。

12
2.蚁群算法的特征
基本蚁群算法流程图（详细）
1. 在初始状态下，一群蚂蚁外出，此时没有信息素，那 么各自会随机的选择一条路径。 2. 在下一个状态，每只蚂蚁到达了不同的点，从初始点 到这些点之间留下了信息素，蚂蚁继续走，已经到达目 标的蚂蚁开始返回，与此同时，下一批蚂蚁出动，它们 都会按照各条路径上信息素的多少选择路线(selection)， 更倾向于选择信息素多的路径走（当然也有随机性）。 3. 又到了再下一个状态，刚刚没有蚂蚁经过的路线上的 信息素不同程度的挥发掉了(evaporation)，而刚刚经过 了蚂蚁的路线信息素增强(reinforcement)。然后又出动 一批蚂蚁，重复第2个步骤。 每个状态到下一个状态的变化称为一次迭代，在迭代多 次过后，就会有某一条路径上的信息素明显多于其它路 径，这通常就是一条最优路径。
蚂蚁在运动过程中，能够在它所经过的路径 上留下一种称之为外激素(pheromone)的物质进 行信息传递，而且蚂蚁在运动过程中能够感知这 种物质，并以此指导自己的运动方向，因此由大 量蚂蚁组成的蚁群集体行为便表现出一种信息正 反馈现象：某一路径上走过的蚂蚁越多，则后来 者选择该路径的概率就越大。
4
1.蚁群算法的提出
ACO），又称蚂蚁算法——一种用来在图中 寻找优化路径的机率型算法。
它由Marco Dorigo于1992年在他的博士 论文“Ant system: optimization by a colony of cooperating agents”中提出，其 灵感来源于蚂蚁在寻找食物过程中发现路径的 行为。最早用于解决著名的旅行商问题(TSP , traveling salesman problem)。
式中，Q表示蚂蚁循环一周，且在一定程度上影响算法收敛速度的信息 素总量；Lk表示本次循环中，蚂蚁k所走路段的长度。

(2)启发式算法。
寻求一种能产生可行解的启发式规则，以找到一个最优解或近似 最优解。该方法的求解效率虽然比较高，但对每—个需要求解的 问题都必须找出其特有的启发式规则，这个启发式规则无通用性， 不适合于其他问题。
21.12.2020
9
(3)搜索算法。寻求一种搜索算法，该算法在可行解集合的一个 子集内进行搜索操作，以找到问题的最优解或近似最优解。该方 法虽然保证不了一定能够得到问题的最优解，但若适当地利用一 些启发知识，就可在近似解的质量和求解效率上达到—种较好的 平衡。
21.12.2020
4
遗传算法是模拟生物在自然环境力的遗传和进化过程而形成的 一种自适应全局优化概率搜索算法。
它最早由美国密执安大学的Holland教授提出，起源于60年代对 自然和人工自适应系统的研究。
70年代De Jong基于遗传算法的思想在计算机上进行了大量的纯 数值函数优化计算实验。
在—系列研究工作的基础上，80年代由Goldberg进行归纳总结， 形成了遗传算法的基本框架。
21.12.2020
5
一、遗传算法概要
对于一个求函数最大值的优化问题(求函数最小值也类同)，— 般可描述为下述数学规划模型：
max
s.t .
f (X) XR RU
式中，X x1 x2 xnT为决策变量，f(X)为目标函数，后两个
式子为约束条件，U是基本空间，R是U的一个子集。
满足约束条件的解X称为可行解，集合R表示由所有满足约束条 件的解所组成的一个集合，叫做可行解集合。它们之间的关系 如图所示。
21.12.2020
16
三、遗传算法的特点
(1)遗传算法以决策变量的编码作为运算对象。
传统的优化算法往往直接利用决策变量的实际值本身来进行优 化计算，但遗传算法不是直接以决策变量的值，而是以决策变 量的某种形式的编码为运算对象。