当前位置：文档库 › 粒子群优化算法车辆路径问题

粒子群优化算法车辆路径问题

粒子群优化算法计算车辆路径问题

摘要

粒子群优化算法中,粒子群由多个粒子组成,每个粒子的位置代表优化问题在D 维搜索空间中潜在的解。根据各自的位置,每个粒子用一个速度来决定其飞行的方向和距离,然后通过优化函数计算出一个适应度函数值(fitness)。粒子是根据如下三条原则来更新自身的状态:(1)在飞行过程中始终保持自身的惯性;(2)按自身的最优位置来改变状态;(3)按群体的最优位置来改变状态。本文主要运用运筹学中粒子群优化算法解决车辆路径问题。车辆路径问题由Dan tzig 和Ram ser 于1959年首次提出的, 它是指对一系列发货点(或收货点) , 组成适当的行车路径, 使车辆有序地通过它们, 在满足一定约束条件的情况下, 达到一定的目标(诸如路程最短、费用最小, 耗费时间尽量少等) , 属于完全N P 问题, 在运筹、计算机、物流、管理等学科均有重要意义。粒子群算法是最近出现的一种模拟鸟群飞行的仿生算法, 有着个体数目少、计算简单、鲁棒性好等优点, 在各类多维连续空间优化问题上均取得非常好的效果。本文将PSO 应用于车辆路径问题求解中, 取得了很好的效果。

针对本题，一个中心仓库、7个需求点、中心有3辆车，容量均为1，由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。

1233,1,7.

k q q q l =====货物需求

量12345670.89,0.14,0.28,0.33,0.21,0.41,0.57g g g g g g g =======，

且

x i k g q ≤。利用matlab 编程，求出需求点和中心仓库、需求点之间的各

个距离，用ij c 表示。求满足需求的最小的车辆行驶路径，就是求m i n i j i j k

Z c x =∑∑∑。经过初始化粒子群，将初始的适应值作为每个粒子的个

体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。本题的最短路径由计算可知为217.81。

关键字：粒子群算法、车辆路径、速度

一、问题的重述

一个中心仓库序号为0，7个需求点序号为1~7，其位置坐标见表1，中心有3辆车，容量均为1，由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。求满足需求的距离最小的车辆行驶路径。

表1 仓库中心坐标和需求点坐标及需求量

二、问题假设

1．现实生活中中心仓库以及各个需求点之间军事直线连接，两点之间距离即为坐标系中两点坐标间距离。

2．不因天气及失火等原因车辆停止运输。

3．每个需求点由一辆车供应货物。

三、符号说明

四、问题分析

4.1算法分析

车辆路径问题（VRP ）可以描述为有一个中心仓库，拥有K 辆车，容量分别为),,2,1(K k q k =，负责向L 个需求点配送货物，货物需求量为

),,2,1(L i g i =，且k i q g m ax m ax ≤；ij c 表示从点i 到j 的距离。求满足需求的

距离最小的车辆行驶路径。

将中心仓库编号为0，需求点编号为1，2，…，L 。数学模型为:

min ij ijk i

Z c x =∑∑∑

s.t.k q y g i

k ki i ?≤∑,

L i y

,,2,1,1 ==∑ k L j y x

kj i

ijk

?==∑;,,1,0, k L i y x

ki j

ijk

?==∑;,,1,0,

S x X ijk ∈=)( k L j i x ijk ?==;,,1,0,,10 或

k L i y ki ?==;,,1,0,10 或其中，??

?=否则

车配送由需求点0

k i y ki ，??

?=否则

行驶驶从车1j i k x ijk 在本题中，

1233,1,7.

k q q q l =====货物

需

求

量

12345670.89,0.14,0.28,0.33,0.21,0.41,0.57g g g g g g g =======，利用粒子群

优化算法，经过初始化粒子群，将初始的适应值作为每个粒子的个体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。 4.2举例具体演算分析

例如, 设VRP 问题中发货点任务数为7, 车辆数为3, 若某粒子的位置向量X 为:

发货点任务号: 1 2 3 4 5 6 7 X v : 1 2 2 2 2 3 3 X r : 1 4 3 1 2 2 1 则该粒子对应解路径为: 车1: 0 → 1 → 0

车2: 0 → 4 →5 → 3→ 2→ 0 车3: 0 → 7→ 6→ 0

粒子速度向量V 与之对应表示为V v 和V r

该表示方法的最大优点是使每个发货点都得到车辆的配送服务, 并限制每个发货点的需求仅能由某一车辆来完成, 使解的可行化过程计算大大减少Z 虽然该表示方法的维数较高, 但由于PSO 算法在多维寻优问题有着非常好的特性, 维数的增加并未增加计算的复杂性, 这一点在实验结果中可以看到

五、模型的建立与求解

在本题中，需要分别计算以下几个内容，计算需求点与中心仓库及各需求点间距离，利用粒子群优化算法，求出函数的全局最优位置和最后得到的优化极值。

5.1需求点与中心仓库及各需求点间距离

利用直角三角形勾股定理，求斜边长度。1122(,)(,)A x y B x y ，，直角坐标系

中求A,B 两点之间距离AB =

5.2粒子群优化算法 5.2.1算法实现过程步骤1 初始化粒子群

① 粒子群划分成若干个两两相互重叠的相邻子群;

② 每个粒子位置向量X v 的每一维随机取1～ K (车辆数) 之间的整数, X r 的每一维随机取1～L (发货点任务数) 之间的实数;

③ 每个速度向量V v 的每一维随机取- (K - 1)～ (K - 1) (车辆数) 之间的整数,V r 的每一维随机取- (L - 1)～ (L - 1) 之间的实数; ④ 用评价函数Eval 评价所有粒子;

⑤ 将初始评价值作为个体历史最优解P i , 并寻找各子群内的最优解P l 和

总群体内最优解P g

步骤2重复执行以下步骤, 直到满足终止条件或达到最大迭代次数

①对每一个粒子, 计算V v、V r; 计算X v、X r, 其中X v 向上取整; 当V 、X 超过其范围时按边界取值

②用评价函数E va l 评价所有粒子;

③若某个粒子的当前评价值优于其历史最优评价值, 则记当前评价值为该历史最优评价值, 同时将当前位置向量记为该粒子历史最优位置P i;

④寻找当前各相邻子群内最优和总群体内最优解, 若优于历史最优解则更新P l、P g

5.2.2针对本题

0表示中心仓库, 设车辆容量皆为q= 1. 0, 由3辆车完成所有任务，初始化群体个数n= 40; 惯性权重w = 0. 729;学习因子c1= c2= 1. 49445; 最大代数

MaxDT=；搜索空间维数（未知数个数）7;

算法得到的最优值的代数及所得到的最优解，预计迭代次数50，共进行20次运算

从实验结果分析，15次达到已知最优解，得到的最优总路径为：

→→→→→→→→→→

0760*******

对应的行车路线为：

车辆一：0760

→→→

车辆二：010

→→

车辆三:023450

→→→→→

行车总距离217.81

粒子群优化算法达到最优路径50次的代数

六、模型的评价

粒子群优化算法结果分析

分析PSO 方法, 可以看出它与GA 等其他演化算法的最大不同在于

1) 迭代运算中只涉及到初等运算, 且运算量非常少;

