使用演化算法玩pacman吃豆人

一、实现演化算法的关键步骤

1.1 演化算法玩 Pacman 的整体流程

首先由 registerInitialState 函数进行第一次 getActions，将第一轮的动作序列存入 self.actions。

python def registerInitialState(self, state): """ This is the first time that the agent sees the layout of the game board. Here, we choose a path to the goal. In this phase, the agent should compute the path to the goal and store it in a local variable. All of the work is done in this method! state: a GameState object (pacman.py) """ problem = self.searchType(state) # Makes a new search problem self.actions = self.getActions(problem) # Find a path

之后则调用参数为 state 的 getAction 函数，对它进行了修改使之能够在 self.actions 执行完时调用参数为 problem 的 getAction 函数更新新的动作序列，若新的动作序列为空，则到达目标，不需再执行。

参数为 problem 的 getAction 函数是演化算法的主函数，依次进行了类变量的初始化、种群的初始化、迭代 T 轮、选取 fitness 最低（这里最低为最优）的解的动作序列。每轮迭代内依次进行了父辈选择、交叉生成子代、获取子代的 fitness，直到产生了指定数量的后代，进行生存选择。

c++ def getActions(self, problem): ''' The main iteration in Evolutionary algorithms. You can use getFitness, generateLegalActions, mutation, crossover and other function to evolve the population. : param problem: : return: the best individual in the population ''' self.problem = problem self.population = None self.generateLegalActions() for i in range(0, self.T): offspringList = [] for j in range(0, int(self.offspringNum / 2)): parent1, parent2 = self.selectParents() offspring1, offspring2 = self.crossover(parent1, parent2) offspring1 = self.mutation(offspring1) offspring2 = self.mutation(offspring2) score1 = self.getFitness(offspring1[self.actionDim][0]) score2 = self.getFitness(offspring2[self.actionDim][0]) offspringList.append([offspring1, score1]) offspringList.append([offspring2, score2]) self.population = sorted(self.population, key=lambda x: x[1]) [:self.popSize - self.offspringNum] self.population = self.population + offspringList actions = [] self.population = sorted(self.population, key=lambda x: x[1]) for i in range(1, self.actionDim + 1): actions.append(self.population[0][0][i][1]) if self.population[0][0][self.actionDim][0] in positionDict.keys(): positionDict[self.population[0][0][self.actionDim][0]] += 1 else: positionDict[self.population[0][0][self.actionDim][0]] = 1 return actions

1.2 解的表示和合法解的生成

解的表示包含在一个长度为 actionDim+1 的数组里。数组元素为一个列表，列表的 0 号位为执行当前动作后的位置和执行的当前动作组成的列表，1 号位为该位置对应的 fitness。数组 0 号位置存储当前演化算法的初始状态，后面依次为 actionDim 步。数组的 1 到 actionDim 号位的动作序列即为最后执行的动作序列。合法解的生成主要由下面两个函数保证。其中 generateLegalActions 函数是种群初始化时使用的，其使用 self.problem.getSuccessors 函数获取当前状态可选的动作，再随机选取其中的一个动作，保证每一步获取的动作都是合法的。checkValid 函数则是保证突变和交叉后的解合法，其从第一个突变点/交叉点开始，基于前一步所到达的位置对后续的动作序列合法性进行检验，对于合法的动作，不改变动作，只更新位置；对于不合法的动作，则随机选取一个可选动作，并同时更新动作和位置，以保证最后得到的解合法。

1.3 评估函数设计

对每个解进行评估，使用解的最后一个动作执行后到达的状态进行评估，一开始使用的曼哈顿距离，但容易陷入局部最优，即在离目标比较近但隔着墙的地方打转，为避免这种情况，我新增了一个positionDict 字典，对每次使用演化算法后最后到达的位置进行计数，作为最终位置的次数对 fitness 影响的放大倍率乘以最后到达的位置之前作为最终位置的次数，再加上曼哈顿距离，得到 fitness，当然， fitness 越低越优。除此之外，如果不利用 A 算法，很难想到其他有效的 fitness 计算方法可以绕开局部最优，但感觉如果使用 A 算法就没有使用演化算法的必要了。

1.4 演化算子设计

突变使用 bit-wise，若该位发生突变，则在剩下的可选动作中随机选取一个。（若该状态只有原先的一个动作可选，则不变）

