J'ai essayé d'implémenter le problème du voyageur de commerce avec python. Nous créons un écran GUI utilisant Qt4 pour que la ville puisse être configurée librement. J'utilise QTimer pour le rendu en temps réel. Les gènes sont exprimés dans l'ordre *. (Parce qu'il ne génère pas de progéniture avec un gène mortel même s'il est croisé)
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-Retourne l'index individuel par sélection de roulette à partir de l'entrée de 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
'''Renvoie l'indice du croisement à 2 points'''
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)
"""bouton"""
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)
"""Gestionnaire de mise en page"""
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_())
Ceci est le premier message, alors jetez un coup d'œil avec des yeux doux. Si vous en avez envie, je voudrais poster un commentaire sur l'algorithme génétique.
Recommended Posts