本文将介绍遗传算法在Pyamaze模块中的实现。
自主路径规划是一个通过各种算法和技术实现的经典编程问题。它在工业应用、运送包裹、监视方面有多种实际用途，甚至可以在自然灾害中保护人的生命。
本文使用遗传算法（受自然选择进化理论启发的搜索启发式算法）在pyamaze的帮助下构建迷宫和任务的GUI，深入研究这个相同的问题。
遗传算法通过以下步骤解决问题：
1.创建一个随机的染色体种群。 2.使用适应度函数评估最适者。 3.选择父染色体，使用交叉法产生子染色体。 4.在群体中进行突变。 5.重复项目序号2~4直到找到解决方案。。
路径规划
解决迷宫最重要的方面是路径规划。在这个项目中主要使用了两种不同类型的路径，都是针对正方形[n*n]和长方形[m*n]迷宫实施的。路径基本上是由种群中的染色体推导得出的，为此必须首先讨论染色体。路径规划的两种方法是列优先和行优先。
染色体：染色体由一个列表（Python中的列表对象）表示，包含不同的基因。在每个染色体中，列表索引代表列，每个索引的元素值代表行。每个基因代表路径的里程碑。
列优先：对于列优先，路径首先在列中移动，如果列是相同的，则继续在行中移动。
这样，染色体[1 1 3 6 9 9 9 10 5 7 7 7 12 15]可以表示为X，而中间步骤表示为O。
行优先：在行优先中，遵循同样的表述，但路径首先检查行，然后改变列。
这样，染色体[1 1 3 6 9 9 9 10 5 7 7 7 12 15]可以表示为X，而中间步骤表示为O。
遗传算法的功能
现在将集中讨论该程序的实际功能。迷宫是使用Pyamaze模块创建的。遵循遗传算法的路径在网格上移动的代理（或角色）也是使用Pyamaze创建的。
from pyamaze import maze,COLOR,agent
# 创建/加载起点为(1,1)的迷宫和代理
m=maze(row, column)
m.CreateMaze(row, column, theme=COLOR.dark, loopPercent=100)
a=agent(m, x=1, y=1, footprints = True)
# 通过GA创建路径后
m.tracePath({a:path})
m.run()
生成随机的染色体群
此函数使用Python的内置随机模块为迷宫生成随机群体。每个染色体的长度为n-2（第2列）。这样做是因为对于一个m*n大小的网格，迷宫开始于（1,1），结束于（m,n）。但正如稍后看到的，随机突变发生了。为了防止生成的路径出现任何问题，将在需要时使用一个单独的函数（chromosomemaker
）添加这些值。
列表（chromosome
）的实际值在0到m-1之间。函数返回一个完整的染色体种群，以列表的形式实现。
def generate_population(rows, columns, popsize):
for _ in range (0, pop_size):
sublist =[]
sublist= [random.randrange(0,rows) for _ in range(columns - 2)]
population.append(sublist)
return population
染色体的生成方向
此函数的工作原理与上述函数类似，但生成一个数字来决定路径的方向。其中0→列先，1→行先。
def generate_direction():
direction = [random.randrange(2) for _ in range (pop_size)]
return direction
完善染色体
Chromosome maker
为每条染色体添加起点和终点基因，以创建准确的路径。该函数将染色体（不完整）作为输入并返回完整的染色体。
def chromosomemaker(chromosome):
# chromosome --> 要完成的种群中的每个染色体
chromo = []
chromo.append(0)
for gene in chromosome:
chromo.append(gene)
chromo.append(Grid_rows-1)
return chromo
路径评估器
路径评估器函数对每一列产生的路径进行评估，并将包含不可行步骤（导致路径跳过迷宫障碍的动作）、路径中的转弯和每个染色体的路径长度的数据填入三个列表。
该函数的参数是人口、方向和地图迷宫（由Pyamaze模块生成）。
# 用于检查不可行的步骤
for k in range (0,step-1):
row,col = path[k]
if mapmaze[path[k]]['E']==0 and path[k+1]==(row,col+1):
infeas+=0.25
elif mapmaze[path[k]]['W']==0 and path[k+1]==(row,col-1):
infeas+=0.25
elif mapmaze[path[k]]['N']==0 and path[k+1]==(row-1,col):
infeas+=0.25
elif mapmaze[path[k]]['S']==0 and path[k+1]==(row+1,col):
infeas+=0.25
inf.append(infeas)
pathvar1
和pathvar2
函数用于为每条染色体创建路径。pathvar1
为给定的染色体创建路径，列优先（0），而pathvar2
创建路径，行优先（1）。
适应度函数和排序函数
适应度函数计算每个染色体的适应度，由不可行的步骤、转弯和路径长度决定。对inf
、turn
和step
进行归一化处理，并对每个属性用不同的权重进行评估。
这里的归一化是指将数值在0和1之间进行缩放。而不可行的步骤的权重=5，转弯和步骤的权重都是=2。在下面的代码块中，maxinf=群体中最大的不可行步骤，mininf=最小的不可行步骤（取为0，意味着解决方案）。
算法中的排序是根据适合度值进行降序排列的。[最适合（如500）→最不适合（如0）] 。
def fitnessfn(inf, turns, steps):
maxinf, maxturns, maxsteps = max(inf), max(turns), max(steps)
mininf, minturns, minsteps = 0, min(turns), min(steps)
for j in range (0,pop_size):
finf = 1 - ((inf[j] - mininf) / (maxinf - mininf))
fturn = 1 - ((turns[j] - minturns) / (maxturns - minturns))
flength = 1 - ((steps[j] - minsteps) / (maxsteps - minsteps))
fitval = 5 * 100 * finf * ((2 * fturn + 2 * flength) / (2 + 2))
fitness.append(fitval)
return fitness
#Sort function can be used as follows
sortt=[(fitness[i],population[i]) for i in range (0,pop_size)]
sortt.sort(reverse=True)
#then unpack the sortt into seperate list for fitness and population and
#return it.
交叉
交叉是指选择父本1的一部分并与父本2相连接。例如创建两个新的染色体，如下图所示。
算法的交叉点是每个染色体的中点。交叉发生在最适合的染色体之间。这为遗传算法的下一次迭代创造了新的一代。
突变和寻找解决方案
突变是在每个染色体的随机索引处放置一个随机值。这也增加了自然界中存在的突变因素，算法的变异率为50%。
解决方案是通过定位零不可行步骤的染色体来确定的，这种方法优先寻找解决方案，而不是寻找最理想的解决方案。
def mutation(population):
index, val = 0,0
for i in range (0,pop_size,2):
index = random.randint(0,Grid_columns-3)
val = random.randint(0,Grid_rows-1)
population[i].insert(index,val)
return population
def solution(inf):
for i in range(0,pop_size):
if (inf[i]==0.00) :
return i
return 0
解决方案
随机网格中的比较：
下面的图表显示了随机迷宫中算法的成功率是如何变化的。这些网格的数据被收集了100次的迭代。找到解决方案的平均迭代数与成功率的趋势相似。
这表明随机迷宫的继承率是如何随着网格大小的变化而降低的。
随机网格和相同网格之间的比较：
从上图可以看出，如果提供相同的迷宫，程序寻找解决方案的效率要高得多，而在随机网格中，算法有时无法找到一个最佳解决方案。
适应度趋势：
图形是用Python的matplotlib
包绘制的。
推荐书单
《Python神经进化网络实战》
本书详细阐述了与神经进化网络开发相关的基本解决方案，主要包括神经进化方法概述、Python库和环境设置、使用NEAT进行XOR求解器优化、摆杆平衡实验、自主迷宫导航、新颖性搜索优化方法、基于超立方体的NEAT和视觉辨别、ES-HyperNEAT和视网膜问题、协同进化和SAFE方法、深度神经进化等内容。此外，本书还提供了相应的示例、代码，以帮助读者进一步理解相关方案的实现过程。本书适合作为高等院校计算机及相关专业的教材和教学参考书，也可作为相关开发人员的自学教材和参考手册。
购买链接：https://item.jd.com/13208078.html
精彩回顾
长按关注《Python学研大本营》，加入读者群 长按访问【IT今日热榜】，发现每日技术热点
