遗传算法在平面魔方游戏中的应用
开篇：润墨网以专业的文秘视角，为您筛选了一篇遗传算法在平面魔方游戏中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要:平面魔方游戏类似于传统魔方、九连环等智力游戏,它具有很高的启智、益智的功能,并且包含了丰富的搜索优化的算法,本文针对游戏规则,提出了一种簇减少的算法思想,并且采用遗传算法来代替传统的搜索算法。最后,通过程序的实现和演示,对算法进行了测试和验证。
1 引言
像魔方、九连环等智力游戏都具有很高的启智、益智的功能,并且包含了丰富的搜索优化的算法,对这些算法的研究具有重要的理论价值和应用价值。平面魔方是一种类似传统魔方的旋转拼图游戏,游戏规则为:
如图1中“初始状态”所示,由带有颜色的区域(这里用数字表示,一个数代表一种颜色)所构成的N*N的矩阵区域。通过不断旋转场地中某些部分的正方形,扩大纵横相连同色的区域,最终达到如图1“完成状态”所示。
每一次旋转,将对n*n(n为正偶数)的区域,以该区域的中心为旋转中心,可以进行90度、180度和270度的旋转。图2便是示例的对4*4的区域进行270度右旋转的样子。
胜负的判定为,在规定的时间内,使得各种颜色的单元格的最大连通数之和最大,在最大连通数之和相同时尽量使旋转次数最少。
该游戏过程中包含一个基本的命题:如何用最少的旋转次数将各种颜色连接到一起。
2 问题分析
根据问题描述,可以知道该问题最终的解有很多,解的步数也不确定。采用搜索算法时,搜索树中的各个节点信息可以用一个数据结构表示:(旋转中心x坐标,旋转中心y坐标,旋转半径,旋转角度)。例如图2中的旋转可以表示为(1,3,2,3),其中(1,3)表示旋转中心的坐标,2表示为旋转半径,3表示270度(1表示90度,2表示180度)。
假设图形由N*N的矩阵区域构成,那么,可以作为旋转中心的点有(N-1)*(N-1)个,旋转半径可以是1到MinDis (旋转中心到四个边界最短距离)中的任意一个,而对于确定中心和半径的每一个旋转来说又有3种旋转角度。可以想象当N的值较大时,图3中的搜索树将非常庞大,本文提出采用遗传算法来代替传统的搜索算法思想,在有限的计算时间和旋转步骤内,使得图形中同种颜色的单元格尽量连通。
3 遗传算法设计
使用遗传算法解决问题时,需要确定适应函数、编码方案、选择策略以及遗传算子等信息的表示。
3.1 适应函数的确定
先来介绍一个概念“簇”,它指的是由上下左右相邻的超过1块同色区域所构成的区域。换言之,“簇”是由1个以上的同色单元格所构成的。同理,在没达到完成状态之前,在图形中将会有多块相同颜色的“簇”。
根据游戏规则,最终的状态就是要达到一个图形中“簇”的数量等于颜色的数目。初始状态到终止状态的过程就是“簇”减少的过程。因此,我们将遗传算法的适应函数设定如下:
F=单元格数-“簇”数
遗传算法就是在规定的旋转次数内找到函数F的最大值,F的理论最大值是单元格数减去颜色数。
3.2 “簇”数的计算
将保存图形的二维数组看作“图”结构,每个单元格看作“图”的一个节点,相同颜色且坐标相邻的节点视为连通。此时,可以通过深度优先的算法遍历“图”中的各个节点,从而确定“簇”数。具体算法如下:
(1)定义计数器count,初始为0,定义存放节点的栈,初始为空;
(2)如果“图”中存在未标记结点,取一个未标记结点放入栈中,计数器增1,否则返回计数器,算法结束;
(3)如果栈为空,返回至第(2)步,否则,从栈顶取出一个节点,并标记当前取到的节点已被访问;
(4)如果当前节点存在未标记的连通节点(相邻且同色),则将所有连通节点放入栈中,返回第(3)步,否则直接返回第(3)步。
3.3 编码方案和种群的初始
对于平面魔方问题,我们采用有序串的编码方案为遗传算法中的个体进行编码。假定个体是长度为L的有序串,对应该问题的一个解,串中的每一个元素对应一次合法的旋转。
上面的两个公式中表示个体,表示第i次旋转是个体的基因,分别表示旋转中心的横纵坐标,分别表示旋转的半径和角度。
通过上述的编码方案,我们将平面魔方问题转换为:在规定的旋转次数内(L次旋转,取决于个体的长度),求“簇”数最少的问题。
我们假定种群大小为M,即种群中有M个个体。因此,初始种群时需要随机产生M*L个旋转,旋转中心都是0到N-2的随机整数(N为图形的边长),旋转半径是1到MinDis (旋转中心到四个边界最短距离)的随机整数,旋转角度是0-2的随机整数(0表示90度,1表示180度,3表示270度,角度以顺时针为方向)。
3.4 选择策略
在选择策略上,本问题采用基于概率的轮转盘选择策略。首先,在产生下一代种群之前,计算出当前每个个体适应函数的值,记为p0,p1…pL-1,并对所有值求和,记为SUM。然后,在产生下一代种群的第i个个体时,在0到SUM-1中产生一个随机整数p,如果p小于p0,则将上一代中的第0个个体作为本轮种群的第i个个体,否则,将p减去p0,继续与p1进行比较……。
通过上述选择策略,我们可以使种群中适应函数值较高的个体遗传到下一代种群当中。
3.5 杂交和变异
杂交组合了两个亲体父体的特征,并通过交换父代相应片断形成两个后代。本文问题中,假定杂交概率为pc(0到1之间的随机小数),为新种群中的每个个体产生一个随机数pci(0到1之间的随机小数),当pci小于pc时,再随机选择另一个体与当前个体杂交。假设个体长度为L,在0到L-1之间产生随机整数q,杂交之前的两个个体为:
变异是一种局部随机搜索,可提高算法的局部搜索能力。本文问题中,假定变异概率为pm(0到1之间的随机小数),为杂交后产生的新个体的每一个基因(旋转)产生一个随机数pmi(0到1之间的随机小数),当pmi小于pm时,则重新随机产生该基因。
3.6 算法的终止条件
本问题中,遗传算法将在满足以下3种条件之一时终止:
(1)存在个体的适应函数F取得理论最大值,此时的“簇”数等于颜色数。
(2)遗传MAX_M代,MAX_M预先设定。
(3)连续遗传MAX_N代,群体中个体的适应函数F的最大值无变化,MAX_N预先设定。
4 算法实现
根据上述分析设计,我们使用Microsoft Visual 6.0作为开发平台,开发了该游戏软件。下面给出遗传算法的伪代码:
初始种群并计算所有个体适应函数值;
初始杂交概率pc,变异概率pm,最大遗传代数等参数;
while(!满足终止条件)
{
for(i:0->个体数-1)
{
使用选择策略产生新种群的第i个个体;
}
for(i:0->个体数-1)
{
产生随机数p;
if(p
{
生成在0到个体数-1之间且不等于i
的随机数j;
杂交个体i和个体j;
for(k:0->个体长度-1)
{
产生随机数q1,q2;
if(q1
变异个体i的第k位上的基因;
if(q2
变异个体j的第k位上的基因;
}
}
}
计算所有个体适应函数值;
}
5 算法测试
运行软件,使用图4中的5*5的图作为测试用例,最大遗传代数为10000,最大不增长代数为1000,种群大小为50,个体长度为6杂交概率0.6,变异概率0.15,在10秒内得到最优解。具体的旋转方法为:(3,1,2,3),(1,2,2,2),(4,4,2,1),(4,1,2,1),(2,1,2,2),(2,3,4,2)。最终状态如图4所示,测试结果经手动测试完全正确。
6 结束语
该问题是日本第20届国际编程大赛的题目,图形的初始情况(图形的大小,颜色数以及各个单元格的初始颜色等)将在比赛前由主办方给出。在此次比赛的准备阶段,我们使用传统的剪枝搜索算法以及本文提出的遗传算法,分别开发了两套比赛程序。经实验验证,在图形较小时(7*7以下),遗传算法在参数设定合理的情况下与剪枝搜索算法的效率相仿,但是遗传算法的各个参数需要提前训练、摸索,特别是个体的长度(旋转的步数),因此,我们认为,在图形较小时应采用剪枝搜索算法。在图形较大时(8*8以上),由于搜索空间过庞大,在有限时间内(5分钟),剪枝搜索算法和遗传算法都不能得到最优解,但是,图形越大遗传算法得到的解越要优于剪枝搜索算法得到的解,因此,我们认为,在图形较大时应采用遗传算法。
参考文献
[1].武苏里,王湘桃等.易阵游戏中两子交换算法的研究[J].计算机应用与软件,2009(2).
[2].刘汝佳,黄亮.算法艺术与信息学竞赛[M].北京:清华大学出版社,2004.
[3].郑宗汉,郑晓明.算法设计与分析[M].北京:清华大学出版社,2005.
[4].金聪,戴上平,等.人工智能教程[M].北京:清华大学出版社,2007.