Immune Genetic Algorithm Based on Orthogonal Experiment for Scheduling Problems
-
摘要: 提出了优先权值编码与三个体交叉算子相结合的免疫遗传算法．该编码方法不仅满足车间作业调度问题（Job-shop Scheduling Problem，JSP）中工序优先约束的要求，而且可以有效避免非可行解的产生．三个体交叉的交叉算子在保证后代群体多样性的前提下，在很大程度上继承了父代的优良特性．基于正交试验的免疫算子丰富了抗体群的多样性，从而大大提高了算法克服局部收敛的能力．在算法参数的选取上，采用正交试验法来确定参数值，加快了收敛速度．对车间作业调度的几个典型问题进行了仿真，并与其它算法进行了比较．实验结果表明了该算法的有效性，仿真结果令人满意．Abstract: 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 three-individual-crossover inherit to a great degree the excellent characteristics from their parents while guaranteeing the diversity of their descendants.The immune operator based on orthogonal experiment diversifies the antibodies,which greatly improves the algorithm's ability to overcome partial convergence.This paper uses orthogonal experiment method to confirm the parameters,which enhances the convergence speed.Simulations are made on several benchmark 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.
-
-
[1] Holland J H.Adaptation in Natural and Artificial Systems[M].Cambridg,MA,USA:The MIT Press,1992. [2] Davis L.Job shop scheduling with genetic algorithms[A].Pro-ceedings of the 1st International Conference on Genetic Algorithm[C].Mahwah,NJ,USA:Lawrence Erlbaum Associates,Inc.,1985.136～140. [3] 李茂军,罗安,童调生.人工免疫算法及其应用研究[J].控制理论与应用,2004,21(2):153～157. [4] 徐震浩,顾幸生.不确定条件下的中间存储时间有限的FlowShop提前/拖期调度问题[J].控制理论与应用,2006,23(3):480～486. [5] 李云雁,胡传荣.试验设计与数据处理[M].北京:化学工业出版社,2005. [6] 王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003. [7] 赵宏立,庞小红,吴智铭.一种使用再编码染色体求解Job-Shop问题的并行遗传算法[J].机械科学与技术,2004,23(12):1421～1425. [8] 徐雪松,诸静.免疫遗传算法的改进及其在模糊控制中的应用研究[J].信息与控制,2003,32(5):462～466. [9] 柳毅,马慧民,叶春明.免疫遗传算法在柔性Job-shop调度问题中的应用[J].上海理工大学学报,2005,27(5):393～396. [10] 杨晓梅,曾建潮.采用多个体交叉的遗传算法求解作业车间问题[J].计算机集成制造系统,2004,10(9):1114～1119.
计量
- 文章访问数: 1725
- HTML全文浏览量: 2
- PDF下载量: 360
下载:
