基于正交试验的免疫遗传算法在调度问题中的应用

Immune Genetic Algorithm Based on Orthogonal Experiment for Scheduling Problems

提出了优先权值编码与三个体交叉算子相结合的免疫遗传算法.该编码方法不仅满足车间作业调度问题(Job-shop Scheduling Problem,JSP)中工序优先约束的要求,而且可以有效避免非可行解的产生.三个体交叉的交叉算子在保证后代群体多样性的前提下,在很大程度上继承了父代的优良特性.基于正交试验的免疫算子丰富了抗体群的多样性,从而大大提高了算法克服局部收敛的能力.在算法参数的选取上,采用正交试验法来确定参数值,加快了收敛速度.对车间作业调度的几个典型问题进行了仿真,并与其它算法进行了比较.实验结果表明了该算法的有效性,仿真结果令人满意.

An immune genetic algorithm is proposed based on the combination of a preference weight coding and a three-individual-crossover. This coding method not only meets the demand of operational preferential constraint in Job-shop Scheduling Problem （JSP） but also avoids unfeasible solutions effectively. The crossover operators of threeindividual-crossover inherit to a great degree the excellent characteristics from their parents while guaranteeing The diversity of their deseendauts. The immune operator based on orthogonal experiment diversifies the antibodies, which greatly improves the algorithm＇s abilily to overcome partial convergence. This paper uses orthogonal experiment method to confirm the parameters, which enhances the convergence speed. Simulations are made on several henchmark problems in JSP, and comparisons are made between the presented algorithm and other algorithms. With satisfactory results, the experiments prove that the proposed algorithm is valid for JSP problems.