概要
pythonで巡回セールスマン問題を実装してみました。都市を自由に設置できるようQt4を利用してGUI画面を作成しています。
リアルタイム描写するためにQTimer使っています。
遺伝子は順序表現*にしています。（交叉しても致死遺伝子を持つ子を発生させないため）
*順序表現とは、次に巡回する都市が残りの都市の中で何番目にあるかの番号を遺伝子とし、固定された出発点の都市から順にこれを並べた文字列を染色体とする方法です。
pythonでの実装
traveling_salesman_problem.py
# -*- coding: utf-8 -*-
import sys
from PyQt4.QtCore import *
from PyQt4.QtGui import *
import numpy as np
import random
import math
import time
class TravelingSalesman(QGraphicsItem):
def __init__(self, width=500, height=500):
super(TravelingSalesman, self).__init__()
self.width = width
self.height = height
self.NH = self.height
self.NW = self.width
self.x = np.array([])
self.y = np.array([])
self.champ = np.array([])
self.r = None
def boundingRect(self):
return QRectF(0,0,self.width,self.height)
def mousePressEvent(self, event):
pos = event.pos()
self.x = np.append(self.x, pos.x())
self.y = np.append(self.y, pos.y())
self.update()
def reset(self):
self.x = np.array([])
self.y = np.array([])
self.champ = np.array([])
self.update()
def paint(self, painter, option, widget):
painter.setBrush(Qt.white)
pen = QPen()
pen.setColor(Qt.black)
pen.setWidth(3)
painter.setPen(pen)
for i in range(len(self.x)):
painter.drawPoint(self.x[i], self.y[i])
pen.setColor(Qt.red)
pen.setWidth(1)
painter.setPen(pen)
if self.champ is not None:
if len(self.champ) is not 0:
index = list(np.arange(self.order))
for i in range(self.order - 1):
j = index[self.champ[i]]
del index[self.champ[i]]
k = index[self.champ[i + 1]]
painter.drawLine(self.x[j], self.y[j], self.x[k], self.y[k])
if self.r is not None:
pen.setColor(Qt.blue)
painter.setPen(pen)
if self.r == self.n_change:
text = "finish!!"
else:
text = str(self.r) + "/" + str(self.n_change)
painter.drawText(0, 0, self.width-20, self.height, Qt.AlignLeft, QString(text))
def get_n_change(self):
return self.n_change
def param_init(self, n_gene=30, change_ratio=0.1, n_change=None):
self.n_gene = n_gene
self.order = len(self.x)
self.NumOfMutate = int(self.n_gene * change_ratio)
self.NumOfPopulation = int(self.n_gene / 2) - self.NumOfMutate
self.NumOfSurvival = self.n_gene - 2 * self.NumOfPopulation - self.NumOfMutate
if n_change is None:
self.n_change = self.order * 100
self.r = 0
self.init_genes()
def uniq_matrix(self, a):
b = np.ascontiguousarray(a).view(np.dtype((np.void, a.dtype.itemsize * a.shape[1])))
_, idx = np.unique(b, return_index=True)
return a[idx]
def init_genes(self):
self.genes = np.zeros((self.n_gene, self.order), np.int)
for i in range(self.n_gene):
gene = np.zeros(self.order)
for j in range(self.order):
gene[j] = random.randint(0, self.order - j - 1)
self.genes[i] = gene
self.genes = self.uniq_matrix(self.genes)
self.gene_cost = np.array([self.calc_cost(i) for i in self.genes])
self.genes = self.genes[np.argsort(self.gene_cost)]
self.champ = self.genes[0]
self.min = np.min(self.gene_cost)
self.update()
def step(self):
child = np.zeros((self.n_gene, self.order), np.int)
index_a = 2 * self.NumOfPopulation
index_b = index_a + self.NumOfMutate
index_c = index_b + self.NumOfSurvival
child[0:index_a,:] = self.population(self.NumOfPopulation)
child[index_a:index_b,:] = self.mutate(self.NumOfMutate)
child[index_b:index_c,:] = self.survival(self.NumOfSurvival)
self.genes = child
self.gene_cost = np.array([self.calc_cost(i) for i in self.genes])
self.genes = self.genes[np.argsort(self.gene_cost)]
if self.min > np.min(self.gene_cost):
self.champ = self.genes[0]
self.min = np.min(self.gene_cost)
print self.champ, self.min
self.r = self.r + 1
self.update()
def population(self, num):
child = np.zeros((2 * num, self.order), np.int)
for i in range(num):
p_a_index = self.set_index(random.random())
p_b_index = self.set_index(random.random())
if p_a_index is p_b_index:
while p_a_index is p_b_index:
p_b_index = self.set_index(random.random())
p_a = self.genes[p_a_index]
p_b = self.genes[p_b_index]
a, b = self.region_indexs()
child_a = p_a.copy()
child_a[a:b] = p_b[a:b]
child_b = p_b.copy()
child_b[a:b] = p_a[a:b]
child[i * 2] = child_a
child[i * 2 + 1] = child_b
return child
def mutate(self, num):
child = np.zeros((num, self.order), np.int)
for i in range(num):
index = self.set_index(random.random())
a = self.genes[index]
for j in range(self.order):
if random.random() > 0.5:
a[j] = random.randint(0, self.order - j - 1)
child[i,:] = a
return child
def survival(self, num):
child = np.zeros((num, self.order), np.int)
for i in range(num):
index = self.set_index(random.random())
child[i,:] = self.genes[index]
return child
''' 0-1の入力からルーレット選択で個体のインデックスを返す '''
def set_index(self, rate):
cost_sum = np.sum(1.0 / self.gene_cost)
_sum = 0
index = 0
for i, cost in enumerate(self.gene_cost):
_sum += 1 / (cost_sum * cost)
if rate < _sum:
index = i
break
return index
''' ２点交叉のインデックスを返す '''
def region_indexs(self):
a = random.randint(0, self.order - 1)
b = random.randint(0, self.order - 1)
if a is b:
while a is b:
b = random.randint(0, self.order - 1)
if a > b:
a, b = b, a
return a, b
def calc_cost(self, gene):
index = list(np.arange(self.order))
score = 0
for i in range(self.order - 1):
j = index[gene[i]]
p1 = [self.x[j], self.y[j]]
del index[gene[i]]
j = index[gene[i + 1]]
p2 = [self.x[j], self.y[j]]
score += self.calc_dist(p1, p2)
return score
def calc_dist(self, p1, p2):
return math.sqrt(pow(p1[0] - p2[0], 2) + pow(p1[1] - p2[1], 2))
class MainWindow(QWidget):
def __init__(self, parent=None):
super(MainWindow, self).__init__(parent, Qt.WindowStaysOnTopHint)
self.graphicsView = QGraphicsView()
scene = QGraphicsScene(self.graphicsView)
scene.setSceneRect(0, 0, 800, 400)
self.graphicsView.setScene(scene)
self.TravelingSalesman = TravelingSalesman(800,400)
scene.addItem(self.TravelingSalesman)
""" ボタン """
self.resetButton = QPushButton("&Reset")
self.resetButton.clicked.connect(self.reset)
self.solveButton = QPushButton("&Solve")
self.solveButton.clicked.connect(self.solve)
buttonLayout = QHBoxLayout()
buttonLayout.addWidget(self.resetButton)
buttonLayout.addWidget(self.solveButton)
""" レイアウトマネージャ """
layout = QVBoxLayout()
layout.addWidget(self.graphicsView)
layout.addLayout(buttonLayout)
self.setLayout(layout)
self.setWindowTitle("Traveling Salesman Problem")
self.timer = None
def reset(self):
self.TravelingSalesman.reset()
def solve(self):
self.TravelingSalesman.param_init()
self.n = self.TravelingSalesman.get_n_change()
self.r = 0
self.timer = QTimer()
self.timer.setInterval(10)
self.timer.timeout.connect(self.timeout)
self.timer.start()
def timeout(self):
if self.r < self.n:
self.TravelingSalesman.step()
self.r = self.r + 1
else:
self.timer.stop()
self.timer = None
if __name__ == '__main__':
app = QApplication(sys.argv)
""" Main Window """
w = MainWindow()
w.show()
sys.exit(app.exec_())
初投稿なので優しい目で見てあげてください。
気が向いたら遺伝的アルゴリズムの解説を載せたいと思います。