【作者】 林笑旭；

【导师】 吴迪；

【作者基本信息】 大连理工大学 ， 计算机应用， 2009， 硕士

【摘要】 遗传算法作为一种新的全局优化搜索算法,以其简单通用,鲁棒性强和并行处理以及应用范围广等显著特点,在诸多人工智能计算领域获得了广泛的应用,同时取得了大量的研究成果。本文主要对遗传算法进行了学习与研究,提出了一种新的改进的遗传策略MICGA。本文首先介绍了课题的研究背景以及遗传算法的搜索机制并简要分析了遗传算法在搜索过程中的优势与其广泛的应用背景。然而遗传算法本身存在早熟以及对某些特定问题搜索慢等缺陷。针对缺陷,基于混合遗传算法的思想,融合了混沌与免疫两种机制并基于模式提出了改进的算法MICGA。混沌是看似随机无序,但却有着精致的内在结构,利用混沌随机性、遍历性和对初值敏感的特性初始化种群,使初始种群抗体能够均匀的分布在解空间中,避免了由于初始种群完全随机产生而导致的搜索速度慢的弊端;通过免疫原理的浓度机制与多样性原理改进了选择算子,保证了种群多样性,避免由于种群多样性降低而引起的早熟现象。同时,在混合的算法基础上,基于遗传算法中串的实质是模式的运算,根据模式的概念,提出了模式算子,对变异之后的种群整体进行了模式的改进,即在变异操作之后,对适应度值高的个体排序,在一定权重下,识别出有利于搜索趋势的模式并使用该模式对种群中的个体进行修改,提高群体质量,并通过退火策略的原理通过子父代的共同作用防止退化的产生,从而达到加快向最优解靠近的收敛速度;最后,对变化后的个体加以混沌扰动,避免算法陷入局部最优解,提高局部搜索效率。通过对经典的测试函数算例的测试,利用平均截止代数和截止代数熵两个性能指标对算法MICGA进行了评估,测试评估结果说明改进后的算法在算法的稳定性及搜索的速度上均有了稳步的提高。更多还原

【Abstract】 As a new global optimization search method, with its many characteristics like simple and universal, robust, parallelism and extensive use, Genetic Algorithm has been applied in many fields as artificial intelligence and gets a lot of research findings. Based on the study and the research about the genetic algorithm, this thesis proposes a new advanced genetic strategy which is called MICGAFirstly, this thesis introduces the research background and basic search mechanism about genetic algorithm and expounds its traits and applications briefly. But this algorithm itself has some defects like premature and slow convergence to specific problems, etc. To the defects like that, with the thought of inosculation, this advanced algorithm takes two optimization mechanisms, chaos and immune. It looks like that chaos is stochastic and out-of-order, but it is a phenomenon by inherent exquisite structure. Use the stochastic, ergodicity and sensitivity of initial value of chaos to generate population and this process can make the individuals distributed in the space of solutions evenly, avoiding the defects of slow convergence caused by the totally stochastic. Immune mechanism is used to amend the select operator by its density of antigen to maintain the diversity of the population in order to prevent premature convergence. Based on all of those mentioned, it also draws into a new method named schema recognition which is highlighted by the schema to improve the whole population. Its process is that after the mutation operator, the individuals are sorted by their fitness value, then with certain weight-value the best schema in this generation is recognized to improve the whole population, meanwhile it takes anneal principle to avoid degeneration condition. The convergence velocity is fast by these operators. At last, it draws into chaotic perturbation operation to do heuristic mutation to accelerate convergence velocity and improve searching capability. Through some tests on the classic test function with two evaluative criteria, the average truncated generation and the distribution entropy of truncated generations, the test results show that this novel algorithm is effective.更多还原