关键词:遗传算法
虽然,有许多变化的因素在影响遗传算法,包括人群大小、代(算法的迭代)、合并方法、适应性函数,适应性将如何影响繁衍的可能性,以及发生了多少变异。
该算法也存在一些缺陷。如果把应用于DNA的适应性官能看成是一系列的二进制位,效果最好。换句话说,如果DNA是一系列二进制的选项,是还是不是。蓝眼睛?黑眼睛?红头发?黑头发?合并双亲的DNA和随后的变异应当不允许特定的一些位组合出现,因为得出的DNA可能不再是最初的问题的有效解答。请记住,所谓“DNA”仅仅是适应性公式纯数学的一种解答。该公式中用到的一些值可能是无效的—例如,除数为零。
另外,遗传算法不受时间限制。由您来挑选代的数目。您可以确定某个目标 — 比方说,“找一个适应性为0.99999 的个体”,找到后停止。但是,结果是算法永远也不会结束,因为它没找到那个个体。如果您制定了不切实际的目标,或者代的数目太小,就会出现问题。尝试、出错,以及深入的思考是解决这个问题的最佳途径。
适应性公式返回的是介于0和1之间的一个浮点数。您也可以使用其它的范围的数,但是我的经验告诉我,浮点数是最有效的。比如,如果出于优选的考虑,您希望适应性是一个7位的整型数,您想要的范围就是0到32767之间。
当然,把优选推迟到您认为有需要的时候,这是一个好主意,那么您在开始的时候,最起码得有一个简单的适应性公式。适应性公式是遗传算法中最常用的函数,(它将要被调用的次数是(人群大小)x(代的数目)次),所以您应当尽可能的使它简单、快速。
有三种“好”的可以退出遗传算法的方式!首先,当 DNA 池里不再有变化时,您就可以决定退出。事实上,这是个棘手的测试,只要您能够把DNA表示为字符串,就可以利用一个确定串之间的差异的CPAN模块。第二,如果达到了适应性的目标,您也可以退出。除非对适应性公式非常了解(在这种情形下,无论如何,您都可能不再需要遗传算法了),设定适应性目标的结果,或者是导致无穷循环,或者是得到一个仅仅是“足够好”的个体。第三,在迭代了一定的次数或者说经历了一定数目的“代”后,您也可以退出。
在实践中,这三种方式(或者至少是第二种和第三种)都会被用于控制遗传算法。只要经过为数不多的测试,可能是10次,也可能是20次,您就会清楚的知道算法汇集需要多长时间,以及您想要的适应性是什么样子的。
一个简单的例子
清单 1 里的代码把一个字节看作是DNA(它的值介于0和255之间,8位)。对每个新个体应用适应性公式一次,用表示DNA的字节所具有的数值,去除以256。这样适应性公式总是会返回一个介于0和255/256之间的数值,因此,它永远也不会等于1。那么,您认为最适应的DNA应当是多少呢?
清单1.繁殖字节以测试其适应性
numbers.pl source
清单1里有几件非常有趣的事情。它的主循环位于程序的开始部分,您应当弄懂所有的程序片,以及它们是如何共同作用于人群的(既然这些部分是相互独立的,因此我们还可以在下面的例子中重复使用)。您可以运行清单1,程序文件为numbers.pl。
通过把map()堆栈到grep()的上部,我们在select_parents()函数里建立了weights数组。虽然我们本来可以把它写成循环,但是长度只有一行的解决方案要清楚得多,并且不会显著降低程序运行的速度。
清单2.map和grep堆栈
my @weights = map { $_->{fitness} } grep { $_->{survived} } @$population;
$population数组引用是间接引用。那么,只有带“survived”域的数组元素(在前面由survive()函数设定的)通过grep。然后这些幸存者被蒸馏成代表其适应性的数字,并存入weights数组里该幸存者所对应的位置。
取大小为256的人群,原因是这样便于把个体都初始化成一个与其序号相等的数字。您可以自由选择不同的人群大小开始。
大于1%的变异率使得适应性的最大值和最小值剧烈波动。人群绝不可能稳定在高适应性。变异率低导致了需要更多的时间人群才能整体上达到高适应性。最后,对于我们讨论的人群大小而言,1%恰好合适。
繁衍选择算法会查找weights数组,选择第一个双亲 — 其实,每个个体都有可能成为双亲,但是双亲位置的数目是确定的。另一个双亲是随机地从双亲人群中挑选的。为什么呢?噢,本来我们可以在weights数组里把另外一个双亲也确定下来,但是,这样我们可以确保每个可以成为双亲的个体都有可能参与繁衍过程。