非线性规划的算法研究

《非线性规划的算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、非线性规划的算法研究　　论文关键词：非线性规划　最优决策　初值依赖　matlab　　论文摘要：本课题主要研究非线性规划的算法。非线性规划在军事，经济，管理，生产过程自动化，工程设计和产品优化设计等方面都有着重要的应用。但非线性规划的研究目前还不成熟，有许多问题需要进一步完善。非线性规划不像线性规划有统一的算法，对于不同的问题需要用不同的算法处理，现阶段各种算法都有一定的局限性，只有对各种算法加以改正，才能有效地解决人们在日常的生产、生活中遇到的优化问题，做出最优决策。　　本文主要是对现有的各种算法加以测试，指出各种算法的优缺点

2、，寻找一种不受初值依赖，收敛更快的最优算法。首先介绍了非线性规划研究的背景和国内外研究状况，然后论述了方案的选取过程，重点描实验过程，主要是对各种非线性最优计算方法用matlab软件编程，给出一个在工程中具有代表性的最优函数实例，经过大量的测试，并给出了结果分析。最后给出了整个实验的总结和由此对未来的展望。　　1选题背景　　1.1课题背景　　非线性规划的一个重要理论是1951年Kuhn-Tucker最优条件(简称KT条件)的建立.此后的50年代主要是对梯度法和牛顿法的研究.以Davidon(1959),Fletcher和Pop

3、lexmethod）开始，但单纯形不是多项式算法。随后，Kamaka提出了椭球算法(多项式算法)，内点法。对于非线性问题，起初人们试图用线性优化理论去逼近求解非线性问题，但效果并不理想。后来的非线性理论大多都建立在二次（凸）函数的基础上，也就用二次函数去逼近其他非线性函数。在此基础上提出许多优化经典的优化算法。无约束的优化算法包括：最速下降法（steepest）、共轭梯度法、牛顿法（Ne）、拟牛顿法（pseudoNes）、信赖域法。约束优化算法包括：拉格朗日乘子法（AugmentedLagrangianAlgorithms），

4、序列二次规划（ＳＱＰ）等。　　随着社会的发展，实际问题越来越复杂，例如全局最优化问题。经典算法一般都用得局部信息，如单个初始点及所在点的导数等，这使得经典算法无法避免局部极小问题。全局最优化是NP-Hard问题,所以原有的经典算法不再使用，必须对其进行改进，或将其与启发式算法结合。启发式算法是受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，取得了巨大的成就。　　40年代：由于实际需要，人们已经提出了一些解决实际问题快速有效的启发式算法。　　

5、50年代：启发式算法的研究逐步繁荣起来。随后，人们将启发式算法的思想和人工智能领域中的各种有关问题的求解的收缩方法相结合，提出了许多启发式的搜索算法。其中贪婪算法和局部搜索等到人们的关注。　　60年代:随着人们对数学模型和优化算法的研究越来越重视，发现以前提出的启发式算法速度很快，但是解得质量不能保证。虽然对优化算法的研究取得了很大的进展，但是较大规模的问题仍然无能为力（计算量还是太大）。　　70年代：计算复杂性理论的提出。NP完全理论告诉我们，许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度

6、快，但解不好的原因主要是他们只是在局部的区域内找解，得到的解不能保证全局最优性。由此必须引入新的搜索机制和策略，才能有效地解决这些困难问题。　　80年代以后：模拟退火算法（SimulatedAnnealingAlgorithm），人工神经网络（ArtificialNeuralNet）,蚁群算法（AntAlgorithms），拟人拟物算法，量子算法等油相继兴起，掀起了研究启发式算法的高潮。由于这些算法简单和有效，而且具有某种智能，因而成为科学计算和人类之间的桥梁。　　优胜劣汰是大自然的普遍规律，它主要通过选择和变异来实现。选择是

7、优化的基本思想，变异（多样化）是随机搜索或非确定搜索的基本思想。“优胜劣汰”是算法搜索的核心，根据“优胜劣汰”策略的不同，可以获得不同的超启发式算法。超启发式算法的主要思想来自于人类经过长期对物理、生物、社会的自然现象仔细的观察和实践，以及对这些自然现象的深刻理解，逐步向大自然学习，模仿其中的自然现象的运行机制而得到的。　　遗传算法：是根据生物演化，模拟演化过程中基因染色体的选择、交叉和变异得到的算法。在进化过程中，较好的个体有较大的生存几率。　　模拟退火：是模拟统计物理中固体物质的结晶过程。在退火的过程中，如果搜索到好的解接

8、受；否则，以一定的概率接受不好的解（即实现多样化或变异的思想），达到跳出局部最优解得目的。　　神经网络：模拟大脑神经处理的过程，通过各个神经元的竞争和协作，实现选择和变异的过程。　　禁忌搜索：模拟人的经验，通过禁忌表记忆最近搜索过程中的历史信息，禁忌某些解，以避免走回头路，达