39

今天，我阅读了 Roger Alsing 的这篇博客文章，内容是关于如何仅使用 50 个半透明多边形绘制蒙娜丽莎的复制品。

我对那个特定案例的结果很着迷，所以我想知道（这是我的问题）：遗传编程如何工作以及遗传编程可以解决哪些其他问题？

4

8 回答 8

31

关于罗杰的蒙娜丽莎计划是否是基因编程存在一些争论。它似乎更接近于 (1 + 1)进化策略。这两种技术都是更广泛的进化计算领域的例子，其中还包括遗传算法。

遗传编程 (GP) 是进化计算机程序的过程（通常以树的形式 - 通常是 Lisp 程序）。如果您专门询问全科医生，John Koza 被广泛认为是领先的专家。他的网站包含许多指向更多信息的链接。GP 通常是计算密集型的（对于不平凡的问题，它通常涉及大量机器）。

如果您问得更笼统，进化算法 (EA) 通常用于为使用其他技术无法轻松解决的问题（例如 NP-hard 问题）提供良好的近似解决方案。许多优化问题都属于这一类。找到精确的解决方案可能计算量太大，但有时接近最优的解决方案就足够了。在这些情况下，进化技术可能是有效的。由于它们的随机性，进化算法永远不能保证找到任何问题的最佳解决方案，但如果存在，它们通常会找到一个好的解决方案。

进化算法也可以用来解决人类不知道如何解决的问题。没有任何人类先入之见或偏见的 EA 可以生成令人惊讶的解决方案，这些解决方案可与人类产生的最佳努力相媲美或更好。即使我们不知道如何创建一个好的解决方案，我们也必须能够识别出一个好的解决方案。换句话说，我们需要能够制定一个有效的适应度函数。

一些例子

编辑： 免费提供的书，遗传编程领域指南，包含 GP 产生人类竞争结果的示例。

于 2008-12-10T12:21:05.993 回答
10

有趣的是，在 Grand Theft Auto IV 和最新的星球大战游戏（The Force Unleashed）等游戏中使用的动态角色动画背后的公司使用基因编程来开发运动算法。该公司的网站在这里，视频令人印象深刻：

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

我相信他们模拟了角色的神经系统，然后在一定程度上随机化了连接。然后，他们将走得最远的模型的“基因”结合起来，在后代中创造出越来越多能干的“孩子”。真正迷人的模拟工作。

我还看到了寻路自动机中使用的遗传算法，寻找食物的蚂蚁就是典型的例子。

于 2008-12-10T12:55:01.590 回答
8

遗传算法可用于解决大多数优化问题。但是，在很多情况下，有更好、更直接的方法来解决它们。它属于元编程算法类，这意味着它能够适应几乎任何你可以扔给它的东西，因为你可以生成一种编码潜在解决方案的方法，组合/变异解决方案，并决定哪个解决方案比其他解决方案更好。GA 优于其他元编程算法，因为它可以比纯爬山算法（如模拟退火）更好地处理局部最大值。

于 2008-12-10T09:33:09.127 回答
6

我在论文中使用遗传编程来模拟基于地形的物种进化，但这当然是遗传算法的 A-life 应用。

GA擅长的问题是爬山问题。问题是，通常手工解决大多数问题更容易，除非定义问题的因素是未知的，换句话说，你无法以其他方式获得这些知识，比如与社会和社区有关的事情，或者在以下情况下你有一个很好的算法，但你需要微调参数，这里 GA 非常有用。

我做过的一个微调的情况是，基于相同的算法微调几个奥赛罗 AI 玩家，赋予每个不同的游戏风格，从而使每个对手都独一无二，并有自己的怪癖，然后我让他们竞争选出顶部我在游戏中使用的 16 个 AI。好处是他们都是非常优秀的玩家，技术差不多，所以这对人类对手来说很有趣，因为他们无法轻易猜出AI。

于 2008-12-10T09:11:13.040 回答
5

http://en.wikipedia.org/wiki/Genetic_algorithm#Problem_domains

于 2008-12-10T09:10:41.027 回答
5

您应该问自己：“我可以（先验地）定义一个函数来确定特定解决方案相对于其他解决方案的好坏程度吗？”

在蒙娜丽莎的例子中，你可以很容易地确定新绘画是否比以前的绘画更像源图像，因此可以“轻松”应用遗传编程。

于 2008-12-10T09:30:21.097 回答
4

我有一些使用遗传算法的项目。GA 是优化问题的理想选择，因为当您无法开发完全顺序的、精确的算法来解决问题时。例如：什么是汽车特性的最佳组合，以使其更快，同时更经济？

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

于 2008-12-10T12:59:35.370 回答
2

机器人技术中有一个新兴领域，称为进化机器人学( w:Evolutionary Robotics )，它大量使用遗传算法 (GA)。

请参阅w：遗传算法：

简单的世代遗传算法伪代码

  1. 选择初始种群
  2. 评估群体中每个个体的适应度
  3. 重复直到终止：（达到时间限制或足够的适应度）
  4. 选择排名最佳的个体进行复制
  5. 通过交叉和/或突变（基因操作）培育新一代并产生后代
  6. 评估后代的个体适应度
  7. 用后代替换人口中排名最差的部分

关键是生殖部分，它可能发生有性或无性，使用遗传算子Crossover和Mutation。

于 2008-12-14T22:38:19.043 回答