毕业论文：非线性规划问题的粒子群算法

非线性规划是世纪年代才开始形成的门新兴学科。

年库恩和塔克发表的关于最优性条件的论文是非线性规划正式诞生的个重要标志。

在年代可得出了可分离规划和二次规划的种解法，它们大都是以丹齐克提出的解线性规划的单纯形法为基础的。

年代末到年代末出现了许多解非线性规划问题的有效的算法，年代又得到进步的发展。

非线性规划在工程管理经济科研军事等方面都有广泛的应用，为最优设计提供了有力的工具。

非线性规划问题广发存在于科学与工程领域，是类比较难以解决的优化问题，没有普遍使用的解法。

传统的求解该问题的方法如罚函数，可行方向法，以及变尺度法等是基于梯度的方法所以目标函数与约束式必须是可微的，并且这些方法只能保证求的局部最优解。

粒子群算法简介粒子群算法，的基本概念源于对于鸟群捕食行为的简化社会模型的模拟，年由和等人提出，它同遗传算法类似，通过个体间的协作和竞争实现全局搜索系统初始化为组随机解，称之为粒子。

通过粒子在搜索空间的飞行完成寻优，在数学公式中即为迭代，它没有遗传算法的交叉及变异算子，而是粒子在解空间追随最优的粒子进行搜索。

算法的改进主要在参数选择拓扑结构以及与其他优化算法相融合方面。

据此当前典型的改进算法有自适应算法模糊算法杂交算法混合粒子算法和离散算法等等。

其中自适应和模糊算法是研究了惯性因子对优化性能的影响，发现较大的值有利于跳出局部极小点，较小的值有利于算法的收敛。

自适应算法通过线性地减少值动态的调整参数，而模糊算法则在此基础上利用模糊规则动态调整参数的值，即构造个输入输出的模糊推理机来动态地修改惯性因子。

杂交和混合粒子群算法是受遗传算法自然选择机制的启示，将遗传算子与基本相结合而得。

杂交在基本中引入了杂交算子，两者均取得了满意的结果，改善了算法的性能。

基本算法是求解连续函数优化的有力工具部最优解结束的原因。

样本数对算法运行时间的影响为了能得到样本数对算法运行时间的影响，我们需要对不同大小的样本集进行聚类，统计运行时间，分析统计结果。

我们分别用两种算法对大小分别为的样本集进行聚类。

为了保证统计的公正性，我们对每个样本集用不同的随机种子数运行次，用次所得时间的平均值作为该样本集的实际运行时间，时间单位为纳秒。

实际结果如表所示。

表对不同的样本数算法运行时间统计表对上表按列求平均值，将统计结果作为实际运行时间，得到表。

表实际运行时间表为了直观地观察样本数对算法运行时间的影响，我们将上表数据在图像中表示出来。

得到运行时间变化曲线图，如图，所示。

图随样本数变化运行时间的变化曲线图随样本数变化运行时间的变化曲线上节我们分析了遗传算法和算法的时间复杂度。

遗传算法的时间复杂度为是，当迭代次数和种群大小不变，仅改变样本数时，遗传算法的时间复杂度是线性变化的。

由图我们可以看到遗传算法运行时间时随着样本数的线性增加也是呈线性增长。

算法的时间复杂度是，簇个数时确定的，是不确定的，所以当样本数线性增大时，的运行时间时不确定的。

由图我们可以看到当样本数线性增加时，算法的运行时间时非线性变化的，增长幅度随样本数增加成逐渐变大。

由以上分析我们可以看出，遗传算法的时间性能比算法要好。

算法的发展与展望算法的展望与发展粒子群优化算法自提出以来，得到了国际上相关领域众多学者的关注和研究，成为国际化计算研究的热点。

目前，出现了多种改进算法，且已经应用于许多科学和工程领域，特别是在非线性规划等领域的应用。

算法的发展趋势纵观国内外粒子群优化算法的研究和应用现状，本人归纳了粒子群优化算法的发展趋势算法的理论分析虽然粒子群算法在实际应用中被证明是有效的，但其算法分析还不够成熟和系统。

利用有效数学工具对算法的收敛性，收敛速度，参数选择以及参数鲁棒性等进行分析将是未来的发展趋势之。

算法的改进目前对算法的改进主要有两个方面预期它理论结合改进和与其它算法结合改进。

已有的协同算法随机算法有拉伸功能的算法耗散算法都是与其它领域的结合改进，而混合算法杂交算法基于模拟退火的算法免疫算法自适应变异的算法都是与其它算法结合。

今后的改进方向仍以提高算法的性能为目的，提高收敛精度和速度，增强全局搜索能力等。

另外，与其它各种智能方法和先进技术的融合还不足，粒子群优化算法必将通过与其它优化算法相比较，将其优点与自身优点相结合，扬长避短。

算法的应用由于算法具有计算速度快，概念简明，依赖的经验参数少，实现方便等特点它已成为应用于诸多领域，特别是优化问题的求解，又粒子群优化算法中的微粒速度和位置都是连续变量，能够直接应用于连续优化问题，而对于非线性规划这类问题，需要做些调整和改变才能应用求解。

算法的研究最终是为了应用，而应用又反作用于算法的研究，对深化算法有非常重要的意义。

