Parallel Problem Solving from Nature - PPSN XV - 15th International Conference, Coimbra, Portugal, September 8-12, 2018, Proceedings, Part II
Parallel Problem Solving from Nature - PPSN XV - 15th International Conference, Coimbra, Portugal, September 8-12, 2018, Proceedings, Part II
复制标题
自然并行问题解决 - PPSN XV - 第 15 届国际会议，葡萄牙科英布拉，2018 年 9 月 8-12 日，会议记录，第二部分
DOI：
10.1007/978-3-319-99259-4_2
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Corus D
中科院分区：
文献类型：
--
作者：
Corus D
典型的人工免疫系统（AIS）算子，如具有突变潜力的超突变和老化，可以有效地克服进化算法（EA）难以逃脱的局部最优解。这种行为已被证明为人工示例功能，如跳跃，ClifforTrap构建，特别是要显示的困难，EA可能会遇到优化过程中。然而，没有证据表明类似的影响也可能发生在更现实的问题。在本文中，我们进行了分析，标准的NP-HardPartitionproblem从组合优化和严格表明，超变和老化允许AIS有效地逃离局部最优的标准EA需要指数时间。因此，我们证明，而EA和随机本地搜索可能会陷入4/3近似，AIS找到任意好的近似解决方案的比率（）为任何constantwithin的时间是多项式的问题大小和指数只有在。
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 such asJump,ClifforTrapconstructed especially to show difficulties that EAs may encounter during the optimisation process. However, no evidence is available indicating that similar effects may also occur in more realistic problems. In this paper we perform an analysis for the standard NP-HardPartitionproblem 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 may get trapped on 4/3 approximations, AISs find arbitrarily good approximate solutions of ratio () for any constantwithin a time that is polynomial in the problem size and exponential only in.