非线性规划的粒子群算法.doc

xx大学智能优化算法课内实验报告书院系名称：学生姓名： 专业名称：班 级：学号：时间： 非线性规划问题的粒子群算法1.1 背景介绍1.1.1 非线性规划简介具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要的分支，非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的机制问题且目标函数和约束条件至少有一个是未知量的非线性函数，目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年h.w库恩和a.w塔克发表的关于最优性条件的论文是非线性规划正式诞生的一个重要标志。在50年代可得出了可分离规划和二次规划的n种解法，它们大都是以g.b.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。非线性规划问题广发存在于科学与工程领域，是一类比较难以解决的优化问题，没有普遍使用的解法。传统的求解该问题的方法（如罚函数，可行方向法，以及变尺度法等）是基于梯度的方法所以目标函数与约束式必须是可微的，并且这些方法只能保证求的局部最优解。1.1.2 粒子群算法简介粒子群算法（particle swarm optimization，pso）的基本概念源于对于鸟群捕食行为的简化社会模型的模拟，1995年由kenndy和eberhart等人提出，它同遗传算法类似，通过个体间的协作和竞争实现全局搜索系统初始化为一组随机解，称之为粒子。通过粒子在搜索空间的飞行完成寻优，在数学公式中即为迭代，它没有遗传算法的交叉及变异算子，而是粒子在解空间追随最优的粒子进行搜索。pso算法的改进主要在参数选择、拓扑结构以及与其他优化算法相融合方面。据此当前典型的改进算法有：自适应pso算法、模糊pso算法、杂交pso算法、混合粒子算法（hpso）和离散pso算法等等。其中自适应和模糊pso算法是eberhartshi研究了惯性因子对优化性能的影响，发现较大的值有利于跳出局部极小点，较小的值有利于算法的收敛。自适应pso算法通过线性地减少值动态的调整参数，而模糊pso算法则在此基础上利用模糊规则动态调整参数的值，即构造一个2输入、1输出的模糊推理机来动态地修改惯性因子。杂交和混合粒子群算法（hpso）是受遗传算法、自然选择机制的启示，将遗传算子与基本pso相结合而得。杂交pso在基本pso中引入了杂交算子，两者均取得了满意的结果，改善了算法的性能。基本pso算法是求解连续函数优化的有力工具，但对离散问题却无能为力。因此kenndy和eberhart发展了离散pso算法，用于解决组合优化问题等。在一定程度上完善发展了基本pso算法，并将其应用于旅行商问题（tsp）的求解，取得了较好的结果。目前pso已经广泛应用于函数优化、神经网络训练、模糊系统控制以及其它遗传算法的应用领域。最初应用到神经网络训练上，在随后的应用中pso又可以用来确定神经网络的结构。一般说来，pso比较有潜在的应用包括系统设计、多目标优化、分类、模式识别、调度、信号处理、决策、机器人应用等。其中具体应用实例是非线性规划的粒子群算法。总之，pso算法的应用十分广泛，它有着比较好的发展前景，值得做进一步的研究。4 基本粒子群算法4.1 粒子群算法简介粒子群算法是一个非常简单的算法，且能够有效的优化各种函数。从某种程度上说，此算法介于遗传算法和进化规划之间。此算法非常依赖于随机的过程，这也是和进化规划的相识之处，此算法中朝全局最优和局部最优靠近的调整非常的类似于遗传算法中的交叉算子。此算法还是用了适应值的概念，这是所有进化计算方法所共有的特征。在粒子群算法中，每个个体称为一个“粒子”，其实每个粒子代表着一个潜在的解。例如，在一个d维的目标搜索空间中，每个粒子看成是空间内的一个点。设群体由m个粒子构成。m也被称为群体规模，过大的m会影响算法的运算速度和收敛性。pso算法通常的数学描述为：设在一个d维空间中，由m个粒子组成的种群，其中第i个粒子位置为，其速度为。它的个体极值为，种群的全局极值为，按照追随当前最优例子的原理，粒子将按(4.1)、(4.2)式改变自己的速度和位置。 (4.1) (4.2)式中j=1,2,d，i=1,2,m，m为种群规模，t为当前进化代数，为分布于0,1之间的随机数；为加速常数。从式(4.1)中可知，每个粒子的速度由三部分组成：第一部分为粒子先前的速度；第二部分为“认知”部分，表示粒子自身的思考；第三部分为“社会”部分，表示粒子间的信息共享与相互合作。4.1.3 粒子群算法的特点粒子群算法是一种新兴的智能优化技术，是群体智能中一个新的分支，它也是对简单社会系统的模拟。该算法本质上是一种随机搜索算法，并能以较大的概率收敛于全局最优解。实践证明，它适合在动态、多目标优化环境中寻优，与传统的优化算法相比较具有更快的计算速度和更好的全局搜索能力。具体特点如下：（1）粒子群优化算法是基于群体智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索。与进化算法比较，pso是一种更为高效的并行搜索算法。（2）pso与ga有很多共同之处，两者都是随机初始化种群，使用适应值来评价个体的优劣程度和进行一定的随机搜索。但pso是根据自己的速度来决定搜索，没有ga的明显的交叉和变异。与进化算法比较，pso保留了基于种群的全局搜索策略，但是其采用的速度-位移模型操作简单，避免了复杂的遗传操作。（3）pso有良好的机制来有效地平衡搜索过程的多样性和方向性。（4）ga中由于染色体共享信息，故整个种群较均匀地向最优区域移动。在pso中gbest将信息传递给其他粒子，是单向的信息流动。多数情况下，所有的粒子可能更快地收敛于最优解。（5）pso特有的记忆使其可以动态地跟踪当前的搜索情况并调整其搜索策略。（6）由于每个粒子在算法结束时仍然保持着其个体极值。因此，若将pso用于调度和决策问题时可以给出多种有意义的选择方案。而基本遗传算法在结束时，只能得到最后一代个体的信息，前面迭代的信息没有保留。（7）即使同时使用连续变量和离散变量，对位移和速度同时采用和离散的坐标轴，在搜索过程中也并不冲突。所以pso可以很自然、很容易地处理混合整数非线性规划问题。（8）pso算法对种群大小不十分敏感，即种群数目下降时性能下降不是很大。（9）在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性）使得后期收敛速度明显变慢，以致算法收敛到一定精度时无法继续优化。因此很多学者都致力于提高pso算法的性能。4.1.4 粒子群算法的应用粒子群算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的适应性，所以广泛应用于很多学科。下面是粒子群算法的一些主要应用领域：（1）函数优化。函数优化是粒子群算法的经典应用领域，也是对粒子群算法进行性能评价的常用算例。（2）约束优化。随着问题的增多，约束优化问题的搜索空间也急剧变换，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。粒子群算法是解决这类问题的最佳工具之一。实践证明，粒子群算法对于约束优化中的规划，离散空间组合问题的求解非常有效。（3）工程设计问题。工程设计问题在许多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。现在粒子群算法已成为解决复杂调度问题的有效工具，在电路及滤波器设计、神经网络训练、控制器设计与优化、任务分配等方面粒子群算法都得到了有效的应用。（4）电力系统领域。在其领域中有种类多样的问题，根据目标函数特性和约束类型许多与优化相关的问题需要求解。pso在电力系统方面的应用主要如下：配电网扩展规划、检修计划、机组组合、负荷经济分配、最优潮流计算与无功优化控制、谐波分析与电容配置、配电网状态估计、参数辨识、优化设计。随着粒子群优化理论研究的深入，它还将在电力市场竞价交易、投标策略以及电力市场仿真等领域发挥巨大的应用潜在力。（5）机器人智能控制。机器人是一类复杂的难以精确建模的人工系统，而粒子群算法可用于此类机器人群搜索，如机器人的控制与协调，移动机器人路径规划。所以机器人智能控制理所当然地成为粒子群算法的一个重要应用领域。（6）交通运输领域。交通方面有车辆路径问题，在物流配送供应领域中要求以最少的车辆数、最小的车辆总行程来完成货物的派送任务；交通控制，城市交通问题是困扰城市发展、制约城市经济建设的重要因素。城市交通运输系统的管理和控制技术进行研究，来为缓解交通拥挤发挥巨大作用。其中在其解决方法中应用粒子群算法给解决问题提供了新的，有效的计算方式。（7）通信领域。其中包括路由选择及移动通信基站布置优化，在顺序码分多址连接方式（ds-cdma）通讯系统中使用粒子群算法，可获得可移植的有力算法并提供并行处理能力。比传统的先前的算法有了显著的优越性。还应用到天线阵列控制和偏振模色散补偿等方面。（8）计算机领域。在计算机中处理各种问题都涉及到大量的信息计算的方法选择以减少程序运行的时间，增加系统解决问题的能力，其中包括任务分配问题、数据分类、图像处理等，都得到了粒子群算法的实际问题解决效率的提高。（9）生物医学领域。许多菌体的生长模型即为非线性模型提出了用粒子群算法解决非线性模型的参数估计问题。还在分子力场的参数设定和蛋白质图形的发现。根据粒子群算法提出的自适应多峰生物测定融合算法，提高了解决问题的准确性。在医学方面，如医学成像上得到的推广应用等。4.2 基本粒子群算法4.2.1 基本粒子群算法的构成要素（1）粒子群编码方法。基本粒子群算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集0，1所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。（2）个体适应度评价。通过确定局部最优迭代达到全局最优收敛，得出结果。（3）基本粒子群算法的运行参数。基本粒子群算法有下述7个运行参数需要提前设定：r为粒子群算法的种子数，对粒子群算法其中种子数值可以随机生成也可以固定为一个初始的数值，要求能涵盖目标函数的范围内。m：粒子群群体大小，即群体中所含个体的数量，一般取为20100。在变量比较多的时候可以取100以上较大的数。max_d：一般为最大迭代次数以最小误差的要求满足的。粒子群算法的最大迭代次数，也是终止条件数。r1,r2：两个在0,1之间变化的加速度权重系数随机产生。c1,c2：加速度数，取随机2左右的值。ww：为惯性权重产生的。vk，xk：为一个粒子的速度和位移数值，用粒子群算法迭代出每一组数值。4.2.2 基本粒子群算法的形式化定义基本粒子群算法可定义为的元素：max_d粒子群算法的最大迭代次数；r给定个体的种子数值；fmax为最大的惯性权值；fmin为最小的惯性权值；pg初始群体值；m粒子群的群体大小；vk粒子移动的速度；xk粒子移动的方向；c1,c2；r1,r1随机参数变量；x,dd=judge(x,m)算法调用的求解函数。4.2.3 基本粒子群算法描述begin initalize ;%包括初始化粒子群数，粒子初始速度和位置 x,xd=judge(x,pop_size);%调用judge函数，初始化第一次值 for num=2:最大迭代次数 wk=wmax-num*(wmax-wmin)/max_gen;%计算惯性权重 r1= ; r2= %随机产生加速权重 pso算法 迭代求vk,xk； while 判断vk是否满足条件 再次重新生成加速权重系数r1;r2 pso算法 再次迭代求vk;xk数值 end 调用x,xd=judge(x,pop_size);重新计算出目标函数值 判断并重新生成pj数值； 判断并重新生成pjd数值； if 迭代前数值迭代后的数值 累加迭代次数值 end 输出随机数种子、进度、最优迭代次数、每个函数的数值和目标函数的数值 用ascii保存粒子位移的数值 用ascii保存粒子速度的数值 end5 基于粒子群算法求解非线性规划问题的设计作为运筹学的一个重要的分支，非线性规划问题求解方法一直式人们研究的重点。随着优化对象复杂性的增加，优化问题的规模也越来越大，传统的优化方法难以适应，因此人们在寻求严格最优化理论化方法和智能优化方法如遗传算法，蚁群算法等，但各种方法都有其相应的适用范围和局限性。粒子群优化算法是由kennedy和eberhart开发的一种演化计算技术。由于pso概念简单、容易实现并且没有许多参数需要调整，同时又有深刻的智能背景，即适合科学计算，又特别适合工程应用。因此，将粒子群算法应用于非线性规划，是改善求解非线性规划的效果，提高非线性规划质量的有效途径。本章就是介绍粒子群算法在非线性规划中的具体应用，设计并实现基于粒子群算法的非线性规划问题的求解。5.1 实用粒子群算法设计5.1.1 编码方法设计在matlab中编写非线性规划问题的粒子群算法编码的过程中，首先在函数中把非线性规划函数转化为一种matlab可以阅读的矩阵型的函数值，在其中添加约束条件，并作超出约束的变换的方法。在运行函数中设置各种参数数值，编写粒子群方法的实现方法，并迭代求解各个过程中目标函数的数值解，输出结果值。在所有局部解中搜索最优解，作为最终的目标函数数值。计算结束。5.1.2 适应度函数设计适应度表示个体x对环境的适应程度。分为两类，一类为针对被优化的目标函数的优化型适应度，另一类为针对约束函数的约束性适应度。其中优化型适应度和约束型适应度分别表示为 （5-1） （5-1）定义不同约束条件的权重为，则总的约束型适应度为。其中，这里，随机获得，任意选取k组，获得的k个适应值的均值作为最终的总的约束型适应度。5.1.3 基于约束适应度优先排序的约束条件处理方法因为粒子向适应度函数值高的方向群游，因此对群体中所有粒子按照适应值进行排序，基本思想是：首先比较粒子的约束适应度，适应值大的粒子排名靠前；如果约束值大的粒子排名靠前。与通常的惩罚函数方法相比，这种方法的优点是可行点的适应度总是优于非可行点的适应度。从而使得优化过程先得到可行点，然后由这些可行点及较好的不可行点的进行操作得到最优可行点。这样可以将进入可行域和得到优化点统一起来，且无需变换优化目标的适应度到大于零，并且无需设置约束适应度和目标适应度的权重，使用较为简单。5.1.4 动态邻域算子因为在适应值较好的点的邻域一定存在适应度更好的个体，为此可采用动态邻域算子方法，基本思想是：在优化的初始阶段，一个微粒的邻域就是它本身，当优化代数增加后，邻域逐渐变大，最后将包括所有的微粒。为得到邻域，首先在约束适应度空间，计算候选个体与其他所有个体的距离，其中对第个个体的距离为，找出距离最近的k个个体（k为邻域大小），其中目标函数适应值大的个体为邻域的局部历史最好值，其中最大距离为，并定义一个与当前计算代数有关的分数，如果，且，则针对进行搜索；否则使用。根据粒子邻域是否为整个群体，pso分为全局模型和局部模型，对于模型，每个粒子与整个群体的其他粒子进行信息交换，并有向所有粒子中的历史最佳位置移动的趋势。kennedy指出，模型虽然具有较快的收敛速度，但更容易陷入局部极值。为了克服全局模型的缺点，研究人员采用每个粒子仅在一定的邻域内进行信息交换，提出各种局部模型。根据现有的研究成果，本文将邻域分为空间邻域、性能空间邻域和社会关系邻域。空间邻域直接在搜索空间按粒子间的距离进行划分，如suganthan引入一个时变的欧式空间邻域算子：在搜索初始阶段，将邻域定义为每个粒子自身；随着迭代次数的增加，将邻域范围逐渐扩展到整个种群。性能空间指根据性能指标（如适应度、目标函数值）划分的邻域。社会关系邻域通常按粒子存储阵列的索引编号进行划分，这也是研究最多的一种划分手段，主要有：环形拓扑、轮形拓扑或星形拓扑、塔形拓扑、冯-诺以曼拓扑以及随机拓扑等。针对不同的优化问题，这些拓扑的性能表现各异；但总的来说随机拓扑往往对大多数问题能表现出较好的性能，其次是冯-诺以曼拓扑。5.1.5 可变惯性权重和最大速度惯性权重控制前一变化量对当前变化量的影响，如果较大，能够搜索以前未能达到的区域，整个算法的全局搜索能力加强；若较小，则前一部分的影响较小，主要是在当前解的附近搜索，局部搜索能力较强，在具体实例中的方法将惯性权重设为从0.8到0.2随时间线性减小的变量，使其在前期时有较高的探索能力以及得到合适的种子，而在后期时有较高的开发能力以加快收敛速度。最大速度决定在当前位置与最好的位置之间的区域的分辨率（或精度），如果太高，微粒可能会飞过好解，如果太小，微粒不能在局部好区间之外进行足够的探索，导致陷入局部优值。5.1.6 粒子群算法运行参数设计（1）群体大小m。群体大小m表示群体中所含个体的数量。m取值的大小与粒子群算法运行速度，群体多样性有关。一般取值为50100。在变量比较多的时候会影响粒子群算法的精确度，因此可以扩大粒子群的大小，本文引用300个粒子数。（2）权重fmax，fmin，c1，c2。fmax为初始惯性权重，fmin为终止惯性权重。c1粒子自身加速度权重系数，一般在0-2之间的取值，c2为全局加速度权重系数，一般在0-2之间取值。在算法中c1和c2为随机产生数值。（3）r1，r2。0,1范围内两个相互独立的，均匀分布的随机数。（4）粒子自身速度vk。为了减少在搜索过程中粒子离开搜索空间的可能性，vk通过被限定于一定的范围内，即，当然，亦可根据具体情况，将搜索空间限定于一定的范围内，粒子的位移内。（5）代沟g。这里我们由父代生成子代过程中，不是单纯地直接遗传，而是进行两次遗传操作。将当前群体mi作为父代，对父代mi进行遗传操作（交叉、变异）产生群体大小相同的子代mi1，在对父代mi和子代mi1按适应度值大小降序排列，将种群mi和mi1中前1/2的较好个体整合成一个种群mx2，对种群mx2进行遗传操作（交叉、变异）产生群体大小相同的孙代mi2。由此得到3个群体大小相同的种群mi、mi1、mi2。对3个种群按适应度大小进行降序排列，用mi1、mi2中前1/3的个体（即最好的m/3个个体）淘汰mi中后2/3的个体，新形成的种群mx3，将种群mx3作为子代种群mi+1。5.2 非线性规划的粒子群算法程序设计5.2.1 算法过程描述由基本粒子群算法的算法描述再结合本次毕业设计的实际情况，我们设计了以下的具体算法流程。步骤如下：（1）初始化粒子群算法的参数，最大迭代次数（终止条件）max_d=1000；粒子群大小m=300；给定种子数值为r=20880001。（2）设置初始judgex,m函数及初始条件和初始计算结果。（3）对粒子群赋初始值。（4）设置惯性权重值fmax=0.8；fmin=0.2。随机产生加速度权重系数。（5）进入算法迭代，计算惯性权重系数wk，同时随机产生加速权重系数r1,r2，算法迭代。（6）判断粒子速度防止速度超出范围，再次进行粒子群算法重新计算粒子速度vk和粒子位移xk。（7）调用judge函数重新计算目标函数数值。（8）判断num-1次数值与num次数值，并重新生成新的目标函数值。（9）判断目标函数数值的大小，并ww=num生成进度数值。（10）输出种子数值、进度数、最优迭代次数、目标函数数值。（11）用ascii保存粒子位移数值。（12）用ascii保存粒子速度数值。（13）绘图出目标函数数值的变化情况。5.2.2 粒子群算法程序流程图由以上程序过程描述我们