Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
复制标题
DOI：
10.1016/j.artint.2019.03.001
复制
发表时间：
2019-09-01
影响因子：
14.4
通讯作者：
Yazdani, Donya
中科院分区：
文献类型：
--
作者：
Corus, Dogan;Oliveto, Pietro S.;Yazdani, Donya
典型的人工免疫系统（AIS）算子，如具有突变潜力的超突变和老化，可以有效地克服进化算法（EA）难以逃脱的局部最优解。这种行为已在人工示例函数中得到证明，该函数是专门为显示EA在优化过程中可能遇到的困难而构建的。然而，没有证据表明，这两个运营商有类似的行为，也在更现实的问题。在本文中，我们进行了分析，从组合优化的标准NP-hard PARTITION问题，并严格表明，超变和老化允许AIS有效地逃离局部最优，其中标准EA需要指数时间。因此，我们证明了，虽然EA和随机局部搜索（RLS）可能会陷入4/3近似，AIS发现任意好的近似解决方案的比率（1+）内n（<$（-（2/<$）-1））（1-<$）（-2）e（3）2（2/<$）+2n（3）2（2/<$）2（n3）2n 3函数评估的期望。这个期望值在问题规模上是多项式的，而在1/1范围内是指数的。据我们所知，这是第一次证明任何AIS的性能保证为一个经典的组合优化问题。Crown版权所有（C）2019由Elsevier B. V.发布。保留所有权利。
Typical artificial immune system (AIS) operators such as hypermutations with mutation potential and ageing allow to efficiently overcome local optima from which evolutionary algorithms (EAs) struggle to escape. Such behaviour has been shown for artificial example functions constructed especially to show difficulties that EAs may encounter during the optimisation process. However, no evidence is available indicating that these two operators have similar behaviour also in more realistic problems. In this paper we perform an analysis for the standard NP-hard PARTITION problem from combinatorial optimisation and rigorously show that hypermutations and ageing allow AISs to efficiently escape from local optima where standard EAs require exponential time. As a result we prove that while EAs and random local search (RLS) may get trapped on 4/3 approximations, AISs find arbitrarily good approximate solutions of ratio (1+epsilon) within n(epsilon(-(2/epsilon)-1)) (1-epsilon)(-2)e(3)2(2/epsilon)+2n(3)2(2/epsilon)2(n3) 2n3 function evaluations in expectation. This expectation is polynomial in the problem size and exponential only in 1/epsilon. To the best of our knowledge this is the first time performance guarantees of any AIS are proven for a classical combinatorial optimisation problem. Crown Copyright (C) 2019 Published by Elsevier B.V. All rights reserved.