创建您自己的达尔文式的繁殖基础
Teodor Zlatanov (tzz@iglou.com)
程序员，Gold Software Systems
2001 年 8 月
遗传编程建立在达尔文适者生存的自然选择法则的基础之上，利用变异和复制来生成算法，该算法可创建不断改进的计算机程序。在本专栏里，您将开始了解用浅显 的术语表述的遗传算法。Ted 给出了几种特定的任务的 Perl 实现，您可以用于广泛的用途。为了示范遗传算法，Ted 繁殖了一些数字和字母，应用 于公式以测试这些数字的适应性，而繁殖的字母则形成了英语单词。
如果您的机器上已经安装了 Perl 5.005 或者更高的版本，您可以运行一下文章中的例子。您的系统最好应该是安装了最近的（2000 年或者更迟 些）主流的 UNIX（Linux，Solaris，BSD），但其它种类的操作系统可能也可以。文中的例子可能可以在更老的版本的 Perl、 UNIX 以及其它操作系统下运行，但是如果不行的话，读者应当把它看作是一次练习来解决。
历史
进入 20 世纪以来，在速度和影响范围方面遗传学的发展只有电子学和计算机科学能与之相比。遗传算法是 20 世纪出现的最令人感兴趣的算法之一，这一说法是恰当的。
遗传算法（以及普遍意义上的进化算法）出现在 20 世纪 60 年代早期，并在计算机科学的确定性和非确定性算法之间占据了一席之位。本质上，遗传算法 具有如同您所希望的那样的确定性，意味着用户可以决定重复次数和结束条件。它模拟达尔文的自然选择，还有变异，把“适应性”（正如适用于个体的公式所决定 的那样）作为主要因素选择生存繁衍和变异的个体。
其它的进化算法试图模拟拉马克的进化论，在他看来，行为是一种生存的机制，可以在两代之间传递，甚至有一些进化程序是出于某种目的而自然出现的。以上这些都不在本文的论述范围之内。
Perl 用于实现遗传算法的主要缺点在于速度慢。由于遗传算法的计算需要，用 C 语言或其它低级的预编译语言来实现效率会更高。本文展示的 Perl 例程不如其 C 语言的等价程序快，但是可以使您明白遗传算法是如何工作的，况且，对于一些问题来说，已经够快了。
那么什么是遗传算法呢？
遗传算法是如此简单，任何人只要用高中时学过的生物术语就可以理解。以一群个体为例，它们都有自己的 DNA。然后衡量每一个个体的适应性（把它看作是适 用于个体的 DNA 的官能来衡量），并且使那些更适应的个体更有可能繁衍。而最不适应的个体将会被灭绝。每个幸存者都会有机会繁衍（重要的是任何幸存者 都可能会繁衍，如果不太适应的话，仅仅是降低了可能性）。合并双亲的 DNA，对合并后的 DNA 应用随机变异以模拟繁衍。理论上说来，新的个体是和双 亲一样适应的，由于变异或增或减会有些微小的变化。然后循环会周而复始。
遗传算法常见问题解答
参阅参考资料中遗传算法常见问题解答的链接部分。该链接还指向一些遗传算法软件，这些软件有的是免费的，有的是商业化的。参阅取自遗传算法常见问题解答的算法 GA。
显然，有许多变化的因素在影响遗传算法，包括人群大小、代（算法的迭代）、合并方法、适应性函数，适应性将如何影响繁衍的可能性，以及发生了多少变异。
该算法也存在一些缺陷。如果把应用于 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
Listing 1. Breeding bytes for fitness 数据挖掘研究院
#!/usr/bin/perl -w
# GA demonstration with numeric DNA (between 0 and 255)
use strict;
use Data::Dumper;
# individuals in the population - no sense making more than DNA can provide for 数据挖掘研究院
my $popsize = 256;
my $mut_rate = 0.01; # the mutation rate
my $min_fitness = 0.1; # the minimum fitness for survival
my $generation_count = 100000; # run for this many generations 数据挖掘研究院
my $generation = 0; # generation counter
my $pop_ref = []; # a reference to a population array
init_population($pop_ref, $popsize);
do
{
evaluate_fitness($pop_ref, &fitness);
# print out a generation summary line
my @sorted_population = sort { $a->{fitness} $b->{fitness} } @$pop_ref;
printf "generation %d: size %d, least fit DNA [%d], most fit DNA [%d]
", 数据挖掘研究院
$generation,
scalar @sorted_population,
$sorted_population[0]->{dna},
$sorted_population[-1]->{dna};
survive($pop_ref, $min_fitness); # select survivors from the population 数据挖掘研究院
select_parents($pop_ref);
$pop_ref = recombine($pop_ref); # recombine() returns a whole new population array reference
# from this point on, we are working with a new generation in $pop_ref
mutate($pop_ref, $mut_rate); # apply mutation to the individuals 数据挖掘研究院
} while ($generation++ < $generation_count); # run until we are out of generations
sub init_population
{
my $population = shift @_;
my $pop_size = shift @_;
# for each individual
foreach my $id (1 .. $pop_size)
{
# insert an anonymous hash reference in the population array with the individual′s data
# the DNA is equal to the individual′s number minus 1 (0-255) 数据挖掘研究院
push @$population, { dna => $id-1, survived => 1, parent => 0, fitness => 0 };
}
}
sub evaluate_fitness
{
my $population = shift @_; 数据挖掘研究院
my $fitness_function = shift @_;
foreach my $individual (@$population)
{
# set the fitness to the result of invoking the fitness function
# on the individual′s DNA
$individual->{fitness} = $fitness_function->($individual->{dna});
}
}
sub survive
{
my $population = shift @_;
my $min_fitness = shift @_;
foreach my $individual (@$population)
{
# set the fitness to the result of invoking the fitness function
# on the individual′s DNA
$individual->{survived} = $individual->{fitness} >= $min_fitness;
# set the fitness to 0 for unfit individuals (so they won′t procreate)
$individual->{fitness} = 0 if $individual->{fitness} < $min_fitness;
}
}
sub select_parents
{
my $population = shift @_;
my $pop_size = scalar @$population; # population size
# create the weights array: select only survivors from the population,
# then use map to have only the fitness come through
my @weights = map { $_->{fitness} } grep { $_->{survived} } @$population;
# if we have less than 2 survivors, we′re in trouble
die "Population size $pop_size is too small" if $pop_size < 2; 数据挖掘研究院
# we need to fill $pop_size parenting slots, to preserve the population size
foreach my $slot (1..$pop_size)
{
my $index = sample(@weights); # we pass a reference to the weights array here
数据挖掘研究院
# do sanity checking on $index
die "Undefined index returned by sample()"
unless defined $index;
die "Invalid index $index returned by sample()"
unless $index >= 0 && $index < $pop_size;
# increase the parenting slots for this population member
$population->[$index]->{parent}++;
}
}
数据挖掘实验室
sub recombine
{
my $population = shift @_;
my $pop_size = scalar @$population; # population size
my @parent_population;
my @new_population;
数据挖掘研究院
my $total_parent_slots = 1;
while ($total_parent_slots)
{
# find out how many parent slots are left
$total_parent_slots = 0;
$total_parent_slots += $_->{parent} foreach @$population; 数据挖掘研究院
last unless $total_parent_slots;
# if we are here, we′re sure we have at least one individual with parent > 0
my $individual = undef; # start with an undefined individual
do 数据挖掘研究院
{
# select a random individual
$individual = $population->[int(rand($pop_size))];
# individual is acceptable only if he can be a parent
undef($individual) unless $individual->{parent};
} while (not defined $individual);
push @parent_population, $individual; # insert the individual in the parent population
$individual->{parent}--; # decrease the parenting slots of the individual by 1
} 数据挖掘研究院
foreach my $parent (@parent_population)
{
# select a random individual from the parent population (parent #2)
my $parent2 = @parent_population[int(rand($pop_size))];
my $child = { survived => 1, parent => 0, fitness => 0 }; 数据挖掘研究院
# this is breeding!
my $bitmask = int(rand(256)); # a random byte between 0 and 255
# swap random bits between parents, according to the bitmask
$child->{dna} = ($parent2->{dna} & $bitmask) | ($parent->{dna} & ~$bitmask);
push @new_population, $child; # the child is now a part of the new generation
}
return @new_population;
}
sub mutate
{
my $population = shift @_;
my $mut_rate = shift @_;
foreach my $individual (@$population)
{
# only mutate individuals if rand() returns more than mut_rate
next if rand > $mut_rate;
# mutate the DNA by and-ing and then or-ing it with two random
# integers between 0 and 255
my $old_dna = $individual->{dna}; 数据挖掘研究院
$individual->{dna} &= int(rand(256));
$individual->{dna} |= int(rand(256));
# print "Mutated $old_dna to ", $individual->{dna}, "
";
}
}
sub fitness
{
my $dna = shift @_;
return $dna/256;
}
# Function to sample from an array of weighted elements
# originally written by Abigail <abigail@foad.org> 数据挖掘研究院
sub sample
{
# get the reference to the weights array
my $weights = shift @_ or return undef;
# internal counting variables
my ($count, $sample);
for (my $i = 0; $i < scalar @$weights; $i ++)
{
$count += $weights->[$i];
$sample = $i if rand $count [$i];
}
数据挖掘研究院
# return an index into the weights array
return $sample;
}
清单 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 数组里把另外一个双亲也确定下来，但是，这样我们可以确保每个可以成为双亲的个体都有可 能参与繁衍过程。
实际上实现繁殖的是一个随机的 8 位位掩码。我们只把这个位掩码和第一个双亲的 DNA（请记住，它只是一个字节）作 AND 运算，并且把位掩码取反后和第二个双亲的 DNA 作 AND 运算。结果，我们可以从一个双亲上随机选择某些位，其余的来自另外一个双亲。
变异是通过对个体的 DNA 和随机生成的 8 位位掩码作 AND 和 OR 运算实现的。
对了，顺便说一下，最适应的 DNA 当然是 255。您并不需要等待 100,000 代。当您只是在欣赏状态行时，请按 Ctrl-C 结束。
繁殖单词
在这个例子里，我们用的 DNA 是 32 位（5 个字节）的。每个字节代表一个字母或者一个空格。我们本来可以在一个字节中包含更多的信息，但是这样 可能会使这个例子的本意变得模糊。每一字节的值（介于 0-255 之间的数值）可能对应 A 到 Z 之间的一个字母（如果它的值在 65 到 90 之间，便于选择同 ASCII 码集相匹配），或者也可能是一个空格（如果数值介于 0 到 64 之间，或 91 到 255 之间的话）。
请关注一下下面的这个例子和清单 1 的例子的相似之处。dictionary 的单词跟在程序的后面。
清单 3. 繁殖单词
words.pl source
Listing 3. Breeding words
#!/usr/bin/perl -w
# GA demonstration with word DNA (512 bits) 数据挖掘研究院
use strict;
use Data::Dumper;
# individuals in the population
my $popsize = 1024; # a good starting point
my $dna_length = 512; # 4 "letters" in the DNA
my $dna_byte_length = $dna_length / 8; # the DNA byte length
my $mut_rate = 0.01; # the mutation rate
my $min_fitness = 0.1; # the minimum fitness for survival
my $generation_count = 100000; # run for this many generations
my $generation = 0; # generation counter
my $pop_ref = []; # a reference to a population array
init_population($pop_ref, $popsize);
do
{
evaluate_fitness($pop_ref, &fitness);
# print out a generation summary line
my @sorted_population = sort { $a->{fitness} $b->{fitness} } @$pop_ref;
printf "generation %d: size %dnleast fit DNA [%s]/%d
most fit DNA [%s]/%d
",
$generation,
scalar @sorted_population,
dna_to_words($sorted_population[0]->{dna}),
$sorted_population[0]->{fitness},
dna_to_words($sorted_population[-1]->{dna}),
$sorted_population[-1]->{fitness};
survive($pop_ref, $min_fitness); # select survivors from the population
select_parents($pop_ref);
$pop_ref = recombine($pop_ref); # recombine() returns a whole new population array reference
# from this point on, we are working with a new generation in $pop_ref
mutate($pop_ref, $mut_rate); # apply mutation to the individuals
} while ($generation++ < $generation_count); # run until we are out of generations
sub init_population
{
my $population = shift @_;
最新评论共有 0 位网友发表了评论
查看所有评论
发表评论
热点关注
