期刊
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION
卷 24, 期 6, 页码 995-1009出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TEVC.2019.2917014
关键词
Runtime; Evolutionary computation; Genetic algorithms; Sociology; Statistics; Heuristic algorithms; Standards; Computational and artificial intelligence; evolutionary computation; genetic algorithms
It is known that the (1 + 1)-EA with mutation rate c/n optimizes every monotone function efficiently if c < 1, and needs exponential time on some monotone functions (HOTTOPIC functions) if c >= 2.2. We study the same question for a large variety of algorithms, particularly for the (1 + lambda)-EA, (mu + 1)-EA, (mu + 1)-GA, their fast counterparts, and for the (1 + (lambda, lambda))-GA. We find that all considered mutation-based algorithms show a similar dichotomy for HOTTOPIC functions, or even for all monotone functions. For the (1 + (lambda, lambda))-GA, this dichotomy is in the parameter c gamma, which is the expected number of bit flips in an individual after mutation and crossover, neglecting selection. For the fast algorithms, the dichotomy is in m(2)/m(1), where m(1) and m(2) are the first and second falling moment of the number of bit flips. Surprisingly, the range of efficient parameters is not affected by either population size mu nor by the offspring population size lambda. The picture changes completely if crossover is allowed. The genetic algorithms (mu + 1)-GA and (mu+1)-fGA are efficient for arbitrary mutations strengths if mu is large enough.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据