2) 每个粒子能直接获取群体历史经验和个体历史经验, 比在其他方法中使用精英集(elit ism ) 的方法更有效;

3) 整个粒子群被划分为几个的子群, 且子群之间有一定重叠, 从而使收敛于局部最优解的几率大大减少L

正因为如此, 本文将PSO 应用于带时间窗车辆路径问题求解中, 取得了很好的效果, 有着运算速度快、解的质量与个体数目相关性小、所获得的解质量高等诸多优点

七、模型的改进和推广

7.1模型的改进

针对粒子群优化算法存在的问题，提出了一种新的改进算法—基于粒子进化的多粒子群优化算法。该算法采用局部版的粒子群优化方法，从“粒子进化”和“多种群”两个方面对标准粒子群算法进行改进。多个粒子群彼此独立地搜索解空间，保持了粒子种群的多样性，从而增强了全局搜索能力而适当的“粒子进化”可以使陷入局部最优的粒子迅速跳出，有效的避免了算法“早熟”，提高了算法的稳定性。

将基于粒子进化的多粒子群优化算法用于求解非线性方程组。该算法求解精度高、收敛速度快，而且克服了一些算法对初值的敏感和需要函数可导的困难，能较快地求出复杂非线性方程组的最优解。数值仿真结果显示了该算法的有效性和可行性，为求解非线性方程组提供了一种实用的方法。

7.2模型的推广

作为物流系统优化中的重要一环，合理安排车辆路径、进行物流车辆优化调度可以提高物流经济效益、实现物流科学化。粒子群算法在多维寻优中有着非常好的特性，加入“邻居算子”的粒子群算法能使算法更好的全局寻优。本文的研究表明，改进局部办粒子群算法，能过有效地解决车辆路径问题。

八、参考文献

[1] 李军, 郭耀煌. 物流配送车辆优化调度理论与方法[M ]. 北京: 中国物资出版社, 2001.

[2] 马炫，彭芃，刘庆. 求解带时间窗车辆路径问题的改进粒子群算法.计

算机工程与应用，2009，45（27）：200-202

[3]姜启源，《数学建模》，高教出版社，2000年

附录

需求点与中心仓库及各需求点间距离

c=[];

zuobiao=[18 54

22 60

58 69

71 71

83 46

91 38

24 42

18 40];

for i=1:8

for j=1:8

c(i,j)=sqrt((zuobiao(j,2)-zuobiao(i,2))^2+(zuobiao(j,1)-zuobiao(i,1)) ^2);

end

粒子群优化算法求解

主算法

clear all;

clc;

format long;

%------给定初始化条件----------------------------------------------

c1=1.4962; %学习因子1

c2=1.4962; %学习因子2

w=0.7298; %惯性权重

MaxDT=50; %最大迭代次数

D=7; %搜索空间维数（未知数个数）

N=40; %初始化群体个体数目

%------初始化种群的个体(可以在这里限定位置和速度的范围)------------

for i=1:N

for j=1:D

x1(i,j)=ceil(3*rand()); %随机初始化位置ceil 是向离它最近的大整数圆整 x2(i,j)=ceil(7*rand());

v1(i,j)=2*(2*rand()-1); %随机初始化速度

%v2(i,j)=6*(2*rand()-1);

end

%------先计算各个粒子的适应度，并初始化Pbest和gbest---------------------- for i=1:N

y1(i,:)=x1(i,:);

y2(i,:)=x2(i,:);

pbest(i)=fitness(y1(i,:),y2(i,:),D);

end

pg1=x1(1,:); %Pg为全局最优

pg2=x2(1,:);

for i=2:N

if fitness(x1(i,:),x2(i,:),D)

pg1=x1(i,:);

pg2=x2(i,:);

gbest=fitness(pg1,pg2,D);

end

%------进入主要循环，按照公式依次迭代，直到满足精度要求------------

for t=1:MaxDT

for i=1:N

v1(i,:)=w*v1(i,:)+c1*rand*(y1(i,:)-x1(i,:))+c2*rand*(pg1-x1(i,:));

x1(i,:)=x1(i,:)+v1(i,:);

x1(i,:)=ceil(x1(i,:));

for j=1:D

if x1(i,j)<1

x1(i,j)=1;

end

if x1(i,j)>3

x1(i,j)=3;

end

for j=1:D

x2(i,j)=ceil(7*rand());

