帮助网
(7065) 点赞: (143) 标签: 高级编程
from random import choice,sample,randint,shuffle
import copy,time
#遗传算法实例之：解01背包问题 for python 3.x
# 作者微信：19958289908
# QQ：191501000或850288808
#网址：www.pythonhelp.cn
#为了彰显代码的优越性，测试用例数据取至于网络：
goods_weight = [5, 7, 9, 8, 4, 3, 10, 14, 13, 19, 6, 8, 25, 15]#物品重量
#goods_weight = [80,82,85,70,72,70,82,75,78,45,49,76,45,35,94,49,76,79,84,74,76,63,35,26,52,12,56,78,16,52,16,42,18,46,39,80,41,41,16,35,70,72,70,66,50,55,25, 50,55,40]
goods_count = len(goods_weight)#物品数量
goods_points = [10, 8, 15, 9, 6, 5, 20, 10, 13, 10, 7, 12, 5, 18]#物品价值
#128
#goods_points = [200,208,198,192,180,180,168,176,182,168,187,138,184,154,168,175,198,184,158,148,174,135,126,156,123,145,164,145,134,164,134,174,102,149,134,156,172,164,101,154,192,180,180,165,162,160,158,155, 130,125]
#3966
max_weigh = 100#背包容量(最大载重)
#max_weigh = 1000#背包容量(最大载重)
m = 200#初始人口(种群)数量
#m = 520#初始人口(种群)数量，(越大越有可能确保最优解，但效率会随之降低)
maxiteration_max = 50#终止进化的条件阈值
maxiteration_count = 0#终止进化的条件阈值计数
convergence = 0.3#变异的概率
def init_population():
"""------------初始化：种群(人口，每个人的染色体)------------"""
initialization = []
count = 0
while True:
chromosome = ''.join([choice('01') for i in range(goods_count)])
if len(set(chromosome)) == 2:#确保不是纯0或纯1
j,total_weight,total_points = calculated_fitness(chromosome)#适应度计算(即物品的共计重量与价值计算)
#print(j,total_weight,total_points)
if chromosome not in initialization and total_weight <= max_weigh:#确保染色体不重复、并过滤超重的
initialization.append(chromosome)
count += 1
if count == m:
break
return initialization
def population_mapping(initialization):
"""将初始的人口编号、并字典映射"""
population_dict = dict()
for chromosome,i in enumerate(initialization):
population_dict[chromosome] = i
return population_dict
def calculated_fitness(i):
"""计算适应度"""
#print(i)#不能全部是0或者全部是1
j = list(zip(*filter(lambda i:i, map(lambda x,y,z:int(x) and [y,z], i, goods_weight, goods_points))))
return j, sum(j[0]), sum(j[1])
def calculated_assignment(population):
#------------适应度计算、并赋值------------
#print(population)
j,total_weight,total_points = calculated_fitness(population)#计算
fitness = [j,total_weight, total_points]#赋值
return fitness
def roulette_rotating(population_dict, fitness_dict):
"""旋转轮盘、模拟轮盘赌法
遗传算法的精髓：
“轮盘转赌法”即随机普遍选择实现按概率自动化择优...
"""
partitions = []
for area, k in enumerate(fitness_dict):
roulette_partition = [area]*fitness_dict[k][2]#生成不同面积的分区轮盘
partitions.extend(roulette_partition)
#print('#模拟轮盘分区：')
#print(partitions, end='\n\n')#轮盘分区
#按分区大小的概率随机配对、且确保不是同一个染色体(模拟旋转轮盘)：
#print('#模拟轮盘：')
roulette_size = len(partitions)#轮盘大小
roulette = list(range(roulette_size))
#print(roulette, end='\n\n')#轮盘
while True:
v = choice(roulette)
mw1 = partitions[v]#其中一个指针指定的分区
#print(mw1)
w = (v + roulette_size//2) % roulette_size
mw2 = partitions[w]#180度对应的另一个指针指定的分区
#print(mw2)
if mw1 != mw2:
break
#print('随机普遍选择配对::', v, w, mw1, mw2)
return population_dict[mw1], population_dict[mw2]#返回一组(2个)配对成功的染色体
"""
1. 交叉的作用：
2. 交叉的作用：保证种群的稳定性，朝着最优解的方向进化；
3. 变异的作用：保证种群的多样性，避免交叉可能产生的局部收敛。
4. 选择的作用：优胜劣汰，适者生存；
"""
def mating(mws):
"""单点交配函数"""
male,female = mws
male,female = list(male),list(female)
male_copy,female_copy = copy.deepcopy(male),copy.deepcopy(female)
s = set([''.join(male)])
s.add(''.join(female))
for w,j in enumerate(female):
male[w:],female[w:] = female[w:],male[w:]
s.add(''.join(male))
s.add(''.join(female))
male,female = male_copy,female_copy
return s
def matings(mws):
"""多点交配函数"""
male,female = mws
male,female = list(male),list(female)
male_copy,female_copy = copy.deepcopy(male),copy.deepcopy(female)
s = set([''.join(male)])
s.add(''.join(female))
for v,i in enumerate(male):
for w,j in enumerate(female):
male[w::v+2],female[w::v+2] = female[w::v+2],male[w::v+2]
s.add(''.join(male))
s.add(''.join(female))
male,female = male_copy,female_copy
return s
def survival_fittest(fitness_dict, offspring):
"""适者生存、劣者淘汰"""
mins = min(fitness_dict.items(), key=lambda i:i[1][2])#最劣者
a, b = mins[1], offspring
if b[2] > a[2] and b[1] <= max_weigh:#判断(变异)后代是否优于最劣者、并局限最大负载(约束条件)
a = b
#print('淘汰最劣者：', a)
d = 1#用于识别是否有淘汰劣者
else:
d = 0
return mins[0], a, d
def generate_progenys(population_dict, fitness_dict):
"""交配、生成后代：(参数接受原映射字典、和适应度计算后的映射字典)"""
#------------轮盘赌法配对------------
mws = roulette_rotating(population_dict, fitness_dict)#旋转轮盘
#print('#轮盘赌法配对后的(180度)配对男女：')
#print(mws, end='\n\n')
#------------单点交配------------
progeny1 = mating(mws)
#print('#单点交配后生成的后代：')
#print(progeny1, end='\n\n')#交配后生成的后代
#------------多点交配------------
progeny2 = matings(mws)
#print('#多点交配后生成的后代：')
#print(progeny2, end='\n\n')#交配后生成的后代
#交配后的后代：
progenys = progeny1 | progeny2
#print('#交配后产生的后代：')
#print(progenys, end='\n\n')
return progenys#交配后产生的后代
def variation(progenys, r_L_count):
"""后代直接变异(测试函数)"""
#print('变异...')
#随机生成染色体的变异位的索引:
indexL = list(range(goods_count))
L = []
for i in range(1, goods_count+1):
L.append(sample(indexL, i))
#print(L)
#使后代变异：
s = set([])#一组变异的染色体集合
for offspring in progenys:
offspring = list(offspring)#列表化每个染色体
r_L_count += 1 #变异过程中的迭代次数+1
for i in L:#迭代随机生成的索引
offspring_copy = copy.deepcopy(offspring)
for j in i:
#使染色体变异：
if offspring[j] == '0':
offspring[j] = '1'
elif offspring[j] == '1':
offspring[j] = '0'
s.add(''.join(offspring))
#print(i, s)
offspring = offspring_copy
return s,r_L_count
def convergence_func(convergence):
"""#变异与否的概率实践函数"""
convergenceL = int(convergence * 100) * [0]#变异占比
not_convergence = int((1 - convergence) * 100) * [1]#不变异占比
L = convergenceL + not_convergence
shuffle(L)
c = choice(L)
print('C::', c)
return c
def main():
pass
if __name__ == '__main__':
main()