启发式算法解决旅行商问题

A. 急求 蚁群混合遗传算法在matlab上的实现以解决TSP旅行商的问题 小弟感激不尽

建立m文件
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

%%-------------------------------------------------------------------------

%% 主要符号说明

%% C n个城市的坐标，n×2的矩阵

%% NC_max 最大迭代次数

%% m 蚂蚁个数

%% Alpha 表征信息素重要程度的参数

%% Beta 表征启发式因子重要程度的参数

%% Rho 信息素蒸发系数

%% Q 信息素增加强度系数

%% R_best 各代最佳路线

%% L_best 各代最佳路线的长度

%%=========================================================================

%%第一步：变量初始化

n=size(C,1);%n表示问题的规模（城市个数）

D=zeros(n,n);%D表示完全图的赋权邻接矩阵

for i=1:n

for j=1:n

if i~=j

D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;

else

D(i,j)=eps; %i=j时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示

end

D(j,i)=D(i,j); %对称矩阵

end

end

Eta=1./D; %Eta为启发因子，这里设为距离的倒数

Tau=ones(n,n); %Tau为信息素矩阵

Tabu=zeros(m,n); %存储并记录路径的生成

NC=1; %迭代计数器，记录迭代次数

R_best=zeros(NC_max,n); %各代最佳路线

L_best=inf.*ones(NC_max,1); %各代最佳路线的长度

L_ave=zeros(NC_max,1); %各代路线的平均长度

while NC<=NC_max %停止条件之一：达到最大迭代次数，停止

%%第二步：将m只蚂蚁放到n个城市上

Randpos=[]; %随即存取

for i=1:(ceil(m/n))

Randpos=[Randpos,randperm(n)];

end

Tabu(:,1)=(Randpos(1,1:m))'; %此句不太理解？

%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游

for j=2:n %所在城市不计算

for i=1:m

visited=Tabu(i,1:(j-1)); %记录已访问的城市，避免重复访问

J=zeros(1,(n-j+1)); %待访问的城市

P=J; %待访问城市的选择概率分布

Jc=1;

for k=1:n

if length(find(visited==k))==0 %开始时置0

J(Jc)=k;

Jc=Jc+1; %访问的城市个数自加1

end

end

%下面计算待选城市的概率分布

for k=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);

end

P=P/(sum(P));

%按概率原则选取下一个城市

Pcum=cumsum(P); %cumsum，元素累加即求和

Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线

to_visit=J(Select(1));

Tabu(i,j)=to_visit;

end

end

if NC>=2

Tabu(1,:)=R_best(NC-1,:);

end

%%第四步：记录本次迭代最佳路线

L=zeros(m,1); %开始距离为0，m*1的列向量

for i=1:m

R=Tabu(i,:);

for j=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1)); %原距离加上第j个城市到第j+1个城市的距离

end

L(i)=L(i)+D(R(1),R(n)); %一轮下来后走过的距离

end

L_best(NC)=min(L); %最佳距离取最小

pos=find(L==L_best(NC));

R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线

L_ave(NC)=mean(L); %此轮迭代后的平均距离

NC=NC+1 %迭代继续

%%第五步：更新信息素

Delta_Tau=zeros(n,n); %开始时信息素为n*n的0矩阵

for i=1:m

for j=1:(n-1)

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);

%此次循环在路径（i，j）上的信息素增量

end

Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);

%此次循环在整个路径上的信息素增量

end

Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发，更新后的信息素

%%第六步：禁忌表清零

Tabu=zeros(m,n); %%直到最大迭代次数

end

%%第七步：输出结果

Pos=find(L_best==min(L_best)); %找到最佳路径（非0为真）

Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径

Shortest_Length=L_best(Pos(1)) %最大迭代次数后最短距离

subplot(1,2,1) %绘制第一个子图形

DrawRoute(C,Shortest_Route) %画路线图的子函数

subplot(1,2,2) %绘制第二个子图形

