文档章节

游戏编程中的人工智能 二 (Python改编)

crazyskady
 crazyskady
发布于 2017/03/31 16:41
字数 2047
阅读 125
收藏 1

本文改编自Mat Buckland的游戏开发中的人工智能技术中的Chapter 4 解决TSP问题(旅行商问题),C++代码重新用python来实现(本文所有遗传算法相关代码均改编值Mat的C++代码,如有雷同,纯属巧合)。

TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。(从百度拷贝而来)

Mat Buckland选择了围成一圈的城市来进行求解,这样就可以很直观的观察到我们求解的结果是否是所有路径中的最小值,最终结果如下: TSP

#定义城市的位置 城市的定义非常简单,在本例中只需要给出城市在窗口中的x,y坐标即可:

class CoOrd(object):
	def __init__(self, a, b):
		self._x = a
		self._y = b

	def X(self):
		return self._x

	def Y(self):
		return self._y

#定义旅行的地图mapTSP 在定义本算法的地图类时,需要接受3个参数,地图的宽和高,以及城市的数量。在定义了这三个参数之后,我们就可以算出圆形布局的城市在地图上所在的x,y坐标,从而创建出需要旅行的地图:

def __init__(self, mapWidth, mapHeight, numCities):
	self._mapWidth          = mapWidth
	self._mapHeight         = mapHeight
	self._numCities         = numCities
	self._BestPossibleRoute = 0
	self._CityCoOrds        = []
	self.CreateCitiesCircular()
	self.CalculateBestPossibleRoute()
	return

def CreateCitiesCircular(self):
	margin = 40 #if you have GUI, this parameter should be set
	radius = 0
	if self._mapHeight < self._mapWidth:
		radius = (self._mapHeight/2) - margin
	else:
		radius = (self._mapWidth/2) - margin
	origin = CoOrd(self._mapWidth/2, self._mapHeight/2)
	segmentSize = 2 * math.pi / self._numCities
	angle  = 0
	while angle < (2 * math.pi):
		thisCity = CoOrd((radius*math.sin(angle) + origin.X()), (radius * math.cos(angle) + origin.Y()))
		self._CityCoOrds.append(thisCity)
		angle += segmentSize
	return

当然,在该类中我们需要提供计算一条旅行路径的长度的接口GetTourLength,可能会有人很奇怪为什么在该类中我们又直接计算出了最佳路径的长度self._BestPossibleRoute,既然已经知道结果,为什么还要通过遗传算法来多此一举?其实在进化算法过程中,大多情况下是不能知道最优结果的,只是预先设定一个target,然后通过进化算法不断的逼近这个target(或者是达到一定进化代数后终止进化,取当前进化过程中的最优值),我们在这里预先计算出已知的最优结果作为target是为了更好的展示算法的效果。

def CalculateA_to_B(self, city1, city2):
	#print city1, city2
	xDist = city1.X() - city2.X()
	yDist = city1.Y() - city2.Y()
	return math.sqrt(xDist*xDist + yDist*yDist)

def CalculateBestPossibleRoute(self):
	#print "Enter CalculateBestPossibleRoute"
	self._BestPossibleRoute = 0
	for idx, city in enumerate(self._CityCoOrds[:-1]):
		self._BestPossibleRoute += self.CalculateA_to_B(city, self._CityCoOrds[idx+1])
		self._BestPossibleRoute += EPSILON
	self._BestPossibleRoute += self.CalculateA_to_B(self._CityCoOrds[-1], self._CityCoOrds[0])
	return

def BestPossibleRoute(self):
	return self._BestPossibleRoute

def GetTourLength(self, route):
	#print "Enter GetTourLength", route
	TotalDistance = 0
	for idx, city in enumerate(route[:-1]):
		TotalDistance += self.CalculateA_to_B(self._CityCoOrds[city], self._CityCoOrds[route[idx+1]])
	TotalDistance += self.CalculateA_to_B(self._CityCoOrds[route[-1]], self._CityCoOrds[route[0]])
	return TotalDistance