python def mutation(self, individual): first = 0 for i in range(1, self.actionDim + 1): if random.random() < self.mutateProb: successors = self.problem.getSuccessors(individual[i - 1][0]) otherAction = [] for j in range(0, len(successors)): if successors[j][1] != individual[i][1]: otherAction.append([successors[j][0], successors[j][1]]) if len(otherAction) != 0: next = random.choice(otherAction) individual[i] = [next[0], next[1]] if first == 0: first = i if first == 0: return individual else: return self.checkValid(individual, first + 1)

交叉使用单点交叉。

c++ def crossover(self, parent1, parent2): crossPoint = random.randint(2, len(parent1[0]) - 1) offspring1 = parent1[0][:crossPoint] + parent2[0][crossPoint:] offspring2 = parent2[0][:crossPoint] + parent1[0][crossPoint:] return self.checkValid(offspring1, crossPoint), self.checkValid(offspring2, crossPoint)

父辈选择使用轮盘赌法，fitness 越小，被选中的概率越大。

c++ if self.population[0][1] != 0: for i in range(0, self.popSize): sumFitness += 1.0 / self.population[i][1] for _ in range(0, 2): temp = 0 randomNum = random.uniform(0, sumFitness) for i in range(self.popSize - 1, -1, -1): temp += 1.0 / self.population[i][1] if randomNum <= temp: choosen.append(self.population[i]) break else: for i in range(0, self.popSize): sumFitness += 1.0 / (self.population[i][1] + 1) for _ in range(0, 2): temp = 0 randomNum = random.uniform(0, sumFitness) for i in range(self.popSize - 1, -1, -1): temp += 1.0 / (self.population[i][1] + 1) if randomNum <= temp: choosen.append(self.population[i]) break return choosen[0], choosen[1]

生存选择使用精英策略，优先保留 fitness 低的。但这样容易导致陷入局部最优，考虑修改为优先保留新的。

二、实验效果

2.1 具体参数设定以及使用评估函数的次数及分数

2.1.1 smallMaze

动作序列长度 actionDim=20，迭代轮数 T = 100，种群大小 popSize = 100，每位的突变概率 mutateProb = 0.2，每轮产生的后代数量 offspringNum = 20，作为最终位置的次数对 fitness 影响的放大倍率 times = 10。

运行了五次，结果如下

2.1.2 openMaze

动作序列长度 actionDim=30，迭代轮数 T = 200，种群大小 popSize = 200，每位的突变概率 mutateProb = 0.2，每轮产生的后代数量 offspringNum = 40，作为最终位置的次数对 fitness 影响的放大倍率 times = 20。

运行了五次，结果如下

运行时可发现可以很好的跳出局部最优。

2.1.3 bigMaze

动作序列长度 actionDim=10，迭代轮数 T = 100，种群大小 popSize = 100，每位的突变概率 mutateProb = 0.2，每轮产生的后代数量 offspringNum = 20，作为最终位置的次数对 fitness 影响的放大倍率 times = 50。

运行了五次，结果如下

针对这种局部最优特别多的迷宫型地图，只能降低每次演化算法的计算负担，让它在较短的时间内在局部最优附近徘徊，并将他们作为最后位置的数量刷上去，这样才能尽快跳出，故按照这个理念设置了参数。但在实际运行时，虽然能够跳出局部最优，但算法仍然难以将正确路径和断头路区分开，实际运行下来仍然需要花费大量时间。

任务二

这个任务要求你在 Search 和 Classic 环境中测试你在任务一中实现的演化算法，具体测试地图：

Search1、 Search2 、 Search3；

minimaxClassic、originalClassic、powerClassic。

三、测试结果

由于此前演化算法的启发式函数是基于找出口而设计的，在找食物的环境中表现其实比较一般。

3.1 Search1

动作序列长度 actionDim=5，迭代轮数 T = 50，种群大小 popSize = 50，每位的突变概率 mutateProb =0.2

，每轮产生的后代数量 offspringNum = 10，作为最终位置的次数对 fitness 影响的放大倍率 times =50

运行了五次，结果如下

因为这个地图很小，其实动作序列不需要很长，由于动作序列短，种群的大小、迭代次数、每次迭代的后代数都可以相应减少，放大倍率可以设置的大一些，以偏向于探索未访问的地方，更快吃到食物而不是在原先问题的目标附近徘徊。

3.2 Search2

动作序列长度 actionDim=5，迭代轮数 T = 50，种群大小 popSize = 50，每位的突变概率 mutateProb =0.2

每轮产生的后代数量 offspringNum = 10，作为最终位置的次数对 fitness 影响的放大倍率 times =100

