遗传算法解决推箱子问题

算法解决推箱子问题"/>

遗传算法解决推箱子问题

遗传算法

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。最早听说这个算法是在一门公选课上，当时了解的还包括蚁群算法等。总之，这种算法通过模拟自然界物种的繁衍，来寻找适宜生存的种群，达到寻找相对优解的过程。这种方法可以很好的避免我们的算法找到局部最优解之后就停滞不前。

推箱子问题

推箱子相比大家都玩过，在地图上，玩家控制小人把地图上的箱子推到指定的位置。这个问题看似十分简单，但当地图变得十分大，箱子非常多的时候，这个问题实际上并不好解决。本文旨在使用遗传算法，自动求解推箱子问题，虽然从实际效果来看，不甚理想，可改进的地方很多，但是也可看作对遗传算法和数学建模的一次很好的初级实践。

本文推箱子地图的表示参考这个网站：/ 里面推箱子的问题都十分有趣，可以尝试一下。

遗传算法的流程

图片来自超详细的遗传算法解析

下面，我们根据算法流程，逐步求解该问题。

遗传算法求解推箱子问题

（1）编码

我们定义0代表向上，1代表向下，2代表向左，3代表向右。因此给定一个数组，便可确定玩家的所有动作。

（2）推箱子问题环境编程

根据上文关于推箱子地图的定义，@代表玩家，#代表墙，-代表空地，·代表目标点，$代表箱子。为方便起见，目标点我直接通过一个静态数组声明。

----#####----------
----#---#----------
----##--#----------
--###--###---------
--#--#-#-#---------
###################
#-------##----$-.$#
#-------##-$@---.$#
#####---##----$-.$#
--------###########
----#######--------

上面为我们这次测试用的地图（极其简单）。

target_points = [[6, 16], [6, 17], [7, 16], [7, 17], [8, 16], [8, 17]]# 读取推箱子地图
def read_to_matrix():matrix = []f = open("test.txt")line = f.readline()while line:matrix_line = []for char in line:matrix_line.append(char)matrix.append(matrix_line)line = f.readline()np.array(matrix)f.close()return matrix# 寻找玩家位置
def find_person(matrix):for i in range(0, 11):for j in range(0, 19):if matrix[i][j] == '@':return i, jreturn -1, -1# 计算箱子到目标点的最近曼哈顿距离
def calculate_points(matrix):points = 0for i in range(0, 11):for j in range(0, 19):if matrix[i][j] == '$':distances = []for point in target_points:distance = abs(i - point[0]) + abs(j - point[1])distances.append(distance)points = points + min(distances)return points# 移动
def move(matrix, direction):if direction == 0:if up(matrix):return Truereturn Falseelif direction == 1:if down(matrix):return Truereturn Falseelif direction == 2:if left(matrix):return Truereturn Falseelif direction == 3:if right(matrix):return Truereturn Falsedef up(matrix):i, j = find_person(matrix)if i > 0:up_i = i - 1if matrix[up_i][j] == '-' or matrix[up_i][j] == '.':matrix[i][j] = '-'matrix[up_i][j] = '@'return Trueelif matrix[up_i][j] == '#':return Falseelif matrix[up_i][j] == '$':if up_i > 0:box_up = up_i - 1if matrix[box_up][j] == '-' or matrix[box_up][j] == '.':matrix[i][j] = '-'matrix[up_i][j] = '@'matrix[box_up][j] = '$'return Trueelse:return Falseelse:return Falseelse:return Falsedef down(matrix):i, j = find_person(matrix)if i < 10:down_i = i + 1if matrix[down_i][j] == '-' or matrix[down_i][j] == '.':matrix[i][j] = '-'matrix[down_i][j] = '@'return Trueelif matrix[down_i][j] == '#':return Falseelif matrix[down_i][j] == '$':if down_i < 10:box_down = down_i - 1if matrix[box_down][j] == '-' or matrix[box_down][j] == '.':matrix[i][j] = '-'matrix[down_i][j] = '@'matrix[box_down][j] = '$'return Trueelse:return Falseelse:return Falseelse:return Falsedef left(matrix):i, j = find_person(matrix)if j > 0:left_j = j - 1if matrix[i][left_j] == '-' or matrix[i][left_j] == '.':matrix[i][j] = '-'matrix[i][left_j] = '@'return Trueelif matrix[i][left_j] == '#':return Falseelif matrix[i][left_j] == '$':if left_j > 0:box_left = left_j - 1if matrix[i][box_left] == '-' or matrix[i][box_left] == '.':matrix[i][j] = '-'matrix[i][left_j] = '@'matrix[i][box_left] = '$'return Trueelse:return Falseelse:return Falseelse:return Falsedef right(matrix):i, j = find_person(matrix)if j < 18:right_j = j + 1if matrix[i][right_j] == '-' or matrix[i][right_j] == '.':matrix[i][j] = '-'matrix[i][right_j] = '@'return Trueelif matrix[i][right_j] == '#':return Falseelif matrix[i][right_j] == '$':if right_j < 18:box_left = right_j + 1if matrix[i][box_left] == '-' or matrix[i][box_left] == '.':matrix[i][j] = '-'matrix[i][right_j] = '@'matrix[i][box_left] = '$'return Trueelse:return Falseelse:return Falseelse:return False#根据数组移动
def sequence_move(move_array, matrix):for direction in move_array:if move(matrix, direction):continueelse:move_array.remove(direction)return calculate_points(matrix)

