CINVESTAV-IPN, Departamento de Computación, México D.F., México.
Evol Comput. 2010 Spring;18(1):65-96. doi: 10.1162/evco.2010.18.1.18103.
Recently, a convergence proof of stochastic search algorithms toward finite size Pareto set approximations of continuous multi-objective optimization problems has been given. The focus was on obtaining a finite approximation that captures the entire solution set in some suitable sense, which was defined by the concept of epsilon-dominance. Though bounds on the quality of the limit approximation-which are entirely determined by the archiving strategy and the value of epsilon-have been obtained, the strategies do not guarantee to obtain a gap free approximation of the Pareto front. That is, such approximations A can reveal gaps in the sense that points f in the Pareto front can exist such that the distance of f to any image point F(a), a epsilon A, is "large." Since such gap free approximations are desirable in certain applications, and the related archiving strategies can be advantageous when memetic strategies are included in the search process, we are aiming in this work for such methods. We present two novel strategies that accomplish this task in the probabilistic sense and under mild assumptions on the stochastic search algorithm. In addition to the convergence proofs, we give some numerical results to visualize the behavior of the different archiving strategies. Finally, we demonstrate the potential for a possible hybridization of a given stochastic search algorithm with a particular local search strategy-multi-objective continuation methods-by showing that the concept of epsilon-dominance can be integrated into this approach in a suitable way.
最近，已经给出了随机搜索算法在连续多目标优化问题的有限大小 Pareto 集逼近方面的收敛性证明。重点是获得有限逼近，以某种合适的意义捕捉整个解集，这是由ε优势的概念定义的。尽管已经获得了极限逼近的质量的界-这完全由存档策略和ε的值决定-但是这些策略并不能保证获得 Pareto 前沿的无间隙逼近。也就是说，这样的逼近 A 可以揭示差距，即 Pareto 前沿中的点 f 存在这样的情况，即 f 到任何映像点 F(a)的距离，a ∈ A，是“大的”。由于在某些应用中需要这样的无间隙逼近，并且当在搜索过程中包括遗传策略时相关的存档策略是有利的，所以我们在这项工作中旨在寻找这样的方法。我们提出了两种新颖的策略，以在随机搜索算法的温和假设下从概率意义上实现这一目标。除了收敛性证明，我们还给出了一些数值结果来可视化不同存档策略的行为。最后，我们通过展示ε优势的概念可以以合适的方式集成到这种方法中，证明了给定的随机搜索算法与特定的局部搜索策略-多目标连续方法的杂交的可能性。
