第六章群智能算法
智能优化计算
6.1 群智能
6.1.1 群智能的概念
6.1.2 群智能算法
6.2 蚁群优化算法原理
6.2.1 蚁群算法的起源
6.2.2 蚁群算法的原理分析
6.3 基本蚁群优化算法
6.3.1 蚂蚁系统的模型与实现
6.3.2 蚂蚁系统的参数设置和基本属性
6.4 改进的蚁群优化算法
6.4.1 蚂蚁系统的优点与不足
6.4.2 最优解保留策略蚂蚁系统
6.4.3 蚁群系统
6.4.4 最大－最小蚂蚁系统
6.4.5 基于排序的蚂蚁系统
6.4.6 各种蚁群优化算法的比较
智能优化计算
6.5 蚁群优化算法的应用
6.5.1 典型应用
6.5.2 医学诊断的数据挖掘
6.6 粒子群算法的基本原理
6.6.1 粒子群算法的提出
6.6.2 粒子群算法的原理描述
6.7 基本粒子群优化算法
6.7.1 基本粒子群算法描述
6.7.2 参数分析
6.7.3 与遗传算法的比较
6.8 改进粒子群优化算法
6.8.1 离散二进制PSO
6.8.2 惯性权重模型
6.8.3 收敛因子模型
6.8.4 研究现状
智能优化计算
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
6.9.2 其它应用
6.10 群智能算法的特点与不足
智能优化计算
6.1 群智能
智能优化计算
群智能（Swarm Intelligence, SI ）
人们把群居昆虫的集体行为称作“群智能”（“群体智能”、“群集智能”、“集群智能”等）
特点
个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂（智能）的行为特征。
6.1.1 群智能的概念
6.1 群智能
智能优化计算
描述
群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。
特性
指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。
6.1.2 群智能算法
6.1 群智能
智能优化计算
优点
灵活性：群体可以适应随时变化的环境；
稳健性：即使个体失败，整个群体仍能完成任务；
自我组织：活动既不受中央控制，也不受局部监管。
典型算法
蚁群算法（蚂蚁觅食）
粒子群算法（鸟群捕食）
6.1.2 群智能算法
6.2 蚁群优化算法原理
智能优化计算
蚁群的自组织行为
“双桥实验”
通过遗留在来往路径
上的信息素
（Pheromone）的挥
发性化学物质来进行
通信和协调。
6.2.1 蚁群算法的起源
6.2 蚁群优化算法原理
智能优化计算
蚁群的自组织行为
“双桥实验”
6.2.1 蚁群算法的起源
6.2 蚁群优化算法原理
智能优化计算
提出蚁群系统
1992年，意大利学者M. Dorigo在其博士论文中提出
蚂蚁系统（Ant System）。
近年来，M. Dorigo等人进一步将蚂蚁算法发展为一种通用的优化技术——蚁群优化（ant colony optimization, ACO）。
6.2.1 蚁群算法的起源
蚂蚁从A点出发，随机选择路线ABD或ACD。经过9个时间单位时：走ABD的蚂蚁到达终点，走ACD的蚂蚁刚好走到C点。
6.2 蚁群优化算法原理
智能优化计算
6.2.2 蚁群算法的原理分析
蚁巢
食物
6.2 蚁群优化算法原理
智能优化计算
经过18个时间单位时：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。
6.2.2 蚁群算法的原理分析
蚁巢
食物
最后的极限是所有的蚂蚁只选择ABD路线。（正反馈过程）
6.2 蚁群优化算法原理
智能优化计算
6.2.2 蚁群算法的原理分析
蚁巢
食物
6.3 基本蚁群优化算法
智能优化计算
解决TSP问题
在算法的初始时刻，将m只蚂蚁随机放到n座城市;
将每只蚂蚁k的禁忌表tabuk(s)的第一个元素tabuk(1)设置为它当前所在城市;
设各路径上的信息素τij(0)=C（C为一较小的常数）;
6.3.1 蚂蚁系统的模型与实现
6.3 基本蚁群优化算法
智能优化计算
解决TSP问题
每只蚂蚁根据路径上的信息素和启发式信息（两城市间距离）独立地选择下一座城市：
在时刻t，蚂蚁k从城市i转移到城市j的概率为
α、β分别表示信
息素和启发式因子
的相对重要程度。
6.3.1 蚂蚁系统的模型与实现
下一步允许的城市的集合
6.3 基本蚁群优化算法
智能优化计算
解决TSP问题
当所有蚂蚁完成一次周游后，各路径上的信息素将进行更新：
其中，ρ（0<ρ<1）表示路径上信息素的蒸发系数，Q为正常数，Lk表示第k只蚂蚁在本次周游中所走过路径的长度。
6.3.1 蚂蚁系统的模型与实现
6.3 基本蚁群优化算法
智能优化计算
算法流程
6.3.1 蚂蚁系统的模型与实现
6.3 基本蚁群优化算法
智能优化计算
初始参数
城市数30;
蚂蚁数30；
α=1;
β=5;
ρ=0.5;
最大迭代代数200;
Q=100;
6.3.1 蚂蚁系统的模型与实现6.3 基本蚁群优化算法
智能优化计算
运行结果
6.3.1 蚂蚁系统的模型与实现6.3 基本蚁群优化算法
智能优化计算
运行结果
6.3.1 蚂蚁系统的模型与实现6.3 基本蚁群优化算法
智能优化计算
运行结果
6.3.1 蚂蚁系统的模型与实现6.3 基本蚁群优化算法
智能优化计算
运行结果
6.3.1 蚂蚁系统的模型与实现6.3 基本蚁群优化算法
智能优化计算
运行结果
6.3.1 蚂蚁系统的模型与实现6.3 基本蚁群优化算法
智能优化计算
运行结果
6.3.1 蚂蚁系统的模型与实现智能优化计算
三种模型
ant-cycle：
（蚁周）
ant-quantity：
（蚁量）
ant-density:
（蚁密）
6.3 基本蚁群优化算法
6.3.1 蚂蚁系统的模型与实现智能优化计算
三种模型
在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素（局部信息），而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后（全局信息）才对信息素进行更新。
6.3 基本蚁群优化算法
6.3.1 蚂蚁系统的模型与实现
智能优化计算
三种模型的比较
模型ant-density, ant-quantity, ant-cycle的比较(M. Dorigo,1996)
6.3 基本蚁群优化算法
6.3.1 蚂蚁系统的模型与实现
智能优化计算
信息素的分布
6.3 基本蚁群优化算法
6.3.2 蚂蚁系统的参数设置和基本属性
智能优化计算
信息素的分布
蒸发系数的影响：
6.3 基本蚁群优化算法
6.3.2 蚂蚁系统的参数设置和基本属性
ρ＝0.05
ρ＝0.95
智能优化计算
参数α、β对算法性能的影响
停滞现象（Stagnation behavior）：所有蚂蚁都选择相同的路径，即系统不再搜索更好的解。原因在于较好路径上的信息素远大于其他边上的，从而使所有蚂蚁都选择该路径。
6.3 基本蚁群优化算法
6.3.2 蚂蚁系统的参数设置和基本属性
智能优化计算
参数α、β对算法性能的影响
α取较大值时，意味着在选择路径时，路径上的信息素非常重要；当α取较小值时，变成随机的贪婪算法。
6.3 基本蚁群优化算法
6.3.2 蚂蚁系统的参数设置和基本属性
智能优化计算
参数α、β对算法性能的影响
α＝0，蚂蚁之间无协同作用；α＝1，有协同作用
6.3 基本蚁群优化算法
6.3.2 蚂蚁系统的参数设置和基本属性
α＝0
α＝1
智能优化计算
蚂蚁数m对算法的影响
m≈n时，ant-cycle可以在最少迭代次数内找到最优解。
6.3 基本蚁群优化算法
6.3.2 蚂蚁系统的参数设置和基本属性
m＝15
m＝150
m＝30
智能优化计算
蚂蚁的初始分布
两种情况实验：
（1）所有蚂蚁初始时刻放在同一城市；
（2）蚂蚁分布在不同城市中。
第（2）中情况可获得较高性能。
（3）在不同城市分布时，随机分布与统一分布的差别不大。
6.3 基本蚁群优化算法
6.3.2 蚂蚁系统的参数设置和基本属性
智能优化计算
优点
较强的鲁棒性；
分布式计算；
易于与其他方法结合。
缺点
搜索时间较长；
容易出现停滞现象。
6.4 改进的蚁群优化算法
6.4.1 蚂蚁系统的优点与不足
智能优化计算
最优解保留策略（Ant System with Elitist, ASelite）
每次迭代完成后，对全局最优解更进一步地进行利用；
信息素更新策略
σ为最优蚂蚁数，Lgb为全局最优解。
6.4 改进的蚁群优化算法
6.4.2 最优解保留策略蚂蚁系统
智能优化计算
最优解保留策略（Ant System with Elitist, ASelite）
该策略能够以更快的速度获得最好解，但是如果选择的精英过多则算法会由于较早收敛于局部次优解而导致搜索的过早停滞。
6.4 改进的蚁群优化算法
6.4.2 最优解保留策略蚂蚁系统
智能优化计算
蚁群系统（Ant Colony System, ACS）的改进之处
（1）在选择下一城市时，更多地利用了当前最好解；
（2）只在全局最优解所属边上增加信息素；
（3）每次蚂蚁从城市i 转移到城市j 时，边ij上的信息素将会适当减少，从而实现一种信息素的局部调整以减少已选择过的路径再次被选择的概率。
6.4 改进的蚁群优化算法
6.4.3 蚁群系统
智能优化计算
可行解的构造
伪随机比率选择规则：
蚂蚁以概率q0（0～1间的常数）移动到最大可能的城市
q为0～1的随机数，S为一随机变量，当q> q0时，S以以下概率来选择：
6.4 改进的蚁群优化算法
6.4.3 蚁群系统
智能优化计算
局部信息素更新
使已选的边对后来的蚂蚁具有较小的影响力，从而使蚂蚁对没有选中的边有更强的探索能力。当蚂蚁从城市i转移到城市j后，边ij上的信息素更新为：
其中，τ0为常数，ξ∈(0,1)为可调参数。
6.4 改进的蚁群优化算法
6.4.3 蚁群系统
智能优化计算
全局信息素更新
只针对全局最优解进行更新：
6.4 改进的蚁群优化算法
6.4.3 蚁群系统
智能优化计算
最大－最小蚂蚁系统（max-min ant system, MMAS）的改进之处
（1）每次迭代后，只有最优解（最优蚂蚁）所属路径上的信息被更新；
（2）为了避免过早收敛，将各条路径可能的信息素限制于[τmin ,τmax]；
（3）初始时刻，各路径上信息素设置为τmax ，在算法初始时刻，ρ取较小值时算法有更好的发现较好解的能力。
6.4.4 最大－最小蚂蚁系统
智能优化计算
信息素的全局更新
使所有蚂蚁完成一次迭代后，进行信息素更新：
6.4 改进的蚁群优化算法
6.4.4 最大－最小蚂蚁系统
智能优化计算
基于排序的蚂蚁系统（rank-based version of ant system, ASrank）
每次迭代完成后，蚂蚁所经路径按从小到大的顺序排列，并对它们赋予不同权值，路径越短权值越大。全局最优解权值为w，第r个最优解的权值为max{0,w-r}。
6.4 改进的蚁群优化算法
6.4.5 基于排序的蚂蚁系统
智能优化计算
基于排序的蚂蚁系统（rank-based version of ant system, ASrank）
信息素更新：
6.4 改进的蚁群优化算法
6.4.5 基于排序的蚂蚁系统
智能优化计算
优化结果比较
对对称TSP各迭代10000次，对非对称TSP各迭代20000次：
6.4 改进的蚁群优化算法
6.4.6 各种蚁群优化算法的比较
智能优化计算
典型应用列表
6.5 蚁群优化算法的应用
6.5.1 典型应用
智能优化计算
如何应用
用蚁群算法解决数据分类（数据挖掘任务中的一种）的问题：
预先定义一组类，然后把数据系中的每一个数据根据该数据的属性，归入这些类中的一个。当数据量很大时，难以人为判别分类。
6.5 蚁群优化算法的应用
6.5.2 医学诊断的数据挖掘
智能优化计算
如何应用
分类的规则：
IF
每个term是一个三元组（属性、关系符、属性取值）
希望在一个规则中使用最少的判别语句，采用蚁群优化算法达到最优的选择。
6.5.2 医学诊断的数据挖掘
智能优化计算
例：非典型肺炎
考虑如下因素：
6.5 蚁群优化算法的应用
6.5.2 医学诊断的数据挖掘
智能优化计算
例：非典型肺炎
结构图：
一个蚂蚁从始点行走至终点，得到一条路径{0, 2, 1, 0}，其对应的规则为
IF （职业＝其他人员）AND（胸部阴影＝无）THEN （非典型肺炎）
对此路径，应给予非常差的评价。
6.5 蚁群优化算法的应用
6.5.2 医学诊断的数据挖掘
智能优化计算
蚁群算法的实现
假设a表示属性的总个数，第i个属性的取值域中可取bi个数值。一只蚂蚁的行走k步的路径可以表示为
route*k+=(y1,y2,…,ya)
yi=0表示不包含属性i。
6.5 蚁群优化算法的应用
6.5.2 医学诊断的数据挖掘
智能优化计算
评价函数
解的评价函数定义为：
Q的数值越接近1，说明对该
类的判断越准确。
TP—true positives
TN—true negatives
FP—false positives
FN—false negatives
6.5 蚁群优化算法的应用
6.5.2 医学诊断的数据挖掘
True：判断结果，正确
False：判断结果，失误
Positives：真实属性，属于
Negatives：真实属性，不属于
智能优化计算
转移概率
ηij表示每个条件项的启发式参数值（信息熵），τij(t)表示第i 个属性的第j 个取值在t 时刻的信息素。
6.5 蚁群优化算法的应用
6.5.2 医学诊断的数据挖掘
智能优化计算
信息素增加
R是当前规则中所有包含的条件项；
信息素挥发
减少没被选中的三元组的信息量。
6.5 蚁群优化算法的应用
6.5.2 医学诊断的数据挖掘
智能优化计算
结果分析
诊断准确度比较
6.5 蚁群优化算法的应用
6.5.2 医学诊断的数据挖掘
智能优化计算
结果分析
诊断规则数比较
6.5 蚁群优化算法的应用
6.5.2 医学诊断的数据挖掘
智能优化计算
由James Kenney（社会心理学博士）和Russ Eberhart（电子工程学博士，https://www.doczj.com/doc/f416345085.html,/~eberhart/ ）于1995年提出粒子群算法（Particle Swarm Optimization, PSO）
6.6 粒子群算法的基本原理
6.6.1 粒子群算法的提出
智能优化计算
源于对鸟群捕食行为的研究，是基于迭代的方法
简单易于实现，需要调整的参数相对较少
在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。6.6 粒子群算法的基本原理
6.6.1 粒子群算法的提出
智能优化计算
鸟群：
假设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。PSO算法
每个解看作一只鸟，称为“粒子(particle)”，所有的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。
6.6 粒子群算法的基本原理
6.6.2 粒子群算法的原理描述
智能优化计算
PSO算法
初始化为一群随机粒子，通过迭代找到最优。
每次迭代中，粒子通过跟踪“个体极值（pbest）”和“全局极值(gbest)”来
更新自己的位置。
6.6 粒子群算法的基本原理
6.6.2 粒子群算法的原理描述
智能优化计算
粒子速度和位置的更新
假设在D维搜索空间中，有m个粒子；
其中第i个粒子的位置为矢量
其飞翔速度也是一个矢量，记为
第i个粒子搜索到的最优位置为
整个粒子群搜索到的最优位置为
第i个粒子的位置和速度更新为：
6.7 基本粒子群优化算法
6.7.1 基本粒子群算法描述
智能优化计算
粒子速度和位置的更新
其中，w称为惯性权重，
c1和c2为两个正常数，称
为加速因子。
将vidk限制在一个最大速
度vmax内。
6.7 基本粒子群优化算法
6.7.1 基本粒子群算法描述
智能优化计算
粒子速度和位置的更新
6.7 基本粒子群优化算法
6.7.1 基本粒子群算法描述
“惯性部分”，对自身运动状态的信任
“认知部分”，对微粒本身的思考，即来源于自己经验的部分
“社会部分”，微粒间的信息共享，来源于群体中的其它优秀微粒的经验
智能优化计算
迭代过程
6.7 基本粒子群优化算法
6.7.1 基本粒子群算法描述
智能优化计算
算法流程
6.7 基本粒子群优化算法
Start
Initialize particles with random position
and velocity vectors.
For each particle’s position (xi)
evaluate fitness
If fitness(xi) better than
fitness(p) then p= xi
Loop until all particles exhaust
Set best of ps as gBest
Update particles velocity and
position
Loop until max iter
Stop: giving gBest, optimal solution.
6.7.1 基本粒子群算法描述
智能优化计算
惯性权重w
使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动。
较大的w有利于跳出局部极值，而较小的w有利于算法收敛。
6.7 基本粒子群优化算法
6.7.2 参数分析
智能优化计算
加速常数c1和c2
代表将微粒推向pbest和gbest位置的统计加速项的权重。
表示粒子的动作来源于自己经验的部分和其它粒子
经验的部分。
低的值允许粒子在被拉回之前可以在目标区域外徘
徊，而高的值则导致粒子突然冲向或越过目标区
域。
6.7 基本粒子群优化算法
6.7.2 参数分析
智能优化计算
加速常数c1和c2
将c1和c2统一为一个控制参数，υ= c1+c2
如果υ很小，微粒群运动轨迹将非常缓慢；
如果υ很大，则微粒位置变化非常快；
实验表明，当υ=4.1（通常c1=2.0，c2=2.0）时，具有很好的收敛效果。
6.7 基本粒子群优化算法
6.7.2 参数分析
智能优化计算
粒子数
一般取20～40，对较难或特定类别的问题可以取
100～200。
最大速度vmax
决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度。
终止条件
最大循环数以及最小错误要求。
6.7 基本粒子群优化算法
6.7.2 参数分析
智能优化计算
共性
（1）都属于仿生算法；
（2）都属于全局优化方法；
（3）都属于随机搜索算法；
（4）都隐含并行性；
（5）根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等；（6）对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。
6.7 基本粒子群优化算法
6.7.3 与遗传算法的比较
智能优化计算
差异
（1）PSO有记忆，所有粒子都保存较优解的知识，而GA，以前的知识随着种群的改变被改变；
（2）PSO中的粒子是一种单向共享信息机制。而GA中的染色体之间相互共享信息，使得整个种群都向最优区域移动；
（3）GA需要编码和遗传操作，而PSO没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。
6.7 基本粒子群优化算法
6.7.3 与遗传算法的比较
智能优化计算
用途
基本PSO是用来解决连续问题优化的，离散二进制PSO用来解决组合优化问题。
运动方程不同
粒子的位置只有(0,1)两种状态。速度值越大，则粒子位置取1的可能性越大，反之越小。
6.8 改进粒子群优化算法
6.8.1 离散二进制PSO
智能优化计算
思路
在考虑实际优化问题时，往往希望先采用全局搜索，使搜索空间快速收敛于某一区域，然后采用局部精细搜索以获得高精度的解。
研究发现，较大的w 值有利于跳出局部极小点，而
较小的w 值有利于算法收敛，因此提出了自适应调
整的策略，即随着迭代的进行，线性地减小w 的
值。
6.8 改进粒子群优化算法
6.8.2 惯性权重模型
智能优化计算
变化的惯性权重
wmax、wmin分别是w的最大值和最小值；iter、itermax分别是当前迭代次数和最大迭代次数。
6.8 改进粒子群优化算法
6.8.2 惯性权重模型
智能优化计算
提出
1999年Clerc对算法的研究证明，采用收敛因子能
够确保算法的收敛。
收敛因子模型
通常将υ设为4.1，经计算k为0.729。
6.8 改进粒子群优化算法
6.8.3 收敛因子模型
智能优化计算
主要研究方向
主要集中于对算法结构和性能的改善方面，包括：参数设置、粒子多样性、种群结构和算法的融合。
发展方向
目前大部分成果都是通过大量试验获得的，缺少对算法机理的研究，对PSO中的参数分析没有实质性的认识，还处于试验分析阶段。
6.8 改进粒子群优化算法
6.8.4 研究现状
智能优化计算
交换子和交换序
设n个节点的TSP问题的解序列为s=(ai)，i=1…n。定义交换子SO(i1,i2)为交换解S中的点ai1和ai2，则S’=S+SO(i1,i2)为解S经算子SO(i1,i2)操作后的新解。
一个或多个交换子的有序队列就是交换序，记作SS，SS=(SO1,SO2,…SON)。其中，SO1,…,SON 等是交换子，之间的顺序是有意义的, 意味着所有的交换子依次作用于某解上。
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
符号的定义
若干个交换序可以合并成一个新的交换序，定义为两个交换序的合并算子。
设两个交换序SS1和SS2按先后顺序作用于解S上，得到新解S’。假设另外有一个交换序SS’作用于同一解S上，能够得到形同的解S’，可定义
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
符号的定义
和属于同一等价集，在交换序等价集中，拥有最少交换子的交换序称为该等价集的基本交换序。
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
解决TSP问题的速度算式定义
α、β为[0,1]上的随机数。
vid表示交换序，xid表示路径序列（解）。
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
算法流程
1. 初始化粒子群，给每个粒子一个初始解(xid)和随机的交换序(vid);
2. 如果满足结束条件，转步骤5;
3. 根据粒子当前位置xid计算下一新解xid’;
4. 如果整个群体找到一个更好的解，更新Pgd，转步骤2;
5. 显示结果。
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
算法流程
3. 根据粒子当前位置xid计算下一新解xid’:
1）计算A=pid-xid，A是一个基本交换序，表示A作用于xid得到pid；
2）计算B=pgd-xid，B也是一个基本交换序；
3）更新速度，并将其转换为一个基本交换序；
4）更新解；
5）如果找到一个更好得解，更新pid。
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
运行结果
α=0.25
β=0.25
迭代次数=200
粒子数=80
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
10城市TSP问题（d*=2.691）
0.4 0.4439;
0.2439 0.1463;
0.1707 0.2293;
0.2293 0.761;
0.5171 0.9414;
0.8732 0.6536;
0.6878 0.5219;
0.8488 0.3609;
0.6683 0.2536;
0.6195 0.2634
智能优化计算
运行结果
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
运行结果
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
运行结果
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
运行结果
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
运行结果
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
运行结果
6.9 粒子群优化算法的应用
6.9.1 求解TSP问题
智能优化计算
神经网络的训练
主要包含3个方面：连接权重、网络拓扑结构及传递函数、学习算法。
每个粒子包含神经网络的所有参数，通过迭代来优化这些参数，从而达到训练的目的。
与BP算法相比，使用PSO训练神经网络的优点在于不使用梯度信息，可使用一些不可微的传递函数。多数情况下其训练结果优于BP算法，而且训练速
度非常快。
6.9 粒子群优化算法的应用
6.9.2 其它应用
智能优化计算
参数优化
模糊控制器的设计
机器人路径规划
信号处理和模式识别等问题
组合优化
背包问题
目标分配问题
作业调度问题
6.9 粒子群优化算法的应用
6.9.2 其它应用
智能优化计算
其他应用
多目标优化
自动目标检测
生物信号识别
决策调度
系统辨识
6.9 粒子群优化算法的应用
6.9.2 其它应用
智能优化计算
共同特点
基于概率计算的随机搜索进化算法，在结构、研究内容、方法以及步骤上有较大的相似性；存在的问题
（1）数学理论基础相对薄弱；
（2）参数设置没有确切的理论依据，对具体问题和应用环境的依赖性大；
6.10 群智能优化的特点与不足
智能优化计算
存在的问题
（3）比较性研究不足，缺乏用于性能评估的标准测试集；
（4）不具备绝对的可信性，存在应用风险；
进一步的工作
（1）进一步研究真实群居动物的行为特征；
（2）进一步研究算法的收敛性；
6.10 群智能优化的特点与不足
智能优化计算
存在的问题
（3）进一步提高收敛速度，从而解决大规模优化问题；
（4）进一步研究各种参数设置问题；
（5）研究群智能的并行算法；
（6）进一步研究各算法的适用范围；
（7）研究与其它算法的混合技术。
6.10 群智能优化的特点与不足
第六章结束
智能优化计算
第六章群智能算法 智能优化计算 6.1 群智能 6.1.1 群智能的概念 6.1.2 群智能算法 6.2 蚁群优化算法原理 6.2.1 蚁群算法的起源 6.2.2 蚁群算法的原理分析 6.3 基本蚁群优化算法 6.3.1 蚂蚁系统的模型与实现 6.3.2 蚂蚁系统的参数设置和基本属性 6.4 改进的蚁群优化算法 6.4.1 蚂蚁系统的优点与不足 6.4.2 最优解保留策略蚂蚁系统 6.4.3 蚁群系统 6.4.4 最大－最小蚂蚁系统 6.4.5 基于排序的蚂蚁系统 6.4.6 各种蚁群优化算法的比较 智能优化计算 6.5 蚁群优化算法的应用 6.5.1 典型应用 6.5.2 医学诊断的数据挖掘 6.6 粒子群算法的基本原理 6.6.1 粒子群算法的提出 6.6.2 粒子群算法的原理描述 6.7 基本粒子群优化算法 6.7.1 基本粒子群算法描述 6.7.2 参数分析 6.7.3 与遗传算法的比较 6.8 改进粒子群优化算法 6.8.1 离散二进制PSO 6.8.2 惯性权重模型 6.8.3 收敛因子模型 6.8.4 研究现状 智能优化计算 6.9 粒子群优化算法的应用 6.9.1 求解TSP问题 6.9.2 其它应用 6.10 群智能算法的特点与不足 智能优化计算 6.1 群智能 智能优化计算 群智能（Swarm Intelligence, SI ） 人们把群居昆虫的集体行为称作“群智能”（“群体智能”、“群集智能”、“集群智能”
等） 特点 个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂（智能）的行为特征。 6.1.1 群智能的概念 6.1 群智能 智能优化计算 描述 群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。 特性 指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。 6.1.2 群智能算法 6.1 群智能 智能优化计算 优点 灵活性：群体可以适应随时变化的环境； 稳健性：即使个体失败，整个群体仍能完成任务； 自我组织：活动既不受中央控制，也不受局部监管。 典型算法 蚁群算法（蚂蚁觅食） 粒子群算法（鸟群捕食） 6.1.2 群智能算法 6.2 蚁群优化算法原理 智能优化计算 蚁群的自组织行为 “双桥实验” 通过遗留在来往路径 上的信息素 （Pheromone）的挥 发性化学物质来进行 通信和协调。 6.2.1 蚁群算法的起源 6.2 蚁群优化算法原理 智能优化计算 蚁群的自组织行为 “双桥实验” 6.2.1 蚁群算法的起源 6.2 蚁群优化算法原理 智能优化计算 提出蚁群系统 1992年，意大利学者M. Dorigo在其博士论文中提出 蚂蚁系统（Ant System）。
现代智能优化算法课程群智能优化算法综述 学生姓名： 学号： 班级： 2014年6月22日
摘要 工程技术与科学研究中的最优化求解问题十分普遍，在求解过程中，人们创造与发现了许多优秀实用的算法。群智能算法是一种新兴的演化计算技术，已成为越来越多研究者的关注焦点，智能优化算法具有很多优点,如操作简单、收敛速度快、全局收敛性好等。群智能优化是智能优化的一个重要分支，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的联系。群智能优化通过模拟社会性昆虫的各种群体行为，利用群体中个体之间的信息交互和合作实现寻优。本文综述群智能优化算法的原理、主要群智能算法介绍、应用研究及其发展前景。 关键词：群智能；最优化；算法
目录 摘要 (1) 1 概述 (3) 2 定义及原理 (3) 2.1 定义 (3) 2.2 群集智能算法原理 (4) 3 主要群智能算法 (4) 3.1 蚁群算法 (4) 3.2 粒子群算法 (5) 3.3 其他算法 (6) 4 应用研究 (7) 5 发展前景 (7) 6 总结 (8) 参考文献 (9)
1 概述 优化是人们长久以来不断研究与探讨的一个充满活力与挑战的领域。很多实际优化问题往往存 在着难解性,传统的优化方法如牛顿法、共扼梯度法、模式搜索法、单纯形法等己难以满足人们需求。 因此设计高效的优化算法成为众多科研工作者的研究目标。随着人类对生物启发式计算的研究, 一些社会性动物( 如蚁群、蜂群、鸟群) 的自组织行为引起了科学家的广泛关注。这些社会性动物在漫长的进化过程中形成了一个共同的特点: 个体的行为都很简单, 但当它们一起协同工作时, 却能够“突现”出非常复杂的行为特征。基于此,人们设计了许多优化算法,例如蚁群算法、粒子群优化算法、混合蛙跳算法、人工鱼群算法,并在诸多领域得到了成功应用。目前, 群智能理论研究领域主要有两种算法: 蚁群算法(Ant Colony Optimization, ACO) 和粒子群优化算法(ParticleSwarm Optimization, PSO)。 2 定义及原理 2.1 定义 群集智能优化算法源于对自然界的生物进化过程或觅食行为的模拟。它将搜索和优化过程模拟成个体的进化或觅食过程，用搜索空间中的点模拟自然界中的个体；将求解问题的目标函数度量成个体对环境的适应能力；将个体的优胜劣汰过程或觅食过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。从而，形成了一种以“生成+检验”特征的迭代搜索算法，是一种求解极值问题的自适应人工智能技术。各类优化算法实质上都是建立问题的目标函数，求目标函数的最优解，因而实际工程优化问题均可转化为函数优化问题。其表达形式如下： 求： ,,2,1,0)(..), (min , ,,2,1,),,,(21Lm j X g t s X f n L i x L x x X i T n i =≤== 。Ω∈X 其中， i X 为设计变量；)(X f 为被优化的目标函数；0)(≤X g j 为约束函数；Ω为设计变量的 可行域。
群体协同智能优化算法改进及其应用研究优化问题广泛地存在于实际工程问题和科学研究中。优化问题具有解空间规模大、维数高的特点,一些传统优化算法在求解大规模优化问题时,存在计算复杂度高、时间长等问题。群体智能算法因其参数少、模型简单、易于实现等优点,已成为求解优化问题新的研究方向。随着人工智能的高速发展,电子商务、移动互联网金融无时无刻不断产生数据。 数据挖掘技术越来越受到众多领域的广泛关注。聚类技术是数据挖掘领域的一个重要分支,在无监督条件下,用于挖掘数据潜在结构,已成为人工智能领域研究热点。密度峰值快速搜索聚类算法是聚类算法中极具竞争力的一种新型聚类算法,已得到各领域广泛认可,但其仍存在手动设置参数的缺陷。本文将布谷鸟搜索算法作为主要研究对象,对其进行研究与改进,并对密度峰值快速搜索聚类算法存在缺陷进行改进。 本文主要内容和创新点如下:(1)针对布谷鸟搜索算法在处理复杂函数时,算法收敛速度慢;在处理多维数据时,算法寻优精度低,算法稳定性较差的问题,提出动态自适应步长的双重策略的布谷鸟搜索算法。算法引入动态自适应步长机制和双重评价策略,动态步长中学习因子加速算法在解空间中搜索速度,在算法迭代前期,双重评价策略中的逐列排序策略在全局搜索中快速定位,并引入动态发现概率增加全局搜索能力。(2)针对密度峰值快速搜索聚类算法存在手动设置截断距离d_c,欧式距离无法准确反映数据间的相似性等缺陷,提出布谷鸟优化的密度峰值快速搜索聚类算法。算法通过布谷鸟搜索算法优化截断距离,并引入余弦相似度,将方向与实际距离相结合,更好区分两类中间区域数据点的归属度。 仿真实验结果表明,改进密度峰值快速搜索聚类算法具有较好聚类性能。(3)基于布谷鸟优化的密度峰值快速搜索聚类算法,对银行个人信贷数据进行聚类。仿真实验结果表明,本文提出的方法能够较为有效地分析和预测银行个人信贷违约情况,帮助银行信贷部门合理地做出决策。
粒子群优化算法综述 摘要：本文围绕粒子群优化算法的原理、特点、改进与应用等方面进行全面综述。侧重于粒子群的改进算法，简短介绍了粒子群算法在典型理论问题和实际工业对象中的应用，并给出了粒子群算三个重要的网址，最后对粒子群算做了进一步展望。 关键词；粒子群算法；应用；电子资源；综述 0.引言 粒子群优化算法]1[(Particle Swarm Optimization ，PSO)是由美国的Kenned 和Eberhar 于1995年提出的一种优化算法,该算法通过模拟鸟群觅食行为的规律和过程，建立了一种基于群智能方法的演化计算技术。由于此算法在多维空间函数寻优、动态目标寻优时有实现容易，鲁棒性好，收敛快等优点在科学和工程领域已取得很好的研究成果。 1. 基本粒子群算法]41[- 假设在一个D 维目标搜索空间中，有m 个粒子组成一个群落，其中地i 个粒子组成一个D 维向量，),,,(21iD i i i x x x x =，m i ,2,1=，即第i 个粒子在D 维目标搜索空间中的位置是i x 。换言之，每个粒子 的位置就是一个潜在的解。将i x 带入一个目标函数就可以计算出其适 应值，根据适应值得大小衡量i x 的优劣。第i 个粒子的飞翔速度也是一个D 维向量，记为),,,(21iD i i i v v v v =。记第i 个粒子迄今为止搜索到的最优位置为),,,(21iD i i i p p p p =，整个粒子群迄今为止搜索到的最优位置为),,,(21gD gi g g p p p p =。 粒子群优化算法一般采用下面的公式对粒子进行操作
)()(22111t id t gd t id t id t id t id x p r c x p r c v v -+-+=+ω (1) 11+++=t id t id t id v x x (2) 式中，m i ,,2,1 =；D d ,,2,1 =；ω是惯性权重， 1c 和2c 是非负常数， 称为学习因子， 1r 和2r 是介于]1,0[间的随机数；],[max max v v v id -∈，max v 是常数，由用户设定。 2. 粒子群算法的改进 与其它优化算法一样PSO 也存在早熟收敛问题。随着人们对算 法搜索速度和精度的不断追求，大量的学者对该算法进行了改进，大致可分为以下两类：一类是提高算法的收敛速度；一类是增加种群多样性以防止算法陷入局部最优。以下是对最新的这两类改进的总结。 2.1.1 改进收敛速度 量子粒子群优化算法]5[:在量子系统中，粒子能够以某一确定的 概率出现在可行解空间中的任意位置，因此，有更大的搜索范围，与传统PSO 法相比，更有可能避免粒子陷入局部最优。虽然量子有更大的搜索空间，但是在粒子进化过程中，缺乏很好的方向指导。针对这个缺陷，对进化过程中的粒子进行有效疫苗接种，使它们朝着更好的进化方向发展，从而提高量子粒子群的收敛速度和寻优能力。 文化粒子群算法]6[:自适应指导文化PSO 由种群空间和信念空间 两部分组成。前者是基于PSO 的进化，而后者是基于信念文化的进化。两个空间通过一组由接受函数和影响函数组成的通信协议联系在一起，接受函数用来收集群体空间中优秀个体的经验知识；影响函数利用解决问题的知识指导种群空间进化；更新函数用于更新信念空间；
混合群智能优化算法研究及应用 优化问题广泛地存在于科学研究和工程实践中。群智能优化算法是优化算法中最新的一个分支,也是最热门的发展方向。群智能优化算法是通过模拟自然界中生物间相互合作、共享信息等群体行为而建立起来的随机搜索算法,相较于经典优化算法具有结构简单、易于实现等优点。不同的群智能优化算法是模拟不同生物行为形成的,所以它们各具特点和适用场景。然而,单一的群智能优化算法均有其局限性,如搜索精度不够高、收敛速度慢、性能受参数影响较大和容易陷入局部最优等。将不同群智能优化算法有机结合,设计混合群智能优化算法是一种提高算法性能的有效方法,具有重要的研究意义。本文的主要研究内容及创新点包括以下几个方面:(1)针对单目标数值优 化问题提出了一种基于跟随蜂搜索的自适应粒子群算法(Follower Bee Search Based Adapitve Particle Swarm Optimization,F-APSO)。首先在经典粒子群算法粒子飞行轨迹分析的基础上提出了一种自适 应的粒子群算法(Adapitve Particle Swarm Optimization,APSO), 提高了算法在求解单峰问题时的性能。然后提出了一种针对自适应粒子群算法的稳定性分析方法,基于该方法对APSO进行了稳定性分析,给出了能够保证算法稳定的参数取值条件。接着通过引入人工蜂群算法中的跟随蜂搜索,提高了算法的开拓性,并将APSO的稳定性条件拓展到了 F-APSO中。仿真实验表明F-APSO在求解单目标数值优化问题时在解的质量和时间消耗上都具有良好表现。将F-APSO用于解决矿山生产排程优化问题,与原有生产方案相比优化后的方案在不同铁
粒子群算法综述 【摘要】：粒子群算法(pso)是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已得到广泛研究和应用。为了进一步推广应用粒子群算法并为深入研究该算法提供相关资料，本文对目前国内外研究现状进行了全面分析，在论述粒子群算法基本思想的基础上，围绕pso的运算过程、特点、改进方式与应用等方面进行了全面综述，并给出了未来的研究方向展望。 【关键词】：粒子群算法优化综述 优化理论的研究一直是一个非常活跃的研究领域。它所研究的问题是在多方案中寻求最优方案。人们关于优化问题的研究工作，随着历史的发展不断深入，对人类的发展起到了重要的推动作用。但是，任何科学的进步都受到历史条件的限制，直到二十世纪中期，由于高速数字计算机日益广泛应用，使优化技术不仅成为迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。这些优化技术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、生产调度等。随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，常规优化法如牛顿法、车辆梯度法、模式搜索法、单纯形法等已经无法处理人们所面的复杂问题，因此高效的
优化算法成为科学工作者的研究目标之一。 1.粒子群算法的背景 粒子群算法(particle swarm optimization，pso)是一种新兴的演化算法。该算法是由j.kennedy和r.c.eberhart于1995年提出的一种基于群智能的随机优化算法。这类算法的仿生基点是：群集动物(如蚂蚁、鸟、鱼等)通过群聚而有效的觅食和逃避追捕。在这类群体的动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。如在蚁群中，当每个个体发现食物之后，它将通过接触或化学信号来招募同伴，使整个群落找到食源；在鸟群的飞行中，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，但随着时间推移，这些初始处于随机状态的鸟通过相互学习(相互跟踪)组织的聚集成一个个小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集在同一位置──食源。这些群集动物所表现的智能常称为“群体智能”，它可表述为：一组相互之间可以进行直接通讯或间接通讯(通过改变局部环境)的主体，能够通过合作对问题进行分布求解。换言之，一组无智能的主体通过合作表现出智能行为特征。粒子群算法就是以模拟鸟的群集智能为特征，以求解连续变量优化问题为背景的一种优化算法。因其概念简单、参数较少、易于实现等特点，自提出以来已经受到国内外研究者的高度重视并被广泛应用于许多领域。
现代智能优化算法课程群智能优化算法综述学生姓名: 学号: 班级: 2014年6月22日
摘要 工程技术与科学研究中的最优化求解问题十分普遍,在求解过程中,人们创造与发现了许多优秀实用的算法。群智能算法就是一种新兴的演化计算技术,已成为越来越多研究者的关注焦点,智能优化算法具有很多优点,如操作简单、收敛速度快、全局收敛性好等。群智能优化就是智能优化的一个重要分支,它与人工生命,特别就是进化策略以及遗传算法有着极为特殊的联系。群智能优化通过模拟社会性昆虫的各种群体行为,利用群体中个体之间的信息交互与合作实现寻优。本文综述群智能优化算法的原理、主要群智能算法介绍、应用研究及其发展前景。 关键词:群智能;最优化;算法
目录 摘要 0 1 概述 (2) 2 定义及原理 (2) 2、1 定义 (2) 2、2 群集智能算法原理 (3) 3 主要群智能算法 (3) 3、1 蚁群算法 (3) 3、2 粒子群算法 (4) 3、3 其她算法 (5) 4 应用研究 (6) 5 发展前景 (6) 6 总结 (7) 参考文献 (8)
1 概述 优化就是人们长久以来不断研究与探讨的一个充满活力与挑战的领域。很多实际优化问题往往存 在着难解性,传统的优化方法如牛顿法、共扼梯度法、模式搜索法、单纯形法等己难以满足人们需求。 因此设计高效的优化算法成为众多科研工作者的研究目标。随着人类对生物启发式计算的研究, 一些社会性动物( 如蚁群、蜂群、鸟群) 的自组织行为引起了科学家的广泛关注。这些社会性动物在漫长的进化过程中形成了一个共同的特点: 个体的行为都很简单, 但当它们一起协同工作时, 却能够“突现”出非常复杂的行为特征。基于此,人们设计了许多优化算法,例如蚁群算法、粒子群优化算法、混合蛙跳算法、人工鱼群算法,并在诸多领域得到了成功应用。目前, 群智能理论研究领域主要有两种算法: 蚁群算法(Ant Colony Optimization, ACO) 与粒子群优化算法(ParticleSwarm Optimization, PSO)。 2 定义及原理 2、1 定义 群集智能优化算法源于对自然界的生物进化过程或觅食行为的模拟。它将搜索与优化过程模拟成个体的进化或觅食过程,用搜索空间中的点模拟自然界中的个体;将求解问题的目标函数度量成个体对环境的适应能力;将个体的优胜劣汰过程或觅食过程类比为搜索与优化过程中用好的可行解取代较差可行解的迭代过程。从而,形成了一种以“生成+检验”特征的迭代搜索算法,就是一种求解极值问题的自适应人工智能技术。各类优化算法实质上都就是建立问题的目标函数,求目标函数的最优解,因而实际工程优化问题均可转化为函数优化问题。其表达形式如下: 求: ,,2,1,0)(..), (min , ,,2,1,),,,(21Lm j X g t s X f n L i x L x x X i T n i =≤== 。Ω∈X 其中,i X 为设计变量;)(X f 为被优化的目标函数;0)(≤X g j 为约束函数;Ω为设计变量的可行
第十六章群体智能优化算法总结 总结一下最近一段时间关于群体智能优化算法的文章，这方面的文章目前一共发表了13篇，涉及粒子群（鸟）、人工蜂群、蜘蛛猴、蚁群、布谷鸟、萤火虫群、萤火虫、蝙蝠、鱼群、蟑螂、猫群、细菌觅食和烟花算法，虽然这都是些五花八门的小东西，但也不是无规律可循，这里需要注意的是，群体智能一般是指具有生命的种群（鸟、鱼等），但也有像烟花这样的无生命个体，这里我们将所有这些个体统称为智能体，认为它们具有一定的能动性，可以在解空间中进行搜索。图1为各主要优化算法的提出时间和提出者，可以看出大多数算法诞生于2000~2010年这十年左右，随着计算机计算能力的提升，人们开始依赖于这种既能得到较优的结果又不会消耗太多计算时间的元启发式算法。 图1 群体智能优化算法发展历程 下面总结一下这些算法的共同点： 1、都有多个粒子，代表每种智能体； 2、每个个体通过一定的机制进行位置的变化或者移动，来对解的空间进行搜索； 3、个体之间具有一定的独立性，利用局部信息和全局信息进行交互；
4、群体在演变过程中都引入了随机数，以便进行充分地探索。 其实人群也算是一种特殊的群体，只不过他不像其他的群体那样，仅仅是觅食，人作为一种高级动物，除了吃饱肚子以外，还有其他很多精神方面的需求，比如幸福度、快乐度和舒适度等等各个方面，并且人类具有的最大优势是语言沟通和学习能力，因此，基于这样的特性也可以提出基于人群的优化算法，只不过可能需要结合更多的组织行为学和行为心理学等相关的知识，对人的群集行为进行理论解释，同时可以采用更多以机器学习或人工智能为基础的高级策略，并应用于多目标优化问题。不过好像在2006年就已经有类似的算法了，至于为什么没有普及开来，可能还是人的行为太复杂了吧。 对于群体智能优化方面的更新将暂时告一段落，接下来将更多的关注另一种元启发式算法-进化计算，这类算法主要是基于生物的进化理论，包括遗传算法、进化策略、进化规划等，都将在后续的内容中逐渐详细讲解。
智能优化算法的统一框架 指导老师：叶晓东教授 姓名：李进阳 学号：2 班级：电磁场与微波技术5班 2011年6月20日
目录 1 概述 (3) 2群体智能优化算法.................................. 错误!未定义书签。 人工鱼群算法 (4) 蚁群算法 (5) 混合蛙跳算法 (9) 3神经网络算法 (10) 神经网络知识点概述 (10) 神经网络在计算机中的应用 (11) 4模拟退火算法 (15) 5遗传算法.......................................... 错误!未定义书签。 遗传算法知识简介 (17) 遗传算法现状 (18) 遗传算法定义 (19) 遗传算法特点和应用 (20) 遗传算法的一般算法 (21) 遗传算法的基本框架 (26) 6总结 (28) 7感谢 (29)
1概述 近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑。众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。智能优化算法就是在这种背景下产生并经实践证明特别有效的算法。 2群体智能优化算法 自然界中群体生活的昆虫、动物,大都表现出惊人的完成复杂行为的能力。人们从中得到启发,参考群体生活的昆虫、动物的社会行为,提出了模拟生物系统中群体生活习性的群体智能优化算法。在群体智能优化算法中每一个个体都是具有经验和智慧的智能体 (Agent) ,个体之间存在互相作用机制,通过相互作用形成强大的群体智慧来解决复杂的问题。自 20世纪 90年代模拟蚂蚁行为的蚁群算法(ACO)提出以来,又产生了模拟鸟类行为的微粒群算法 ( PSO)、模拟鱼类生存习性的人工鱼群算法、模拟青蛙觅食的混合蛙跳算法 ( SFLA)等。这些群体智能优化算法的出现,使原来一些复杂的、难于用常规的优化算法进行处理的问题可以得到解决,大大增强了人们解决和处理优化问题的能力,这些算法不断地用于解决工程实际中的问题,使得人们投入更大的精力对其理论和实际应用进行研究。群体智能优化算法本质上是一种概率搜索,它不需要问题的梯度信息具有以下不同于传统优化算法的特点: ①群体中相互作用的个体是分布式的,不存在直接的中心控制,不会因为个别个体出现故障而影响群体对问题的求解,具有较强的鲁棒性; ②每个个体只能感知局部信息,个体的能力或遵循规则非常简单,所以群体智能的实现简单、方便; ③系统用于通信的开销较少,易于扩充; ④自
2012年第32 期 群智能算法是人们受自然界或生物界种群规律的启发，根据其原理，仿生模拟其规律而设计求解问题的算法。近几十年来，人们通过模拟自然生态系统机制以求解复杂优化问题的仿生智能算法相继被提出和研究。群智能算法有遗传算法、模拟退火算法、蚁群算法、粒子群算法等。 萤火虫算法是一种新颖的仿生群智能算法，是受自然界中的萤火虫通过荧光进行信息交流这种群体行为的启发演变而来的。萤火虫算法目前有两种版本：a)由印度学者Krishnanand等人［1］提出，称为GSO(glowworm swarm optimization)；b)由剑桥学者Yang[2]提出，称为FA( firefly algorithm)。两种算法的仿生原理相同，但在具体实现方面有一定差异。 本文分析了萤火虫算法的仿生原理，并从数学角度对两种版本的算法实现优化过程进行定义。 1．GSO算法 1.1算法的数学描述与分析 在基本GSO中，把n个萤火虫个体随机分布在一个D维目标搜索空间中，每个萤火虫都携带了萤光素li。萤火虫个体都发出一定量的萤光相互影响周围的萤火虫个体，并且拥有各自的决策域r i d(0＜r i d ≤r s)。萤火虫个体的萤光素大小与自己所在位置的目标函数有关，荧光素越大，越亮的萤火虫表示它所在的位置越好，即有较好的目标值,反之则目标值较差。决策域半径的大小会受到邻域内个体的数量的影响，邻域内萤火虫密度越小，萤火虫的决策域半径会加大，以便找到更多的邻居；反之，则萤火虫的决策域半径会缩小。最后，大部分萤火虫会聚集在多个位置上。初始萤火虫时，每个萤火虫个体都携带了相同的萤光素浓度l0和感知半径r0。 定义1萤光素更新 l i(t)=(1-ρ)l i(t-1)+γJ(x i(t))（1） 其中，J(x i(t))为每只萤火虫i在t迭代的位置x i(t)对应的目标函数值；l i(t)为荧光素值转化为荧光素值；γ为荧光素更新率。 定义2概率选择选择移向邻域集N i(t)内个体j的概率p ij(t)： p ij(t)=l j(t)-l i(t) k∈N i (t) Σ(l k(t)-l i(t)) （2） 其中，邻域集N i（t）={j:d ij(t) 第1章 群体智能算法概述 1975年，美国Michigan大学的John Holland[1]教授发表了其开创性的著作《Adapatation in Natural and Artificail System》，在该著作中John Holland教授对智能系统及自然界中的自适应变化机制进行了详细阐述，并提出了计算机程序的自适应变化机制，该著作的发表被认为是群体智能（Swarm Intelligence）[2]算法的开山之作。随后，John Holland和他的学生对该算法机制进行了推广，并正式将该算法命名为遗传算法（Gentic Algorithm，GA）[3]~[5]。遗传算法的出现和成功，极大地鼓舞了广大研究工作者向大自然现象学习的热情。经过多年的发展，已经诞生了大量的群体智能算法，包括：遗传算法、蚁群优化（Ant Colony Optimization，ACO）[6]~[7]算法、差异演化（Differential Evolution，DE）[8]~[12]算法、粒子群优化（Particle Swarm Optimization，PSO）[13]~[16]算法等。 随着群体智能算法在诸如机器学习、过程控制、经济预测、工程预测等领域取得了前所未有的成功，它已经引起了包括数学、物理学、计算机科学、社会科学、经济学及工程应用等领域的科学家们的极大兴趣。目前关于群体智能计算的国际会议在全世界各地定期召开，各种关于信息技术或计算机技术的国际会议也都将智能进化技术作为主要研讨课题之一。甚至有专家指出，群体智能计算技术、混沌分析技术、分形几何、神经网络等将会成为研究非线性现象和复杂系统的主要工具，也将会成为人们研究认知过程的主要方法和工具。 1.1 群体智能算法的特点 1.1.1 智能性 群体智能算法通过向大自然界中的某些生命现象或自然现象学习，实现对于问题的求解，这一类算法中包含了自然界生命现象所具有的自组织、自学习和自适应性等特性。在运算过程中，通过获得的计算信息自行组织种群对解空间进行搜索。种群在搜索过程中依据事先设定的适应度函数值，采用适者生存、优胜劣汰的方式进化，所以算法具有一定的智能性。 由于群体智能算法具有的这种优点，应用群体智能算法求解问题时，不需要事 研究生课程论文及评阅书 （2013—2014学年下学期） 论文题目：几种现代优化算法的比较研究课程名称：智能优化方法及应用 任课教师：周永权 授课时间：2014年2月日至2014年6月日 学号：2013081203402 姓名：吴丽佳 专业名称：计算机应用技术 所在学院：信息科学与工程学院 课程论文格式要求 1．课程论文一律使用标准A4复印纸打印，以左侧为准装订成册，本页装订在封面的背面。 2．课程论文格式按照《广西民族大学学报》论文的格式要求实行。 3．论文打印的格式要求： （1）论文标题（使用黑体二号加黑；一级标题、二级标题、三级标题分别使用宋体三号、四号及小四号并加黑）； （2）摘要、关键字（需使用宋体小四号）； （3）正文（使用宋体小四号，行距23磅）； （4）参考文献（使用宋体五号）。 4．“任课教师的评语”放在最后，单独一页。 几种现代优化算法的比较研究 摘要：现代最优化算法比较常见的有遗传算法、粒子群算法、群体复合形进化算法、鱼群算法、模拟退火算法和蚁群算法。文章主要是对遗传算法、粒子群算法和鱼群算法三个算法的优化性能进行比较。首先介绍了三个算法的基本思想和算法优化过程，以此可以了解三种算法有着自身的特点和优势，促进理解后面不同的优化结果和改进方向。文章中，将三种算法分别对这三个函数用VC编出程序，得出优化结果，再针对结果分析算法。三个典型函数特点各不同，但对算法的优化能力要求都比较高，在不同方面考验了算法的收敛和爬山功能。最后，通过分析三个函数的九个优化结果，提出这三种算法的优点和不足，并列出改进措施。从分析结果可以看出遗传算法要优于另两种算法，并且其改进的余地也是最大的，粒子群算法的优化结果次之，鱼群算法的优化结果相对来说是最差的，但三种算法都可以进行改进以达到更好的优化结果。 关键词：优化；遗传算法；粒子群算法；鱼群算法；比较 Abstract: Modern optimization includes genetic algorithm, particle swarm algorithm, multi-complex algorithm, fish school algorithm, Simulated Annealing algorithm and ant colony algorithm. The paper mainly compares the optimization abilities of genetic algorithm, particle swarm algorithm and fish school algorithm. Firstly, the article introduces the basic ideas and the optimization processes of the three algorithms, from which the characteristics and advantages of the three algorithms will be found out, after that, the optimization results and the ways of improvements behind will be understood easily. Secondly, the three algorithms program with VC for the three functions, so get the results of optimization and analyze them. The three representative functions have specialties from each other, but they have one same point which is having much more demands on the algorithms, which tests the abilities of astringency and mountain climbing. At last, through analyzing the nine optimization results of three functions, the paper explains the advantages and the disadvantages of the three algorithms, and puts forward the improvement means. From the conclusion, genetic algorithm is much better than the other two optimization algorithms, and its room of improvement is the most maximum in the three algorithms too. The article also 群体智能方法在最优化问题的应用和发展前景 姓名：曾燕亭学号：201110510133 班级：11计科1班 摘要：将遗传算法解决最优化问题，即将最优化问题转化为求解目标函数的最优解问题。关键词：遗传算法；最优化 1.定义 1.1定义及原理 顾名思义，群体智能即群其实质是将物理问题数字化，体产生的智能，与集体智慧类似。我们可以从两个方面来理解群体智能的含义。一方面，群体智能是自然界广泛存在的一种现象，指大量简单个体构成的群体按照简单的交互规则相互协作，完成了其中任何一个个体不可能单独完成的复杂任务。以蚁群为例，正如斯坦福大学生物学家D．Gordon的概括：蚂蚁很笨，但蚁群很聪明。另一方面，人们通过对这些群体行为的研究，逐步形成了群体智能理论，即研究大量个体的简单行动如何成为群体的高智能行为的理论。群体智能理论自20世纪80年代出现以来便吸引了众多研究者的关注，是人工智能及经济、社会、生物等交叉学科的热点和前沿领域，因此设计高效的优化算法成为众多科研工作者的研究目标。随着人类对生物启发式计算的研究, 一些社会性动物( 如蚁群、蜂群、鸟群) 的自组织行为引起了科学家的广泛关注。这些社会性动物在漫长的进化过程中形成了一个共同的特点: 个体的行为都很简单, 但当它们一起协同工作时, 却能够“突现”出非常复杂的行为特征。基于此,人们设计了许多优化算法,例如蚁群算法、粒子群优化算法、混合蛙跳算法、人工鱼群算法,并在诸多领域得到了成功应用。目前, 群智能理论研究领域主要有两种算法: 蚁群算法和粒子群优化算法。 群集智能优化算法源于对自然界的生物进化过程或觅食行为的模拟。它将搜索和优化过程模拟成个体的进化或觅食过程，用搜索空间中的点模拟自然界中的个体；将求解问题的目标函数度量成个体对环境的适应能力；将个体的优胜劣汰过程或觅食过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。从而，形成了一种以“生成+检验”特征的迭代搜索算法，是一种求解极值问题的自适应人工智能技术。各类优化算法实质上都是建立问题的目标函数，求目标函数的最优解，因而实际工程优化问题均可转化为函数优化问题。其表达形式如下： 求： 粒子群优化算法 1. 引言 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，由Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究 PSO同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。详细的步骤以后的章节介绍 同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域 2. 背景: 人工生命 "人工生命"是来研究具有某些生命基本特征的人工系统. 人工生命包括两方面的容 1. 研究如何利用计算技术研究生物现象 2. 研究如何利用生物技术研究计算问题 我们现在关注的是第二部分的容. 现在已经有很多源于生物现象的计算技巧. 例如, 人工神经网络是简化的大脑模型. 遗传算法是模拟基因进化过程的. 现在我们讨论另一种生物系统- 社会系统. 更确切的是, 在由简单个体组成的群落与环境以及个体之间的互动行为. 也可称做"群智能"(swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为 例如floys 和boids, 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计. 在计算智能(computational intelligence)领域有两种基于群智能的算法. 蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟. 已经成功运用在很多离散优化问题上. 粒子群优化算法(PSO) 也是起源对简单社会系统的模拟. 最初设想是模拟鸟群觅食的过程. 但后来发现PSO是一种很好的优化工具. 3. 算法介绍 第十二章 蟑螂算法 12.1 介绍 蟑螂群优化算法(Cockroach Swarm Optimization ，CSO)是受蟑螂群体捕食行为的启发而提出的，该算法是通过模仿蟑螂个体寻找整体最优值的追逐行为而建立的。蟑螂是一种昆虫，通常出现在黑暗和潮湿的地方。它们表现出追逐、聚集和分散等觅食行为(Kwiecien & Pasieka, 2017)。 CSO 算法是通过模仿蟑螂的生物学行为来实现的：聚集、分散和残忍行为，下面分别对各个过程进行建模。 12.2 聚集行为（Chase-Swarming behavior ） ()()*rand*,*rand*,r r r r r r r g r r r y a y y y y a y y ρρρρ+-≠??=?+-=?? （1） 其中y r 为蟑螂的位置，a 代表步长，为固定值，rand 为(0,1)之间的任意值，ρr 和ρg 分别是个体最优和全局最优蟑螂的位置点，个体最优可以通过下式进行计算： {},visual r s s r s opt y y y ρ=-≤ （2） 其中visual 为常数，表示蟑螂的视野范围，r=1,2,3,...N ，s=1,2,3,...N 。全局最优位置可以通过下式确定： {}opt g r r y ρ= （3） 12.3 分散行为（Dispersing behavior ） 在一定的时间间隔内，每个个体被随机分散，以保持当前个体的多样性，模型如下： rand(1,),1,2,,r r y y E r N =+=? （4） 其中rand(1,E)为可以在一定范围内设置的E 维（问题空间维度）随机向量。 12.4 残忍行为（Ruthless behavior ） 在一定的时间间隔内，当前的最佳个体取代随机选择的个体，即弱肉强食。模型如下： l g y ρ= （5） l 为[1,N]之间的任意整数。 12.5 蟑螂算法 Step1：参数设置和种群初始化。设置参数a ，N ，E ，生成蟑螂种群y r （r=1,2,...N ）； Step2：使用式（2）和（3）搜索局部和全局最优位置ρr 和ρg ； Step3：根据式（1）执行聚集行为，更新全局最优ρg ； Step4：根据式（4）执行分散行为，如果新的位置由于原有的位置，则使用新的位置，否则保留原有位置，同时更新全局最优ρg ； Step5：根据式（5）执行残忍行为； Step6：重复Step2~5，直到满足终止条件。第1章群体智能算法概述
智能优化方法论文
群体智能方法在最优化问题的应用和未来
粒子群优化算法综述
群体智能优化算法-蟑螂算法
相关主题
文本预览