今天我读了Roger Alsing关于如何使用50个半透明多边形绘制蒙娜丽莎复制品的博客文章.
我对这个特定案例的结果非常着迷,所以我想知道(这是我的问题):遗传编程如何运作以及遗传编程可以解决哪些其他问题？
关于罗杰的蒙娜丽莎计划是否完全是遗传编程,存在一些争论.它似乎更接近(1 + 1)进化战略.这两种技术都是进化计算的更广泛领域的例子,其中还包括遗传算法.
遗传编程(GP)是发展计算机程序的过程(通常以树的形式 - 通常是Lisp程序).如果你专门询问GP,John Koza被广泛认为是领先的专家.他的网站包含许多指向更多信息的链接.GP通常是计算密集型的(对于非平凡的问题,它通常涉及大型机器网格).
如果您更普遍地询问,进化算法(EA)通常用于为使用其他技术(例如NP难问题)无法轻易解决的问题提供良好的近似解决方案.许多优化问题都属于这一类.找到精确的解决方案可能计算量太大,但有时候接近最优的解决方案就足够了.在这些情况下,进化技术可能是有效的.由于它们的随机性,进化算法永远不能保证为任何问题找到最佳解决方案,但如果存在,它们通常会找到一个好的解决方案.
进化算法也可用于解决人类实际上不知道如何解决的问题.没有任何人类偏见或偏见的EA可以产生令人惊讶的解决方案,这些解决方案与人类最好的努力相当或更好.即使我们不知道如何创建一个好的解决方案,如果它被呈现给我们,我们只需要认识到一个好的解决方案.换句话说,我们需要能够形成有效的适应度函数.
一些例子
旅行推销员
数独
编辑: 免费提供的书,遗传编程实地指南,包含GP产生人类竞争结果的例子.
有趣的是,在侠盗猎车手IV和最新的星球大战游戏(The Force Unleashed)等游戏中使用的动态角色动画背后的公司使用遗传编程来开发运动算法.该公司的网站在这里,视频非常令人印象深刻:
http://www.naturalmotion.com/euphoria.htm
我相信他们模拟了角色的神经系统,然后在某种程度上随机化了连接.然后,他们将模型的"基因"结合起来,这些模型走得最远,以便在后代中创造出越来越多的"儿童".真正令人着迷的模拟工作.
我也看到了在寻路自动机中使用的遗传算法,食物寻找蚂蚁就是典型的例子.
遗传算法可用于解决大多数任何优化问题.但是,在很多情况下,有更好,更直接的方法来解决它们.它属于元编程算法类,这意味着它能够适应你可以抛出的任何东西,因为你可以生成一种编码潜在解决方案的方法,组合/改变解决方案,并决定哪个解决方案比其他人更好.GA优于其他元编程算法,因为它可以比纯爬山算法(如模拟退火)更好地处理局部最大值.
我在论文中使用遗传编程来模拟基于地形的物种进化,但这当然是遗传算法的A-life应用.
GA擅长的问题是登山问题.问题是通常手工解决大多数这些问题更容易,除非定义问题的因素未知,换句话说,你不能以其他方式获得知识,说与社会和社区相关的事情,或者在你有一个很好的算法,但你需要微调参数,这里GA非常有用.
我所做的微调情况是根据相同的算法微调几个奥赛罗AI玩家,给出每种不同的游戏风格,从而使每个对手都独一无二,并有自己的怪癖,然后我让他们竞争剔除顶部16 AI是我在游戏中使用的.优点是他们都是技术水平相当高的优秀球员,所以人类对手很有意思,因为他们无法轻易猜到人工智能.
http://en.wikipedia.org/wiki/Genetic_algorithm#Problem_domains
您应该问自己:"我(先验)可以定义一个函数来确定特定解决方案相对于其他解决方案的优势吗？"
在mona lisa示例中,您可以轻松确定新绘画看起来是否比上一幅绘画更像源图像,因此可以"轻松"应用遗传编程.
京公网安备 11010802040832号 | 京ICP备19059560号-6 