这里没有关于遗传算法的理论。先看其他文章。 参考https://blog.csdn.net/baiyuxuan123123/article/details/11481824这篇文章，编码做了这个题目:
配送中心负责将货物配送到指定的配送点。每个配送点都有一定的货物需求，以货物重量表示。 配送中心有几辆车，每辆车都有一定的载荷和里程限制，车辆的载荷和里程不得超过指定值。 一辆车可以负责一个或多个点的配送任务，每个配送点只服务一次。 在某一时刻，所有负责配送的车辆同时从配送中心出发，分别完成各自的配送任务，然后返回配送中心。 根据上述条件设计最佳配送方案。对于每个方案，应给出每辆车的配送点及其顺序。
我们给出以下三个指标来衡量方案之间的优缺点： 配送总时间t：从配送开始 最后一辆车返回物流中心的时间 车辆总里程s：所有配送车辆的里程之和 车辆总数n：车辆数量用于配送 在实际应用中，我们分别为这三个指标分配一个权重 wt ws 和 wn 以下公式作为每个方案的得分：得分越高，方案越好。 score = ? ( wt ? t ws ? s wn ? n )
from collections import namedtuple import random import numpy as np # ***** begin 配置信息 ***** max_iter = 500 population_size = 100 mutate_max_try_times = 20 select_ratio = 0.5 max_car_no = 10 min_car_no = 6 # 如果car_no设置小，鉴权可能多次失败，效率差异 cargo_site_total = 20 site_location_range = tuple(range(-100, 101, 5)) car_carrying_range = tuple(range(80, 501, 10)) car_speed_range = tuple(range(20, 51, 10)) move_cargo_second = 2 # 每次装卸时间简化， 与货物重量相关的变量也可以使用 max_cargo_weight = 100 max_car_distance = 1200 time_weight = 0.4 distance_weight = 0.3 cargo_no_weight = 1 - time_weight - distance_weight # ***** end 配置信息 ***** # 配置计算 生成数据 cargo_sites = list(range(1, cargo_site_total 1)) cargo_site_info = namedtuple("cargo_site_info", ("site_location_x", "site_location_y", "cargo_weight")) cargo_site_info_dict = {site_no: cargo_site_info( random.choice(site_location_range), random.choice(site_location_range), random.randint(0, max_cargo_weight)) for site_no in cargo_sites} # 补充起点和终点site_location计算距离时会使用信息。最后一个weight用不到 cargo_site_info_dict[0] = cargo_site_info(0, 0, 0) car_info = namedtuple("car_info", ("speed", "volume")) car_info_dict = {car_no: car_info(random.choice(car_speed_range), random.choice(car_carrying_range)) for car_no in range(1, max_car_no 1)} def get_fitness_info(cargo_site_car_list, cargo_car_loc2carno): car_ix_consume_time, distances = calculate_fitness_info(cargo_site_car_list, cargo_car_loc2carno) return -(time_weight * max(car_ix_consume_time.values()) distance_weight * sum(distances) cargo_no_weight * len(cargo_car_loc2carno)), car_ix_consume_time def calculate_fitness_info(cargo_site_car_list, cargo_car_loc2carno): distances = [] car_ix_consume_time = {} # car_ix 不是 car_no， 仅为以后的变化提供参考 car_ix = 0 last_site_no = 0 # 不会有0号site 这是为了计算距离 distance = 0 for ix, x in enumerate(cargo_site_car_list): tmp_distance = np.linalg.norm( np.array([cargo_site_info_dict[x].site_location_x, cargo_site_info_dict[x].site_location_y]) - np.array([cargo_site_info_dict[last_site_no].site_location_x, cargo_site_info_dict[last_site_no].site_location_y])) if x > 0: distance = tmp_distance last_site_no = x else: distances.append(distance) consume_time = (distance / car_info_dict[cargo_car_loc2carno[ix]].speed) move_cargo_second car_ix = 1 car_ix_consume_time[car_ix] = consume_time last_site_no = 0 distance = 0 return car_ix_consume_time, distances def get_a_possible_try(): cargo_site_list = random.sample(cargo_sites, cargo_site_total) try_times = 0 while True: car_list = random.sample(range(1, max_car_no 1), random.randint(min_car_no, max_car_no)) # 不生成在cargo_sites第一和最后一 car_location = random.sample(range(2, cargo_site_total - 1), len(car_list) - 1) car_location.append(cargo_site_total) # 最后 一辆车 car_location.sort() car_location2no = {location: car_no for location, car_no in zip(car_location, car_list)} # 其实不做强鉴权 或者有一定的概率 保持非法解决 也可以，以后可能会变异成 合法的解 if cargo_site_and_car_location_authok(cargo_site_list, car_location, car_location2no): break try_times = 1 if try_times >= 40: print("try times is %s:" % try_times) cargo_site_car_list, cargo_car_loc2carno = get_cargo_site_car_list(car_location, cargo_site_list, car_list) return cargo_site_car_list, cargo_car_loc2carno def get_cargo_site_car_list(car_location, cargo_site_list, car_list): cargo_site_car_list = cargo_site_list.copy() for location in car_location[::-1]: cargo_site_car_list.insert(location, 0) cargo_car_loc2carno = get_cargo_car_loc2carno(cargo_site_car_list, car_list) return cargo_site_car_list, cargo_car_loc2carno def get_cargo_car_loc2carno(cargo_site_car_list, car_list): ix = 0 cargo_car_loc2carno = {} for location_ix location in enumerate(cargo_site_car_list):
if location == 0:
cargo_car_loc2carno[location_ix] = car_list[ix]
ix += 1
return cargo_car_loc2carno
def cargo_site_and_car_location_authok(cargo_site_list, car_location, car_location2no):
# 如果生成连续两个0 两辆车连在一起 后一辆未载重 放弃
if (np.diff(np.array(car_location)) == 0).any():
return False
# 如果car_no较小，可能会鉴权失败多次，效率差
# print("cargo_site_list and car_location is ", cargo_site_list, car_location)
last_index = 0
for location in car_location:
tmp_cargo_sites = cargo_site_list[last_index: location]
if sum([cargo_site_info_dict[cargo_site_no].cargo_weight for cargo_site_no in tmp_cargo_sites]
) > car_info_dict[car_location2no[location]].volume:
return False
last_index = location
return True
def cargo_site_car_list_authok(cargo_site_car_list, cargo_car_loc2carno):
last_index = 0
for location_ix, location in enumerate(cargo_site_car_list):
if location == 0:
tmp_cargo_sites = cargo_site_car_list[last_index: location_ix]
if sum([cargo_site_info_dict[cargo_site_no].cargo_weight for cargo_site_no in tmp_cargo_sites]
) > car_info_dict[cargo_car_loc2carno[location_ix]].volume:
# print("location_index", location_index, car_info_dict[car_ix + 1], car_ix + 1,)
return False
last_index = location_ix
return True
def get_population_by_size(size=population_size):
population_info = [get_a_possible_try() for _ in range(size)]
return population_info
def get_fitness_by_length(population_info):
population_fitness_info = []
for cargo_site_car_list, cargo_car_loc2carno in population_info:
population_fitness_info.append((*get_fitness_info(cargo_site_car_list, cargo_car_loc2carno),
cargo_site_car_list, cargo_car_loc2carno))
return population_fitness_info
def cross_and_mutation_by_fitness(population_fitness_info):
new_pop = []
pass
def select_mutate_multiply(population_fitness_info, select_ratio=select_ratio):
new_population_info = []
# select
population_fitness_info.sort(key=lambda x: x[0], reverse=True)
new_population_fitness_info = population_fitness_info[:int(len(population_fitness_info) * select_ratio + 1)]
# 在select 后的基础上变异
for fitness_score, car_ix_consume_time, cargo_site_car_list, cargo_car_loc2carno in new_population_fitness_info:
new_population_info.append(mutate(
cargo_site_car_list, cargo_car_loc2carno, car_ix_consume_time))
# 繁殖新的一批
new_population_info.extend([get_a_possible_try() for _ in range(int(len(population_fitness_info) * select_ratio))])
return new_population_info
def mutate(cargo_site_car_list, cargo_car_loc2carno, car_ix_consume_time, max_try_times=mutate_max_try_times):
try_times = 0
while try_times <= max_try_times:
# 这只是一种变异的方式 也可以根据fitness的各项指标 分别设计
to_move_min_ix, to_move_max_ix, to_move_max_value = get_move_info(
cargo_site_car_list, cargo_car_loc2carno, car_ix_consume_time)
new_cargo_site_car_list, new_cargo_car_loc2carno = get_move_result(
cargo_site_car_list, cargo_car_loc2carno, to_move_min_ix, to_move_max_ix, to_move_max_value)
if cargo_site_car_list_authok(new_cargo_site_car_list, new_cargo_car_loc2carno):
# print("mutate success. try times is %s:" % try_times)
return new_cargo_site_car_list, new_cargo_car_loc2carno
try_times += 1
# print("mutate fail after try times is %s:" % max_try_times)
return cargo_site_car_list, cargo_car_loc2carno
def get_move_info(cargo_site_car_list, cargo_car_loc2carno, car_ix_consume_time):
# 把耗时最长的车辆对应的货物点 移一个加到耗时最短的车辆对应的货物点
sorted_car_time = sorted(car_ix_consume_time.items(), key=lambda x: x[1])
min_ix = sorted_car_time[0][0]
max_ix = sorted_car_time[-1][0]
larger_range = list(cargo_car_loc2carno.keys())[max(max_ix - 2, 0): max_ix]
smaller_range = list(cargo_car_loc2carno.keys())[max(min_ix - 2, 0): min_ix]
to_move_min_ix = random.choice(list(range(smaller_range[0], smaller_range[1]))
) if len(smaller_range) > 1 else smaller_range[0]
to_move_max_ix = random.choice(list(range(larger_range[0] + 1, larger_range[1]))
) if len(larger_range) > 1 else larger_range[0]
to_move_max_value = cargo_site_car_list[to_move_max_ix]
return to_move_min_ix, to_move_max_ix, to_move_max_value
def get_move_result(cargo_site_car_list, cargo_car_loc2carno, to_move_min_ix, to_move_max_ix, to_move_max_value):
new_cargo_site_car_list = []
for location_ix, location in enumerate(cargo_site_car_list):
if location_ix != to_move_max_ix:
new_cargo_site_car_list.append(location)
if location_ix == to_move_min_ix:
new_cargo_site_car_list.append(to_move_max_value)
# car_list 也可以在get_a_possible_try中 保存下来减少计算
car_list = [car_no for (_, car_no) in sorted(cargo_car_loc2carno.items(), key=lambda x: x[0])]
new_cargo_car_loc2carno = get_cargo_car_loc2carno(new_cargo_site_car_list, car_list)
return new_cargo_site_car_list, new_cargo_car_loc2carno
def print_final_result(population_info):
population_fitness_info = get_fitness_by_length(population_info)
population_fitness_info.sort(key=lambda x: x[0], reverse=True)
fitness_score, car_ix_consume_time, cargo_site_car_list, cargo_car_loc2carno = population_fitness_info[0]
print("\nthe final best score is %s cargo_site_car_list is %s, where the 0s representing car_list is %s."
% (round(fitness_score, 2), cargo_site_car_list,
[car_no for (_, car_no) in sorted(cargo_car_loc2carno.items(), key=lambda x: x[0])]))
return None
def run():
population_info = get_population_by_size()
for ix in range(max_iter):
population_fitness_info = get_fitness_by_length(population_info)
population_info = select_mutate_multiply(population_fitness_info)
if ix % 10 == 0:
print("run times %s, score is: %s" % (ix, np.mean(np.array([x[0] for x in population_fitness_info]))))
print_final_result(population_info)
if __name__ == '__main__':
run()没有做可视化，目前只通过打印日志，看到分数的下降。 小说明，每次运行时 货物点等数据都是动态生成的。当然如果想做其他观察可以生成后保存下来 每次重新load.
另外: 看到这篇介绍 https://blog.csdn.net/lqk1985/article/details/7103875， 看到这里面的图， 你第一想到什么？ 根据本人学习顺序，第一反应当然是对抗生成网络。
评价扇贝像不像Firefox的函数“适应函数” 不就相当于判别器D么？ 变异 不就相当于生成器(虽然没有依据正态分布和均匀分布去产生)么？ 不过这里的变异 没法弱化D的判别能力，因为GAN里的生成器的损失函数 包含了判别器D的输出。这里的变异，只是变异本身。 “当然，它也有缺点，比如说早期的优势基因可能会很快通过交换基因的途径散播到整个种群中，这样有可能导致早熟（premature），也就是说整个种群的基因过早同一化，得不到足够好的结果” --他竟然提到了 模型坍塌！！ 内味更多了，是不？ 那再类比想想， 遗传算法中的变异，有没有机会 去影响到适应函数，让适应函数去自我提升(提升适应函数 是为了反过来再提升变异)？ 好像没法子呵? 如果你想到了，可以通知我一下。
旁边的高人妹子 说她看到图片，第一想到的是 一个不可描述的超空间，用某种方式 不停的去接近它。 这不就是VAE(主要是变分推断)么?
与强化学习的 value-based, policy-based比呢，也有那么一点点相似之处？