一种基于正交离散过程的蚁群算法毕业论文

《一种基于正交离散过程的蚁群算法毕业论文》由会员分享，可在线阅读，更多相关《一种基于正交离散过程的蚁群算法毕业论文（38页珍藏版）》请在装配图网上搜索。

1、郑州航空工业管理学院毕 业 论 文（设 计） XXXXXXXXX 届 机械设计制造及其自动化 专业 班级题 目 基于正交离散过程的蚁群算法 姓 名 XXXXXXXXXX 学 指导教师 XXX 职称 XX 二一 年 五 月 十八 日基于正交离散过程的蚁群算法内 容 摘 要 蚁群算法是一种仿生优化算法，其灵感来源于真实蚁群的觅食机理，这种思想吸收了蚂蚁群体有规律的行为，通过对真实蚁群搜索食物过程的模拟来完成对问题的求解。 本文首先介绍了蚁群算法的研究进展和基本原理，然后对蚁群算法的改进优化和仿真应用分别进行了描述。为了解决蚁群算法在初始阶段执行效率低下、信息素随机分布、路径杂乱无章的缺点，本文采取

2、了几项改进措施。例如：将正交设计方法引入初始化中，创建正交离散过程，形成正交优化的路径设置；优化初始化过程，以便形成初始解；以动态概率转移规则来构造新的路径；精练的选路策略等改进措施的初始路径优化模型。该模型提高了算法的执行效率，其成功应用于解决连续域问题的啤酒配方设计方面，表明该方法是有效可行的，同时开辟了一条解决啤酒配方设计问题的新途径，对蚁群算法解决连续域问题提供了可供参考的模型和求解方法。 关键词蚁群算法；正交设计；正交离散；连续优化；啤酒配方设计 Ant Colony Algorithm based on orthogonal discrete process (Mechanical

3、 and electrical engineering institute, Aviation industry management college in zheng zhou )Abstract The ant colony algorithm is a novel simulated evolutionary algorithm, which is inspired by foraging mechanisms of real ant colonies. This idea absorbs the regular behaviors of the ants colonies, by si

4、mulating the process of the real ant colonys searching for food to solve the problems.The current research progresses and basic principle of ant colony algorithm are firstly introduced in this paper, then the improvement optimization and simulation application of ant colony algorithm are also overvi

5、ewed respectively. In order to solve the problems of low efficiency, randomly distributed pheromone, scrambled paths in the initial stage of the ant colony algorithm. Several improved methods of the initial paths optimization model are proposed. For example, the orthogonal design method is introduce

6、d to the initial route optimization course so as to create orthogonal discrete process and form the path settings of orthogonal optimization; The initial course is optimized in order to get the initial solutions; Dynamical transfer rules are used to construct the new paths; Refined routing strategie

7、s and so on. This model enhances the implementation efficiency of the algorithm. And then the beer recipe design simulation application is successfully presented to prove validity and feasibility of the proposed method, consequently, opening up a new way in terms of beer recipe design, and the metho

8、d offers referenced models and solving methods for ant colony algorithm to solve the continual domain problems. Key wordsAnt Colony Algorithm; orthogonal design; orthogonal discretion; continuous optimization; beer recipe design 目 录内容摘要. 1Abstract. 2第一章 绪论61.1 研究背景61.2 国内外对蚁群算法的研究进展71.3 本文的研究主线及体系结构

9、7第二章 蚁群算法92.1 蚁群算法的基本原理及其数学模型92.1.1 真实蚁群的觅食机理92.1.2 基本蚁群算法数学模型的建立112.1.3 基本蚁群算法的系统学特征132.2 基本蚁群算法的具体实现142.2.1 基本蚁群算法的实现步骤142.2.2 基本蚁群算法的程序结构流程图15第三章 基于正交离散过程的蚁群算法173.1 正交试验设计173.1.1 正交试验设计的基本概念173.1.2 正交试验设计的基本原理173.1.3 正交表及其基本性质193.2 基于正交离散过程的蚁群算法203.2.1 正交离散过程蚁群算法的基本原理203.2.2 正交离散过程蚁群算法的寻优过程233.2.

10、3 正交离散过程蚁群算法的数学模型263.3 正交离散过程蚁群算法的具体实现273.3.1 正交离散过程蚁群算法的实现步骤273.3.2 正交离散过程蚁群算法的程序结构流程图273.4 正交离散过程蚁群算法的仿真应用29第四章 本文的工作总结与展望344.1 本文的工作总结344.2 展望34致 谢35参考文献36 第一章 绪论1.1 研究背景根据蚂蚁群体寻找食物的行为，1991年，意大利学者Dorigo M.等人在法国巴黎召开的第一届欧洲人工生命会议上提出了基本蚁群算法的基本模型；1992年，Dorigo M在其博士论文中又进一步描述了蚁群算法的基本原理。蚁群算法是最新发展起来的一种模拟蚂蚁

11、群体智能行为的仿生优化算法，该算法采用了正反馈并行自催化机制，在解决许多实际复杂优化问题方面展现出了良好性能和巨大的发展潜力，近几年吸引了国内外许多学者对蚁群算法进行了多方面的研究工作。国际顶级学术期刊Nature曾多次对蚁群算法的研究成果进行报道，IEEE Transactions On Evolutionary Computation和Future Generation Computer Systems分别在2001年和2003年出版了蚁群算法特刊，在布鲁塞尔每两年召开一次的蚁群算法国际研讨会进一步促进了该仿生优化算法的学术交流，从而使蚁群算法展示出了勃勃生机和广阔的发展前景。目前，这种新

