学科教育论文-非线性规划的算法研究.doc
学科教育论文-非线性规划的算法研究论文关键词:非线性规划最优决策初值依赖matlab论文摘要:本课题主要研究非线性规划的算法。非线性规划在军事,经济,管理,生产过程自动化,工程设计和产品优化设计等方面都有着重要的应用。但非线性规划的研究目前还不成熟,有许多问题需要进一步完善。非线性规划不像线性规划有统一的算法,对于不同的问题需要用不同的算法处理,现阶段各种算法都有一定的局限性,只有对各种算法加以改正,才能有效地解决人们在日常的生产、生活中遇到的优化问题,做出最优决策。本文主要是对现有的各种算法加以测试,指出各种算法的优缺点,寻找一种不受初值依赖,收敛更快的最优算法。首先介绍了非线性规划研究的背景和国内外研究状况,然后论述了方案的选取过程,重点描实验过程,主要是对各种非线性最优计算方法用matlab软件编程,给出一个在工程中具有代表性的最优函数实例,经过大量的测试,并给出了结果分析。最后给出了整个实验的总结和由此对未来的展望。1选题背景1.1课题背景非线性规划的一个重要理论是1951年Kuhn-Tucker最优条件(简称KT条件)的建立.此后的50年代主要是对梯度法和牛顿法的研究.以Davidon(1959),Fletcher和Powell(1963)提出的DFP方法为起点,60年代是研究拟牛顿方法活跃时期,同时对共轭梯度法也有较好的研究.在1970年由Broyden,Fletcher,Goldfarb和Shanno从不同的角度共同提出的BFGS方法是目前为止最有效的拟牛顿方法.由于Broyden,Dennis和More的工作使得拟牛顿方法的理论变得很完善.70年代是非线性规划飞速发展时期,约束变尺度(SQP)方法(Han和Powell为代表)和Lagrange乘子法(代表人物是Powell和Hestenes)是这一时期主要研究成果.计算机的飞速发展使非线性规划的研究如虎添翼.80年代开始研究信赖域法、稀疏拟牛顿法、大规模问题的方法和并行计算,90年代研究解非线性规划问题的内点法和有限储存法.可以毫不夸张的说,这半个世纪是最优化发展的黄金时期.以后随着电子计算机的普遍使用,非线性规划的理论和方法有了很大的发展,其应用的领域也越来越广泛,特别是在军事,经济,管理,生产过程自动化,工程设计和产品优化设计等方面都有着重要的应用。1.2课题研究的目的和意义一般来说,解非线性规划问题要比求解线性规划问题困难得多,而且也不像线性规划那样有统一的数学模型及如单纯形法这一通用解法。非线性规划的各种算法大都有自己特定的适用范围。都有一定的局限性,到目前为止还没有适合于各种非线性规划问题的一般算法。这正是需要人们进一步研究的课题。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用,为最优设计提供了有力的工具。例如:如何在现有人力、物力、财力条件下合理安排产品生产,以取得最高的利润;如何设计某种产品,在满足规格、性能要求的前提下,达到最低的成本;如何确定一个自动控制系统的某些参数,使系统的工作状态最佳;如何分配一个动力系统中各电站的负荷,在保证一定指标要求的前提下,使总耗费最小;如何安排库存储量,既能保证供应,又使储存费用最低;如何组织货源,既能满足顾客需要,又使资金周转最快等。对于静态的最优化问题,当目标函数或约束条件出现未知量的非线性函数,且不便于线性化,或勉强线性化后会招致较大误差时,就可应用非线性规划的方法去处理。1.3国内外概况解决最优化问题的算法分为经典优化算法和启发式优化算法。经典算法的确立可以从(G.B.Dantzig1947)提出解决线形规划的单纯形(Simplexmethod)开始,但单纯形不是多项式算法。随后,Kamaka提出了椭球算法(多项式算法),内点法。对于非线性问题,起初人们试图用线性优化理论去逼近求解非线性问题,但效果并不理想。后来的非线性理论大多都建立在二次(凸)函数的基础上,也就用二次函数去逼近其他非线性函数。在此基础上提出许多优化经典的优化算法。无约束的优化算法包括:最速下降法(steepest)、共轭梯度法、牛顿法(NewtonAlgorithm)、拟牛顿法(pseudoNewtonAlgorithms)、信赖域法。约束优化算法包括:拉格朗日乘子法(AugmentedLagrangianAlgorithms),序列二次规划()等。随着社会的发展,实际问题越来越复杂,例如全局最优化问题。经典算法一般都用得局部信息,如单个初始点及所在点的导数等,这使得经典算法无法避免局部极小问题。全局最优化是NP-Hard问题,所以原有的经典算法不再使用,必须对其进行改进,或将其与启发式算法结合。启发式算法是受大自然的启发,人们从大自然的运行规律中找到了许多解决实际问题的方法。启发式算法的计算量都比较大,所以启发式算法伴随着计算机技术的发展,取得了巨大的成就。40年代:由于实际需要,人们已经提出了一些解决实际问题快速有效的启发式算法。50年代:启发式算法的研究逐步繁荣起来。随后,人们将启发式算法的思想和人工智能领域中的各种有关问题的求解的收缩方法相结合,提出了许多启发式的搜索算法。其中贪婪算法和局部搜索等到人们的关注。60年代:随着人们对数学模型和优化算法的研究越来越重视,发现以前提出的启发式算法速度很快,但是解得质量不能保证。虽然对优化算法的研究取得了很大的进展,但是较大规模的问题仍然无能为力(计算量还是太大)。70年代:计算复杂性理论的提出。NP完全理论告诉我们,许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快,但解不好的原因主要是他们只是在局部的区域内找解,得到的解不能保证全局最优性。由此必须引入新的搜索机制和策略,才能有效地解决这些困难问题。80年代以后:模拟退火算法(SimulatedAnnealingAlgorithm),人工神经网络(ArtificialNeuralNetwork),禁忌搜索(TabuSearch)相继出现。最近,演化算法(EvolutionaryAlgorithm),蚁群算法(AntAlgorithms),拟人拟物算法,量子算法等油相继兴起,掀起了研究启发式算法的高潮。由于这些算法简单和有效,而且具有某种智能,因而成为科学计算和人类之间的桥梁。优胜劣汰是大自然的普遍规律,它主要通过选择和变异来实现。选择是优化的基本思想,变异(多样化)是随机搜索或非确定搜索的基本思想。“优胜劣汰”是算法搜索的核心,根据“优胜劣汰”策略的不同,可以获得不同的超启发式算法。超启发式算法的主要思想来自于人类经过长期对物理、生物、社会的自然现象仔细的观察和实践,以及对这些自然现象的深刻理解,逐步向大自然学习,模仿其中的自然现象的运行机制而得到的。遗传算法:是根据生物演化,模拟演化过程中基因染色体的选择、交叉和变异得到的算法。在进化过程中,较好的个体有较大的生存几率。模拟退火:是模拟统计物理中固体物质的结晶过程。在退火的过程中,如果搜索到好的解接受;否则,以一定的概率接受不好的解(即实现多样化或变异的思想),达到跳出局部最优解得目的。神经网络:模拟大脑神经处理的过程,通过各个神经元的竞争和协作,实现选择和变异的过程。禁忌搜索:模拟人的经验,通过禁忌表记忆最近搜索过程中的历史信息,禁忌某些解,以避免走回头路,达到跳出局部最优解的目的。蚂蚁算法:模拟蚂蚁的行为,拟人拟物,向蚂蚁的协作方式学习。虽然人们研究对启发式算法的研究将近年,但它还有很多不足:1)启发式算法目前缺乏统一、完整的理论体系。2)由于NP理论,各种启发式算法都不可避免的遭遇到局部最优的问题,如何判断已经找到的最优值是全局最优值。3)各种启发式算法都有各自优点,如何完美结合。