基于图论分析差分演化算法的并行性特征
发布时间：2019-01-20 12:18
【摘要】：近年来智能计算在人类生活中各个方面都展示了其不容忽视的作用,智能计算辅助人类进行高效的生产,为工业生产、科技发展及人类社会进步作出积极的贡献.为更好的解决社会生产生活所面临的最优化问题,模仿自然界生物进化过程的众多随机启发式仿生算法随之应运而生,这些仿生算法在解决复杂问题方面有着显著的成效.为使仿生算法发挥更好的性能,从理论分析的角度抽象出仿生算法内在的规律是迫切需要进行研究的方向.差分演化算法是目前应用较为广泛的随机启发式算法,因其所具有效果显著、空间复杂性低等特点使其受到了广泛的关注.本文基于并行性特征这一原理分析差分演化算法在迭代过程中的特点,利用图论的方式展现出算法所具有的内在特征,利用这一理论方法分析出差分演化算法所具有的稳定性及强健性的原因,从算法的进化过程中分析出算法所具有并行特征的强弱对算法的影响.本文从理论分析差分演化算法的并行性特征出发,分析算法在进化过程中的特点,关注算法并行特征对算法效果的影响.本文的研究成果主要有以下几方面:(1)从并行性的思想角度出发,仿生算法展现出越来越杰出的搜索高效性和信息共享性的特征,算法中种群进化行为越来越趋于群体性和并行性,利用种群迭代过程中所包含的并行性特征行为作为分析算法性能的出发点.(2)本文将基于图论的研究方法分析差分演化算法的并行特征,图论作为数学科学中的一个重要的分支,将有效的展现种群个体进化过程中的个体间的关系,更好的辅助算法理论进行分析研究.(3)从随机启发式算法进化过程的研究来看,仿生算法的理论分析至今都是研究的薄弱环节,利用图论论证生成路径的数量对于算法性能的影响,在种群信息共享的基础上,分析个体所产生新搜索方向,成为分析算法内在特征的量化指标.本文的研究成果不仅丰富了随机启发式算法的理论研究成果,而且得到算法的并行性程度与算法性能之间存在相关性的结论.
[Abstract]:In recent years, intelligent computing has played an important role in all aspects of human life. Intelligent computing can assist human to carry out efficient production and make positive contributions to industrial production, scientific and technological development and the progress of human society. In order to solve the optimization problem of social production and life better, many random heuristic bionic algorithms, which mimic the evolution process of natural organisms, emerge as the times require. These bionic algorithms have remarkable results in solving complex problems. In order to improve the performance of bionic algorithm, it is urgent to abstract the inherent law of bionic algorithm from the angle of theoretical analysis. Differential evolution algorithm (DEA) is a widely used stochastic heuristic algorithm, which has attracted wide attention because of its remarkable effect and low spatial complexity. Based on the principle of parallelism, this paper analyzes the characteristics of the differential evolution algorithm in the iterative process, and shows the inherent characteristics of the algorithm by means of graph theory. The reason of stability and robustness of the differential evolution algorithm is analyzed by using this method. The influence of the strength of the parallel characteristic of the algorithm on the algorithm is analyzed from the evolutionary process of the algorithm. Based on the theoretical analysis of the parallelism of the differential evolution algorithm, this paper analyzes the characteristics of the algorithm in the evolution process, and pays attention to the influence of the parallel feature of the algorithm on the effectiveness of the algorithm. The main research results of this paper are as follows: (1) from the perspective of parallelism, bionic algorithms show more and more outstanding features of search efficiency and information sharing. The evolutionary behavior of population in the algorithm tends to be group and parallelism more and more. The parallel characteristic behavior included in the population iteration process is used as the starting point to analyze the performance of the algorithm. (2) in this paper, the parallel features of the differential evolution algorithm are analyzed based on graph theory. As an important branch of mathematical science, graph theory will effectively show the relationship between individuals in the evolution of individual population. (3) from the research of evolutionary process of stochastic heuristic algorithm, the theoretical analysis of bionic algorithm is still the weak link. The effect of the number of generated paths on the performance of the algorithm is demonstrated by using graph theory. On the basis of population information sharing, the new search direction produced by individuals is analyzed, which becomes a quantitative index for analyzing the inherent characteristics of the algorithm. The research results of this paper not only enrich the theoretical research results of stochastic heuristic algorithm, but also obtain the conclusion that the degree of parallelism of the algorithm is related to the performance of the algorithm.
【学位授予单位】：广东工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;O157.5
本文编号：2412035
[Abstract]:In recent years, intelligent computing has played an important role in all aspects of human life. Intelligent computing can assist human to carry out efficient production and make positive contributions to industrial production, scientific and technological development and the progress of human society. In order to solve the optimization problem of social production and life better, many random heuristic bionic algorithms, which mimic the evolution process of natural organisms, emerge as the times require. These bionic algorithms have remarkable results in solving complex problems. In order to improve the performance of bionic algorithm, it is urgent to abstract the inherent law of bionic algorithm from the angle of theoretical analysis. Differential evolution algorithm (DEA) is a widely used stochastic heuristic algorithm, which has attracted wide attention because of its remarkable effect and low spatial complexity. Based on the principle of parallelism, this paper analyzes the characteristics of the differential evolution algorithm in the iterative process, and shows the inherent characteristics of the algorithm by means of graph theory. The reason of stability and robustness of the differential evolution algorithm is analyzed by using this method. The influence of the strength of the parallel characteristic of the algorithm on the algorithm is analyzed from the evolutionary process of the algorithm. Based on the theoretical analysis of the parallelism of the differential evolution algorithm, this paper analyzes the characteristics of the algorithm in the evolution process, and pays attention to the influence of the parallel feature of the algorithm on the effectiveness of the algorithm. The main research results of this paper are as follows: (1) from the perspective of parallelism, bionic algorithms show more and more outstanding features of search efficiency and information sharing. The evolutionary behavior of population in the algorithm tends to be group and parallelism more and more. The parallel characteristic behavior included in the population iteration process is used as the starting point to analyze the performance of the algorithm. (2) in this paper, the parallel features of the differential evolution algorithm are analyzed based on graph theory. As an important branch of mathematical science, graph theory will effectively show the relationship between individuals in the evolution of individual population. (3) from the research of evolutionary process of stochastic heuristic algorithm, the theoretical analysis of bionic algorithm is still the weak link. The effect of the number of generated paths on the performance of the algorithm is demonstrated by using graph theory. On the basis of population information sharing, the new search direction produced by individuals is analyzed, which becomes a quantitative index for analyzing the inherent characteristics of the algorithm. The research results of this paper not only enrich the theoretical research results of stochastic heuristic algorithm, but also obtain the conclusion that the degree of parallelism of the algorithm is related to the performance of the algorithm.
【学位授予单位】：广东工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;O157.5
【参考文献】
相关期刊论文 前6条
1 黄翰;徐威迪;张宇山;林智勇;郝志峰;;基于平均增益模型的连续型(1+1)进化算法计算时间复杂性分析[J];中国科学:信息科学;2014年06期
2 黄翰;林智勇;郝志峰;张宇山;李学强;;基于关系模型的进化算法收敛性分析与对比[J];计算机学报;2011年05期
3 张金标;;并行设计混合迭代过程规划的遗传算法[J];现代制造工程;2008年07期
4 黄翰;郝志峰;吴春国;秦勇;;蚁群算法的收敛速度分析[J];计算机学报;2007年08期
5 郭振宇;程博;叶敏;康龙云;曹秉刚;;一种并行混沌差异演化算法[J];西安交通大学学报;2007年03期
6 徐宗本,聂赞坎,张文修;遗传算法的几乎必然强收敛性——鞅方法[J];计算机学报;2002年08期
，本文编号：2412035
本文链接：https://www.wllwen.com/kejilunwen/yysx/2412035.html
