基于混合多智能体遗传算法的作业车间调度问题研究

《基于混合多智能体遗传算法的作业车间调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2017年2月第43卷第2期北京航空航天大学学报JournalofBeijingUniversityofAeronauticsandAstronauticsFebruary2017V01．43NO．2http：／／bhxb．buaa．edu．cnjbuaa@buaa．edu．cnDOI：10．13700／j．bh．1001-5965．2016．0103基于混合多智能体遗传算法的作业车间调度问题研究李小涛，彭种+(北京航空航天大学机械工程及自动化学院，北京100083)摘要：针对作业车间调度问题(JSP)的非确定性多项式特性与解空间分布的大山谷属性，本文提出一种多智能体遗

2、传算法(MAGA)与自适应模拟退火算法(ASA)的混合优化算法，用于寻找最大完工时间最短的调度。首先，将每个染色体视作独立的智能体并采用工序编码方式随机初始化每个智能体，结合多智能体协作与竞争理论设计了实现智能体之间交互作用的邻居交互算子，进而利用一定数量智能体进行全局搜索，找到多个适应度较高的可行解。其次，为避免算法陷入局部最优，采用ASA对每个智能体开展局部寻优。最后，通过基准测试库中典型实例的计算结果验证了该算法的有效性。关键词：作业车间调度(JSP)；多智能体；遗传算法；邻居交互算子；自适应模拟退火算法(ASA)中图分类号：TP301．6；F406．2文献标识码

3、：A文章编号：1001．5965(2017)02加410-07车间调度是生产加工的重要环节，基本任务之一是合理安排各机器上的待加工工件的顺序，使得最大完工时间最短。作为流水车间调度问题的扩展，作业车间调度问题(JobshopSchedulingProblem，JSP)中每个工件可以有特定的工序安排，1976年Garey等⋯证明了它是一个非确定性多项式(Non—deterministicPolynomial，NP)难题。对于JSP，早期研究中大多采用的方法可分为近似方法和精确方法。其中近似方法以优先规则法心1和瓶颈移动法"1为代表，其求解过程较为复杂且计算量很大；而对于基

4、准测试库H1中10工件10机器的问题，Applegate与Cook∞1采用的分支定界法是非常有效的精确方法，但对规模更大的情形却不太适用。近年来许多元启发式算法相继提出，用于求解JSP的有遗传算法。61、模拟退火算法o“、粒子群算法旧J、生物地理学优化算法。91等。遗传算法的主要优点是通用性强，它适用于各类优化问题‘1“”。，但在求解离散空间且具有NP特性的优化问题时容易陷入局部最优。通过引入多智能体协同理论，Zhong等¨4。提出了用于连续空间优化的多智能体遗传算法(MuhiagentGeneticAlgorithm，MAGA)，Sivasubramani和Swaru

5、p¨划将多智能体差分算法用于电力系统的无功优化，改进后的算法不仅有良好的全局和局部寻优能力，且具有快速收敛性和较好的鲁棒性。对于复杂的组合优化问题，一般来说没有通用的算法框架，特别是对于解空间分布类似大山谷结构的JSP，采用单一算法往往难以找到问题的最优解，研究的趋势是将具有良好全局搜索能力的算法和局部搜索算法相结合‘1⋯。例如，Gao等⋯1结合遗传算法与变邻域算法求解JSP，Xia和wu¨¨运用粒子群算法与模拟退火算法混合寻优。模拟退火算法是一种广泛应用的局部搜索算法，通过以一定概率接受劣解使得算法具有跳出收稿日期：2016-01-26；录用日期：2016-02—29

6、；网络出版时闰：2016-03-0715：08网络出版地址：WWW．cnki．net／kcms／detail／11．2625．V．20160307．1508．001．html基金项目：国家重大科技专项(2015ZX04005005)}通讯作者：E-mail：pch@buaa．edu．cn引用格式：李小游，彭种．基于混合多智能体遗传算法的作业车间调度问题研究fJJ．北京航空航天大学学报，2017，43(2)：410—416．LIXT，PENGC．Hybridmuttiagentgeneticalgorithmforjobshopschedulingprobleme】1．J

7、ournalofBeqingUniversityofAeronauticsandAstronautics，2017，43f2)：410—416(inChinese)．第2期李小涛，等：基于混合多智能体遗传算法的作业车间调度问题研究411局部最优的能力，寻优结果的好坏取决于退火进度表的选择和邻域解的产生机制。精细的退火进度表能够使寻优的效果更好，利用在马尔可夫链平稳分布下的目标函数均方差表达式，Romeo等¨9。成功推导出一种自适应退火策略。对于JSP的局部寻优而言，最早被提出且较为成功的邻域结构是由vanLaarhoven等"。提出的N2