【作者】 由雪梅；

【导师】 杨连中；

【作者基本信息】 山东大学 ， 计算机软件与理论， 2011， 博士

【摘要】 在现实世界中,很多优化问题都是要寻找一种最佳的解决方案,即在满足一定的约束条件下,寻找一组参数值,使得系统某些性能指标达到最大或最小。根据问题的属性,优化问题可以分为不同的类型：单峰问题和多峰问题；无约束优化问题和约束优化问题；连续优化问题和离散优化问题；单目标优化问题和多目标优化问题；低维优化问题和高维优化问题。这些问题的求解难度也大不相同,一般来讲,局部最优解越少,约束条件越少,目标函数越少,维数越低时,问题容易求解。当局部最优解较多时,算法容易陷入局部最优,很难找到较好的解。当约束条件较多时,处理约束时将变得很困难,很难找到可行解。当目标函数变多时,很难找到满足多个目标的Pareto前沿。问题维数的增加,将使得解的搜索空间呈指数规模增大,算法的收敛速度和搜索能力将受到极大的挑战。差分演化算法是…类基于群体的全局搜索算法,对于这类复杂优化问题的求解,它比传统的数学方法有更大的优势。本文对几类复杂优化问题,包括经典的优化问题、多峰问题、约束优化问题以及高维问题进行了系统深入的研究,根据问题的特征,设计和开发了不同的差分演化算法,并将设计的算法应用于上述问题的基准测试问题和一些实际应用问题,以验证算法的有效性和实用性。论文的主要研究成果可以概括为以下儿个方面：1.针对经典无约束优化问题的求解,我们提出了一种改进的DE算法。该方法使用了最近提出的DE/current-to-pbest变异策略的优点,为了避免手工调整控制参数,我们设计了一种自适应参数调节策略。通过对20个经典的基准测试问题进行实验仿真,我们的算法在其中18个问题上都能找到满意的解。在与最近提出的几种知名的DE算法相比,我们的算法在大部分问题上都能找到更精确的解。2.针对复杂多峰优化问题的求解,我们设计了一种混合DE算法。该方法融合了DE/current-to-best/2策略和反向学习机制。前者能加快算法的收敛速度,后者通过同时评估当前解及其反向解,能提高找到较好解的概率。在11个复杂多峰问题上的仿真实验表明,我们的算法优于标准DE算法和其它6种改进的PSO算法。为了更好的比较各种算法的性能,我们做了t检验和Friedman假设检验,结果显示,我们的算法是8种比较算法中最好的。3.针对约束优化问题的求解,我们提出了一种基于多父体杂交的DE算法。该方法在基于中心个体和随机选择的3个不同的个体所形成的子空间内杂交产生子代个体,这种杂交模式能让产生的子代更靠近可行域空间。针对最优解可能出现在可行域的边界的情况,我们应用了一种边界搜索策略来处理边界解的问题。在约束处理方面,我们使用了一种可行解优先法(违反约束越小越好)。为了验证算法的性能,我们选择了13个著名的约束优化基准测试问题进行实验仿真。数值仿真和实验比较表明,我们的算法能有效的处理约束,并能找到较好的可行解。另外,我们将该算法应用于解决工程领域的4个约束优化设计问题,包括焊接梁的设计优化、压力容器的设计优化、弹簧的设计优化以及减速器的设计优化。仿真结果表明了我们算法的有效性。4.针对高维优化问题(维数达到1000)的求解,我们提出了一种改进的DE算法,该方法通过修改DE变异策略,旨在学习全局个体和局部领域最好个体的搜索信息,最终达到平衡DE算法的全局和局部搜索能力。为了检验算法的性能,我们测试了6个常用的基准高维测试问题(维数为100、500和1000)。仿真结果表明,我们的算法在大部分测试问题上都能找到合理的解。为了比较多个算法在测试问题集上的性能,我们应用了Friedman假设检验来计算6种比较算法的平均排名。结果表明,我们的算法是6种比较的算法中最好的。为了分析算法的计算运行时间,我使用了幂函数回归模型来拟合实验中实际所得的计算时间。结果显示,我们算法的计算时间复杂度低于O(D2)。因而,将该方法应用于更高维问题的求解将是可行的。更多还原