#遗传算法 - Genome 求解该问题的Genome的初始化很简单,即生成一个随机的城市id的序列,按照该序列来进行计算旅行的距离:

class SGenome(object):
	def __init__(self, nc):
		self._Fitness = 0
		self._Cities = self.GrabPermutation(nc)
		return

	def GrabPermutation(self, limit):
		Perm = []
		for i in xrange(limit):
			NextPossibleNumber = random.randint(0, limit-1)
			while NextPossibleNumber in Perm:
				NextPossibleNumber = random.randint(0, limit-1)
			Perm.append(NextPossibleNumber)
		return Perm

	def Show(self):
		print self._Cities

#遗传算法 - 算法描述 gaTSP初始化时接收参数为:mutRate-变异概率,crossRate-交叉概率,popSize-种群大小, numCities-旅行城市数目,mapWidth, mapHeight - 旅行的地图的宽和高。 self._FittestGenome 是最佳的旅行路径在种群中的索引。 self._Generation 是遗传算法进化的代数。 self._ShortestRoute 用于保存最短路径。 self._TotalFitness 用于保存总的适应度用于个体选择。 self._Population 保存当前种群。 self._Map 保存的旅行地图。

class gaTSP(object):
	def __init__(self, mutRate, crossRate, popSize, numCities, mapWidth, mapHeight):
		self._MutationRate = mutRate
		self._CrossoverRate = crossRate
		self._PopSize = popSize
		self._FittestGenome = 0
		self._Generation = 0
		self._ShortestRoute = 9999999999
		self._LongestRoute = 0
		self._ChromoLength = numCities
		self._Busy = False
		self._TotalFitness = 0.0

		self._Population = []

		self._Map = mapTSP(mapWidth, mapHeight, numCities)
		self.CreateStartingPopulation()

		return

种群初始化很简单,生成popSize大小的SGenome并保存到_Population:

def CreateStartingPopulation(self):
	self._Population = []
	for i in xrange(self._PopSize):
		self._Population.append(SGenome(self._ChromoLength))
	self._Generation    = 0
	self._ShortestRoute = 9999999999
	self._FittestGenome = 0
	self._Busy          = False
	return

同上文一样,依然选择轮盘赌的方式来挑选个体:

def RouletteWhellSelection(self):
	fSlice = random.random() * self._TotalFitness
	cfTotal = 0.0
	SelectedGenome = 0
	for i in xrange(self._PopSize):
		cfTotal += self._Population[i]._Fitness
		if cfTotal > fSlice:
			SelectedGenome = i
			break
	return self._Population[SelectedGenome]

变异算子,因为编码方式与上文不同,故变异算子有所差异,这里采用的变异算子称之为交换变异算子(Exchange Mutation Operator),它再染色体上选择两个基因并将其交换:

5,-3-,2,1,7,-4-,0,6

这里我们选中3和4,交换位置后的染色体如下:

5,-4-,2,1,7,-3-,0,6

代码实现如下:

def MutateEM(self, chromo):
	if random.random() > self._MutationRate:
		return chromo
	pos1 = random.randint(0, len(chromo)-1)
	pos2 = pos1
	while pos1 == pos2:
		pos2 = random.randint(0, len(chromo)-1)
	chromo[pos1], chromo[pos2] = chromo[pos2], chromo[pos1]
	return chromo

交叉算子,同样因为编码方式与上文不同,交叉算子要比上文的二进制交叉略为复杂,这里采用的交叉算子称为部分映射交叉(Partially-Mapped Crossover)。 假设8个城市的问题已经用整数编码,两个可能的周游路径为:

2,5,0,3,6,1,4,7
3,4,0,7,2,5,1,6

随机选择两个交叉点,比如第3个和第6个城市之后:

2,5,0, -X- 3,6,1, -X- 4,7
           | | |
3,4,0, -X- 7,2,5, -X- 1,6

记录下选中的两个交叉点中的映射关系,也就是(3--7, 6--2, 1--5),然后再将这个映射关系用到这两个周游路径本身,这样就生成了两个新的周游路径:

6,1,0,7,2,5,4,3
7,4,0,3,6,1,5,2

代码实现如下:

