改进的DNA免疫遗传算法在车间调度中的应用

Application of Improved DNA Immune Genetic Algorithms on Workshop Scheduling

根据生命科学中免疫系统的信息处理机制,在一般遗传算法的基础上,将免疫算法和DNA遗传算法相结合,提出一种用于车间调度的新DNA免疫遗传算法。引入一个遗传密码表,用于DNA碱基链的解码;算法中子群体之间的信息交换采用孤岛模型;引入一个疫苗库,通过接种疫苗提高抗体的适应度,通过免疫选择防止种群的退化。这些改进措施对降低算法的复杂程度、提高算法的收敛速度和全局搜索能力有重要意义。应用标准测试集中的测试用例和实际调度中的问题对改进后的算法进行了测试。仿真程序表明,该算法能以较快的速度完成给定范围的搜索和全局优化任务。

According to the information processing mechanism of an immune system in biotic science, on the basis of simple genetic algorithm, a new DNA immune genetic algorithm for job shop scheduling through combining immune algorithm with DNA genetic algorithm was proposed. A genetic codon table was built to decode DNA base chain. The island model was employed for information exchange between subgroups in this algorithm. The fitness of an antibody by vaccination from a vaccine base was raised, and species degeneration by immune selection was prevented. These improved measures were of great significance on reducing complexities and enhancing convergence velocity, as well as increasing global searching ability of the algorithm. The improved algorithm was tested through using examples in the standard test set and the actual problem in scheduling. The simulation results of the test show that this algorithm can complete the task of the fast search in the given range and global optimization.