12、生的仿生优化算法已成为在国际智能计算领域中备受关注的前沿性课题和研究热点。1.2 国内外对蚁群算法的研究进展自从1991年意大利学者DorigoM.首次提出蚁群算法以后，蚁群算法逐渐得到了世界许多研究者的关注，其在很多领域得到了很好的应用，在这期间国内外大量有价值的研究成果也陆续发表。2000年，Dorigo M和Bonabeau E等在国际顶级学术刊物Nature上发表了蚁群算法的研究综述，从而把这一领域的研究推向了国际学术最前沿性的课题，鉴于Dorigo M在蚁群算法研究领域做出的的杰出贡献，2003年11月欧盟委员会特别授予他“居里夫人杰出成就奖”。我国在蚁群算法领域的研究也取得了一些令

13、世人瞩目的成就：陈烨在2001年发表了带杂交算子的蚁群算法一文，并且基于Visual Basic开发了一个功能齐全人性化的“蚁群算法实验室”。在2003到2005年间，李艳君、段海滨提出了一种基于网格划分措施的自适应连续域蚁群算法和一种用于求解连续域优化问题的自适应连续域蚁群算法。在2008年，郑松为了解决蚁群算法在解决组合优化问题时收敛速度慢、消耗时间长的缺点，提出将确定性搜索引入基本蚁群算法的搜索过程中，并研究了改进后的蚁群算法在啤酒配方优化设计中的具体应用。1.3 本文的研究主线及体系结构1）本文的研究主线：研究主线是基于正交离散过程的蚁群算法，通过将蚁群算法与正交试验设计相结合，把连续

14、性问题离散化，在常规搜索中创建正交离散过程，优化路径设置提高算法的搜索速度和运行效率。将基于正交离散过程的蚁群算法应用于啤酒原料配方设计实践中，取得了非常好的效果，从而开辟了一种解决连续域变量问题的求解方法。2）本文的体系结构：本文全面地介绍了蚁群算法的理论、方法及其具体实现，按照分析、深化、改进、仿真应用的逻辑结构进行安排，本文共分为四章，其内容基本上构成了一个完整体系，具体而言，各章主要包括如下内容：第一章 阐述了蚁群算法的研究背景及国内外对蚁群算法的研究进展，同时列举了部分改进的蚁群算法及其应用情况，最后给出了本文的研究主线和体系结构。第二章 在介绍蚂蚁的群体觅食行为特征的基础上，从深层

15、意义上进一步分析蚁群算法的机制原理、数学模型、以及具体实现步骤，最后讨论了基本蚁群算法的系统学特征。本章主要内容对基本蚁群算法原理进行分析，也是后面章节对蚁群算法进行改进研究的基础。第三章 详细阐述基于正交离散过程的蚁群算法。分析了正交试验设计的基本原理、正交离散的基本原理、特点，以及正交离散过程蚁群算法实现寻优过程的寻优规则、数学模型，并分析了该改进型蚁群算法在啤酒原料配方设计方面的仿真应用等内容。第四章 对本文的主要内容进行总结，讨论了目前蚁群算法所存在的主要问题，然后从蚁群算法的模型改进、理论分析、并行实现、应用领域等方面对蚁群算法在以后的研究进展方向进行了讨论。第二章 蚁群算法2.1

16、蚁群算法的基本原理及其数学模型2.1.1 真实蚁群的觅食机理 根据研究者的长期观察发现：蚂蚁在运动时会在路径上释放出一种信息素来寻找路径。当它们碰到一个陌生路口时，就任意挑选一条路径前进，同时释放出与路径长度相关的一定强度信息素。蚂蚁走过的路径越长，所释放的信息素就越少。当后来的蚂蚁再次来到这个路口时，选择信息素强度较大路径的可能性较大，这样蚁群之间就会形成一种信息正反馈机制。最短路径上的信息素强度逐渐增大，而其他路径上的信息素强度随着时间的推移而逐渐消减，最终整个蚁群就会找出最佳路径。如图2.1.1（a）所示，我们总可以观察到蚂蚁群体在蚁穴与食物之间形成近似于直线形状的路径，而不是曲线、折线

17、等其他形状。如图2.1.1（b）所示，在蚂蚁运动路线上有障碍物出现时，开始时各只蚂蚁均匀分布，不管路径是长是短，蚂蚁先随机选择各条路径。蚂蚁在运动过程中在经过的路径上留下一定强度的信息素，其他蚂蚁能够感知这种物质的强度，并以此指导自己继续向信息素浓度高的方向移动，如图2.1.1（c）所示，蚂蚁倾向于选择信息素浓度高的路径，在相等时间内，较短路径上遗留的信息素逐渐增多，选择较短路径的蚂蚁也越来越多。蚂蚁集体行为存在着一种信息正反馈现象，即蚂蚁在某一路径上经过的次数越多，后来的蚂蚁就越有可能选择该路径，蚂蚁个体之间就是通过这种信息正反馈机制来搜索食物并最终找到最优路径的，如图2.1.1（d）所示。