end

if fitness(x1(i,:),x2(i,:),D)

y1(i,:)=x1(i,:);

y2(i,:)=x2(i,:);

pbest(i)=fitness(y1(i,:),y2(i,:),D);

end

if pbest(i)

pg1=x1(i,:);

pg2=x2(i,:);

end

%------最后给出计算结果

disp('*************************************************************') disp('函数的全局最优位置为：')

Solution1=pg1

Solution2=pg2

disp('最后得到的优化极值为：')

Result=fitness(pg1,pg2,D)

disp('*************************************************************') 辅助算法一

function result=fitness(x1,x2,D);

aa=[inf inf inf inf inf inf inf];

bb=[inf inf inf inf inf inf inf];

cc=[inf inf inf inf inf inf inf];

for i=1:D

if x1(i)==1

aa(i)=x2(i);

else if x1(i)==2

bb(i)=x2(i);

else

cc(i)=x2(i);

end

result=f(cc)+f(bb)+f(aa);

辅助算法二

function ff=f(x);

load c.mat

sum=0;

[y ind]=sort(x);

for i=1:7

if y(i)==inf

j=i-1;

break;

else

j=7;

end

if j<1

sum=inf;

else if j==1

sum=sum+2*c(1,ind(j)+1);

else

sum=sum+c(1,ind(j)+1)+c(1,ind(1)+1); for i=1:j-1

sum=sum+c(ind(i)+1,ind(i+1)+1); end

end

ff=sum;

改进的粒子群优化算法

第37卷第4期河北工业大学学报2008年8月V ol.37No.4JOURNAL OF HEBEI UNIVERSITY OF TECHNOLOGY August2008 文章编号：1008-2373(2008)04-0055-05 改进的粒子群优化算法宋洁，董永峰，侯向丹，杨彦卿（河北工业大学计算机科学与软件学院，天津300401）摘要粒子群优化算法是一种基于群体的自适应搜索优化算法，存在后期收敛慢、搜索精度低、容易陷入局部极小等缺点，为此提出了一种改进的粒子群优化算法，从初始解和搜索精度两个方面进行了改进，提高了算法的计算精度，改善了算法收敛性，很大程度上避免了算法陷入局部极小．对经典函数测试计算，验证了算法的有效性．关键词粒子群优化算法；均匀化；变量搜索；初始解；搜索精度中图分类号TP391文献标识码A A Modified Particle Swarm Optimization Algorithm SONG Jie,DONG Yong-feng,HOU Xiang-dan,Y ANG Yan-qing (School of Computer Science and Engineering,Hebei University of Technology,Tianjin300401,China) Abstract Particle Swarm Optimization Algorithm is a kind of auto-adapted search optimization based on community. But the standard particle swarm optimization is used resulting in slow after convergence,low search precision and easily leading to local minimum.A new Particle Swarm Optimization algorithm is proposed to improve from the initial solution and the search precision.The obtained results showed the algorithm computation precision and the astringency are im- proved,and local minimum is avoided.The experimental results of classic functions show that the improved PSO is ef- ficient and feasible. Key words PSO；average；variable search；initial solution；search accuracy 0引言粒子群优化（Particle Swarm Optimization，PSO）算法是一种基于群体的随机优化技术，最早在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart[1]共同提出，基本思想源于对鸟群觅食行为的研究．PSO将每个可能产生的解都表述为群中的一个微粒，每个微粒都具有自己的位置向量和速度向量，和一个由目标函数决定的适应度，通过类似梯度下降算法使各粒子向适应度函数值最高的方向群游．该算法控制参数少、程序相对简单，因此在应用领域表现出了很大的优越性．由于PSO算法容易理解、易于实现，所以PSO算法发展很快．目前，多种PSO改进算法已广泛应用于函数优化、神经网络训练、模式识别、模糊系统控制以及其他的应用领域．许多学者对PSO算法进行研究，发现其容易出现早熟、最优解附近收敛慢等现象，并提出了一些改进方案，例如自适应PSO算法、混合PSO算法、杂交PSO算法等[2-4]．因此，本文从初始解和收敛精度两个角度出发对PSO算法进行了改进，提高了算法的计算精度，有效的改善了算法的优化性能． 1基本PSO算法 PSO算法是一种基于群体的随机优化技术，基本思想源于对鸟群觅食行为的研究．通过对鸟群飞行时经常会突然改变方向、散开、聚集，但整体总保持一致性，个体与个体间鸟群好像在一个中心的控制收稿日期：2008-04-17 基金项目：河北省自然科学基金（F2006000109）作者简介：宋洁（1967-），女（汉族），副教授．

基于粒子群优化算法的图像分割

安康学院学年论文（设计）题目_____________________________________________ 学生姓名_______________ 学号_____________________________ 所在院（系）_______________________________________ 专业班级__________________________________________________ 指导教师_____________________________________________ 年月曰

