王朝网络
分享
 
 
 

功能丰富的Perl:遗传算法仿真多细胞机体

王朝perl·作者佚名  2008-05-19
宽屏版  字体: |||超大  

我的前两篇关于使用 Perl 实现遗传算法(GA)的文章(参阅 参考资料)讲述的是个体细胞的变异与生命周期,它的适合度(fitness)完全依赖于它们自己的 DNA。本文将介绍如何仿真一个多细胞机体。具体的应用程序将会生成由其复杂性和正确性决定的字谜(letter puzzles)。要获得 GA 的背景知识,您应该去参考先前的两篇文章。

个体细胞是字谜中的字母块(letter tiles)。它们的适合度将取决于它们与所有其他细胞的组合,所以,在应用于上下文之前,细胞 DNA 本身没有意义。而且, DNA 必须较长,但并不复杂。它只是要告诉我们任意一个特定细胞可能会连接到哪些字母,当然,它也会告诉我们这个特定细胞的字母(也可能是一个空块)。

那么,让我们来开始设计!

仿真设计

有两方面基本设计。首先是个体细胞的设计,其次是细胞间交互的设计。我将从个体细胞开始讲起。

本质上,每个细胞都是纵横拼字谜(crossword puzzle)中的一个字母。那将是 DNA 的一个片段。而且, DNA 将决定一个细胞与其他字母的适合程度。这样,对英文纵横字谜来说,“an”和“he”将是合适的组合,而“xz”将不是。这并不是说“xz”不可能出现,而只是说使用它生成的纵横字谜没有多高的价值。我将使用一个词典,这个词典默认位于 GNU/Linux 系统的 /usr/share/dict/words 中(至少在我的 Debian 系统中是这样 ―― 否则,可以使用 whereis 或 locate 命令来找到它,并相应地修改 $words_file)。

细胞之间的交互将发生在一个 N 乘 N 的字谜中,其中 N 在命令行中给定,默认为 10。在任何时刻都会有 N^2 个细胞被选中,留下 N*2 个细胞(所以,在一个 10x10 字谜的循环周期中,总共有 120 个细胞)。这些数字是任意的,不太重要,只不过,一个大的“无限制”的池将使细胞选择的值的适合度降低,而一个小的池将限制元素的机会。

您应该记住,这里的目标不是生成“正确”的解决方案 ―― 没有这样的解决方案。目标是仿真细胞之间的交互,特别要注意平衡字母细胞所需要的空块细胞。

从初始细胞池中对细胞的选择由字母关联性来完成。如果在字谜板(puzzle board)上没有其他细胞,那么任何细胞都是可以的。不过,如果程序正在为一个与“A”和“Q”相邻的块来选择细胞,那么“A”和“Q”的细胞关联性就有关系了。因此,细胞关联性是 DNA 的一个基本部分,和细胞的字母一样受到变异的影响。细胞关联性的范围是 0 到 255,所以可以方便地由 DNA 的一个字节来描述它。

最后,我将缓存细胞所构成的词。我不会采用这种简单的方法:选出每个块并指出它构成哪些词。您想知道为什么吗?因为我试过那种方法,为了得到正确的方法,浪费了好多个小时的时间,而且它并不快!

我的方法是,从左到右,从上到下对谜板进行扫描(两遍,这是为了得到垂直方向和水平方向的词)。当找到一个词后,我会记住构成那个词的细胞,然后将那个词添加到所有那些细胞的词缓存中。词缓存是一个数组,不是散列表,反映出事实上同一个词可以出现在水平方向上,也可以出现在垂直方向上,但细胞只能归于一个这样的词。对于微不足道的细胞来说,那将是极其不公平的。

对于谜板而言,它是一个简单的散列表。我尝试过使用嵌套数组来仿真一个矩阵,不过没有必要那么麻烦。我只需要使用一个具有 x y 键的简单散列表就可以完成仿真。唯一所需要的映射是 xy2index() 函数;我编写了一个名为 index2xy() 的反向映射函数,但是没必要使用它。

与先前文章的不同之处

本文中的程序是我先前撰写的两篇遗传算法文章中 GA 仿真程序的改进版本。基于读者 Matt Neuberg 的建议,以及我本人的经验,我做了一些修改。

select_parents() 是不严格的,因为它将不适合的亲本(parents)留在种群(population)中,即使它们的适合度为 0,不可能被选择。为了纠正那一点,我添加了一个额外的 grep() 调用。

recombine() 函数

我应该提醒您,基于亲本的适合度,亲本种群包含有对亲本的多个引用。亲本越适合,在亲本种群中出现的次数就会多,因而就会有更多机会繁殖下去。