18、 图2.1.1 现实中蚁群寻找食物的过程 由上述可见，在整个寻优过程中，虽然单只蚂蚁的寻优能力有限，但是整个蚁群的行为通过信息素的作用便具有非常高的自组织性能，蚂蚁之间交换路径信息素，最终通过蚂蚁的正反馈机制找到最佳路径。2.1.2 基本蚁群算法数学模型的建立蚁群算法首先成功应用于TSP问题，TSP问题就是给定n个城市与城市之间的距离，某一旅行商从某一城市出发，逐个访问各个城市一次且仅一次后再回到原来出发的城市，找出一条最短的巡游路径。下面我们以简单的TSP问题为例来说明蚁群算法基本原理。将m只蚂蚁随机放在n个城市上,设初始时刻各个城市之间每一条路径上的信息素强度=c (c是常数), 表示禁忌

19、表,记录当前蚂蚁所走过的城市集合, 不允许蚂蚁再次访问禁忌表中的城市结点。当n个城市结点都进入禁忌表中时,表示蚂蚁进行了一次完整循环。在搜索当中, 蚂蚁根据状态转移概率来选择各条路径上的城市节点。在t时刻,蚂蚁k（k=1,2,m）由城市i转移到城市j的转移概率为 （1）式（1）中有：表示t时刻路径（i,j）上的信息素强度；表示信息素启发因子，表示蚂蚁在运动过程中积累的信息素所起的作用；是期望启发式因子，表示路径能见度的相对重要程度，反映了蚂蚁在选择路径过程中启发式信息所起的作用；是启发函数，在TSP问题中，通常取=,是相邻两个城市节点之间的距离，启发函数表示蚂蚁k从i城市移动到j城市的期望程度

20、；=1,2,n-表示不在禁忌表中的城市集合，表示蚂蚁下一步要继续搜索的城市集合。为了避免信息素残留的过多引起残留信息掩盖启发信息，在每只蚂蚁走完一步或遍历完所有城市后，要对残留的信息素进行适时更新。在t+n时刻在路径（i，j）上的信息素强度要可按以下公式更新调整：（） （）其中表示蚂蚁在本次循环中路径(i,j)上的信息素增量,设初始时刻。表示蚂蚁k在本次循环中在路径（i,j）上的信息素增量。是信息素挥发系数，1-则表示信息素残留系数，为了防止信息素累积过多，的取值范围应该为：。信息素挥发因子的取值大小影响到蚁群算法的全局搜索效率和收敛速度，信息素残留因子1-表示了蚂蚁个体之间相互影响的程度。根

21、据不同的信息素更新措施，Dorigo M提出了三种基本蚁群算法模型，分别是Ant-Cycle模型、Ant-Quantity模型和Ant-Density模型，它们之间的差别在于的求法有所不同。在Ant-Cycle模型中 （）式（）中,L表示第k只蚂蚁在本次循环中所经过路径的总长度，Q为常数，指信息素强度，表示的是蚂蚁在本次循环中释放在所经过路径上的信息素总量。在Ant-Quantity模型中 （） 在Ant-Density模型中 （）它们的区别在于：式（）和（）中表示的是局部信息素，也就是蚂蚁在走完一步后更新路径上的信息素；而式（）中表示的是整体信息素，即蚂蚁完成一次完整循环后更新所经过路径上的

22、信息素，（4）在求解TSP问题时性能比较好，因此通常采用公式（）作为蚁群算法的基本模型。2.1.3 基本蚁群算法的系统学特征1）基本蚁群算法是一个系统系统强调系统元素之间的相互影响程度以及系统对其中元素的整体作用。蚂蚁群体就构成了一个系统，在该系统中，蚂蚁的个体行为可作为系统中的元素，蚂蚁个体之间的相互影响表现了系统的相关性，而整个蚂蚁群体能够完成个体所完成不了的复杂任务则体现了系统的整体性。在基本蚁群算法中，多只蚂蚁的求解结果明显好于单只蚂蚁的求解结果，因此基本蚁群算法是一个系统。2）分布式计算类似于人体很多细胞相互独立地完成某一项工作，当其中一个细胞停止工作后，人身体的整体功能不会因此而受

23、到影响。蚁群算法也体现了分布式特点。每只蚂蚁个体在整个问题空间的多个节点相互独立地构造问题的解，而整个问题的求解过程不会因为其中某只蚂蚁无法求解而受到影响。分布式特征增强了蚁群算法的可靠性。3）自组织性昆虫群落中的生物个体相互作用，可以协同完成一项集体工作，体现了较强的自组织性能。蚁群算法就体现了自组织性。在算法的初始阶段，单只蚂蚁杂乱无章地寻找解，但是算法经过一段时间的演化过程，蚂蚁越来越倾向于搜索那些接近于最优解的一部分解，这就体现出蚂蚁行为从无序到有序的自组织性。自组织性增强了算法的鲁棒性。4)正反馈从自然界中真实蚁群的觅食行为机制可以发现，蚂蚁之所以能够找到最优路径，主要是由于信息素不

