完整版人工鱼群法在组合优化问题的研究毕业设计.docx
《完整版人工鱼群法在组合优化问题的研究毕业设计.docx》由会员分享，可在线阅读，更多相关《完整版人工鱼群法在组合优化问题的研究毕业设计.docx（18页珍藏版）》请在冰点文库上搜索。
完整版人工鱼群法在组合优化问题的研究毕业设计
学生毕业设计（论文）
课题名称
人工鱼群法在组合优化问题的研究
姓名
何少武
学号
院系
数学与计算科学学院
专业
数学与应用数学
指导教师
林仁讲师
2013年4月23日
湖南城市学院本科毕业设计（论文）诚信声明
本人郑重声明：
所呈交的本科毕业设计（论文），是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本设计（论文）不含任何其他个人或集体已经发表或撰写过的作品成果。
对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。
本人完全意识到本声明的法律结果由本人承担。
本科毕业设计（论文）作者签名：
二○年月日
目录
摘要...........................................................1
关键词.........................................................1
Abstract......................................................1
Keywords......................................................1
1绪论.............................................................2
1.1课题背景及意义................................................2
1.2课题的研究现状...............................................2
2解决组合优化问题的几种智能算法.................................3
2.1遗传算法....................................................3
2.2蚁群算法.....................................................4
2.3粒子群算法..................................................5
2.4几种智能算法特点.............................................6
2.5小结.......................................................7
3基本人工鱼群算法................................................7
3.1人工鱼群算法模型.............................................7
3.2算法描述.....................................................8
3.3算法全局收敛性...............................................11
3.4各参数对收敛性能的影响分析.，.................................12
3.5应用.........................................................12
3.6小结.........................................................12
4总结和展望......................................................14
参考文献.......................................................14
致谢............................................................15
人工鱼群算法在组合优化问题的研究
何少武
摘要：
组合优化问题在现实生活中有着很广泛的应用，并且有很强的工程代表性，但最优化解很困难，目前对组合优化问题的求解主要以启发式算法为主。
人工鱼群算法是一种新的群智能优化算法，其原理简单，收敛速度快，求解精度高。
近年来得到广泛关注和应用。
人工鱼群算法的觅食行为是算法全局收敛的基础，聚群行为和追尾行为更加增强了算法的全局收敛性。
蚁群算法决旅行商问题存在收敛速度慢，而且参数的设定对算法的性能影响很大，而人工鱼群算经过实例证明具有优于蚁群算法的收敛速度。
关键字:
人工鱼群算法;组合优化问题;群聚行为；蚁群算法
Artificialfishalgorithmincombinatorialoptimizationproblem
Heshaowu
Abstract：
Combinatorialoptimizationproblemreallife,andproblemsmainlyalgorithm,theprincipleissimple,fastconvergenceandrecentyearswidespreadconcernandapplications.
Thefeedinglineoftheartificialfishswarmalgorithmisaglobalconvergenceonthebasisofthebehaviorofclustersandrear-endbehaviorandmoretoenhancetheglobalconvergenceofthealgorithm.Antcolonyalgorithmdecisiontravelingsalesmanproblemsofslowconvergenceandparametersettingsaffecttheperformanceofthealgorithm,artificialfishschooloperatorthroughexamplesprovebetterthantheantcolonyalgorithmconvergencerate.
Keywords:
artificialfishswarmalgorithm;combinatorialoptimizationproblems;flockingbehavior;geneticalgorithms
1绪论
1.1课题背景及意义
优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题。
组合优化，又称离散优化问题，是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学中一个经典且重要的分支，随着计算机科学、管理科学、现代化生产技术等的日益发展，这类问题与日俱增，受到诸多学者的高度重视。
典型的组合优化问题有旅行商问题、背包问题、车间作业调度问题、装箱问题、图着色问题、聚类问题等。
这些问题描述简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。
目前常见的启发式算法有遗传算法、模拟退火算法、禁忌搜索算法、人工鱼群算法、蚁群算法、粒子群算法等。
人工鱼群算法是我国学者在2002年提出的一种新的群智能算法。
得到国内外学者的广泛关注，目前处于研究改进阶段。
人工鱼群算法已经成为交叉学科中一个非常活跃的研究问题。
人工鱼群算法对目标函数的性质要求不高，对初值要不高，对参数设定的要求不高，具备全局优化能力，能够快速跳出局部极值点。
具有并行性，简单性，全局性，快速性。
1.2课题的研究现状
优化问题是生产过程中广泛存在的一个问题，经过优化处理后，生产过程系统会降低能量消耗、提高生产效率。
为提供解决优化领域的问题的有效方法，智能搜索算法综合了生物学、计算机和人工智能等各个科学领域的知识，随着各个科学的发展，也是逐渐深入的。
人工鱼群算法是一种新型的智能优化算法，目前用人工鱼群算法解决组合优化问题还是一个比较新的领域。
人工鱼群算法（AFSA）是浙江大学的李晓磊、钱积新等人提出的，2002年李晓磊在其博士论文中对人工鱼群算法进行了系统的介绍。
与其他群集智能算法相比，人工鱼群算法既有相同点又有自己的特点和相异之处。
对TSP问题，优化专家们提出各种不同启发式算法，以得到该问题的近似优化算法。
这些不同算法的共同目的是尽量提高其解的精度。
各类启发式算法是目前比较理想的算法，适用于不同规模和时间要求的TSP问题，他们都可以得到局部最优解或全局最优解。
近年连来有很多的国内外学者在研究遗传算法，粒子群算法解决TSP问题。
并且取得了一定的成效。
JSP问题的研究广泛吸收遗传算法，粒子群算法，人工神经网络，模拟退火算法的精髓。
解决TSP问题主要有三步:
JSP仿生，创建JSP遗传算法所需要的材料，包括JSP染色体以及个体群组;JSP遗传进化创造JSP遗传算法所需要的遗传算子，包括选择，交叉，变异，组合算子，同时设定遗传进化参数;JSP仿真，以JSP的实际需求为依据，定义JSP遗传算法所需要的JSP个体适应度，并设计JSP个体适应度的求解方法。
2解决组合优化问题的几种智能算法
2.1遗传算法
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体（individual）组成。
每个个体实际上是染色体（chromosome）带有特征的实体。
染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。
因此，在一开始需要实现从表现型到基因型的映射即编码工作。
由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。
这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
与传统的优化算法相比，遗传算法具有以下特点:
（1）遗传算法从问题解的串集开始搜索，而不是从单个解开始。
这是遗传算法与传统优化算法的极大区别。
传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。
遗传算法从串集开始搜索，覆盖面大，利于全局择优。
（2）遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。
（3）遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。
适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。
这一特点使得遗传算法的应用范围大大扩展。
（4）遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。
（5）具有自组织、自适应和自学习性。
遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。
2.2蚁群算法
蚁群算法，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。
它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。
针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。
与遗传算法，模拟退火算法等模拟进化算法一样，通过候选解组成的群体在进化过程中来寻找最优解具有以下特点:
（l）较强通用性，对基本蚁群算法模型稍加修改，便可以应用于其它问题;
（2）分布式计算，蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现;
（3）易与其它方法结合:
蚁群算法很容易与多种启发式算法结合，以改善算法的功能;
诸多研究表明，蚁群算法具有很强的寻优能力，不仅利用了正反馈原理，而且是一种本质并行算法，不同个体之间不断进行着信息交流与传递，从而能够相互协作，有利于发现较好的解。
蚁群算法解决组合优化问题的主要步骤有:
（l）设置参数，初始信息踪迹。
（2）对于蚁群中的每只蚂蚁，每个解构造。
蚂蚁按照信息素及启发式信息的指引构造一步问题的解，进行局部信息素更新。
（3）以某些已获得的解为起点进行邻域搜索.（4）根据某些己知获得的质量进行全局信息素更新。
（5）如果不满足结束条件，再转到
（2）。
（6）达到条件，结束。
以上算法中，蚂蚁逐步构造问题的可行解，在一步解构造过程中，蚂蚁以概率方式选择信息素强且启发式因子高的弧达到下一个节点，直到不能继续移动为止。
此时，蚂蚁走过的路径对应求解问题的一个可行解。
局部信息素更新针对蚂蚁当前走过的一步路径上的信息素进行，全局信息素更新是在所有蚂蚁找到可行解之后，根据发现解的质量或者当前算法找到的最好路径上的信息素进行更新。
蚁群算法的参数的选择更多还是依靠实验和经验，没有定理来确定解决组合优化问题的几种智能算法，而且计算时间偏长。
我们以求解平面上个城市的JSP问题（1，2，…，表示城市序号）为例说明蚁群算法的模型。
个城市的TSP问题就是寻找通过个城市各一次且最后回到出发点的最短路径。
为模拟实际蚂蚁的行为，首先引人如下记号：
设是蚁群巾蚂蚁的数量。
（=1，2...）表示城市和之间的路径上残留的信息量。
来模拟实际蚂蚁的信息素浓度。
在初始化的时候，个蚂蚁被放置在不同的城市上，赋予每条边上的信息量为（0）。
每个蚂蚁的的第一个元素赋值为它所在的城市。
用表示在￡时刻蚂蚁由城市转移到城市的概率，则
=
（1）
其中表示蚂蚁下一步允许走过的城市的集合，它随蚂蚁的行进过程而动态改变；信息量随时间的推移会逐步衰减，用1-表示分别表示蚂蚁在运动过程中所积累的信息量及启发式因子在蚂蚁选择路径中所起的不同作用,为由城市转移到城市的期望程度可根据某种启发算法而定。
经过个时刻。
蚂蚁走完所有的城市，完成一次循环。
此时，要根据下式对各路径上的信息量作更新：
（2）
其中：
=（3）
表示蚂蚁在本次循环中在城市和城市之间留下的信息量，其计算方法根据计算模型而定，在最常用的antcyclesystem模型中；
=
（4）
其中为常数,为蚂在本次循环中所走路径的长度。
2.3粒子群算法
粒子群算法，也称粒子群优化算法（ParticleSwarmOptimization），缩写为PSO，是近年来发展起来的一种新的进化算法（Evolu2tionaryAlgorithm-EA）。
PSO算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”（Crossover）和“变异”（Mutation）操作，它通过追随当前搜索到的最优值来寻找全局最优。
这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。
设想这样一个场景：
一群鸟在随机搜索食物。
在这个区域里只有一块食物。
所有的鸟都不知道食物在那里。
但是他们知道当前的位置离食物还有多远。
那么找到食物的最优策略是什么呢。
最简单有效的就是搜寻目前离食物最近的鸟的周围区域。
PSO从这种模型中得到启示并用于解决优化问题。
PSO中，每个优化问题的解都是搜索空间中的一只鸟。
我们称之为“粒子”。
所有的例子都有一个由被优化的函数决定的适应值（fitnessvalue），每个粒子还有一个速度决定他们飞翔的方向和距离。
然后粒子们就追随当前的最优粒子在解空间中搜索。
PSO初始化为一群随机粒子（随机解）。
然后通叠代找到最优解。
在每一次叠代中，粒子通过跟踪两个"极值"来更新自己。
第一个就是粒子本身所找到的最优解。
这个解叫做个体极值pBest.另一个极值是整个种群目前找到的最优解。
这个极值是全局极值gBest。
另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。
在找到这两个最优值时,粒子根据如下的公式来更新自己的速度和新的位置
v[]=w*v[]*rand（）*（pbest[]-present[]）*rand（）*（gbest[]-present[]） （a）
present[]=persent[]v[] （b）
v[]是粒子的速度,w是惯性权重,persent[]是当前粒子的位置.pbest[]和gbest[]如前定义rand（）是介于（0，1）之间的随机数.,是学习因子。
通常==2，大多数情况0≤=≤4在每一维粒子的速度都会被限制在一个最大速度，如果某一维更新后的速度超过用户设定的，那么这一维的速度就被限定为.
2.4几种智能算法特点
遗传算法发展历史长，理论基础完备，已经在组合优化领域取得巨大成功。
遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。
具有自组织、自适应和自学习性。
但是，由于遗传算法是基于个体竞争这样一种机制，使得算法后期多样性匾乏，降低算法效率。
蚁群算法鲁棒性强，具有优越的正反馈机制，每个个体只能感知局部的信息，一不直接使用全局信息;个体可改变环境、并通过环境来进行间接通讯;是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会求得全局最优解;其优化过程不依赖于优化问题本身的严格数学性质，如连续性，可导性及目标函数和约束函数的精确数学描述;是一类基于多主体的智能算法，各主体之间通过相互协作来更好地适应环境;具有潜在的并行性，其搜索过程不是从一点出发，而是从多个点同时过行，这种分布式多智能体的协作是异步并发进行的，分布并行的模式将大大提高整个算法的运行效率和快速反应的能力。
蚁群算法在构造解的过程中，随机选择策略增加了生成解的随机性，接收了解在一定程度上的退化，使得搜索范围在一段时间内保持足够大这样影响了算法的收敛速度。
粒子群算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解，它具有概念简单容易实现，搜索速度快，搜索范围大的突出优点，粒子群算法参数少，原理简单，易于编程实现最初是用来解决连续优化问题，一般采用实数编码。
由于粒子群算法粒子间快速的信息交换，使得粒子群算法早期收敛速度较快，但是这种信息交换方式是建立在粒子都向最优方向移动机制的基础上，使得粒子趋向同一化，所以到寻优后期算法容易陷入局部最优。
2.5小结
本章主要介绍了遗传算法，蚁群算法几种智能算法的基本理论和求解组合优化问题的的基本步骤和方法，总结了这几种智能算法的优缺点，为本课题在研究人工鱼群算法求解组合优化问题提供参考。
3基本人工鱼群算法
人工鱼群算法（ArtificialFishschoolAlgofithm）是一种基于模拟鱼群行为的优化算法，在基本AFSA中，主要是利用了鱼群的觅食、聚群和追尾行为，从构造一条鱼的底层行为做起，通过鱼群中各个体的局部寻优，达到全局最优值在群体中突现出来的目的。
该算法具有良好的克服局部极值、取得全局极值的能力。
并且算法中只使用目标函数的函数值，无需目标函数的梯度值等特殊信息，对搜索空间具有一定的自适应能力.算法对初值无要求，对各参数的选择也不很敏感。
动物在进化过程中，经过漫长的自然界的优胜劣汰，形成了形形色色的觅食和生存方式，这些方式为人类解决问题的思路带来了不少启发和鼓舞。
动物一般不具备人类所具有的复杂逻辑推理能力和综合判断能力的高级智能，它们的目的是在个体的简单行为或通过群体的简单行为而达到或突现出来的。
3.1人工鱼群算法模型
人工鱼群算法是一种基于行为的人工智能思想,通过鱼在水里的行为方式模拟构建了一种鱼群模式,用来解决寻优问题,从而产生了一种新型的智能算法。
在一片水域中，鱼生存的数目最多的地方就是本水域中富含营养物质最多的地方，根据这一特点来模仿鱼群的觅食等行为，从而实现全局最优，这就是鱼群算法的基本思想。
鱼群的活动中，觅食行为，聚群行为，追尾行为和随机行为与寻优命题的解决有着密切的关系，如何利用简单有效的方式来构造实现这些行为是算法实施的主要问题。
觅食行为主要认为就是循着食物多的方向游动的一种行为，在寻优算法中则是向较优方向前进的迭代方式，如鱼群模式中的视觉概念。
在聚群行为中，我们借鉴Reynolds的思想（Reynolds1987），我们对每条人工鱼规定了这样两个规则:
l）尽量向临近伙伴的中心移动。
2）避免过分拥挤，这样就基本实现人工鱼的聚群能力。
追尾行为就是一种向临近的最活跃者追逐的行为，在寻优算法中可以理解为是向附近最优伙伴前进的过程。
算法采用自上而下的设计方法，所以首先着重构造人工鱼的模型，采用面向对象的技术，并用C+十语言的伪代码形式来说明。
人工鱼的模型用如下描述:
ClassArtificial_fish
{
Various:
floatAF_X[n];AF’sposition
floatAF_step;distancethatAFcanmoveforeach
floatAF_visual;visualdistanceofAF
floatAF_number;attemptimeunthebehaviorofprey
floatdelta;conditionofjamming
Function;
floatAF_foodconsistence（）;foodconsistenceofAF’scyrrentposit
floatAF_move（）;AFmovetothenextposition
floatAF_follow（）;behavioroffolllow
floatAF_prey（）;behaviorofprey;
floatAFswarm（）;behaviorifswarm
floatAF_evaluate（）;evaluateandselectthebehavior
floatAF_init（）;initializetheAF
Artificaalfish（）;
};
3.2算法描述
鉴于以上描述的人工鱼行为，每个人工鱼探索它当前所处的环境状况和伙伴的状况，其实伙伴的状况相对于其自身应该也是归属于环境的状况，从而选择一种行为，最终，人工鱼集结在几个局部极值的周围一般情况下，在讨论求极大问题时，拥有较大的AF_foodcinsistence值的人工鱼一般处于值较大的极值域周围，这有助于获取全
升级会员 