强大的遗传算法:用50个半透明多边形重现蒙娜丽莎

53 views
Skip to first unread message

Calon

unread,
Dec 9, 2008, 10:13:25 AM12/9/08
to min...@googlegroups.com


 
 

Sent to you by Calon via Google Reader:

 
 

via Matrix67: My Blog by Matrix67 on 12/8/08

通过不断的杂交、变异并与原作比较确定适应度,经过904314代后,终于得到了一个满意的结果。
来源:http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

 



 
 

Things you can do from here:

 
 

biantaishabi

unread,
Dec 9, 2008, 5:04:50 PM12/9/08
to Copy&Paste Exchange
这应该不能算是进化论的遗传算法吧, 这是神创论算法......

神已经设计好了一个最终模型(最优解, 在这里就是蒙娜丽莎的原作), 然后往那个上面慢慢地修正 (而且算法里没有交配, 只有变异, 每次改变一下
DNA序列, 看来是单性繁殖的)。
遗传算法的目的是为了找到那个未知的最优解, 有一个类似自然选择的优胜劣汰的评估的函数来评估每次的得出来的解, 然后试图找到最优的解。

这个是既然已经知道最优解了, 每次把他的序列往解的方向修改一小点, 当然最后最收敛到最后的解了。 这个当然也可以说是遗传算法, 只不过它的评估
函数就是他的解。 知道最优解了往解上靠, 和不知道解要求解, 我觉得还是挺不一样的。


On Dec 9, 4:13 pm, Calon <calon...@gmail.com> wrote:
> Sent to you by Calon via Google Reader: 强大的遗传算法:用50个半透明多

> 边形重现蒙娜丽莎 via Matrix67: My Blog by Matrix67 on 12/8/08


> 通过不断的杂交、变异并与原作比较确定适应度,经过904314代后,终于得到了一
> 个满意的结果。
> 来

> 源:http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mo...


>
> Things you can do from here:

> - Subscribe to Matrix67: My Blog using Google Reader
> - Get started using Google Reader to easily keep up with all your
> favorite sites

Willow

unread,
Dec 9, 2008, 10:33:07 PM12/9/08
to min...@googlegroups.com
石油工人都要了解遗传算法了?这年头要混口饭吃好难啊...

发自我的 iPhone

在 2008-12-10,6:04,biantaishabi <bianta...@gmail.com> 写到:

biantaishabi

unread,
Dec 9, 2008, 10:42:27 PM12/9/08
to Copy&Paste Exchange
晕, 我以前混研究生的时候就是研究(试图研究......)组合优化算法的呀 ;D

On Dec 10, 4:33 am, Willow <chengyin....@gmail.com> wrote:
> 石油工人都要了解遗传算法了?这年头要混口饭吃好难啊...
>
> 发自我的 iPhone
>

> 在 2008-12-10,6:04,biantaishabi <biantaish...@gmail.com> 写到:

Calon

unread,
Dec 9, 2008, 11:44:45 PM12/9/08
to min...@googlegroups.com
原初的神创论是没有进化算法的,因为神创造的必是完美的、有其目的的,不需要进化;

如果整体上是有目的的定向进化,可能和拉马克进化论会更接近一点,那样计算过程中间阶段被抛弃的其他组合就会少很多;不过作者的解释是随机生成多边形,再抛弃那些不合适的,相当于随机变异+特定环境选择,那么应该还是更接近达尔文的理论吧。

我的理解是这样的,无论是自然的、生物本身的、还是人类或神的压力或者目的,对算法来说都是要逼近的目标,算法只要关心怎么获取筛选对象怎么逼近怎么筛选。
不知道解要求解,对算法来说是不可能的,因为就算是自然选择也是要告诉你当前需要适应的环境条件如何,这已经不是未知的了。

道金斯在说明进化论不是完全随机过程时,也写过一个小程序,每一次随机变异后都保留有特定特征的变异体,就和这个算法本质上差不多,而仍然是属于达尔文进化论范畴的。

