【作者】 马佳；

【导师】 高立群；

【作者基本信息】 东北大学 ， 控制理论与控制工程， 2008， 博士

【摘要】 随着生产社会化的不断深入,生产规模及物资流通量越来越大,复杂性也越来越高,优化调度问题已经渗透到科研及工程应用的各个领域。近代人工智能技术的飞速发展对于解决优化调度问题提供了有力的理论基础保障。因此,在该领域的研究具有重要的理论意义和实用价值。传统优化调度方法存在着种种不足,已经不能很好地适用于大规模复杂问题。近年来,多学科交叉研究为解决此类问题提供了新的思路。其中以模仿生物免疫机理为理论基础的人工免疫优化算法在各领域的研究与应用中表现出优异的性能,已成为人工智能领域一个新的研究热点。免疫遗传算法隶属于人工免疫优化算法范畴,该算法将免疫思想融入遗传进化流程中,使其有选择、有目的地利用特征信息来促进种群向优化趋势发展,同时抑制优化过程中的退化现象。本文在归纳了基本免疫遗传算法的原理与特点的基础上,总结其不足之处,综合运用多种免疫学和遗传学思想,从多种角度对算法进行改进,并将改进算法应用于几种典型的优化调度问题。通过实例仿真,验证改进算法的有效性和实用价值。本文的主要研究内容和成果如下：(1)深入研究人工免疫系统及其算法,系统地介绍了人工免疫系统的生物学原理及其仿生机理,详细阐述了人工免疫系统的具体研究内容和范围。在剖析基本免疫遗传算法原理、框架及特点基础上,着重分析了基本免疫遗传算法解决大规模复杂问题时,在稳定性、收敛性及适应性等方面的不足,提出了相应的改进思路。(2)针对基本免疫遗传算法存在的局部搜索能力差、早熟收敛等问题,借鉴生物免疫系统的克隆选择思想及记忆理论,提出了一种免疫克隆算法。该算法通过引入克隆算子来改善基本免疫遗传算法局部搜索能力差的缺点。通过克隆增殖和超变异算子加大种群的搜索范围,保持了种群的多样性。并把该算法用于求解物流配送调度问题,通过计算不同规模、不同类型的Benchmark问题,验证了算法的稳定性和有效性。(3)针对基本免疫遗传算法存在易陷入平衡态和丢失优势基因等不良现象,提出了一种多种群、双倍体免疫遗传算法。该算法一方面采用多种群同时进化,交换种群之间优势个体所携带的遗传信息,以打破种群内平衡态达到更高的平衡态；另一方面通过双倍体编码方式延长了有用基因块的寿命,显著提高了算法的局部搜索效率,保持了种群的多样性,有利于算法跳出局部最优解。并将该算法应用于求解单级多资源限制生产批量计划问题。通过仿真实例证明,多种群双倍体免疫遗传算法不但具有良好的全局和局部搜索能力,并且具有很好的逼近精度和搜索速度。(4)针对基本免疫遗传算法由于静态地指定交叉、变异概率和疫苗而带来的搜索过程缓慢甚至停滞不前等缺点,提出了一种自适应免疫遗传算法。该算法通过自适应调整交叉、变异概率,动态生成疫苗等方式,改善了基本免疫遗传算法收敛速度缓慢、疫苗失效等缺点。并将该算法应用于求解柔性作业车间调度问题,应用不同算法对实例进行仿真,将自适应免疫遗传算法的仿真结果同遗传算法、免疫遗传算法进行对比分析,证明改进算法有良好的收敛性和鲁棒性。本文通过以上的研究工作和仿真结果分析,对改进的免疫遗传算法进行综合性地概括、归纳和总结。在处理复杂优化调度问题方面提出了一些改进的思想,并进行了算法实现和仿真。对有待进一步深入研究的问题进行了设想,对免疫遗传算法解决相关优化调度问题进行了展望。更多还原

