非线性规划的粒子群算法.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粒子群算法简介

粒子群算法（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个粒子组成的种群，其中第i个粒子位置为，其速度为。它的个体极值为，种群的全局极值为，按照追随当前最优例子的原理，粒子将按(4.1)、(4.2)式改变自己的速度和位置。

(4.1)

(4.2)式中j=1,2,…,D，i=1,2,…m，m为种群规模，t为当前进化代数，为分布于[0,1]之间的随机数；为加速常数。从式(4.1)中可知，每个粒子的速度由三部分组成