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

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

的自组织性。 自 组织性 增强了算法的鲁棒性。 4)正反馈 从自然界中真实蚁群的觅食行为机制可以发现 ，蚂蚁之所以能够 找到最优 路径，主要是由于 信息素不断地在 较优 路径上 的 累积，而信息素的累 积 过程 就 是一个正反馈 过程。 基本 蚁群算法 的 反馈机制 是在较优 路径 上留下更多的信息素， 而 更多的信息素又 吸引 来 了更多的蚂蚁，这个过程 引导 着 整个系统不断向 最优解的方向进化。 以上从系统学方面分析了蚁群算法的机理，可见蚁群算法体现了 不同于常规算法的 许多 新思想，这也正是基本蚁群算法在系统学上 研究 的意义所在。 基本蚁群算法的具体实现 基本蚁群 算法的实现步骤 基本 蚁群 算法 的 具体实现步骤如下： （１ ） 令初始时刻 循环次数 0Nc ，设 最大 循环 次数 为 Ncmax，将ｍ个 15 蚂蚁 随机 放在 ｎ个元素 节点 上 ，设 每 条路径 （ｉ，ｊ）的初始化信息量 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, 则多因素全面 试验方案的次数 m 为abm 次 ,从试验次 数的公 式 可知 , 因素数 和 水平 数 增多 , 试验次数将会大大增加。 例如有 5个因素，每个因 素有 4个水平，若 全面试验就要进行102445  次，这样试验 规模 就会大大增加， 给研究 工作 带来了繁重 的任务 , 而且也 会消耗 大量 时间 、 原材料 和 财力。 正交 试验设计 就是利用正交表来安排、 分析多因素 多水平 试验的一种设计方法。 它是从 全面 试验的全部水平组合中，挑选 出 一 部分 代表性很强 的水平组合进行试验，通过 分析 这部分 有 代表性 水平组合 的 试验结果 ，来 了解全面试验的情况， 减少试验次数， 从而找出最优 水平组合。 正交试验设计的基本原理 在试验安排中， 当因素水平数不多时，适合 进行全面试验， 例 如，一个三因素三水平试验， 各因素 各 水平之间的全部 水平 组合就有 33=27种。 可以用一个立方体来表示 多 因素 试验的选优区域 ， 对于 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、 C这 3个因素来说，正交试验次数 仅 是全面试验次数的三分之一， 这样就 大大减少了试验 次数。 正交试验设计的数据 试验 点在立方体选优区中 19 的分布如图 — 2所示 : 图 — 2 正交试验设计的数据 试验 点分布 从图 — 2中可以看到， 9个试验 数据点在选优区中 均衡 分布 ，在立方体的每个平面上 恰好只有 3个试验点， 在立方体的每条线上 恰 好只 有1个试验点。 所选的这 9个试验点 在整个立方体内均衡分布， 代表性 很强，能够全面 反映 整个 立方体 选优区内的基本情况。 因此它们能很 好地 代表27次全面试验的情况， 这就是正交 试验 设计的优点 】【 4。 正交表及其基本性质 正交表是正交试验设计的基本工具，正交试验设计安排以及 分析试验 结果都要用到正交表 ， 合理选用 正交表 是 正 交设计的基础。 常用的正交表已经 规范标准化，我们 根据试验需要从 参考书中选取合适的正交表。 正交表的记号为  bL am ，其中 L代表正交表， m 是试验 次数 即 正交表的行数， b表示 水平数， a 表示因素 数 即列数。 正交表的基本性质 如下： 1）正交性 ：在正交表中任意一列中，某因素的所有水平都 出现，且出现的次 数是相等的，在任意两列之间，两因素的各种不同水平组合都出现，并且出现的次数也相等。 20 2） 均衡分布 性：在正交表中的各因素水平组合在选优区中 均衡分布。 例如图 — 2所示，在立方体中，每 一平面内只 有 3个 数据试验点，每一条直线上只 包含 1个 试验点，正交 试验 点均衡 分布在全面试验点中。 3）独立性：正交表中没有完全重 复的水平组合，从全面试验组合中挑出 的这一部分试验组合没有 重复试验 的情况 ，在讨论某一因素时，不用 考虑 其他因素的影响 ， 正交表中的试验方案能够综合处理大量 的 信息。 4）整齐可比 性 ： 整齐可比是指各个 因素的各 个 水平 之 间具有可比性。 正交表中某一因素的各个水平都均匀 搭配 着其他 因素的各个水平。 如在 3因素 3 水平试验中的 A、 B、 C3 个因素 ， A 因素的 3 个水平 A A A3各搭配 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因素 下的 3 个水平 分别 组合 了 B、 C两因素的 3 个水平， 且任意两个水平组合 不会有 重复 的情况。 A因素 3 水平之 间具有 整齐 可比性。 同理 B、 C 两 因素 的 3水平间也 具有整齐 可比性。 基于正交离散过程的蚁群算法 正交离散 过程 蚁群算法的基本原理 传统基本 蚁群算法在实际应用中主要是解决离散域的组合优化问题， 而难于解决连续域 变量 的函数优化问题，在原料配方设计等连续变量领域中 应 用困难。 然 而正交试验设计 可以综合处理大量信息，有效 地解决连续域 变量 问题。 正交离散主要是将基本蚁群算法与正交 试验 设计相结合 ，通过正交设计形成正交离散点，使连续域问题离散化， 让蚂蚁 21 在正交试验得出的几条优化路径中寻找最优解， 改进 了初始阶段蚁群算法信息素随机分布、路径杂乱无章的缺点 ， 最终可以取得满意的结果。 以原料配 方设计为例 进一步说明正交离散过程的蚁群算法。 设原料品种（ nRR~1 ）为横坐标，原料用量为  100~1iXi ，原料品种所占的 比例 iX 从 0～ 100％ 连续均匀 变化，属于典型的连续域变量问题。 由于从 0～100％之间有无穷多个节点，若用基本蚁群算法， 那么 蚂蚁将会从 start点 开始访问无穷多个节点，这样必然会造成庞大的计算量而无限延长计算时间，所求的结果也会比较分散，所以应把问题离散化。 在正交试验优化中，以品种数 作为因素数，每个 原料品种在 所占比例 范围内选定水平数。 例如： 有四个原料品种，也就是有四个因素，每个品种有三个水平 ，也就是 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 有 321 , CCC 三。