粒子群优化算法是种新兴的基于群体智能的进化算法，与遗传算法和模拟退火算法相比，算法缺乏系统的理论分析方法，其数学基础相对薄弱，且还存在许多不完善和未涉及到的问题，在收敛性理论计算性能实现技术和参数的设置等方面缺乏严密的数学基础，其应用大多数仍然依靠经验和实验，对具体问题和应用环境的依赖性比较大，如何将算法应用与离散多目标约束不确定动态等优化问题将是粒子群优化算法的主要研究方向。

然而，就非线性规划领域而言，其研究的复杂问题有多种解法，在其中选择合适的仍没有套系统的理论和方法。

如何选择优化和调整算法参数，使得算法既能避免早熟又能比较快速的收敛，较好地应用于生产调度这类组合优化问题必将有着十分重要的意义。

总结本文详细介绍了非线性规划粒子群算法和传统非线性规划的基本理论。

分析了传统非线性规划的两个致命缺陷是容易陷入局部最优解，二是对初始值敏感。

详细介绍了粒子群算法的优点简单，通用，鲁棒性强，不要求目标函数可导，是种由局部最优到全局搜索算法。

由此我们意识到将粒子群算法应用于非线性规划是提高求解效果的有效途径。

在充分理解粒子群算法基本理论，算法思想，关键技术的基础上，结合实际情况，设计并最终实现了基于粒子群算法的非线性规划求解过程。

同时我们也通过实例并实现了最经典的传统非线性规划牛顿法。

通过比较两种算法的实际运行结果，分析两者之间的性能差异。

通过理论分析以及对测试数据的统计分析，我们可以看到基于粒子群算法的聚类分析算法与传统聚类分析算法相比，聚类效果整体性较好，聚类结果更合理，性能更稳定，鲁棒性强，受随机因素影响小，有效地克服了传统算法受随机因素影响较大，容易陷入局部最优解的缺陷。

但遗传算法程序设计复杂，算法耗费大量存储空间和运行时间。

但在硬件成本大幅下降的今天，用空间和时间换取最佳结果是值得的。

传统算法程序简单，易于实现，耗费资源少，但聚类效果较差，性能不稳定，受随机因素影响较大，容易陷入局部最优解。

同时我们也看到，有时候传统算法所得结果比遗传算法要好，这说明传统算法也有其可取之处，遗传算法无法完全取代传统算法。

通过几个月的努力，即将完成论文，由于本人能力有限，本论文中或多或少地会存在些缺点，所设计的程序难免有些不足，还恳请各位老师和同学给予批评和指正。

致谢光阴似箭日月如梭，四年的本科学习很快就要过去了，在论文即将完成之际，我衷心的感谢所有指导关心和帮助我的老师同学和朋友。

首先感谢我的指导老师厍向阳副教授，本文的所有工作都是在厍老师的悉心指导和严格要求督促下完成的。

在课题的研究和论文的写作过程中，厍老师给了我很多耐心的指导和启发。

厍老师渊博的学识严谨的治学态度敬业的精神和平易近人的态度，给我留下了深刻的印象，在厍老师的教导下，我在学习生活方面都得到了很多的进步，他既是良师又是益友，不仅让我学到了专业知识，还让我学到了很多做人的道理，启发自己要不断自我奋发学习努力进步激励着自己以后的言行。

这些都将使我在以后的人生中受益，老师的谆谆教诲将令我终身难忘。

在此，请允许我表示我深深的敬意和衷心的感谢，在这次毕业设计过程当中，厍老师的研究生，我的赵春兰师姐也给了我很大的帮助和启发。

在学习中通过她给我讲解的知识都是很难在课本和课堂中学习到的。

通过讲解我的知识也有很大的进步和提高，对毕业设计的内容和研究方法都有新的获益启发。

在以后自己的学习中我也会像师姐样在研究学习中，秉着对自己对科学的追崇高求，来要求自己完成件完美的研究学习。

所以请让我再次感谢赵春兰师姐对我的细心指导，衷心的感谢你，还要感谢我的同学和室友，他们在毕业设计的过程中给了我很多启发和帮助。

在我的学习和生活中给与了我很大的帮助和支持。

对他们也表示我衷心的感谢，最后，我要感谢所有在我论文完成过程中给予了帮助和关心的朋友。

参考文献董颖，唐加福，许宝栋，汪定伟东北大学学报自然科学版，梁军粒子群算法在最优化问题的研究广西师范大学著杨振凯，周红，易兵，张瑜等译运筹学应用范例与解法北京清华大学出版社，赵瑞安，吴方著非线性最优化理论和方法浙江浙江科学技术出版社，周柯中国学科教育论文网站朱儒，黄皓，朱开水非线性规划北京中国矿业大学出版社，赵瑞安，吴方非线性最优化理论和方法北京浙江科学技术出版社汪定伟，王俊伟，王洪峰，张瑞友等编著智能优化方法北京高等教育出版社，王凌，刘波著微粒子群优化与调度算法北京清华大学出版社，孙志胜，曹爱增，梁永涛基于遗传算法的聚类分析及其应用济南大学学报刘文远，王宝文等基于遗传算法的模糊聚类分析计算机工程安良，胡勇，胡良梅，孟玲玲种改进的模糊均值聚类算法合肥工业大学学报陆林花，王波种