I implemented the traveling salesman problem in python. We are creating a GUI screen using Qt4 so that cities can be set up freely. I use QTimer for real-time rendering. Genes are expressed in order *. (Because it does not generate a child with a lethal gene even if it crosses)
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-Returns the index of the individual by selecting roulette from the input of 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
'''Returns the index of 2-point crossing'''
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)
"""button"""
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 manager"""
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_())
This is the first post, so please take a look with gentle eyes. If you feel like it, I would like to post a commentary on the genetic algorithm.
Recommended Posts