运行了五次，结果如下

地图变大了，放大倍率可以再设置的大一些，以偏向于探索未访问的地方，更快吃到食物而不是在原先问题的目标附近徘徊。

3.3 Search3

动作序列长度 actionDim=10，迭代轮数 T = 20，种群大小 popSize = 20，每位的突变概率 mutateProb =0.2

，每轮产生的后代数量 offspringNum = 10，作为最终位置的次数对 fitness 影响的放大倍率 times =150

运行了五次，结果如下

地图又变大了，同样放大倍率可以再设置的大一些，同时可以也适当增大一下动作序列长度，并减少迭代轮数和种群大小，以使解不容易偏向向原先问题的目标聚集。

3.4 minimaxClassic

动作序列长度 actionDim=5，迭代轮数 T = 20，种群大小 popSize = 20，每位的突变概率 mutateProb =0.2

每轮产生的后代数量 offspringNum = 10，作为最终位置的次数对 fitness 影响的放大倍率 times =50

运行了五次，结果如下

地图比较小，故动作序列长度也设置的小一点，但地图太小，精灵的密度太大，启发式函数又没用到食物信息，这种地图该演化算法基本无法获胜。

3.5 originalClassic

动作序列长度 actionDim=10，迭代轮数 T = 20，种群大小 popSize = 20，每位的突变概率 mutateProb =0.2

每轮产生的后代数量 offspringNum = 10，作为最终位置的次数对 fitness 影响的放大倍率 times =150

运行了五次，结果如下

地图比较大，同样采用类似 Search3 的思路设置参数。

3.6 powerClassic

动作序列长度 actionDim=10，迭代轮数 T = 20，种群大小 popSize = 20，每位的突变概率 mutateProb =0.2

每轮产生的后代数量 offspringNum = 10，作为最终位置的次数对 fitness 影响的放大倍率 times =100

运行了五次，结果如下

地图大小中等，故可将放大倍率稍微调小一些，食物密度大，且大食物多，比较适合这个算法。任务三

对所实现的演化算法进行改进，并在任务二中的几个环境中进行测试。

可能的改进方向：

解的表示改进评估函数改进演化算子改进参数优化

四、改进思路

首先是要改进评估函数，即启发式函数的设计，使之能够利用食物、精灵、和大食物位置信息，因为之前的启发式函数实际上是基于固定位置目标设计的，其实并不适用于吃食物和躲避精灵。改进后应使得趋向于食物和大食物的解的 fitness 小（更优），当处于无敌状态时，趋向于精灵的解的 fitness 小（更优），反之，远离精灵的解的 fitness 小（更优），使 fitness 的计算更加准确。

其次可以将生存选择从保留较优的改为保留较年轻的，这样有助于跳出局部最优。

参数优化与场景本身的性质关系比较大，包括地图大小、墙的布局、任务类型等，可以对不同的场景使用不同的参数组合进行多次测试再取平均，找到更适合每个场景的参数组合。

具体改进和改进后的效率 由于时间关系，未能完成改进的实现，故这一部分略过。

参考文献

• 基于深度学习和行为序列的电影推荐系统研究与实现（西南交通大学·程思）
• 基于回溯蚁群的分类规则算法研究（辽宁工程技术大学·王志鹏）
• 主题爬虫关键技术研究（哈尔滨工程大学·黄正德）
• 基于知识图谱的健康膳食知识智能问答系统（兰州大学·王璐）
• 基于J2EE的数据挖掘系统的设计与实现（暨南大学·叶松云）
• 基于SSH框架的电子宠物系统设计与实现（吉林大学·王丽丽）
• 基于知识图谱的健康膳食知识智能问答系统（兰州大学·王璐）
• 基于深度学习和行为序列的电影推荐系统研究与实现（西南交通大学·程思）
• 基于协同过滤的视频推荐系统（山东大学·王雯思）
• 基于标签的专家信息推荐系统的研究（安徽理工大学·陈俊然）
• 基于LDA模型的豆瓣电影推荐算法研究（杭州电子科技大学·陈超）
• 基于进化算法的局部社团结构发现及其在推荐系统上的应用（西安电子科技大学·王朋）
• 基于回溯蚁群的分类规则算法研究（辽宁工程技术大学·王志鹏）
• 基于J2EE的物流软件系统——仓储管理系统的研究与设计（成都理工大学·隋永）
• 多策略自适应差分进化算法的改进与应用研究（兰州理工大学·霍明明）