求解Job-Shop调度问题的多种群双倍体免疫算法研究

Job-Shop调度问题是制造工程学科的NP难题,传统求解方法都有各自的特色和不足。免疫算法是模拟生物免疫系统功能的一种智能优化算法,具有解决复杂工程问题的潜力。针对免疫算法存在的缺陷,提出了多种群双倍体免疫算法,用于求解Job-Shop调度问题。建立了Job-Shop调度问题的数学模型,对典型Job-Shop问题进行了仿真,仿真结果不但验证了它的有效性,而且表明此算法优于其它算法。

Multi-Colony Diploid Immune Algorithm (MCDIA) for Better Job-Shop Scheduling

Aim.Existing immune algorithms(IAs) for job-shop scheduling suffer,in our opinion,from two shortcomings: prematurity and stagnation.In order to suppress these two shortcomings,we propose MCDIA.The colonies hybridize some iterations through hybridization operators,but,after some time,the MCDIA can break the balance state of IA and enter higher balance state through exchanging available information carried by the excellent anti-bodies.Furthermore,the MCDIA distributes the most excellent anti-bodies to each colony through the pass excellence operator,helping to implement the parallel operation among the colonies and quicken evolution speed and suppress prematurity.To find the gene segments of optimal solution,we introduce the concept of diploidy to separate anti-body into implicit and explicit parts and introduce the explicit immunity operator and implicit-explicit reset operator to prolong the life-cycle of usable gene segments and to keep the diversity of the colonies as a whole.Finally we use three algorithms,including MCDIA,to simulate the typical job-shop scheduling benchmark problem LA03.The simulation results presented in Table 2 in the full paper show preliminarily that our MCDIA has the following two merits compared with the other two algorithms: the average windage probability of the optimal value is the smallest;the probability of obtaining globally optimal value is 70%,much higher than the 0% and 20% for the other two algorithms respectively.