《车辆路径问题概念、模型与算法(五星推荐)》由会员分享，可在线阅读，更多相关《车辆路径问题概念、模型与算法(五星推荐)（31页珍藏版）》请在金锄头文库上搜索。
1、车辆路径问题概念、模型及算法2021/6/1611、定义车辆路径路径问题(VRP)一般定一般定义为：对一系列装一系列装货点和卸点和卸货点，点，组织适当的行适当的行车线路，使路，使车辆有序地通有序地通过它它们，在在满足一定的足一定的约束条件束条件(如如货物需求量、物需求量、发送量、交送量、交发货时间、车辆容量限制、行容量限制、行驶里程限制、里程限制、时间限制等限制等)下，达到一定下，达到一定问题的目的目标(如路程最短、如路程最短、费用最少、用最少、时间尽量少、使用尽量少、使用车辆数尽量少等数尽量少等)。2021/6/1622021/6/163目前有关目前有关VRP的研究已的研究已经可以表示（如可
2、以表示（如图1）为：给定定一个或多个中心点（中心一个或多个中心点（中心仓库，central depot）、一）、一个个车辆集合和一个集合和一个顾客集合，客集合，车辆和和顾客各有自己的属客各有自己的属性，每性，每辆车都有容量，所装都有容量，所装载货物不能超物不能超过它的容量。它的容量。起初起初车辆都在中心点，都在中心点，顾客在空客在空间任意分布，任意分布，车把把货物物从从车库运送到每一个运送到每一个顾客（或从每个客（或从每个顾客客处把把货物运到物运到车库），要求），要求满足足顾客的需求，客的需求，车辆最后返回最后返回车库，每，每个个顾客只能被服客只能被服务一次，怎一次，怎样才能使运才能使运输费用
3、最小。而用最小。而顾客的需求或已知、或随机、或以客的需求或已知、或随机、或以时间规律律变化。化。2021/6/1642、VRP问题约束(1) 容量容量约束：任意束：任意车辆路径的路径的总重量不能超重量不能超过该车辆的能力的能力负荷。引出荷。引出带容量容量约束的束的车辆路径路径问题(CapacitatedVehicle Routing Problem，CVRP)。(2) 优先先约束：引出束：引出优先先约束束车辆路径路径问题(VehicleRouting Problem with precedence Constraints，VRPPC)。(3) 车型型约束：引出多束：引出多车型型车辆路径路径问题
4、(Mixed/Heterogeneous Fleet Vehicle Routing Problem，MFVRP/ HFVRP)。2021/6/165(4) 时间窗窗约束：包括硬束：包括硬时间窗窗(Hard Time windows)和和软时间窗窗(Soft Time windows) 约束。引出束。引出带时间窗窗(包括硬包括硬时间窗和窗和软时间窗窗)的的车辆路径路径问题(Vehicle Routing Problem withTime windows，VRPTW)。(5) 相容性相容性约束：引出相容性束：引出相容性约束束车辆路径路径问题(VehicleRouting Problem with
5、 Compatibility Constraints，VRPCC)。(6) 随机需求：引出随机需求随机需求：引出随机需求车辆路径路径问题(VehicleRouting Problem with Stochastic Demand，VRPSD)。2021/6/166(7) 开路：引出开路开路：引出开路车辆路径路径问题(Open Vehicle RoutingProblem)。(8) 多运多运输中心：引出多运中心：引出多运输中心的中心的车辆路径路径问题(Multi-Depot Vehicle Routing Problem)。(9) 回程运回程运输：引出：引出带回程运回程运输的的车辆路径路径问题(
6、VehicleRouting Problem with Backhauls)。(10) 最后最后时间期限：引出期限：引出带最后最后时间期限的期限的车辆路径路径问题(Vehicle Routing Problem with Time Deadlines)。(11) 车速随速随时间变化：引出化：引出车速随速随时间变化的化的车辆路径路径问题(Time-Dependent Vehicle Routing Problem)。2021/6/1673、 CVRP问题描述及其数学模型描述及其数学模型CVRP的描述：的描述：设某中心某中心车场有有k辆车，每，每辆配送配送车的的最大最大载重量重量Q，需要，需要对n
7、个客个客户(节点点)进行运行运输配送，配送，每每辆车从中心从中心车场出出发给若干个客若干个客户送送货，最，最终回到中回到中心心车场，客，客户点点i的的货物需求量是物需求量是qi (i=1,2,n)，且，且qiQ。记配送中心配送中心编号号为0，各客，各客户编号号为i(i=1,2 ,n)， cij表示客表示客户i到客到客户j的距离。求的距离。求满足足车辆数最数最小，小，车辆行行驶总路程最短的运送方案。路程最短的运送方案。2021/6/168定定义变量如下量如下:2021/6/169建立此建立此问题的数学模型的数学模型：2021/6/16104、车辆路径问题算法综述目前，求解目前，求解车辆路径路径问
8、题的方法非常多，基本上可以分的方法非常多，基本上可以分为精确算法和启精确算法和启发式算法式算法2大大类。精确算法是指可求出其最精确算法是指可求出其最优解的算法，主要运用解的算法，主要运用线性性规划、整数划、整数规划、非划、非线性性规划等数学划等数学规划技划技术来描述物流来描述物流系系统的数量关系，以便求得最的数量关系，以便求得最优决策。（运筹学决策。（运筹学领域）域）精确算法主要有精确算法主要有：分枝定界法分枝定界法(Branch and Bound Approach)割平面法割平面法(Cutting Planes Approach)网网络流算法流算法(Network Flow Approac
9、h) 动态规划算法划算法(Dynamic Programming Approach)2021/6/1611分枝定界法分枝定界法(Branch and Bound Approach)以求相以求相应的的线性性规划划问题的最的最优解解为出出发点，如果得到点，如果得到的解不符合整数条件，就将原的解不符合整数条件，就将原规划划问题分成几支，每支分成几支，每支增加了增加了约束条件，即束条件，即缩小了可行解区域，可行解范小了可行解区域，可行解范围也也随之随之缩小了，因而整数小了，因而整数规划的最划的最优值不会不会优于相于相应的的线性性规划最划最优值。“定界定界”是指是指为目目标函数定上下界，以便自函数定上下
10、界，以便自动舍去那些最舍去那些最优值较差的子差的子问题，提高，提高计算效率。当整数算效率。当整数规划划问题的的最最优目目标函数函数值的上下界相等的上下界相等时，该整数整数规划最划最优解已解已求出。求出。2021/6/1612首先，不考首先，不考虑变量的整数量的整数约束，求解松弛束，求解松弛问题线性性规划的最划的最优解。如果解。如果线性性规划的最划的最优解恰好是整数解，解恰好是整数解，则这个解就是整数个解就是整数规划的最划的最优解。解。如果如果线性性规划的最划的最优解中至少有一个解中至少有一个变量不是整数，量不是整数，把把线性性规划的可行域切割成两部分，分划的可行域切割成两部分，分别求解两个求解
11、两个线性性规划的最划的最优解。解。2021/6/1613如果如果这两个两个线性性规划的最划的最优解解还不是整数解，分不是整数解，分别把把每一个可行域再每一个可行域再进行分割。行分割。这个个过程，叫做程，叫做“分支分支”。分支分支过程得到的整数解中，目程得到的整数解中，目标函数函数值最最优的一个叫的一个叫做整数做整数规划目划目标函数函数值的的“界界”。分支。分支过程中非整数的程中非整数的线性性规划的最划的最优解，如果目解，如果目标函数函数值劣于或等于劣于或等于这个个“界界”，就停止，就停止继续分支。分支。这个个过程，叫做程，叫做“定界定界”。2021/6/1614割平面法割平面法(Cutting
12、 Planes Approach)用割平面法求解整数用割平面法求解整数规划的基本思路是：先不考划的基本思路是：先不考虑整数整数约束条件，求松弛束条件，求松弛问题的最的最优解，如果解，如果获得整数最得整数最优解，解，即即为所求，运算停止。如果所得到最所求，运算停止。如果所得到最优解不解不满足整数足整数约束条件，束条件，则在此非整数解的基在此非整数解的基础上增加新的上增加新的约束条件重束条件重新求解。新求解。这个新增加的个新增加的约束条件的作用就是去切割相束条件的作用就是去切割相应松弛松弛问题的可行域，即割去松弛的可行域，即割去松弛问题的部分非整数解的部分非整数解(包括原已得到的非整数最包括原已得
13、到的非整数最优解解)。而把所有的整数解都。而把所有的整数解都保留下来，故称新增加的保留下来，故称新增加的约束条件束条件为割平面。当割平面。当经过多多次切割后，就会使被切割后保留下来的可行域上有一个次切割后，就会使被切割后保留下来的可行域上有一个坐坐标均均为整数的整数的顶点，它恰好就是所求点，它恰好就是所求问题的整数最的整数最优解。即切割后所解。即切割后所对应的松弛的松弛问题，与原整数，与原整数规划划问题具具有相同的最有相同的最优解。解。2021/6/1615网网络流算法流算法(Network Flow Approach)图论中的一种理中的一种理论与方法，研究网与方法，研究网络上的一上的一类最最
14、优化化问题 。1955年年 ，T.E.哈里斯哈里斯在研究在研究铁路最大通量路最大通量时首先首先提出在一个提出在一个给定的网定的网络上上寻求两点求两点间最大运最大运输量的量的问题。1956年，年，L.R. 福特和福特和 D.R. 富富尔克森等人克森等人给出了解决出了解决这类问题的算法，从而建立了的算法，从而建立了网网络流理流理论。所。所谓网网络或容或容量网量网络指的是一个指的是一个连通的通的赋权有向有向图 D= （V、E、C） ， 其中其中V 是是该图的的顶点集，点集，E是有向是有向边(即弧即弧)集，集，C是是弧上的容量。此外弧上的容量。此外顶点集中包括一个起点和一个点集中包括一个起点和一个终点
15、。点。网网络上的流就是由起点流向上的流就是由起点流向终点的可行流，点的可行流，这是定是定义在在网网络上的非上的非负函数，它一方面受到容量的限制，另一方函数，它一方面受到容量的限制，另一方面除去起点和面除去起点和终点以外，在所有中途点要求保持流入量点以外，在所有中途点要求保持流入量和流出量是平衡的。和流出量是平衡的。2021/6/1616动态规划算法划算法(Dynamic Programming Approach)动态规划是一种求解多划是一种求解多阶段决策段决策问题的系的系统技技术。如果一如果一类活活动过程可以分程可以分为若干个互相若干个互相联系的系的阶段，在段，在每一个每一个阶段都需作出决策，
16、一个段都需作出决策，一个阶段的决策确定以后，段的决策确定以后，常常影响到下一个常常影响到下一个阶段的决策，从而就完全确定了一个段的决策，从而就完全确定了一个过程的活程的活动路路线，则称它称它为多多阶段决策段决策问题。 各个各个阶段的决策构成一个决策序列，称段的决策构成一个决策序列，称为一个策略。每一个策略。每一个一个阶段都有若干个决策可供段都有若干个决策可供选择，因而就有，因而就有许多策略多策略供我供我们选取，取，对应于一个策略可以确定活于一个策略可以确定活动的效果，的效果，这个效果可以用数量来确定。策略不同，效果也不同，多个效果可以用数量来确定。策略不同，效果也不同，多阶段决策段决策问题，就
17、是要在可以，就是要在可以选择的那些策略中的那些策略中间，选取一个最取一个最优策略，使在策略，使在预定的定的标准下达到最好的效果。准下达到最好的效果。2021/6/1617总的的说来，精确性算法基于来，精确性算法基于严格的数学手段，在可以求格的数学手段，在可以求解的情况下，其解通常要解的情况下，其解通常要优于人工智能算法。但由于引于人工智能算法。但由于引入入严格的数学方法，格的数学方法，计算量一般随算量一般随问题规模的增大呈指模的增大呈指数增数增长，因而无法避开指数爆炸，因而无法避开指数爆炸问题，从而使，从而使该类算法算法只能有效求解中小只能有效求解中小规模的确定性模的确定性VRP，并且通常，并
18、且通常这些些算法都是算法都是针对某一特定某一特定问题设计的的,适用能力适用能力较差差,因此因此在在实际中其中其应用范用范围很有限。很有限。2021/6/1618启启发式算法式算法由于由于车辆路径路径优化化问题是是NP难题，高效的精确算法存，高效的精确算法存在的可能性不大在的可能性不大(除非除非P=NP)，所以，所以寻找近似算法是必找近似算法是必要和要和现实的，的，为此此专家主要把精力花在构造高家主要把精力花在构造高质量的启量的启发式算法上。启式算法上。启发式算法是在状式算法是在状态空空间中的改中的改进搜索算搜索算法，它法，它对每一个搜索的位置每一个搜索的位置进行行评价，得到最好的位置，价，得到
19、最好的位置，再从再从这个位置个位置进行搜索直到目行搜索直到目标。在启。在启发式搜索中，式搜索中，对位置的估价十分重要，采用不同的估价可以有不同的效位置的估价十分重要，采用不同的估价可以有不同的效果。目前已提出的启果。目前已提出的启发式算法式算法较多，分多，分类也相当多，主也相当多，主要的启要的启发式算法有以下几式算法有以下几类：构造算法、两：构造算法、两阶段法、智段法、智能化算法。能化算法。2021/6/1619构造算法构造算法(Constructive Algorithm)这类方法的基本思想是：根据一些准方法的基本思想是：根据一些准则，每一次将一个，每一次将一个不在不在线路上的点增加路上的点
20、增加进线路，直到所有点都被安排路，直到所有点都被安排进线路路为止。止。该类算法的每一步把当前的算法的每一步把当前的线路构形路构形(很可能很可能是不可行的是不可行的)跟另外的构形跟另外的构形(也可能是不可行的也可能是不可行的)进行比行比较并加以改并加以改进，后者或是根据某个判，后者或是根据某个判别函数函数(例如例如总费用用)会会产生最大限度的生最大限度的节约的构形，或是以最小代价把一个的构形，或是以最小代价把一个不在当前构形上的需求不在当前构形上的需求对象插入象插入进来的构形，最后得到来的构形，最后得到一个一个较好的可行构形。好的可行构形。这类算法中中最著名的是算法中中最著名的是Clarke和和
21、Wright在在1964年提出的年提出的节约算法。算法。构造算法最早提出来解决旅行商构造算法最早提出来解决旅行商问题，这些方法一般速些方法一般速度快，也很灵活，但度快，也很灵活，但这类方法有方法有时找到的解离最找到的解离最优解差解差得很得很远。2021/6/1620两两阶段法段法(Two-phase Algorithm)学者学者们通通过对构造算法的研究，构造算法的研究，认为由构造算法求得的由构造算法求得的解可以被解可以被进一步改一步改进，为此提出了两此提出了两阶段法。第一段法。第一阶段段得到一可行解，第二得到一可行解，第二阶段通段通过对点的点的调整，在始整，在始终保持保持解可行的情况下，力解可
22、行的情况下，力图向最向最优目目标靠近，每一步都靠近，每一步都产生生另一个可行解以代替原来的解，使目另一个可行解以代替原来的解，使目标函数函数值得以改得以改进，一直一直继续到不能再改到不能再改进目目标函数函数值为止。止。2021/6/1621一般第一一般第一阶段常用构造算法，在第二段常用构造算法，在第二阶段常用的改段常用的改进技技术有有2-opt(Lin,1965)，3-opt(Lin Kernighan,1973)和和Or-opt (Or,1976)交交换法，法，这是一种在解的是一种在解的邻域中搜索，域中搜索，对初始解初始解进行某种程度行某种程度优化的算法，以改化的算法，以改进初始解。初始解。
23、在两在两阶段法求解段法求解过程中，常常采用交互式程中，常常采用交互式优化技化技术，把，把人的主人的主观能能动作用作用结合到合到问题的求解的求解过程中，其主要思程中，其主要思想是：有想是：有经验的决策者具有的决策者具有对结果和参数的某种判断能果和参数的某种判断能力，并且根据知力，并且根据知识直感，把主直感，把主观的估的估计加到加到优化模型中化模型中去。去。这样做通常会增加模型最做通常会增加模型最终实现并被采用的可能性。并被采用的可能性。2021/6/1622智能化算法智能化算法(Intelligent Algorithm)这类算法以启算法以启发式准式准则来代替精确算法中的决策准来代替精确算法中的
24、决策准则，以以缩小解搜索的空小解搜索的空间。总体来看，尽管启体来看，尽管启发式算法能式算法能够在有限的在有限的时间内求出内求出质量量较高的解，但由于其搜索解空高的解，但由于其搜索解空间的能力有所限制，因的能力有所限制，因此此经常无法达到常无法达到预期的要求。期的要求。20世世纪90年代以来，由年代以来，由于人工智能方法在解决于人工智能方法在解决组合合优化化问题中的中的强大功能，不大功能，不少学者开始将人工智能引入少学者开始将人工智能引入车辆路路线问题的求解中，并的求解中，并构造了大量的基于人工智能的启构造了大量的基于人工智能的启发式算法式算法(智能化启智能化启发式算法式算法)。2021/6/1
25、623智能化启智能化启发式算法从本式算法从本质上上讲仍然属于启仍然属于启发式算法，其式算法，其基本思想是从一初始解开始，通基本思想是从一初始解开始，通过对当前的解当前的解进行反复行反复地局部地局部扰乱乱(Perturbations)以达到以达到较好的解。目前，好的解。目前，最常最常见的智能化启的智能化启发式算法包括模式算法包括模拟退火算法退火算法(Simulated Annealing)、禁忌搜索算法、禁忌搜索算法(Tabu Search)、遗传算法算法(Genetic Algorithm)、蚁群算法群算法(Ant Colony)和神和神经网网络(Neutral Networks)、粒子群、粒
26、子群算法（算法（Particle Swarm Optimization,PSO）方法等。）方法等。2021/6/1624模模拟退火算法退火算法(Simulated Annealing)模模拟退火算法来源于固体退火原理，将固体加温至充分退火算法来源于固体退火原理，将固体加温至充分高，再高，再让其徐徐冷却，加温其徐徐冷却，加温时，固体内部粒子随，固体内部粒子随温升温升变为无序状，内能增大，而徐徐冷却无序状，内能增大，而徐徐冷却时粒子粒子渐趋有序，在有序，在每个温度都达到平衡每个温度都达到平衡态，最后在常温，最后在常温时达到基达到基态，内能，内能减减为最小。根据最小。根据Metropolis准准则，
27、粒子粒子在温度在温度T时趋于于平衡的平衡的概率概率为e(-E/(kT)，其中，其中E为温度温度T时的内能，的内能，E为其改其改变量，量，k为Boltzmann常数。用常数。用固体固体退火模退火模拟组合合优化化问题，将内能，将内能E模模拟为目目标函数函数值f，温度，温度T演化成控制参数演化成控制参数t，即得到解，即得到解组合合优化化问题的模的模拟退火退火算法：由初始解算法：由初始解i和控制参数初和控制参数初值t开始，开始，对当前解重复当前解重复“产生新解生新解计算目算目标函数差函数差接受或舍弃接受或舍弃”的迭代，并的迭代，并逐步衰减逐步衰减t值，算法，算法终止止时的当前解即的当前解即为所得近似所
28、得近似最最优解解，这是基于是基于蒙特卡蒙特卡罗迭代求解法的一种启迭代求解法的一种启发式式随机搜随机搜索索过程。退火程。退火过程由冷却程由冷却进度表度表(Cooling Schedule)控制，包括控制参数的初控制，包括控制参数的初值t及其衰减因子及其衰减因子t、每个、每个t值时的迭代次数的迭代次数L和停止条件和停止条件S。2021/6/1625禁忌搜索算法禁忌搜索算法(Tabu Search)禁忌算法是一种随机搜索算法，它从一个初始可行解出禁忌算法是一种随机搜索算法，它从一个初始可行解出发，选择一系列的一系列的特定搜索方向（移特定搜索方向（移动）作）作为试探，探，选择实现让特定的目特定的目标函
29、数函数值变化最多化最多的移的移动。为了避免陷入局部最了避免陷入局部最优解，解，TS搜索中采用了一种灵活的搜索中采用了一种灵活的“记忆”技技术，对已已经进行的行的优化化过程程进行行记录和和选择，指，指导下一步的搜索方向，下一步的搜索方向，这就是就是Tabu表的建立。表的建立。1、在搜索中，构造一个短期循、在搜索中，构造一个短期循环记忆表表-禁忌表，禁忌表中存放禁忌表，禁忌表中存放刚刚进行行过的的 |T|（T称称为禁忌表）个禁忌表）个邻居的移居的移动，这种移种移动即解的即解的简单变化。化。2、禁忌表中的移、禁忌表中的移动称称为禁忌移禁忌移动。对于于进入禁忌表中的移入禁忌表中的移动， 在以后的在以后
30、的 |T| 次循次循环内是禁止的，以避免回到原来的解，从而避免陷入循内是禁止的，以避免回到原来的解，从而避免陷入循环。|T| 次次循循环后禁忌解除。后禁忌解除。3、禁忌表是一个循、禁忌表是一个循环表，在搜索表，在搜索过程中被循程中被循环的修改，使禁忌表始的修改，使禁忌表始终保保持持 |T| 个移个移动。4、即使引入了禁忌表，禁忌搜索仍可能出、即使引入了禁忌表，禁忌搜索仍可能出现循循环。因此，必。因此，必须给定停止定停止准准则以避免出以避免出现循循环。当迭代内所。当迭代内所发现的最好解无法改的最好解无法改进或无法离开它或无法离开它时，算法停止。算法停止。2021/6/1626遗传算法算法(Gen
31、etic Algorithm)遗传算法是模算法是模拟达达尔文文生物生物进化化论的自的自然然选择和和遗传学学机理的生物机理的生物进化化过程的程的计算算模型模型，是一种通，是一种通过模模拟自然自然进化化过程搜程搜索索最最优解解的方法。的方法。遗传算法是从代表算法是从代表问题可能潜在的解集的一个可能潜在的解集的一个种群种群（population）开始的，而一个种群）开始的，而一个种群则由由经过基因基因（gene）编码的一定数目的个体的一定数目的个体(individual)组成。每个个体成。每个个体实际上是上是染色染色体体(chromosome)带有特征的有特征的实体。染色体。染色体作体作为遗传物物质
32、的主要的主要载体，即多个基因体，即多个基因的的集合集合，其内部表，其内部表现（即（即基因型基因型）是某种）是某种基因基因组合，它决定了个体的形状的外部表合，它决定了个体的形状的外部表现，如黑，如黑头发的特征是由染色体中控制的特征是由染色体中控制这一特征的某种基因一特征的某种基因组合决定的。因此，在合决定的。因此，在一开始需要一开始需要实现从从表表现型型到基因型的到基因型的映射映射即即编码工作。由于仿照基因工作。由于仿照基因编码的工作很的工作很复复杂，我，我们往往往往进行行简化，如化，如二二进制制编码，初代种群初代种群产生之后，按照适者生存和生之后，按照适者生存和优胜劣汰的原理，逐代（劣汰的原理
33、，逐代（generation）演化）演化产生生出越来越好的近似解，在每一代，根据出越来越好的近似解，在每一代，根据问题域中个体的域中个体的适适应度度（fitness）大小）大小选择（selection）个体，并借助于自然）个体，并借助于自然遗传学学的的遗传算子算子（genetic operators）进行行组合交叉（合交叉（crossover）和）和变异（异（mutation），），产生出代表新的解集的种群。生出代表新的解集的种群。这个个过程将程将导致种群像自然致种群像自然进化一化一样的后生代种群比的后生代种群比前代更加适前代更加适应于于环境，末代种群中的最境，末代种群中的最优个体个体经过解解
34、码（decoding），可以作），可以作为问题近似最近似最优解。解。2021/6/1627蚁群算法群算法(Ant Colony)各个各个蚂蚁在没有事先告在没有事先告诉他他们食物在什么地方的前提下食物在什么地方的前提下开始开始寻找食物。当一只找到食物以后，它会向找食物。当一只找到食物以后，它会向环境境释放放一种一种挥发性分泌物性分泌物pheromone (称称为信息素信息素,该物物质随随着着时间的推移会逐的推移会逐渐挥发消失，消失，信息素信息素浓度的大小表征度的大小表征路径的路径的远近近)来来实现的，吸引其他的的，吸引其他的蚂蚁过来，来，这样越越来越多的来越多的蚂蚁会找到食物。有些会找到食物。有
35、些蚂蚁并没有像其它并没有像其它蚂蚁一一样总重复同重复同样的路，他的路，他们会另辟蹊径，如果另开辟的会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，道路比原来的其他道路更短，那么，渐渐地，更多的地，更多的蚂蚁被吸引到被吸引到这条条较短的路上来。最后，短的路上来。最后，经过一段一段时间运运行，可能会出行，可能会出现一条最短的一条最短的路径路径被大多数被大多数蚂蚁重复着。重复着。2021/6/1628神神经网网络(Neutral Networks)神神经网网络是通是通过对人人脑的基本的基本单元元神神经元的建模和元的建模和联接，探索模接，探索模拟人人脑神神经系系统功能的模型，并研制一种功能的模
36、型，并研制一种具有学具有学习、联想、想、记忆和模式和模式识别等智能信息等智能信息处理功能理功能的人工系的人工系统。神。神经网网络的一个重要特性是它能的一个重要特性是它能够从从环境境中学中学习，并把学，并把学习的的结果分布存果分布存储于网于网络的突触的突触连接中。接中。神神经网网络的学的学习是一个是一个过程，在其所程，在其所处环境的激励下，境的激励下，相相继给网网络输入一些入一些样本模式，并按照一定的本模式，并按照一定的规则（学（学习算法）算法）调整网整网络各各层的的权值矩矩阵，待网，待网络各各层权值都都收收敛到一定到一定值，学，学习过程程结束。然后我束。然后我们就可以用生成就可以用生成的神的神
37、经网网络来来对真真实数据做分数据做分类。2021/6/1629粒子群算法（粒子群算法（Particle Swarm Optimization,PSO）粒子群粒子群优化算法化算法是一种是一种进化化计算技算技术(evolutionary computation)，1995 年由年由Eberhart 博士和博士和kennedy 博士博士提出，源于提出，源于对鸟群捕食的行群捕食的行为研究研究 。该算法最初是受到算法最初是受到飞鸟集群活集群活动的的规律性启律性启发，进而利用群体智能建立的一个而利用群体智能建立的一个简化模型。粒子群算法在化模型。粒子群算法在对动物集群活物集群活动行行为观察基察基础上，上，
38、利用群体中的个体利用群体中的个体对信息的共享使整个群体的运信息的共享使整个群体的运动在在问题求解空求解空间中中产生从无序到有序的演化生从无序到有序的演化过程，从而程，从而获得最得最优解。解。PSO同同遗传算法算法类似，是一种基于迭代的似，是一种基于迭代的优化算法。化算法。系系统初始化初始化为一一组随机解，通随机解，通过迭代搜迭代搜寻最最优值。但是它没有。但是它没有遗传算法用的交叉算法用的交叉(crossover)以及以及变异异(mutation)，而是，而是粒子在粒子在解空解空间追随最追随最优的粒子的粒子进行搜索。同行搜索。同遗传算法比算法比较，PSO的的优势在于在于简单容易容易实现并且没有并且没有许多参数需要多参数需要调整。整。目前已广泛目前已广泛应用于函数用于函数优化，神化，神经网网络训练，模糊系，模糊系统控控制以及其他制以及其他遗传算法的算法的应用用领域。域。2021/6/1630 结结束束语语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！