（3）确定程序所用参数

change_rate = 0.05        #变异率
expel_rate = 0.5          #淘汰率
initial_length = 10       #初始移动步数
max_length = 50           #最大移动步数
add_step = 10             #每次增加的步长
max_epoch = 2000          #最大迭代次数
sample = 100              #种群数量
mix_length = 3            #基因混合长度
animals = []

（4）初始化种群

class Animal:def __init__(self, move_array, points):self.move_array = move_arrayself.points = points#初始化种群
for i in range(0,sample):change_matrix = read_to_matrix()move_array = []for j in range(0,initial_length):move_array.append(random.randint(0,3))points = sequence_move(move_array,change_matrix )animals.append(Animal(move_array,points))
animals.sort(key=lambda x:x.points,reverse=False)

（5）计算种群适应度

我们定义适应度函数为所有箱子到最近目标点的曼哈顿距离，当该距离为0时，我们可以确定所有的箱子到达目标点，游戏成功。

其实在上述初始化种群的过程中，计算种群适应度已经完成，这个函数上面已经出现过了。函数如下：

# 计算箱子到目标点的最近曼哈顿距离
def calculate_points(matrix):points = 0for i in range(0, 11):for j in range(0, 19):if matrix[i][j] == '$':distances = []for point in target_points:distance = abs(i - point[0]) + abs(j - point[1])distances.append(distance)points = points + min(distances)return points

（6）选择淘汰

这里我们采用最最简单的淘汰办法（其实这样不大好），直接根据淘汰率，选择适应度最差的个体淘汰。

因此排序之后，直接：

animals = animals[0:50]

（7）变异

根据变异率，随机的进行变异，考虑到这是一个不断增长的序列，因此也要有一定几率随机增加染色体的基因。

# 变异
def variation(animals):for animal in animals:if animal.points!=0:for m in range(0,len(animal.move_array)):ret = random.random()if ret<change_rate:animal.move_array[m] = random.randint(0,3)elif ret<2*change_rate and len(animal.move_array)<max_length:animal.move_array.insert(m,random.randint(0,3))return animals

（8）复制

根据mix_length，随机选择父本或母本的基因继承，考虑到这是一个不断增长的序列，在不超过最大序列长度限制的前提下，每次随机在尾部增加几位。

# 复制
def hybridize(parents):child = []father = parents[0]mather = parents[1]i = 0while i < len(father.move_array)-mix_length and i < len(mather.move_array)-mix_length:flag =  random.randint(0,1)if flag == 0:for j in range(0,mix_length):child.append(father.move_array[i+j])else:for j in range(0,mix_length):child.append(mather.move_array[i+j])i = i+mix_lengthif len(child)<max_length:for k in range(0,add_step):child.append(random.randint(0,3))return child

（9）循环往复

#种群迭代
for k in range(0,max_epoch):animals = animals[0:50]animals = variation(animals)    #变异for n in range(0,50):change_matrix = read_to_matrix()# 交配增殖parents = random.sample(animals, 2)child_array = hybridize(parents=parents)points = sequence_move(child_array,change_matrix)animals.append(Animal(child_array,points))animals.sort(key=lambda x: x.points,reverse=False)print(animals[0].points)if animals[0].points==0:print(animals[0].move_array)break

具体代码见我的github:genetic-algorithm

参考

超详细的遗传算法解析

十分钟搞懂遗传算法