def CrossoverPMX(self, mum, dad):
	if random.random() > self._CrossoverRate or mum == dad:
		return mum, dad
		
	baby1 = copy.deepcopy(mum)
	baby2 = copy.deepcopy(dad)
	beg = random.randint(0, len(mum)-2)
	end = random.randint(beg+1, len(mum)-1)
	for pos in range(beg, end+1):
		gene1 = baby1[pos]
		gene2 = baby2[pos]
		if gene1 != gene2: #每个数字都是应该不重复的
			posGene1 = baby1.index(gene1)
			posGene2 = baby1.index(gene2)
			baby1[posGene1], baby1[posGene2] = baby1[posGene2], baby1[posGene1]
			posGene1 = baby2.index(gene1)
			posGene2 = baby2.index(gene2)
			baby2[posGene1], baby2[posGene2] = baby2[posGene2], baby2[posGene1]
	return baby1, baby2

每次迭代进化的时候都需要进行种群的适应度的计算,更新相关的结果,实现如下:

def CalculatePopulationsFitness(self):
	for i in xrange(self._PopSize):
		TourLength = self._Map.GetTourLength(self._Population[i]._Cities)
		self._Population[i]._Fitness = TourLength
		if TourLength < self._ShortestRoute:
			self._ShortestRoute = TourLength
			self._FittestGenome = i
		if TourLength > self._LongestRoute:
			self._LongestRoute = TourLength
	for i in xrange(self._PopSize):
		self._Population[i]._Fitness = self._LongestRoute - self._Population[i]._Fitness
		self._TotalFitness += self._Population[i]._Fitness
	return

进化,注意我们在每次进化的过程中都保留了最好的两个个体,其余的个体用轮盘赌选择父代后交叉生成子代,当寻找到的最短路径小于预先计算出来的路径的时候,进化终止:

def Epoch(self):
	self.Reset()
	self.CalculatePopulationsFitness()
	if self._ShortestRoute <= self._Map.BestPossibleRoute():
		self._Busy = False
		print "Generation: ", self._Generation, " Find Path: ", self._Population[self._FittestGenome]._Cities
		return
	NewPop = []
	for i in xrange(NUM_BEST_TO_ADD):
		NewPop.append(copy.deepcopy(self._Population[self._FittestGenome]))
	while len(NewPop) < self._PopSize:
		mum = self.RouletteWhellSelection()
		dad = self.RouletteWhellSelection()
		baby1 = SGenome(0)
		baby2 = SGenome(0)
		baby1._Cities, baby2._Cities = self.CrossoverPMX(mum._Cities, dad._Cities)
		baby1._Cities = self.MutateEM(baby1._Cities)
		baby2._Cities = self.MutateEM(baby2._Cities)
		NewPop.append(baby1)
		NewPop.append(baby2)
	self._Population = NewPop
	self._Generation += 1
	return

def Run(self):
	self.CreateStartingPopulation()
	self._Busy = True

def Started(self):
	return self._Busy

def Stop(self):
	self._Busy = False
	return

最后,我们将上面的所以代码整合起来,用pygame来绘图,就达到我们文初所展现的进化效果了。各位看官可自行调整算法参数来查看进化的效果 :)