基于粒子群优化算法的图像分割（作者：）（）指导教师：【摘要】本文通过对粒子群优化算法的研究，采用Java编程，设计出一套用于图像分割的系统。基于粒子群优化算法的图像分割系统，可以将一幅给定的图像进行分割，然后将分割结果保存。图像分割的目的是将感兴趣的区域从图像中分割出来，从而为计算机视觉的后续处理提供依据。图像分割的方法有多种，阈值法因其实现简单而成为一种有效的图像分割方法。而粒子群优化（PSO）算法是一类随机全局优化技术，它通过粒子间的相互作用发现复杂搜索空间中的最优区域缩短寻找阈值的时间。因此，基于粒子群优化算法的图像分割以粒子群优化算法为寻优工具，建立具有自适应和鲁棒性的分割方法。从而可以在最短的时间内，准确地确定分割阈值。关键词：粒子群优化（PSO，图像分割，阈值法，鲁棒性 Abstract T his paper based on the particle swarm optimizati on algorithm, desig ns a set of system for image segme ntati on using Java program min g. Image segme ntati on system based on particle swarm optimizati on algorithm, the image can be a given segmentation, and then the segmentation results would be saved. Image segmentation is the purpose of the interested area from the image, thus providing the basis for the subsequent processing of computer vision. There are many methods of image segmentation, threshold method since its simple realization, becomes a kind of effective method in image segmentation. Particle swarm optimization （PSO） algorithm is a stochastic global optimization technique; it finds optimal regions of complex search spaces for threshold time shorte ned through the in teractio n betwee n particles. Therefore, particle swarm optimization algorithm of image segmentation based on particle swarm optimization algorithm based on optimizati on tools; establish segme ntati on method with adaptive and robust. Therefore, it is possible for us in the shortest possible time to accurately determ ine the segme ntati on threshold. Key word s: PSO, image segmentation, threshold method, robust. 1引言 1.1研究的背景和意义技术的不断向前发展，人们越来越多地利用计算机来获取和处理视觉图像信息。据统计，人类

车辆路径优化问题的均衡性

!""#$%%%&%%’( )#$$&***+,#清华大学学报-自然科学版. /012345678329-":2;0<:5.= *%%>年第(>卷第$$期 *%%>=?@A B(>=#@B$$ +C,+C $C(’&$C(D 车辆路径优化问题的均衡性但正刚=蔡临宁=杜丽丽=郑力 -清华大学工业工程系=北京$%%%D(. 收稿日期E*%%’&%>&%F 基金项目E国家自然科学基金资助项目-F%*%$%%D. 作者简介E但正刚-$C F D&.=男-汉.=重庆=博士研究生G 通讯联系人E蔡临宁=副教授=H&I72A E:72A3J K1234567B.$$&$C(’&%( P Q R ST R U R V W X V YQ Z[\]^]\X W U] _Q‘[X V Ya_Q T U]b c d ef g h i j j k i j=l d m n o i i o i j=c pn o q o=f r s e t n o -u]a R_[b]V[Q Z v V S‘w[_X R U x V Y X V]]_X V Y=y w X V Y\‘R z V X^]_w X[{= |]X}X V Y~!!!"#=$\X V R. %T w[_R W[EO37A4@&2K5I’71L<9:G 本文利用文9F:的)A7&*<&-&245K-)&-.算法=并结合打包原则和装配线线均衡算法的思想=设计出一种新的启发式算法;;/01算法来解决?78配送均衡问题G ~模型建立对于带有容积限制的?78问题=在图<=->= ?.上=>=@A%=A$=B=A C D代表节点集合=A%代表停车场=A E -E=$=B=C.代表第E个客户=每个客户的需求为F E G对客户进行服务的车辆数为G=每辆车的容积为H G G对于图<的每条弧-A E=A I.J?=都有一个费用或距离值K E I G若两点间没有弧-A E=A I.相连= 则相应K E I 值为无穷大G该问题的可行解是=所有点被服务且仅被服务$次=每条路径都开始和终止于A%=每辆车的负载不超过车辆的容积H G G具体数学模型如下E I23L=M E M I M G K E I N E I G B-$. M E F E O G E P H G=QG B-*. M G O G E=$=E=$=B=C B-+. O G E=%或$=E=%=$=B=C M QG= 点E任务由车辆G完成为$=否则为%B-(. N E I G=%或$=E=I=%=$=B=C M QG= 车辆G从E到I为$=否则为%B-’. 式-*.表示某单一路线的总运输量不超过车辆的承载量=式-+.表示一个需求点仅被一辆车服务G 本文假设E$.车辆行驶时间与行驶路线长度成线性关系=可简单按一定比例折算M*.车辆到达每个需求点仅执行卸载操作M+.在工作时间约束范围内=每辆车仅完成一个回路M(.某单一路线的总运　万方数据

粒子群优化算法综述

