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

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

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

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

3、cal 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

4、 simulating 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 ove

5、rviewed 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 introd

6、uced 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 strate

7、gies 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 me

8、thod 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 目 录第一章 绪论61.1 研究背景61.2 国内外对蚁群算法的研究进展71.3 本文的研究主线及体系结构7第二章 蚁群算法92.1 蚁

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

10、模型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、食物，建立蚁穴并抚养后代，整个蚂蚁群体发挥出了超出个体的行为能力，能完成许多蚂蚁个体所不能完成的复杂任务。蚁群算法(ant colony algorithm,ACA)是最新发展起来的一种模拟蚂蚁群体智能行为的仿生优化算法，该算法采用了正反馈并行自催化机制，在解决许多复杂优化问题方面展现出优异性能和巨大的发展潜力，最近几年吸引了国内外许多研究者对蚁群算法进行了多方面的研究工作。国际著名顶级学术期刊Nature曾多次对蚁群算法的研究成果进行报道，Future Generation Computer Systems和IEEE Transactions On Evolutionary Computat

12、ion分别在2000年和2002年出版了蚁群算法特刊，在布鲁塞尔每两年召开一次的蚁群算法国际研讨会进一步促进了这一智能计算领域的学术交流，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景。目前，蚁群算法已经成为国际智能计算领域中备受关注的研究热点和前沿性课题。1.2 国内外对蚁群算法的研究进展自1991年意大利学者DorigoM.提出蚁群算法以后，蚁群算法逐渐得到了世界许多研究者的关注，其在很多领域得到了很好的应用，在这期间国内外大量有价值的研究成果也陆续发表。2000年，Dorigo M和Bonabeau E等在国际顶级学术刊物Nature上发表了蚁群算法的研究综述，从而把这一领域

13、的研究推向了国际学术最前沿，鉴于Dorigo M在蚁群算法研究领域的杰出贡献，2003年11月欧盟委员会特别授予他“居里夫人杰出成就奖”。我国在蚁群算法领域的研究也取得了一些令世人瞩目的成就：陈烨在2001年发表了带杂交算子的蚁群算法一文，并基于Visual Basic开发了一个功能齐全人性化的“蚁群算法实验室”。在2003到2005年间，李艳君、段海滨提出了一种基于网格划分策略的自适应连续域蚁群算法和一种用于求解连续域优化问题的自适应连续域蚁群算法。在2008年，郑松为了解决蚁群算法演化过程收敛速度慢、消耗时间长的缺点，提出将确定性搜索引入基本蚁群算法的搜索过程中，并研究了改进后的蚁群算法在

14、啤酒配方优化设计中的具体应用。1.3 本文的研究主线及体系结构1）本文的研究主线：研究主线是基于正交离散过程的蚁群算法，通过将蚁群算法与正交试验设计相结合，把连续性问题离散化，在常规搜索中创建正交离散过程，优化路径设置提高算法的搜索速度和运行效率。将基于正交离散过程的蚁群算法应用于啤酒原料配方设计实践中，取得了非常好的效果，从而开辟了一种解决连续域变量问题的求解方法。2）本文的体系结构：本文全面地介绍了蚁群算法的理论、方法及其具体实现，按照分析、深化、改进、仿真应用的逻辑结构进行安排，本文共分为四章，其内容基本上构成了一个完整体系，具体而言，各章主要包括如下内容：第一章 阐述了蚁群算法的研究背

15、景及国内外对蚁群算法的研究进展，同时列举了部分改进的蚁群算法及其应用情况，最后给出了本文的研究主线和体系结构。第二章 在介绍蚂蚁的群体觅食行为特征的基础上，从深层意义上进一步分析蚁群算法的机制原理、数学模型、以及具体实现步骤，最后讨论了基本蚁群算法的系统学特征。本章主要内容对基本蚁群算法原理进行分析，也是后面章节对蚁群算法进行改进研究的基础。第三章 详细阐述基于正交离散过程的蚁群算法。分析了正交试验设计的基本原理、正交离散的基本原理、特点，以及正交离散过程蚁群算法实现寻优过程的寻优规则、数学模型，并分析了该改进型蚁群算法在啤酒原料配方设计方面的仿真应用等内容。第四章 对本文的主要内容进行总结，

