TSP - GitPress.io

Example Python program TSP.py

Modules

import sys
import random
import math
import time
import Tkinter
import threading
from GA import GA

Classes

class MyTSP(object):

Methods

def init(self, root, width=800, height=600, n=32):
def __bind_events(self):
def title(self, s):
def new(self, evt=None):
def distance(self, order):
def mk_life(self):
def f():
def judge(self):
def x_func(self):
def f(lf1, lf2):
def m_func(self):
def f(gene):
def save(self):
def f(lf, gen):
def evolve(self, evt=None):
def line(self, order):
def line2(i1, i2):
def clear(self):
def quite(self, evt):
def stop(self, evt):
def mainloop(self):

Code

Python tkinter example

# -*- coding: utf-8 -*-

"""TSP.py

TSP问题
"""

import sys
import random
import math
import time
import Tkinter
import threading

from GA import GA


class MyTSP(object):
    """TSP"""

    def __init__(self, root, width=800, height=600, n=32):
        self.root = root
        self.width = width
        self.height = height
        self.n = n
        self.canvas = Tkinter.Canvas(
            root,
            width=self.width,
            height=self.height,
            bg="#ffffff",
            xscrollincrement=1,
            yscrollincrement=1
        )
        self.canvas.pack(expand=Tkinter.YES, fill=Tkinter.BOTH)
        self.title("TSP")
        self.__r = 5
        self.__t = None
        self.__lock = threading.RLock()
        self.__running = False
        self.nodes = []
        self.nodes2 = []
        self.ga = None
        self.order = []

        self.__bind_events()
        self.new()

    def __bind_events(self):
        self.root.bind("q", self.quite)
        self.root.bind("n", self.new)
        self.root.bind("e", self.evolve)
        self.root.bind("s", self.stop)

    def title(self, s):
        self.root.title(s)

    def new(self, evt=None):
        self.__lock.acquire()
        self.__running = False
        self.__lock.release()

        self.clear()
        self.nodes = []  # 节点坐标
        self.nodes2 = []  # 节点图片对象
        for i in range(self.n):
            x = random.random() * (self.width - 60) + 30
            y = random.random() * (self.height - 60) + 30
            self.nodes.append((x, y))
            node = self.canvas.create_oval(
                x - self.__r,
                y - self.__r, x + self.__r, y + self.__r,
                fill="#ff0000",
                outline="#000000",
                tags="node",
            )
            self.nodes2.append(node)

        self.ga = GA(
            life_count=50,
            mutation_rate=0.05,
            judge=self.judge(),
            mk_life=self.mk_life(),
            x_func=self.x_func(),
            m_func=self.m_func(),
            save=self.save()
        )
        self.order = range(self.n)
        self.line(self.order)

    def distance(self, order):
        """得到当前顺序下连线总长度"""
        distance = 0
        for i in range(-1, self.n - 1):
            i1, i2 = order[i], order[i + 1]
            p1, p2 = self.nodes[i1], self.nodes[i2]
            distance += math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

        return distance

    def mk_life(self):
        def f():
            lst = [i for i in range(self.n)]
            random.shuffle(lst)
            return lst

        return f

    def judge(self):
        """评估函数"""
        return lambda lf, av=100: 1.0 / self.distance(lf.gene)

    def x_func(self):
        """交叉函数"""

        def f(lf1, lf2):
            p1 = random.randint(0, self.n - 1)
            p2 = random.randint(self.n - 1, self.n)
            g1 = lf2.gene[p1:p2] + lf1.gene
            # g2 = lf1.gene[p1:p2] + lf2.gene
            g11 = []
            for i in g1:
                if i not in g11:
                    g11.append(i)
            return g11

        return f

    def m_func(self):
        """变异函数"""

        def f(gene):
            p1 = random.randint(0, self.n - 2)
            p2 = random.randint(self.n - 2, self.n - 1)
            gene[p1], gene[p2] = gene[p2], gene[p1]
            return gene

        return f

    def save(self):
        def f(lf, gen):
            pass

        return f

    def evolve(self, evt=None):
        self.__lock.acquire()
        self.__running = True
        self.__lock.release()

        while self.__running:
            self.ga.next()
            self.line(self.ga.best.gene)
            self.title("TSP - gen: %d" % self.ga.generation)
            self.canvas.update()

        self.__t = None

    def line(self, order):
        """将节点按 order 顺序连线"""
        self.canvas.delete("line")

        def line2(i1, i2):
            p1, p2 = self.nodes[i1], self.nodes[i2]
            self.canvas.create_line(p1, p2, fill="#000000", tags="line")
            return i2

        reduce(line2, order, order[-1])

    def clear(self):
        for item in self.canvas.find_all():
            self.canvas.delete(item)

    def quite(self, evt):
        self.__lock.acquire()
        self.__running = False
        self.__lock.release()
        sys.exit()

    def stop(self, evt):
        self.__lock.acquire()
        self.__running = False
        self.__lock.release()

    def mainloop(self):
        self.root.mainloop()


if __name__ == "__main__":
    MyTSP(Tkinter.Tk()).mainloop()

Useful Links

Articles: https://python-commandments.org/
Python shell: https://bsdnerds.org/learn-python/
Tutorial: https://pythonprogramminglanguage.com/