遗传算法的基本运算过程如下：
（1）初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
（2）个体评价：计算群体P(t)中各个个体的适应度。
（3）选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
（4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。
（5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
（6）终止条件判断：若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
现以TSP问题为例实现GA算法：
1.初始化及参数设置
初始个体为到访城市顺序，为15个互不相同的0-14数字的数组组成
Dis = [
[0,29,82,46,68,52,72,42,51,55,29,74,23,72,46],
[29,0,55,46,42,43,43,23,23,31,41,51,11,52,21],
[82, 55, 0, 68, 46, 55, 23, 43, 41, 29, 79, 21, 64, 31, 51],
[46, 46, 68, 0, 82, 15, 72, 31, 62, 42, 21, 51, 51, 43, 64],
[68, 42, 46, 82, 0, 74, 23, 52, 21, 46, 82, 58, 46, 65, 23],
[52, 43, 55, 15, 74, 0, 61, 23, 55, 31, 33, 37, 51, 29, 59],
[72, 43, 23, 72, 23, 61, 0, 42, 23, 31, 77, 37, 51, 46, 33],
[42, 23, 43, 31, 52, 23, 42, 0, 33, 15, 37, 33, 33, 31, 37],
[51, 23, 41, 62, 21, 55, 23, 33, 0, 29, 62, 46, 29, 51, 11],
[55, 31, 29, 42, 46, 31, 31, 15, 29, 0, 51, 21, 41, 23, 37],
[29, 41, 79, 21, 82, 33, 77, 37, 62, 51, 0, 65, 42, 59, 61],
[74, 51, 21, 51, 58, 37, 37, 33, 46, 21, 65, 0, 61, 11, 55],
[23, 11, 64, 51, 46, 51, 51, 33, 29, 41, 42, 61, 0, 62, 23],
[72, 52, 31, 43, 65, 29, 46, 31, 51, 23, 59, 11, 62, 0, 59],
[46, 21, 51, 64, 23, 59, 33, 37, 11, 37, 61, 55, 23, 59, 0]
]
M = 100
ori = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
t = 0
T = 150 #最大次数
Pc = 0.5 #交叉概率
Pm = 0.05 #变异概率
fitnessMin = 10000
def init(M, ori):
res = [[0] * 15 for row in range(M)]
for i in range(M):
temp = copy.copy(ori)
index = 0
limit = len(temp)
while(limit > 0):
visit = random.randint(0, limit - 1)
res[i][index] = visit
limit -= 1
index += 1
return res
2. 计算适应度
def calofFitness(P,ori):
cities = copy.copy(ori)
listofCity = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
res = 0
index = 0
for city in P:
listofCity[index] = cities[city]
index += 1
cities.pop(city)
#print(listofCity)
for i in range(14):
res += Dis[listofCity[i]][listofCity[i+1]]
res += Dis[0][listofCity[14]]
return res3.选择运算
def choose(P,select,M):
selectedRace = [[0] * 15 for row in range(M)]
for i in range(M):
random.seed()
rate = random.random()
rateofSelect = 0
indexofSelect = 0
for j in select:
rateofSelect += j
if(rateofSelect >= rate):
selectedRace[i] = P[indexofSelect]
break
else:
indexofSelect += 1
if(indexofSelect >= M):
selectedRace[i] = P[indexofSelect-1]
return selectedRace4. 交叉运算
def cross(selectedRace,Pc,M):
res = []
for i in range(int(M / 2)):
random.seed()
rateofCross = random.random()
if(rateofCross < Pc):
indexofCross = random.randint(0, len(selectedRace[0]) - 1)
temp1 = []
temp2 = []
temp1.extend(selectedRace[i * 2][0:indexofCross])
temp1.extend(selectedRace[i * 2 + 1][indexofCross:len(P[i])])
temp2.extend(selectedRace[i * 2 + 1][0:indexofCross])
temp2.extend(selectedRace[i * 2][indexofCross:len(P[i])])
res.append(temp1)
res.append(temp2)
else:
res.append(selectedRace[i * 2])
res.append(selectedRace[i * 2 + 1])
return res5. 变异运算
def mutation(crossedRace,Pm):
for i in range(M):
random.seed()
rateofMutation = random.random()
if(rateofMutation < Pm):
#print(1)
a = random.randint(0,14)
b = random.randint(0,14-a)
crossedRace[i][a] = b整体代码
import copy
import random
'''init start race'''
def init(M, ori):
res = [[0] * 15 for row in range(M)]
for i in range(M):
temp = copy.copy(ori)
index = 0
limit = len(temp)
while(limit > 0):
visit = random.randint(0, limit - 1)
res[i][index] = visit
limit -= 1
index += 1
return res
'''calculate the fitness '''
def calofFitness(P,ori):
cities = copy.copy(ori)
listofCity = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
res = 0
index = 0
for city in P:
listofCity[index] = cities[city]
index += 1
cities.pop(city)
#print(listofCity)
for i in range(14):
res += Dis[listofCity[i]][listofCity[i+1]]
res += Dis[0][listofCity[14]]
return res
'''normalization and calculate the scale'''
def calofScale(fitness):
res = copy.copy(fitness)
total = sum(res)
for i in range(M):
res[i] = (max(fitness) - fitness[i])/(max(fitness) * M - total)
return res
'''choose single to evaulate'''
def choose(P,select,M):
selectedRace = [[0] * 15 for row in range(M)]
for i in range(M):
random.seed()
rate = random.random()
rateofSelect = 0
indexofSelect = 0
for j in select:
rateofSelect += j
if(rateofSelect >= rate):
selectedRace[i] = P[indexofSelect]
break
else:
indexofSelect += 1
if(indexofSelect >= M):
selectedRace[i] = P[indexofSelect-1]
return selectedRace
'''cross'''
def cross(selectedRace,Pc,M):
res = []
for i in range(int(M / 2)):
random.seed()
rateofCross = random.random()
if(rateofCross < Pc):
indexofCross = random.randint(0, len(selectedRace[0]) - 1)
temp1 = []
temp2 = []
temp1.extend(selectedRace[i * 2][0:indexofCross])
temp1.extend(selectedRace[i * 2 + 1][indexofCross:len(P[i])])
temp2.extend(selectedRace[i * 2 + 1][0:indexofCross])
temp2.extend(selectedRace[i * 2][indexofCross:len(P[i])])
res.append(temp1)
res.append(temp2)
else:
res.append(selectedRace[i * 2])
res.append(selectedRace[i * 2 + 1])
return res
'''mutation'''
def mutation(crossedRace,Pm):
for i in range(M):
random.seed()
rateofMutation = random.random()
if(rateofMutation < Pm):
#print(1)
a = random.randint(0,14)
b = random.randint(0,14-a)
crossedRace[i][a] = b
Dis = [
[0,29,82,46,68,52,72,42,51,55,29,74,23,72,46],
[29,0,55,46,42,43,43,23,23,31,41,51,11,52,21],
[82, 55, 0, 68, 46, 55, 23, 43, 41, 29, 79, 21, 64, 31, 51],
[46, 46, 68, 0, 82, 15, 72, 31, 62, 42, 21, 51, 51, 43, 64],
[68, 42, 46, 82, 0, 74, 23, 52, 21, 46, 82, 58, 46, 65, 23],
[52, 43, 55, 15, 74, 0, 61, 23, 55, 31, 33, 37, 51, 29, 59],
[72, 43, 23, 72, 23, 61, 0, 42, 23, 31, 77, 37, 51, 46, 33],
[42, 23, 43, 31, 52, 23, 42, 0, 33, 15, 37, 33, 33, 31, 37],
[51, 23, 41, 62, 21, 55, 23, 33, 0, 29, 62, 46, 29, 51, 11],
[55, 31, 29, 42, 46, 31, 31, 15, 29, 0, 51, 21, 41, 23, 37],
[29, 41, 79, 21, 82, 33, 77, 37, 62, 51, 0, 65, 42, 59, 61],
[74, 51, 21, 51, 58, 37, 37, 33, 46, 21, 65, 0, 61, 11, 55],
[23, 11, 64, 51, 46, 51, 51, 33, 29, 41, 42, 61, 0, 62, 23],
[72, 52, 31, 43, 65, 29, 46, 31, 51, 23, 59, 11, 62, 0, 59],
[46, 21, 51, 64, 23, 59, 33, 37, 11, 37, 61, 55, 23, 59, 0]
]
M = 100
ori = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
t = 0
T = 150 #最大次数
Pc = 0.5 #交叉概率
Pm = 0.05 #变异概率
fitnessMin = 10000
P = init(M,ori)
while(t < T):
fitness = [0] * M
'''make the fitness'''
for i in range(M):
fitness[i] = calofFitness(P[i],ori)
#print(fitness)
'''record the best answer'''
if fitnessMin > min(fitness):
listMin = P[fitness.index(min(fitness))]
fitnessMin = min(fitness)
'''make the select matrix'''
#print(fitness)
select = calofScale(fitness)
#print(select)
'''choose the single to evulate'''
selectedRace = choose(P,select,M)
#print(selectedRace)
'''cressover operation'''
crossedRace = cross(selectedRace,Pc,M)
#print(crossedRace)
'''mutation operation'''
mutation(crossedRace,Pm)
P = copy.copy(crossedRace)
#print(crossedRace)
t += 1
print(fitnessMin)
print(listMin)
版权声明：本文为yang605439282原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。