两类复杂优化问题的进化算法及应用研究

发布时间：2018-01-13 21:38

本文关键词：两类复杂优化问题的进化算法及应用研究　出处：《西安电子科技大学》2016年博士论文　论文类型：学位论文

【摘要】：全局优化和多目标优化问题是两类复杂的优化问题,它们在数学、工程、管理、军事等诸多领域有着广泛的应用,但是当问题为非线性全局优化和非线性非凸多目标优化问题时,对它们求解非常困难,研究它们高效的求解算法不仅具有重要的理论意义,而且具有广泛的应用价值。进化算法是求解这些复杂优化问题的一种智能优化算法,已经成功地解决了实际中许多复杂优化问题。随着进化算法研究和应用的不断深入,通过多种机制有机协同的进化算法已成为提高算法效率和改善其适应性的有效途径,尤其适合解决高维、非线性、不可微、多局部最优、多目标、动态不确定等复杂优化问题。本文针对高维非线性全局优化和非线性非凸多目标优化问题的高效进化算法进行了深入研究,提出了几种高效的进化算法,并以并行与分布式系统下的可分任务调度问题为实际应用背景,建立了一个任务优化调度模型,并设计了相应的进化算法对模型进行求解。具体工作如下：1、NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithm-Ⅱ)算法是目前求解多目标优化问题的最有效算法之一,其中,聚集距离在NSGA-Ⅱ算法的收敛性和分布均匀性保持上起到重要的作用,但算法没有充分利用微观的个体本身和宏观的种群整体信息。为更合理地估计区域密度,使所求解集更好更均匀地收敛于Pareto最优边界,本文利用均匀聚集区间和基尼系数权重构造了一种均匀聚集距离算子,并基于该算子提出了一种改进的NSGA-Ⅱ算法。最后,通过对10个标准多目标测试问题的实验验证了算法的有效性。2、目标函数加权法是求解多目标优化问题最常用和最简单的方法。但是,对于非凸或者复杂多目标优化问题,这种方法无法求出Pareto前沿非凸部分的最优解,因而通常无法求出在整个Pareto前沿均匀分布的代表解集。为了解决这个问题,本文提出了一种新的基于自适应多适应度函数和空间划分进化算法。通过均匀设计将目标空间划分为相近大小的多个区域,每个区域由目标函数加权作为其适应度函数来搜索该区域内的非支配解。当某个区域包含较少的非支配解时,该区域会被划分为更小的子区域,且会为每个子区域添加一个新的适应度函数。因此,每个区域内的Pareto解将逐步得到更新,最终均匀地分布在整个Pareto前沿。最后,通过求解13个标准测试函数,将所提算法与10个已有算法进行了性能比较。结果表明所提算法的性能要优于已有算法,它不仅可以有效的解决非凸及复杂优化问题,而且可以在整个Pareto前沿找到分布均匀且宽广的解集。3、未成熟收敛以及收敛性能差等是目前进化算法面临的重要缺陷。为了进一步提高进化算法的全局搜索能力和避免算法陷入局部最优解,本文提出了一种基于基因多样性测度的自适应协同进化算法,并且证明了算法的全局收敛性。该算法以基因多样性测度为纽带,实现了算子之间的协同搜索；通过自适应的选择算子和变异算子维持了子种群的多样性,降低算法陷入局部最优解的可能性；通过自适应替换算子实现了各子种群信息之间的动态协同交换,提高了子种群交互信息价值潜力和算法的搜索能力。最后,通过7个函数优化实验验证了算法的有效性。4、针对并行与分布式系统下的可分任务调度这一实际应用问题,考虑到处理机的异构性,即处理机具有任意大小的通信速率、计算速率、计算启动开销和通信启动开销,本文以任务的最短完成时间为目标建立了一个新的优化模型。该模型可以解决以下三个问题：确定最优的参与计算的处理机数目、最优的处理机调度顺序,以及最优的任务分配方案。为了有效的求解该模型,本文设计了一种新的混合遗传算法,并证明了该算法以概率1收敛到全局最优解。为了加快算法的收敛,在算法中引入了局部搜索策略。最后,通过仿真实验验证了模型和算法的有效性。
[Abstract]:Global optimization and multi-objective optimization problems are two kinds of complex optimization problems, in mathematics, engineering, management, military and other fields has been widely used, but when the problem is a multi-objective optimization problem of nonlinear and non convex global optimization and nonlinear, it is difficult to solve them, study their efficient algorithm not only has the important theoretical significance, but also has wide application value. The evolutionary algorithm is an intelligent optimization algorithm for solving the complex optimization problems, has succeeded in solving many complex optimization problems in practice. With the research and application of the algorithm deeply, through various mechanisms of organic co evolutionary algorithm has become an effective way to improve the algorithm to improve the efficiency and adaptability, especially suitable for solving high dimensional, nonlinear, non differentiable, locally optimal, multi-objective, uncertain dynamic and complex optimization problems. This paper studies efficient evolutionary algorithm for non convex multiobjective optimization problem of high-dimensional nonlinear global optimization and nonlinear characteristics, puts forward several efficient evolutionary algorithms, and practical applications in parallel and distributed systems can be divided into task scheduling, a task scheduling model, and design the evolutionary algorithm corresponding to solve the model. The details are as follows: 1, NSGA- II (Non-dominated Sorting Genetic Algorithm- II) algorithm is one of the most effective algorithm to solve multi-objective optimization problem in which the crowding distance plays an important role in the convergence and distribution of NSGA- II algorithm to maintain homogeneity, but the algorithm does not make full use of the micro individual and macro population overall information. For the better estimation of regional density, the better solution set more uniformly converges to the optimal boundary Pareto, Uniform aggregation interval and Gene coefficient weight to construct a uniform distance based aggregation operator, and the operator is proposed based on an improved NSGA- algorithm. Finally, based on the multi-objective test problems of 10 standard experiments verify the effectiveness of.2 algorithm, the objective function is the weighted method for multi-objective optimization problems the most common and simple method. However, for non convex or complex multi-objective optimization problem, this method can find the optimal solution of the nonconvex Pareto front, and usually cannot find out evenly throughout the Pareto front generation table set. In order to solve this problem, this paper presents a new adaptive multi adaptation function and space division evolutionary algorithm based on uniform design. Through the objective space is divided into multiple regions similar to the size of each region by weighted objective function as the fitness function Searching the non dominated solutions in the region. When the non dominated solution of a region contains less, the area will be divided into smaller sub regions, and will add a new fitness function for each sub region. Therefore, each region within the Pareto solution will gradually be updated, eventually uniformly distributed throughout the Pareto frontier. Finally, by solving 13 standard test functions, the proposed algorithm is compared with 10 existing algorithms are compared. The results show that the performance of the proposed algorithm is superior to the existing algorithms, it can not only convex and non effective to solve complex optimization problems, but also can find the solution and uniform distribution set.3 broad in the Pareto frontier, premature convergence and convergence performance of the poor is an important defect of current evolutionary algorithm face. In order to further improve the global search ability of evolutionary algorithm and avoid local optima, this paper. A co evolutionary algorithm based on adaptive measurement of gene diversity, and prove the global convergence of the algorithm. The algorithm to measure the genetic diversity as a link, to achieve synergies between the search operator; the selection operator and adaptive mutation operator to maintain the diversity of sub populations, reduce the possibility of getting into local optimal algorithm the solution; the adaptive operator realizes the dynamic substitution between sub population information collaborative exchange, improve the sub population interaction information value potential and search ability of the algorithm. Finally, through the 7 function optimization experiments verify the effectiveness of the.4 algorithm, aiming at the practical problem of scheduling parallel and distributed system under the sub tasks, taking into account the heterogeneity of processors, computing speed of communication rate, the processor has any size, computational overhead and communication overhead start start, taking To establish a new optimization model of task completion time shortest as the goal. The model can solve the following three problems: to determine the optimal number of processors involved in the computation of the optimal sequence, processor scheduling, and the optimal task allocation scheme. In order to solve the proposed model, this paper designed a new hybrid the genetic algorithm, and proves that the algorithm with probability 1 converges to the global optimal solution. In order to speed up the convergence of the algorithm, the local search strategy is introduced in the algorithm. Finally, through the simulation experiments verify the effectiveness of the model and algorithm.

【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP18

【相似文献】