On the runtime analysis of the opt-IA artificial immune system
On the runtime analysis of the opt-IA artificial immune system
复制标题
opt-IA人工免疫系统的运行时分析
DOI：
10.1145/3071178.3079194
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Corus D
中科院分区：
文献类型：
--
作者：
Corus D
我们提出了一个时间复杂度分析的Opt-IA人工免疫系统（AIS）。我们首先强调其区分算子的能力和局限性（即，具有突变潜力和老化的超突变）。最近的工作表明，老化与局部突变相结合，可以帮助摆脱局部最优的动态优化基准函数。我们概括了这一结果，严格证明老化导致相当大的速度加快（相比进化算法（EA））的标准Cliffbenchmark功能时，使用本地和全球的突变。除非停止在第一建设性突变（FCM）机制的应用，我们表明，超突变需要指数预期运行时间优化任何函数的多项式数量的最优。如果使用FCM，则预期运行时间至多是比使用人工适应度水平方法的任何随机局部搜索算法所实现的上限大的线性因子。然而，我们证明了使用超变的算法可以大大快于EA在逃避局部最优。完整的Opt-IA的分析表明，它是有效的，以前考虑的功能和突出的问题，使用完整的算法是至关重要的。
We present a time complexity analysis of the Opt-IA artificial immune system (AIS). We first highlight the power and limitations of its distinguishing operators (i.e., hypermutations with mutation potential and ageing) by analysing them in isolation. Recent work has shown that ageing combined with local mutations can help escape local optima on a dynamic optimisation benchmark function. We generalise this result by rigorously proving that ageing leads to considerable speed-ups (compared to evolutionary algorithms (EAs)) on the standard Cliffbenchmark function both when using local and global mutations. Unless thestop at first constructive mutation(FCM) mechanism is applied, we show that hypermutations require exponential expected runtime to optimise any function with a polynomial number of optima. If instead FCM is used, the expected runtime is at most a linear factor larger than the upper bound achieved for any random local search algorithm using the artificial fitness levels method. Nevertheless, we prove that algorithms using hypermutations can be considerably faster than EAs at escaping local optima. An analysis of the complete Opt-IA reveals that it is efficient on the previously considered functions and highlights problems where the use of the full algorithm is crucial.
登录
查看更多内容
自然进化和人工进化的运行时比较
影响因子：
1.1
作者：
T. Paixão;Jorge Pérez Heredia;Dirk Sudholt;Barbora Trubenová
通讯作者：
Barbora Trubenová
遗传算法中多样性的出现及其对交叉的好处
DOI：
--
发表时间：
2016
期刊：
Parallel Problem Solving from Nature
影响因子：
--
作者：
D. Dang;T. Friedrich;Timo Kötzing;Martin S. Krejca;P. Lehre;P. S. Oliveto;Dirk Sudholt;Andrew M. Sutton
通讯作者：
Andrew M. Sutton
当加号策略优于逗号策略时以及何时不优于逗号策略
DOI：
--
发表时间：
2007
期刊：
IEEE Symposium on Foundations of Computational Intelligence
影响因子：
--
作者：
J. Jägersküpper;T. Storch
通讯作者：
T. Storch
人工免疫系统的变异：具有突变潜力的超突变
DOI：
--
发表时间：
2011
期刊：
International Conference on Artificial Immune Systems
影响因子：
--
作者：
T. Jansen;C. Zarges
通讯作者：
C. Zarges
论免疫算法的收敛性
DOI：
--
发表时间：
2007
期刊：
IEEE Symposium on Foundations of Computational Intelligence
影响因子：
--
作者：
V. Cutello;Giuseppe Nicosia;Mario Romeo;P. S. Oliveto
通讯作者：
P. S. Oliveto