16、讨论了目前蚁群算法所存在的主要问题，然后从蚁群算法的模型改进、理论分析、并行实现、应用领域等方面对蚁群算法在以后的进展进行了讨论。第二章 蚁群算法2.1 蚁群算法的基本原理及其数学模型2.1.1 真实蚁群的觅食机理 根据研究者的长期观察发现：蚂蚁在运动时会在路径上释放出一种信息素来寻找路径。当它们碰到一个陌生路口时，就随机地挑选一条路径前进，同时释放出一定强度与路径长度相关的信息素。蚂蚁走过的路径越长，所释放的信息量就越少。当后来蚂蚁再次碰到这个路口时，选择信息量较大路径的可能性比较大，由此便形成了一个正反馈机制。最短路径上的信息素强度逐渐增大，其他路径上的信息量随着时间的延长而逐渐消减，整个

17、蚁群最终找出最佳的路径。如图2.1.1（a）所示，我们总可以观察到蚂蚁群体在蚁穴与食物之间形成近乎直线的路径，而不是曲线或者折线等其他形状。如图2.1.1（b）所示，蚂蚁运动路线上突然出现障碍物时，开始时各只蚂蚁均匀分布，不管路径的长短，蚂蚁总是先随机选择各条路径。蚂蚁在运动过程中在经过的路径上留下一定强度的信息素，其他蚂蚁能够感知这种物质的强度，并以此指导自己继续移动，如图2.1.1（c）所示，蚂蚁倾向于选择信息素浓度高的路径，相等时间内在较短路径上遗留的的信息素量就比较多，选择较短路径的蚂蚁也越来越多。蚂蚁集体行为表现出一种信息正反馈现象，即蚂蚁在某一路径上经过的越多，后来的蚂蚁选择该路径

18、的可能性就越大，蚂蚁个体之间就是通过这种信息正反馈机制来搜索食物并最终找到最优路径的，如图2.1.1（d）所示。 图2.1.1 现实中蚁群寻找食物的过程 由上述可见，在整个寻优过程中，虽然单只蚂蚁的寻优能力有限，但是整个蚁群的行为通过信息素的作用便具有非常高的自组织性，蚂蚁之间交换路径信息素，最终通过蚂蚁的正反馈机制找到最优路径。2.1.2 基本蚁群算法数学模型的建立蚁群算法首先成功应用于TSP问题，其形象描述是：给定n个城市与城市之间的距离，某一旅行商从某一城市出发，逐个访问各个城市一次且仅一次后再回到原来出发的城市，找出一条最短的迅游路径。下面我们以简单的TSP问题为例来说明蚁群算法基本原

19、理。将m只蚂蚁随机地放置在n个城市上,设初始时刻城市之间每一条路径信息素强度=c (c是一个常量), 是禁忌表,用来记录蚂蚁当前所走过的城市集合, 不允许蚂蚁再次访问该其中的城市结点。当n个城市结点都写入禁忌表中时,表示蚂蚁完成一次循环。在搜索过程中, 蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。在t时刻,蚂蚁k（k=1,2,m）由城市i转移到城市j的转移概率为 （1）式（1）中有：表示t时刻路径（i,j）上的信息素强度;表示信息启发式因子，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用；作为期望启发式因子，表示路径能见度的相对重要性，反映了蚂蚁在运动过程中启发信息

20、在蚂蚁选择路径中的受重视程度; 是启发函数，在TSP问题中，通常取=,表示相邻两个城市之间的距离，启发函数表示蚂蚁从城市i转移到城市j的期望程度；=1,2,n-表示不在中的那些城市的集合，也就是允许蚂蚁下一步继续寻找的城市集合。为了避免残留信息素过多而引起残留信息淹没启发信息，在每只蚂蚁走完一步或者对所有n个城市遍历完（也即一个循环结束）后，要对残留信息进行更新处理。在t+n时刻在路径（i，j）上的信息量要可按以下公式更新调整：（） （）其中表示本次循环路径(i,j)的信息素增量,在初始时刻。表示第k只蚂蚁在这次循环中在路径（i,j）上的信息素增量。表示信息素挥发系数，1-表示信息素残留系数，

