#!/usr/bin/env python
# coding: utf-8
# In[1]:
import numpy as np
import copy
import random
# 初始种群设置为1000
M0 = 1000
T = 501 #迭代轮次
M = 300 # 种群中个体的个数
#自然选择的概率
prob_of_select = 0.3
number_of_city = 30
prob_of_change = 0.1
prob_of_cross = 0.8
#轮盘赌的概率
retain_rate = 0.3
# 随机生成城市坐标
# In[2]:
pos = []
for i in range(number_of_city):
x = np.random.randint(0,101)
y = np.random.randint(0,101)
# print([x,y])
pos.append([x,y])
# pos = list(set(pos))
# 去掉重复元素
pos2 = []
for i in pos :
if i not in pos2 :
pos2.append(i)
pos2 = np.array(pos2)
pos = copy.copy(pos2)
# 计算城市之间的距离
# In[3]:
distance = []
for i in range(len(pos)):
distance_x = []
for j in range(len(pos)):
if i!=j:
x1,y1 = pos[i]
x2,y2 = pos[j]
dis = np.sqrt((x1-x2)**2+(y1-y2)**2)
distance_x.append(copy.copy(dis))
else:
distance_x.append(0)
# print(len(distance_x))
distance.append(copy.copy(distance_x))
print(distance[0][1])
# In[4]:
import matplotlib.pyplot as plt
plt.plot(pos[:,0],pos[:,1])
pos = pos.tolist()
print(pos)
# **变异算子**
# In[5]:
def change(a):
#简单处理为交换两个城市的顺序
# a = list(a)
n = len(a)
# d1 = random.randint(0,n-1)
# d2 = random.randint(0,n-1)
# # 这种写法也是支持的
# a[d2],a[d1] = a[d1],a[d2]
#复杂一点试试看
d1 = random.randint(0,n-1)
d2 = random.randint(0,n-1)
if d1 > d2:
d1,d2 = d2,d1
while d1 == d2:
d1 = random.randint(0,n-1)
d2 = random.randint(0,n-1)
if d1 > d2:
d1,d2 = d2,d1
tc = a[d1:d2]
# print(tc)
a0 = a.copy()
for i in a:
# print("i",i)
if i in tc:
a0.remove(i)
# print(i)
for i in a:
if i not in a0:
a0.append(i)
return a0
# ### 适应度函数
# 直接所有城市距离求和，再取导数，即为适应度函数(个体打分)
# In[6]:
def total_distance(x):
dist=0
for i in range(len(x)):
if i==len(x)-1:
dist += distance[0][x[i]]
else:
dist += distance[x[i]][x[i+1]]
return dist
# ### 选择算子
# ##### 轮盘赌
# 这一部分实在写不了了，细节太多了，我选择放弃。
# 这一部分浪费了我大量的时间，也是太久没编程了\
# Selection=0\
# Probability_Total=0\
# m = random.random()\
# 这一部分每次都要初始化！！！
# In[7]:
def lunpandu(P0,P0_prob,M0=M):
P1 = []
#轮盘赌
for i in range(M0):
Selection=0
Probability_Total=0
m = random.random()
for j in range(len(P0)):
Probability_Total=Probability_Total+P0_prob[j]
if(Probability_Total>=m):
Selection=j
break
try :
P1.append(P0[Selection])
except Exception:
print("len P0",len(P0))
print("Selection",Selection)
return P1
# In[8]:
def select(Parents):
# 记P0为当前这一带，P1为P0产生的子代
# 对总距离从小到大进行排序
graded = [[total_distance(x), x] for x in Parents]
graded = [x[1] for x in sorted(graded)]
# 选出适应性强的个体
retain_length = int(len(graded) * retain_rate)
P1 = graded[:retain_length]
#根据适应度选择弱势个体幸存下来
P0 = graded[retain_length:]
score_P0 = []
for a in P0:
score_P0.append(1/total_distance(a))
P0_prob = []
for i in score_P0:
P0_prob.append(i/sum(score_P0))
# for i in range(len(P0_prob)):
# if random.random() < P0_prob[i]:
# P1.append(P0[i])
P1 += lunpandu(P0,P0_prob,M-retain_length)
# print(len(lunpandu(P0,P0_prob,M-retain_length)))
return P1
# ### 交叉算子
# 产生2个后代
# In[9]:
## Order Crossover (OX)
def cross2(a,b):
d1 = random.randint(0,len(a)-1)
#两个杂交点的太麻烦了，我只设一个交叉点
t1 = copy.copy(a[0:int(d1)])
t2 = copy.copy(b[0:int(d1)])
for i in b:
if i not in t1:
t1.append(copy.copy(i))
for i in a:
if i not in t2:
t2.append(copy.copy(i))
return t1,t2
def cross(parents):
# 用 P_next 贮存下一子代
P_next = []
# 随机杂交，
#生成子代的个数,以此保证种群稳定
target_count=len(parents)
for i in range(target_count):
male_index = random.randint(0, len(parents) - 1)
female_index = random.randint(0, len(parents) - 1)
if male_index != female_index:
# 按概率杂交
if random.random() < prob_of_cross:
x,y = cross2(parents[male_index],parents[male_index])
P_next.append(x)
P_next.append(y)
return P_next
# In[10]:
def score(a):
return 1*100/total_distance(a)
def bestone_of_P(P):
maxx = 0
maxx_i = 0
for i in range(len(P)):
if maxx <= score(P[i]):
maxx = score(P[i])
maxx_i = i
return maxx,maxx_i
# ### 准备就绪，开始迭代！
# In[11]:
# 产生很多字符串，初始种群
a_line = [i for i in range(number_of_city)]
P = []
for i in range(M0):
a_line2 = copy.copy(a_line)
random.shuffle(a_line2)
P.append(a_line2)
P0 = P.copy()
# In[ ]:
# In[12]:
P = P0.copy()
for i in range(T):
# 选择
Parents_select = select(P)
if i%10==0:
print("第",i,"代")
print("父代个数为",len(Parents_select),"个")
print("父代的第一个是",Parents_select[0])
x,y = bestone_of_P(Parents_select)
print("父代最好的是",Parents_select[y])
print("父代最好的得分是", x)
# 交叉
children = cross(Parents_select)
if i%10==0:
print("子代个数为：",len(children))
print("the best one of 子代 is", bestone_of_P(children))
print("="*100)
# 把子代和父代放到一起
children += copy.copy(Parents_select)
# 变异
for i in range(len(children)):
if random.random() < prob_of_change:
children[i] = change(children[i])
P = copy.copy(children)
# In[13]:
_,i = bestone_of_P(P)
a_line = P[i]
x = [pos[i][0] for i in a_line] + [pos[a_line[0]][0]]
y = [pos[i][1] for i in a_line] + [pos[a_line[0]][1]]
plt.plot(x,y)
# In[14]:
_,i = bestone_of_P(P)
a_line = P[i]
x = [pos[i][0] for i in a_line] + [pos[a_line[0]][0]]
y = [pos[i][1] for i in a_line] + [pos[a_line[0]][1]]
plt.plot(x,y)
评论0