遗传算法之前写过用来求最大值问题的 blog, 不再赘述, 记录一下求解 TSP 问题的代码.
算法很简单, 唯一需要注意的是如何定义问题的表示, 交叉算子, 变异算子以及适应度函数.
水一篇, 上课老师讲的太困了, 边听边写~
问题表示
用一组序列表示访问顺序, 只有三个节点的样本可以用一组序列表示, 如 [2,1,0] 表示先访问二号节点, 然后访问 1 号节点, 最后访问 0 号节点.
所以生成样本直接 np.random.shuffle(np.arange(n))就可以生成样本了.
交叉算子
本问题中涉及两个序列之间的交叉, 比如序列 [2,1,3,4,0] 和序列 [1,2,3,4,0] 在第 0 到第 3 之间的位置进行交叉, 但是直接交换会导致交换后的样本有重复数字, 所以我在设计的时候直接用这些位置的 shuffle.
实质上并没有实现交叉, 但是交叉存在的意义其实是保留两者优秀的基因, 随机选择的位置可能是优秀基因, 也可能不是, 通过交叉可以交换优秀的基因, 我这种操作其实等同于局部变异, 但是是针对优秀父代的局部变异, 同时保留了父代, 如果这种变异不好, 会被淘汰掉的. 虽然设计的不是很好, 但结果上还是 work 的.
变异算子
变异算子比较好实现, 随机选取一个区间, 区间内的序列随机打乱即可.
- Coding
- import numpy as np
- class GA(object):
- def __init__(self,cities,num_iters = 250):
- self.cities = cities
- self.num_iters = num_iters
- init_number = 500
- n = self.cities.shape[0]
- self.weight = np.tile(np.arange(n)[np.newaxis,:],[init_number,1]) # 种群初始化数量为 100 个个体
- for i in range(n):
- np.random.shuffle(self.weight[i])
- self.distance = np.zeros((n,n))
- for i in range(n):
- for j in range(n):
- self.distance[i,j] = np.linalg.norm(self.cities[i] - self.cities[j])
- def solve(self):
- for iter in range(self.num_iters):
- n = self.weight.shape[0]
- w = [self.fitness(self.weight[i]) for i in range(n)]
- print(sum(w) / len(w))
- w/= sum(w)
- probablity = [sum(w[:i+1]) for i in range(len(w))]
- new_x = []
- for _ in range(n):
- p = np.random.random()
- for j in range(n):
- if j ==0:
- if p>=0 and p <= probablity[j]:
- temp = self.weight[j].copy()
- q = np.random.random()
- if q> 0.4:
- self.variation(temp)
- new_x.append(temp)
- break
- else:
- if p>= probablity[j-1] and p <= probablity[j]:
- temp = self.weight[j].copy()
- q = np.random.random()
- if q> 0.4:
- self.variation(temp)
- new_x.append(temp)
- break
- fm = sorted(new_x,key = lambda x:self.fitness(x))[0:2]
- new_x.extend(self.cross(fm[0],fm[1]))
- self.weight = np.array(new_x)
- result = sorted(self.weight.tolist(),key = lambda x:self.fitness(x))[-1]
- print(result,1./self.fitness(result))
- @staticmethod
- def variation(x):
- n = x.shape[0]
- a = np.random.randint(0,n-1)
- b = np.random.randint(0,n-1)
- a,b = (b,a) if b<a else (a,b)
- np.random.shuffle(x[a:b])
- @staticmethod
- def cross(x,y):
- n = x.shape[0]
- a = np.random.randint(0,n-1)
- b = np.random.randint(0,n-1)
- a,b = (b,a) if b<a else (a,b)
- xx = x.copy()
- yy = y.copy()
- np.random.shuffle(xx[a:b])
- np.random.shuffle(yy[a:b])
- #xx[a:b],yy[a:b] = yy[a:b],xx[a:b]
- return [xx,yy]
- def fitness(self,x):
- n = self.cities.shape[0]
- fit = 0.
- for i in range(n):
- j = i+1 if i+1 <n else 0
- fit += self.distance[x[i],x[j]]
- return 1./fit
- if __name__ == "__main__":
- #cities = np.array([[0,0],[0,1],[1,0],[1,1]])
- cities = np.array([[2,6],[2,4],[1,3],[4,6],[5,5],[4,4],[6,4],[3,2]])
- # [2, 1, 0, 3, 5, 4, 6, 7] 16.084259940083065
- solver = GA(cities)
- #print(1./solver.fitness(np.array([1,2,0,3,5,4,6,7]))) # 17.246537600251443
- #solver.solve()
结果
[2, 1, 0, 3, 5, 4, 6, 7] 16.084259940083065
感觉和 hopfield 网络一样, 每次运行其实结果都会不太一样, hopfield 我跑的比较好的一次总距离是 14.714776642118863, 比这个要好一点, 也有跑的比这个差的情况. 跑节点比较少的比如四个节点, 结果是百分百正确, 节点多了可能会有点不稳定.(因为多了我也不知道最小距离是多少了 /)
[学习笔记] GA 解 TSP 问题
来源: http://www.bubuko.com/infodetail-3474904.html