24、断地在较优路径上的累积，而信息素的累积过程就是一个正反馈过程。基本蚁群算法的反馈机制是在较优路径上留下更多的信息素，而更多的信息素又吸引来了更多的蚂蚁，这个过程引导着整个系统不断向最优解的方向进化。以上从系统学方面分析了蚁群算法的机理，可见蚁群算法体现了不同于常规算法的许多新思想，这也正是基本蚁群算法在系统学上研究的意义所在。2.2 基本蚁群算法的具体实现2.2.1 基本蚁群算法的实现步骤 基本蚁群算法的具体实现步骤如下：（）令初始时刻循环次数，设最大循环次数为，将个蚂蚁随机放在个元素节点上，设每条路径（，）的初始化信息量（为常数），初始时刻设置每条路径上的信息素增量。（）循环次数。（）设初始

25、时刻蚂蚁的禁忌表索引号。（）蚂蚁数目。（）蚂蚁个体根据状态转移概率公式（）选择下一个元素，然后继续往前搜索移动，此时。（）选择好下一个元素之后，再将蚂蚁移动到新的元素节点，并把该元素转移到该蚂蚁个体的禁忌表中，此时，。（）如果集合中元素还没有遍历完，即，则跳转到第（）步，否则执行第（）步。（）根据路径上信息量更新公式（）和信息量变化公式（）更新每条路径（，）上的信息量。（）如果满足结束条件，即循环次数，则本次循环结束，输出程序计算的最佳结果，否则清空禁忌表并跳转到第（）步。2.2.2 基本蚁群算法的程序结构流程图基本蚁群算法的程序结构流程图如图2.2.2所示。图2.2.2 基本蚁群算法的程序结

26、构流程图开始初始化迭代次数N=N+1蚂蚁k=1蚂蚁k=k+1按照状态转移概率公式（1）选择下一个元素修改禁忌表=+1k蚂蚁总数m？ 按照公式（2）和公式（3）进行信息素更新满足结束条件？输出程序计算结果结束NNYY第三章 基于正交离散过程的蚁群算法3.1 正交试验设计3.1.1 正交试验设计的基本概念在正交试验要解决的实际问题中，要明确评价试验效果的影响指标，影响试验评价指标者称为因素，因素在试验中变化的状态称为水平。对于单因素或者两因素试验，其因素数较少，试验的设计、安排都比较简单。但在实际生产过程中要研究许多因素多水平对产品指标的影响。例如因素数为a, 因素的水平数为b, 则多因素全面试验

27、方案的次数为次,从试验次数的公式可知, 因素数和水平数增多, 试验次数将会大大增加。例如有5个因素，每个因素有4个水平，若全面试验就要进行次，这样试验规模就会大大增加，给研究工作带来了繁重的任务, 而且也会消耗大量时间、原材料和财力。正交试验设计就是利用正交表来安排、分析多因素多水平试验的一种设计方法。它是从全面试验的全部水平组合中，挑选出一部分代表性很强的水平组合进行试验，通过分析这部分有代表性水平组合的试验结果，来了解全面试验的情况，减少试验次数，从而找出最优水平组合。3.1.2 正交试验设计的基本原理在试验安排中，当因素水平数不多时，适合进行全面试验，例如，一个三因素三水平试验，各因素各

28、水平之间的全部水平组合就有33=27种。可以用一个立方体来表示多因素试验的选优区域，对于3因素3水平试验，就可以选择有27个网格点的立方体作为选优区，如果这27个格点都进行试验，就是全面试验。全面试验的数据试验点分布如图3.1.21所示。图3.1.21 全面试验的数据试验点分布由图可见：全面试验数据均匀分布，各个因素水平全面搭配，缺点就是试验次数太多，如果是5因素4水平试验，全面试验的话就要进行次试验，这会因实验条件的实际限制而难于实施，因此全面试验适用于因素水平数不多的情况下。正交试验设计就是从全面试验点中挑选一部分具有代表性的试验点来进行试验。对于3因素3水平而言，设有A,B,C三个因素，

29、A因素有三个试验水平，B因素有三个试验水平，C因素有三个试验水平，利用正交表 从27个试验点中挑选出9个试验点，这9个试验点为：（1）；（2）；（3）;（4）;（5）;（6）;（7）;（8）;（9）。这种选择保证了A因素的3个水平与B、C因素的3个水平在试验过程中各搭配一次，对于A、B、C这3个因素来说，正交试验次数仅是全面试验次数的三分之一，这样就大大减少了试验次数。正交试验设计的数据试验点在立方体选优区中的分布如图3.1.22所示:图3.1.22 正交试验设计的数据试验点分布 从图3.1.22中可以看到，9个试验数据点在选优区中均衡分布，在立方体的每个平面上恰好只有3个试验点，在立方体的每

30、条线上恰好只有1个试验点。所选的这9个试验点在整个立方体内均衡分布，代表性很强，能够全面反映整个立方体选优区内的基本情况。因此它们能很好地代表27次全面试验的情况，这就是正交试验设计的优点。3.1.3 正交表及其基本性质正交表是正交试验设计的基本工具，正交试验设计安排以及分析试验结果都要用到正交表，合理选用正交表是正交设计的基础。常用的正交表已经规范标准化，我们根据试验需要从参考书中选取合适的正交表。正交表的记号为，其中L代表正交表，是试验次数即正交表的行数，b表示水平数，表示因素数即列数。正交表的基本性质如下：1）正交性：在正交表中任意一列中，某因素的所有水平都出现，且出现的次数是相等的，在

