混合遗传模拟退火算法解决多机调度问题

来源:用户上传      作者: 吕青普

　　摘要：将模拟退火引入遗传算法，构造混合遗传模拟退火算法。通过对具体多机调度问题的求解，表明混合遗传模拟退火算法的效率要优于单一的遗传算法和模拟退火算法。
　　关键词：多机调度；遗传算法；模拟退火算法；混合遗传模拟退火算法
　　
　　作业调度问题是生产管理与控制的一个基本问题。按照加工设备数量和加工作业的流动方式，一般可分为单机调度、并行机调度、Flowshop调度、可重入式调度和Jobshop调度等多种类型。作业调度中的许多问题，不仅具有随机性、约束复杂、规模大及多目标冲突等特点，而且许多都属于NP完全问题，即使在单机情形也是如此。因此，如何寻求有效可行的调度求解方案，一直是生产管理与控制研究的热点和难点。
　　
　　一、多机调度问题的数学模型
　　
　　二、算法分析
　　
　　自Davis首次将遗传算法（Genetic Algorithms，GA）引入到调度问题的研究中以来，进化算法（包括遗传算法）在制造生产零件和生产调度研究领域获得了广泛的应用，并取得了较好的优化效果。遗传算法用于求解某些并行多机调度问题也有不少的研究成果。遗传算法的优点是：不受搜索空间的限制性假设的约束，不必要求诸如连续性、导数存在和单峰的假设，并且具有内在的并行性，收敛速度快，能够解决非常困难的寻优问题。当然，传统的遗传算法也有许多缺点，其中最为严重的是“过早收敛”问题。所谓“过早收敛”是指在搜索的初期，由于优良个体急剧增加使种群失去多样性，从而造成程序陷入局部，达不到全局最优解的现象。遗传算法的另一个缺陷是“GA欺骗”问题，即在GA的搜索过程中，有可能搜索到最优解然后又发散出去的现象。另外，遗传算法还有参数选择未能定量和不能精确定位最优解等缺陷。
　　模拟退火算法（Simulated Annealing，SA）又称为模拟冷却法、统计冷却法、Monte－Carlo退火法、随机松弛法和概率爬山法等。模拟退火算法是一种新的统计优化方法，其思想最早是由N．Metropolis等人借鉴统计力学中物质退火方法而提出的。1983年Kirkpatrick等人开展了一些富有成效的工作，成功地将该思想引入组合优化理论。模拟退火算法源于对固体退火过程的模拟，采用Meteropolis接受准则，并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。模拟退火算法的主要优点之一就是能以一定的概率接收目标函数值不太好的状态。即算法不但往好的方向走也可向差的方向走；这使得算法即便落入局部最优的陷阱中，理论上经过足够长的时间后也可跳出来从而收敛到全局最优解。模拟退火算法的主要缺点是解的质量与求解时间长短之间的矛盾。为得到一个好的近似最优解，需要进行反复迭代运算，当问题的规模不可避免地增大时，缺乏可行的解决途径。
　　
　　三、多机调度问题的混合遗传模拟退火算法
　　
　　从测试结果来看，混合遗传模拟退火算法在搜优率上较遗传算法和模拟退伙算法有了较大的提高。从运算过程中的数据可以看出，由于混合遗传模拟退火算法中邻域的选择、变异发生的概率都取自模拟退火的接受概率，再加上它采取了适应度拉伸系数λ，使得遗传算法的“早熟”现象得到很好的解决。另外本文所采用的混合遗传模拟算法的还具有以下优点：①优化行为的增强。它具有GA算法的优化时间性能和SA算法可以最终趋于全局最优的优点，克服了GA算法“过早收敛”问题和SA算法优化时间性能较差的缺点。②优化效率的提高。它是一种并行而且具有自动保优功能的算法，同时利用GA和SA各自不同的邻域搜索结构相结合，这样使得算法在解空间中的搜索能力所增强，优化效率得到提高。③鲁棒性的提高。它的多点搜索消弱了SA算法对初值的依赖性，同时它还利用GA算法不影响平稳分布的特性，提高了整个算法的鲁棒性。
　　遗传算法和模拟退火两种算法均属于基于概率分布机制的优化算法。遗传算法是通过概率意义下的“优胜劣汰”思想的群体遗传操作实现优化；模拟退火算法的优化机制是通过赋予搜索过程一种时变和最终趋于零的概率突变性，来避免陷入局部极小而达到全局最优。本文结合这两种算法的优缺点，将模拟退火的思想引入遗传算法，将模拟退火的接受概率应用于种群的选取以及变异操作，并采用适应值拉伸的方法，极大地缓解了遗传算法的选择压力。它不但丰富和优化了整个过程，而且增强了全局和局部意义下的搜索能力和效率。从试验结果可以看出，本文的混合遗传模拟退火算法在解决多机任务调度问题时较单一的遗传算法、模拟退火算法在优化行为与效率上有了很大的提高。
　　
　　参考文献：
　　1、许国平，叶效锋，鲍立威.基于模拟退火遗传算法的车辆路径问题研究[J].工业控制计算机.2004.24(3):58-62.
　　2、黄德才，郭海东，沈良忠.基于JIT的多目标并行多机调度问题的混合遗传算法[J].系统工程理论与实践.2004.24(3):58-62.
　　3、张婧，杨炳儒.基于混合遗传算法的聚类模式数据挖掘方法[J].微计算机信息,2006,18：219-221.
　　4、刘志刚，王建华，耿英三，欧阳森.一种改进的遗传模拟退火算法及其应用[J].系统仿真学报.2004.16(5):1099-1101.
　　5、尹文君，刘民，吴澄.进化计算在生产线调度研究中的现状与展望[J].计算机集成制造系统-CIMS-2001.7(12):1-6.
　　6、刘民，吴澄.解决并行多机提前/拖后调度问题的混合遗传算法方法[J]自动化学报.2000.26(2):258-262.
　　7、姚伟力，杨德礼，胡祥培.遗传算法对车间作业调度的研究[J]运筹与管理.1999.8(2):85-88.
　　8、周明，孙数栋.遗传算法原理及应用.国防工业出版社.1997.
　　9、行文训，谢金星.现代优化计算方法(第2版).清华大学出版社.2005.09.
　　10、陈国良，王煦法，庄镇.遗传算法及其应用.人民邮电出版社.2001.02.
　　11、王立平，曹立明.遗传算法――理论、应用与软件实现[M].西安:西安交通大学出版社，2002.
　　12、康立山.非数值并行算法(第一册)―模拟退火算法.科学出版社.2000.6.
　　*基金项目：天津科技攻关项目 编号：06YFGZGX05500
　　（作者单位：天津财经大学理工学院信息科学与技术系）
　　注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”

转载注明来源:https://www.xzbu.com/2/view-431998.htm