[PYTHON] I tried to implement the traveling salesman problem

Overview

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)

Implementation in 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-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

I tried to implement the traveling salesman problem
Python: I tried the traveling salesman problem
I tried paiza's campaign problem. (Traveling salesman problem)
I tried to implement PCANet
About the traveling salesman problem
I tried to implement StarGAN (1)
I tried to solve the problem with Python Vol.1
I tried to implement Deep VQE
About the Ordered Traveling Salesman Problem
I tried to implement hierarchical clustering
I tried to implement Realness GAN
I tried to move the ball
I tried to estimate the interval.
I tried to implement the mail sending function in Python
I tried to implement PLSA in Python
I tried to implement Autoencoder with TensorFlow
I tried to summarize the umask command
I tried to implement permutation in Python
I tried to recognize the wake word
I tried to implement PLSA in Python 2
I tried to summarize the graphical modeling.
I tried to implement ADALINE in Python
I tried to estimate the pi stochastically
I tried to touch the COTOHA API
I tried to implement PPO in Python
I tried to implement CVAE with PyTorch
Solve the traveling salesman problem with OR-Tools
I tried to solve the shift scheduling problem by various methods
I tried web scraping to analyze the lyrics.
I tried to implement reading Dataset with PyTorch
I tried to optimize while drying the laundry
I tried to express sadness and joy with the stable marriage problem.
I tried to save the data with discord
I tried to touch the API of ebay
I tried to correct the keystone of the image
I tried to debug.
I tried to implement TOPIC MODEL in Python
I tried to paste
Qiita Job I tried to analyze the job offer
LeetCode I tried to summarize the simple ones
I tried to predict the price of ETF
I tried to vectorize the lyrics of Hinatazaka46!
Try to solve the traveling salesman problem with a genetic algorithm (Python code)
I tried to learn the sin function with chainer
I tried to graph the packages installed in Python
I tried to implement multivariate statistical process management (MSPC)
I tried to detect the iris from the camera image
I tried to implement and learn DCGAN with PyTorch
I tried to summarize the basic form of GPLVM
I tried to implement Minesweeper on terminal with python
I tried to touch the CSV file with Python
I tried to predict the J-League match (data analysis)
I tried to solve the soma cube with python
I tried to implement a recommendation system (content-based filtering)
I tried to implement Dragon Quest poker in Python
I tried to implement an artificial perceptron with python
I tried to implement time series prediction with GBDT
I tried to put pytest into the actual battle
[Python] I tried to graph the top 10 eyeshadow rankings
I tried to erase the negative part of Meros
I tried to simulate the dollar cost averaging method