非线性规划的粒子群算法(1)

xx大学智能优化算法课内实验报告书院系名称：学生姓名：专业名称：班级：学号：时间：非线性规划问题的粒子群算法1.1背景介绍1.1.1非线性规划简介具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要的分支，非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的机制问题且目标函数和约束条件至少有一个是未知量的非线性函数，目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正式诞生的一个重要标志。在50年代可得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。非线性规划问题广发存在于科学与工程领域，是一类比较难以解决的优化问题，没有普遍使用的解法。传统的求解该问题的方法（如罚函数，可行方向法，以及变尺度法等）是基于梯度的方法所以目标函数与约束式必须是可微的，并且这些方法只能保证求的局部最优解。1.1.2粒子群算法简介粒子群算法（ParticleSwarmoptimization，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个粒子组成的种群1(,...,,...,)iDXxxx，其中第i个粒子位置为12(,,...,)TiiiiDxxxx，其速度为12(,,...,,...,)TiiiidiDVvvvv。它的个体极值为12(,,...,)TiiiiDpppp，种群的全局极值为12(,,...,)TggggDpppp，按照追随当前最优例子的原理，粒子ix将按(4.1)、(4.2)式改变自己的速度和位置。))()()(())()()(()()1(2211txtptrctxtptrctvtvijgjijijijij(4.1))1()()1(tvtxtxijijij(4.2)式中j=1,2,…,D，i=1,2,…m，m为种群规模，t为当前进化代数，12,rr为分布于[0,1]之间的随机数；12,cc为加速常数。从式(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：粒子群群体大小，即群体中所含个体的数量，一般取为20～100。在变量比较多的时候可以取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基本粒子群算法描述beginInitalize;%包括初始化粒子群数，粒子初始速度和位置[x,xd]=judge(x,pop_size);%调用judge函数，初始化第一次值fornum=2:最大迭代次数wk=wmax-num*(wmax-wmin)/max_g