plot(L_best)

hold on %保持图形

plot(L_ave,'r')

title('平均距离和最短距离') %标题

function DrawRoute(C,R)

%%=========================================================================

%% DrawRoute.m

%% 画路线图的子函数

%%-------------------------------------------------------------------------

%% C Coordinate 节点坐标，由一个N×2的矩阵存储

%% R Route 路线

%%=========================================================================

N=length(R);

scatter(C(:,1),C(:,2));

hold on

plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)],'g')

hold on

for ii=2:N

plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'g')

hold on

end

title('旅行商问题优化结果 ')

建m文件
function DrawRoute(C,R)

%%=========================================================================

%% DrawRoute.m

%% 画路线图的子函数

%%-------------------------------------------------------------------------

%% C Coordinate 节点坐标，由一个N×2的矩阵存储

%% R Route 路线

%%=========================================================================

N=length(R);

scatter(C(:,1),C(:,2));%画散点图

hold on

plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)],'g')

hold on

for ii=2:N

plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'g')

hold on

end

title('TSP问题优化结果 ')

命令窗口运行
C=[1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975
];
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

B. 用遗传算法 解决旅行商问题，进化1000代，结果产生新解的代数一直都在刚开始几代，而且不是最佳解，怎么解

首先，遗传算法实际使用上并不能保证得到全局最优解。
出现这种情况说明遗传算法在开始前几代已经达到并陷入一个局部解。而算法的相关参数，例如交叉，变异概率等无法使算法跳出局部解。因此可以尝试改变遗传算法的参数。

C. 想问一下什么是vrp问题，什么是tsp问题

、旅行商问题（Traveling Salesman Problem, TSP）

这个问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。

TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。

TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。

2、中国邮递员问题（Chinese Postman Problem CPP）

同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投递邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题， 因为是我国学者管梅古谷教授于1962年提出的这个问题并且给出了一个解法。

3、“一笔画”问题（Drawing by one line）

还有一个用图论语言的描述方式：平面上有n个点，用最短的线将全部的点连起来。称为“一笔画”问题。

4、配送路线问题（Route of Distribution）

TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。

TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）！。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。

5、多回路运输问题（Vehicle Routing Problem, VRP）

多回路运输问题在物流中的解释是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。

VRP问题和TSP问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了客户的需求，必须是多辆交通工具以及运输工具的行车顺序两个问题的求解。相对于TSP问题，VRP问题更复杂，求解更困难，但也更接近实际情况。

6、多个旅行商问题（Multiple TSP）

由于限制条件的增加，TSP问题可以衍生出多个旅行商问题（MTSP），就是一个出发点，m个旅行商的TSP，即所访问的客户没有需求，车辆没有装载的限制，优化目标就是要遍历所有的客户，达到总里程最短。

VRP问题是MTSP问题的普遍化，当客户的需求不仅仅是被访问，而是有一定容积和重量的商品的装载和卸载，涉及到不同种类和型号或不同载重量车辆的调度策略时，MTSP问题转换为VRP问题。

7、最近邻点法（Nearest Neighbor）

这是一种用于解决TSP问题的启发式算法。方法简单，但得到的解并不十分理想，可以作为进一步优化的初始解。求解的过程一共四步：首先从零点开始，作为整个回路的起点，然后找到离刚刚加入到回路的上一节点最近的一个节点，并将其加入到回路中。重复上一步，直到所有的节点都加入到回路中，最后，将最后一个加入的节点和起点连接起来，构成了一个TSP问题的解。

8、最近插入法（Nearest Insertion）

最近插入法是另一个TSP问题的求解方法。它的求解过程也是4步：首先从一个节点出发，找到一个最近的节点，形成一个往返式子回路；在剩下的节点中，寻找一个离子回路中某一节点最近的节点，再在子回路中找到一个弧，使弧的两端节点到刚寻找到的最近节点的距离之和减去弧长的值最小，实际上就是把新找到的节点加入子回路以后使得增加的路程最短，就把这个节点增加到子回路中。重复以上过程，直到所有的节点都加入到子回路中。最近插入法比最近邻点法复杂，但可以得到相对比较满意的解。

