遗传算法与蒙娜丽莎

这几天我订阅的几个网站都在转载同一个消息:某人利用遗传算法,只用50个半透明的多边形就重现了达芬奇名画《蒙娜丽莎》(http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/)。

这只是遗传算法一个很典型也很简单的应用,之所以引人关注,是因为作者利用图像这种可视化的方式直观地呈现出算法结果的质量。我觉得在教授遗传算法或全局优化的课上,这是一个很好的例子和练习。

这个例子让人觉得遗传算法确实”威力强大“。但”No Free Lunch Theorem“指出,在求解优化问题时,如果不利用问题结构的信息,任何算法在平均意义上都不比瞎猜更好。遗传算法之所在这个蒙娜丽莎问题上有不错的性能,是因为这个问题解空间的结构有一些很好的性质:

  1. 任何解都是可行解。换而言之,任何一种多边形的放置方式都是可以接受的。
  2. 相邻的解有相近的目标函数值。换而言之,如果多边形的放置方式相似,则所得到的画的效果(用与达芬奇原画的相似程度衡量)也相近。
  3. 目标函数的形状很好:最优解所在的峰远高于其他地方,很有可能几乎就是一个单峰函数,或者虽然是多峰,但这些峰的高度都接近最优解。因此,就算只是随便一个局部最优的解,看起来已经足够好了。
About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: