邓世龙的自留地

兼济天下则达 独善其身则穷

遗传算法和busy-beaver


问题描述:设计一个只有五个状态(外加一个终止状态)和两个字符集的图灵机,要求能够停机,并且状态转移后要求向左走或向右走,使图灵机走的步数尽可能的多。在这里看到busy beaver问题,看到博主用遗传算法,于是也想自己动手写程序,生成一个图灵机,因为之前没有学过遗传算法,于是上网找了一下资料,找到一篇介绍遗传算法的很好例子,遗传算法:内存中的进化 .写的挺久的,因为老是出现错误。

  • 第一步是生成合法的初始解,因为生成的规则会进入死循环,所以我设定超过5000步的都丢弃,这里我只生成了500个初始解。
  • 第二步是执行杂交和变异,这里引进500个外来物种进行繁殖。随机选取上一代中的一个规则与外来物种中的一个规则杂交,变异。杂交是交换两个规则的转移函数,变异是对其中一个转移函数进行改变或者添加一个转移函数。之后排序,选取最优的500个为下一代。

跑了三个多小时,得到一些结果,361,1004步。用Python写还是挺好的,就是程序运行的慢了一点。遗传算法很有意思,简单的规则,经过不断演化,能解决问题。

上一次说被Python的缩进弄的头痛,现在终于知道原因了。原来只要将Tab设置为4个空格宽度,并且将Tab改为空格就可以了。之前说要写一个博客系统放在SAE上,现在想想还是放弃了,因为意义不大,现在这个博客挺好的,界面很清爽。