Skip to content

Instantly share code, notes, and snippets.

@oldj oldj/GA.py
Last active May 16, 2019

Embed
What would you like to do?
py-TSP
# -*- coding: utf-8 -*-
"""GA.py
遗传算法类
"""
import random
from Life import Life
class GA(object):
def __init__(self, x_rate=0.7, mutation_rate=0.005, life_count=50, gene_length=100, judge=lambda lf, av: 1,
save=lambda: 1, mk_life=lambda: None, x_func=None, m_func=None):
self.x_rate = x_rate
self.mutation_rate = mutation_rate
self.mutation_count = 0
self.generation = 0
self.lives = []
self.bounds = 0.0 # 得分总数
self.best = None
self.life_count = life_count
self.gene_length = gene_length
self.__judge = judge
self.save = save
self.mk_life = mk_life # 默认的产生生命的函数
self.x_func = (x_func, self.__x_func)[x_func == None] # 自定义交叉函数
self.m_func = (m_func, self.__m_func)[m_func == None] # 自定义变异函数
for i in range(life_count):
self.lives.append(Life(self, self.mk_life()))
def __x_func(self, p1, p2):
# 默认交叉函数
r = random.randint(0, self.gene_length)
gene = p1.gene[0:r] + p2.gene[r:]
return gene
def __m_func(self, gene):
# 默认突变函数
r = random.randint(0, self.gene_length - 1)
gene = gene[:r] + ("0", "1")[gene[r:r] == "1"] + gene[r + 1:]
return gene
def __bear(self, p1, p2):
# 根据父母 p1, p2 生成一个后代
r = random.random()
if r < self.x_rate:
# 交叉
gene = self.x_func(p1, p2)
else:
gene = p1.gene
r = random.random()
if r < self.mutation_rate:
# 突变
gene = self.m_func(gene)
self.mutation_count += 1
return Life(self, gene)
def __get_one(self):
# 根据得分情况,随机取得一个个体,机率正比于个体的score属性
r = random.uniform(0, self.bounds)
for lf in self.lives:
r -= lf.score;
if r <= 0:
return lf
def __new_child(self):
# 产生新的后代
return self.__bear(self.__get_one(), self.__get_one())
def judge(self, f=lambda lf, av: 1):
# 根据传入的方法 f ,计算每个个体的得分
last_avg = self.bounds / float(self.life_count)
self.bounds = 0.0
self.best = Life(self)
self.best.set_score(-1.0)
for lf in self.lives:
lf.score = f(lf, last_avg)
if lf.score > self.best.score:
self.best = lf
self.bounds += lf.score
def next(self, n=1):
# 演化至下n代
while n > 0:
# self.__getBounds()
self.judge(self.__judge)
new_lives = [Life(self, self.best.gene)]
# self.bestHistory.append(self.best)
while len(new_lives) < self.life_count:
new_lives.append(self.__new_child())
self.lives = new_lives
self.generation += 1
# print("gen: %d, mutation: %d, best: %f" % (self.generation, self.mutationCount, self.best.score))
self.save(self.best, self.generation)
n -= 1
# -*- coding: utf-8 -*-
"""Life.py
生命类
"""
import random
class Life(object):
def __init__(self, env, gene=None):
self.env = env
self.score = 0
if gene is None:
self.__rnd_gene()
elif isinstance(gene, list):
self.gene = []
for k in gene:
self.gene.append(k)
else:
self.gene = gene
def __rnd_gene(self):
self.gene = ""
for i in range(self.env.gene_length):
self.gene += str(random.randint(0, 1))
def set_score(self, v):
self.score = v
def add_score(self, v):
self.score += v
# -*- 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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.