基于代理模型的实值演化算法研究

发布时间：2018-04-20 16:16

本文选题：演化算法 + 代理模型　；参考：《中国科学技术大学》2017年博士论文

【摘要】：实值优化在现实生活中存在着广泛的应用背景。演化算法(Evolutionary Al-gorithm)作为一类基于种群的随机优化算法,在实值优化领域受到了广泛的关注。不过,演化算法在实际应用中仍然面临着挑战。由于演化算法使用基于种群的搜索和以个体适应度值为基础的优胜劣汰选择机制,演化算法往往需要大量的适应度评估才能获得满意的解。然而,在实际应用中,广泛存在着计算代价高的问题(Computationally Expensive Problems)。对于这类问题,一次适应度评估的代价是非常高的,这限制了演化算法在相关领域里的应用。针对演化算法存在的这点不足,本论文的主要目的是研究设计适用于计算代价高的实值优化问题的演化算法。基于这个目的,本文从代理模型(Surrogate Model)着手,通过构造计算代价不高的代理模型并引入到演化算法中来代替真实的适应度评估,从而使演化算法更好地求解计算代价高的实值优化问题。本文的主要研究工作与创新之处包括以下几个方面:1.基于分类模型的差分演化(Differential Evolution)算法在演化算法中引入代理模型牵涉到学习和优化的互相作用。一般来讲,代理模型的选择和使用方式需要结合具体的演化算法来进行设计。本文通过分析差分演化算法的搜索原理,将差分演化算法的选择过程归约为一个分类问题。基于此,本文提出了将分类模型引入到差分演化的选择过程中、以代替真实适应度评估对个体进行比较的基于分类模型的差分演化算法。区别于以往基于代理模型的演化算法中常常用到的回归模型和排序模型,分类模型能更好地匹配差分演化算法的选择机制的本质,因而可以更好地提高差分演化算法在有限的计算时间内求解计算代价高的优化问题的性能。2.基于分类模型和回归模型结合的差分演化算法代理模型有不同的类型。不同类型的代理模型求解的问题不同,因而可以在演化算法中扮演不同的角色。作为对本文提出的基于分类模型的差分演化算法的改进,本文将分类模型和回归模型结合起来融入到差分演化算法中。分类模型可以帮助差分演化算法避免在不好的子代个体上浪费真实的适应度评估;回归模型可以在分类模型预测的好的子代个体上给出替代真实适应度值的近似适应度值,从而进一步减少差分演化算法每代所需要的真实适应度评估的次数。3.基于代理模型的自适应差分演化框架演化算法对操作算子及参数设置敏感。自适应机制在演化算法中扮演着重要的角色,它可以帮助演化算法在演化搜索的过程中自动地调整操作算子和参数值,从而提高演化算法的性能。本文分析了自适应差分演化算法在求解计算代价高的问题时存在的不足,并提出了基于代理模型的方法来对差分演化的操作算子和参数设置进行自适应调整,为差分演化算法提供了一种适用于计算代价高问题的自适应机制。4.基于多模型的模因演算法(Memetic Algorithm)构建代理模型的方式有很多种。同样的构建方式构建出的代理模型在不同问题上的表现不同,因而代理模型的构建方式的选择是影响基于代理模型的演化算法的性能的一个重要因素。一般来讲,代理模型的建模方式应该结合具体的应用问题来进行选择。然而,由于这需要一些事先并不知道的有关具体应用问题的先验知识,所以是不可行的。基于此,本文在模因演算法的框架下提出了具有层次结构的多模型使用机制,实现了一种新颖的模型构建方式的自适应选择机制。本论文分别从演化算法层面和代理模型构建层面开展工作,研究如何设计高效的基于代理模型的演化算法。在演化算法层面,考虑到代理模型能够在演化算法中扮演不同的角色,本文分别提出了基于分类模型的差分演化算法、基于分类模型和回归模型结合的差分演化算法、以及基于代理模型的自适应差分演化框架。在代理模型层面,考虑到同样的构建方式构建出的代理模型在不同问题上的表现不同,本文在模因演算法的框架下提出了一种高效的具有层次结构的代理模型构建方式的自适应选择机制。本文提出的基于分类模型的差分演化算法以及基于分类模型和回归模型结合的差分演化算法,可以供后续的为其它使用成对比较的选择机制的演化算法设计代理模型融入方式的工作参考。本文提出的基于代理模型的自适应差分演化框架可以作为通用的框架和其它同时使用多个搜索策略的差分演化算法结合。本文提出的多模型自适应选择机制能够为后续的基于多个代理模型的优化算法的研究设计提供参考。
[Abstract]:Real value optimization has a wide application background in real life. As a class of population based stochastic optimization algorithms, Evolutionary Al-gorithm has received extensive attention in the field of real value optimization. However, evolutionary algorithms still face a challenge in practical applications. According to the selection mechanism of the fittest based on the individual fitness value, the evolutionary algorithm often requires a large number of fitness evaluation to obtain satisfactory solutions. However, in practical applications, there is a widespread problem of high computational cost (Computationally Expensive Problems). For such problems, the cost of an adaptation assessment is very high, This restricts the application of evolutionary algorithms in the related fields. Aiming at the shortage of evolutionary algorithms, the main purpose of this paper is to study the design of evolutionary algorithms for real value optimization problems with high computational cost. Based on this purpose, this paper starts with the agent model (Surrogate Model) and constructs a proxy model with low computational cost. The main research work and innovation of this paper include the following aspects: 1. the Differential Evolution algorithm based on the classification model introduces the agent to the evolutionary algorithm. The model involves the interaction of learning and optimization. Generally speaking, the choice and use of the agent model needs to be designed with a specific evolutionary algorithm. By analyzing the search principle of the differential evolution algorithm, the selection process of the differential evolution algorithm is reduced to a sub class problem. Based on this, this paper proposes a classification model. In the selection process of the differential evolution, the differential evolution algorithm based on the classification model is replaced by the real fitness evaluation, which is different from the regression model and the sort model commonly used in the evolutionary algorithm based on the proxy model. The classification model can better match the selection mechanism of the differential evolution algorithm. In essence, it can better improve the performance of the differential evolution algorithm to solve the optimization problem with high computation cost in the limited computing time..2. based on the differential evolution algorithm based on the combination of the classification model and the regression model has different types. The different types of agent models are different in solving the problem, so it can be used in the evolutionary algorithm. As an improvement on the differential evolution algorithm based on the classification model proposed in this paper, this paper combines the classification model and the regression model into the differential evolution algorithm. The classification model can help the differential evolution algorithm avoid the real fitness evaluation on the bad offspring; the regression model can be used. The approximate fitness value is given to replace the true fitness value on the good sub generation of the classified model prediction, thus further reducing the number of true fitness evaluation required for each generation of the differential evolution algorithm.3., the adaptive differential evolution framework evolution algorithm based on the agent model is sensitive to the operator and parameter setting. It plays an important role in the evolutionary algorithm. It can help the evolutionary algorithm to automatically adjust the operator and parameter value in the process of evolutionary search, thus improving the performance of the evolutionary algorithm. This paper analyzes the shortcomings of the adaptive differential evolution algorithm in solving the problem of high computing cost, and proposes a proxy model based on the agent model. This method adaptively adjusts the operator and parameter setting of differential evolution, and provides an adaptive mechanism for differential evolution algorithm (.4.), which is suitable for high computational cost problems. There are many ways to build the agent model based on the multiple model based meme algorithm (Memetic Algorithm). The representation of the model is an important factor affecting the performance of the evolutionary algorithm based on the agent model. Generally speaking, the modeling method of the agent model should be selected in combination with the specific application problems. In this paper, a hierarchical multi model use mechanism is proposed under the framework of meme algorithm, and an adaptive selection mechanism for a novel model building mode is realized. In this paper, we propose a differential evolution algorithm based on the classification model, the differential evolution algorithm based on the combination of the classification model and the regression model, and the self - based model based on the evolution algorithm level. Adaptive differential evolution framework. At the level of agent model, considering the different representation of the agent model built in the same way, this paper proposes an efficient self adapted selection mechanism for the construction of an agent model with hierarchical structure under the framework of meme algorithm. This paper is based on the classification model. The differential evolution algorithm and the differential evolution algorithm based on the combination of the classification model and the regression model can be used as a reference for the subsequent design of the agent model integration for the evolutionary algorithms that use the selection mechanism for comparison. This paper proposes an adaptive framework based on the agent model which can be used as a general framework. The multi model adaptive selection mechanism proposed in this paper can provide reference for the subsequent research and design of the optimization algorithm based on multiple agent models.

【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】