1 前⾔
这是⼀篇课程作业，⽬的是复现参考⽂献[1]，采⽤MATLAB编程。⽂献[1]⽤遗传算法解决了从直线运动运载体上发射的⽆⼈机的旅⾏商问题，本⽂对相关概念进⾏了介绍，给出了仿真程序与最终结果，并与⽂献[1]进⾏⽐较，验证了⽂献[1]的有效性。
⾄于为何要发博客，是因为这是我第⼀次完全看懂并从头到尾复现⼀篇⽂献的经历，特此纪念。请各位⼤佬轻喷，并希望在以后的⽣活学习中我能继续保持这种⼼态前进。写作中参考了其他博客与⽹页，如有侵权请联系我。
2 相关概念及原理
2.1 旅⾏商问题
旅⾏商问题（Travelling Salesman Problem, TSP）⼜称旅⾏推销员问题，是数学领域的著名问题之⼀。假设有⼀个旅⾏商⼈要拜访N个城市，每个城市只能拜访⼀次，⽽最后要回到原来的城市。旅⾏商问题的内容便是如何选择拜访城市的路线，使得总的路程最⼩。旅⾏商问题是⼀个NP问题，即⾮确定性多项式问题。它的解空间包含(N-1)!个⽅案，当N→∞时问题规模⽐指数级增长更快，当N⼤于⼀定程度时，
采⽤穷举法求解旅⾏商问题的计算开销会变得不可接受。因此，解决旅⾏商问题多采⽤启发式算法，例如遗传算法、粒⼦算法、蚁算法、模拟退⽕算法等等。
2.2 遗传算法
遗传算法（Genetic Algorithm, GA）是由美国的John Holland于20世纪70年代提出，该算法根据⾃然界中的⽣物进化规律⽽设计。通过模拟⾃然选择和⽣物进化的遗传学机理，遗传算法是⼀种解决搜索问题的有效⼿段。遗传算法直接对某种结构对象进⾏操作，不存在求导与对函数连续性的要求，使⽤⽅便；遗传算法不是漫⽆⽬的的随机搜索，⽽是能⾃动获取、指导并优化搜索⽅向，因⽽具有更好的全局寻优能⼒。
遗传算法的基本单元是染⾊体。由于算法不能直接处理问题空间的参数，因此需要将待求解问题通过编码表⽰成遗传空间的染⾊体（或称个体），染⾊体中的每个单元称为基因。编码策略通常需要具备完备性、健全性和⾮冗余性。将问题编码后，就可以通过⼀定规则构建初始种，随后便可开始进⾏进化模拟：
（1）选择：模拟⾃然选择，从种中通过某种特定规则选择出较适应环境的个体，适者⽣存，不适者淘汰，并⽤这些个体繁殖下⼀代。参照的规则由适应度函数表⽰，也可以⽤代价函数表⽰。
（2）交叉：模拟⽣物繁殖过程中的染⾊体交叉互换。对两个不同的亲代个体在相同的位置进⾏基因交换，从⽽产⽣新的个体。
（3）变异：模拟⽣物繁殖过程中的基因突变。随机选择种中的某些个体，对其中的某些基因进⾏异向转化，从⽽保证基因的多样性。
每进⾏⼀周期遗传操作，产⽣的种称作⼀代。在对每代染⾊体进⾏选择时可以采⽤精英主义，即⼤量克隆当前种中的最优个体，保证最优个体的基因⼤概率会传播下去，从⽽在⼀定程度上杜绝遗传操作带来的退化现象。
最后，本⽂遗传算法的步骤如图所⽰。
2.3 最邻近算法
另⼀个常⽤于解决TSP问题的算法是最邻近算法，其本质为贪⼼算法，即每⼀步都选择距离当前城市最近的城市作为下⼀个⽬的地。该⽅法的运算速度极快，但结果的好坏极⼤程度上取决于问题中各个城市点的排布。
2.4 2-Opt
2-Opt为2-Optimization的简称，即两元素优化。它是由Croes提出的，最早⽤于解决TSP问题的算法。2-Opt算法是⼀种局部搜索算法，其基本思路为：对于遗传空间中的⼀个可⾏解染⾊体，计算其代价，然后随机在染⾊体中选取两个基因位点，将两位点之间的染⾊体反转并接回原来的位置，并计算其代价。如果新染⾊体代价⼩于原染⾊体，则⽤新染⾊体代替原染⾊体，否则保持原染⾊体不变。从2-Opt的原理可知，只要给出⾜够长的时间，2-Opt必定能求出TSP问题的最优解。但实际上，由于基因位点选取的随机性和计算机计算能⼒的限制，2-Opt算法只能给出局部的最优解。这时，由于遗传算法具有全局寻优的能⼒，将遗传算法与2-Opt相结合能⼤⼤提⾼算法效果和效率。本⽂在每代遗传操作结束后⽤2-Opt⽅法处理种所有染⾊体。
3 使⽤遗传算法解决TSP问题
3.1 编码
对于旅⾏商问题，所要求解的是访问城市的最佳顺序。由于城市坐标已知，当顺序确定时，路程就确定了，据此可以将基因编码为正整数1,2,...,N，分别代表第1,2,...,N个城市，⽽城市访问顺序与染⾊体基因顺序⼀⼀对应。相应的适应度函数即为每条染⾊体所代表的访问顺序的总路程，总路程越低，说明适应能⼒越好。需要注意的是，适应度函数中也应该包括从起飞点到第⼀个城市，以及从最后⼀个城市到降落点的距离。
3.2 定义起飞点
出于简单考虑，本⽂假设运载体从原点(0,0)出发，并沿⼀个⾓度θ做速度为Vc的匀速直线运动。因此，运载体的路线是已知且可预测的，运载体路线上的所有点均可作为⽆⼈机的潜在起飞点。理论上，每个潜在起飞点之间的距离应⾜够⼩，才不会影响⽆⼈机的路径设计。在实验中，可以在运载体路线上取⼀定数量的等距点，近似作为起飞点参与TSP运算。更复杂的运载体运动路线可以以此为基础深⼊研究。
3.3 遗传操作
⽤遗传算法解决TSP问题的步骤与图1的流程⼤致相同，区别在于需要在“繁殖、交叉、变异”⼀步后加上2-Opt算法对本代染⾊体进⾏局部寻优。本⽂的算法设计流程如下：
（1）初始化：将TSP中的地点次序编码成基因后，随机产⽣⾜够多的初代染⾊体加⼊种，直到达到种容量上限。对于起飞点，根据贪⼼算法的思想，将距离染⾊体⾸位基因所对应城市最近的潜在起飞点作为起飞点。
（2）精英主义⾃然选择：将种适应度从⼩到⼤排序，消灭后⼀半个体并克隆第⼀个个体，直到种数量再次达到上限。这⼀步会保证当前的局部最优个体的基因⼤概率被传⼊⼦代中。
（3）染⾊体交叉：由于TSP问题要求每个城市只访问⼀次，简单的染⾊体交叉可能会造成访问重复和空缺。为此采⽤部分映射交叉（Partial-Mapped Crossover, PMX）对染⾊体进⾏交叉处理。
部分映射交叉的思想如下：⾸先随机选取两个交叉位点，交换两条亲代染⾊体在交叉位点之间的部分。然后固定交换的部分不变，遍历每条染⾊体中未交换的部分，如果有基因与交换部分重复，则根据交换部分的⼀⼀对应关系将重复的基因也换成相对的基因，如此往复直到每条染⾊体中都不包含重复的基因。部分交叉映射的⼀个例⼦如图所⽰：
（4）基因突变：随机选取染⾊体中的两个位点，交换这两个位点的基因。
（5）2-Opt：采⽤2-Opt算法对种的每条染⾊体进⾏局部优化。在优化完成后，由于⾸位基因可能更改，所以需重新计算起飞点。
3.4 适应度计算
4 实验代码及仿真实验
4.1 实验代码
主函数main
%遗传算法解决旅⾏商问题
%参考⽂献
%Savuran Halil and Karakaya Murat.
%Route Optimization Method for Unmanned Air Vehicle Launched from a Carrier[J]. %Lecture Notes on Software Engineering, 2015, 3(4) : 279-284. %——————————————————————————
%Copyright 2021 Eterrank. All rights reserved.
clear;clc;
%% 初始化
%初始化数据，读取数据集
UAV_SPEED = 300; %⽆⼈机速度
CARRIER_SPEED = 40; %运载体速度
CARRIER_THETA = pi/4; %载体航向⾓
TAKEOFF_NUM = 30; %起飞点数量设置
%读取数据集及参数配置
%共6个数据集，分别为'Berlin52','Eil76','Bier127'
%'CH130','CH150','KroB200'
DataCell = set_data_set('CH150');
GENES = DataCell{1};
POPSIZE = DataCell{2}; %种⼤⼩
GENSIZE = DataCell{3}; %遗传代数
P_CROSS = DataCell{4}; %交叉概率
P_MUTATE = DataCell{5}; %变异概率
OPT_2 = DataCell{6}; %2-opt次数
t_factor = DataCell{7}; %地图尺度缩放因⼦，偷懒⽤
%% 绘制地图背景
%画出城市点
figure;plot(GENES(:,1),GENES(:,2),'.','markersize',10);
figure;plot(GENES(:,1),GENES(:,2),'.','markersize',10);
axis ij; %反转坐标轴
%定义载体航线以及起飞点
%由于不同数据集地图⼤⼩不同，为了偷懒，⽤缩放因⼦t_factor放⼤缩⼩起飞点坐标
takeoff = zeros(TAKEOFF_NUM,2);
for i = 1:TAKEOFF_NUM
takeoff(i,1) = i * CARRIER_SPEED * cos(CARRIER_THETA) * t_factor;
takeoff(i,2) = i * CARRIER_SPEED * sin(CARRIER_THETA) * t_factor;
end
%% 初代遗传计算
%随机产⽣初始种并指定起飞点，pop和takeoff_pos是索引
pop = generate(GENES,POPSIZE);
takeoff_pos = calc_takeoff_pos(GENES,pop,takeoff);
%检验每个城市对应的起飞点
% for i = 1:length(takeoff_pos)
% hold on;
% plot([GENES(pop(i,1),1),takeoff(takeoff_pos(i),1)],[GENES(pop(i,1),2),takeoff(takeoff_pos(i),2)]);
% end
%计算每条染⾊体的适应度，杀死后⼀半个体并克隆第⼀个个体
pop_after_clone = kill_clone(pop,takeoff_pos,GENES,takeoff,[]);
%部分映射交叉PMX、变异及精英主义筛选
pop_after_PMX = PMX(pop_after_clone,P_CROSS,P_MUTATE,GENES,takeoff);
%由于种早已变化，重新计算⼀次起飞点
takeoff_pos = calc_takeoff_pos(GENES,pop_after_PMX,takeoff);
%2-opt局部最优搜索
new_pop = OPT2(pop_after_PMX,takeoff_pos,GENES,takeoff,OPT_2);
%再重新计算起飞点
takeoff_pos = calc_takeoff_pos(GENES,new_pop,takeoff);
%重新计算代价
value = cost(new_pop,takeoff_pos,GENES,takeoff);
%计算载体路程和降落点
[inter,r_val] = landing(new_pop,GENES,takeoff_pos,takeoff,value,UAV_SPEED,CARRIER_SPEED,CARRIER_THETA); %计算总代价
value = value + r_val;
%% ⼦代循环计算
%⾄此初代计算完成，new_pop为⼦代，value为⼦代适应度，从杀死⼀半个体开始继续繁衍
%为防范变异影响，记录最后五代
[num,chromlength] = size(pop);
pop_5 = zeros(5,chromlength);
takeoff_5 = zeros(5,1);
value_5 = zeros(5,1);
inter_5 = zeros(5,2); %最后五代的交汇点
%记录每轮最优代价值
matlab求导value_all = zeros(GENSIZE,1);
for i = 1:GENSIZE
pop_after_clone = kill_clone(new_pop,takeoff_pos,GENES,takeoff,value);
pop_after_PMX = PMX(pop_after_clone,P_CROSS,P_MUTATE,GENES,takeoff);
takeoff_pos = calc_takeoff_pos(GENES,pop_after_PMX,takeoff);
new_pop = OPT2(pop_after_PMX,takeoff_pos,GENES,takeoff,OPT_2);
takeoff_pos = calc_takeoff_pos(GENES,new_pop,takeoff);
value = cost(new_pop,takeoff_pos,GENES,takeoff);
[inter,r_val] = landing(new_pop,GENES,takeoff_pos,takeoff,value,UAV_SPEED,CARRIER_SPEED,CARRIER_THETA); value = value + r_val;
[sort_val,index] = sort(value,'ascend');
value_all(i) = sort_val(1);
%防范变异影响，记录最后五代
if i >= GENSIZE - 4
j = i - GENSIZE + 5;
pop_5(j,:) = new_pop(index(1),:);
takeoff_5(j) = (takeoff_pos(index(1)));
value_5(j) = sort_val(1);
inter_5(j,:) = inter(index(1),:);
end
end
%% 画图
%从最后五代中选择最优个体
发布评论