网站后缀,网站设计技术方案,服装网站建设的规模和类别,进口全屋定制十大名牌一、自适应大邻域搜索概念介绍 自适应大邻域搜索#xff08;Adaptive Large Neighborhood Search#xff0c;ALNS#xff09;是一种用于解决组合优化问题的元启发式算法。以下是关于它的详细介绍#xff1a;
-自适应大领域搜索的核心思想是#xff1a;破坏解、修复解、动…
一、自适应大邻域搜索概念介绍 自适应大邻域搜索Adaptive Large Neighborhood SearchALNS是一种用于解决组合优化问题的元启发式算法。以下是关于它的详细介绍
-自适应大领域搜索的核心思想是破坏解、修复解、动态调整权重并选择自适应。
一 基本原理
1大邻域搜索LNS基础 传统的局部搜索算法通常在当前解的小邻域内进行搜索容易陷入局部最优解。大邻域搜索则通过破坏destroy当前解的一部分生成一个更大的邻域然后再通过修复repair操作得到新的可行解从而有可能跳出局部最优。 例如在车辆路径规划问题中破坏操作可以是移除一些客户节点修复操作则是将这些移除的节点重新插入到路径中。 与同类算法相比在邻域搜索算法中有的算法可以只使用一种邻域如模拟退火算法因此它仅仅搜索了解空间的一小部分找到全局最优的概率较小它的优势之一是可以避免陷入局部最优 邻域搜索算法以一个初始解 x xx 为输入在 x xx 的邻域进行搜索以寻找可能存在的更优解每次找到一个更优解就用它替换当前解直到达到局部最优解找不到任何更优解。该算法被称为最佳改进算法因为它总是选择邻域中的最佳解。 而有的算法可以使用多种算子如变邻域搜索算法VNS它通过在当前解的多个邻域中寻找更满意的解能够大大提高算法在解空间的搜索范围但是它在使用算子时盲目地将每种算子形成的邻域结构都搜索一遍缺少了一些启发式信息的指导 而自适应大邻域搜索算法就弥补了这种不足这种算法根据算子的历史表现与使用次数选择下一次迭代使用的算子通过算子间的相互竞争来生成当前解的邻域结构而在这种结构中有很大概率能够找到更好的解 销毁方法通常包含随机元素因此每次调用该方法时都会销毁解决方案的不同部分。然后解 x xx 的邻域 N ( x ) N(x)N(x) 被定义为通过首先应用破坏方法然后应用修复方法可以达到的解集。 2自适应机制 ALNS在LNS的基础上引入了自适应机制。它会根据不同的破坏和修复操作在搜索过程中的表现动态地调整这些操作被选择的概率。表现好的操作在后续搜索中被选择的概率会增加反之则减少。 具体来说算法会为每个破坏和修复操作维护一个分数根据该分数更新操作的权重进而影响操作被选择的概率。
二 主要步骤
1 初始化 生成一个初始解。这个初始解可以是通过某种启发式方法得到的也可以是随机生成的。 初始化各种破坏和修复操作的权重通常初始权重可以设置为相等。
2 迭代搜索 选择操作根据当前操作的权重使用某种选择策略如轮盘赌选择选择一个破坏操作和一个修复操作。 破坏阶段使用选择的破坏操作对当前解进行破坏得到一个部分解。 修复阶段使用选择的修复操作对部分解进行修复得到一个新的可行解。 接受准则根据一定的接受准则如模拟退火中的Metropolis准则决定是否接受这个新解。如果接受则将新解作为当前解否则保持当前解不变。 更新操作分数和权重根据新解的质量更新所使用的破坏和修复操作的分数然后根据分数更新操作的权重。
3 终止条件 当满足一定的终止条件如达到最大迭代次数、运行时间超过限制等时算法停止输出当前找到的最优解。 1. 生成初始解当前解X0 初始解最优解X1 X02. 重复以下步骤进行迭代直到停止准则2.1 根据算子权重选择破坏与修复算子并更新算子使用次数2.2 破坏算子和修复算子依次对当前解操作得到新解X22.3 更新当前解 - 如f(X2) f(X0)则X0 X2- 如f(X2) f(X0)则以一定的概率接受该解作为当前解2.4 更新最优解 - 如f(X2) f(X1)则X1 X22.5 更新算子的分数2.6 更新算子的权重2.7 重置当前解3. 返回最优解X1 4关于破坏算子选择以及修复算子选择说明 5关于动态调整权重并选择自适应过程的说明 三算法评析 1优点
全局搜索能力强通过大邻域搜索能够跳出局部最优有更大的机会找到全局最优解。
自适应特性能够根据搜索过程中的反馈动态调整操作的选择概率提高搜索效率。
灵活性高可以应用于各种组合优化问题只需要根据具体问题设计合适的破坏和修复操作。
2 缺点
参数调整复杂算法中有多个参数需要调整如初始权重、分数更新规则等参数设置不当可能会影响算法的性能。
计算复杂度高由于需要进行多次破坏和修复操作计算量较大对于大规模问题可能需要较长的运行时间。
3 应用领域
ALNS在许多组合优化问题中都有应用例如
车辆路径规划问题VRP包括带时间窗的VRP、多车辆VRP等。
调度问题如作业车间调度、项目调度等。
资源分配问题如护士排班、课程排课等。
二、算法实例
一ALNS算法实现34个城市的TSP问题
#以下是python实现的代码。 其中destroy算子有3个随机筛选N个城市、删除距离最大的N个城市和随机删#除连续的N个城市repair算子有2个随机插入和贪心插入不过考虑到随机插入的效果大概率比较差所以#代码中实际只使用了贪心插入。import copy
import time
import random
import numpy as np
import pandas as pd
import os
import math
import foliumclass ALNSSearch():# 计算TSP总距离# 计算TSP总距离staticmethoddef dis_cal(path, dist_mat):distance 0for i in range(len(path) - 1):distance dist_mat[path[i]][path[i 1]]distance dist_mat[path[-1]][path[0]]return distance# 随机删除N个城市staticmethoddef random_destroy(x, destroy_city_cnt):new_x copy.deepcopy(x)removed_cities []# 随机选择N个城市并删除removed_index random.sample(range(0, len(x)), destroy_city_cnt)for i in removed_index:removed_cities.append(new_x[i])x.remove(new_x[i])return removed_cities# 删除距离最大的N个城市staticmethoddef max_n_destroy(x, destroy_city_cnt):new_x copy.deepcopy(x)removed_cities []# 计算顺序距离并排序dis []for i in range(len(new_x) - 1):dis.append(dist_mat[new_x[i]][new_x[i 1]])dis.append(dist_mat[new_x[-1]][new_x[0]])sorted_index np.argsort(np.array(dis))# 删除最大的N个城市for i in range(destroy_city_cnt):removed_cities.append(new_x[sorted_index[-1 - i]])x.remove(new_x[sorted_index[-1 - i]])return removed_cities# 随机删除连续的N个城市staticmethoddef continue_n_destroy(x, destroy_city_cnt):new_x copy.deepcopy(x)removed_cities []# 随机选择N个城市并删除removed_index random.sample(range(0, len(x) - destroy_city_cnt), 1)[0]for i in range(removed_index destroy_city_cnt, removed_index, -1):removed_cities.append(new_x[i])x.remove(new_x[i])return removed_cities# destroy操作def destroy(self, flag, x, destroy_city_cnt):# 三个destroy算子第一个是随机删除N个城市第二个是删除距离最大的N个城市第三个是随机删除连续的N个城市removed_cities []if flag 0:# 随机删除N个城市removed_cities self.random_destroy(x, destroy_city_cnt)elif flag 1:# 删除距离最大的N个城市removed_cities self.max_n_destroy(x, destroy_city_cnt)elif flag 2:# 随机删除连续的N个城市removed_cities self.continue_n_destroy(x, destroy_city_cnt)return removed_cities# 随机插入def random_insert(x, removed_cities):insert_index random.sample(range(0, len(x)), len(removed_cities))for i in range(len(insert_index)):x.insert(insert_index[i], removed_cities[i])# 贪心插入def greedy_insert(self, x, removed_cities):dis float(inf)insert_index -1for i in range(len(removed_cities)):# 寻找插入后的最小总距离for j in range(len(x) 1):new_x copy.deepcopy(x)new_x.insert(j, removed_cities[i])if self.dis_cal(new_x, dist_mat) dis:dis self.dis_cal(new_x, dist_mat)insert_index j# 最小位置处插入x.insert(insert_index, removed_cities[i])dis float(inf)# repair操作def repair(self, flag, x, removed_cities):# 两个repair算子第一个是随机插入第二个贪心插入if flag 0:self.random_insert(x, removed_cities)elif flag 1:self.greedy_insert(x, removed_cities)# 选择destroy算子def select_and_destroy(self, destroy_w, x, destroy_city_cnt):# 轮盘赌逻辑选择算子prob destroy_w / np.array(destroy_w).sum()seq [i for i in range(len(destroy_w))]destroy_operator np.random.choice(seq, size1, pprob)[0]# destroy操作removed_cities self.destroy(destroy_operator, x, destroy_city_cnt)return removed_cities, destroy_operator# 选择repair算子def select_and_repair(self, repair_w, x, removed_cities):# # 轮盘赌逻辑选择算子prob repair_w / np.array(repair_w).sum()seq [i for i in range(len(repair_w))]repair_operator np.random.choice(seq, size1, pprob)[0]# repair操作此处设定repair_operator1即只使用贪心策略self.repair(1, x, removed_cities)return repair_operator# ALNS主程序def calc_by_alns(self, dist_mat):# 模拟退火温度T 100# 降温速度a 0.97# destroy的城市数量destroy_city_cnt int(len(dist_mat) * 0.1)# destroy算子的初始权重destroy_w [1, 1, 1]# repair算子的初始权重repair_w [1, 1]# destroy算子的使用次数destroy_cnt [0, 0, 0]# repair算子的使用次数repair_cnt [0, 0]# destroy算子的初始得分destroy_score [1, 1, 1]# repair算子的初始得分repair_score [1, 1]# destroy和repair的挥发系数lambda_rate 0.5# 当前解第一代贪心策略生成removed_cities [i for i in range(dist_mat.shape[0])]x []self.repair(1, x, removed_cities)# 历史最优解第一代和当前解相同注意是深拷贝此后有变化不影响x也不会因x的变化而被影响history_best_x copy.deepcopy(x)# 迭代cur_iter 0max_iter 100print(cur_iter: {}, best_f: {}, best_x: {}.format(cur_iter, self.dis_cal(history_best_x, dist_mat),history_best_x))while cur_iter max_iter:# 生成测试解即伪代码中的x^ttest_x copy.deepcopy(x)# destroy算子remove, destroy_operator_index self.select_and_destroy(destroy_w, test_x, destroy_city_cnt)destroy_cnt[destroy_operator_index] 1# repair算子repair_operator_index self.select_and_repair(repair_w, test_x, remove)repair_cnt[repair_operator_index] 1if self.dis_cal(test_x, dist_mat) self.dis_cal(x, dist_mat):# 测试解更优更新当前解x copy.deepcopy(test_x)if self.dis_cal(test_x, dist_mat) self.dis_cal(history_best_x, dist_mat):# 测试解为历史最优解更新历史最优解并设置最高的算子得分history_best_x copy.deepcopy(test_x)destroy_score[destroy_operator_index] 1.5repair_score[repair_operator_index] 1.5else:# 测试解不是历史最优解但优于当前解设置第二高的算子得分destroy_score[destroy_operator_index] 1.2repair_score[repair_operator_index] 1.2else:if np.random.random() np.exp((self.dis_cal(x, dist_mat) - self.dis_cal(test_x, dist_mat)) / T):# 当前解优于测试解但满足模拟退火逻辑依然更新当前解设置第三高的算子得分x copy.deepcopy(test_x)destroy_score[destroy_operator_index] 0.8repair_score[repair_operator_index] 0.8else:# 当前解优于测试解也不满足模拟退火逻辑不更新当前解设置最低的算子得分destroy_score[destroy_operator_index] 0.5repair_score[repair_operator_index] 0.5# 更新destroy算子的权重destroy_w[destroy_operator_index] \destroy_w[destroy_operator_index] * lambda_rate \(1 - lambda_rate) * destroy_score[destroy_operator_index] / destroy_cnt[destroy_operator_index]# 更新repair算子的权重repair_w[repair_operator_index] \repair_w[repair_operator_index] * lambda_rate \(1 - lambda_rate) * repair_score[repair_operator_index] / repair_cnt[repair_operator_index]# 降低温度T a * T# 结束一轮迭代重置模拟退火初始温度cur_iter 1print(cur_iter: {}, best_f: {}, best_x: {}.format(cur_iter, self.dis_cal(history_best_x, dist_mat),history_best_x))# 打印ALNS得到的最优解print(history_best_x)print(self.dis_cal(history_best_x, dist_mat))return history_best_xif __name__ __main__:original_cities [[西宁, 101.74, 36.56],[兰州, 103.73, 36.03],[银川, 106.27, 38.47],[西安, 108.95, 34.27],[郑州, 113.65, 34.76],[济南, 117, 36.65],[石家庄, 114.48, 38.03],[太原, 112.53, 37.87],[呼和浩特, 111.65, 40.82],[北京, 116.407526, 39.90403],[天津, 117.200983, 39.084158],[沈阳, 123.38, 41.8],[长春, 125.35, 43.88],[哈尔滨, 126.63, 45.75],[上海, 121.473701, 31.230416],[杭州, 120.19, 30.26],[南京, 118.78, 32.04],[合肥, 117.27, 31.86],[武汉, 114.31, 30.52],[长沙, 113, 28.21],[南昌, 115.89, 28.68],[福州, 119.3, 26.08],[台北, 121.3, 25.03],[香港, 114.173355, 22.320048],[澳门, 113.54909, 22.198951],[广州, 113.23, 23.16],[海口, 110.35, 20.02],[南宁, 108.33, 22.84],[贵阳, 106.71, 26.57],[重庆, 106.551556, 29.563009],[成都, 104.06, 30.67],[昆明, 102.73, 25.04],[拉萨, 91.11, 29.97],[乌鲁木齐, 87.68, 43.77]]original_cities pd.DataFrame(original_cities, columns[城市, 经度, 纬度])D original_cities[[经度, 纬度]].values * math.pi / 180city_cnt len(original_cities)dist_mat np.zeros((city_cnt, city_cnt))for i in range(city_cnt):for j in range(city_cnt):if i j:# 相同城市不允许访问dist_mat[i][j] 1000000else:# 单位kmdist_mat[i][j] 6378.14 * math.acos(math.cos(D[i][1]) * math.cos(D[j][1]) * math.cos(D[i][0] - D[j][0]) math.sin(D[i][1]) * math.sin(D[j][1]))# ALNS求解TSPtime0 time.time()alns ALNSSearch()history_best_x alns.calc_by_alns(dist_mat)print(city_cnt)print(使用ALNS求解TSP耗时: {} s.format(time.time() - time0))
#运行代码后可发现经过不到4s的计算时间ALNS便可以得到15662.59的解和全局最优解15614.84之间的#gap仅约0.3%。
2 Robust Optimization for the Dual Sourcing Inventory Routing Problem in Disaster Relief
import numpy as np
import math
import re
import csv
import random
import copy
import time
import os
# --------------------------- Global Configuration ---------------------------------------removal_operators_list[shaw,distance,worst,worst_replenishment_time,random]
insertion_operators_list[greedy,2_regret,shaw]##################################################################################for root, dirs, files in os.walk(./Test_set):for set_name in files:print(set_name)time_start time.time()instance set_nameproblem base.generate_problem(instance)records base.Record(removal_operators_list, insertion_operators_list)solution base.generate_initial_solution(problem)removal_operators base.Removal_operators(removal_operators_list)insertion_operators base.Insertion_operators(insertion_operators_list)solution.obj base.calculate_objective(solution, problem)current_solution copy.deepcopy(solution)best_solution copy.deepcopy(solution)time_end time.time()time_cost time_end - time_startrecords.initial_generator_time_cost time_costtime_start time.time()iteration_num 0iteration_counter 0segment_counter 0while time_cost 3600:if problem.temperature 0.01:breakif iteration_counter problem.segments_capacity:segment_counter 1iteration_counter 0for i in removal_operators_list:records.removal_operator_score_record[i].append(removal_operators.removal_operator_score[i])records.removal_operator_weights_record[i].append(removal_operators.removal_operator_weight[i])records.removal_operator_times_record[i].append(removal_operators.removal_operator_times[i])for i in insertion_operators_list:records.insertion_operator_score_record[i].append(insertion_operators.insertion_operator_score[i])records.insertion_operator_weights_record[i].append(insertion_operators.insertion_operator_weight[i])records.insertion_operator_times_record[i].append(insertion_operators.insertion_operator_times[i])removal_operators.update_weight(removal_operators_list,problem)insertion_operators.update_weight(insertion_operators_list,problem)for i in removal_operators_list:removal_operators.removal_operator_score[i] 0removal_operators.removal_operator_times[i] 0for i in insertion_operators_list:insertion_operators.insertion_operator_score[i] 0insertion_operators.insertion_operator_times[i] 0best_solution, current_solution base.do_2opt(best_solution, current_solution, problem)solution copy.deepcopy(current_solution)selected_removal_operator removal_operators.select(removal_operators_list)selected_insertion_operator insertion_operators.select(insertion_operators_list)removal_operators.removal_operator_times[selected_removal_operator] 1insertion_operators.insertion_operator_times[selected_insertion_operator] 1sub_time_start time.time()sub_time_cost sub_time_start - time_endbase.do_remove(selected_removal_operator, solution, problem)sub_time_end time.time()sub_time_cost sub_time_end - sub_time_startsub_time_start sub_time_endbase.do_insert(selected_insertion_operator, solution, problem)sub_time_end time.time()sub_time_cost sub_time_end - sub_time_startsub_time_start sub_time_endrecords.best_solution_obj_record.append(best_solution.obj)if solution.obj current_solution.obj:if solution.obj best_solution.obj:removal_operators.removal_operator_score[selected_removal_operator] problem.score_factor_1insertion_operators.insertion_operator_score[selected_insertion_operator] problem.score_factor_1current_solution copy.deepcopy(solution)best_solution copy.deepcopy(solution)current_solution copy.deepcopy(solution)records.best_solution_obj_record[iteration_num] best_solution.objsegment_counter 0print(get best solution , best_solution.obj)records.best_solution_update_iteration_num.append(iteration_num)else:removal_operators.removal_operator_score[selected_removal_operator] problem.score_factor_2insertion_operators.insertion_operator_score[selected_insertion_operator] problem.score_factor_2current_solution copy.deepcopy(solution)elif random.random() math.exp(-(solution.obj - current_solution.obj)/problem.temperature):removal_operators.removal_operator_score[selected_removal_operator] problem.score_factor_3insertion_operators.insertion_operator_score[selected_insertion_operator] problem.score_factor_3current_solution copy.deepcopy(solution)iteration_num 1iteration_counter 1time_end time.time()time_cost time_end - time_startif time_cost 1200 and iteration_num 3000/3:problem.cooling_rate (0.01/problem.temperature) ** (1/iteration_num)if time_cost 2400 and iteration_num 3000/2:problem.cooling_rate (0.01/problem.temperature) ** (1/(iteration_num/2))problem.temperature problem.temperature*problem.cooling_rateprint(iteration str(iteration_num) finished!)print(problem.instance_name, has finished!)with open(Data.csv, a, newline, encodingANSI) as f_out:csv.writer(f_out, delimiter,).writerow([set_name, best_solution.obj,time_cost])print(problem.instance_name, has finished!)三、基础知识介绍
一轮盘赌是什么 来源Evolutionary Computing: 遗传算法_轮盘赌选择转载 - 柠檬雨 - 博客园
参考引用它山之石
「1」https://zhuanlan.zhihu.com/p/353562821
「2」元启发式算法详解(自适应)大邻域搜索算法(A)LNS-CSDN博客
「3」https://zhuanlan.zhihu.com/p/102298240