人类想要获得产奶高的奶牛时,是有一个已知的目的的,这个不断筛选的过程和机制,对奶牛来说,与自然选择没有本质区别(人也相当于奶牛们的"自然"因素),还是进化论的算法。

2008/12/10 biantaishabi <bianta...@gmail.com>

biantaishabi

unread,
Dec 10, 2008, 12:00:28 AM12/10/08
to Copy&Paste Exchange
当然是不知道解才求解, 知道了还求个什么?

On Dec 10, 5:44 am, Calon <calon...@gmail.com> wrote:
> 原初的神创论是没有进化算法的,因为神创造的必是完美的、有其目的的,不需要进化;
> 如果整体上是有目的的定向进化,可能和拉马克进化论会更接近一点,那样计算过程中间阶段被抛弃的其他组合就会少很多;不过作者的解释是随机生成多边形,再抛弃那些不合适的,相当于随机变异+特定环境选择,那么应该还是更接近达尔文的理论吧。
>
> 我的理解是这样的,无论是自然的、生物本身的、还是人类或神的压力或者目的,对算法来说都是要逼近的目标,算法只要关心怎么获取筛选对象怎么逼近怎么筛选。
> 不知道解要求解,对算法来说是不可能的,因为就算是自然选择也是要告诉你当前需要适应的环境条件如何,这已经不是未知的了。
>
> 道金斯在说明进化论不是完全随机过程时,也写过一个小程序,每一次随机变异后都保留有特定特征的变异体,就和这个算法本质上差不多,而仍然是属于达尔文进化论范畴的。
>
> 人类想要获得产奶高的奶牛时,是有一个已知的目的的,这个不断筛选的过程和机制,对奶牛来说,与自然选择没有本质区别(人也相当于奶牛们的"自然"因素),还是进化论的算法。
>

> 2008/12/10 biantaishabi <biantaish...@gmail.com>

biantaishabi

unread,
Dec 10, 2008, 12:17:37 AM12/10/08
to Copy&Paste Exchange
不知道解要求解,对算法来说是不可能的

---------------

举个例子, 比如旅行推销员问题, 一个推销员要分布在美国的n个城市, 每个都要走到, 求最短路线。 算法当然可以解决这个问题, 最蠢的算法可以
穷举, 但是复杂度是n的阶乘。 或者可以用别的算法, 可以得出最短的路线解, 但是复杂度要低得多。这里的条件就是要路线要短,比其他的路线都要
短。

自然选择不是解本身, 而是约束条件, 在遗传算法里面就是用你的约束条件做些评估函数来作为自然选择来优胜劣汰。 开始是不并不知道最后的路线是怎么
样的, 最后算完了才知道, 哦, 原来是这样的。 进化也是这样, 开始并不知道是什么样子, 最后才知道是什么样子, 而且其中有基因突变就会有无
限的可能。 但是这个蒙娜丽莎已经知道最后是个什么样子了, 仅仅是看起来像进化而已, 实际上就是一个收敛, 无论如何是只有一个结果的。

On Dec 10, 5:44 am, Calon <calon...@gmail.com> wrote:

> 原初的神创论是没有进化算法的,因为神创造的必是完美的、有其目的的,不需要进化;
> 如果整体上是有目的的定向进化,可能和拉马克进化论会更接近一点,那样计算过程中间阶段被抛弃的其他组合就会少很多;不过作者的解释是随机生成多边形,再抛弃那些不合适的,相当于随机变异+特定环境选择,那么应该还是更接近达尔文的理论吧。
>
> 我的理解是这样的,无论是自然的、生物本身的、还是人类或神的压力或者目的,对算法来说都是要逼近的目标,算法只要关心怎么获取筛选对象怎么逼近怎么筛选。
> 不知道解要求解,对算法来说是不可能的,因为就算是自然选择也是要告诉你当前需要适应的环境条件如何,这已经不是未知的了。
>
> 道金斯在说明进化论不是完全随机过程时,也写过一个小程序,每一次随机变异后都保留有特定特征的变异体,就和这个算法本质上差不多,而仍然是属于达尔文进化论范畴的。
>
> 人类想要获得产奶高的奶牛时,是有一个已知的目的的,这个不断筛选的过程和机制,对奶牛来说,与自然选择没有本质区别(人也相当于奶牛们的"自然"因素),还是进化论的算法。
>