31、任意两列之间，两因素的各种不同水平组合都出现，并且出现的次数也相等。2）均衡分布性：在正交表中的各因素水平组合在选优区中均衡分布。例如图3.1.22所示，在立方体中，每一平面内只有3个数据试验点，每一条直线上只包含1个试验点，正交试验点均衡分布在全面试验点中。3）独立性：正交表中没有完全重复的水平组合，从全面试验组合中挑出的这一部分试验组合没有重复试验的情况，在讨论某一因素时，不用考虑其他因素的影响，正交表中的试验方案能够综合处理大量的信息。4）整齐可比性：整齐可比是指各个因素的各个水平之间具有可比性。正交表中某一因素的各个水平都均匀搭配着其他因素的各个水平。如在3因素3水平试验中的A、B、C

32、3个因素，A因素的3个水平A1、A2、A3各搭配 B、C两因素的3个不同水平，即：（1）；（2）；（3）;（4）;（5）;（6）;（7）;（8）;（9）。在这9个水平组合中，A因素下的3个水平分别组合了B、C两因素的3个水平，且任意两个水平组合不会有重复的情况。A因素3水平之间具有整齐可比性。同理B、C两因素的3水平间也具有整齐可比性。3.2 基于正交离散过程的蚁群算法3.2.1 正交离散过程蚁群算法的基本原理传统基本蚁群算法在实际应用中主要是解决离散域的组合优化问题，而难于解决连续域变量的函数优化问题，在原料配方设计等连续变量领域中应用困难。然而正交试验设计可以综合处理大量信息，有效地解决连

33、续域变量问题。正交离散主要是将基本蚁群算法与正交试验设计相结合，通过正交设计形成正交离散点，使连续域问题离散化，让蚂蚁在正交试验得出的几条优化路径中寻找最优解，改进了初始阶段蚁群算法信息素随机分布、路径杂乱无章的缺点，最终可以取得满意的结果。以原料配方设计为例进一步说明正交离散过程的蚁群算法。设原料品种（）为横坐标，原料用量为，原料品种所占的比例从0100连续均匀变化，属于典型的连续域变量问题。由于从0100之间有无穷多个节点，若用基本蚁群算法，那么蚂蚁将会从start点开始访问无穷多个节点，这样必然会造成庞大的计算量而无限延长计算时间，所求的结果也会比较分散，所以应把问题离散化。在正交试验优

34、化中，以品种数作为因素数，每个原料品种在所占比例范围内选定水平数。例如：有四个原料品种，也就是有四个因素，每个品种有三个水平，也就是4因素3水平正交试验，则选用正交试验表，产生12个正交离散节点，组成9个初始配方组合，让初始蚂蚁在这9个初始路径中释放一定的信息素，然后运行蚂蚁更加趋向于从这9个配方组合中寻找适应解配方，最终确定最优解，这样就实现了把连续性问题离散化处理了。原料成分离散化及配方搜索图如图3.2.1所示： 0100各原料所占的质量分数图3.2.1 原料正交离散及配方搜索图Startend品种因素 为了能够有效运用正交离散的蚁群算法，要把研究对象离散化成如图3.2.1所示的形式，这样

35、就大大缩小了搜索范围，在很大程度上改善了寻优性能，极大缩短了计算时间。首先挑选四个原料品种作为四个因素，即品种，每个因素再选择三个水平，即因素有三个水平、因素有三个水平、因素有三个水平、因素有三个水平，由正交试验表可知可以组成9个初始配方组合，也就是如图3.2.1所示的9条已经初始化一定量信息素的路径，即（1）；（2）；（3）;（4）;（5）;（6）;（7）;（8）;（9）。创建正交试验表，如表格3.2.2所示:表3.2.2 因素水平正交试验分配方案表因素试验编号ABCD1A1B1C1D12A1B2C2D23A1B3C3D34A2B1C2D35A2B2C3D16A2B3C1D27A3B1C3D

36、28A3B2C1D39A3B3C2D1如图3.2.1所示，一只蚂蚁从Start点开始出发，逐步经过每个品种上的正交离散节点，最后到达代表最后一个品种的end点，完成一次循环就形成一个完整的配方，多只蚂蚁循环上述过程便形成多种配方组合。通过对原料用量正交离散化处理，大大减少了搜索初始解集的试验配方次数，提高了蚁群算法的运算效率。由图3.2.1可见，这12个正交离散点所组成的配方组合总共有种，而这81条路径具有很强的代表性，它们可以代表原料比例在0100范围内全面试验的无穷多条路径，而正交试验中的9种初始化配方组合代表了所挑选的这部分全面试验中的81种配方组合。根据专业知识和实践经验，再对所研究问

37、题具体分析，明确哪几个因素及其哪几个水平对试验指标的影响比较大，然后再挑选这几种因素及其水平进行试验。在正交表3.2.2中确定的9种优化组合配方中很有可能存在最佳配方，也就是说蚂蚁最有可能在这已经初始化一定信息素的9条路径中搜索到最优解，比如图3.2.1中加黑加粗的那条路径2，即配方组合有可能是最优解。但是除了这9条路径之外的其它72条路径中的一条配方组合也有可能是最优解，只不过这9条路径中的一条成为最优解的可能性比较大，而其他72条路径成为最优解的可能性比较小而已。这种方法将会克服基本蚁群算法随机搜索无规律、效率低、结果分散的缺陷，在很大程度上提高了蚁群算法的求解精度。因此，基于正交离散过程

