课程设计蜂群算法及其应用.doc

课 程 设 计 论 文题 目 蜂群智能算法与应用 学院 物理与信息科学学院 专 业 通信工程 班 级 通信工程04班 学生姓名 邹海洋 学 号 2010130436 2013 年 9月 15 日至 2010 年 9 月 30 日 共 2 周指导教师 江沸波 2013年 9月 27日蜂群智能算法及其应用1 研究背景。 伴随着当今社会、经济、文化和科技日新月异的发展，现实生活中面临着许多复杂的非线性大系统和快速反应性系统，这使得我们传统的优化方法逐渐陷入困境。于是，人们开始寻找更快、更好的方法去解决这些复杂问题。在自然界中，那些不起眼的群居低智能的生物表现出来的令人叹为观止的复杂的群体智慧给予我们启迪，如：蚁群、鸟群、蜜蜂群、鱼群等。在群居生物中，单个个体的智能是简单的，但若干个个体组成的群体却表现出远远超出个体相加的智慧。在群体中，个体间相互合作、相互协调的自组织能力能够完成非常复杂的任务。这种现象引起众多学者的关注，人们开始研究现象背后存在的机理，并用计算机仿真其中可循的规律，用以解决传统优化方法难以解决的复杂问题。其中，较为典型且广泛应用的群体智能算法有：蚁群算法、微粒群算法以及蜂群算法等。二十世纪初期以来，在优化领域中，传统的方法，如：线性规划、非线性规划、对策论、多目标规划、决策论排队论、随机规划、库存论等，不仅在理论上的研究有很大的发展，而且在军事、经济、城市建设规划、工厂生产规划、最优设计等各个方面的应用取得显著成就。但伴随着社会、经济和科学技术的飞速发展，在生产生活中出现的许多复杂的非线性系统和快速反应系统等不断的呈现在我们面前，使得传统的优化方法遇到了空前的挑战。群体智能是指由大量数目的智能个体组成的具有智能的群体，这个群体体现出来的智能绝对不是个体智能的简单相加，而是超过这个和的智能现象。在进行目标搜索时，单个个体虽然也能够寻找到目标，但往往只是局限于局部，并不是全局最好的结果。个体在空间中随机搜寻，在没有得到整个群体的信息反馈时，它的搜索是随机的、低智能的、无规律的。只有群体问的个体相互合作、相互协调，进行信息共享时，才能表现出来在全局中针对目标的寻优特征。作为智能个体，就其大小和功能来说，又是相对的，要根据所要解决的具体问题而定。另外，群体智能中的个体，在整个群体寻优过程中也并不能时刻保证都具有寻优的特征，其智能寻优方式的实现足通过整个智能群体的优化特征而体现出来的。人工蜂群算法作为典型的群体智能算法，是基于种群寻优的启发式搜索算法，充分发挥群体中个体问的信息传递，在蜂巢周围寻找到路径最短，食物最丰富的食物源。由于整个觅食过程与旅行商问题的相似性，该算法适合用来解决旅行商的最短路径问题，并取得较好的结果。蜂群算法(BCO，Bee Colony Optimization)是受到自然界的蜜蜂行为启发而提出的一种新颖的元启发式优化算法。根据所受启发的生物机理的不同，蜂群算法可分为两大类：基于蜜蜂繁殖机理的蜂群算法(BCO on propagating)。基于蜜蜂采蜜机理的蜂群算法(BC0 on gathering)。两种思想各有其独特的实现原理和发展轨迹。对于基于繁殖的蜂群算法。Abbass发展出一种蜜蜂繁殖优化模型(BMO，Bee Mating Optimization)。 Bozorg Haddad和AAfshar共同将其发展并应用基于离散变量的水库优化问题中。随后，Bozorg Haddad等将同一理论在三种数学问题的测试平台上进行了应用。蜜蜂的采蜜行为是一种典型的群体智慧行为。Yang发展出一种虚拟蜜蜂理论(VBA，virtual bee algorithm)来解决数值优化问题。VBA中，一群虚拟蜜蜂初始时随机分布在解空间中：这个蜜蜂根据判决函数计算的适应度来寻找附近的花蜜源。理论中，解的优化程度可以用蜜蜂之间交流的剧烈程度来衡量。对于多变量数值优化问题，Karaboga根据蜜蜂采集行为设计了虚拟蜜蜂种群模型(ABC，artificial bee colony algorithm)，并和Basturk一起将ABC模型与GA进行了性能上的比较，并进一步与其他比较著名的元启发式理论如：差分进化(DE)，粒子群(PSO)在非约束数值优化问题上进行了仿真比较。进而ABC理论被扩展应用到解决约束(CO，constraint optimization)问题，并在13种比较著名的约束优化问题上与DE，PSO进行了比较。目前，ABC模型的研究主要集中在人工神经网络的训练上。2 蜂群算法的理论基础Seely最早提出一种蜂群的群居行为为模型。模型中，群体中的各个角色蜜蜂，只是完成简单的、低智商的任务；但群体中的个体通过舞蹈、气味等信息交互方式使整个群体协同能够完成较为复杂的任务，如建筑蜂巢、繁衍后代和觅食等。Karaboga D在2005年将蜂群算法应用到函数值优化问题上，并提出系统的ABC(Artificial Bee Colony Algorithm)算法，取得很好的效果。在人工蜂群算法中，食物源的位置表示待优化问题的一个可行解，食物源的丰富程度代表解的质量，即适应度。在模型中，我们通常设：引领蜂的数量=跟随蜂的数量=群体中解的数量。算法中，初始化生成M个解，对于每个解都是一个D维向量。而后，蜜蜂开始对全部的食物源进行循环搜索，最大循环次数为MCN。其中，引领蜂会先对全局进行搜索，并比较搜索前后食物源的丰富程度，蜜蜂会选择食物源较为丰富的目标。当所有的引领蜂完成搜索后，他们会回到信息交流区(舞蹈区)把自己掌握的关于食物源的信息与其他蜜蜂进行信息共享。跟随蜂则会根据引领蜂提供的信息按照一定的概率选择引领蜂进行跟随。越丰富的食物源被选择的概率越大。然后，跟随蜂会和引领蜂一样进行邻域搜索，并选择较好的解。人工蜂群算法中，蜜蜂的采蜜行为和函数优化问题的对应关系如表21所示： 表1 蜂群觅食行为与函数优化的对应关系 蜂群采蜜行为可行解优化问题蜜源位置蜜源大小收益度寻找及觅食的速度最大收益度可行解可行解的质量可行解优化速度最优解初始化时，随机生成Ns个可行解并计算函数值，将函数值从优到劣排名，前50作为蜜源位置即引领蜂，后50为跟随蜂。随机产生可行解的公式如下： (1)其中j1，2,.，Q为Q维解向量的某个分量。蜜蜂记录自己到目前为止的最优值，并在当前蜜源附近展开邻域搜索，产生一个新位置替代前一位置的公式为： (2) 其中j1，2,.，Q，k(1，2,.，sn)，k为随机生成且ki，为一1，1之间的随机数。蜜蜂采蜜时采用贪婪原则，将记忆中的最优解和邻域搜索到的解做比较，当搜索解优于记忆中的最优解时，替换记忆解；反之，保持不变。在所有的引领蜂完成邻域搜索后，引领蜂跳摆尾舞与跟随蜂共享蜜源信息。跟随蜂根据蜜源信息以一定概率选择引领蜂，收益度大的引领蜂吸引跟随蜂的概率大于收益度小的引领蜂。同样，跟随蜂在采蜜源附近邻域搜索，采用贪婪准则，比较跟随蜂搜索解与原引领蜂的解，当搜索解优于原引领蜂的解时，替换原引领蜂的解，完成角色互换；反之，保持不变。ABC算法中，跟随蜂选择引领蜂的概率公式为： (3)按照如下公式计算适应值： (4)根据f是否大于零， 式(3)中，为第f个解的适应值，对应食物源的丰富程度。食物源越丰富,被跟随蜂选择的概率越大。为防止算法陷入局部最优，算法1imit次迭代没有改进，放弃该解，由侦察蜂产生一个新的位置代替。人工蜂群算法的算法流程：ABC算法的流程为：1：初始化种群；2：cycle=l：3：repeat：4:雇佣蜂根据公式（2）在解的邻域内产生新解（食物源位置），其中，k是i邻域内的一个值，是一1，1之间的随机数；5:应用贪婪原则选择在和之问做出选择；6：根据公式(3)(4)计算转移概率；7：根据转移概率，跟随蜂选择引领蜂进行跟随，并根据公式(2)产生一个新解； 8：跟随蜂应用贪婪原则选择在和之问做出选择； 9：放弃一个解，角色转变成侦查蜂，并根据公式(1)产生一个新解； 10：记录最好解； 11：cycle=cycle+1； 12：达到最大循环数，最Pcycle=mcn。，从上述算法中我们不难看出，ABC算法的核心由三个部分构成： 1引领蜂：进行邻域搜索； 2跟随蜂：对目标进行“开采”； 3侦察蜂：对目标进行“探索”。3 蜂群算法解决函数优化问题3.1函数优化问题的描述目标优化问题可以描述为： Max f(x ) xS (5)或：Min f( x) xS (6)这里S 称为搜索空间，f(x)：S称为目标函数。 (5)式描述的优化问题称为极大化问题,(6)式描述的称为极小化问题。 当把f(x)看成是一序列的函数时上述的问题就转变为多目标优化问题。 对很多实际问题进行数学建模后。可将其抽象为一个数值函数的优化问题。由于问题种类的繁多、影响因素的复杂。这些数学函数会呈现出不同的数学特征，比如连续的、离散的、凸的、凹的、单峰值的、多峰值的函数等等，经常遇到的函数还有这些不同数学特征的组合。除了在函数是连续、可求导、低阶的简单情况下可解折地求出其最优解外。大部分情况需要通过数值计算方法来进行近似优化计算，尽管人们对这个问题研究了很多年。但至今仍无一种既能处理各种不同的复杂函数、又具有良好求解结果的数值计算方法。特别是当问题的规模比较大时，优化计算时的搜索空间急 剧扩大，人们认识到要严格地求出其最优解不太现实。所以需要研究出一种能够在可接受的时间和可接受的精度范围内求出数值函数近似最优解的方法或通用算法。蜂群算法提供了求解复杂系统优化问题的通用框架，函数优化正是其最成熟的应用域。也是对蜂群算法进行性能评价的常用算倒。在对各种复杂形式的测试函数的计算中。由于蜂群算法直接以目标函数值作为搜索信息。同时使用多个搜索点进行索，且这种概率搜索始终遍及整个解空间，都能找到几乎全局最优解。对于一些非线性、多模型、多目标的函数优化问题，在其他优化方法较难求解时遗传算法也能方便地得到较好的结果。 实践表明，遗传算法求解函数优化问题的计算教率比较高、适用范围相当广。与传统的优化方法相比遗传算法具有如下特点：具有简单通用、鲁捧性强、适 于并行处理以及高效、实用等显著优点。3.2 解决问题的步骤(1) 编码在遗传算法的运行过程中，它不对所求问题的实际决策变量直接进行操作，而是对表示可行解的个体编码施加选择、交叉和变异等遗传操作。将一个问题的可行解从其可行解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。典型的遗传算法都采用二进制的编码方式，在本文中我们也采用这种与自然界中的实际情况相对应的编码方式。但是在多个变量的情况下，传统的整体编码是用一个一维数组来按顺序存放所有的基因。这样的编码方式明显地存在着问题：随着自变量维数的增加或求解精度要求的提高，整个位串的长度会迅速地增加，这样，整个位串的长度将变得难以忍受，不方便操作；此外，一旦位串过长,将不可避免地导致重复操作，而且由于位串过长，还会降低杂交和变异操作的结果，致使算法易陷于局部最优或增加运行时间。为了解决这些问题，我们采用一种改进的二进制编码方式独立编码方式。它将每个变量都相互独立开来，采用多维的数组来表示多维的变量，用独立编码方式就表示为： x1=0110110100 ，x2=1101001011 chromn0= 0110110100 chromn1= 1101001011 实验表明，独立编码较整体编码具有良好的收敛性，能使函数较好地逼近于极值。原因主要在于当杂交和变异概率不变时，原始的整体编码由于精度要求，导致位串过长，而其中相当大的一部分位串只表示小数点后的数值，所以若杂交和变异算子作用在这一部分上，则对数值的改变不大。而独立编码由于大大缩短了位串长度，所以使得杂交和变异算子有很大可能作用到代表小数点以前的数值位串上，致使自变量的数值有较大改变。这就能使算法有效地跳出局部最优解陷阱，更好地接近全局最优解。(2) 选择与交叉蜂后以一定的速率穿梭于空间中的不同区域，并在各个区域内随机地与碰到的雄蜂进行交配。在婚飞的开始，给蜂后赋予一定量的能量，在能量消耗到零或某一限度时或在受精囊装满时返回蜂巢。雄蜂提供给后代一半的基因，因此保证雄蜂的高适应度也有利于产生适应度较高的幼蜂。为此，我们使用一个模拟的退火算法来对雄蜂进行选择。按照退火算法的原理，令当前的雄蜂为D0，随机产生下一个用于交配的雄蜂为 D1，如果f (D1) f (D0) 则D1被接受为当前雄蜂(f(D)表示雄蜂 D 的适应度) ，准备与蜂后交配。否则 D1仅以概率: (7) 被接受。s（t）表示蜂后在 t 时刻的速率，随着时间的推移，S（t）的值会越来越小，则接受不良个体的概率也就越来越小，所以总能保持雄蜂的高适应度。雄蜂与蜂后交配的随机率用下式表示： (8) 此处，prob（Q ，D）是将 D的精子加入到蜂后Q的受精囊的概率，也就是指交配成功的概率；f（t）是 D 的适应度 f（D）与Q 的适应度 f（Q）的绝对差值；S（t）表示蜂后在t 时刻的速率。表面上看来这个函数有些类似退火算法，当蜂后在刚开始婚飞因而速率很大时或是雄蜂的适应度和蜂后的一样高时，交配的概率很大。随着时间的推移，蜂后的速率和能量以下面的方式衰减： (9) (10) 此处， 是一个因子，0 ，1 ；r 是每次转移后能量的消耗量。（3）变异和灾变自然界中的变异率是进化的动力，只有通过变异率才能使后代产生前代没有的特性，为进化提供条件。同时变异率设置得是否合适对于算法的表现也有很大的影响。如果变异率太小则某位的有效基因可能经过好多代的进化都不会出现，算法容易陷入局部解中；如果变异率设得太大则经常变异容易丢失一些有效基因，反而倒丧失了启发性而变得更像随机搜索。一般情况下，变异率设在 0.0001 0.1就比较合适了。在自然界中，有时会因为环境的突然性的巨大变化而使物种发生很大的改变，这时原有的基因平衡被打破，创造出完全不同的染色体，生物的性状发生很大的变化。将这种思想应用于我们的蜂群算法中，有利于进化跳出局部极值点，快速、准确地搜索出全局最优解。但是，灾变率的选择也不是任意的，它应该根据具体的情况而合理地设定。多次实验的结果表明：选择灾变率的标准是要在整个的进化过程中保证发生1 到2 次的灾变。否则，若灾变率设得太小，可能整个进化完成后都没有发生一次灾变，也就丧失了设置灾变率的意义；若灾变率太大，则多次的反复灾变就很容易丢失经过多代进化积累起来的有利基因组合。3.3 核心参数的设置改进后的ABC算法中需设定的参数有三个：种群数SN，搜索代数MCN，limit 。（1）Rosenbrock 函数 (11) （2）Griew函数 (12) （3）Schaffer函数 (13) 二维Rosenbrok函数 是一个非凸函数，它在（1 ，1）处达到极小值；f2(X) 是由Griewangk提出的。它的全局极小是xi=0 ，i=1 ，2 ，。其局部极小点是xi k* *,i=1,2, ，n，k=0 ，1 ，2 ，。函数,算法参数设置为：种群规模SN=100；终止代MCN=300limit=100 ，T0=100。函数 ，算法参数设置为：种群规模SN=50；终止代数MCN=500limit=50 ，T0=100。函数 ，算法参数设置为：种群规模SN=30；终止代数MCN=60；limit=10 ，T0=100。3.4 核心代码clear allclose allclc%/* Control Parameters of ABC algorithm*/NP=20; %/* The number of colony size (employed bees+onlooker bees)*/FoodNumber=NP/2; %/*The number of food sources equals the half of the colony size*/limit=100; %/*A food source which could not be improved through limit trials is abandoned by its employed bee*/maxCycle=2500; %/*The number of cycles for foraging a stopping criteria%/* Problem specific variables*/objfun=Sphere; %cost function to be optimizedD=100; %/*The number of parameters of the problem to be optimized*/ub=ones(1,D)*100; %/*lower bounds of the parameters. */lb=ones(1,D)*(-100);%/*upper bound of the parameters.*/runtime=1;%/*Algorithm can be run many times in order to see its robustness*/%Foods FoodNumberD; /*Foods is the population of food sources. Each row of Foods matrix is a vector holding D parameters to be optimized. The number of rows of Foods matrix equals to the FoodNumber*/%ObjValFoodNumber; /*f is a vector holding objective function values associated with food sources */%FitnessFoodNumber; /*fitness is a vector holding fitness (quality) values associated with food sources*/%trialFoodNumber; /*trial is a vector holding trial numbers through which solutions can not be improved*/%probFoodNumber; /*prob is a vector holding probabilities of food sources (solutions) to be chosen*/%solution D; /*New solution (neighbour) produced by v_ij=x_ij+phi_ij*(x_kj-x_ij) j is a randomly chosen parameter and k is a randomlu chosen solution different from i*/%ObjValSol; /*Objective function value of new solution*/%FitnessSol; /*Fitness value of new solution*/%neighbour, param2change; /*param2change corrresponds to j, neighbour corresponds to k in equation v_ij=x_ij+phi_ij*(x_kj-x_ij)*/%GlobalMin; /*Optimum solution obtained by ABC algorithm*/%GlobalParamsD; /*Parameters of the optimum solution*/%GlobalMinsruntime; /*GlobalMins holds the GlobalMin of each run in multiple runs*/GlobalMins=zeros(1,runtime);for r=1:runtime% /*All food sources are initialized */%/*Variables are initialized in the range lb,ub. If each parameter has different range, use arrays lbj, ubj instead of lb and ub */Range = repmat(ub-lb),FoodNumber 1);Lower = repmat(lb, FoodNumber 1);Foods = rand(FoodNumber,D) .* Range + Lower;ObjVal=feval(objfun,Foods);Fitness=calculateFitness(ObjVal);%reset trial counterstrial=zeros(1,FoodNumber);%/*The best food source is memorized*/BestInd=find(ObjVal=min(ObjVal);BestInd=BestInd(end);GlobalMin=ObjVal(BestInd);GlobalParams=Foods(BestInd,:);iter=1;while (iter = maxCycle),% EMPLOYED BEE PHASE % for i=1:(FoodNumber) %/*The parameter to be changed is determined randomly*/ Param2Change=fix(rand*D)+1; %/*A randomly chosen solution is used in producing a mutant solution of the solution i*/ neighbour=fix(rand*(FoodNumber)+ %/*Randomly selected solution must be different from the solution i*/ while(neighbour=i) neighbour=fix(rand*(FoodNumber)+1; end sol=Foods(i,:); % /*v_ij=x_ij+phi_ij*(x_kj-x_ij) */ sol(Param2Change)=Foods(i,Param2Change)+(Foods(i,Param2Change)-Foods(neighbour,Param2Change)*(rand-0.5)* % /*if generated parameter value is out of boundaries, it is shifted onto the boundaries*/ ind=find(solub); sol(ind)=ub(ind); %evaluate new solution ObjValSol=feval(objfun,sol); FitnessSol=calculateFitness(ObjValSol) % /*a greedy selection is applied between the current solution i and its mutant*/ if (FitnessSolFitness(i) %/*If the mutant solution is better than the current solution i, replace the solution with the mutant and reset the trial counter of solution i*/ Foods(i,:)=sol; Fitness(i)=FitnessSol; ObjVal(i)=ObjValSol; trial(i)=0; else trial(i)=trial(i)+1; %/*if the solution i can not be improved, increase its trial counter*/ end end;% CalculateProbabilities %/* A food source is chosen with the probability which is proportioal to its quality*/%/*Different schemes can be used to calculate the probability values*/%/*For example prob(i)=fitness(i)/sum(fitness)*/%/*or in a way used in the metot below prob(i)=a*fitness(i)/max(fitness)+b*/%/*probability values are calculated by using fitness values and normalized by dividing maximum fitness value*/prob=(0.9.*Fitness./max(Fitness)+0.1;% ONLOOKER BEE PHASE %i=1;t=0;while(tFoodNumber) if(randprob(i) t=t+1; %/*The parameter to be changed is determined randomly*/ Param2Change=fix(rand*D)+1; %/*A randomly chosen solution is used in producing a mutant solution of the solution i*/ neighbour=fix(rand*(FoodNumber)+1; %/*Randomly selected solution must be different from the solution i*/ while(neighbour=i) neighbour=fix(rand*(FoodNumber)+1; end; sol=Foods(i,:); % /*v_ij=x_ij+phi_ij*(x_kj-x_ij) */ sol(Param2Change)=Foods(i,Param2Change)+(Foods(i,Param2Change)-Foods(neighbour,Param2Change)*(rand-0.5)*2; % /*if generated parameter value is out of boundaries, it is shifted onto the boundaries*/ ind=find(solub); sol(ind)=ub(ind); %evaluate new solution ObjValSol=feval(objfun,sol); FitnessSol=calculateFitness(ObjValSol); % /*a greedy selection is applied between the current solution i and its mutant*/ if (FitnessSolFitness(i) %/*If the mutant solution is better than the current solution i, replace the solution with the mutant and reset the trial counter of solution i*/ Foods(i,:)=sol; Fitness(i)=FitnessSol; ObjVal(i)=ObjValSol; trial(i)=0; else trial(i)=trial(i)+1; %/*if the solution i can not be improved, increase its trial counter*/ end; end; i=i+1; if (i=(FoodNumber)+1) i=1; end; end;%/*The best food source is memorized*/ ind=find(ObjVal=min(ObjVal); ind=ind(end); if (ObjVal(ind)limit) Bas(ind)=0; sol=(ub-lb).*rand(1,D)+lb; ObjValSol=feval(objfun,sol); FitnessSol=calculateFitness(ObjValSol); Foods(ind,:)=sol; Fitness(ind)=FitnessSol; ObjVal(ind)=ObjValSol;End;fprintf(er=%d ObjVal=%gn,iter,GlobalMin);iter=iter+1;end % End of ABCGlobalMins(r)=GlobalMin;end; %end of runssave all3.4 实验结果和分析(1)函数f1(X) ，50