基于空间搜索的遗传算法研究

发布时间：2019-04-24 12:16

【摘要】：遗传算法是最早的进化算法之一,它具有良好的稳定性和全局寻优能力,广泛的应用于实际问题中。相比于现今粒子群,差分等进化算法,它的收敛速度相对很慢,在局部寻优上存在不足。但是,众多学者长期致力于遗传算法的理论基础研究,构建不同的遗传算法模型,完善的分析其收敛性和有效性,提供了良好的基础。我们将遗传算法结合各种不同机制或者提出新的改进策略,增加算法的应用领域,提高算法效率。本文基于空间搜索的方式,通过了解种群在变量空间的分布状态,提出了改进的策略对遗传算法进行相关的研究分析。论文的主要工作如下:1)研究遗传算法的理论基础,仔细分析其收敛过程。遗传算法是一种基于启发式搜索的并行性算法,它具有良好的寻优能力和简单的流程。从模式定理中,我们可以了解到,对于遗传算法中的编码,通常难以保留较长的模式,它们有很大的几率被破坏,交叉与变异操作就是让个体的编码可以随机分布在变量空间。在由适应度值引导的过程中,只有趋向相同的编码才可以保留相对稳定的编码个体,因此才容易让遗传算法陷入早熟。本文主要是提出一种可以产生新的编码个体的方式,保持种群的多样性。2)在单目标遗传算法中,提出结合自适应算法的空间划分策略。为了避免自适应遗传算法在后期陷入局部较优,提高搜索的效率,文中提出一种通过种群中个体的变量空间分布来划分区间的方式,来重新分配部分个体,从而加速收敛过程的方法。在遗传算法迭代过程中,对种群个体的分布统计分析,查看种群分布的区间状态,观测收敛的过程。改进的自适应遗传算法了解在整个变量空间内种群个体的分布状态,在重新分配部分种群时,增加个体的多样性从而加速收敛的过程。通过实验可以发现,改进后的自适应遗传算法在种群的多样性上具有差异性,同时可以快速的收敛到全局最优解。3)在多目标遗传算法中,提出构建空间决策树。在高维度空间中,解集的偏好空间难以取舍,记录种群个体的所在位置,将个体在进化中保留的相对稳定的部分位值构造成树。通过生成的空间决策树引导种群的搜索方向,可以有效的保证个体在寻优过程中保持一定的距离具有多样性,又可以快速的向全局进行搜索。通过实验可以发现,增加了空间决策树的NSGA2算法对于目标维数较高的高维多目标优化问题能够取得较好的效果。
[Abstract]:Genetic algorithm is one of the earliest evolutionary algorithms, it has good stability and global optimization ability, it is widely used in practical problems. Compared with the present evolutionary algorithms such as particle swarm optimization and differential algorithms, its convergence rate is relatively slow, and there are some shortcomings in local optimization. However, many scholars have been devoted to the theoretical basis of genetic algorithm for a long time, construct different genetic algorithm models, perfect analysis of its convergence and effectiveness, provide a good basis. We combine genetic algorithms with different mechanisms or propose new improvement strategies to increase the application of the algorithm and improve the efficiency of the algorithm. In this paper, based on the spatial search method and through understanding the distribution state of population in variable space, an improved strategy is proposed to study and analyze the genetic algorithm. The main work of this paper is as follows: 1) the theoretical basis of genetic algorithm is studied and its convergence process is analyzed carefully. Genetic algorithm is a parallel algorithm based on heuristic search. It has good searching ability and simple flow. From the pattern theorem, we can see that it is difficult to retain long patterns for coding in genetic algorithms, and they have a great probability of being destroyed. Crossover and mutation operations are to make the coding of individuals distribute randomly in variable space. In the process of being guided by adaptation values, only codes that tend to be the same can retain relatively stable encoding individuals, so it is easy for genetic algorithms to fall into precocity. In this paper, we propose a new encoding method to keep the diversity of population. 2) in single-objective genetic algorithm, a spatial partition strategy combining with adaptive algorithm is proposed. In order to avoid the self-adaptive genetic algorithm falling into local optimization in the later stage and improve the efficiency of searching, this paper proposes a method of dividing the interval through the variable space distribution of individuals in the population, so as to redistribute some individuals. The method of accelerating the convergence process. In the iterative process of genetic algorithm, the statistical analysis of the distribution of individual population is carried out, the interval state of population distribution is observed, and the process of convergence is observed. The improved adaptive genetic algorithm can find out the distribution state of population individuals in the whole variable space, and increase the diversity of individuals to accelerate the process of convergence when redistributing part of the population. The experiment shows that the improved adaptive genetic algorithm has difference in the diversity of population and can converge to the global optimal solution rapidly. 3) in multi-objective genetic algorithm, the spatial decision tree is proposed. In the high dimensional space, the preference space of the solution set is difficult to choose. The position of the individual in the population is recorded, and the relatively stable partial bits retained by the individual in evolution are constructed into the tree. The search direction of the population can be guided by the generated spatial decision tree, which can effectively ensure the diversity of individuals in the process of optimization, and it can also search quickly to the whole world. The experiments show that the NSGA2 algorithm with the addition of spatial decision tree can achieve better results for the high dimensional multi-objective optimization problem with higher target dimension.
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18

【参考文献】