> 2008/12/10 biantaishabi <biantaish...@gmail.com>

biantaishabi

unread,
Dec 10, 2008, 12:29:01 AM12/10/08
to Copy&Paste Exchange
我也搞不清楚产奶多的奶牛那算不算进化, 我总觉得人对于奶牛来说有点像神的感觉的, 现在人都可以通过基因工程以改变奶牛的基因排列来搞出来产奶更多
的奶牛了......

On Dec 10, 5:44 am, Calon <calon...@gmail.com> wrote:

> 原初的神创论是没有进化算法的,因为神创造的必是完美的、有其目的的,不需要进化;
> 如果整体上是有目的的定向进化,可能和拉马克进化论会更接近一点,那样计算过程中间阶段被抛弃的其他组合就会少很多;不过作者的解释是随机生成多边形,再抛弃那些不合适的,相当于随机变异+特定环境选择,那么应该还是更接近达尔文的理论吧。
>
> 我的理解是这样的,无论是自然的、生物本身的、还是人类或神的压力或者目的,对算法来说都是要逼近的目标,算法只要关心怎么获取筛选对象怎么逼近怎么筛选。
> 不知道解要求解,对算法来说是不可能的,因为就算是自然选择也是要告诉你当前需要适应的环境条件如何,这已经不是未知的了。
>
> 道金斯在说明进化论不是完全随机过程时,也写过一个小程序,每一次随机变异后都保留有特定特征的变异体,就和这个算法本质上差不多,而仍然是属于达尔文进化论范畴的。
>
> 人类想要获得产奶高的奶牛时,是有一个已知的目的的,这个不断筛选的过程和机制,对奶牛来说,与自然选择没有本质区别(人也相当于奶牛们的"自然"因素),还是进化论的算法。
>

> 2008/12/10 biantaishabi <biantaish...@gmail.com>

Calon

unread,
Dec 10, 2008, 11:12:47 AM12/10/08
to min...@googlegroups.com
想了一下,其实这个算法不是遗传算法,该算爬山算法,不是因为人为设置了目标,而是因为其个体数是1,之后的变化和比较都是在这一个个体上的,如果是有n个初始的图像,每个图像中有若干个多边形,然后它们交配和变异,再根据适应度选择出下一代,如此反复得到最优解(设置一个终止条件:如与蒙娜丽莎画像的相似度达到什么程度),才算遗传算法。
至于之前争论的话题,我觉得后者(n个个体交叉变异的)即使设置了"蒙娜丽莎的画像"作为目标,也还是遗传算法。

这个算法得到的只是"很像蒙娜丽莎画像"的结果,而不是唯一的结果,再跑一次,还会是蒙娜丽莎,但这次最优解的多边形数量、形状和位置可能都不同(而且可能中途走错了路径,没得出最优解),这可以看作是自然界要求某种生物在某种条件下存活下去而不管它是如何进化到这个目标和以何种面貌出现的。

如果把旅行推销员问题中的"最短"看作"蒙娜丽莎",而把"路线"看作"多边形的数量、形状和位置",那么是不是好理解一些?如果没有"最短"的目标,那么"路线"的计算要如何停下来?最优解的"如何算是最优"是已知的(就像最像原画是已知的),而具体怎么解(怎么画)才是未知的。

之前提到的类似自然选择的优胜劣汰的评估的函数,不知其评估的依据是什么呢?

