?
一、tsp问题
TSP问题即旅行商问题，经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的哈密尔顿回路。
旅行商问题有很多种不同的问法，最近做了几个关于TSP的题，下面总结一下。由于大部分TSP问题都是NP-Hard的，因此很难得到什么高效的多项式级别的算法，一般采用的算法都偏向于暴力搜索以及状压DP，这里都采取用状压DP解决。大部分TSP问题所给的地点数目都非常小。
考虑经典的TSP问题，如果采用状压DP，将每个地点访问与否作为二进制1/0压缩，不难得到状态转移方程：
dp[S][i] = min(dp[S][i], dp[S ^ (1 << (i - 1))][k] + dist[k][i])
S代表当前状态，i(从1开始)表示到达当前状态时最后访问的是第i个地点
k为S中所有访问的与i不同的地点。
dist表示两点间最短路。
以及初始化：
DP[S][i] = dist[start][i](S == 1<<(i - 1))
如果初次遇到状压dp，感到陌生的话，就请仔细思考上面式子的含义，这是大部分TSP问题的关键。
二、nsga-II算法
1 NSGA算法
1.1 Paerot支配关系
1.2 Pareto最优解定义
多目标优化问题与单目标优化问题有很大差异。当只有一个目标函数时,人们寻找最好的解,这个解优于其他所有解,通常是全局最大或最小,即全局最优解。而当存在多个目标时,由于目标之间存在冲突无法比较,所以很难找到一个解使得所有的目标函数同时最优,也就是说,一个解可能对于某个目标函数是最好的,但对于其他的目标函数却不是最好的,甚至是最差的。因此,对于多目标优化问题,通常存在一个解集,这些解之间就全体目标函数而言是无法比较优劣的,其特点是:无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解(nondominated soluitons)或Pareto最优解(Pareto optimal Soluitons),定义如下：
也即没有其他值可以支配Xu。
2、NSGA一般流程
NSGA采用的非支配分层方法,可以使好的个体有更大的机会遗传到下一代;适应度共享策略则使得准Pareto面上的个体均匀分布,保持了群体多样性,克服了超级个体的过度繁殖,防止了早熟收敛。流程图如下：
NSGA与简单的遗传算法的主要区别在于:该算法在选择算子执行之前根据个体之间的支配关系进行了分层。其选择算子、交叉算子和变异算子与简单遗传算法没有区别。
从图中可以看到，算法首先判断种群是否全部分级，如果已经全部分级，则在分级的基础上，使用基于拥挤策略的小生境(NIChe)技术对虚拟适应度值进行调整，并确定每个种群的虚拟适应度值，然后根据虚拟适应度值的大小，确定优先选择进行处理的种群（遗传算法）。
2.1 非支配排序
考虑一个目标函数个数为K(K>1)、规模大小为N的种群,通过非支配排序算法可以对该种群进行分层,具体的步骤如下:
通过上述步骤得到的非支配个体集是种群的第一级非支配层;然后,忽略这些标记的非支配个体,再遵循步骤(1)一(4),就会得到第二级非支配;依此类推,直到整个种群被分类。
2.2 虚拟适应度值的确定
在对种群进行非支配排序的过程中,需要给每一个非支配层指定一个虚拟适应度值。级数越大,虚拟适应度值越小;反之,虚拟适应度值越大。这样可以保证在选择操作中等级较低的非支配个体有更多的机会被选择进入下一代,使得算法以最快的速度收敛于最优区域。另一方面,为了得到分布均匀的Pareto最优解集,就要保证当前非支配层上的个体具有多样性。NSGA中引入了基于拥挤策略的小生境(NIChe)技术,即通过适应度共享函数的方法对原先指定的虚拟适应度值进行重新指定。
3、NSGAII算法
NSGA一II算法的基本思想为:首先,随机产生规模为N的初始种群,非支配排序后通过遗传算法的选择、交叉、变异三个基本操作得到第一代子代种群;其次,从第二代开始,将父代种群与子代种群合并,进行快速非支配排序,同时对每个非支配层中的个体进行拥挤度计算,根据非支配关系以及个体的拥挤度选取合适的个体组成新的父代种群;最后,通过遗传算法的基本操作产生新的子代种群:依此类推,直到满足程序结束的条件。相应的程序流程图如下图所示。
3.1 快速非支配排序算法
3.2 拥挤度和拥挤度比较算子
挤度是指种群中给定个体的周围个体的密度,直观上可表示为个体。周围仅仅包含个体。本身的最大长方形的长,用nd表示,
拥挤度的算法如下：
3.3拥挤度比较算子
三、部分代码
% function NSGA_2
clc;clear;
tic;
%% 初始化
PopSize=200;%种群大小
MaxIteration =300;%最大迭代次数
R=50;
% location1=load(‘location1_100.txt‘);%优化100个城市
% location2=load(‘A_location2_100.txt‘);
location1=load(‘location1.txt‘);
location2=load(‘location2.txt‘);
CityNum =size(location1,2);%城市数
V=CityNum;
M=2;
pc=0.8;pm=0.9;
for i=1:PopSize
chromosome(i,1:CityNum)=randperm(CityNum);
chromosome(i,CityNum+1:CityNum+2)=costfunction(chromosome(i,1:CityNum),location1,location2);
end
chromosome= non_domination_sort_mod(chromosome);%将解分 最后一列为拥挤度 倒数第二列为分级数
index=find(chromosome(:,103)==1);
costrep=chromosome(index,101:102);%第一级即非劣解
%% 主循环
pool = round(PopSize/2); %突变池规模
for Iteration=1:MaxIteration
if ~mod(Iteration,10)
fprintf(‘current iter:%d\n‘,Iteration)
disp([‘ Number of Repository Particles = ‘ num2str(size(costrep,1))]);
scro(2,m1)=tt;
end
scro_cost(1,:)=costfunction(scro(1,:),location1,location2);
scro_cost(2,:)=costfunction(scro(2,:),location1,location2);
offspring_var=[offspring_var;scro];%解
offspring_cost=[offspring_cost;scro_cost];%适应度
end
offspring_chromosome(:,1:V)=offspring_var;
offspring_chromosome(:,V+1:V+M)=offspring_cost;
main_pop = size(chromosome,1);
offspring_pop = size(offspring_chromosome,1);
intermediate_chromosome(1:main_pop,:) = chromosome;
intermediate_chromosome(main_pop + 1 :main_pop + offspring_pop,1 : M+V) = ...
offspring_chromosome;
intermediate_chromosome = ...
non_domination_sort_mod(intermediate_chromosome);
%% 选择
chromosome = replace_chromosome(intermediate_chromosome,PopSize);
index=find(intermediate_chromosome(:,103)==1);
costrep=intermediate_chromosome(index,101:102);
cost=intermediate_chromosome(:,101:102);
if ~mod(Iteration,1)
figure (1)
plot(costrep(:,1),costrep(:,2),‘r*‘,cost(:,1),cost(:,2),‘kx‘);
xlabel(‘F1‘);ylabel(‘F2‘);
title(strcat(‘Interaction ‘,num2str(Iteration), ‘ Pareto non-dominated solutions‘));
% hold on
end
if ~mod(Iteration,MaxIteration)
% if ~mod(Iteration,1)
fun_pf=costrep;
[fun_pf,~]=sortrows(fun_pf,1);
plot(fun_pf(:,1),fun_pf(:,2),‘k*-‘);
title(strcat(‘Interaction ‘,num2str(Iteration), ‘ Pareto non-dominated solutions‘));
hold on;
grid on;
end
end四、仿真结果
?
五、参考文献
[1]刘胜军,耿焕同,谢飞.新型定向交叉在NSGA-Ⅱ求解多目标TSP问题中的应用[J].电子技术与软件工程,2017(06):154.
?
?