• 精选
  • 会员

遗传算法与可变结构受限生成过程模型

2024年12月25日  来源:涌现 作者:约翰·霍兰德 提供人:It8933......

在最后一个例子中,我将阐述在可变结构受限生成过程模型中嵌入遗传算法所采取的方法。这一嵌入使我们能够从无机的起点出发,来模拟和研究遗传过程的起源。这个特殊例子与后面的讨论没有多少关系。因此,如果读者对遗传算法不感兴趣,完全可以跳过这个例子而不会影响对后面内容的理解。如果读者对此有兴趣而又缺乏遗传算法背景知识,我推荐一本不错的参考书,是梅拉妮·米歇尔1996年出版的《遗传算法入门》(An Introduction to Genetic Algorithms)。

遗传算法使用的运算符号来自遗传学,这种算法可以实现字符串集合,或称为“字符串群体”的进化演变。字符串用来模拟染色体,并为状态和取值编码。例如,可变结构受限生成过程模型中当前状态表的条目就可以作为这样的字符串。

遗传算法的执行分为3个步骤。

1.从群体中挑选并复制字符串。挑选的依据是,选中字符串的某个参数,也就是遗传学上所说的“适应度”,或者是由该字符串定义的机制(s)搜集足够“资源”的能力,以便能够复制字符串自身(隐性适应度)。

2.在染色体复制过程中,一些干扰运算会导致复制的字符串不规范。典型的运算有常见变异运算,比较不常见的运算有交叉和倒置。

3.修改后的字符串被插入群体中,并替换其他字符串,以使群体的规模保持不变。

前面我讨论了在可变结构受限生成过程模型中把机制作为一段程序使用的方法。相同的技术可以用来在可变结构受限生成过程中嵌入遗传算法。我们可以给群体中的元素分配标识,就好像它们存在计算机的寄存器中。随后,通过一些特殊机制的组合,像前面提到的ARITH、NEXT和INSTR,可以编写一段“程序”来执行遗传算法的三个步骤。

虽然这个过程十分简单,但它也为我们揭示了一种至今尚未得到利用的可能性。如果我们退后一步,建立那些能使遗传算法有可能实现的设备(机制),而不是为遗传算法设计一段“程序”,又能有什么用呢?如果使用得当,可变结构受限生成过程模型能够产生不同类型的遗传算法和其他的字符串变化程序。此外,通过设置标识,不同类型以及多种类型混合的字符串变化程序,可以应用于不同的字符串群体。

这种设置使我们能够观察到,这些处理字符串群体的程序如何从以前没有这些程序的系统中涌现出来。像对康威自动机的讨论一样,持续性在这里起到了关键作用。具有不同类型字符串变化算法的不同群体,彼此将会“相互竞争”,这非常类似于康威自动机中的模式。那些字符串变化程序不起作用的群体将不能保持足够的连贯性以持续存在,并且会像康威自动机中未被定义完好的滑翔机一样被分解而消失。而持续存在的群体将进一步影响它们在可变结构受限生成过程模型中的发展变化。

借助这种字符串处理程序中涌现现象的可变结构受限生成过程模型,我们可以研究模型中与遗传学有关的领域出现的极其相似的问题。哪些类型的字符串变化(遗传)运算将会出现?它们怎样为持续性服务?在诸多不同的初始条件下,相同类型的运算是否会出现?一旦我们开始问这些关于模型的问题,也就开始注意到生物学体系的知识,在生物学中寻找类似的现象。模型可以通过一定的“调整”来更加接近现实的观察结果,同时模型的运行也为我们提供了新的观察结果。

如涉及版权,请著作权人与本网站联系,删除或支付费用事宜。

0000