if __name__ == "__main__":

	WINDOW_WIDTH  = 500
	WINDOW_HEIGHT = 500	
	NUM_CITIES = 20
	CITY_SIZE = 5
	MUTATION_RATE = 0.2
	CROSSOVER_RATE = 0.75
	POP_SIZE = 40	

	#Test Code(self, mutRate, crossRate, popSize, numCities, mapWidth, mapHeight):
	test_gaTSP = gaTSP(MUTATION_RATE, CROSSOVER_RATE, POP_SIZE, NUM_CITIES, WINDOW_WIDTH, WINDOW_HEIGHT)
	test_gaTSP.Run()

	pygame.init()	

	screen = pygame.display.set_mode((WINDOW_WIDTH, WINDOW_HEIGHT), 0, 32)
	font = pygame.font.SysFont("arial", 16)

	while True:
		for event in pygame.event.get():
			if event.type == QUIT:
				exit()

		screen.fill((255, 255, 255))

		for idx, item in enumerate(test_gaTSP._Map._CityCoOrds):
			pygame.draw.circle(screen,[255,0,0],[int(item._x), int(item._y)],5,0)

		if test_gaTSP.Started():
			test_gaTSP.Epoch()

		drawPoints = []
		for idx, item in enumerate(test_gaTSP._Population[test_gaTSP._FittestGenome]._Cities):
			cityPos = test_gaTSP._Map._CityCoOrds[item]
			drawPoints.append([int(cityPos._x), int(cityPos._y)])

		pygame.draw.lines(screen, [0, 255, 0], True, drawPoints, 2)
		generatioinStr = "Generation: " + str(test_gaTSP._Generation)
		screen.blit(font.render(generatioinStr, True, (0, 0, 255)), (20, 20))

		pygame.display.update()

© 著作权归作者所有

crazyskady
粉丝 0
博文 5
码字总数 6747
作品 0
南京
程序员
私信 提问
不学Python迟早会被淘汰?Python真有这么好的前景?

最近几年Python编程语言在国内引起不小的轰动,有超越Java之势,本来在美国这个编程语言就是最火的,应用的非常非常的广泛,而Python的整体语言难度来讲又比Java简单的很多。尤其是在运维的应...

诸葛青云h
04/28
0
0
JavaScript能写一切?Python不服:盘它!

几天前,LinkedIn 领英发布了《2019 年职场十大趋势》,其中第一大趋势,便是人工智能赋能未来。人工智能是领英上数量增长最快的技能之一,近几年增幅达 190%。而人工智能领域并不简单,需要...

AI科技大本营
01/24
0
0
人工智能用Python?高考要加入Python?!Python成为微软官方Excel脚本语言?再不学习就OUT了!

Python适合初学者入门最好的语言 人工智能用Python?高考要加入Python?现在连微软官方Excel都要把Python作为官方语言!Python魅力这么大!小伙伴们知道吗?小编只想说,现在不学Python就OUT...

q1622479435
2018/06/08
0
0
JavaScript 能写一切?Python 不服:盘它!

几天前,LinkedIn 领英发布了《2019 年职场十大趋势》,其中第一大趋势,便是人工智能赋能未来。人工智能是领英上数量增长最快的技能之一,近几年增幅达 190%。而人工智能领域并不简单,需要...

CSDN资讯
01/22
0
0
拿下斯坦福和剑桥双offer,00后的算法学习之路

董文馨,00后,精通英语,西班牙语。斯坦福大学计算机系和剑桥大学双Offer,秋季将进入斯坦福大学学习。 10岁开始在国外上学;12岁学Scratch; 13岁学HTML & CSS; 14岁开始学Python & Java...

AI科技大本营
03/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

3_数组

3_数组

行者终成事
今天
7
0
经典系统设计面试题解析:如何设计TinyURL(二)

原文链接:https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR 编者注:本文以一道经典的系统设计面试题:《如何设计TinyURL》的参考答案和解析为例,帮助...

APEMESH
今天
7
0
使用logstash同步MySQL数据到ES

概述   在生成业务常有将MySQL数据同步到ES的需求,如果需要很高的定制化,往往需要开发同步程序用于处理数据。但没有特殊业务需求,官方提供的logstash就很有优势了。   在使用logstas...

zxiaofan666
今天
10
0
X-MSG-IM-分布式信令跟踪能力

经过一周多的鏖战, X-MSG-IM的分布式信令跟踪能力已基本具备, 特点是: 实时. 只有要RX/TX就会实时产生信令跟踪事件, 先入kafka, 再入influxdb待查. 同时提供实时sub/pub接口. 完备. 可以完整...

dev5
今天
7
0
OpenJDK之CyclicBarrier

OpenJDK8,本人看的是openJDK。以前就看过,只是经常忘记,所以记录下 图1 CyclicBarrier是Doug Lea在JDK1.5中引入的,作用就不详细描述了,主要有如下俩个方法使用: await()方法,如果当前线...

克虏伯
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部