论文部分内容阅读
本文从蚁群优化算法理论模型角度以及在生产调度问题中的应用角度开展了如下研究: 定义了蚁群算法考虑结点模式和弧模式信息素分布的解构造图,并把蚁群算法的解构造过程形象为蚂蚁在解构成元素组成的解构造图上按照分布在弧或者结点上的信息素指引进行概率性旅行的问题,并提出了蚁群算法基于解构造图的解空间参数化概率分布模型并在此模型上提出了蚁群算法的统一框架。 基于解空间参数化概率分布模型,首先提出了一个以概率1收敛于最优解的解空间概率分布的迭代更新过程,然后提出了通过最小化不同分布间的交互熵距离以及蒙特卡洛采样来逼近此迭代过程的最小交互熵信息素更新规则,接着分别给出了弧模式以及结点模式信息素分布模型下的最小交互熵等式。本章还提出了一种全局归一化的的蚂蚁种子信息素更新规则,该规则能保证分布在整个解构造图上的信息素的总量保持恒定,同时解决了信息素初始化的问题以及消除了解质量函数的量纲对算法性能的影响。然后定义了一种特殊的解构造图-矩阵解构造图,并提出了Flowshop问题的矩阵解构造图模型,同时针对矩阵解构造图提出了局部归一化的蚂蚁种子信息素更新规则,该规则能保证分布在矩阵解构造图每一行结点上的信息素总量保持恒定。此外,还定义了无约束矩阵解构造图,并证明了无约束矩阵解构造图的局部归一化蚂蚁种子信息素更新规则为最小交互熵信息素更新规则。本章最后提出了解决并行机调度问题的蚁群算法,该算法把并行机调度问题映射为无约束矩阵解构造图,并在算法的信息素更新过程中应用了无约束矩阵解构造图的局部归一化蚂蚁种子信息素更新规则,与其他几个高性能算法的仿真对比试验证明这种方法是非常有效的。 把组合优化问题描述为一个多阶段序列决策问题,并对蚁群优化算法中解构造过程所对应的有限状态马尔科夫决策过程用强化学习理论的框架进行描述,同时说明了所有蚁群算法均满足强化学习理论中基于马尔科夫状态的不完全信息的广义策略迭代算法框架。此外在强化学习的理论框架内说明了AS算法是一种基于蒙特卡洛方法的强化学习算法,ACS和Ant-Q算法是一种蒙特卡洛方法与瞬时差分方法在形式上相结合的强化学习算法。本文还在蚁群算法中引入强化学习的资格迹理论并提出了一个新颖的基于资格迹的蚁群优化算法Ant(λ),该算法实现了蒙特卡洛方法与瞬时差分方法的数学意义上结合,并能使蚂蚁获得的延迟强化信号及时地在其旅行路径上反向传播。11 摘 要 提出了FIOWShop问题的一个局部归一化蚂蚁种于算法ACOPORM,一个引入停滞状态脱离机制以及信息素踪迹限制机制的ACO STAG算法和一个基于资格迹的Ant Q0)算法。算法还提出了一种基于Dannenbring方法的启发式信息。仿真试验表明,信息素的结点模式总体优于孤模式;启发式信息能较大改进算法性能;ACO STAG算法的信息素踪迹更新过程中的停滞状态脱离机制以及信息素踪迹限制机制能帮助蚂蚁跳出局部最优解;此外Ant QO)算法的资格迹机制能大大改进采用弧模式解构造图的蚁群算法性能。给出了FIOWShop问题的几种基于关键路径的邻域结构,并把蚁群算法与邻域搜索相结合构成混合算法,与其他算法在Taillard流水作业调度测试问题集上的比较试验表明,混合算法性能更优。 提出了混合中间存储策略下多产品间歇生产过程调度问题的一种完成时间算法,该算法考虑了产品传输时间,与产品生产顺序有关的设备准备时间,中间存储清洗时间以及中间存储“双传输”对完成时间的影响。采用ACO NORM和ACO STAG算法用于解决多产品间歇生产过程的优化调度问题。还提出了一种改进的基于Dannenbring方法的启发式信息。仿真试验表明,启发式信息能较大改进算法性能。为加速算法的收敛,蚁群算法与邻域搜索相结合构成混合算法,用一些测试问题对本章算法进行试验评价,试验结果表明本章提出的方法的有效性。 利用受控赋时Petri同对柔性生产线调度中的离散事件建模,在山Petri网仿真运行获得调度性能评价的基础上,采用两级递阶进化优化方法求解柔性生产过程的优化调度问题,即山蚁群优化方法优化加工路径,然后对蚁群在信息素指引下所构造的加工路径,由遗传算法优化在同一机器上加工的作业排序。在蚁群算法解构造过程中提出了一种有效的启发式信息。测试问题的求解结果说明了算法的有效性。 提出了一种ACO-BATCH算法,用十解决有限批量流水线分批与优化调度问题。在考虑与批处理顺序相关的批处理设备准备时间和产品批在处理设备间的传输时间基础上,提出了无中间存储策略(*IS )和零等待存储策略(*W)下流水作业工序流程的仿真模型和基于此模型的完成时间算法。一组60个仿真测试问题的求解结果说明了算法的有效性。