巡回セールスマン問題(TSP)を遺伝的アルゴリズム(GA)を用いて解くプログラム

TSP_GA.py

#coding:utf-8
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from scipy.spatial import distance as dis

class TSP:
	def __init__(self,path=None,n_gene = 256,n_parent = 10,change_ratio = 0.1):
		""" 初期化を行う関数 """
		self.n_gene = n_gene							# 一世代の遺伝子の個数
		self.n_parent = 10								# 親として残す個体数
		self.change_ratio = change_ratio				# 突然変異で変化させる場所の数
		if path is not None:
			self.set_loc(np.array(pd.read_csv(path)))
	
	def init_genes(self,):
		""" 遺伝子をランダムに初期化 """
		self.genes = np.zeros((self.n_gene,self.n_data),np.int)
		order = np.arange(self.n_data)
		for i in range(self.n_gene):
			np.random.shuffle(order)
			self.genes[i] = order.copy()
		self.sort()
	
	def set_loc(self,locations):
		""" 位置座標を設定する関数 """
		self.loc = locations							# x,y座標
		self.n_data = len(self.loc)						# データ数
		self.dist = dis.squareform(dis.pdist(self.loc))	# 距離の表を作成
		self.init_genes()								# 遺伝子を初期化
	
	def cost(self,order):
		""" 指定された順序のコスト計算関数 """
		return np.sum( [ self.dist[order[i],order[(i+1)%self.n_data]] for i in np.arange(self.n_data) ] )
	
	def plot(self,order=None):
		""" 指定された順序でプロットする関数 """
		
		if order is None:
			plt.plot(self.loc[:,0],self.loc[:,1])
		else:
			plt.plot(self.loc[order,0],self.loc[order,1])
		plt.show()
	
	def solve(self,n_step=1000):
		""" 遺伝的アルゴリズムで解く関数 """
		for i in range(n_step):
			print("Generation ... %d, Cost ... %lf" % (i,self.cost(self.genes[0])))
			self.step()
		self.result = self.genes[0]
		
		return self.result
	
	def step(self):
		""" 遺伝子を一世代分進化させる関数 """
		# 突然変異
		for i in range(self.n_parent,self.n_gene):
			self.genes[i] = self.mutation( np.random.randint(self.n_parent) )
		self.sort() # ソートする

	def sort(self):
		""" 遺伝子を昇順にする関数 """
		# コストを計算し，ソート
		gene_cost = np.array([self.cost(i) for i in self.genes])
		self.genes = self.genes[ np.argsort(gene_cost) ]

	def mutation(self,index):
		""" 突然変異を起こした遺伝子を返す関数 """
		n_change = int(self.change_ratio * self.n_data)
		gene = self.genes[index].copy()
		
		for i in range(n_change):
			# n_changeの個数だけ値を入れ替える
			left = np.random.randint(self.n_data)
			right = np.random.randint(self.n_data)
			
			temp = gene[left]
			gene[left] = gene[right]
			gene[right] = temp
		
		return gene
	
if __name__=="__main__":
	#tsp = TSP(path="input.csv")
	tsp = TSP()
	tsp.set_loc(np.random.random_sample((30,2)))
	tsp.plot()
	tsp.solve()
	tsp.plot(tsp.result)