【Abstract】 In real-world, many optimization problems aim to find the best solutions. When satisfying certain constraints, searching a set of parameters maximize or minimize some targets of system performance. According to the properties of problems, optimization problems can be divided into different types:unimodal and multimodal problems, unconstrained and constrained optimization problems, continuous and discrete optimization problems, single object and multi-object optimization problems, low and high dimensional optimization problems. The difficulties of those problems are different. Generally, problems with less local minima, smaller number of constraints and objects, and lower dimensions are easy to solve. When problems have more local optima, algorithms are easily trapped and hard to find better solutions. When problems have more constrains, algorithms are difficult to deal with constraints and search feasible solutions. When problems have many objects, algorithms are hard to satisfy the Pareto front of objects. When increasing the dimensions of problems, the convergence speeds of algorithms are faced with a big challenge. Differential Evolution (DE) is a class of population-based global search algorithms. Compared to traditional pure mathematical methods, DE is superior to solve the above complex problems.This dissertation focuses on DE for solving several complex optimization problems, including classical optimization problems, multimodal optimization problems, constrained optimization problems and high dimensional optimization problems. According to the features of problems, we design different DE variants to solve the abovementioned problems and some real-world applications. The main contributions of this dissertation can be summarized as follows.1. For solving classical optimization problems, we present an improved DE algorithm, with employs a recently proposed DE/current-to-pbest mutation strategy. To avoid manually adjusting control parameters, we design a self-adaptive parameter tuning mechanism. Simulation studies on 20 classical benchmark optimization problems demonstrate that our approach can find promising solutions on 18 problems. When compared with some famous DE variants, our algorithm achieves better solutions on the majority of test problems.2. For solving complex multimodal optimization problems, we design a hybrid DE algorithm, which combines DE/current-to-best/2 strategy and opposition-based learning (OBL) mechanism. The former can accelerate the convergence speed, and the latter can improve the probability of finding better solutions by simultaneously evaluating current solutions and opposite solutions. Experimental studies on 11 complex multimodal problems show that our algorithm outperforms standard DE and other six improved particle swarm optimization algorithms. In order to compare multiple algorithms on the whole test suite, we conduct t-test and Friedman test. The results show that our algorithm is the best one among the eight compared algorithms.3. For solving constrained optimization problems, we propose a new DE algorithm based on multi-parent crossover, which generates offspring based on the center individual and three randomly selected individuals. The offspring created by this crossover scheme are closer to the feasible region. To deal with the solutions in the boundaries of feasible region, we apply a boundary search strategy. To handle constraints, we employ a feasible solution preferred rule (an individual with less constraint violations is better). To verify the performance of our approach, we test it on 13 well-known constrained benchmark optimization problems. Simulation results and comparisons demonstrate that our algorithm can effectively deal with constraints and achieves better feasible solutions. Additionally, we apply the algorithm to solve four real-world applications, including welded beam design optimization problem, pressure vessel design optimization problem, tension/compression spring design optimization problem and speed reducer design optimization problem. Simulation results demonstrate the effectiveness of our algorithm.4. For solving high dimensional (D=1000) optimization problems, we propose an improved DE variants, which modifies the DE mutation scheme to learn the information of global and local best individuals, and aims to balance the global and local search abilities of DE. To verify the performance of our algorithm, we test it on six common high dimensional benchmark optimization problems (D=100,500 and 1000). Simulation results show that our algorithm can find reasonable solutions on the majority of test problems. To compare multiple algorithms on the test suite, we apply Friedman test to calculate the average rankings of the involved six algorithms. The results show that our algorithm is best one among all compared algorithms. To analyze the computational running time, we use power regression model to fit the real running time. Simulation results show that the time complexity of our algorithm is below O(D2). Therefore, it is applicable to use the algorithm to solve higher dimensional problems.更多还原