logo标签列表

遗传编程的典型应用场景是什么？

genetic-programming
39
今天我阅读了Roger Alsing的博客文章，关于如何使用50个半透明多边形绘制Mona Lisa的复制品。
我对这个特定案例的结果非常着迷，所以我想知道（这是我的问题）：遗传编程是如何工作的？遗传编程还可以解决哪些其他问题？
一般来说，当你不知道如何解决问题时，所有的人工智能方法都是很好的选择。 - zaratustra
8个回答
31
有争议是否Roger的《蒙娜丽莎》程序属于遗传编程。它似乎更接近于(1 + 1)进化策略。这两种技术都是进化计算的广泛领域的例子，该领域还包括遗传算法。
遗传编程(GP)是演化计算的过程(通常以树的形式——通常是Lisp程序来表示计算机程序)。如果你特别询问GP，John Koza被广泛认为是领先的专家。他的网站包含了大量的链接以获取更多信息。对于非平凡问题，GP通常具有非常高的计算强度(它通常涉及大量的机器网格)。
如果您更一般地提问，进化算法(EAs)通常用于为不能轻易使用其他技术(如NP难问题)解决的问题提供良好的近似解。许多优化问题属于这个类别。找到一个精确解可能太过于计算密集，但有时一个近似最优解就足够了。在这些情况下，进化技术可以是有效的。由于它们的随机性质，进化算法永远不能保证为任何问题找到最优解，但如果存在一个好的解，它们通常会找到一个好的解。
进化算法也可以用来解决人类不知道如何解决的问题。一个没有任何人类先入为主或偏见的EA，可以生成令人惊讶的解决方案，这些解决方案与最好的人类生成的努力相媲美甚至更好。我们只需要能够识别出一个好的解决方案，即使我们不知道如何创建一个好的解决方案。换句话说，我们需要能够制定一个有效的fitness function。
一些例子：
- Travelling Salesman - Sudoku 编辑：免费提供的书籍A Field Guide to Genetic Programming包含了GP产生人类竞争结果的示例。
3
这场辩论有点愚蠢。定义很清楚，而且《蒙娜丽莎》代码缺乏重组。使用重组的正确定义可以大幅减少迭代次数（尽管会增加更昂贵的迭代），从而潜在地提高整体运行时间。 - Konrad Rudolph
详细数独生成器 http://anthony-tresontani.github.com/Python/2012/12/31/sudoku-generator-with-genetic/ - trez
10

有趣的是，Grand Theft Auto IV和最新的星球大战游戏（The Force Unleashed）中使用的动态角色动画背后的公司使用遗传编程来开发移动算法。该公司的网站在此处，并且视频非常令人印象深刻：

http://www.naturalmotion.com/euphoria.htm

我相信他们模拟了角色的神经系统，然后在一定程度上随机连接。然后将行走距离最远的模型的“基因”组合起来，以创建越来越能够成功的“后代”。真正迷人的模拟工作。

我也看到过遗传算法用于路径规划自动机器人，寻找食物的蚂蚁是经典例子。

你提到的蚂蚁示例并不是遗传算法，而是所谓的蚁群算法，它们具有类似的目的，但算法完全不同。 - Robert Gould
3
@Robert. 他提到的蚂蚁示例实际上是GP的经典玩具示例，它与蚂蚁群算法完全不同。 - Dennis
8
遗传算法可以用于解决几乎所有的优化问题。然而，在很多情况下，有更好的、更直接的方法来解决这些问题。它属于元编程算法的范畴，这意味着它能够适应几乎任何你能想到的东西，只要你能生成一种编码潜在解决方案的方法，组合/变异解决方案，并决定哪些解决方案比其他解决方案更好。与模拟退火等纯爬山算法相比，遗传算法具有处理局部最大值的优势。
6
我在我的论文中使用遗传编程来模拟基于地形的物种进化，但这当然是遗传算法的人工生命应用。
GA擅长解决的问题是爬山问题。问题在于，通常情况下，除非定义问题的因素未知，否则大多数这些问题都可以手动解决，换句话说，你无法以其他方式获得这些知识，例如与社会和社区有关的事情，或者在你有一个好的算法但需要微调参数的情况下，GA非常有用。
我所做的微调情况是根据相同算法微调了几个黑白棋AI玩家，给每个玩家不同的游戏风格，从而使每个对手独特且具有自己的特点，然后让它们竞争，挑选出前16名AI用于我的游戏。优势在于它们都是非常优秀的玩家，技能水平更或多或少相等，因此对于人类对手来说很有趣，因为他们不能轻易猜测AI。
2
我在我的论文中使用了遗传编程来模拟基于地形的物种进化。有什么在线的东西可以看一下吗？ :P - fableal
5
你应该问自己：“我是否可以（先验地）定义一个函数来确定特定解决方案与其他解决方案相比的好坏？”在蒙娜丽莎的例子中，你可以轻松地确定新绘画是否比以前的绘画更像源图像，因此遗传编程可以被“轻松”应用。
4

我有一些使用遗传算法的项目。当您无法开发完全顺序的精确算法来解决问题时，GA非常适用于优化问题。例如：如何使汽车更快且更经济，需要找到最佳的汽车特性组合。

目前，我正在开发一个简单的GA来制作播放列表。我的GA必须找到相似的专辑/歌曲的更好组合（这种相似性将通过last.fm的帮助进行“计算”），并为我建议播放列表。

5
哇，播放列表软件听起来像是一个有趣的项目。我希望你能与公众分享你从中学到的东西 :) - Dave R.
2
机器人学中出现了一个新兴领域，称为进化机器人学（w:Evolutionary Robotics），该领域广泛使用遗传算法（GA）。
请参见w:遗传算法：
简单的生成式遗传算法伪代码如下：
  1. 选择初始种群
  2. 评估种群中每个个体的适应性
  3. 重复执行以下步骤，直到终止条件满足（时间限制或达到足够的适应性）：
  4. 选择最好排名的个体进行繁殖
  5. 通过交叉和/或变异（遗传操作）繁衍新一代并产生后代
  6. 评估后代的个体适应度
  7. 用后代替换种群中最差的部分
关键在于繁殖部分，可以通过性或无性方式进行，使用遗传算子交叉和突变。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接