21、为了防止信息素的无限积累，的取值范围为：。信息素挥发因子的大小关系到算法的全局搜索能力和收敛速度，信息素残留因子1-反映了蚂蚁个体之间相互影响的程度。根据信息素更新策略的不同，Dorigo M 提出了三种不同的基本蚁群算法模型分别称之为Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型，其差别在于的求法不同。在Ant-Cycle模型中 （）式（）中,L表示第k只蚂蚁在本次循环中所走路径的总长度，Q为常数，所指的是信息素强度，表示的是蚂蚁完成一次循环时释放在所经过路径上的信息素总量。在Ant-Quantity模型中 （） 在Ant-Density模型中 （）它们的区

22、别在于：式（）和（）中利用的是局部信息，也就是蚂蚁完成一步后更新路径上的信息素；而式（）中利用的是整体信息，也就是蚂蚁完成一个循环后更新所有路径上的信息素，在求解TSP问题时性能较好，因此通常采用式（）作为蚁群算法的基本模型。2.1.3 基本蚁群算法的系统学特征1）基本蚁群算法是一个系统系统可以定义为处于一定的相互关系中并与环境发生关系的各组成部分的综合体。这个定义强调的不是功能，而是系统元素之间的相互作用以及系统对元素的整体作用。蚂蚁群体就构成了一个系统，在该系统中，蚂蚁的个体行为可以作为系统中的元素，蚂蚁之间相互影响体现了系统的相关性，而蚂蚁群体能完成个体所完成不了的复杂任务体现了系统的整

23、体性，在基本蚁群算法中，采用多只蚂蚁的求解结果好于单只蚂蚁的求解结果，因此基本蚁群算法是一个系统。2）分布式计算生命系统是一个分布式系统，它使得生命体具有很强的适应能力。比如说人体的很多细胞相互独立完成同一项工作，当一个细胞停止工作或新陈代谢之后，整体的功能不会因此而受到影响。蚁群算法也体现了群体行为的分布式特征。每只蚂蚁在问题空间的多个点相互独立地构造问题的解，而整个问题的求解过程不会因为某只蚂蚁无法求解而受到影响。分布式特征增强了蚁群算法的可靠性。3）自组织性如果系统在获得时间的、空间的或者功能的结构过程中，没有外界的特定干预，则称该系统是自组织的。最典型的自组织就是生物体，即类似蚂蚁、蜜

24、蜂这样的昆虫群落中，生物个体相互作用，协同完成某项群体工作，自然就体现出很强的自组织性。蚁群算法就体现了自组织性。在算法初期，单只蚂蚁无序地寻找解，但是经过一段时间的算法演化，蚂蚁越来越倾向于寻找那些接近于最优解的一部分解，这就体现了蚂蚁行为从无序到有序的自组织性。自组织性增强了算法的鲁棒性。4)正反馈反馈是控制论中的重要概念，它代表信息输入对输出的反作。由自然界中真实蚂蚁的觅食行为可见，蚂蚁之所以能够找到最优路径，直接依赖于信息素不断地在最短路径上累积，而信息素的累积就是一个正反馈的过程。蚁群算法的反馈方式是在较优路径上留下更多的信息素，而更多的信息素又吸引了更多的蚂蚁，此过程引导整个系统不

25、断地向最优解的方向进化。以上从系统学的角度分析了蚁群算法的机理，可见蚁群算法体现出许多不同于常规算法的新思想，这也正是基本蚁群算法在系统学上的研究意义所在。2.2 基本蚁群算法的具体实现2.2.1 基本蚁群算法的实现步骤 蚁群算法的具体实现步骤如下：（）令时间和循环次数，设置最大循环次数为，将个蚂蚁置于个元素上，令每条路径（，）的初始化信息量，其中为常数，并且初始时刻设置每条路径上的信息素增量。（）循环次数。（）蚂蚁的禁忌表索引号。（）蚂蚁数目。（）蚂蚁个体根据状态转移概率公式（）计算的概率选择下一个元素，继续往前移动，此时。（）选择好下一个元素之后，将蚂蚁移动到新的元素，并把该元素移动到该蚂

