论文标题
间隔方法和进化算法的杂交解决困难优化问题
Hybridization of interval methods and evolutionary algorithms for solving difficult optimization problems
论文作者
论文摘要
可靠的全球优化致力于在存在四舍五入错误的情况下找到全球最小值。实现全局优化的数值证明的唯一方法是间隔分支和结合方法，这些方法交织了搜索空间的分支和无法包含最佳解决方案的子域的修剪。这是最重要的：i）计算目标函数的尖锐外壳以及给定子域的约束； ii）找到全局最小值的良好近似值（上限）。 最先进的求解器通常是整合方法，也就是说，它们嵌入了局部优化算法，以计算每个子空间上全局最小值的良好上限。在本文档中，我们提出了一个合作框架，其中间隔方法与进化算法合作。后者是随机算法，其中候选解决方案在搜索空间中迭代发展以达到令人满意的溶液。进化算法赋予了运营商，这些操作员有助于个人逃离当地的最小值，特别适合于传统方法难以融合的困难问题。 在我们的合作求解器charibde中，进化算法和基于间隔的算法通过消息传递以并联和交换界限，解决方案和搜索空间运行。一种新颖的策略阻止了过早融合到局部最小值。 Charibde与最先进的求解器（Globsol，IBBA，IBEX）在困难问题的基准上的比较表明，Charibde的收敛速度更快。为五个多模式问题提供了新的最佳结果，文献中很少有解决方案。最后，我们为开放的Lennard-Jones群集问题提供了第一个数值的最佳证明，并提供了五个原子。
Reliable global optimization is dedicated to finding a global minimum in the presence of rounding errors. The only approaches for achieving a numerical proof of global optimality are interval branch and bound methods that interleave branching of the search-space and pruning of the subdomains that cannot contain an optimal solution. It is of the utmost importance: i) to compute sharp enclosures of the objective function and the constraints on a given subdomain; ii) to find a good approximation (an upper bound) of the global minimum. State-of-the-art solvers are generally integrative methods, that is they embed local optimization algorithms to compute a good upper bound of the global minimum over each subspace. In this document, we propose a cooperative framework in which interval methods cooperate with evolutionary algorithms. The latter are stochastic algorithms in which a population of candidate solutions iteratively evolves in the search-space to reach satisfactory solutions. Evolutionary algorithms, endowed with operators that help individuals escape from local minima, are particularly suited for difficult problems on which traditional methods struggle to converge. Within our cooperative solver Charibde, the evolutionary algorithm and the interval-based algorithm run in parallel and exchange bounds, solutions and search-space via message passing. A novel strategy prevents premature convergence toward local minima. A comparison of Charibde with state-of-the-art solvers (GlobSol, IBBA, Ibex) on a benchmark of difficult problems shows that Charibde converges faster by an order of magnitude. New optimality results are provided for five multimodal problems, for which few solutions were available in the literature. Finally, we provide the first numerical proof of optimality for the open Lennard-Jones cluster problem with five atoms.