38、的蚁群算法能很好地解决连续域变量的配方组合优化问题。3.2.2 正交离散过程蚁群算法的寻优过程在正交优化过程中，蚂蚁主要有初始蚂蚁和运行蚂蚁两种。初始蚂蚁的主要任务是在图3.2.1中的9条正交优化路径上释放一定的信息素，即蚂蚁初始化信息素（为常数）。蚂蚁从start点出发进行寻优，结束于end点，在寻优过程中，相邻两个因素的各个水平节点之间都存在连接路径，蚂蚁在各个水平节点之间按照动态概率转移规则构造新的路径，当所有的蚂蚁遍历完后，就可以找出最优解。在蚂蚁创建优化解的过程中，蚂蚁逐个访问各个离散节点，位于节点r上的蚂蚁根据伪随机比例规则选择下一个将要访问的节点s，单个蚂蚁在遍历的过程中根据信息

39、素局部更新规则对它所经过的路径进行信息素更新，当所有的蚂蚁遍历完所有的节点后，再按照全局信息素更新规则对所经过的路径进行信息素更新。 1）伪随机比例规则：该规则主要是在蚂蚁探索一条新路径和根据蚂蚁所积累的搜索经验开发一条新路径这两者之间保持体一种平衡状态。位于节点r的蚂蚁k利用以下规则选择下一个将要访问的节点s： （7） 式（7）中，函数argmaxf(x)表示寻找最优解的参量，表示的是定义域中的一个子集，而该子集中的任一元素都可使函数f(x)取得最优解。表示蚂蚁k下一步要访问的节点集合，表示路径（r,j）上的信息素强度，=,表示启发式信息。q是服从均匀分布的一个随机数，是自定义的一个参数。S

40、是根据以下的概率公式（8）计算得来的随机变量。 （8）由式（7）和（8）决定的状态转移规则被称为伪随机比例规则。伪随机比例规则使蚂蚁更倾向于选择距离短且信息素浓度高的路径。参数决定了“探索”一条新路径和利用蚂蚁积累的有效搜索经验“开发”一条路径这两种过程之间的相对重要程度。参数要根据路径信息素分布情况和寻优目标适时地进行调节，这样可以发挥在选择节点、寻找最优解过程中的作用。蚂蚁在开始时的 、中间选择节点时的和最终找到最优解时的都应适时地进行调节，这样在初始阶段可以加快算法运算的速度，在寻优过程中又可以避免算法陷入局部最优状态。当蚂蚁从节点r向节点s移动时，它会选择一个随机数，如果，按照（7）式

41、根据启发式信息和信息素强度选择最优路径，否则按照（8）式的随机比例规则选择下一步要移动的路径。2）信息素全局更新规则：当蚂蚁访问完所有的节点以后，只增强那些属于最短路径上的信息素浓度，信息素全局更新规则使蚁群算法寻找最优解的过程具有更强的指导性。当所有的蚂蚁遍历完所有的节点之后，按照以下的公式进行信息素全局更新： （9） （10）其中参数（）是信息素衰减系数，表示试验开始至今所找到的全局最短路径的长度。3）信息素局部更新规则：单个蚂蚁在节点之间遍历时按照信息素局部更新规则对所经过路径上的信息素进行更新： （11）其中参数是信息素挥发系数。实验表明，（是初始化信息素）时算法的效果比较好。应用信息

42、素局部更新规则会使蚂蚁经过路径上的信息素减少一部分，这样后来的蚂蚁选择这些路径的可能性就会地减少了，从而增强了算法的“探索”能力，有效地避免了算法进入局部停滞状态，避免蚂蚁收敛到同一条路径。3.2.3 正交离散过程蚁群算法的数学模型目标函数根据所研究问题的实际限定因素而设定，例如：目标函数： (12)表示经济目标比如最大利润、最低成本等；表示各种原料的价格系数；表示各种原料在配方中的比例（）；n为变量数。根据配方中各原料用量的相关标准确定约束条件：（13）为约束值，也就是配方应该满足的各项指标（原料重量、营养价值等指标）；为各种原料的相应化学成分含量；m为约束方程的个数。 3.3 正交离散过程

43、蚁群算法的具体实现3.3.1 正交离散过程蚁群算法的实现步骤正交离散过程蚁群算法具体实现步骤如下所示：第一步：明确正交离散过程蚁群算法需要解决的实际问题。 第二步：根据实际问题确定目标函数，根据实际限定因素确定约束函数条件，建立正交离散过程蚁群算法的基本数学模型。 第三步：根据正交设计优化路径设置，将研究对象正交离散化处理。 第四步：初始蚂蚁在正交试验设计中所确定的几条优化路径中释放一定量的信息素，对蚁群算法参数进行初始化。然后运行蚂蚁根据初始蚂蚁建立的路径信息素强度和启发信息按照伪随机比例规则运行，进行全局范围内的搜索寻优移动。 第五步：适时调节参数，动态调整状态转移概率，优化路径设置。 第

