Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

概要

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

  ''' 2点交叉のインデックスを返す '''
  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_())

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした