从前,一群扇贝在海岸边悠哉游哉地生活着。它们衣食不愁,连房子也有了着落,担忧的只有一件事:每隔一段时间,总有人来挖走它们之中的一部分。有意思的是,这个人的家族以Firefox的图标作为纹章,所以他总是选择那些花纹长得比较不像Firefox图标的扇贝。经过几十万代的繁衍后,扇贝壳上的图案逐渐变得与Firefox图标相差无几。
这个故事确有其事———它们生活在我的电脑中,是一个遗传算法程序的一部分。程序的目的就是用100个半透明三角形画出Firefox图标。
遗传算法是一种解决问题的方法。它模拟大自然中种群在选择压力下的演化,从而得到问题的一个近似解。在上世纪五十年代,生物学家已经知道基因在自然演化过程中的作用了。他们希望能在新出现的计算机上模拟这个过程,用以尝试定量研究基因与进化之间的关系。这就是遗传算法的滥觞。
首先,我们把100个半透明三角形组成的东西看成一个生物个体(比如扇贝),可以说它的样子是由这些三角形的具体位置和颜色决定的。所以,我们可以把一个一个的半透明三角形看做是这些扇贝的“基因”。而组成扇贝的这100个基因就组成了每个扇贝个体的“染色体”。
扇贝当然要繁衍后代。生物界中的繁衍无非就是父母的基因组合产生新的个体。所以,我们在程序中选择两个原有的扇贝,然后从这两个扇贝的染色体中随机选取一共100个基因组成新个体的染色体。为了产生新的基因,使基因的种类更多样化,在组合的时候,新的扇贝的基因有一定的概率发生变异。这就是说,其中透明三角形的位置或者颜色有可能发生随机改变。
为了使扇贝的样子向Firefox图标靠近,我们要给它们加上一点选择压力:把每一代扇贝中最不像Firefox的淘汰出去。这个选择过程可以通过像素比较来完成。
最后,在自然界中,种群的演化是一个无休止的过程,但程序总要停下来给出一个结果。那么,什么时候终止演化输出结果呢?这就要订立一个终止条件。一旦满足这个条件,程序就输出当前最好的结果并停止。最简单的终止条件就是,如果种群经过了很多代之后仍然没有显著改变适应性的变异的话,我们就停止并输出结果。
好了,现在是万事俱备只欠东风了。定义好基因,写好繁衍、变异、评价适应性、淘汰和终止的代码之后,只需要随机产生一个适当大小的种群,然后让它这样一代代地繁衍、变异和淘汰下去,到最后我们就会获得一个让人惊喜的结果。
遗传算法能在相对较短的时间内给出一个足够好、能凑合的答案,它从问世伊始就越来越受到大家的重视,对它的研究也是方兴未艾。当然,它也有缺点,比如说早期的优势基因可能会很快通过交换基因的途径散播到整个种群中,这样有可能导致早熟(premature)。这个问题是难以完全避免的。
这也从一个侧面说明,我们不一定需要一个智能才能得到一个构造精巧的系统。无论如何,如果我们要将遗传算法的发明归功于一个人的话,我会将它归功于达尔文,进化论的奠基人。如果我们不知道自然演化的过程,我们也不可能在电脑中模拟它,更不用说将它应用于实际了。
向达尔文致敬!
“扇贝实验”中的子代输出结果。每个图形下面的数字代表其代数。很显然,最初那些由随机三角形组成的“生物”,在“繁殖”了12万代之后,看起来已经与Firefox图标相差无几了。
from http://tech.sina.com.cn/
分享到:
相关推荐
为寻找计算机自动绘制原始图形的方法,提出了通过遗传算法进行图形自动拼贴、分层次组合绘制的方法.首先对已有的图形进行层次划分、功能分解,分解成具有最小层次和最小单元的细胞图形;根据顾客需求以及输入的需求参数...
遗传算法先画出函数曲线,随后第一遗传算法参数,参数可自调,对曲线进行寻优,可以得到最优个体,以及种群均值变化。
用python实现的遗传算法的一个实例 求函数f x 10 sin 5x + 7 cos 4x 0 < x < 10的最大值
遗传算法代码解析 遗传算法是一种基于自然选择和遗传原理的优化方法,通过模拟自然界中的进化过程来搜索最优解。下面是对遗传算法代码的解析: 变量初始化 在代码中,变量 `m` 和 `n` 分别表示总工件数和总工序数...
遗传算法的优化处理,输出优化前后染色体的变化情况以及优化迭代收敛曲线,matlab2021a测试
基于遗传算法,利用python PIL库,使用100个三角形拟合100*100像素图片。
利用de Casteljau算法绘制Bezier曲线,是利用了递归的思想
基于VC++6.0的遗传算法解TSP问题对话框应用程序,拥有直接绘制城市路径图功能,遗传算法效率高。适应函数采用了基于排序的指数型评价函数,收敛性更快,自然选择效果更优;提供两种交叉算法,默认使用贪婪交叉算法,...
2)调用画点的函数,分别用DDA、中点Bresenham算法和改进Bresenham算法绘制直线和中点算法绘制直线、用不同的算法绘制圆和椭圆 ,并各自比较算法精度与效率的差别 。 3)实现二维图形的变换。(包括平移,放缩,...
C# C# 绘制实时曲线及坐标轴的绘制 图像处理、遗传算法集C# C# 绘制实时曲线及坐标轴的绘制 图像处理、遗传算法集
通过采用遗传算法实现函数全局最优的极值计算。采用matlab语言编写完成,可以直接运行,包含图形的绘制
遗传算法 GA 最优保留 轮盘赌算子、单点交叉算子、位点变异算子 最后绘制最优适应度进化曲线
并利用MATLAB软件编写了普通V带传动遗传算法优化设计程序,绘制出最佳适应度值线图描述遗传算法的搜索过程,在获得可靠的V带传动结构全局最优解的同时,使求解过程简化,计算精度提高,从而为普通V带传动优化设计提供了...
遗传算法GA 优化VMD 变分模态分解参数,优化参数为分解层数K和惩罚因子alpha,适应度函数为包络熵或样本熵,MATLAB程序。 以齿轮折断状态为测试组(该组数据为Excel,可将其直接替换为自己的数据), 根据不同的增加...
利用遗传算法,对帐篷工序问题进行优化安排的MATLAB程序,并绘制生产工序甘特图
matlab利用遗传算法求解目标函数,包括适应度曲线
绘制桌面图标的背景,网吧等经常使用的壁纸生成器.
- 通过opencv绘制函数曲线图和坐标图 - 一元最优化目标 ...- 量子遗传算法(QGA)是一种概率型算法,抛弃普通遗传算法的基因交叉和变异操作,通过使用量子门旋转来调整基因,基本理解是每个基因代表
遗传算法求解VRP问题,自带绘制路径功能