26、蚁个体的禁忌表中，此时，。（）若集合中元素未遍历完，即，则跳转到第（）步，否则执行第（）步。（）根据路径上信息量更新公式（）和信息量变化公式（）更新每条路径（，）上的信息量。（）若满足结束条件，即如果循环次数，则循环结束，输出程序计算的最佳结果，否则清空禁忌表并跳转到第（）步。2.2.2 基本蚁群算法的程序结构流程图基本蚁群算法的程序结构流程图如图2.2.2所示。图2.2.2 基本蚁群算法的程序结构流程图开始初始化迭代次数N=N+1蚂蚁k=1蚂蚁k=k+1按照状态转移概率公式（1）选择下一个元素修改禁忌表=+1k蚂蚁总数m？ 按照公式（2）和公式（3）进行信息素更新满足结束条件？输出程序计算结

27、果结束NNYY第三章 基于正交离散过程的蚁群算法3.1 正交试验设计3.1.1 正交试验设计的基本概念在正交试验要解决的问题中，要明确衡量试验效果的影响指标，影响试验评价指标者称为因素，因素在试验中变化的状态称为水平。对于单因素或者两因素试验，因其因素数比较少，试验的设计、安排等都比较简单。但在实际生产中需要研究多个因素对产品指标的影响。例如因素数为a, 因素的水平数为b, 则多因素完全试验方案的次数为次,从试验次数的计算式可以发现, 随着因素数和因素水平数的增多, 试验的次数将急剧增多。例如有5个因素，每个因素有4个水平，如果全面试验就要进行次，则试验的规模将会大大增大，这样不仅会给研究带来

28、很大的工作量, 而且也会浪费大量的时间、原料、和财力。正交试验设计则是利用正交表来安排与分析多因素试验的一种设计方法。它是从试验因素的全部水平组合中，挑选出部分有代表性的水平组合进行试验的，通过对这部分代表性的试验结果的分析，来了解全面试验的情况，找出最优的水平组合。3.1.2 正交试验设计的基本原理在试验安排中，当因素水平数不多时，人们首先想到进行全面试验，例如，一个三因素三水平试验，各因素水平之间的全部组合就有33=27种。各3个因素的选优区可以用一个立方体来表示，3个因素各取3个水平，就可以把立方体划分成27个格点，若这27个网格点都进行试验，就是全面试验。全面试验的数据试验点分布如图3

29、.1.21所示。图3.1.21 全面试验的数据试验点分布由图可见：全面试验数据分布的非常均匀，各个因素水平的搭配很全面，缺点就是试验次数太多，如果是5因素4水平试验，全面试验的话就要进行次试验，这会因实验条件的限制而难于实施，因此全面试验适用于因素水平数不多的情况下。正交设计就是从选优区全面试验点（水平组合）中挑选出部分有代表性的试验点来进行试验。对于3因素3水平而言，设有A,B,C三个因素，A因素有三个试验水平，B因素有三个试验水平，C因素有三个试验水平，利用正交表 从27个试验点中挑选出来的9个试验点，这9个试验点为：（1）；（2）；（3）;（4）;（5）;（6）;（7）;（8）;（9）。

30、这样的选择保证了A因素的3个水平与B、C因素的3个水平在试验过程中各搭配一次，对于A、B、C3个因素来说，正交试验次数仅是全面试验次数的三分之一，大大减少了试验次数。正交试验设计的数据试验点在立方体选优区中的分布如图3.1.22所示:图3.1.22 正交试验设计的数据试验点分布 从图3.1.22中可以看到，9个试验数据点在选优区中分布是均衡的，在立方体的每个平面上恰好只有3个试验点，在立方体的每条线上恰好只有一个试验点。所选的这9个试验点具有很强的代表性，能够比较全面地反映整个选优区内的基本情况。因此它们能很好的代表27次全面试验的情况，这就是正交设计的优点。3.1.3 正交表及其基本性质正交