9、节约里程法（Saving Algorithm）

节约算法是用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。它的核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小得幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。

10、扫描算法（Sweep Algorithm）

它也是求解车辆数目不限制的VRP问题的启发式算法。求解过程同样是4步：以起始点为原点建立极坐标系，然后从最小角度的两个客户开始建立一个组，按逆时针方向将客户逐个加入到组中，直到客户的需求总量超出了车辆的载重定额。然后建立一个新的组，继续该过程，直到将全部客户都加入到组中

D. 什么是tsp问题，数学模型中的一种模型问题

Traveling Saleman Problem 旅行商问题
“旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。以42个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。多年来全球数学家绞尽脑汁，试图找到一个高效的算法，近来在大型计算机的帮助下才取得了一些进展。 TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。 TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。

具体参见网络
http://ke..com/view/1162183.htm

多个旅行商同时出发的问题称为MTSP问题。设立虚点转化为TSP即可求解。
数学模型是可以用线性规划来描述，但是在多项式求解时间内无解，所以才出现了各种启发式算法，什么遗传算法，模拟退火，蚁群算法之类的

E. 求最短路径问题 送货郎问题

最佳答案检举 模型一：利用“图”的知识，将送货点抽象为“图”中是顶点，由于街道和坐标轴平行，即任意两顶点之间都有路。在此模型中，将两点之间的路线权值赋为这两点横纵坐标之和。如A（x1，y1），B（x2，y2）两点，则权值为Q=|x2-x1|+|y2-y1|。并利用计算机程序对以上结果进行了校核。经典的Dijkstra算法和 Floyd算法思路清楚、 方法简便,但随着配送点数的增加,计算的复杂性以配送点数的平方增加,并具有一定的主观性. 所以本研究在利用动态规划法的基础上引入扑食搜索法的原理,提高辆车的装载率,从而减少车辆的需求,达到降低成本的目的.

模型二：根据题意（B题），建立动态规划的数学模型。然后用动态规划的知识求得最优化结果。

根据所建立的两个数学模型，对满足设计要求的送货策略和费用最省策略进行了模拟，在有标尺的坐标系中得到了能够反映运送最佳路线的模拟图。最后，对设计规范的合理性进行了充分和必要的论证。

快递公司送货策略

1 问题的提出

在快递公司送货策略中，确定业务员人数和各自的行走路线是本题的关键。这个问题可以描述为:一中心仓库(或配送调度中心) 拥有最大负重为25kg的业务员m人, 负责对30个客户进行货物分送工作, 客户i 的货物需求为以知 , 求满足需求的路程

最短的人员行驶路径,且使用尽量少的人数,并满足以下条件:

1) 每条配送路径上各个客户的需求量之和不超过个人最大负重。

2) 每个客户的需求必须满足, 且只能由一个人送货.

3）每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h。

4）为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克。

处于实际情况的考虑, 本研究中对人的最大行程不加限制.本论文试图从最优化的角度，建立起满足设计要求的送货的数学模型，借助于计算机的高速运算与逻辑判断能力，求出满足题意（B题）要求的结果。

2 问题的分析

2. 1根据题意（B题）的要求，每个人的工作时间不超过6小时，且必须从早上9点钟开始派送，到当天17点之前（即在8小时之内）派送完毕。

表一列出了题中任意两配送点间的距离。

表一：任意两点间的距离矩阵

因为距离是对称的，即从送货点i到送货点j的距离等于从j到i的距离。记作：di,j.

表二给出了产品的需求，为了完成配送任务，每个人在工作时间范围内，可以承担两条甚至更多的配送线路。表中给出了送货点编号，快件量T，以及送货点的直角坐标。