44、六步：动态地进行信息素局部和全局更新优化，以提高寻优效率。 第七步：如果满足结束的条件，计算目标函数值，否则回到第二步。第八步：最终输出程序计算的最佳结果。3.3.2 正交离散过程蚁群算法的程序结构流程图正交离散过程蚁群算法的程序结构流程图如图3.3.2所示：开始明确研究问题定义目标函数、约束函数条件，建立数学模型正交离散化初始化蚁群算法参数状态转移概率优化信息素动态更新优化进行选路寻优计算满足结束条件？计算目标函数值输出程序计算最佳结果结束N迭代 Y 图3.3.2 正交离散过程蚁群算法的程序结构流程图3.4 正交离散过程蚁群算法的仿真应用配方试验设计就是连续域变量优化问题，在满足实际意义的约

45、束条件下，求解各种原料配方的最佳比例，使问题的目标函数值达到最大或最小的效果。下面以啤酒原料配方设计为例对正交离散过程蚁群算法进行仿真应用验证。啤酒配方主要包括多种大麦和大米等原料，这些原料糖化处理制成麦汁，再经过发酵制成啤酒。以某企业所要求的具体生产指标和原料种类为例对该算法进行仿真验证。假设该企业可提供的原料种类有以下几种：宁麦加麦、宁麦澳麦、宁麦哈默林、九源甘三、九得利KA4B、宝应甘三、小麦麦芽和大米。不同原料具有各自不同的营养参数属性，具体营养标准如表3.4.1所示： 表3.4.1 啤酒原料营养参数标准麦芽品种单价/（元/kg）产槽率/（L/kg）氨基氮/（mg/100g）总可溶性氮

46、/（mg/100g）葡萄糖/（mg/100g）糖化力/（WK/100g）宁麦加麦2.702180695155335宁麦澳麦2.712165650125350宁麦哈默林2.703205795120405九源甘三2.372200805175320九得利KA4B2.403205795210405宝应甘三2.393206796185410小麦麦芽2.411.5195105590485大米1.850.360000该啤酒企业要求的啤酒原料配方各项生产指标主要有5个约束条件：（1）保证糟层的厚度不低于22cm;(2)保证麦汁氨基氮的含量在160mg/L210mg/L范围内;(3)保证麦汁总可溶性氮含量在65

47、0mg/L1000mg/L范围内；（4）保证麦汁葡萄糖含量90mg/L250mg/L范围内；（5）保证原料的糖化力在1600WK/kg2100WK/kg范围内。参考该啤酒企业的原料配方设计手册，定义算法所研究问题的数学模型如下：目标函数为最低成本函数： （14）约束条件为各种期望生产指标： （15） （16） （17） （18） （19） 在以上各式中，表示一批次所需要的啤酒原料总质量；表示过滤槽设备的直径；表示第种原料的成本单价；表示配方中第种原料所占的百分比含量；表示第种原料糖化力的数值；表示第种原料总氮含量；表示第种原料氨基氮的含量；表示第种原料葡萄糖含量；表示第种原料产槽率。优化的最终

48、目标就是实现原料的总成本最低，即定义函数为最终目标函数。啤酒原料麦芽品种所占的百分比含量在0100范围内均匀变化，属于典型的连续变量优化问题，由于从0到100之间有无穷多个节点，如果让蚂蚁在0100范围内逐个进行访问的话，必然会造成庞大的计算量而无限延长计算时间，求解的结果也会比较分散，因此无法用传统的蚁群算法对其进行研究，必须把原料用量正交离散化处理。在对研究对象进行正交离散化处理的过程中，根据啤酒原料营养标准手册和相关实践经验确定几个对试验指标效果影响比较大的因素数以及水平数。以宁麦澳麦、宁麦哈默林、宝应甘三、九得利KA4B、九源甘三、小麦六种主要啤酒原料配方为基础，作为正交试验设计中的六

49、个因素，每种原料可确定五个用量比例等级，根据相关配方手册和实践经验，啤酒原料用量的最佳比例应该在这五个数量比例范围之内，然后将其作为正交设计中的五个水平，即6因素5水平的正交试验。采用正交表，创建正交离散配方搜索图，产生30个正交离散点，进行25次试验，并产生25个初始配方组合，即产生25条初始化优化路径。各原料参数正交试验水平表如表3.4.2所示： 表3.4.2 各原料参数正交试验水平表因素水平宁麦澳麦宁麦哈默林宝应甘三九得利KA4B九源甘三小麦10.54.08.05.59.07.521.05.08.56.59.58.531.56.09.07.510.09.542.07.09.58.510.

50、510.552.58.010.09.511.011.5根据啤酒原料配方设计的数学模型采用基于正交离散过程的蚁群算法求解程序，即根据图3.3.2 正交离散过程蚁群算法的程序结构流程图进行运算，运算步骤如下所示：（1）根据相关标准和实践经验从研究对象中挑选6个因素，每个因素5个水平如表3.4.2所示，构建正交离散原料配方搜索图，由此可产生30个正交离散节点，形成25个初始化优化路径。（2）让初始蚂蚁在这25条试验路径上初始化一定量的信息素，优化路径设置，运行蚂蚁根据此信息素强度寻优，将试验对象正交离散化。（3）让m只蚂蚁从start点开始出发，每只蚂蚁独立地按照（7）式和（8）式组成的伪随机比例规