31、表是正交试验设计的基本工具，正交设计安排实验和分析试验结果都要用到正交表，合理选用正交表是正交设计的基础。常用的正交表已经标准化，我们可以根据试验需要从参考书中选取合适的正交表。 正交表的记号为，其中L代表正交表，a是试验的次数即正交表的行数，b表示水平数，c表示因素数即列数。正交表的基本性质如下：1）正交性：在正交表中任意一列中，某因素的所有水平都出现，且出现的次数是相等的，在任意两列之间，两因素的各种不同水平组合都出现，并且出现的次数也相等。2）均衡分布性：在正交表中的各因素水平组合在选优区中是均衡分布的。例如图3.1.22所示，在立方体中，每一平面内只有3个数据试验点，每一条直线上只包含

32、1个数据试验点，正交试验的试验点均衡地分布在全面试验点中。3）独立性：正交表中没有完全重复的水平组合，从全部试验组合中挑选的这一部分试验组合没有重复试验的情况，在讨论某一因素时，不用考虑其他因素的影响，正交表中的试验方案能够综合处理大量信息。4）整齐可比性：整齐可比是指每一因素的各个水平之间具有可比性。正交表中每一因素的各个水平都均匀地搭配着其他因素的各个水平。如在3因素3水平试验中的A、B、C3个因素，A因素的3个水平A1、A2、A3各有 B、C两因素的3个不同水平，也就是：（1）；（2）；（3）;（4）;（5）;（6）;（7）;（8）;（9）。在这9个水平组合中，A因素下的每个水平组合了B

33、、C两因素的3个水平，且任意两个水平组合不会发生重复现象。A因素3个水平间具有整齐可比性。同样B、C两因素的3个水平间亦具有整齐可比性。3.2 基于正交离散过程的蚁群算法3.2.1 正交离散过程蚁群算法的基本原理传统基本蚁群算法在实际应用中主要是解决离散域的组合优化问题，而难于解决连续域的函数优化问题，在原料配方设计等连续变量领域中应用困难。而正交试验设计可以综合处理大量的信息，有效地解决连续域问题。正交离散主要是将基本蚁群算法与正交试验设计相结合，通过正交设计形成正交离散点，使连续域问题离散化，让蚂蚁在正交试验得出的几条优化路径中寻找最优解，改进了初始阶段蚁群算法信息素随机分布、路径杂乱无章

34、的缺点，最终可以取得满意的结果。以原料配方设计为例进一步说明正交离散过程的蚁群算法。设原料品种（）为横坐标，原料用量为，原料品种所占的比例i从1100连续均匀变化，属于典型的连续域变量问题。由于从1100之间有无穷多个节点，若用基本蚁群算法，那么蚂蚁将会从第一个节点1开始访问无穷多个节点，这样必然会造成庞大的计算量而无限延长计算时间，所求的结果也会比较分散，所以应把问题离散化。在正交试验优化中，以品种数作为因素数，每个原料品种在所占比例范围内选定水平数。例如：有四个原料品种，也就是有四个因素，每个品种有三个水平，也就是4因素3水平正交试验，则选用正交试验表，产生12个正交离散节点，组成9个初始

35、配方组合，让初始蚂蚁在这9个初始路径中释放一定的信息素，然后运行蚂蚁更加趋向于从这9个配方组合中搜索适应解配方，最终确定最优解，这样就实现了把连续性问题离散化处理了。原料成分离散化及配方搜索图如图3.2.1所示： 0100各原料所占的质量分数图3.2.1 原料正交离散及配方搜索图Startend品种因素 为了能够有效运用正交离散的蚁群算法，要把研究对象离散化成如图3.2.1所示的形式，这样就大大缩小了搜索范围，在很大程度上改善了寻优性能，极大缩短了计算时间。首先挑选四个原料品种作为四个因素，即品种，每个因素再选择三个水平，即因素有三个水平、因素有三个水平、因素有三个水平、因素有三个水平，由正交