表二
对于上述的路线确定和费用优化问题，应用如下启发
从公司总部配出一个人，到任意未配送的送货点，然后将这个人配到最近的未服务的送货点范围之内的邻居，并使送货时间小于6小时，各送货点总重量不超过25kg。

继续上述指派，直到各点总重量超过25kg，或者送货时间大于6小时。最后业务员返回总部，记录得到的可行行程（即路线）。

对另一个业务员重复上述安排，直到没有未服务的送货点。对得到的可行的行程安排解中的每一条路径，求解一个旅行商问题，决定访问指派给每一条行程的业务员的顺序，最小化运输总距离。得到可行解的行程安排解后退出。

上面的方法通过以下两种方法实现：

（1） 每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。

（2） 每一个行程的第一个送货点是距离总部最远的未服务的送货点。然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。

然后比较两组结果，通过函数拟合即可得到最优化结果。

3 模型假设

（1）假设每个人的送货路线一旦确定，再不更改。

（2）送货期间，每个人相互之间互不影响。

（3）如果到某一个点距离最近的点不至一个，就按下面的方法进行确定：考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但路线中各点总重量加上该点的快件量超过25kg的上限时，该点舍去。如距离4最近的点有2，5，6，7四个点，其中，0-1-3-4路线易确定，且各点重量之和为 19.5kg，因此对于2，7两点，直接舍去，选5最合适。

4 符号说明

A：所有配送点的集合，A={0，1，2，3，…….，n}，其中0代表配送中心

m: 业务员人数

C：任意一点到原点（总部）的距离

C总：表示一条路线所运行的总公里数

i,j: 表示送货点，如i点，j点

K：表示K条路线

qi: 点i的需求量，q0=0，表示总部的需求量

B总K: K条路线的总运行费用

X：校核时的适应度

Xij: 业务员路线安排

5 模型的建立及求解

5.1 TSP模型的数学描述为：

其顶点集合为A

顶点间的距离为C={Cij| i,j∈N,1≤i,j≤n}

m n

min ∑ ∑ CijXij

i=1j=1

满足

n

∑ Xij=1,ⅰi=1,2,⋯n

j=1

m

∑ Xij=1,j=1,2,⋯n

j=1

Xij∈{0,1}, i=1,2⋯n,j=1,2⋯n，而根据题意，任意两点之间都有通路，即不存在Xij=0的情况。

根据上述所列的启发式方法生成一个行程安排解。每一个行程的第一个送货点是距离总部最近的未服务的送货点。

第一条行程中访问了节点0-1-3-4-5-0，是因为1距离原点最近，因此由1

出发，3是距离1点最近的点，而且两处快件量之和为14kg，小于每个人最大负重量，可以继续指配。接着，4是距离3最近的点，而且三处快件量之和为 19.5kg，仍小于25kg,还可以继续指配。在剩下未服务送货点中，5距离4最近（其实距离4最近的点有2，5，6，7四个点，然后考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但超过25kg上限的点舍去。这里2，7被舍去，故选择了5）总快件量之和为24kg。再继续扩充，发现就会超出“25kg”这个上限，因此选择返回，所以0-1-3-4-5就为第一条路线所含有的送货点。

现在0-1-3-4-5这四个送货点之间的最优访问路径安排就是一个典型的单回路问题。可以通过单回路运输模型-TSP模型求解。一般而言，比较简单的启发式算法求解TSP模型求解有最邻近法和最近插入法两种。由RosenkrantzStearns等人在1977年提出的最近插入法，能够比最近邻点法，取得更满意的解。由于0-1-3-0 已经先构成了一个子回路，现在要将节点4 插入，但是客户4有三个位置可以插入，现在分析将客户4插入到哪里比较合适:

1.插入到（0，1）间，C总= 7+4+5+1+4+9=30。

2.插入到（1，3）间，C总=5+6+4+9=24。

3.插入到（3，0）间，C总=5+4+4+11=24。