recombine() 使用 List::Util shuffle() 函数来随机组合亲本种群。这样做的效果好于选择随机亲本并保持对哪些已经是亲本的追踪。另外,以前第二个亲本是随机选择出来的,而且我认为这样是对演化的相当准确的描述,但是我改变了那种方法,通过将它们从亲本种群中选择出来然后再插入回去的方式,基于它们的适合度来选择第二个亲本。

清单 1. recombine() 函数

sub recombine

{

my $population = shift @_;

my $pop_size = scalar @$population;# population size

my @parent_population;

my @new_population;

my $total_parent_slots = 0;

$total_parent_slots += $_-{parent}

foreach @$population;

my $position = 0;

foreach my $individual (@$population)

{

foreach my $parenting_opportunity (1 .. $individual-{parent})

{

push @parent_population, $individual;

}

$individual-{parent} = 0;

}

@parent_population = shuffle @parent_population;

while (1)

{

# this could result in a parent breeding with itself, which is not a big deal

my $parent = shift @parent_population;

my $parent2 = shift @parent_population;

my $out_of_parents = 0;

# when we're out of parents...

unless (defined $parent2)

{

$parent2 = $parent;

$out_of_parents = 1;

}

my $child = { survived = 1, parent = 0, fitness = 0, dna = 0 };

# this is breeding!

my $dna1 = $parent-{dna};

my $dna2 = $parent2-{dna};

# note we do operations on BYTES, not BITS.

This is because bytes

# are the unit of information (and preserving them is the faster

# breeding method)

foreach my $byte (1 .. $dna_byte_length)

{

# get one byte from either parent (the parent choice is random) and add it to the child

vec($child-{dna}, $byte-1, 8) = vec(((rand()

}

push @new_population, $child;# the child is now a part of the new generation

push @parent_population, $parent2;# use the second parent again, but at the tail end

last if $out_of_parents;

}

return \@new_population;

}

注意,如果最后一个亲本恰好是自亲本种群中获得的,应该如何去设置 $out_of_parents;那是跳出亲本选择循环的唯一途径。

构建字谜

字谜网格由相应的名为 build_puzzle() 的函数来构建。种群中的每一个个体细胞都在内部存储了一个网格位置,所以,当我想要找到某个细胞的网格位置时,不必搜索网格或者维持一个外部散列表。每一个个体还拥有一个“单词”数组引用,在这个数组中保持有在衍生过程中那个个体生成的单词。

另外,我为每个细胞赋予了一个 ID 属性,不过只是使用它来检查算法的正确性。

在 build_puzzle() 中,所有的个体都安置于 @puzzle_population。我做了一个 @puzzle_population 的拷贝,这样我可以从它里面去删除个体,以使得对个体的改变不会是永久的 ―― 它是一个浅拷贝(shallow copy)。选择块的顺序是随机的,再次使用了 List::Util::shuffle()。注意,所有的位置都存储在一个 [x,y] 数组中。那样,数据可以像单一的参数一样传递,而不是多个参数。

清单 2. build_puzzle() 函数

sub build_puzzle

{

my $population = shift @_;

my @puzzle_population = @$population;# make a local copy we can alter

my $i = 0;

foreach (@puzzle_population)

{

$_-{id} = $i++;

$_-{position} = undef;

$_-{words} = [];

}

my $puzzle = {};

my @positions;

foreach my $row (0 .. $size-1)

{

foreach my $column (0 .. $size-1)

{

push @positions, [$row, $column];

}

}

foreach my $p (shuffle @positions)

{

my $row

= $p-[0];

my $column = $p-[1];

my $cell =

choose_tile(\@puzzle_population, $puzzle, $p);

$cell-{position} = $p;

$puzzle-{xy2index($p)} = $cell;

}

return $puzzle;

}

注意,上面的 recombine() 和 build_puzzle()中,以及程序所有其他位置,都没有类似于 $i 的计数器。由于 Perl 没有内存分配问题,所以对我来说缺陷的最主要来源就是追踪计数器变量的错误(错误的初始化,错误的增量,或者错误的边界)。这并不是说我在编写 Perl 程序的时候出现了很多缺陷,只是我发现计数器变量会增加使用时出现缺陷的可能性。

现在登场的是 choose_tile()。字谜中的每一个网格位置都会调用它来选择一个将成为字谜块的细胞。在为网格

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
>>返回首页<<
推荐阅读
 
 
频道精选
 
静静地坐在废墟上,四周的荒凉一望无际,忽然觉得,凄凉也很美
© 2005- 王朝网络 版权所有