【Abstract】 With the development of socialization of production and the increase of production scale and circulation of materials as well as the improvement of the complexity, optimization scheduling problem is already impregnated into every domain of scientific research and engineering applications. In modern times, the rapid development of artificial intelligence technology has provided a strong theoretical foundation on solving optimization scheduling problem. Therefore the research in this field has important theoretical meaning and practical value. The traditional optimization scheduling method has many shortcomings which would be unable to effectively apply to large scale complex problems. In recent years, interdisciplinary acrossing research has offered a new train of thought to solve such kind of problem, in which artificial immune optimization algorithm based on the theoretical foundation of imitating biological immune mechanism has demonstrated outstanding performance in various researching and application fields and has become a new hotspot in the fartificial intelligence area.Immune genetic algorithm is subordinate to artificial immune optimization algorithm category. The algorithm put immune thinking into genetic evolution process, which make it have destination to promote population evolving towards optimization trend selectively by using characteristic information. At the same time, it restrains the degraded phenomenon in optimization course. This paper summarizes the theory and characteristics of simple immune genetic algorithm, sums up its shortcomings, improves the algorithm by using various immunology and genetics thinking, and applies the improved algorithm to several typical optimization scheduling problems. Through simulating of examples, the effectiveness and practical value of the algorithm is verified. The main contents and results are as follows:(1) Researching on the artificial immune system and its algorithm deeply, the paper introduces systematacially the biology principle and simulate mechanism of artificial immune system and elaborates the specific content and of artificial immune system. Having analysed the principle and characteristic of simple immune genetic algorithm, the paper emphasizes the lack of simple immune genetic algorithm at stability, convergence and adaptability on solving complex and large scale issues, and puts forward corresponding improving ideas.(2) According to the defects of simple immune genetic algorithm that has the poor local search capacity and premature convergence, the paper draws on the thinking of clonal selection and memory theory in biological immune system, and puts forward a sort of immune clonal algorithm. The proposed algorithm reforms the defects of of simple immune genetic algorithm for its poor local research ability by using clonal operator, increases the searching scope and maintains the diversity of the population through clonal proliferation and super mutation operators,. The paper applies immune clonal algorithms to solving the capacitated vehicle routing problems and verifies the validity and stability of improved algorithm through calculating the Benchmark problems by different sizes and types.(3) According to the ill phenomenons of simple immune genetic algorithm that is easy to fall into equilibrium state and lose advantage genes, the paper puts forward a kind of multi population diploid immune genetic algorithm. On the one hand, the algorithm makes various groups evolving synchronously and exchanges advantaged individuals carrying hereditary information in population, which breaks current equilibrium state in population to reach a higher equilibrium state; On the other hand, it uses the diploid coding mode to prolong the life of useful genic blocks, improve the local search efficiency of algorithm obviously and maintains the diversity of population, which makes the algorithm jump out of local optimal solution. The paper applies the improved algorithm to solving single item capacitated lot-sizing schedule problem. The simulation of examples shows that multi population diploid immune genetic algorithm not only has well overall and local search ability, but also has a well approaching precision and searching speed.(4) According to the defects of simple immune genetic algorithm that designates crossover probability, mutation probability and vaccine statically which makes the search course to perform slowly and even come to a standstill, the paper puts forward a sort of adaptive immune genetic algorithm. Through adjusting crossover and mutation probability adaptively and generating vaccines dynamically, the algorithm improve the shortcomings of simple immune genetic algorithm for slow convergence and vaccine failure. The paper applies the algorithm to solving flexible job-shop scheduling problem, carries out simulation using different algorithm, comparaes the simulation results of adaptive immune genetic algorithm with genetic algorithm and immune genetic algorithm and has a analysis. The contrastive analysis proves that the improved algorithm has a well convergence and robustness.Through studies and analysis of simulation results above, the paper performances comprehensive summary, conclusion and summarize to the improved immune genetic algorithms. In the aspect of handling complex optimization scheduling problem, the paper has put forward some thoughts of improvement, carried out realization and simulation of the algorithm. The paper has a envisagement to the problem for future research and has a prospect on solving optimization scheduling problem using immune genetic algorithm.更多还原