首页> 外文期刊>Algorithmica >Ranking-Based Black-Box Complexity
【24h】

Ranking-Based Black-Box Complexity

机译:基于排名的黑匣子复杂性

获取原文
获取原文并翻译 | 示例

摘要

Randomized search heuristics such as evolutionary algorithms, simulated annealing, and ant colony optimization are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field. While several strong runtime analysis results have appeared in the last 20 years, a powerful complexity theory for such algorithms is yet to be developed. We enrich the existing notions of black-box complexity by the additional restriction that not the actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the black-box algorithm. Many randomized search heuristics belong to this class of algorithms. We show that the new ranking-based model can give more realistic complexity estimates. The class of all binary-value functions has a black-box complexity of O(logn) in the previous black-box models, but has a ranking-based complexity ofΘ(n). On the other hand, for the class of all OneMax functions, we present a ranking-based black-box algorithm that has a runtime of Θ(n/logn), which shows that the OneMax problem does not become harder with the additional ranking-basedness restriction.
机译:诸如进化算法,模拟退火和蚁群优化之类的随机搜索启发式方法是一类广泛使用的通用算法。通过理论计算机科学的经典方法对其进行分析是一个不断发展的领域。尽管在过去20年中出现了一些强大的运行时分析结果,但尚未开发出针对此类算法的强大的复杂性理论。我们通过附加的限制来充实现有的黑盒复杂性概念,即黑盒算法不会考虑实际目标值,而只会考虑先前评估的解决方案的相对质量。许多随机搜索启发式算法都属于此类算法。我们表明,新的基于排名的模型可以给出更现实的复杂性估计。所有二进制值函数的类在以前的黑盒模型中都具有O(logn)的黑盒复杂度,但具有基于排名的复杂度Θ(n)。另一方面,对于所有OneMax函数的类,我们提出了一种基于排名的黑盒算法,其运行时间为Θ(n / logn),这表明,通过附加排名,OneMax问题不会变得更加困难-基础限制。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号