36、试验表可知可以组成9个初始配方组合，也就是如图3.2.1所示的9条已经初始化一定量信息素的路径，即（1）；（2）；（3）;（4）;（5）;（6）;（7）;（8）;（9）。创建正交试验表，如表格3.2.2所示:表3.2.2 因素水平正交试验分配方案表因素试验编号ABCD1A1B1C1D12A1B2C2D23A1B3C3D34A2B1C2D35A2B2C3D16A2B3C1D27A3B1C3D28A3B2C1D39A3B3C2D1如图3.2.1所示，一只蚂蚁从Start点开始出发，逐步经过每个品种上的正交离散点，最后到达代表最后一个品种的end点，完成一次循环即形成一个完整的配方，多只蚂蚁循环上述

37、过程便形成多种配方组合。通过对原料用量正交离散化处理，大大减少了搜索初始解集的试验配方次数，提高了蚁群算法的运算效率。由图3.2.1可见，这12个正交离散点所组成的配方组合总共有种，而这81条路径具有很强的代表性，它们代表了原料比例在1100范围内全面试验的无穷多条路径，也就是说这一部分正交试验代表了全面试验。根据专业知识和实践经验，通过对所研究问题的具体分析，明确哪几个因素及其哪几个水平对试验指标的影响比较大，然后再挑选这几种因素及其水平进行试验。在正交表3.2.2中确定的9种优化组合配方中很有可能存在最佳配方，也就是说蚂蚁最有可能在这已经初始化一定信息素的9条路径中搜索到最优解，比如图3.

38、2.1中加黑加粗的那条路径2，即配方组合有可能是最优解。但是除了这9条路径之外的其它72条路径中的一条配方组合也有可能是最优解，只不过这9条路径中的一条成为最优解的可能性比较大，而其他72条路径成为最优解的可能性比较小而已。这种方法将会克服基本蚁群算法随机搜索无规律、效率低、结果分散的缺陷，在很大程度上提高了蚁群算法的求解精度。因此，基于正交离散过程的蚁群算法能很好地解决连续域变量的配方组合优化问题。3.2.2 正交离散过程蚁群算法的寻优过程在正交优化过程中，蚂蚁主要有初始蚂蚁和运行蚂蚁两种。初始蚂蚁的主要任务是在图3.2.1中的9条正交优化路径上释放一定的信息素，即蚂蚁初始化信息素（为常数）

39、。蚂蚁从start点出发进行寻优，结束于end点，在寻优过程中，相邻两个因素的各个水平节点之间都存在连接路径，蚂蚁在各个水平节点之间按照动态概率转移规则构造新的路径，当所有的蚂蚁遍历完后，就可以找出最优解。在蚂蚁创建优化解的过程中，蚂蚁逐个访问各个离散节点，位于节点r上的蚂蚁根据伪随机比例规则选择下一个将要访问的节点s，单个蚂蚁在遍历的过程中根据信息素局部更新规则对它所经过的路径进行信息素更新，当所有的蚂蚁遍历完所有的节点后，再按照全局信息素更新规则对所经过的路径进行信息素更新。 1）伪随机比例规则：该规则主要是在蚂蚁探索一条新路径和根据蚂蚁所积累的搜索经验开发一条新路径这两者之间保持体一种平

40、衡状态。位于节点r的蚂蚁k利用以下规则选择下一个将要访问的节点s： （7） 式（7）中，函数argmaxf(x)表示寻找最优解的参量，表达的是定义域中的一个子集，且该子集中的任一元素都可使函数f(x)取得最优值。表示蚂蚁k下一步要访问的节点的集合，表示路径（r,j）上的信息素强度，=,表示启发式信息。q是服从均匀分布的一个随机数，是自定义的一个参数。S是根据以下的概率公式（8）计算得来的随机变量。 （8）由式（7）和（8）决定的状态转移规则被称为伪随机比例规则。伪随机比例规则使蚂蚁更倾向于选择距离短且信息素强度高的路径。参数决定了“探索”一条新路径和利用蚂蚁积累的有效搜索经验“开发”一条路径这

