1.遺傳演算法簡介
遺傳演算法(GA)是用于解決NP難問題如JSP問題，TSP問題常用的啟發式演算法，上世紀７０年代由美國的John holland提出，是運用計算機仿真，通過交叉變異等方式，模擬自然進化程序搜索最優解的方法，主要特點是對非線性極值問題能以概率 1 跳出區域最優解，找到全域最優解，
2.初始種群的選擇
在求解取值連續的問題時可使用完全隨機的值，但在求解旅行商問題等非連續的問題時通常采用改良圈法，得到一個相對較優的解，然后再利用遺傳演算法得出最優解，
改良圈法基本原理
對于隨機產生的某條路線
C
i
j
=
w
1
w
2
w
3
.
.
.
w
u
?
1
w
u
w
u
+
1
.
.
.
w
v
?
1
w
v
w
v
+
1
.
C_{ij} = w_{1}w_{2}w_{3}...w_{u-1}w_{u}w_{u+1}...w_{v-1}w_{v}w_{v+1}.
Cij?=w1?w2?w3?...wu?1?wu?wu+1?...wv?1?wv?wv+1?.
如果滿足
d
(
w
u
,
w
v
?
1
)
+
d
(
w
u
+
1
,
w
v
)
<
d
(
w
u
,
w
u
+
1
)
+
d
(
w
v
,
w
v
?
1
)
d(w_{u},w_{v-1})+d(w_{u+1},w_{v})<d(w_{u},w_{u+1})+d(w_{v},w_{v-1})
d(wu?,wv?1?)+d(wu+1?,wv?)<d(wu?,wu+1?)+d(wv?,wv?1?)
其中d(x,y)為x,y兩點的間距
原路線修改為
C
i
j
=
w
1
w
2
w
3
.
.
.
w
u
?
1
w
u
w
v
?
1
w
v
?
2
.
.
.
w
u
+
1
w
v
w
v
+
1
.
C_{ij} = w_{1}w_{2}w_{3}...w_{u-1}w_{u}w_{v-1}w_{v-2}...w_{u+1}w_{v}w_{v+1}.
Cij?=w1?w2?w3?...wu?1?wu?wv?1?wv?2?...wu+1?wv?wv+1?.
即u,v之間所有點的順序反轉
改良圈法代碼實作
這部分的代碼以華為面試的蜜蜂采蜜問題為例
即輸入A，B，C，D，E五個點的相對于原點的坐標，得出從原點出發經過這五個點后回傳原點的最小路徑
測驗用例：
輸入：200，0，200，10，200，50，200，30，200，25
輸出：456
import numpy as np
import math
x=[0]
y=[0]
final_list=[]
#計算路徑的長度
def cul_dist(org_rout):
sum=0
for i in range(len(org_rout)-1):
sum+=d[org_rout[i]][org_rout[i+1]]
return sum
#輸入坐標
for i in range(5):
temp_x=int(input("請輸入x坐標"))
temp_y=int(input("請輸入y坐標"))
x.append(temp_x)
y.append(temp_y)
#初始化并得到距離矩陣
d=np.zeros((6,6))
for i in range(6):
for j in range(6):
d[i][j]=math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
#容易陷入區域最優，多次運行確保得到最小值
for i in range(20):
#隨機生成的路線
org_rout=np.random.choice(range(1,6),size=5,replace=False)
#這里是改良圈法的開始
for m in range(6):
#退出條件
flag=0
for j in range(3):
for k in range(j+2,5):
#進行判斷
if d[org_rout[j]][org_rout[k-1]]+d[org_rout[j+1]][org_rout[k]]<d[org_rout[j]][org_rout[j+1]]+d[org_rout[k-1]][org_rout[k]]:
org_rout[j+1:k]=org_rout[k-1:j:-1]
flag=1
#退出
if flag==0:
break
#補上起點終點，便于計算長度
org_rout=np.insert(org_rout,0,0)
org_rout=np.append(org_rout,0)
final_list.append(cul_dist(org_rout))
#得到最小值
print(np.array(final_list).min())
得到結果為456.155，與題目答案一致
PS:這并不是最優的解法，只是恰好可以使用改良圈法
容易發現改良圈法通常只是得到區域最優解，也就引出了我們今天的主題“遺傳演算法”，將其作為遺傳演算法的初始種群，可以大大減少遺傳代數
3.遺傳演算法
包括前面提到的種群選擇，還有建立目標函式，交叉，變異，計算適應度以及選擇等幾大操作，接下來我以一道相對復雜的TSP問題為例，介紹遺傳演算法的使用
問題簡介
A市某輛大貨車要前往三十個點中確定的十四個點送貨，已知其可從任意一點出發出發和各點的位置坐標，求一條最短的路線，使大貨車送完之后仍然回到出發點
編碼與解碼
離散點的問題可采用一串亂數作為編碼，解碼的方式為亂數從小到大排列的下標，例如對于五個點的問題，有編碼[0.22,0.98,0.34,0.42,0.17],對應路徑5-1-3-4-2
對于連續取值的問題，可使用二進制編碼
二進制的編碼和解碼可以參考其他的文章
遺傳演算法詳解 附python代碼實作
構造目標函式
通常由個體解碼后對應值計算得到，本題中為路徑的長度
進行單點交叉
由父本和母本兩個個體繁殖產生新的個體的程序被稱為交叉，子代獲取了部分父本和部分母本的DNA，這個程序中子代繼承了上一代的優良特性，在不斷的交叉和變異中，最終得到問題的最優解
通常選取交叉率為0.8~1之間
具體的操作為，隨機選取一個交叉點，一個子代得到交叉點之前父本的基因和交叉點之后母本的基因，另一個子代得到交叉點之前母本的基因和交叉點之后父本的基因
例如選取父本[0.22,0.98,0.34,0.42,0.17]
母本[0.55,0.32,0.76,0.23,0.01]
選取第二個點之后為交叉點
得到子代分別為[0.22,0.98,0.76,0.23,0.01]和[0.55,0.32,0.34,0.42,0.17]
最后將子代加入群體
隨機進行變異
從序列中隨機選取三個位置u<v<w,位于u,v之間的部分移出并插入w之后
這是實作種群多樣性的手段，也是實作全域最優的保證
計算個體在環境的適應度
為個體在環境中的適應程度，適應度越高代表個體越適合于這個環境，被選擇的幾率也就越大
本題中解碼出路徑越短適應性也就越強，我采用了種群解碼的最大值減去個體解碼的值作為該個體的適應度
選擇個體
為了體現出達爾文“物競天擇，適者生存”的自然選擇法則，我們應該盡可能選擇適應度更高的個體，淘汰掉不適合環境的個體
選擇新的種群時可以進行概率選擇，也可以直接選擇適應度最高的那一部分個體
總的代碼如下：
import numpy as np
import pandas as pd
import math
pop_size=1000
cross_rate=0.95
heter_rate=0.1
generation=50
data=pd.read_csv("經緯坐標.csv")
distance_arr=np.zeros([30,30])
#城市中道路往往呈網格狀，利用坐標差絕對值得到距離矩陣
for i in range(30):
for j in range(30):
distance_arr[i][j]=abs(data.values[i,1]-data.values[j,1])+abs(data.values[i,2]-data.values[j,2])
area=[6,7,8,9,10,21,22,23,24,25,26,27,28,30]
pop_total=[]
#解碼，根據亂數串列回傳對應路徑
def intep(rand_rout):
rand_arg=np.argsort(rand_rout)
point_choiced=[]
for k in rand_arg:
point_choiced.append(area[k])
return point_choiced
#根據路徑計算對應長度
def culc(pop_total):
dist_list=[]
for pot in pop_total:
rout=intep(pot)
dist=distance_arr[rout[len(rout)-1]-1][rout[0]-1]
for i in range(len(rout)-1):
dist+=distance_arr[rout[i]-1][rout[i+1]-1]
dist_list.append(dist)
dist_list=np.array(dist_list)
return (dist_list.max()-dist_list)+1e-4
#交叉操作
def cross(pop_total):
new_pop_total=pop_total.copy()
for father in pop_total:
if np.random.rand() < cross_rate:
#子代c1,c2
c1=[]
c2=[]
choc=math.floor(np.random.rand()*len(pop_total))
mother=pop_total[choc]
cross_p=np.random.randint(low=0, high=14)
c1=father
c1[cross_p:]=mother[cross_p:]
new_pop_total=np.vstack((new_pop_total,c1))
c2=mother
c2[cross_p:]=father[cross_p:]
#插入種群中
new_pop_total=np.vstack((new_pop_total,c2))
return new_pop_total
#變異操作
def heter(pop_total):
for i in pop_total:
if np.random.rand() < cross_rate:
i_c=[]
for ele in i:
i_c.append(ele)
#隨機產生的三個位置
rand_p=np.floor(np.random.rand(3)*14).astype(int)
rand_p=np.sort(rand_p)
temp=i_c[rand_p[0]:rand_p[1]]
del i_c[rand_p[0]:rand_p[1]]
i_c.insert(rand_p[2],temp)
i=i_c
return pop_total
#從種群中挑選下一代的個體
def select(pop_total, fitness):
index = np.argsort(-fitness)
return np.array(pop_total)[index[:pop_size]]
#生成初始種群
for i in range(pop_size):
rand_rout=np.random.rand(14)
point_choiced=intep(rand_rout)
#使用改良圈法
for j in range(len(point_choiced)):
flag=0
for m in range(len(point_choiced)-2):
for n in range(m+2,len(point_choiced)):
if distance_arr[point_choiced[m]-1][point_choiced[n-1]-1]+distance_arr[point_choiced[m+1]-1][point_choiced[n]-1]<distance_arr[point_choiced[m]-1][point_choiced[m+1]-1]+distance_arr[point_choiced[n]-1][point_choiced[n-1]-1]:
rand_rout[m+1:n]=rand_rout[n-1:m:-1]
flag=1
if flag==0:
break
pop_total.append(rand_rout)
pop_total=np.array(pop_total)
for i in range(generation):
pop_total=cross(pop_total)
pop_total=heter(pop_total)
fitness=culc(pop_total)
pop_total=select(pop_total, fitness)
dist_list=[]
for pot in pop_total:
rout=intep(pot)
dist=distance_arr[rout[len(rout)-1]-1][rout[0]-1]
for i in range(len(rout)-1):
dist+=distance_arr[rout[i]-1][rout[i+1]-1]
dist_list.append(dist)
print(np.array(dist_list).min())
用時約15s，得出結果為12.9128
4.改良遺傳演算法
a.在個體配對時講究“門當戶對”
b.使用正態分布選擇變異點
c.優化適應度函式，提高選擇更優解的比例
d.防止優良解因為變異遭到破壞，對于最優解進行保護
e.引入遺傳-災變演算法，有效避免了區域最優解的壟斷，增強了全域搜索的能力
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/233128.html
標籤：其他