基于正交离散过程的蚁群算法毕业论文(编辑修改稿)

基于正交离散过程的蚁群算法毕业论文(编辑修改稿)内容摘要：

蚂蚁无序地寻找解，但是经过一段时间的算法演化，蚂蚁越来越倾向于寻找那些 接近 于最优解的一部分解，这就 体现了蚂蚁行为从无序到有序的自组织性。 自组织性 增强了算法的鲁棒性。 4)正反馈 反馈是控制论中的重要概念，它代表信息输入对输出的反作。 由自然界中真实蚂蚁的觅食行为可见，蚂蚁之所以能够 找到最优 路径，直接依赖于 信息素不断地在 最短路径上 累积，而信息素的累 积就 是一个正反馈的过程。 蚁群算法 的 反馈方式是在较优 路径 上留下更多的信息素， 而更多的信息素又 吸引了更多的蚂蚁，此过程 引导整个系统不断地向 最优解的方向进化。 以上从系 统学的角度 分析了蚁群算法的机理，可见蚁群算法体现出许多不同于常规算法的新思想，这也正是基本蚁群算法在系统学上的研究意义所在。 15 基本蚁群算法的具体实现 基本蚁群算法的实现步骤 蚁群 算法 的 具体实现步骤如下： （１ ） 令时间ｔ＝０和循环次数 0Nc ，设置最大 循环 次数 为 Ncmax，将ｍ个蚂蚁置于ｎ个元素 上 ，令 每 条路径 （ｉ，ｊ）的初始化信息量 Wtij  ，其中Ｗ为常数， 并 且初始时刻 设置每 条路径上的信息素增量  00 ij。 （２）循环次数 1NN cc。 （３）蚂蚁的禁忌表索引号 k ＝１。 （４） 蚂蚁数目 1kk。 （５）蚂蚁个体根据状态转移概率公式（１）计算的概率选择 下一个元素ｊ，继续往前移动， 此时  ktabuCj 。 （６） 选择好下一个元素ｊ之后，将蚂蚁移动到新的元素，并把该元素 移动到该蚂蚁个体的禁忌表中，此时 ， 1 kk tabutabu。 （７）若集合 C 中元素 未遍历完，即ｋ＜ｍ，则跳转到第（４）步，否则执行第（８）步。 （８）根据路径上信息量更新公式（２）和 信息量变化公式（３）更新每条路径（ｉ，ｊ）上的信息量。 （９）若满足结束条件，即如果循环次数 NN cc max，则循环结束，输出程序计算的最佳结果，否则清空禁忌表并跳转到第（２）步。 基本蚁群算法的程序结构流程 图 16 基本蚁群算法的程序结构流程 图 如图。 开始 初始化 迭代次数 Nc =Nc +1 蚂蚁 k=1 蚂蚁 k=k+1 按照状态转移概率公式（ 1）选择下一个元素 修改禁忌表 ktabu = ktabu +1 k≥蚂蚁总数 m。 按照公式（ 2）和公式（ 3）进行信息素更新 满足结束条件。 输出程序计算结果 结束 N N Y Y 图 基 本蚁群算法的程序结构流程图 17 第三章 基于正交离散过程的蚁群算法 正交 试验 设计 正交试验设计的基本概念 在 正交试验要解决的问题 中，要明确 衡量试验效果的影响 指标， 影响试验 评价 指标者称为因素，因素在试验中变化的状态称为水平。 对于单因 素或者两因素试验，因其因素数比较少，试验的设计、安排 等都比较简单。 但 在 实际 生产 中 需要研究多个因素对产品指标的影响。 例如 因素数 为 a, 因素的水平数 为 b, 则多因素完全试验方案的次数 为 abm 次 ,从试验次 数的计算式 可以发现 , 随着因素数 和因素水平 数 的增多 , 试验的次数将急剧增多。 例如有 5个因素，每个因素有 4个水平，如果全面试验就要进行 102445  次，则试验的规模将会大大增大，这样 不仅会给研究带来很 大的工作量 , 而且也会浪费大量的 时间 、 原料 、 和 财力。 正交 试验设计 则 是利用正交表来安排与分析多因素试验的一种设计方法。 它是从 试验因素的全部水平组合中，挑选 出 部分有代表性的水平组合进行试验的，通过对这部分 代表性的 试验结果的分析 ，来 了解全面试验的情况，找出最优的水平组合。 正交试验设计的基本原理 在试验安排中， 当因素水平数不多时，人们首先想到 进行全面试验，例如，一个三因素三水平试验， 各因素水平之间的全部 组合就有 33=27种。 各 3个因素的选优区可以用一个立方体来表示 ， 3个因素各取 3个水平， 就 18 可以 把立方体划分成 27个格点， 若 这 27个网格点都 进行 试验，就是全面试验。 全面试验的数据 试验 点分布如图 — 1所示。 图 — 1 全面试验的数据 试验 点分布 由图可见： 全面试验 数据分布的非常均匀， 各个因素水平的搭配很全面， 缺点就是试验次数太 多，如果是 5因素 4水平试验，全 面试验的话就要进行 102445  次试验，这会因实验条件的限制而难于实施， 因此全面试验适用于因素水平数不多的情况下。 正交设计就是从选优区全面试验点（水平组合）中挑选出 部分 有代表性的试验点来进行试验。 对于 3因素 3水平而言，设有 A,B,C三个因素，A因素有 321 , AAA 三个试验水平， B因素有 321 , BBB 三个试验水平， C因素有321 , CCC 三个试验水平，利用正交表  493L 从 27个试验点中挑选出来的 9个试验点，这 9个试验点为： （ 1） 111 CBA ； （ 2） 221 CBA ； （ 3） 331 CBA。 （ 4）212 CBA。 （ 5） 322 CBA。 （ 6） 132 CBA。 （ 7） 313 CBA。 （ 8） 123 CBA。 （ 9） 233 CBA。 这样的选择保证了 A因素的 3个水平与 B、 C因素的 3个水平在试验过程中各搭配一次 ，对于 A、 B、 C3个因素来说，正交试验次数 仅 是全面试验次数的三分之一，大大减少了试验 次数。 正交试验设计的数据 试验 点在立方 19 体选优区中的分布如图 — 2所示 : 图 — 2 正交试验设计的数据 试验 点分布 从图 — 2中可以看到， 9个试验 数据点在选优区中 分布 是 均衡的 ，在立方体的每个平面上 恰好只有 3个试验点， 在立方体的每条线上 恰好只 有一个试验点。 所选的这 9个 试验点 具 有很强的代表性，能够比较全面地反映 整个 选优区内的基本情况。 因此它们能很好的代表 27次全面试验的情况， 这就是正交设计的优点 】【 4。 正交表及其基本性质 正交表是正交试验设计的基本工具，正交设计安排实验和分析试验结果都要用到正交表 ， 合理选用 正交表 是 正 交设计的基础。 常用的正交表已经标准化，我们可以根据试验需要从 参考书中选取合适的正交表。 正交表的记号为  bL ca ，其中 L代表正交表， a是试验的次数 即 正交表的行数， b表示 水平数， c表示因素 数 即列数。 正交表的基本性质 如下： 1）正交性 ：在正交表中任意一列中，某因素的所有水平都 出现，且出现的次 数是相等的，在任意两列之间，两因素的各种不同水平组合都出现，并且出现的次数也相等。 20 2） 均衡分布 性：在正交表中的各因素水平组合在选优区中是均衡分布 的。 例如图 — 2所示，在立方体中，每 一平面内只 有 3个 数据试验点，每 一条直线上只 包含 1个 数据 试验点，正交试验的试验点均衡地分布在全面试验点中。 3）独立性：正交表中没有完全重 复的水平组合，从全部试验组合中挑选的这一部分试验组合没有 重复试验 的 情况，在讨论某一因素时，不用 考虑 其他因素的影响 ， 正交表中的试验方案能够综合处理大量信息。 4）整齐可比 性 ： 整齐可比是指每一 因素的各 个 水平 之 间具有可比性。 正交表中每一因素的各个水平都均匀地搭配 着其他 因素的各个水平。 如在 3 因素 3水平试验中的 A、 B、 C3个因素 ， A 因素的 3个水平 A AA3各有 B、 C 两因素 的 3个不同水平， 也就是： （ 1） 111 CBA ； （ 2） 221 CBA ；（ 3） 331 CBA。 （ 4） 212 CBA。 （ 5） 322 CBA。 （ 6） 132 CBA。 （ 7） 313 CBA。 （ 8）123 CBA。 （ 9） 233 CBA。 在这 9个水平组合中， A因素 下的每个水平组合 了B、 C 两 因素的 3 个水平， 且任意两个水平组合 不会发生 重复 现象。 A 因素 3个水平间具有 整齐 可比性。 同样 B、 C两 因素 的 3个水平间亦具有整齐 可比性。 基于正交离散过程的蚁群算法 正交离散 过程 蚁群算法的基本原理 传统基本 蚁群算法在实际应用中主要是解决离散域的组合优化问题， 而难于解决连续域的函数优化问题，在原料配方设计等连续变量领域中 应 用困难。 而正交试验设计 可以综合处理大量 的 信息，有效 地 解决 21 连续域问题。 正交离散主要是将基本蚁群算法与正交 试验 设计相结合 ，通过正交设计形成正交离散点，使连续域问题离散化， 让蚂蚁在正交试验得出的几条优化路径中寻找最优解， 改进 了初始阶段蚁群算法信息素随机分布、路径杂乱无章的缺点 ， 最终可以取得满意的结果。 以原料配方设计为 例 进一步说明正交离散过程的蚁群算法。 设原料品种（ nRR~1 ）为横坐标，原料用量为  100~1iXi ，原料品种所占的 比例 i％从 1％～ 100％ 连续均匀 变化，属于典型的连续域变量问题。 由于从 1％～ 100％之间有无穷多个节点，若用基本蚁群算法， 那么 蚂蚁将会从 第一个节点 1％ 开始访问无穷多个节点，这样必然会造成庞大的计算量而无限延长计算时间，所求的结果也会比较分散，所以应把问题离散化。 在正交试验优化中，以品种数作为因素数，每个 原料品种在 所占比例 范围内选定 水平数。 例如： 有四个原料品种，也就是有四个因素，每个品种有三个水平 ，也就是 4 因素 3 水平正交试验，则选用正交试验表 493L ，产生 12 个正交离散节点，组成 9 个初始配方组合，让初始蚂蚁在这 9个初始路径 中释放一定的 信息素，然后运行蚂蚁 更加趋向于 从 这 9个配方组合 中搜索适应解配方，最终确定最优解，这样就实现了把连续性问题离散化处理了。 原料成分离散化及配方搜索图如图 ： 0 100％ 1R 2R 3R 4R nR 2A 各原料所占的质量分数 3B 1C 2D 1A 3A 1B 2B 2C 3C 1D 3D  21,ar  32,br  13,cr  24,dr 图 原料正交离散及配方搜索图 Start end 品种因素 iX 22 为了能够有效运用正交离散的蚁群算法，要 把研究对象离散化成如图 形式 ， 这样就大大缩小了搜索范围，在很大程度上改善了寻优性能，极大缩短了计算时间。 首 先挑 选 四个原料品种作为四个因素，即品种 41 ~RR ，每个因素再选择三个水平， 即因素 1R 有 321 , AAA 三个水平、因素 2R 有 321 , BBB 三个水平、因素 3R 有。