Title: | 遗传算法的若干改进及应用 |
Author: | 周敏
|
Issued Date: | 2001
|
Major: | 计算机应用技术
|
Degree Grantor: | 中国科学院软件研究所
|
Place of Degree Grantor: | 中国科学院软件研究所
|
Degree Level: | 博士
|
Keyword: | 遗传算法
; 交叉
; 变异
; 收敛
|
Abstract: | 遗传算法是一种概率搜索算法,其基本思想是模拟生物进化过程。由于遗传算法不受搜索空间的限制性假设的约束,不要求解空间有连续性、可导等性质,以及其固有的并行性,目前在许多领域得到了广泛的运用。本文介绍了其理论基础,并对诸如未成熟收敛、遗传漂移及如何保持群体的多样性等有关问题作了探讨,设计了一种函数优化算法,利用共享函数来量度群体的多样性,从而动态的调整交叉和变异概率。最后,针对经典问题货郎担问题,设计了一种新的交叉算子,引进“杂交优势”思想,实现了一种启发式搜索策略。对于解包含大量最优路径片段的实验结果,提出了“位移”变异算子,该变异算子能有效的增加最优路径片段进行最优组合的概率。 |
English Abstract: | Genetic Algorithm is a searching method using probability and its basic theorem is to simulate the biology evolution. GA do not require the solution space to be continuious and diravable. Its few limitation on the presumption of the solution space and built-in parallelism make it a useful method in many area. This article briefly summarizes the rationales of Genetic Algorithm and gives an intensive discussion about the premature convergency, genetic drifting and society diversity. Based on the discussion, I designed Genetic Algorithm to solve the problem of function optimization. The algorithm utilize the "share function" to measure the society diversity which in turn decide frequency of crossover operation and mutation operation. In order to solve the TSP, we present a new crossover operator by using the theory of "beneficial crossover". With this new operator, we build up a heuristic searching strategy. Experiments show that there are many valuable "crumbs" in the solution which can be combined into good solution by exchanging the position of these "crumbs". So we design a "crumb switching" mutation operator which can effectively improve the possibility of the right combination of these "crumbs". |
Language: | 中文
|
Content Type: | 学位论文
|
URI: | http://ir.iscas.ac.cn/handle/311060/6806
|
Appears in Collections: | 中科院软件所
|
File Name/ File Size |
Content Type |
Version |
Access |
License |
|
LW004462.pdf(1506KB) | -- | -- | 限制开放 | -- | 联系获取全文 |
|
Recommended Citation: |
周敏. 遗传算法的若干改进及应用[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2001-01-01.
|
|
|