基于空間搜索的遺傳算法研究
發(fā)布時間：2019-04-24 12:16
【摘要】：遺傳算法是最早的進化算法之一,它具有良好的穩(wěn)定性和全局尋優(yōu)能力,廣泛的應用于實際問題中。相比于現今粒子群,差分等進化算法,它的收斂速度相對很慢,在局部尋優(yōu)上存在不足。但是,眾多學者長期致力于遺傳算法的理論基礎研究,構建不同的遺傳算法模型,完善的分析其收斂性和有效性,提供了良好的基礎。我們將遺傳算法結合各種不同機制或者提出新的改進策略,增加算法的應用領域,提高算法效率。本文基于空間搜索的方式,通過了解種群在變量空間的分布狀態(tài),提出了改進的策略對遺傳算法進行相關的研究分析。論文的主要工作如下:1)研究遺傳算法的理論基礎,仔細分析其收斂過程。遺傳算法是一種基于啟發(fā)式搜索的并行性算法,它具有良好的尋優(yōu)能力和簡單的流程。從模式定理中,我們可以了解到,對于遺傳算法中的編碼,通常難以保留較長的模式,它們有很大的幾率被破壞,交叉與變異操作就是讓個體的編碼可以隨機分布在變量空間。在由適應度值引導的過程中,只有趨向相同的編碼才可以保留相對穩(wěn)定的編碼個體,因此才容易讓遺傳算法陷入早熟。本文主要是提出一種可以產生新的編碼個體的方式,保持種群的多樣性。2)在單目標遺傳算法中,提出結合自適應算法的空間劃分策略。為了避免自適應遺傳算法在后期陷入局部較優(yōu),提高搜索的效率,文中提出一種通過種群中個體的變量空間分布來劃分區(qū)間的方式,來重新分配部分個體,從而加速收斂過程的方法。在遺傳算法迭代過程中,對種群個體的分布統計分析,查看種群分布的區(qū)間狀態(tài),觀測收斂的過程。改進的自適應遺傳算法了解在整個變量空間內種群個體的分布狀態(tài),在重新分配部分種群時,增加個體的多樣性從而加速收斂的過程。通過實驗可以發(fā)現,改進后的自適應遺傳算法在種群的多樣性上具有差異性,同時可以快速的收斂到全局最優(yōu)解。3)在多目標遺傳算法中,提出構建空間決策樹。在高維度空間中,解集的偏好空間難以取舍,記錄種群個體的所在位置,將個體在進化中保留的相對穩(wěn)定的部分位值構造成樹。通過生成的空間決策樹引導種群的搜索方向,可以有效的保證個體在尋優(yōu)過程中保持一定的距離具有多樣性,又可以快速的向全局進行搜索。通過實驗可以發(fā)現,增加了空間決策樹的NSGA2算法對于目標維數較高的高維多目標優(yōu)化問題能夠取得較好的效果。
[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
本文編號：2464442
[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
【參考文獻】
相關期刊論文 前10條
1 莊仲杰;崔賓閣;;基于分割質量的遙感圖像最優(yōu)尺度分割方法研究[J];計算機與現代化;2015年04期
2 李動;黃心漢;;基于改進遺傳算法的雷達網優(yōu)化布站方法[J];華中科技大學學報(自然科學版);2013年S1期
3 李賢陽;黃嬋;;一種結合改進OTSU法和改進遺傳算法的圖像分割方法[J];實驗室研究與探索;2012年12期
4 王江晴;楊勛;;基于Pareto-ε優(yōu)勝的自適應快速多目標演化算法[J];計算機應用;2010年04期
5 張國強;彭曉明;;自適應遺傳算法的改進與應用[J];艦船電子工程;2010年01期
6 鞏固;趙向軍;郝國生;陳龍高;;優(yōu)化搜索空間劃分的遺傳算法的研究與實現[J];河南大學學報(自然科學版);2009年06期
7 公茂果;焦李成;楊咚咚;馬文萍;;進化多目標優(yōu)化算法研究[J];軟件學報;2009年02期
8 趙振勇;王力;王保華;楊本娟;;遺傳算法改進策略的研究[J];計算機應用;2006年S2期
9 林開顏,吳軍輝,徐立鴻;彩色圖像分割方法綜述[J];中國圖象圖形學報;2005年01期
10 韓思奇,王蕾;圖像分割的閾值法綜述[J];系統工程與電子技術;2002年06期
相關碩士學位論文 前5條
1 喬陽;基于改進遺傳算法的圖像分割方法[D];電子科技大學;2013年
2 崔珊珊;遺傳算法的一些改進及其應用[D];中國科學技術大學;2010年
3 黃菲;基于遺傳算法的圖像分割[D];武漢科技大學;2008年
4 李欣;自適應遺傳算法的改進與研究[D];南京信息工程大學;2008年
5 陳健;基于空間劃分的搜索算法[D];山東大學;2005年
，本文編號：2464442
本文鏈接：http://sikaile.net/kejilunwen/zidonghuakongzhilunwen/2464442.html