41、两种过程之间的相对重要程度。参数要根据路径信息素分布情况和寻优目标适时地进行调节，这样可以发挥在寻找最优解过程中的作用。蚂蚁在开始时的 、中间选择节点时的和最终找到最优解时的都应适时地进行调节，这样在初始阶段可以加快算法运算的速度，在寻优过程中又可以避免算法陷入局部最优状态。当蚂蚁从节点r向节点s移动时，它会选择一个随机数，如果，按照（7）式根据启发式信息和信息素强度选择最优路径，否则按照（8）式的随机比例规则选择下一步要移动的路径。2）信息素全局更新规则：当蚂蚁访问完所有的节点以后，只增强那些属于最短路径上的信息素，信息素全局更新规则使蚁群算法寻优过程具有很强的指导性。当所有的蚂蚁遍历完所有

42、的节点之后，按照以下的公式进行信息素全局更新： （9） （10）其中参数（）是信息素衰减系数，表示试验开始至今所找到的全局最短路径的长度。3）信息素局部更新规则：单个蚂蚁在节点之间遍历时按照信息素局部更新规则对所经过路径上的信息素进行更新： （11）其中参数是信息素挥发系数。实验表明，（是初始化信息素）时算法效果比较好。应用信息素局部更新规则会使蚂蚁经过路径上的信息素减少一部分，这样后来的蚂蚁选择这些路径的可能性大大地减少了，从而增强了算法的“探索”能力，有效地避免了算法进入局部停滞状态。3.2.3 正交离散过程蚁群算法的数学模型目标函数根据所研究问题的实际限定因素而设定，例如：目标函数： (

43、12)表示经济目标比如最大利润、最低成本等；表示各种原料的价格系数；表示各种原料在配方中的比例（）；n为变量数。根据配方中各原料用量的相关标准确定约束条件：（13）为约束值，也就是配方应该满足的各项指标（重量、营养价值等指标）；为各种原料的相应化学成分含量；m为约束方程的个数。 3.3 正交离散过程蚁群算法的具体实现3.3.1 正交离散过程蚁群算法的实现步骤正交离散过程蚁群算法具体实现步骤如下所示：第一步：明确正交离散过程蚁群算法需要解决的实际问题。 第二步：根据实际问题确定目标函数，根据实际限定因素确定约束函数条件，建立正交离散过程蚁群算法的基本数学模型。 第三步：根据正交设计优化路径设置，

44、将研究对象正交离散化处理。 第四步：初始蚂蚁在正交试验设计中所确定的几条优化路径中释放一定量的信息素，蚁群算法参数进行初始化。然后运行蚂蚁根据初始蚂蚁建立的路径信息素强度和启发信息按照伪随机比例规则运行，进行全局范围内的搜索寻优移动。 第五步：适时调节参数，动态调整状态转移概率、优化路径设置。 第六步：动态地进行信息素局部和全局更新优化，以提高寻优效率。 第七步：如果满足结束条件，计算目标函数值，否则回到第二步。第八步：最终输出程序计算的最佳结果。3.3.2 正交离散过程蚁群算法的程序结构流程图正交离散过程蚁群算法的程序结构流程图如图3.3.2所示：开始明确研究问题定义目标函数、约束函数条件，

45、建立数学模型正交离散化初始化蚁群算法参数状态转移概率优化信息素动态更新优化进行选路寻优计算满足结束条件？计算目标函数值输出程序计算最佳结果结束N迭代 Y 图3.3.2 正交离散过程蚁群算法的程序结构流程图3.4 正交离散过程蚁群算法的仿真应用配方试验设计就是连续域变量优化问题，在满足实际意义的约束条件下，求解各种原料配方的最佳比例，使问题的目标函数值达到最大或最小的效果。下面以啤酒原料配方设计为例对正交离散过程蚁群算法进行仿真应用。啤酒配方主要包括多种大麦和大米等原料，这些原料经过糖化过程制成麦汁，再经过发酵制成啤酒。以某企业所要求的具体生产指标和原料种类为例对该算法进行仿真验证。假设该企业可提供的原料种类有以下几种：宁麦加麦、宁麦澳麦、宁麦哈默林、九源甘三、九得利KA4B、宝应甘三、小麦麦芽和大米。不同原料具有各自不同的营养参数属性，具体营养标准如表3.4.1所示： 表3.4.1 啤酒原料营养参数标准麦芽品种单价/（元/kg）产槽率/（L/kg）氨基氮/（mg/100g）总可溶性氮/（mg/100g）葡萄糖/