巡回セールスマン問題を実装してみた

# 概要
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_())
```

初投稿なので優しい目で見てあげてください。
気が向いたら遺伝的アルゴリズムの解説を載せたいと思います。