蚁群算法优化策略综述（共4篇）
蚁群算法优化策略综述 篇1
1引言
蚁群算法源于1992年一篇博士论文提出的模拟蚂蚁寻找食物所选路径的概率型找寻最优解的方案,这种算法本质是基于一定规则的随机运行来寻找最优方案,模仿蚂蚁寻找和搬运食物时释放信息素的机理,不断优化行走路线,在算法实现中执行时间越长,所获得的路径就越可能接近最优路径。
蚁群优化算法已应用于许多组合优化问题,例如二次分配问题,还有很多实变量动力学问题、随机问题、多目标并行的实现等方面,但在实际算法中需要避免的一个问题是过早收敛的问题,算法在执行中很快陷入到了局部最优解的搜索,难以实现广度搜索。因此,在标准算法基础上出现了优化算法,这些优化算法主体通过对于信息素的调节,防止过早收敛问题。在优化算法中核心在于平衡广度搜索与深度搜索, 保证算法的执行效率、有效性。本文通过对目前常见的蚁群优化算法进行综合分析与比较, 较为清晰的梳理出常见优化算法的特点,有助于在解决实际问题中选择合适方法以及算法优化。
2常见蚁群算法的优化算法
标准蚁群算法存在收敛慢、易停滞、运算时间长等缺陷,后续对其做了一系列的改进,以解决该算法存在的问题,产生了许多改进型算法。下面将介绍三种最典型的改进算法:蚁群系统算法(ACS)、最大最小蚁群系统算法(MMAS)、具有变异特征的蚁群算法。
2.1蚁群系统算法
蚁群系统算法(ACS)是对蚁群算法(AC)的改进,这些改进包括:蚂蚁选择的状态转移规则;全局最优更新规则仅运用于属于最优解路径上的信息素;对所有的路径的信 息量进行 局部更新 规则 (Local UpdatingRule)。在ACS中 ,全局更新只是运用在每一次循环中走最优解路径的蚂蚁,而不再运用与所有的蚂蚁。在所有的蚂蚁搜完成了一次循环后,全局更新才会执行。
2.2最大最小蚁群系统算法
最大最小 蚁群系统 算法 (Max-Min Ant System,MMAS) 是解决TSP、QAP等问题的经典蚁群优化算法之一,其结果要优于一般的蚁群算法。MMAS与ACS一样都只允许在每次迭代中表现最好的蚂蚁更新其路径上的信息素, 这样做可以防止算法过早的出现停滞现象。而MMAS与ACS相比不同的地方在于防止这种停滞现象的方法。MMAS的做法为:限定信息素浓度允许值的上下限,并且采用平滑机制。在算法启动时,MMAS将所有路径上的信息素浓度初始化为最大值。在每次循环之后, 只有在最佳路线上的蚂蚁进行信息素的更新,并将其保持在一个高的水平上,其他之路上的信息素将会按照信息素残留度降低浓度。
2.3与变异结合的蚁群算法
吴庆洪等人提出了一种优化蚁群算法———具有变异特征的蚁群算法。其核心思想为采用逆转变异方式,随机地进行变异,以增大进化时所需的信息量,从而克服传统蚁群算法收敛较慢的问题。这种变异机制之所以会具有较快的收敛速度,是因为它充分利用了2-OPT交换法简洁高效的特点。
3蚁群算法优化的新策略
对蚁群算 法所作的 优化是在 已有的改 进型算法———ACS算法的基础上进行的,下文即将描述的优化途径也都是在前人所做改良(即ACS已有的改良途径)的基础上作的更进一步的改进。
3.1路径选择机制的改良
在ACS的路径选择策略中, 我们需要对ij边上已有的信息进行有效的利用,而对于变量q的设定,存在着很大的偶然性使得我们不能很有效地利用已有信息。对此,为了进一步对已有知识加以充分利用,新变量(∑ijk)/m被引入用以替代变量q,其中∑ijk表示上一次循环中选择路径ij的蚂蚁个体的总数。在q0确定的情况下,∑ijk将伴随着算法的运行而随之增大,从而使蚂蚁个体能在下一次路径选择中优先利用已有的信息来选择将要前往的城市,进一步地提高了算法的搜索性能。
3.2全局信息素更新机制的改进
对于信息素的全局更新,我们不仅仅要运用在每一次循环中走最优解路径的蚂蚁,还要运用与每一次循环中最差的蚂蚁使用。但是对于最差蚂蚁的全局更新规则与走最优解路径蚂蚁的规则不同,其更新规则采用如下的公式
τij(t)←(1-ε)×τij(t)+ε×△τij(t) ;
其中,ε为区间(0,1)上的参数;而△τij(t)则用如下的公式计算:
△τij(t)= Q/L - Q/L’若ij路径是算法已求出的最差路径的一部分
或 = 0若ij路径不是已求出的最差路径的一部分 ;
在ACS算法的基础上, 增加对最差的蚂蚁采用以上的更新机制,能更有效地模拟蚂蚁在自然界的觅食过程中分泌的信息素,能准确得出路径长度与时间之间的关系,可使得更多的已有知识被利用,同时在后续的循环中能够增加好的路径被选择的概率并减少差的路径被选择的概率,这样算法的性能可以大大提高。
3.3增加最小信息素浓度设置
MMAS给每一条支路都设置了一个最小信息素浓度,在算法运行过程中,各个支路的信息素浓度不会降到τmin以下。这样保证了即使没有任何一只蚂蚁选择走某条路径,在再一次的循环中这条路径依然有一定的概率被选中,从而避免了一些可能存在的好的路径被过载地抛弃,同时也避免了算法过早地收敛。设置了一个最小信息素浓度τmin,它的计算公式为:
τmin = 1/[2n?(1-ρ)?L] ;
n表示当前问题的城市节点数 ,ρ为信息素残留度 ,L为算法运算到当前为止,已求出的最优路径的长度 ;为了保证所有路径上的信息素浓度不低于τmin,每当一次循环中的信息素局部及全局更新完成后,就需要比较τij和τmin,如果τij<τmin,则将τij强行设置为τmin。
3.4杂交算子的引入
遗传算法具有良好的搜索能力,引入了杂交算子来对现有的所有解进行重组,这样可以发现潜在的更好的解。我们现在尝试一种新的增强解的方法:杂交算子被引入到ACS算法中, 以对在算法运行过程中产生的新的解进行杂交, 并充分利用当前所知的所有路径信息,两者结合可以发现更好的解,从而对最终我们希望得到的结起了增强作用。
4结束语
蚁群算法作为组合优化的经典算法,在实际问题的应用中仍然存在一些问题,这些问题需要进一步研究。
(1)正反馈机制的建立 ,启发函数的定义 ,求解问题增式的进行,以及最优解与问题定义中的现实世界的况相对应等问题需要考虑。
(2)在开始运行蚁群算法求解问题时 ,需要对大量的变量进行初始化,这些变量的初始值会对算法的性能产生较大的影响。然而这些变量初始值的选取方法和原则在目前还没有一个理论上的依据,只能在多次实验中积累经验从而选择比较好的值。因此在初始化变量的最佳值设置问题上还有待进一步的研究。
摘要：对于求解TSP问题,新型的启发式算法——蚁群算法,是成功解决此类问题核心的算法之一。本文简要介绍了几种启发式算法并引出蚁群算法,并对蚁群算法基本原理、常用算法进行了深入的研究,并介绍了一种新的优化策略。
关键词：TSP问题,蚁群算法,优化策略
蚁群算法优化策略综述 篇2
关键词：VRP,鱼群蚁群算法,智能优化算法
在物流的配送优化等问题中,常见的问题就是:存在一批客户,并且已知客户的地理坐标,每个客户对货物的需求量,运输车辆的最大数量和运载能力等信息。在每辆运输车都从仓库出发,完成部分点的运输任务后返回仓库的前提下,寻求以最少车辆和最短总行程完成物流运输的最优解。此类问题统称为车辆运输路径问题,即Vehicle Routing Problem,VRP。
路径优化问题是现代物流供应链优化中的关键问题,车辆路径问题的理论与算法依然是学者们重视的问题与研究的重点。对算法进行系统的研究不仅为物流运输优化提供更好的思路和方法,更加为构建综合物流系统,发展智能交通运输系统等打下坚实的理论基础。
1 车辆路径问题
1.1 车辆路径问题分类
车辆路径的问题随着相关学科的发展从最初的静态的VRP、VRPTW、VRPPD等模型不断衍生出随机车辆路径问题、模糊车辆路径问题,到现在的动态车辆路径问题。所以可以将车辆路径问题归为两大类,一类是一般车辆路径问题,而另一类则是衍生车辆路径问题[1],具体如下图1所示。
1.2 车辆路径问题的一般模型
对于一般车辆运输问题的优化,为方便模型的建立,对货物的物流运输作以下几点假设:
(1)仅考虑位置已知的一个仓库,所有配送车辆起点和终点均是该仓库。
(2)只考虑单个品种货物的运输,且每个需求点所需要的货物剂不超过车辆的最大载重量。
(3)每个需求点的地理坐标位置和需求量都已知,其需求有且仅由一辆车辆一次送货满足。
(4)只有一种车辆,且车辆的载重量已知。
(5)车辆对每个需求点进行服务,途中只有卸货而无装货。
(6)车辆的平均行驶速度已知,并且确定,行驶的路程与车辆行驶时间成正比。
以上述假设为前提,以配送成本最小化为目标,构造出以下优化模型。
式中,仓库的编号为0,需求点的编号为1,2,......,C ,xijk={1.0}取整数约束,1表示点i到点j由车辆k来完成,否则为0;其中yijk={1.0} 取整数约束,1表示到点i由车辆k来完成 ,否则为0。C为需求点 的个数 ;m为车辆数 ; dij(i,j = 1,2,?,C)为需求点i点与需求点j点之间的距离;ti为车辆实际到达需求点的时间;gi为第i个医疗机构的需求量;q为车的最大载重量;k(k = 1,2,......,m)为车辆的编号。
约束条件为:
每次为需求点运输货物的运输量不能超过车辆的最大载重量;
任意需求点只有1辆车辆来访;
车辆行驶路线为闭合线路;
2智能优化算法的分类与比较
解决车辆路径算法的种类很多从20世纪50年代起的精确算法开始,到之后的启发式算法,以及现在学者们研究的最多的智能优化算法。其中精确算法有:分支界定法(Branch and Bound Approach)、割平面法(Cutting Planes Approach)等,启发式算法有:节约算法(C-W)、扫描算法(Sweep Algorithm)等,应用最多的智能优化算法有:禁忌搜索算法(Tabu Search)、模拟退火算法(Simulated Annealing)、遗传算法(Genetic Algorithm)、蚁群算 法(Ant Colony Optimization)、粒子群算 法(Particle Swarm Optimization),另外还有人工鱼群算法(Artificial Fish School Algorithm)、人工神经 网络算法(Artificial Neural Net-works)等智能优化算法,都在车辆路径问题的研究中有应用。
随着物流业的不断发展,物流运输配送遇到的问题范围不断的扩大,实际问题的规模与复杂性也不断的增大,仅仅靠单一的算法来优化解决问题的效果已经越来越不理想,每个算法都有各自的缺陷,都面临着时间性能和优化性能等挑战。如下表1是目前运用最多的智能优化算法思想和优缺点[2]。
基于上述现象及出发点,可将各种单一的算法取长补短, 利用各算法的优势进行融合,构造出新的优化效率更高的混合算法。
3 鱼群-蚁群算法
3.1 人工鱼群算法
人工鱼群算法(AFSA)是基于模仿鱼群觅食、聚群和追尾等行为而衍生出的一种较新型智能优化算法。这种算法具有并行性、快速性、较强的搜索全局性等特点。在人工鱼群算法中,设人工鱼当前所在的位置是Xi=(xi1,xi2,......,xi N), Xv=(xv1,xv2,?,xv N),其中N表示维数,Visual表示人工鱼的视野范围,Xv表示视野范围内的一个状态。人工鱼的步长用Step表示,人工鱼要从当前状态到一个更优的状态过程可以表示为:
人工鱼群算法还包括了一下几个行为:(1)觅食行为。在人工鱼的视野范围内选择位置Xv,若Xv的适应度Yv大于Xi 的适应度Yi,则该人工鱼向Xv的方向移动一步,反之,则从新选择一个位置。(2)聚群行为。在避免拥挤和逐步中心的规则下,执行觅食行为或随机游动。其中一个重要的参数叫做拥挤因子,用σ表示。
若(其中),表示中心食物较多且不拥挤,人工鱼向Xc方向移动一步,反之,则执行觅食行为或随机游动。(3)追尾行为。在优化过程中,若,表示在视野范围内,最优状态的伙伴位置为Xv,且食物浓度高,不拥挤,则Xi向Xv的方向移动一步,反之,则执行觅食行为。(4)随机移动。即人工鱼在其视野范围内随机移动一步。人工鱼群算法的基本流程如下图2所示。
3.2 蚁群算法
蚁群算法(ACO)是一种在图中寻找优化路径的随机搜索型算法。它最开始是由Marco Dorigo于1992年提出的,后来由Bernd Bullnheimer等[3]率先应用于解决VRP问题,即先通过蚁群算法搜索最优路径,再运用2-Opt法对其进行优化,最后找出最优解。蚁群算法的基本思想是模仿蚂蚁觅食发现最优路径的行为,并以下面三个假设为前提:(1)蚂蚁之间通过产生信息素进行相互通信;(2)蚂蚁对环境的反应由内部的模式决定; (3)每只蚂蚁的行为是随机的且仅依照环境做独立选择,蚁群可以通过自组织形成高度有序的群体行为。
蚁群算法中关键的因素有以下几个:
(1)信息素用τij(t) 表示t时刻路径上信息素的含量,随着时间的推移信息素的含量不断应新旧信息素的加入和挥发而改变,当时刻变为t+n后,各个路径上的信息素变为:(其中ρ信息素的挥发系数)
(2)启发函数用来表示蚂蚁从节点i转移到节点j的期望程度,其计算公式为:
(3)状态转移概率,这里以Pik j(t) 表示,其计算公式为:(其中α为启发因子表示蚂蚁在路径中积累的信息的作用,值越大则意味着蚂蚁间的协作性越强。β为期望启发因子表示启发 信息在蚂蚁路径选择中的重要程度,值越大则意味着该状态下的转移率越接近贪心规则。)
蚁群算法求解VRP的基本流程,如下图所示:
3.3 鱼群蚁群混合算法
在解决VRP问题中,对鱼群蚁群混合算法的研究还不是很多,现有的两种算法可结合的方法主要分为加入改变拥挤因子,改变信息素更新机制两种形式:
(1)改变拥挤因子。文献[4]在研究特殊医疗器械物流配送路径优化时,将鱼群算法与基本蚁群算法相结合,把鱼群算法中的拥挤因子概念引入到基本蚁群算法中,是算法整体增强寻优能力,减少基本蚁群算法陷入局部最优的可能性。其中设拥挤因子σij和拥挤度门限δ(t) 的计算公式分别如式(14)和式 (15),其中γ为极值接近水平,b为阈值变化系数。其改进方法可以控制蚂蚁集数量的多少,以此抑制蚂蚁过早的聚集在高信息素的路径上,从而减少早熟现象的发生几率。但是该方法也存在不足,特别是在算法的后期会影响收敛速度。
文献[5,6]也是研究人工鱼群算法拥挤度的引入。部分区别在于拥挤因子的设置上如式(16)所示。同样在算法的初期设置较强的门限,但是随着迭代次数的增加,拥挤度阈值逐渐增大,信息素的浓度在指导蚁群选择路径的作用逐渐增强,最后蚁群完全由信息素和启发因子来指导寻优从而保证了算法能够快速地收敛到最优解上。
(2)改变信息素更新机制。文献[7]在运用鱼群蚁群混合算法解决模块化产品配置问题中,提出了两种算法动态融合策略。不是通过改变拥挤因子来进行优化,而是通过设置鱼群算法的迭代范围,统计满意的更新率,选择鱼群与蚁群融合的最佳转换时机来进行寻优。当人工鱼群算法的优化速度明显减慢时便终止人工鱼群算法,开始蚁群算法。同时文献中改变了蚁群算法的信息素更新方程,将基本方程如式(10)改为式 (16)。方程中τij(t)min,τij(t)max分别为信息素强度的上下限, 寻求最优解。
文献[8]应用人工鱼群算法的追尾行为对蚁群在可行域上搜索到的可行解进行改进,将微分进化算法引入信息素的更新机制中,改变人工鱼群算法的追尾公式,如式(18),其中Xbest 表示当前最优解,Xki表示蚂蚁k的状态Xk的第i个元素。之后再对修改过的新解进行信息素更新,从而加快收敛速度,快速达到全局最优。
4 结束语
蚁群算法优化策略综述 篇3
目前, 混合动力汽车 (hybrid electric vehicle, HEV) 的控制策略主要有逻辑门限值控制策略、瞬时优化控制策略、全局优化控制策略和模糊控制策略等[1,2]。模糊控制策略鲁棒性强、实时性好, 具有很强的实用性, 但模糊控制策略隶属度函数和模糊控制规则的选取主要依靠专家经验, 一般情况下无法获得全局最优, 因此需要对模糊控制策略进行优化, 以获得最优的控制性能。
HEV控制策略优化是复杂的非线性优化问题, 很难用传统的一些优化方法来求解。近年来涌现出的智能优化方法, 如遗传算法、蚁群算法和粒子群算法等, 能够在搜索过程中自动获取和积累有关搜索空间的知识, 实现在复杂空间中的有效搜索[3]。遗传算法 (genetic algorithms, GA) 是一种具有很强全局寻优能力的仿真算法, 但未利用系统中的反馈信息, 降低了求解效率[4,5];蚁群算法 (ant colony algorithms, ACA) 是一种新型的模拟进化算法, 重点始于组合优化问题的求解, 但存在收敛较慢的问题[6,7]。故笔者采用集遗传算法和蚁群算法优点的遗传-蚁群算法 (genetic-ant colony algorithm, GACA) , 对并联式混合动力电动客车 (parallel hybrid electric bus, PHEB) 的混合动力系统模糊控制器的隶属度函数和模糊控制规则进行优化, 并运用MATLAB/Advisor进行实例PHEB性能仿真分析。
1 PHEB模糊控制策略设计
1.1 PHEB混合动力系统工作模式分析
鉴于城市客车停靠站点多、车速不高、起步、停车十分频繁等特点, 结合超级电容具有在短时间内可大电流充放电、循环寿命长、充放电效率高等优势, 在传统燃油城市客车结构基础上, 设计了一种超级电容和柴油发动机混合的并联式混合动力系统。鉴于超级电容的辅助动力作用, 混合动力系统的发动机工作点范围可向其最佳燃油经济性曲线的上下两侧进行适当拓展, 如图1所示的Ⅱ区域。为了充分发挥并联式混合动力系统的优势, PHEB在不同的行驶工况下, 具有多种不同的控制模式:
(1) 汽车在启动和低速行驶时, 为避免发动机处在高油耗率区, 由超级电容放电驱动电机, 实现纯电驱动模式。
(2) 当汽车在加速或爬坡等大负荷情况下, 或发动机的工作点位于如图1所示的Ⅰ区域时, 进入发动机和电机混合驱动模式。
(3) 当汽车匀速行驶时, 发动机单独驱动, 并根据超级电容的荷电状态 (state of charge, SOC) 值来确定是否对其充电。若发动机工作在相对经济区间 (Ⅱ区域) , 则超级电容不工作;若发动机的工作点位于如图1所示的Ⅲ区域, 并且超级电容的SOC值低于预先设定的下限值, 则发动机在提供整车所需功率的同时向超级电容充电, 直到超级电容SOC值超过预先设定的上限值为止。
(4) 汽车减速/制动时, 电机作为发电机运转, 把驱动轮的动能转化为电能, 并通过功率转换器给超级电容充电, 实现再生制动能量的回收。
1.2 PHEB 模糊控制策略设计
1.2.1 模糊控制器的设计
鉴于PHEB混合动力系统结构特点, 设计一种模糊控制器, 结构如图2所示。该结构主要由3个模块组成:①转矩转化模块, 计算整车的需求转矩与当前转速下发动机最优输出转矩的差值ΔT;②模糊推理模块, 它是模糊控制器的核心部分[8], 由两个输入量 (整车需求转矩与发动机最佳转矩之差ΔT以及超级电容当前SOC值) 和一个输出量 (发动机输出转矩T) 构成;③转矩修正模块, 根据模糊推理器的输出, 最后转化为发动机的实际输出转矩Te。
1.2.2 隶属函数
输入变量ΔT和SOC的论域分别为[-3, 3]和[1,7], 输出变量Te的论域为[1,7]。输入变量ΔT和SOC均定义为5个模糊子集, ΔT描述为{NB (负大) 、NS (负小) 、ZO (零) 、PS (正小) 、PB (正大) };SOC描述为{ S (小) 、RS (较小) 、M (中等) 、RB (较大) 、B (大) }, 输入变量ΔT和SOC的隶属函数分别如图3和图4所示。根据发动机的效率曲线图, 将输出变量Te定义为7个模糊子集, Te描述为{VS (极小) 、S (小) 、RS (较小) 、M (中等) 、RB (较大) 、B (大) 、VB (极大) }, 输出变量Te的隶属函数如图5所示。
1.2.3 模糊控制规则
模糊推理的规则建立原则是, 在保证超级电容充放电平衡的情况下, 尽量使发动机工作在最优曲线附近。在确定各输入、输出变量模糊子集和隶属度函数后, 就可以列写出模糊控制规则, 如表1所示。
1.3 PHEB 控制策略优化目标
PHEB优化目标就是在满足汽车动力性能的基础上, 尽量使PHEB的等效燃料消耗量最小。PHEB控制策略优化问题是一个典型的非线性约束优化问题[9], 其数学模型可以表述为
min f (x) =F (x) (1)
其中, F (x) 为等效燃料消耗量;f (x) 为优化目标函数, 其约束条件gr (x) (r=1, 2, …, M) 是一组非线性不等式约束, 这里主要是满足PHEB的性能要求, 即加速时间、最大爬坡度、0～50km/h的加速时间和超级电容组SOC的平衡等要求。针对实例PHEB的性能技术要求, 约束条件设计如下:①最高车速g1 (x) ≥80km/h;②最大爬坡度g2 (x) ≥20%;③0～50km/h的加速时间g3 (x) ≤30s;④超级电容SOC初始值和终值之差g4 (x) ≤0.5%。
2 基于GACA的模糊控制策略优化
2.1 GACA的基本思路
鉴于遗传算法具有大范围全局搜索的能力, 蚁群算法具有正反馈寻优等优点, 采用集遗传算法和蚁群算法优点的GACA。GACA的基本思路是以PHEB等效燃料消耗量为优化目标, 首先利用遗传算法产生较优解, 并留下初始信息素分布;然后在有一定初始信息素分布的情况下, 利用蚁群算法寻求最优解, 充分发挥遗传算法与蚁群算法在寻优搜索中各自的优势。
2.2 遗传算法规则
2.2.1 编码以及群体初始化
采用浮点数编码方法进行编码, 将优化问题的实际参数构成染色体编码。初始群体中的个体是随机产生的, 通过编码随机产生N个个体形成初始群体。
2.2.2 适应度函数
适应度函数可等价于蚁群算法过程中的目标函数, 并将约束加入到适应度函数中[10]。
2.2.3 选择方法
采用最佳个体保留策略和赌盘轮法相结合的选择方法, 即在群体交叉之前选出最佳个体, 直接遗传到子代群体中, 其余个体采用赌盘轮法来选择。
2.3 蚁群算法规则
2.3.1 信息素的初始值设置
通过遗传算法得到了一定的路径信息素, 把信息素的初始值τS设置为
τS=τC+τG (2)
式中, τC为具体求解问题给定的一个信息素常数;τG为遗传算法求解结果转换的信息素值。
2.3.2 路径选择
在节点i的第k只蚂蚁选择下一跳节点j的规则:
式中, τi j (t) 为t时刻在i、j连线上的信息素量;ηi j (t) 为与τi j (t) 对应的启发式信息;α、β分别为调节信息素强度τ和启发式信息η相对重要性的参数;S为蚂蚁可行路径节点集合;p (k) i j (t) 为t时刻第k只蚂蚁由位置i转移到位置j的概率。
2.3.3 信息素的更新
信息素的更新采用局部更新和全局更新相结合的策略。局部更新可避免蚂蚁在上次更好的路径有限相邻区域内搜索, 全局更新对历史最优解路径上的信息素进行更新。当第k只蚂蚁成功地完成从i到j的一跳, 信息素按照式 (4) 进行更新:
式中, ρ为局部信息素挥发系数, 0<ρ<1;Δ τ (k) i j (t) 为蚂蚁k在i、j连线上留下的单位长度轨迹信息素数量;Q为常数, 用于调整信息素;W为第k只蚂蚁所行走的路径集合。
当所有的蚂蚁完成了一次循环后, 选择出目标函数值最小的路径, 再按照式 (6) 进行全局信息素更新, 以达到较快收敛于最优解的目的:
τi j (t+n) = (1-θ) τi j (t) +θΔ τi j (t+n) (6)
式中, θ为全局信息素挥发系数, 0≤θ<1;Δ τi j (t+n) 为蚁群完成一次循环后的信息素修改值。
2.4 GACA优化流程
基于GACA的控制策略优化流程如下:①随机产生1组实数编码;②根据遗传算法进行若干次迭代, 依据目标函数, 生成初始信息素分布;③根据式 (3) 初始信息素分布, 在源节点放置m只蚂蚁, 每只蚂蚁依据状态转移概率选择下一跳节点;④蚂蚁完成一步后, 根据式 (4) 进行局部信息素更新;⑤所有的蚂蚁完成1次循环后, 根据式 (6) 进行全局信息素更新;⑥若满足结束条件, 即循环次数Tc≥Tmax则循环结束并输出最优解, 否则跳转到步骤⑤。
2.5 基于GACA的PHEB模糊控制策略优化
将GACA和模糊控制相结合, 利用GACA优化PHEB模糊控制器的隶属函数和模糊控制规则, 以期得到最优的模糊控制策略。在已设计的PHEB模糊控制器 (图2) 的基础上进行GACA优化, 建立优化模型, 如图6所示。通过GACA对已建立的糊控制器的控制变量进行调整优化, 从而得到最优的两个输入控制变量 (整车需求转矩与发动机最佳转矩之差ΔT、超级电容当前SOC值) 以及一个输出控制变量 (发动机的实际输出转矩Te) 的隶属函数和模糊控制规则。
3 基于实例的PHEB模糊控制策略优化
3.1 实例PHEB主要技术参数
实例PHEB车型是在传统燃油城市公交车基础上改装而成的, 采用由超级电容和柴油发动机组成并联式混合动力系统。根据城市公交车的运行状况以及道路条件, 确定实例的PHEB主要参数, 如表2所示。
3.2 基于Advisor的实例PHEB仿真模型建立
首先利用MATLAB/Simulink建立发动机、电机、超级电容等主要部件的仿真模型, 并在Advisor平台上进行整车模型的二次开发。然后在MATLAB/Simulink环境下建立基于GACA的模糊控制模块, 并嵌入到Advisor整车仿真模型中, 得到整体封装后的基于GACA模糊控制策略的PHEB整车仿真模型, 如图7所示。其中, 优化后的模糊控制模块的输入控制变量ΔT和SOC及输出控制变量Te的隶属度函数分别如图8～图10所示。
3.3 实例PHEB仿真结果分析
在基于GACA模糊控制策略优化的PHEB整车模型 (图7) 中, 输入实例PHEB基本数据 (表2) , 在中国典型城市公交循环工况下进行仿真分析[11]。结果表明:与优化前相比, 优化后的发动机工作点控制在效率较高的区域内 (图11) , 且超级电容SOC值的变化控制在较小的范围内 (图12) 。
3.4 实例的PHEB道路测试结果分析
基于GACA优化的模糊控制策略, 经硬件在环验证试验, 并与实例PHEB实车道路测试结果进行比较, 结果及分析如表3所示。表3中, 误差表示优化后的仿真值与实车测试值的相对误差。
实例PHEB测试结果表明:基于GACA优化的模糊控制策略能够满足整车动力性能指标要求;优化后百公里的等效燃料消耗量仿真值为28.2L, 比优化前百公里的等效燃料消耗量仿真值31.4L降低了10.2%;实车测试的百公里等效燃料消耗量为29.0L, 比同类车型的传统燃油客车的百公里燃料消耗量36.2 L降低了19.9%;与实车测试值相比, 优化后的各项指标仿真值的相对误差均小于3%。
4 结论
(1) 基于超级电容的PHEB动力系统的结构特点, 设计了分别以整车需求转矩与发动机最佳转矩之差值以及超级电容荷电状态为输入, 以发动机转矩为输出的模糊控制器。采用集遗传算法和蚁群算法优点的GACA, 对PHEB的混合动力系统模糊控制器的隶属度函数和模糊控制规则进行优化。
(2) 实例PHEB仿真分析和实车道路测试表明:基于GACA优化的模糊控制策略能将PHEB的发动机控制在最佳燃油经济性曲线附近, 且超级电容SOC值的变化在较小的范围内;在满足动力性能指标要求的情况下, 基于GACA优化的PHEB等效燃料消耗量的仿真值比优化前降低了10.2%;实车测试的百公里等效燃料消耗量比同类车型的传统燃油客车的百公里燃料消耗量36.2L降低了19.9%, 从而验证了基于GACA优化的模糊逻辑控制策略的可行性, 为新能源汽车的混合动力系统控制策略设计和优化提供了一种新途径。
摘要：以并联式混合动力客车 (PHEB) 为研究对象, 设计了以整车需求转矩与发动机最佳转矩之差以及超级电容荷电状态为输入, 以发动机转矩为输出的模糊控制器, 并应用遗传-蚁群算法对其进行隶属度函数和控制规则优化。基于MATLAB/Advisor建立了PHEB模糊控制策略模型和整车模型, 并对优化前后的实例PHEB性能进行了仿真分析。研究结果表明, 优化后的模糊控制策略能够满足设计要求, 且等效燃料消耗量比优化前降低了10.2%。
关键词：并联式混合动力客车 (PHEB) ,遗传-蚁群算法,模糊控制策略,优化
参考文献
[1]陈清泉, 朱家琏, 田光宇.现代电动汽车技术[M].北京:北京理工大学出版社, 2007.
[2]Farzad R S.Control Strategies for Hybrid ElectricVehicles:Evolution, Classification, Comparison, andFuture Trends[J].IEEE Transactions on VehicularTechnology, 2007 (5) :2393-2404.
[3]吴剑.并联式混合动力汽车能量管理策略优化研究[D].济南:山东大学, 2008.
[4]Morteza M G, Amir P, Babak G.Application of Ge-netic Algorithmfor Opti mization of Control Strategyin Parallel Hybrid Electric Vehicles[J].Journal ofthe Franklin Institute, 2006, 343 (4/5) :420-435.
[5]朱传高.并联混合动力汽车遗传模糊控制策略的优化研究[D].长春:吉林大学, 2009.
[6]赵义武, 牛庆银, 王宪成.遗传算法与蚁群算法的融合研究[J].科学技术与工程, 2010, 10 (16) :4017-4020.
[7]刘彦鹏.蚁群优化算法的理论研究及其应用[D].杭州:浙江大学, 2007.
[8]资新运, 杜常清, 张增建, 等.混合动力汽车模糊逻辑转矩管理策略仿真混合动力汽车模糊逻辑转矩管理策略仿真[J].武汉理工大学学报, 2008, 30 (4) :561-564.
[9]吴静波, 张承宁, 邹渊, 等.基于遗传蚁群算法的履带式混合动力车辆控制策略参数优化[J].车用发动机, 2009 (3) :44-48.
[10]浦金欢, 殷承良, 张建武.遗传算法在混合动力汽车控制策略优化中的应用[J].中国机械工程, 2005, 16 (7) :648-652.
蚁群优化算法应用研究 篇4
蚁群算法本质是一个复杂的智能搜索算法,具有较强的鲁棒性、良好的正反馈性能、优良的分布式计算机制、易于与其他优化算法相结合等特点。如今,该算法已经成为智能优化算法中的研究热点,对它的研究已经渗入到多种不同的应用领域。
1 基本蚁群算法原理
在自然界中,单个的蚂蚁个体行为极为简单,但由多个蚂蚁所组成的群体却成功地在搜寻食物等方面表现出复杂的行为。研究发现,蚂蚁总能找到巢穴与食源之间最短路径。蚁群算法就是借鉴和吸取现实世界中蚂蚁这种集体寻径行为来寻求函数的最优解。
蚂蚁个体之间通过一种称为信息素的物质进行信息传递,蚂蚁在移动过程中通过感知遗留在路径上的该种物质来指导自己的运动方向,并在自己经过的路径上留下该类物质。这样,大量蚂蚁所组成的群体便构成了一种信息正反馈,从而成功地实现了食物搜索,最短路径选择等行为。为了具体说明蚁群算法的原理,举出人工蚁群路径搜索的例子。
如图1所示,路径AB、ED、DH、HB长度分别为1,BC和BD长度分别为0.5。如图1(a)所示,在t=0时刻,有30只蚂蚁分别在A点和B点,蚂蚁单位时间内行程为1并留下1个浓度的信息素。如图1(b)所示,在t=1时刻,A点和E点的蚂蚁同时到达B点和E点,由于此前路径上没有信息素,它们随机选取路径,在DH、HB、BC、DC上将各有15只蚂蚁。如图1(c)所示,在t=2时刻,将有30只蚂蚁到达H点,而有15只蚂蚁分别到达B点和D点,在这段时间内,遗留在BC、CD上的信息素将是DH或是HB的两倍。而蚂蚁是根据遗留在路径上信息素的强弱来选择自己前进的方向,信息素强路径的将会吸引更多的蚂蚁,因此在后续的选择中,选择DC或是BC蚂蚁数量将是DH和HB的两倍,所以,20只蚂蚁选择BC,10只选择BH。如此反复进行下去,直至所有的蚂蚁都选择最短的路径BCD或是DCB。通过上面的例子,可以简单的说明蚁群算法主要的特点:
1)正反馈性。蚂蚁群体行为表现出正反馈过程,通过反馈机制的调整,可对系统的较最优解起到一个自增强的作用,从而使问题的解向着全局最优的方向演变,最终能有效的获得全局最优解。
2)并行性。蚁群算法是一个本质并行的算法,个体之间不断的进行信息的交流与传递,相互协作,有利于最优解的发现,从而在很大程度上减少了陷于局部最优的可能。
2 算法描述[1]
蚁群算法首次提出是用于解决TSP问题,因此我们就以求解n个城市的TSP问题为例来说明基本蚁群算法的求解过程。
TSP问题是一个典型的离散优化问题。其定义是:给定n个城市,TSP等价于寻找一条只经过各个城市一次且长度最短的闭合路径。令dij为城市i和j之间的距离,在欧式空间中,。。
假设蚁群数量为m,τkij(t)表示t时刻在ij上遗留的信息素。在初始时刻,各条路径上的信息素是相等的,τij(0)=C(C为常数),蚂蚁k(k=1,2,,m)在运动的过程中根据各条路径上遗留的信息素决定移动方向。pkij(t)表示t时刻蚂蚁k由城市i选择城市j的转移概率
allowedk={0,1,………,n-1}表示蚂蚁k下一步允许选择的城市,α和β分别反映了蚂蚁在运动的过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性,ηij为由城市i转移到城市j的期望程度,在TSP问题中取ηij=1/dij。建立禁忌表tabuF(F=1,2,……n)记录在t时刻蚂蚁已经走过的城市,不允许该蚂蚁在本次循环中再经过这些城市。当本次循环结束以后,禁忌表将被用来计算改蚂蚁当前所经过的路径长度。之后,禁忌表将被清空,用以准备下一次循环。经过n个时刻,蚂蚁完成一次循环,各条路径上的信息素根据下式调整:
用△τkij表示第k只蚂蚁在本次循环中留在路上的信息素,则,ρ为信息素残留系数,1-ρ表示信息素的消逝程度。
根据具体的算法的不同,△τij、△kij和pkij(t)表达形式也有所不同,可根据具体问题而定。M.Dorigo曾给出三种不同的模型,分别是蚁周系统、蚁量系统、蚁密系统。经过一系列标准测试问题的测试,蚁周系统的性能要优于其他两种算法,故常用的就是蚁周系统更新模式:
其中,Lk为第k只蚂蚁在本次循环中所走的路径长度。
3 蚁群算法的改进[2,3,4,5,6,7]
基本蚁群算法具有很强的全局搜索能力,但是也存在一些问题,例如:搜索时间过长,执行过程中容易出现停滞现象,当问题规模较大时存在陷入局部最优解的可能。因此,很多学者对蚁群算法进行了改进。
3.1 基于优化排序的蚂蚁系统
蚁群算法和遗传算法一样,都有一个共同的缺陷就是容易陷入局部最优解。当路径差别不大,解元素之间的差异减少,致使选择概率的差异也随之减少,从而阻止了对最优解进一步的搜索。借用遗传算法中适应度排序法,将每次循环以后生成的路径进行排序,依照序列的顺序进行信息素加权更新。
3.2 最大最小蚂蚁系统
为了防止过早的算法停滞现象,德国学者T.Stuetzle和H.Hoos提出了最大最小蚂蚁系统(Max-Min Ant System,MMAS),其特点是在算法中引入了信息素最大值和最小值限制。当某条路径上的信息素大于上限,就强制为上限值;小于则为下限值,通过设定信息素的上下限。这样一方面避免了某条路径上的信息素远大于其他路径的信息素浓度,从而有效的降低了过早停滞的可能;另一方面,不会因为某条路径的信息素浓度过低而丧失发现新路径的可能。
有实验表明,MMAS算法较传统的蚁群算法相比,在寻优的有效性方面和防止算法的过早停滞方面具有更好的效果,但是,仅采用最大最小信息素的限制还不足在较长的时间里持久消除停滞现象,因此,可以对其进行进一步改进,如在算法中引入信息素平滑机制等。
3.3 自适应蚁群算法
为了既能保持蚁群算法全局搜索能力,又能提高搜索速度,王颖等人提出了自适应蚁群算法。该算法能在进行过程中自适应的改变ρ值,ρ的初始值取ρ(t0),当算法求得的最优解在固定的N次循环内没有明显得改进时候,对ρ值作出适当的调整。
式中,ρmin为ρ的最小值,可以防止ρ过小而降低算法的全局搜索能力。通过多种实验表明,该算法比一般的算法具有更好的收敛速度和稳定性,更适合于求解大规模的TSP。
4 结论
蚁群算法是一种新的仿生进化计算方法,已经在TSP、图与组合优化、Job-shop等问题上取得了成功的应用,并具有其独特的优越性。但由于蚁群算法还是一种新型的优化算法,其研究刚刚开始,还没像遗传算法和模拟退火算法等那样形成系统的分析方法和坚实的数学基础,因此算法中一些参数的确定目前还没理论上的依据,以公布的实验结果都是针对特定问题而言。
总之,蚁群算法作为一种新兴的研究领域,将会得到不断深入的研究,其模型将会更加丰富,也将相应的得到更加广泛的应用。
摘要：蚁群算法是一种新型的进化算法,在离散函数和连续函数优化中都有着广泛的应用前景。该文简要对算法的研究现状做以概述,介绍该算法的基本原理、算法的模型和若干改进算法。
关键词：蚁群算法,基本原理,改进算法
参考文献
[1]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
[2]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245.
[3]段海滨,王道波.蚁群算法的全局收敛性研究及改进[J].系统工程与电子技术,2004,26(10).
[4]邵晓巍,邵长胜,赵长安.利用信息量留存的蚁群遗传算法[J].控制与决策,2004,19(10).
[5]段海滨,王道波.一种快速全局优化的改进蚁群算法及仿真[J].信息与控制,2004,33(2).
[6]张纪会,徐心和.一种新的进化算法——蚁群算法[J].系统工程理论与实践,1999(3).