小生境免疫算法解决作业车间调度问题

针对免疫算法在解决组合排序问题时一般表现不佳的问题,采用多克隆算子以及独特的浓度控制机制形成具有增强搜索能力的新型免疫算法。多克隆算子与遗传算法中的交叉算子近似,它拓宽了普通免疫算法仅凭高变异方式形成的狭窄搜索空间;基于小生境的浓度控制机制借鉴生物学上的小生境概念,通过相似个体群中选择概率的不均衡分配有效避免算法掉入局部陷阱。所构造的小生境免疫算法在对多个作业车间调度算例的仿真过程中体现了较好的效果。

Niche-based immune algorithm for job shop scheduling problems

To improve the inefficiency of the immune algorithm in solving combinatorial optimization problems including job shop scheduling problems,this paper adopts the multi-clone operator and a unique density-control scheme to improve the immune algorithm’s optimizing ability.The multi-clone operator is introduced from the genetic algorithm to widen the searching space of the problem,and the density-control scheme is enlightened by the concept "niche" in biology,which can lower similar individual group’s propagation probability among the population to avoid local trap in searching.The algorithm is designed for job shop scheduling problems,whose effect is validated by a series of job-shop scheduling benchmark problems.