比较上述三种情况的增量，插入到（3，0）间和（1，3）间增量最小，考虑到下一节点插入时路程最小问题，所以应当将4插入到送货点3和总部0之间。接下来，用同样的方法，将5插到4和0之间，能使该条路线总路程最小，该路线总路程为32km，历时1.96667h。结果子回路为T= {0-1-3-4-5-0}.因为街道平行于坐标轴方向，所以它就是最优化路线。

第二条行程这中，由于所剩下节点中，2距离0点最近，因此由2出发，就可以找到最近点13，接着是7，然后6.这样，第二条优化路线0-2-13-7-6-0就确定了。用这种方法，依次可确定以下剩余六条路线。

具体参看如下图表三（一，二，三，……为路线编号；总重量为该路线所有

节点快件量之和）：

由启发式方法得到的可行的行程安排解一：

表三

直观的具体路线图如下：

图一

然后，根据所经历的时间进行划分，确定运送人数。在工作时间小于6小时的前提下，可作如下分类：

这样，将确定的五种组合情况分别分配给五个业务员去送即可。

这个解是第一个中间最好解。在选择可行解1每条行程中的第一个送货点时，选择了距离总部最近的未服务的点。接下去通过选择距离仓库最远的未服务的点为每条行程的第一个客户生成了可行解2。为了方便遗传算法的分析，编号将连续进行。如果继续增加的新的标签的行程和前面可行解1 中的重复，就是用原先的标签号。

由启发式方法得到的可行的行程安排解二：

表四

直观的具体路线图如下：

图二

注意：通过上述方法，最后剩两个点1，9还没有被列入路线。于是问题就出来了，如何将这两个点插入进这八条路线？

除第十条路线之外，其余各条均能将9号点纳入，而1号点没有办法纳进去，只能作为第十七条路线出现。那么，9号点应纳入哪一条呢？显然，纳入第十六条比较合适，原因是他对总路程的大小没影响，顺便可以带上。

由此可以看到，可行解2没有替代中间最优解，以总路程518km,历时25.72h高于492km和24.68h。

通过对上面的两个可行解进行交叉操作。其中每个解的行程已经按照他们送每千克快件量在每一千米的路程范围内的送货成本的大小降序重新排列，这个参数是对每一行程质量的比较好的测度。本文以此作为适应值（X）。

在对两个解中的行程进行交叉分析时，根据适应值计算的接受每条行程的概率附加到每条行程上。P(X)=Ke- λx ，然后通过设定参数对结果进行拟合。具体而言。如果一条行程的选择概率P(select)值至少和exel相应行的随机概率一样大，那么他就被选择出来可能在交叉分析中被包括进去。

在本题中，根据上述要求，求出了两种可行解，但是由于本题的特殊性（即街道和坐标轴平行），两条路径中没有相同的运行路线，也就是说最终的拟合结果就是解一的结果。因此，可行解一就是本题中的最优解。

至此，B题中的第一问已经解决了。即需要5个业务员，每个业务员的运行线路如下：

第一个人：0-1-3-4-5-0和0-18-26-28-0；

第二个人：0-2-13-7-6-0和0-19-25-24-0；

第三个人：0-10-12-8-9-0和0-16-17-20-14-0；

第四个人：0-22-32-23-15-11-0；

第五个人：0-27-29-30-0.

总的运行公里数为：C总K=32+42+42+72+68+56+88+92=492km。

5．2 下面我们求解B题中的第二个问题：

根据上面设计的最优化路线，容易算出每条路线运行费用及运行第二时间（这里的第二时间指的是在问题2中的新速度的前提下算出的）。具体参看下表五和表六：

表五

表六

从表五和表六的比较来看，解法二以总费用15241.3元和总时间27.36667h高于解一的12208.4元和26.26667h。因此我们选择了解一的优化结果。