粒子群优化算法综述摘要：本文围绕粒子群优化算法的原理、特点、改进与应用等方面进行全面综述。侧重于粒子群的改进算法，简短介绍了粒子群算法在典型理论问题和实际工业对象中的应用，并给出了粒子群算三个重要的网址，最后对粒子群算做了进一步展望。关键词；粒子群算法；应用；电子资源；综述 0.引言粒子群优化算法]1[(Particle Swarm Optimization ，PSO)是由美国的Kenned 和Eberhar 于1995年提出的一种优化算法,该算法通过模拟鸟群觅食行为的规律和过程，建立了一种基于群智能方法的演化计算技术。由于此算法在多维空间函数寻优、动态目标寻优时有实现容易，鲁棒性好，收敛快等优点在科学和工程领域已取得很好的研究成果。 1. 基本粒子群算法]41[- 假设在一个D 维目标搜索空间中，有m 个粒子组成一个群落，其中地i 个粒子组成一个D 维向量，),,,(21iD i i i x x x x =，m i ,2,1=，即第i 个粒子在D 维目标搜索空间中的位置是i x 。换言之，每个粒子的位置就是一个潜在的解。将i x 带入一个目标函数就可以计算出其适应值，根据适应值得大小衡量i x 的优劣。第i 个粒子的飞翔速度也是一个D 维向量，记为),,,(21iD i i i v v v v =。记第i 个粒子迄今为止搜索到的最优位置为),,,(21iD i i i p p p p =，整个粒子群迄今为止搜索到的最优位置为),,,(21gD gi g g p p p p =。粒子群优化算法一般采用下面的公式对粒子进行操作

)()(22111t id t gd t id t id t id t id x p r c x p r c v v -+-+=+ω (1) 11+++=t id t id t id v x x (2) 式中，m i ,,2,1 =；D d ,,2,1 =；ω是惯性权重， 1c 和2c 是非负常数，称为学习因子， 1r 和2r 是介于]1,0[间的随机数；],[max max v v v id -∈，max v 是常数，由用户设定。 2. 粒子群算法的改进与其它优化算法一样PSO 也存在早熟收敛问题。随着人们对算法搜索速度和精度的不断追求，大量的学者对该算法进行了改进，大致可分为以下两类：一类是提高算法的收敛速度；一类是增加种群多样性以防止算法陷入局部最优。以下是对最新的这两类改进的总结。 2.1.1 改进收敛速度量子粒子群优化算法]5[:在量子系统中，粒子能够以某一确定的概率出现在可行解空间中的任意位置，因此，有更大的搜索范围，与传统PSO 法相比，更有可能避免粒子陷入局部最优。虽然量子有更大的搜索空间，但是在粒子进化过程中，缺乏很好的方向指导。针对这个缺陷，对进化过程中的粒子进行有效疫苗接种，使它们朝着更好的进化方向发展，从而提高量子粒子群的收敛速度和寻优能力。文化粒子群算法]6[:自适应指导文化PSO 由种群空间和信念空间两部分组成。前者是基于PSO 的进化，而后者是基于信念文化的进化。两个空间通过一组由接受函数和影响函数组成的通信协议联系在一起，接受函数用来收集群体空间中优秀个体的经验知识；影响函数利用解决问题的知识指导种群空间进化；更新函数用于更新信念空间；

时间窗车辆路径问题【带有时间窗约束的车辆路径问题的一种改进遗传算法】

系统管理学报第１９卷不同，文献［６］中１００，本文３０；③文献［６］中没有给出２０次求解中有多少次求得最优解，本文算法在软硬２种时间窗下，求得最优解的概率分别为９０％和７５％。由此可以看出本文算法具有较快的收敛速度和较高的稳定性。表２实例ｌ。软时间窗下算法运行结果第２个实例［６］，该问题有８个客户，顾客的装货或卸货的时间为Ｔｉ，一般将ｔ作为车辆的行驶时间的一部分计算费用，ｇｆ和［ｎ，，６ｉ］的含义同前，具体数据见表４。这些任务由仓库发出的容量为８ｔ的车辆来完成，车辆行驶速度为５０，仓库以及各个顾客之间的距离见表５。６），达到最优解的概率为８０％，其最终结果与文献［６］中相同最优解其费用值为９１０，对应的子路径

为（Ｏ一３一ｌ一２—０）、（Ｏ一６—４一Ｏ）、（Ｏ一８—５—７一Ｏ）。然而，文献［６］是在ｍａｘｇｅｎ＝５０、ｐｏｐｓｉｚｅ一２０的情况下，达到最优解的概率为６７％。这又说明了本文算法的有效性。表６实例２的算法运行结果４结语尽管用带有子路径分隔符的自然数编码作为遗传算法解决ＶＲＰＴＷ问题的编码方式有其优点，但缺陷也是显而易见的，为了弥补该缺陷，本文去掉了子路径中的分隔符，并采用Ｓｐｌｉｔ作为解码方式，就此设计了求解ＶＲＰＴＷ的遗传算法，并进行了数值试验的对比分析，试验结果表明，该算法是十分有

效的。参考文献ＤａｎｔｚｉｑＧ，ＲａｍｓｅｒＪ．Ｔｈｅｔｒｕｃｋｄｉｓｐａｔｃｈｉｎｇｐｒｏｂｌｅｍ［Ｊ］．Ｍａｎａｇｅｍｅｎｔｓｃｉｅｎｃｅ，１９５９，１３（６）８０一９１．谢秉磊，李军，郭耀煌．有时间窗的非满载车辆调度问题的遗传算法［Ｊ］．系统工程学报，２０００，１５（３）２９０一２９４．宋伟刚，张宏霞，佟玲．有时间窗约束非满载车辆调度问题的遗传算法［Ｊ］．系统仿真学报，２００５，１７（１１）２５９３—２５９７．刘诚，陈治亚，封全喜．带软时间窗物流配送车辆路径问题的并行遗传算法

车辆路径问题

一、车辆路径问题描述和建模 1. 车辆路径问题车辆路径问题（Vehicle Routing Problem, VRP ）,主要研究满足约束条件的最优车辆使用方案以及最优化车辆路径方案。定义：设G={V,E}是一个完备的无向图，其中V={0,1,2…n}为节点集，其中0表示车场。V ,={1,2,…n}表示顾客点集。A={(i,j),I,j ∈V,i ≠j}为边集。一对具有相同装载能力Q 的车辆从车场点对顾客点进行配送服务。每个顾客点有一个固定的需求q i 和固定的服务时间δi 。每条边（i,j ）赋有一个权重，表示旅行距离或者旅行费用c ij 。标准车辆路径问题的优化目标为：确定一个具有最小车辆数和对应的最小旅行距离或者费用的路线集，其满足下列约束条件： ⑴每一条车辆路线开始于车场点，并且于车场点约束； ⑵每个顾客点仅能被一辆车服务一次 ⑶每一条车辆路线总的顾客点的需求不超过车辆的装载能力Q ⑷每一条车辆路线满足一定的边约束，比如持续时间约束和时间窗约束等。 2.标准车辆路径的数学模型: 对于车辆路径问题定义如下的符号： c ij ：表示顾客点或者顾客点和车场之间的旅行费用等 d ij ：车辆路径问题中，两个节点间的空间距离。 Q ：车辆的最大装载能力 d i ：顾客点i 的需求。 δi ：顾客点i 的车辆服务时间 m:服务车辆数，标准车辆路径问题中假设所有的车辆都是同型的。 R ：车辆集，R={1,2….，m} R i :车辆路线，R i ={0，i 1,…i m ,0},i 1,…i m ?V ,,i ?R 。一般车辆路径问题具有层次目标函数，最小化车辆数和最小化车辆旅行费用，在文献中一般以车辆数作为首要优化目标函数，在此基础上使得对应的车辆旅行费用最小，下面给出标准车辆路径问题的数学模型。下面给出标准车辆路径问题的数学模型。对于每一条弧（I,j ）,定义如下变量: x ijv = 1 若车辆v 从顾客i 行驶到顾客点j 0 否则 y iv = 1 顾客点i 的需求由车辆v 来完成0 否则车辆路径问题的数学模型可以表述为： minF x =M x 0iv m i=1n i=1+ x ijv m v=1n j=0n i=0.c ij (2.1) x ijv n i=0m v=1≥1 ?j ∈V , (2.2)

粒子群算法综述

粒子群算法综述【摘要】：粒子群算法(pso)是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已得到广泛研究和应用。为了进一步推广应用粒子群算法并为深入研究该算法提供相关资料，本文对目前国内外研究现状进行了全面分析，在论述粒子群算法基本思想的基础上，围绕pso的运算过程、特点、改进方式与应用等方面进行了全面综述，并给出了未来的研究方向展望。【关键词】：粒子群算法优化综述优化理论的研究一直是一个非常活跃的研究领域。它所研究的问题是在多方案中寻求最优方案。人们关于优化问题的研究工作，随着历史的发展不断深入，对人类的发展起到了重要的推动作用。但是，任何科学的进步都受到历史条件的限制，直到二十世纪中期，由于高速数字计算机日益广泛应用，使优化技术不仅成为迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。这些优化技术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、生产调度等。随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，常规优化法如牛顿法、车辆梯度法、模式搜索法、单纯形法等已经无法处理人们所面的复杂问题，因此高效的

优化算法成为科学工作者的研究目标之一。 1.粒子群算法的背景粒子群算法(particle swarm optimization，pso)是一种新兴的演化算法。该算法是由j.kennedy和r.c.eberhart于1995年提出的一种基于群智能的随机优化算法。这类算法的仿生基点是：群集动物(如蚂蚁、鸟、鱼等)通过群聚而有效的觅食和逃避追捕。在这类群体的动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。如在蚁群中，当每个个体发现食物之后，它将通过接触或化学信号来招募同伴，使整个群落找到食源；在鸟群的飞行中，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，但随着时间推移，这些初始处于随机状态的鸟通过相互学习(相互跟踪)组织的聚集成一个个小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集在同一位置──食源。这些群集动物所表现的智能常称为“群体智能”，它可表述为：一组相互之间可以进行直接通讯或间接通讯(通过改变局部环境)的主体，能够通过合作对问题进行分布求解。换言之，一组无智能的主体通过合作表现出智能行为特征。粒子群算法就是以模拟鸟的群集智能为特征，以求解连续变量优化问题为背景的一种优化算法。因其概念简单、参数较少、易于实现等特点，自提出以来已经受到国内外研究者的高度重视并被广泛应用于许多领域。

基于MATLAB的粒子群优化算法的应用示例

对于函数f=x*sin(x)*cos(2*x)-2*x*sin(3*x)，求其在区间[0,20]上该函数的最大值。 ?初始化种群已知位置限制[0,20],由于一维问题较为简单，因此可以取初始种群N 为50，迭代次数为100,当然空间维数d 也就是1。位置和速度的初始化即在位置和速度限制内随机生成一个N×d 的矩阵，对于此题，位置初始化也就是在0~20内随机生成一个50×1的数据矩阵，而对于速度则不用考虑约束，一般直接在0~1内随机生成一个50×1的数据矩阵。此处的位置约束也可以理解为位置限制，而速度限制是保证粒子步长不超限制的，一般设置速度限制为[-1,1]。粒子群的另一个特点就是记录每个个体的历史最优和种群的历史最优，因此而二者对应的最优位置和最优值也需要初始化。其中每个个体的历史最优位置可以先初始化为当前位置,而种群的历史最优位置则可初始化为原点。对于最优值，如果求最大值则初始化为负无穷，相反地初始化为正无穷。每次搜寻都需要将当前的适应度和最优解同历史的记录值进行对比，如果超过历史最优值，则更新个体和种群的历史最优位置和最优解。 ?速度与位置的更新

速度和位置更新是粒子群算法的核心，其原理表达式和更新方式如下: 每次更新完速度和位置都需要考虑速度和位置的限制，需要将其限制在规定范围内，此处仅举出一个常规方法，即将超约束的数据约束到边界（当位置或者速度超出初始化限制时，将其拉回靠近的边界处）。当然，你不用担心他会停住不动，因为每个粒子还有惯性和其他两个参数的影响。代码如下： clc;clear;close all; %% 初始化种群 f= @(x)x .* sin(x) .* cos(2 * x) - 2 * x .* sin(3 * x); % 函数表达式figure(1);ezplot(f,[0,0.01,20]); N = 50; % 初始种群个数 d = 1; % 空间维数 ger = 100; % 最大迭代次数 limit = [0, 20]; % 设置位置参数限制 vlimit = [-1, 1]; % 设置速度限制 w = 0.8; % 惯性权重 c1 = 0.5; % 自我学习因子 c2 = 0.5; % 群体学习因子 for i = 1:d

粒子群优化算法车辆路径问题

粒子群优化算法计算车辆路径问题摘要粒子群优化算法中,粒子群由多个粒子组成,每个粒子的位置代表优化问题在D 维搜索空间中潜在的解。根据各自的位置,每个粒子用一个速度来决定其飞行的方向和距离,然后通过优化函数计算出一个适应度函数值(fitness)。粒子是根据如下三条原则来更新自身的状态:(1)在飞行过程中始终保持自身的惯性;(2)按自身的最优位置来改变状态;(3)按群体的最优位置来改变状态。本文主要运用运筹学中粒子群优化算法解决车辆路径问题。车辆路径问题由Dan tzig 和Ram ser 于1959年首次提出的, 它是指对一系列发货点(或收货点) , 组成适当的行车路径, 使车辆有序地通过它们, 在满足一定约束条件的情况下, 达到一定的目标(诸如路程最短、费用最小, 耗费时间尽量少等) , 属于完全N P 问题, 在运筹、计算机、物流、管理等学科均有重要意义。粒子群算法是最近出现的一种模拟鸟群飞行的仿生算法, 有着个体数目少、计算简单、鲁棒性好等优点, 在各类多维连续空间优化问题上均取得非常好的效果。本文将PSO 应用于车辆路径问题求解中, 取得了很好的效果。针对本题，一个中心仓库、7个需求点、中心有3辆车，容量均为1，由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。 1233,1,7. k q q q l =====货物需求量12345670.89,0.14,0.28,0.33,0.21,0.41,0.57g g g g g g g =======，且 m a x i k g q ≤。利用matlab 编程，求出需求点和中心仓库、需求点之间的各个距离，用ij c 表示。求满足需求的最小的车辆行驶路径，就是求 m i n i j i j k i j k Z c x = ∑∑∑ 。经过初始化粒子群，将初始的适应值作为每个粒子的个

粒子群算法解决函数优化问题

粒子群算法解决函数优化问题 1、群智能算法研究背景粒子群优化算法（Particle Swarm Optimization，PSO）是由Kennedy 和Eberhart 在研究鸟类和鱼类的群体行为基础上于1995 年提出的一种群智能算法，其思想来源于人工生命和演化计算理论，模仿鸟群飞行觅食行为，通过鸟集体协作使群体达到优。 PSO算法作为一种新的群智能算法，可用于解决大量非线性、不可微和多峰值的复杂函数优化问题，并已广泛应用于科学和工程领域，如函数优化、神经网络训练、经济调度、模式识别与分类、结构设计、电磁场和任务调度等工程优化问题等。 PSO算法从提出到进一步发展，仅仅经历了十几年的时间，算法的理论基础还很薄弱，自身也存在着收敛速度慢和早熟的缺陷。如何加快粒子群算法的收敛速度和避免出现早熟收敛，一直是大多数研究者关注的重点。因此，对粒子群算法的分析改进不仅具有理论意义，而且具有一定的实际应用价值。 2、国内外研究现状对PSO算法中惯性权重的改进：Poli等人在速度更新公式中引入惯性权重来更好的控制收敛和探索，形成了当前的标准PSO算法。研究人员进行了大量的研究工作，先后提出了线性递减权值( LDIW)策略、模糊惯性权值( FIW) 策略和随机惯性权值( RIW) 策略。其中，FIW 策略需要专家知识建立模糊规则，实现难度较大，RIW 策略被用于求解动态系统，LDIW策略相对简单且收敛速度快，任子晖，王坚于2009 年，又提出了基于聚焦距离变化率的自适应惯性权重PSO算法。郑春颖和郑全弟等人，提出了基于试探的变步长自适应粒子群算

法。这些改进的PSO算法既保持了搜索速度快的特点, 又提高了全局搜索的能力。对PSO算法的行为和收敛性的分析：1999 年采用代数方法对几种典型PSO算法的运行轨迹进行了分析，给出了保证收敛的参数选择范围。在收敛性方面Fransvan den Bergh引用Solis和Wets关于随机性算法的收敛准则，证明了标准PSO算法不能收敛于全局优解，甚至于局部优解；证明了保证收敛的PSO算法能够收敛于局部优解，而不能保证收敛于全局优解。国内的学者：2006 年，刘洪波和王秀坤等人对粒子群优化算法的收敛性进行分析，指出它在满足收敛性的前提下种群多样性趋于减小，粒子将会因速度降低而失去继续搜索可行解的能力，提出混沌粒子群优化算法。 2008 年，黄翀鹏和熊伟丽等人分析惯性权值因子大小对PSO算法收敛性所带来的影响，对粒子群算法进行了改进。2009 年，高浩和冷文浩等人，分析了速度因子对微粒群算法影响，提出了一种基于Gaussian 变异全局收敛的粒子群算法。并证明了它能以概率 1 收敛到全局优解。 2010 年，为提高粒子群算法的收敛性,提出了基于动力系统的稳定性理论，对惯性权重粒子群模型的收敛性进行了分析，提出了使得在算法模型群模型收敛条件下的惯性权重和加速系数的参数约束关系，使算法在收敛性方面具有显著优越性。在PSO算法中嵌入别的算法的思想和技术。 1997年，李兵和蒋慰孙提出混沌优化方法； 1998年，Angeline在PSO算法中引入遗传算法中的选择算子，该算法虽然加快了算法的收敛速度，但同时也使算法陷入局部优的概率大增，特别是在优化Griewank 基准函数的优值时得到的结果不理想； 2004 年，高鹰和谢胜利将混沌寻优思想引入到粒子群优化算法中，首先对当前群体中的优粒子进行混沌寻优, 再用混沌寻优的结果随机替换群体中的一个粒子，这样提出另一种混沌粒子群优化算法。

物流配送的车辆路径优化

物流配送的车辆路径优化专业：[物流管理] 班级：[物流管理2班] 学生姓名：[江东杰] 指导教师：[黄颖] 完成时间：2016年6月30日

背景描述物流作为“第三利润源泉”对经济活动的影响日益明显，越累越受到人们的重视，成为当前最重要的竞争领域。近年来，现代物流业呈稳步增长态势，欧洲、美国、日本成为当前全球范围内的重要物流基地。中国物流行业起步较晚，随着国民经济的飞速发展，物流业的市场需求持续扩大。特别是进入21世纪以来，在国家宏观调控政策的影响下，中国物流行业保持较快的增长速度，物流体系不断完善，正在实现传统物流业向现代物流业的转变。现代物流业的发展对促进产业结构调整、转变经济增长方式和增强国民经济竞争力等方面都具有重要意义。配送作为物流系统的核心功能，直接与消费这相关联，配送功能完成质量的好坏及其达到的服务水平直接影响企业物流成本及客户对整个物流服务的满意程度。配送的核心部分是配送车辆的集货、货物分拣及送货过程，其中，车辆配送线路的合理优化对整个物流运输速度、成本、效益影响至关重要。物流配送的车辆调度发展现状 VRP（车辆调度问题）是指对一系列装货点和卸货点，组织适当的行车线路，使车辆有序的通过，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量等限制）下，达到一定的目标（如路程最短、费用最少、时间最少、使用车辆数最少等）。一般认为，不涉及时间的是路径问题，涉及时间的是调度问题。VRP示意图如下当然，VRP并不止是这样的一个小范围，而是又更多的客户点与一个仓库链接，从而达

到一整个物流集群。根据路径规划前调度员对相关信息是否已知，VRP可分为静态VRP和动态VRP，动态VRP 是相对于静态VRP而言的。静态VRP指的是：假设在优化调度指令执行之前，调度中心已经知道所有与优化调度相关的信息，这些信息与时间变化无关。一旦调度开始，便认为这些信息不再改变。而VRP发展到现在的问题也是非常突出的，例如，只有一单货物，配送成本远高于一单的客户所给的运费，在这种情况下，该如何调度车辆？甚至还有回程运输的空载问题，在这些问题之中，或多或少都涉及到了VRP的身影，那么在这样的配送中怎么有效的解决车辆的路径优化问题就是降低运输和物流成本的关键所在。解决怎么样的问题？现如今对于VRP研究现状主要有三种静态VRP的研究、动态VRP的研究以及随机VRP的研究。而我对于VRP的看法主要有以下几点。有效解决VRP或者优化车辆调度路径优化问题，那么将非常有效的降低物流环节对于成本的比重，有效的增大利润。而我想到的方法，就是归类总结法。建立完善的信息系统机制，将订单归类总结出来，可以按地区划分出来，一个地区一个地方的进行统一配送，这样也有效的降低了物流配送的车辆再使用问题，降低了成本。如下图所示。仓库客户变换前由上图可以看出来这样的路径，车辆需要来回两次，严重增加了配送成本，也增加了运输成本，使得利润并不能最大化。

粒子群优化算法及其应用研究【精品文档】(完整版)

摘要在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，由于其几乎不存在对问题的约束，因此，粒子群优化算法在各种优化问题中得到广泛应用。本文首先描述了基本粒子群优化算法及其改进算法的基本原理,对比分析粒子群优化算法与其他优化算法的优缺点，并对基本粒子群优化算法参数进行了简要分析。根据分析结果,研究了一种基于量子的粒子群优化算法。在标准测试函数的优化上粒子群优化算法与改进算法进行了比较,实验结果表明改进的算法在优化性能明显要优于其它算法。本文算法应用于支持向量机参数选择的优化问题上也获得了较好的性能。最后,对本文进行了简单的总结和展望。关键词：粒子群优化算法最小二乘支持向量机参数优化适应度

目录摘要...................................................................... I 目录....................................................................... II 1.概述. (1) 1.1引言 (1) 1.2研究背景 (1) 1.2.1人工生命计算 (1) 1.2.2 群集智能理论 (2) 1.3算法比较 (2) 1.3.1粒子群算法与遗传算法(GA)比较 (2) 1.3.2粒子群算法与蚁群算法(ACO)比较 (3) 1.4粒子群优化算法的研究现状 (4) 1.4.1理论研究现状 (4) 1.4.2应用研究现状 (5) 1.5粒子群优化算法的应用 (5) 1.5.1神经网络训练 (6) 1.5.2函数优化 (6) 1.5.3其他应用 (6) 1.5.4粒子群优化算法的工程应用概述 (6) 2.粒子群优化算法 (8) 2.1基本粒子群优化算法 (8) 2.1.1基本理论 (8) 2.1.2算法流程 (9) 2.2标准粒子群优化算法 (10) 2.2.1惯性权重 (10) 2.2.2压缩因子 (11) 2.3算法分析 (12) 2.3.1参数分析 (12) 2.3.2粒子群优化算法的特点 (14) 3.粒子群优化算法的改进 (15) 3.1粒子群优化算法存在的问题 (15) 3.2粒子群优化算法的改进分析 (15) 3.3基于量子粒子群优化(QPSO)算法 (17) 3.3.1 QPSO算法的优点 (17) 3.3.2 基于MATLAB的仿真 (18) 3.4 PSO仿真 (19) 3.4.1 标准测试函数 (19) 3.4.2 试验参数设置 (20) 3.5试验结果与分析 (21) 4.粒子群优化算法在支持向量机的参数优化中的应用 (22) 4.1支持向量机 (22) 4.2最小二乘支持向量机原理 (22)

《物流车辆路径算法的优化与设计》

物流车辆路径算法的优化与设计【摘要】：随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的50％左右，所以降低物流成本首先要从降低物流配送的运输成本开始。一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化，这正是本文要研究的课题。【关键词】：物流配送；路径；车辆路径问题(VRP)；MATLAB 1 前言 1.1 课题研究背景运输线路是否合理直接影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。因此，自从1959年Danting和Rams er提出车辆路径问题(Vehicle Routing Problem，VRP)以来，VRP便成为近年来物流领域中的研究热点。 VRP一般定义为：对一系列发货点和／或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。本文围绕VRP展开了研究，共包括五章内容。首先，本文收集国内外关于

启发式优化算法综述【精品文档】(完整版)

启发式优化算法综述一、启发式算法简介 1、定义由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题

时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。