51、则追踪生成配方方案。（4）排除不满足该企业生产指标的不可行方案，然后按照公式（14）计算可行方案的目标函数值并保存其最小值，把方案记为当前最好方案。（5）对于找到可行方案的蚂蚁所经过的路径按照公式（9）、（10）和（11）进行信息素局部和全局更新优化。（6）若满足结束条件，即如果循环次数，则循环结束，输出程序计算的最佳结果。在运算时可采用以下参数值：配方搜索图上节点个数,信息素挥发系数，信息素痕迹强度，启发信息权重，参数，信息增量和路径信息素的初始值，根据该企业的实际生产情况，一个批次所需的啤酒原料总质量,过滤槽设备的直径。采用正交离散过程的蚁群算法独立进行20次迭代优化，运算后的具体结果如表

52、3.4.3所示：表3.4.3 啤酒原料最佳优化配方详细配方啤酒原料用量宁麦澳麦1.5宁麦哈默林6.0宝应甘三9.5九得利KA4B8.5九源甘三9.5宁麦加麦0.5小麦9.5大米55约束条件营养水平含量糖化力1856.5WK/kg氨基氮175.2mg/L葡萄糖122.6mg/L麦汁总氮784.5mg/L糟层厚度23.4cm配方总成本37685元采用正交离散过程的蚁群算法获得的最低成本为37685元，而目前该企业所采用的配方原料成本为40048元，优化后明显降低了成本，各种生产指标也符合相关营养标准的要求。由此可见，采用正交离散过程的蚁群算法在啤酒原料配方优化问题中的应用取得了令人满意的效果，其工

53、业应用价值非常好，在一定程度上提高了企业生产效率。与传统的基本蚁群算法相比，该优化算法大大提高了执行效率，同时为蚁群算法更好地解决连续域变量问题提供了一种可行的参考方法。第四章 本文的工作总结与展望4.1 本文的工作总结 本文首先介绍了基本蚁群算法的基本原理及其系统学特征，并针对传统蚁群算法耗时长、收敛慢、执行效率低等缺陷，提出了基于正交离散过程的蚁群算法。介绍了该优化算法的基本原理，并提出了该算法的具体实现办法和步骤。通过在啤酒原料配方设计的仿真应用显示了该优化算法大大提高了执行效率和收敛速度，表明该算法在解决实际连续域变量问题中发挥了非常重要的作用，该令人满意的验证结果为蚁群算法在解决连续

54、域变量问题方面开辟了一种可供参考的方法。4.2 展望自蚁群算法创立这么多年以来，在算法理论和算法应用方面取得了很多突破性的进展。针对自然界中真实蚁群的其他许多智能行为，用发散思维和逆向思维开发不同的蚁群算法模型是一条新的研究思路；同时，在连续域蚁群算法的收敛性证明方面仍存在许多空白，今后蚁群算法的理论分析和收敛性证明仍是一个挑战性的研究方向；此外，在研究蚁群算法的并行实现问题方面，还需要解决在蚁群算法并行化过程中对并行计算模型的选择、映射方法的改进、蚁群算法的分解等问题，这些问题也是今后研究的方向；另外蚁群算法的应用深度还不够，还需要进一步拓宽应用领域，对于如何抽象实际问题，使蚁群算法的求解结

55、果更接近于实际工程意义是广大蚁群算法学者们所关注的一个重要问题。致 谢 首先，在此毕业论文完成之际，我要深深地感谢我们组的指导老师张老师耐心地指导我顺利地完成论文，感谢老师给了我这样一个宝贵的学习机会。张老师严谨的治学态度、实事求是的学术作风、敏锐的洞察力和忘我的工作热情，深深地影响感染了我。在我完成毕业论文的过程中所取得的每一点进步，都离不开张老师的悉心教导。在这一段时间学到的东西将使我在以后的学习和工作中获益匪浅。在此，谨向我的导师张老师致以最诚挚的敬意和最衷心的感谢! 此外，感谢机电工程学院的各位老师们这几年对我的指导、教育和培养，特别感谢我们组的各位同学，论文的顺利完成与你们的无私帮助

56、和支持是分不开的，与你们相处的这一段快乐充实的时光让我难以忘怀，在与大家合作的过程中深深地体会到了团队合作的重要性。最后，感谢老师们和同学们对我的帮助让我能够顺利地完成学业，感谢所有关心和帮助过我的人!参考文献1 刘小梅，张君静. 蚁群优化算法基本原理及其应用 J.西部探矿工程报，2008,10（4）240-243.2 段海滨.蚁群算法原理及其应用 M. 北京,科学出版社，2005.3 陈一昭，姜麟.蚁群算法参数分析 J. 科学技术与工程，2011,12，11（36）:9080-90844 董如何，肖必华，方永水.正交试验设计的理论分析方法及应用 J.自然科学报，2004,6，12（6）:10

57、3-106.5 郑松，侯迪波，唐旭华，叶波，周泽魁. 一种改进蚁群算法及其在配方优化中的应用 J.江南大学自然科学报，2008,8,7（4）:387-3916 倪庆剑，邢汉承，张志政,王蓁蓁. 蚁群算法及其应用研究进展 J. 计算机应用与软件，2008,8，25（8）:12-167 许世杰，刘弘.基于过程优化的蚁群算法研究与应用 D.山东师范大学硕士学位论文，2010,6,19-208 郑松，李春富，于涵诚，葛铭. 啤酒原料配方的蚁群优化设计研究 J.计算机工程与应用，2011,47(11):226-2449 周明天，路纲，牛新征. 蚁群算法研究的新进展和展望 J.计算机应用研究，2007,8,24（4）：435-44237