从上表（表五）很容易看出：B总K=12208.4元。然后根据第二时间的大小，我对运行路线和人员个数做以下调整，具体参看表五。这样，就需六个人就才能完成任务。考虑到人员工作时间不能一边倒（即部分线路组合工作时间太长，部分太短）的情况，每个人的组合路线如下：

第一个人：0-1-3-4-5-0和0-19-25-24-0；

第二个人：0-2-13-7-6-0和0-10-12-8-9-0；

第三个人：0-16-17-20-14-0；

第四个人：0-22-32-23-15-11-0；

第五个人：0-18-26-28-0；

第六个人：0-27-29-30-0。

F. 采用准确优化技术和启发式优化技术解决一个问题会存在什么不同

采用准确优化技术和启发式优化技术解决一个问题会存在的不同之处：

①确定性算法和随机性算法是目前求解优化问题的方法。随机性算法一般是对社会行为和自然现象的模拟，具有对优化函数的解析性质要求低的特点，甚至对无显示解析表达式的问题也可以求解，能较好解决优化中的噪声、不可微、高维等问题。

②启发式算法作为随机性算法的一种，其良好的应用更加快了人们对各种优化方法的探索脚步。 近些年来不断有学者将分形应用于优化中来，试图运用分形思想来处理复杂的优化问题。

③其中，分形算法通过对可行域的分形分割来寻优，是一种新颖的确定性算法，但其局限性较大，只适用于低维简单的问题，对于当今社会中高维复杂问题则几乎无能为力，也使得该算法的影响力微乎其微。

④启发式技术是基于特征值扫描技术上的升级,与传统反病毒特征值扫描技术相比,优点在于对未知病毒的防御.是特征值识别技术质的飞跃。

(6)启发式算法解决旅行商问题扩展阅读

启发式：简化虚拟机和简化行为判断引擎的结合 Heuristic(启发式技术=启发式扫描+启发式监控) 重点在于特征值识别技术上的更新、解决单一特征码比对的缺陷.目的不在于检测所有的未知病毒,只是对特征值扫描技术的补充.主要针对：木马、间谍、后门、下载者、已知病毒(PE病毒)的变种。

一、启发式发展方向

现代启发式算法的研究,在理论方面还处于不断发展中,新思想和新方法仍不断出现。分析目前的现状和发展方向,其发展方向有如下几个方面:

①整理归纳分散的研究成果,建立统一的算法体系结构。

②在现有的数学方法(模式定理、编码策略、马尔可夫链理论、维数分析理论、复制遗传算法理论、二次动力系统理论、傅立叶分析理论、分离函数理论、Walsh函数分析理论)的基础上寻求新的数学工具。

③开发新的混合式算法及开展现有算法改进方面的研究。

④研究高效并行或分布式优化算法。

二、启发式算法算法机制特点

现代启发式算法在优化机制方面存在一定的差异,但在优化流程上却具有较大的相似性,均是一种“邻域搜索”结构。算法都是从一个(一组)初始解出发,在算法的关键参数的控制下通过邻域函数产生若干邻域解,按准则(确定性、概率性或混沌方式)更新当前状态,而后按关键参数修改准则调整关键参数，一直优化到最优结果。

G. 想用动态规划算法解决旅行商（TSP）问题，麻烦指点下方法和思路，详细点，谢谢1

http://hi..com/__%D2%E5__/blog/item/d6326f1fcbdb4eff1ad576d8.html
http://liouwei20051000285.blog.163.com/blog/static/25236742009112242726527/
以上都是动态规划解决TSP问题的，但是个人觉得不是太好，建议你去了解一下遗传算法，很容易懂，网上有很详细的讲解。希望你学到知识

H. 旅行商问题的问题解法

旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP-Complete的问题，所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种：
1、途程建构法（Tour Construction Proceres）
从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：
1）最近邻点法（Nearest Neighbor Procere）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。
2）节省法（Clark and Wright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。
3）插入法（Insertion proceres）：如最近插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。
2、途程改善法（Tour Improvement Procere）
先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：
1）K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代目前路径中K条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。
2）Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止。
3、合成启发法（Composite Procere）
先由途程建构法产生起始途程，然后再使用途程改善法去寻求最佳解，又称为两段解法（two phase method）。有以下几种解法：
1）起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。
2）起始解求解+3-Opt：以途程建构法建立一个起始的解，再用3-Opt的方式改善途程，直到不能改善为止。

I. 想问一下什么是vrp问题，什么是tsp问题

、旅行商问题（TRAVELING SALESMAN PROBLEM, TSP） 这个问题字面上的理解是：有一个推销员，要到N个城市推销商品，他要找出一个包含所有N个城市的具有最短路程的环路。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。 TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。 2、中国邮递员问题（CHINESE POSTMAN PROBLEM CPP） 同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投递邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题， 因为是 国学者管梅古谷教授于1962年提出的这个问题并且给出了一个解法。 3、“一笔画”问题（DRAWING BY ONE LINE） 还有一个用图论语言的描述方式：平面上有N个点，用最短的线将全部的点连起来。称为“一笔画”问题。 4、配送路线问题（ROUTE OF DISTRIBUTION） TSP问题在物流中的描述是对应一个物流配送公司，欲将N个客户的订货沿最短路线全部送到。如何确定最短路线。 TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是N个点的所有排列的集合，大小为（N-1）！。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。 5、多回路运输问题（VEHICLE ROUTING PROBLEM, VRP） 多回路运输问题在物流中的解释是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。 VRP问题和TSP问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了客户的需求，必须是多辆交通工具以及运输工具的行车顺序两个问题的求解。相对于TSP问题，VRP问题更复杂，求解更困难，但也更接近实际情况。 6、多个旅行商问题（MULTIPLE TSP） 由于限制条件的增加，TSP问题可以衍生出多个旅行商问题（MTSP），就是一个出发点，M个旅行商的TSP，即所访问的客户没有需求，车辆没有装载的限制，优化目标就是要遍历所有的客户，达到总里程最短。 VRP问题是MTSP问题的普遍化，当客户的需求不仅仅是被访问，而是有一定容积和重量的商品的装载和卸载，涉及到不同种类和型号或不同载重量车辆的调度策略时，MTSP问题转换为VRP问题。 7、最近邻点法（NEAREST NEIGHBOR） 这是一种用于解决TSP问题的启发式算法。方法简单，但得到的解并不十分理想，可以作为进一步优化的初始解。求解的过程一共四步：首先从零点开始，作为整个回路的起点，然后找到离刚刚加入到回路的上一节点最近的一个节点，并将其加入到回路中。重复上一步，直到所有的节点都加入到回路中，最后，将最后一个加入的节点和起点连接起来，构成了一个TSP问题的解。 8、最近插入法（NEAREST INSERTION） 最近插入法是另一个TSP问题的求解方法。它的求解过程也是4步：首先从一个节点出发，找到一个最近的节点，形成一个往返式子回路；在剩下的节点中，寻找一个离子回路中某一节点最近的节点，再在子回路中找到一个弧，使弧的两端节点到刚寻找到的最近节点的距离之和减去弧长的值最小，实际上就是把新找到的节点加入子回路以后使得增加的路程最短，就把这个节点增加到子回路中。重复以上过程，直到所有的节点都加入到子回路中。最近插入法比最近邻点法复杂，但可以得到相对比较满意的解。 9、节约里程法（SAVING ALGORITHM） 节约算法是用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。它的核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小得幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。 10、扫描算法（SWEEP ALGORITHM） 它也是求解车辆数目不限制的VRP问题的启发式算法。求解过程同样是4步：以起始点为原点建立极坐标系，然后从最小角度的两个客户开始建立一个组，按逆时针方向将客户逐个加入到组中，直到客户的需求总量超出了车辆的载重定额。然后建立一个新的组，继续该过程，直到将全部客户都加入到组中

记得采纳啊