基于遗传算法的旅⾏商问题
旅⾏商问题（Travelling salesman problem, TSP）:
⼀个商品推销员要去若⼲个城市推销商品，该推销员从⼀个城市出发，需要经过所有城市后，回到出发地。应如何选择⾏进路线，以使总的⾏程最短。
遗传算法（Genetic Algorithm）:
模拟达尔⽂⽣物进化论的⾃然选择和遗传学机理的⽣物进化过程的计算模型，通过模拟⾃然进化过程搜索最优解。遗传算法是从⼀组候选解构成的⼀个种群（population）开始的，初代种群产⽣之后，按照适者⽣存和优胜劣汰的原理，逐代（generation）演化产⽣出越来越好的近似解，在每⼀代，根据问题域中个体的适应度（fitness）⼤⼩选择个体，并借助于的遗传算⼦进⾏组合交叉（crossover）和变异（mutation），产⽣出代表新的解集的种群。这个过程将导致种群按照⾃然进化⼀样产⽣后⽣代种群，并且更适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
如图所⽰，在遗传算法中，⼀共有如下⼏个步骤：
1. 初始化：设置进化代数计数器 t=0、设置最⼤进化代数 T、交叉概率、变 异概率、随机⽣成 M 个个体作为初始种群 P
2. 个体评价：计算种群 P 中各个个体的适应度
3. 选择运算：将选择算⼦作⽤于群体。以个体适应度为基础，选择最优个体 直接遗传到下⼀代或通过配对交叉产⽣新的个体再遗传到下
⼀代
4. 交叉运算：在交叉概率的控制下，对群体中的个体两两进⾏交叉
5. 变异运算：在变异概率的控制下，对群体中的个体两两进⾏变异，即对某 ⼀个体的基因进⾏随机调整
6. 经过选择、交叉、变异运算之后得到下⼀代群体 P’
算法实现(python)
（其中只要运⾏TSP_GA.py即可以运⾏终端的版本，运⾏TSP_GA_app.py为GUI版本）
GA.py遗传算法类
import random
from Life import Life
#遗传算法类
class GA(object):
def __init__(lf, aCrossRate, aMutationRate, aLifeCount, aGeneLength, aMatchFun = lambda life : 1):
def __init__(lf, aCrossRate, aMutationRate, aLifeCount, aGeneLength, aMatchFun = lambda life : 1):
lf.mutationRate = aMutationRate #突变概率
lf.lifeCount = aLifeCount #种群数量，就是每次我们在多少个城市序列⾥筛选，这⾥初始化为100
lf.matchFun = aMatchFun #适配函数
lf.lives = [] #种群
中篇小说lf.best = None #保存这⼀代中最好的个体
lf.mutationCount = 0 #⼀开始还没变异过，所以变异次数是0
lf.bounds = 0.0 #适配值之和，⽤于选择时计算概率
lf.initPopulation() #初始化种群
def initPopulation(lf):
"""初始化种群"""
lf.lives = []
for i in range(lf.lifeCount):
#gene = [0,1,…… ,lf.geneLength-1]
#事实就是0到33
gene = list(Length))
#将0到33序列的所有元素随机排序得到⼀个新的序列
random.shuffle(gene)
#Life这个类就是⼀个基因序列，初始化life的时候，两个参数，⼀个是序列gene，⼀个是这个序列的初始适应度值 #因为适应度值越⼤，越可能被选择，所以⼀开始种群⾥的所有基因都被初始化为-1
life = Life(gene)
#把⽣成的这个基因序列life填进种群集合⾥
lf.lives.append(life)
def judge(lf):
"""评估，计算每⼀个个体的适配值"""
#适配值之和，⽤于选择时计算概率
lf.bounds = 0.0
#假设种群中的第⼀个基因被选中
lf.best = lf.lives[0]
for life in lf.lives:
life.score = lf.matchFun(life)
lf.bounds += life.score
#如果新基因的适配值⼤于原先的best基因，就更新best基因
if lf.best.score < life.score:
lf.best = life
def cross(lf, parent1, parent2):
"""交叉"""
index1 = random.randint(0, lf.geneLength - 1)
index2 = random.randint(index1, lf.geneLength - 1)
tempGene = [index1:index2] #交叉的基因⽚段
123英文怎么写newGene = []
p1len = 0 #记录位置
for g :
if p1len == index1:
p1len += 1
if g not in tempGene:
关于教育的素材
newGene.append(g)
p1len += 1
return newGene
def mutation(lf, gene):
"""突变"""
#相当于取得0到lf.geneLength - 1之间的⼀个数，包括0和lf.geneLength - 1
index1 = random.randint(0, lf.geneLength - 1)
index2 = random.randint(0, lf.geneLength - 1)
#把这两个位置的城市互换
gene[index1], gene[index2] = gene[index2], gene[index1]
gene[index1], gene[index2] = gene[index2], gene[index1] #突变次数加1
lf.mutationCount += 1
return gene
def getOne(lf):
"""选择⼀个个体"""
#产⽣0到（适配值之和）之间的任何⼀个实数
r = random.uniform(0, lf.bounds)
for life in lf.lives:
r -= life.score
if r <= 0:
return life
rai Exception("选择错误", lf.bounds)
def newChild(lf):
"""产⽣新后的"""
#选择
parent1 = lf.getOne()
rate = random.random()
#按概率交叉
if rate < lf.crossRate:
parent2 = lf.getOne()
gene = lf.cross(parent1, parent2)
el:
gene =
#按概率突变
rate = random.random()
if rate < lf.mutationRate:
gene = lf.mutation(gene)
return Life(gene)
def next(lf):
"""产⽣下⼀代"""
lf.judge()#评估，计算每⼀个个体的适配值
newLives = []
newLives.append(lf.best)#把最好的个体加⼊下⼀代
while len(newLives) < lf.lifeCount:
newLives.wChild())
百香果水lf.lives = newLives
Life.py基因序列类
SCORE_NONE = -1
#个体类
class Life(object):
def __init__(lf, aGene = None):
< = aGene
lf.score = SCORE_NONE
TSP.py旅⾏商算法类
深思熟虑什么意思class TSP(object):
def __init__(lf, aLifeCount = 100):
lf.initCitys()
lf.lifeCount = aLifeCount
lf.ga = GA(aCrossRate = 0.7,
aMutationRate = 0.02,
aLifeCount = lf.lifeCount,
aGeneLength = len(lf.citys),
aMatchFun = lf.matchFun())
def initCitys(lf):
lf.citys = []
初中生励志名言#这个⽂件⾥是34个城市的经纬度
f = open("","r")
for line adlines():
line = line.strip()
line = line.split(',')
#中国34城市经纬度读⼊citys
lf.citys.append((float(line[1]),float(line[2]),line[0]))
f.clo()
#order是遍历所有城市的⼀组序列，如[1,2,3,7,6,5,4,8……]
蒸饺怎么做
#distance就是计算这样⾛要⾛多长的路
def distance(lf, order):
distance = 0.0
#i从-1到32,-1是倒数第⼀个
for i in range(-1, len(lf.citys) - 1):
index1, index2 = order[i], order[i + 1]
city1, city2 = lf.citys[index1], lf.citys[index2]
distance += math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)
return distance
#适应度函数，因为我们要从种群中挑选距离最短的，作为最优解，所以（1/距离）最长的就是我们要求的 def matchFun(lf):
return lambda life: 1.0 / lf.)
def run(lf, n = 0):
while n > 0:
()
distance = lf.distance(lf.)
print (("%d : %f") % (ation, distance))
print (lf.)
n -= 1
print("经过%d次迭代，最优解距离为：%f"%(ation, distance))
print("遍历城市顺序为：",)
#print "遍历城市顺序为：", lf.
#打印出我们挑选出的这个序列中
for i in lf.:
print(lf.citys[i][2],)
TSP_GA.py
from TSP import TSP
import tkinter
def main():
tsp = TSP()
tsp.run(500)
if __name__ == '__main__':
main()
TSP_app.py旅⾏商算法类(GUI)
import random
class TSP(object):
def __init__(lf,xuan_citys,aLifeCount = 100):
lf.lifeCount = aLifeCount
lf.xuan_citys = xuan_citys
lf.initCitys()
lf.ga = GA(aCrossRate = 0.7,
aMutationRate = 0.02,
aLifeCount = lf.lifeCount,
aGeneLength = len(lf.citys),
aMatchFun = lf.matchFun())
def initCitys(lf):
lf.citys = []
#这个⽂件⾥是34个城市的经纬度
f = open("","r")
for line adlines():
line = line.strip()
line = line.split(',')
#中国34城市经纬度读⼊citys
lf.citys.append((float(line[1]),float(line[2]),line[0]))
f.clo()
new_node = []
for i in lf.citys:
for j in lf.xuan_citys:
if j in i:
new_node.append(i)
lf.citys = new_node
#order是遍历所有城市的⼀组序列，如[1,2,3,7,6,5,4,8……]
#distance就是计算这样⾛要⾛多长的路
def distance(lf, order):
婴儿14天黄疸值对照表distance = 0.0
#i从-1到32,-1是倒数第⼀个
for i in range(-1, len(lf.citys) - 1):
index1, index2 = order[i], order[i + 1]
city1, city2 = lf.citys[index1], lf.citys[index2]
distance += math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)
return distance
#适应度函数，因为我们要从种群中挑选距离最短的，作为最优解，所以（1/距离）最长的就是我们要求的 def matchFun(lf):
return lambda life: 1.0 / lf.)
def run(lf,n,m):
lis_best =[]
lis_dis = []
ch = []
#随机选取m-1组值
for i in range(m-1):
k = random.randint(1,n)
if k not in ch:
ch.append(k)
while n > 0:
()
distance = lf.distance(lf.)
if n in ch:
lis_best.append(lf.)
lis_dis.append(distance)
if n == 1:
lis_best.append(lf.)
lis_dis.append(distance)
#print (("%d : %f") % (ation, distance))
