粒子群优化算法预备知识.ppt

粒子群优化算法（Particle Swarm Optimizer,PSO）基于群智能方法的演化计算技术 预备知识无约束最优化问题 其中 ，通常称变量为决策变量(decision variables)，称 为目标函数(objective function)。预备知识一般约束非线性优化问题的数学模型为：可行集（域）预备知识 为等式约束，为不等式约束，等式约束和不等式约束统称为约束条件(constraint condition)。为英文“subject to”的缩写，表示“受限制于”基本概念若有 使得 ，均有 ，则称 为最优化问题 的（全局）最优解(global optimal solution)（点）或全局极小点。若 使得 ，均有 ，则称为最优化问题 的严格全局极小点。基本概念若存在 的一个邻域 使得 均有 ，则称为最优化问题 的（局部）最优解(local optimal solution)（点）或局部极小点(local minimum point)，其中 而 为向量的模。若 使得 ，均有 则称 为最优化问题 的严格局部极小点点 称为最优解，其所对应的目标函数值 称为最优值，通常用 表示。最优化算法的一般结构 定理定理（一阶必要条件）若 具有一阶连续偏导数，是最优化问题 的局部极小值点（局部最优解），则必有迭代法的基本思想是：首先给出 最优解的一个初始估计点（称为初始点）然后按照某一迭代规则得到一个点列 ，使得当该点列是有穷点列时，其最后一个点是最优化问题 的最优解；当该点列是无穷点列时，有极限点，且其极限点是该最优化问题的最优解。如何得到迭代点列呢？即在得到点 后，如何确定点 。我们这样考虑：因为 是一个向量，而向量由其方向和长度来确定，即 ，其中 是向量（称为搜索方向），是正实数，称为步长。当它们确定后，由 可确定 ，这样就可以得到一个点列 ，从而确定一个算法。优化问题的分类根据最优化问题是否有约束条件，可分为约束最优化问题和无约束最优化问题。若目标函数和约束条件中出现的函数均为线性函数，称该最优化问题为线性规划（Linear Programming）问题，否则称为非线性规划（Nonlinear Programming）问题,即目标函数和约束条件中出现的函数至少有一个不是线性函数，称该最优化问题为非线性规划问题。优化问题的分类若目标函数为二次函数，而约束条件为线性函数，称该最优化问题为二次规划（Quadratic Programming）问题，显然二次规划是最简单的一种非线性规划问题。若优化变量只能取整数值时，称该最优化问题为整数规划（Integer Programming）问题，特别地，若整数规划问题中的优化变量只能取值为0或1，称之为0-1规划。当目标函数不是数量函数而是向量函数时，称之为多目标函数，等等。最优化问题举例例1曲线拟合问题假设热敏电阻R是温度的函数，函数关系如下其中 是待定参数。通过实验测定 和R的15组数据如表1：确定参数 使曲线尽可能地靠近所有的实验点。最优化问题举例利用最小二乘法原理求解，即确定参数的一组值，使其偏差的平方和 最小。即最优化问题举例例2 生产安排问题某工厂生产甲、乙、丙三种产品，每件产品所消耗的材料、工时、盈利见表2 已知该工厂每天的材料消耗不超过600千克，工时不超过1400小时，问每天生产甲、乙、丙三种产品各多少事的盈利最大？最优化问题举例设每天生产甲、乙、丙三种产品分别为 件，因此盈利 ，其相应的材料限制为工时限制为再考虑自然限制因此生产安排问题就是在上述限制条件下，使其盈利达到最大。其数学表达式为：最优化问题举例例3 投资决策问题设在一段时间（比如三年）内，有B亿元的基金可用于投资，有m个项目 可供挑选。若对项目 进行投资，需花费 亿元，可获益 亿元，试确定最佳的投资方案。引入变量 则需满足的条件为最佳的投资方案应该为：投资少，收益大。若要投资少，则 ；若要收益大，则 。测试函数常见的测试函数见附件约束最优化问题约束最优化问题是实际应用中经常遇到的一类数学规划问题，其解法是人们非常感兴趣的，因此许多研究者对该问题进行了深入的研究，提出了许多行之有效的解法。但是，由于问题的复杂性，无论在理论方面还是应用方面都有很大难度，目前尚无一种解法对任意一种约束最优化问题普遍有效，且求得的解大都是局部最优解。