自然选择和遗传算法的过程中确实是有收敛,所以进化才不等于随意的摇晃零件纯粹靠偶然才组成一架飞机,没有收敛,这架"飞机"出现的概率会小到永远只能存在于理论中。

如果把人类也看作自然因素的一种(除了基因改造,那超出了随机变异的范围了,应该属于智慧修正论…),那么奶牛一路走过来是符合进化论的,换个说法则是人类利用进化论改造生物。
牛看人和人看神的区别在于:
1、牛会觉得人搞出来的都是大波怪物,而人认为神创造出来的是完美或者有深意的
2、牛的创造者不是人,进化出奶牛也并不神秘,而人认为神是其创造者,创造方法是个谜

2008/12/10 biantaishabi <bianta...@gmail.com>

John Hax

unread,
Dec 10, 2008, 11:16:46 AM12/10/08
to min...@googlegroups.com
我根据网站上的图片做了一个会动的,见附件。




2008/12/9 Calon <calo...@gmail.com>
monalisa.zip

biantaishabi

unread,
Dec 10, 2008, 11:40:41 AM12/10/08
to Copy&Paste Exchange
评估的依据就是看你的条件了, 比如路线问题, 可以是算最短的路线, 或者是费用最少的路线, 或者是美女最多的路线, 你要求什么样的解就怎样评估
嘛, 从后代中挑一个或者几个好的出来再进化。

因为我对牛的心理学没有研究, 我不跟你讨论牛啦, 都已经说到牛的想法比如牛觉不觉得大波是完美或者是有深意的, 以及牛觉得人深不神秘这样的问题
了......

On Dec 10, 5:12 pm, Calon <calon...@gmail.com> wrote:
> 想了一下,其实这个算法不是遗传算法,该算爬山算法,不是因为人为设置了目标,而是因为其个体数是1,之后的变化和比较都是在这一个个体上的,如果是有n个初始的图像,每个图像中有若干个多边形,然后它们交配和变异,再根据适应度选择出下一代,如此反复得到最优解(设置一个终止条件:如与蒙娜丽莎画像的相似度达到什么程度),才算遗传算法。
> 至于之前争论的话题,我觉得后者(n个个体交叉变异的)即使设置了"蒙娜丽莎的画像"作为目标,也还是遗传算法。
>
> 这个算法得到的只是"很像蒙娜丽莎画像"的结果,而不是唯一的结果,再跑一次,还会是蒙娜丽莎,但这次最优解的多边形数量、形状和位置可能都不同(而且可能中途走错了路径,没得出最优解),这可以看作是自然界要求某种生物在某种条件下存活下去而不管它是如何进化到这个目标和以何种面貌出现的。
>
> 如果把旅行推销员问题中的"最短"看作"蒙娜丽莎",而把"路线"看作"多边形的数量、形状和位置
> ",那么是不是好理解一些?如果没有"最短"的目标,那么"路线"的计算要如何停下来?最优解的"如何算是最优"是已知的(就像最像原画是已知的),而具体怎么解(怎么画)才是未知的。
>
> 之前提到的类似自然选择的优胜劣汰的评估的函数,不知其评估的依据是什么呢?
>
> 自然选择和遗传算法的过程中确实是有收敛,所以进化才不等于随意的摇晃零件纯粹靠偶然才组成一架飞机,没有收敛,这架"飞机"出现的概率会小到永远只能存在于理论中。
>

> 如果把人类也看作自然因素的一种(除了基因改造,那超出了随机变异的范围了,应该属于智慧修正论...),那么奶牛一路走过来是符合进化论的,换个说法则是人类利用进化论改造生物。


> 牛看人和人看神的区别在于:
> 1、牛会觉得人搞出来的都是大波怪物,而人认为神创造出来的是完美或者有深意的
> 2、牛的创造者不是人,进化出奶牛也并不神秘,而人认为神是其创造者,创造方法是个谜
>

> 2008/12/10 biantaishabi <biantaish...@gmail.com>

Reply all
Reply to author
Forward
0 new messages