• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International conference on parallel problem solving from nature >A Simple Proof for the Usefulness of Crossover in Black-Box Optimization
【24h】

A Simple Proof for the Usefulness of Crossover in Black-Box Optimization

机译：黑箱优化中交叉有用性的简单证明

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The idea to recombine two or more search points into a new solution is one of the main design principles of evolutionary computation (EC). Its usefulness in the combinatorial optimization context, however, is subject to a highly controversial discussion between EC practitioners and the broader Computer Science research community. While the former, naturally, report significant speedups procured by crossover, the belief that sexual reproduction cannot advance the search for high-quality solutions seems common, for example, amongst theoretical computer scientists. Examples that help understand the role of crossover in combinatorial optimization are needed to promote an intensified discussion on this subject. We contribute with this work an example of a crossover-based genetic algorithm (GA) that provably outperforms any mutation-based black-box heuristic on a classic benchmark problem. The appeal of our examples lies in its simplicity: the proof of the result uses standard mathematical techniques and can be taught in a basic algorithms lecture. Our theoretical result is complemented by an empirical evaluation, which demonstrates that the superiority of the GA holds already for quite small problem instances.
机译：将两个或多个搜索点重组为新解决方案的想法是进化计算（EC）的主要设计原理之一。但是，其在组合优化环境中的有用性受到EC从业人员与更广泛的计算机科学研究界之间极富争议性的讨论。尽管前者自然而然地报告了由于交叉而实现的显着提速，但是，例如，在理论计算机科学家中，人们普遍认为有性繁殖不能促进对高质量解决方案的搜索。需要一些示例来帮助理解交叉在组合优化中的作用，以促进对此主题的深入讨论。我们为这项工作提供了一个基于交叉的遗传算法（GA）的示例，该算法在经典基准问题上可胜过任何基于突变的黑盒启发式算法。我们的示例的吸引力在于其简单性：结果的证明使用标准的数学技术，并且可以在基础算法课程中进行讲授。我们的理论结果得到了经验评估的补充，该评估表明，遗传算法的优越性已经在相当小的问题实例中占有一席之地。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号