论文部分内容阅读
【摘 要】 在解决Job shop调度问题过程中，针对蚁群算法在收敛速度和全局寻优方面的缺陷，提出一种改进的平滑自适应蚁群算法（SA-ACO）。该算法在循环过程中通过改变自适应参数的值，随机改变蚂蚁搜索范围；并采用自适应平滑机制对信息素进行更新，加快算法收敛速度。当算法陷入局部最优时，自适应地改变挥发系数的取值，使算法跳出局部最优，最终收敛到全局最优解，同时采用奖罚策略加快算法收敛速度。
【关键词】 改进蚁群算法；Job shop调度；平滑机制；自适应；车间调度
随着科学技术的进步和计算机技术的发展，促使大规模定制生产方式向品种多批量小的生产方式转变。本文采用一群算法，針对车间生产调度问题具有的建模/计算复杂性、不确定性、多目标性、多约束性、离散性等特点[2]，提出一种改进的平滑自适应蚁群算法，提高算法收敛速度；当算法进入局部最优时，采用自适应平滑机制对信息素的值进行调整，提高算法的全局搜索能力[3]。
一、工序转移规则
所有蚂蚁在搜索最优路径的过程中，只能选择前期工序已经加工完成而本身尚未加工的工序，将所有符合条件的工序节点放入可选工序集ap中，将所有已经完成的工序放入蚂蚁路径集tabu中。根据以下公式计算出各可选工序的转移概率。
（1）
其中，为从节点到节点的转移概率，蚂蚁位于节点，为可选工序集，即在工序加工完成后，被放入蚂蚁路径集tabu中。 和分别表示信息素和可见度的偏重系数。
二、改进信息素更新策略
该算法对最优路径进行奖励，对最差路径进行惩罚，可以加快算法收敛速度并跳出局部最优。但此方法不能保证彻底清除早熟现象，故将信息素平滑机制与之结合，其主要作用是当各路径上的信息素浓度相差比较大时，可以降低较优路径上信息素的浓度[4]。基本做法是：当前路径上的信息素浓度明显高于其它路径时，为防止算法局部收敛，采用信息素平滑机制，降低该路径上的信息素的值，进而扩大搜索范围，既加快算法的运行速度，还提高该算法寻优性能。在整个蚂蚁寻优路径中，只让最短路径上的蚂蚁释放信息素
四、本章小结
本文提出的改进平滑自适应蚁群算法针对不同的情况，给出了工序选择规则、信息素更新规则和新解接受规则等改进蚁群算法基本规则的设计方法。采用两种信息素自适应调整策略和奖惩措施相结合，并与平滑机制相结合，成功解决了原始算法全局搜索性差，收敛速度慢的问题，并提高了算法的稳定性。
参考文献：
[1]宋存利.生产调度问题及其智能优化算法研究[D].辽宁：大连理工大学，2011：1-20.
[2]徐俊刚，戴国忠，王宏安.生产调度理论和方法研究综述[J].计算机研究与发展：2004，41（2）：257-267.
[3]许瑞，陈华平，邵浩等.极小化总完工时间批调度问题的两种蚁群算法[J].计算机集成制造系统：2010，16（6）：1255-1264.
[4]Gu Wen bin， Tang Dun bing， Zheng Kun. Minimizing makespan in Job-shop Scheduling Problem Using an Improved Adaptive Particle Swarm Optimization Algorithm[C]. Chinese Control and Decision Conference （CCDC）， 2012， 24： 3189-3193.
【关键词】 改进蚁群算法；Job shop调度；平滑机制；自适应；车间调度
随着科学技术的进步和计算机技术的发展，促使大规模定制生产方式向品种多批量小的生产方式转变。本文采用一群算法，針对车间生产调度问题具有的建模/计算复杂性、不确定性、多目标性、多约束性、离散性等特点[2]，提出一种改进的平滑自适应蚁群算法，提高算法收敛速度；当算法进入局部最优时，采用自适应平滑机制对信息素的值进行调整，提高算法的全局搜索能力[3]。
一、工序转移规则
所有蚂蚁在搜索最优路径的过程中，只能选择前期工序已经加工完成而本身尚未加工的工序，将所有符合条件的工序节点放入可选工序集ap中，将所有已经完成的工序放入蚂蚁路径集tabu中。根据以下公式计算出各可选工序的转移概率。
（1）
其中，为从节点到节点的转移概率，蚂蚁位于节点，为可选工序集，即在工序加工完成后，被放入蚂蚁路径集tabu中。 和分别表示信息素和可见度的偏重系数。
二、改进信息素更新策略
该算法对最优路径进行奖励，对最差路径进行惩罚，可以加快算法收敛速度并跳出局部最优。但此方法不能保证彻底清除早熟现象，故将信息素平滑机制与之结合，其主要作用是当各路径上的信息素浓度相差比较大时，可以降低较优路径上信息素的浓度[4]。基本做法是：当前路径上的信息素浓度明显高于其它路径时，为防止算法局部收敛，采用信息素平滑机制，降低该路径上的信息素的值，进而扩大搜索范围，既加快算法的运行速度，还提高该算法寻优性能。在整个蚂蚁寻优路径中，只让最短路径上的蚂蚁释放信息素
四、本章小结
本文提出的改进平滑自适应蚁群算法针对不同的情况，给出了工序选择规则、信息素更新规则和新解接受规则等改进蚁群算法基本规则的设计方法。采用两种信息素自适应调整策略和奖惩措施相结合，并与平滑机制相结合，成功解决了原始算法全局搜索性差，收敛速度慢的问题，并提高了算法的稳定性。
参考文献：
[1]宋存利.生产调度问题及其智能优化算法研究[D].辽宁：大连理工大学，2011：1-20.
[2]徐俊刚，戴国忠，王宏安.生产调度理论和方法研究综述[J].计算机研究与发展：2004，41（2）：257-267.
[3]许瑞，陈华平，邵浩等.极小化总完工时间批调度问题的两种蚁群算法[J].计算机集成制造系统：2010，16（6）：1255-1264.
[4]Gu Wen bin， Tang Dun bing， Zheng Kun. Minimizing makespan in Job-shop Scheduling Problem Using an Improved Adaptive Particle Swarm Optimization Algorithm[C]. Chinese Control and Decision Conference （CCDC）， 2012， 24： 3189-3193.