面向单目标黑箱优化问题的分解进化算法

This proposal is on single objective black box optimization. In many real-world optimization problems, there is no analytic expression of their objective functions. Their solution evaluation is conducted via computer simulation. Each computer simulation could be time-consuming. These optimization problems often have multiple locally optimal solutions. To obtain a good solution, it inevitably requires a large number of function evaluations. Given the emergence of massive computing power provided by a number of parallel and distributed computer architectures in recent years, a very natural and promising strategy is to divide a problem into a number of tasks and solve them in a parallel and distributed computing environment. However, it is very challenging to decompose a black box optimization problem properly. If we divide the search regions into several smaller subregions and search these subregions independently, it will waste a lot of computational resources. This project will develop two novel and generic decomposition algorithmic frameworks for black box optimization problems. These two frameworks will allow easy use of previously well developed and understood single objective and multiobjective optimization techniques. One framework is to decompose the original single objective optimization problem into a number of biobjective optimization problems, in which the optimal solution to the original problem is Pareto optimal to each subproblem and different subproblems have different Pareto optimal sets. In the other framework, a number of helper single objective subproblems are introduced and their relation with the original problem is exploited during the search. In both frameworks, each search procedure is responsible for a different subproblem. We will investigate how each procedure can make use of information from other procedures to adjust its behavior to achieve efficient search. The proposed algorithms will be applied on tunnel design problems.

本项目研究黑箱优化问题，这些问题没有解析表达式，目标函数值计算只能通过计算机仿真或物理试验得出，函数值计算通常耗资费时。这类问题往往有多个局部最优解，为了获得一个好的近似解，不可避免地需要大量多次评估目标函数值，串行式的计算模式常无法在可接受的时间内给出满意解。本项目研究如何利用分而治之的策略将问题分成多个藕合度低的子问题然后在并行或分布式计算环境求解。.本项目的主要研究课题是如何分解和如何用协同合作的方式求解多个子问题。我们将构造和研究两类求解黑箱优化问题的分解算法框架。在这两类框架下，双目标和单目标算法可自然地转变成并行或分布式黑箱优化算法。在两个框架中，每个子问题都用一个过程求解。我们将研究每个过程如何相互使用其它过程的信息来调节自身行为。所发展算法将用来求解风洞设计问题。

本项目研究黑箱优化问题，这些问题没有解析表达式，目标函数值计算只能通过计算机仿真或物理试验得出，函数值计算通常耗资费时。这类问题往往有多个局部最优解，为了获得一个好的近似解，不可避免地需要大量多次评估目标函数值，串行式的计算模式常无法在可接受的时间内给出满意解。本项目研究如何利用分而治之的策略将问题分成多个耦合度低的子问题然后在并行或分布式计算环境求解。本项目主要研究了如何分解和如何用协同合作的方式求解多个子问题。构造和研究了两类求解黑箱优化问题的分解算法框架。在这两类框架下，双目标和单目标算法可自然地转变成并行或分布式黑箱优化算法。取得的主要研究成果包括：（1）证明了用多目标优化中的非支配排序方法可以引导局部搜索跳出单目标的局部最优，从而找到更好的解。将单目标旅行商问题分解为两个目标的旅行商问题，同时证明了用多目标优化中的非支配的排序的方法来引导局部搜索跳出单目标的局部最优。（2）提出了一种策略来检测搜索是否陷入两个停滞状态，然后从中跳出。所提出的检测-逃逸策略利用可行比和总体约束违反的变化率来检测停滞状态，并通过调整约束违反的权重来指导搜索跳出停滞状态。（3）提出了一种利用多惩罚和多局部代理模型（MPMLS）的进化算法来实现昂贵的黑箱约束优化。在每一代中，MPMLS定义和优化了多个子问题。每个子问题使用不同的惩罚系数惩罚原问题中的约束，并拥有各自的搜索子区域。提出的算法在性能上优于其他一些目前最先进的进化算法。（4）提出竞争性多任务优化的基本概念和测试问题，并提出了一种具有在线资源分配策略和自适应信息传递机制的多任务进化算法对其求解。（5）研究了当梯度可用时如何进行昂贵的多目标优化。提出了一种名为MOEA/D - GEK的方法，它结合了MOEA/D和梯度增强克里金方法，运用梯度来建立克里金模型。 通过对跨声速翼型气动优化设计的试验实例和工程问题的实验研究表明，所提方法具有较高的效率和有效性。