没有合适的资源?快使用搜索试试~ 我知道了~
蚁群算法在求解连续空间优化问题中的应用研究
4星 · 超过85%的资源 需积分: 11 10 下载量 182 浏览量
2009-07-10
12:26:44
上传
评论
收藏 609KB DOC 举报
温馨提示
试读
22页
摘 要: 蚁群算法是受自然界中真实蚁群集体行为的启发而提出的一种基于种群的模拟进化算法,属于带构造性特征的随机搜索算法。 本文研究了一种可用于求解连续空间优化问题的蚁群算法策略,能提高最优解搜索过程的效率以及搜索状态的多样性和随机性,且不受优化目标函数是否连续、可微等因素的限制,为实际应用提供了途径,数值算例结果表明该搜索策略能较好地找到近似全局最优解。
资源推荐
资源详情
资源评论
蚁群算法在求解连续空间优化问题中的应用研究
目 录
1 引 言........................................................................................................................................................1
1.1 蚁群算法的研究背景...........................................................................................1
1.2 本文主要工作.......................................................................................................1
1.3 本文组织结构.......................................................................................................2
2 蚁群算法简介.........................................................................................................................................3
2.1 蚁群算法的产生...................................................................................................3
2.2 蚁群算法概述.......................................................................................................3
2.3 蚁群算法的优缺点...............................................................................................3
3 蚁群算法基本模型.................................................................................................................................5
3.1 蚁群算法的工作原理...........................................................................................5
3.2 蚁群算法的基本模型...........................................................................................5
3.3 基本模型的实现...................................................................................................7
3.3.1 基本模型的实现步骤....................................................................................7
3.3.2 基本模型的程序流程....................................................................................8
4 用于连续空间优化问题的蚁群算法.....................................................................................................9
4.1 连续空间优化问题...............................................................................................9
4.2 算法基本思想.......................................................................................................9
4.3 求一维函数优化的蚁群算法模型.....................................................................10
4.4 一维函数优化的局部搜索策略.........................................................................11
4.5 用于一维函数优化的蚁群算法描述.................................................................12
4.6 仿真实验.............................................................................................................13
4.7 实验结果分析及算法性能讨论.........................................................................16
4.7.1 实验结果分析..............................................................................................16
4.7.2 算法性能讨论..............................................................................................16
5 结束语...................................................................................................................................................18
致 谢.........................................................................................................................................................19
参考文献..................................................................................................................................................20
I
忻州师院计算机系本科学士学位论文
蚁群算法在求解连续空间优化问题中的应用研究
摘 要:蚁群算法是受自然界中真实蚁群集体行为的启发而提出的一种基于种群的模拟进
化算法,属于带构造性特征的随机搜索算法。
本文研究了一种可用于求解连续空间优化问题的蚁群算法策略,能提高最优解搜索过
程的效率以及搜索状态的多样性和随机性,且不受优化目标函数是否连续、可微等因素的
限制,为实际应用提供了途径,数值算例结果表明该搜索策略能较好地找到近似全局最优
解。
关键词:蚁群算法 模拟进化算法 转移概率 连续空间优化
Abstract:Ant colony algorithm, a kind of simulated evolutionary algorithms based
on races and enlightened by the group action of ant group in nature, belongs to
random search algorithm along with construction characteristics.
The paper studied a sort of ant colony algorithm available for dealing with
continuous function optimization. It can improve the efficiency of optimal solution
search as well as diversity and randomness of search status. Besides, it is not limited
by the factors like the continuousness of optimal objective function and rectifiable
differential so as to provide methods for practical application. Numerical statistics
show that the search strategy can be better to find an optimal solution similar to the
overall situation.
Keywords : Ant colony algorithm Simulated evolutionary algorithm Transition
probability Continuous function optimization
1 引 言
1.1 蚁群算法的研究背景
蚁群算法(Ant Colony Algorithm)是近几年优化领域中新出现的一种启发
式仿生类并行智能进化算法,它是受到人们对自然界中真实的蚁群集体行为的
研究成果的启发而提出的一种基于种群的模拟进化算法,属于随机搜索算法。
由意大利学者 M.Dorigo 等人首先提出,充分利用了蚁群搜索食物的过程与著
名的旅行商问题(TSP)之间的相似性,通过人工模拟蚂蚁搜索食物的过程(即:
通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径 )来求
解 TSP,为了区别于真实蚂蚁群体系统,我们称这种算法为“人工蚁群算法”。
并用该方法求解 NP-Hard 问题,如:TSP 问题、分配问题、job-shop 调度
问题等,取得了较好的实验结果。虽然对此方法的研究刚刚起步,但研究表明
蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的一些优越性,证明
它是一种很有发展前景的方法。
1.2 本文主要工作
本文的主要工作是用蚁群算法求解连续空间优化问题。连续对象的优化问
题是日常生产、生活中普遍存在的一类问题,大部分最终可归结为函数的极值
问题,可描述为求 minf(x)或 maxf(x),X={x
1
,x
2
,x
3
,…,x
n
}。通常这些
函数是非常复杂的,主要表现为多变量、多约束、非线性、非凸、不可微、多
极值等特性。蚁群算法较好地模拟了自然界蚂蚁群体的觅食过程,仿真实验也
1
蚁群算法在求解连续空间优化问题中的应用研究
取得了较成功的结果
[8]
。但蚁群算法有一个显著的特点:整个算法过程适用于
离散对象问题。该算法在求解组合优化问题过程中,路径是离散和有限的,蚂
蚁的每一步选择都是在离散值中进行的,将其直接应用于一般常规的连续对象
优化问题存在一定的困难。虽然后来许多研究者做了很大努力,该算法已得到
了改进,但是它在求解连续空间寻优问题方面的优越性还是比较弱的。本文提
出一种求解连续空间优化问题的蚁群算法模型,取得了较好的效果。详细内容
将在后面的章节中介绍。
1.3 本文组织结构
本文的主要结构如下:
第一章:简单介绍蚁群算法的研究背景及本文的主要工作;
第二章:简述蚁群算法的产生、算法概述、算法优缺点,并指出它在解决
组合优化问题方面的长处及其在解决连续优化问题方面的不足;
第三章:介绍基本蚁群算法模型,以及它的工作原理及实现方法;
第四章:提出求解连续空间优化问题的蚁群算法模型,并通过实验证明该
模型用于一般函数优化效果良好,具有应用价值;
第五章:蚁群算法已在许多领域取得了成功的应用,但是仍有许多尚待研
究和解决的问题。
2
忻州师院计算机系本科学士学位论文
2 蚁群算法简介
2.1 蚁群算法的产生
蚂蚁是自然界中常见的一种生物,在昆虫世界,蚂蚁是一种群居的世袭大
家庭,我们称之为蚁群(ant colony)。人们对蚂蚁的关注大都是因为“蚂蚁搬
家,天要下雨”之类的民谚。然而随着近代仿生学的发展,这种似乎微不足道的
小东西越来越受到学者们的关注。1991 年意大利学者 M.Dorigo 等人首先提
出了蚁群算法(ant colony algorithm),人们开始了对蚁群的研究:相对弱小,
功能并不强大的个体是如何完成复杂的工作的(如寻找到食物的最佳路径并返回
等),因此在此基础上,蚁群算法从对蚁群行为的研究中产生且逐渐发展起来。
蚁群具有高度组织的社会性,彼此间的沟通不仅可以借助触觉、视觉的联
系,在大规模的协调行动上可以借助外激素(pheromone)之类的生产化信
息介质。蚁群的觅食行为是最易观察的,每只蚂蚁具有如下的职能:平时在巢
穴附近作无规则行走,一旦发现食物,如果独自能搬的就往回搬,否则就回巢
搬兵,一路上它会留下外激素的嗅迹,其强度通常与食物的品质和数量成正比
若其他蚂蚁遇到嗅迹,就会循迹前进,但也会有一定的走失率(选择其他路
径),走失率与嗅迹的强度成反比。
2.2 蚁群算法概述
蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法,也是
一种模拟进化算法,意大利学者 Dorigo 等人充分利用了蚁群搜索食物的过程
与著名的旅行商问题之间的相似性,通过人工模拟蚂蚁搜索食物的过程(即通
过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径)来求
解 TSP 问题。为了区别于真实蚂蚁群体系统,我们称这种算法为“人工蚁群算
法”。仿生学家们经过大量细致的观察研究发现,生物世界中的蚂蚁在搜索食物
时,能在其走过的路径上释放一种信息素,使得在一定范围内的其他蚂蚁能够
觉察到并影响其搜索行为。蚂蚁个体之间是通过一种称为外激素的通讯介质来
相互传递信息的,从而相互协作,完成复杂的任务。
人工蚂蚁算法就是受到人们对自然界中真实的蚁群集体行为研究成果的启
发,而提出的一种基于种群的模拟进化算法,属于随机搜索全局优化算法。与
其它模拟进化算法一样,通过多个候选解组成的群体的进化过程并以最大概率
逼近问题的最优解。
2.3 蚁群算法的优缺点
蚁群算法是一种随机搜索算法。诸多研究证明,蚁群算法具有很强的寻优
能力,不仅利用正反馈原理,在一定程度上加快了寻优过程,而且是一种本质
并行算法,不同个体之间进行信息交流和传递,从而相互协作,有利于发现更
好解。它具有以下优点
[10]
:
(1)较强的鲁棒性(即通用性):对基本蚁群算法模型稍加修改,便可
以应用于其他问题。
(2)分布式计算:蚁群算法是一种基于种群的进化算法,具有本质并行
性,易于并行实现。
(3)易于与其它方法结合:蚁群算法很容易与多种启发式算法结合,以
3
剩余21页未读,继续阅读
资源评论
- lhzh72013-09-17用来交作业不错
god168
- 粉丝: 2
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 人脸检测-使用OpenCV实现的动漫+漫画人脸检测算法-附项目源码-优质项目实战.zip
- 道路贴图,材质材料免费
- 58234458141025
- 人脸检测-基于OpenCV+Node.js+WebSockets实现的实时人脸检测应用-附项目源码-优质项目实战.zip
- 一些常见的MySQL死锁案例-mysql-deadlocks-master(源代码+案例+图解说明)
- UE4动画烘焙器-ue4.27
- 新建文件夹.zip
- 1103a2a791bbd96ea98021062e327495b1c422e32fb27e0c2d6404b1bd74b692.gif
- 同城相亲交友php小程序
- stm32f103实现的按键FIFO
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功