| Profilo di xin流隙FotoBlogElenchi |  Strumenti  Guida |
|
08 settembre 遗传算法—寻路篇 遗传，生物学中的一个伟大的学科，至今都令我着迷，尤其是那短短几微米的DNA双螺旋结构，居然能编码出N百万种蛋白质，把一个生物体完美的表现出来，而遗传算法是是利用计算机模拟对生物体进行编码，让这些模拟的DNA进行配对杂交，变异，最后模拟自然选择从中挑选优秀个个体再进行配对，杂交，变异，最终这样一代又一代的选择下去，优秀基因个体可以很好的遗传给后代，那些拙略的个体最终被淘汰，最后所有的个体几乎都趋向完美，用在算法里也就是说找到了问题的解。所以说，遗传算法（GA）一种神奇的算法，将人们最终摆脱了只有对人工智能进行硬编码的误区。
幸亏自己从小喜欢生物，以及进化论，所以对遗传算法也是情有独钟，看完游戏编成中的人工智能技术这本书，将里面用遗传算法的寻路写成了j2me的代码，可视的寻路会更有意思。
设计概要：
1.进行对问题的编码（DNA），用两个bit编码4个方向: 00:北 01:南 10:东 11:西 （单个基因）
2.初始化基因组群体（100个），每个基因组含有70个单基因（即70步，比玩家在地图上走到终点的最远距离还长一些）
3.进行世代循环
while（true）{
1.检查这100个基因组，看看他们解决问题的性能怎么样（某个基因走不通，抛弃该基因，进行下一个基因）最终为这100
个基因组每个分别分配一个曼哈顿系数（适应性分数）如果为1，则证明找到出口，跳出循环。
2.用赌轮选择算法从100个基因组中挑出2个作为父母基因（基因组的适应性分数越高被选中的几率越大）进行杂交将其
优秀基因传给下一代
3.对新诞生的基因进行变异（变异率非常的小）变异操作就是0变1 1变0
4.用下一代基因组代替上一代组，即新诞生100个基因组来代替原来100个基因组
}
作为遗传算法去寻路有个问题，就是每次寻路的时间不同，有的经过不到10代就能找到，有的经过100代的子孙都还没有找到路。
改进措施：
1. 初始化基因组是完全随机，没有策略，所以有的时候初始群体会很糟糕。
2.修改适应性分数分配函数，使多次进入同一小格的基因得到惩罚，这样能更有效的找到出口
3. 对于繁殖出的新基因需要进行外部保存，这样下次就能从文明世代向前进化，不必每次都从野人世代开始
4. 遗传算法由于用途太广，太新颖，以至于对某种特定的问题进行求解反而不如针对特定问题而开发的算法效率高（比如A*）
但是遗传算法是人工智能的风水岭，以前的硬编码的算法被隔离开来，计算机能自主编码，向前进化。
J2ME 测试程序（需要用sony的模拟器 WTK2.3 会爆内存）
J2SE 测试程序（ＪＤＫ 1.6）
|
|
|
