开题报告文献综述 北理工
不会写开题报告、文献综述,论文的过来看!下面是小编整理的开题报告文献综述 北理工范文。
【一】北京理工大学硕士学位论文开题文献综述报告
学位论文题目为《基于聚类分析的启发式优化算法》 ，论文内容涉及了优化算法(主要是经典优化算法，启发式优化算法) ，算复杂性理论和聚类分析等相关领域。
根据这些领域与论文的相关程度，比较详细的归纳总结启发式优化算法，对计算复杂性理论和聚类分析只做了一般性的总结。
最后对这些相关领域未来的发展和研究提出自己的观点。
在现实生活中许多重要的问题，都涉及到选区一个最好的目标，或者为达到这个目标而选择某些参数、确定某些值，这些问题都可以归结为最优化问题。
对于一个最小值问题，其形式的描述为 min ( )f XXS∈(1) 这里的 S 为解的可行域，也称为解空间或搜索空间，条件 XS∈概括了对向量 X 的约束。
这些约束可以包括线性或非线性函数， 以及离散变量， 都可以根据实际要求设置。
最优化问题的目标是找到(1)的最优解(全局最优解或局部最优解) 。
显然，只要改变目标函数的符号，最大值问题就可以转变成最小值问题，因此，本文在说明都是以最小值问题问标准。
解决最优化问题的算法称为最优化算法，可以分为经典优化算法和启发式优化算法。
而经典优化算法又分为线形与非线性最优化算法，下面分别对两类算法的发展及常用的软件包做了介绍。
1. 线性最优化[1][10]： 线性最优化, 又称线性规划, 是运筹学中应用最广泛的一个分支.这是因为自然科学和社会科学中许多问题都可以近似地化成线性规划问题. 线性规划理论和算法的研究及发展共经历了三个高潮, 每个高潮都引起了社会的极大关注.
线性规划研究的第一高潮是著名的单纯形法的研究.
这一方法是 Dantzig 在 1947 年提出的,它以-15- -15- 成熟的算法理论和完善的算法及软件统治线性规划达三十多年. 随着 60 年代发展起来的计算复杂性理论的研究, 单纯形法在七十年代末受到了挑战.
前苏联数学家 Khachiyan 提出了第一个理论上优于单纯形法的所谓多项式时间算法--椭球法, 曾成为轰动一时的新闻, 并掀起了研究线性规划的第二个高潮.
但遗憾的是广泛的数值试验表明, 椭球算法的计算比单纯形方法差. 1984 年 Karmarkar 提出了求解线性规划的另一个多项式时间算法.
这个算法从理论和数值上都优于椭球法, 因而引起学术界的极大关注, 并由此掀起了研究线性规划的第三个高潮. 从那以后, 许多学者致力于改进和完善这一算法,得到了许多改进算法.这些算法运用不同的思想方法均获得通过可行区域内部的迭代点列, 因此统称为解线性规划问题的内点算法.
目前内点算法正以不可抗拒的趋势将超越和替代单纯形法. 在互联网上能访问到的解线性和整数规划问题的软件还有:EQPS(线性，整数和非线性规划),FMP(线性和混合整数规划) ，HS/LPLO(线性规划) ，KORBX(线性规划) ，LAMPS(线性和整数规划) ，LPBLP(线性规划) ，
MILP(混合整数规划) ，MINTO(混合整数规划) ， MPSIII(线性和混合整数规划) ，OML(线性和混合整数规划) ， OSL(线性，二次和混合整数规划) ，PROCLP(线性和整数规划) ，WB(线性和混合整数规划) ，WHIZARD(线性和混合整数规划) ，XPRESSMP(线性和混合整数规划)等[41]。
2.非线性最优化[1][2][3][10]： 非线性规划的一个重要理论是 1951 年 Kuhn-Tucker 最优条件(简称 KT 条件)的建立[2].此后的 50 年代主要是对梯度法和牛顿法的研究.以 Davidon(1959), Fletcher 和 Powell(1963)提出的 DFP 方法为起点, 60 年代是研究拟牛顿方法活跃时期, 同时对共轭梯度法也有较好的研究.
在 1970 年由 Broyden,Fletcher,Goldfarb 和 Shanno 从不同的角度共同提出的 BFGS 方法是目前为止最有效的拟牛顿方法.
由于Broyden, Dennis 和 More 的工作使得拟牛顿方法的理论变得很完善. 70 年代是非线性规划飞速发展时期, 约束变尺度(SQP)方法(Han和Powell为代表)和Lagrange乘子法(代表人物是 Powell 和 Hestenes)是这一时期主要研究成果.计算机的飞速发展使 -15- 非线性规划的研究如虎添翼.
80 年代开始研究信赖域法、稀疏 拟牛顿法、大规模问题的方法和并行计算, 90 年代研究解非线性规划问题的内点法和有限储存法.
可以毫不夸张的说, 这半个世纪是最优化发展的黄金时期. 与线性规划相比，非线性规划软件还不够完善. 但是已有大量解非线性规划问题的软件, 其中有相当一部分可从互联网上免费下载.LANCELOT 是由 Conn,Gould 和Toint 研制的解大规模最优化问题的软件包,适合解无约束最优化、非线性最小二乘、边界约束最优化和一般约束最优化问题.
这个软件的基本思想是利用增广Lagrange函数来处理约束条件, 在每步迭代中解一个边界约束优化子问题, 其所用的方法结合信赖域和投影梯度等技术.MINPACK 是美国 Argonne 国家实验室研制的软件包， 适合求解非线性方程组和非线性最小二乘问题, 所用的基本方法是阻尼最小二乘法,
此软件可以从网上图书馆获得. PROC NLP 是 SAS 软件公司研制的 SAS 商业软件中 OR 模块的一个程序，这个程序适合解无约束最优化、非线性最小二乘、线性约束最优化、二次规划和一般约束最优化问题.TENMIN 是 Schnabel 等研制的解中小规模问题的张量方法软件。
在互联网上能访问到的解非线性最优化问题的软件还有:CONOPT(非线性规划) ，DOT(优化设计工具箱) ，Excel and Quattro Pro Solvers(线性，整数和非线性规划) ，FSQP(非线性规划和极小极大问题) ，GRG2(非线性规划)， LBFGS(有限储存法) ，
LINDO(线性、二次和混合整数规划) ，LSSOL(最小二乘和二次规划) ，MINOS(线性和非线性规划) ，NLPJOB(非线性多目标规划) ， OPTPACK(约束和无约束最优化),PETS(解非线性方程组和无约束问题的并行算法) ，
QPOPT(线性和二次规划) ,SQOPT (大规模线性和凸二次规划) ， SNOPT (大规模线性、 二次和非线性规划) ，SPRNLP (稀疏最小二乘,稀疏和稠密非线性规划) ， SYSFIT (非线性方程组的参数估计) ，TENSOLVE (非线性方程组和最小二乘) ， VE10(非线性最小二乘)等[38][39][40][41].
大自然是神奇的，它造就了很多巧妙的手段和运行机制。
受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。
对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法 -15- (Heuristic Algorithm) 。
现在的启发式算法也不是全部来自然的规律，也有来自人类积累的工作经验。
启发式算法有不同的定义：一种定义为，一个基于直观或经验的构造的算法，对优化问题的实例能给出可接受的计算成本(计算时间、占用空间等)内，给出一个近似最优解，该近似解于真实最优解的偏离程度不一定可以事先预计;
另一种是，启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度[11]。
我比较赞同第二种定义，因为启发式算法现在还没有完备的理论体系，只能视作一种技术。
启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，取得了巨大的成就[11][23]。
40 年代：由于实际需要，人们已经提出了一些解决实际问题快速有效的启发式算法。
50 年代：启发式算法的研究逐步繁荣起来。
随后，人们将启发式算法的思想和人工智能领域中的各种有关问题的求解的收缩方法相结合，提出了许多启发式的搜索算法。
其中贪婪算法和局部搜索等到人们的关注。
60 年代: 随着人们对数学模型和优化算法的研究越来越重视，发现以前提出的启发式算法速度很快，但是解得质量不能保证。
虽然对优化算法的研究取得了很大的进展，但是较大规模的问题仍然无能为力(计算量还是太大) 。
70 年代：计算复杂性理论的提出。
NP 完全理论告诉我们，许多实际问题不可能在合理的时间范围内找到全局最优解。
发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，得到的解不能保证全局最优性。
由此必须引入新的搜索机制和策略， 才能有效地解决这些困难问题，这就导致了超启发式算法(meta-heuristic algorithms)的产生。
Holland 模拟地球上生物进化规律提出了遗传算法(Genetic Algorithm) ，它的与众不同的搜索机制引起了人们再次引发了人们研究启发式算法的兴趣，从而掀起了研究启发式算法的热潮。
-15- 80 年代以后： 模拟退火算法 (Simulated Annealing Algorithm) ， 人工神经网络 (Artificial Neural Network) ，禁忌搜索(Tabu Search)相继出现。
最近，演化算法(Evolutionary Algorithm), 蚁群算法(Ant Algorithms) ， 拟人拟物算法，量子算法等油相继兴起，掀起了研究启发式算法的高潮。
由于这些算法简单和有效，而且具有某种智能，因而成为科学计算和人类之间的桥梁。
优胜劣汰是大自然的普遍规律，它主要通过选择和变异来实现。
选择是优化的基本思想，变异(多样化)是随机搜索或非确定搜索的基本思想。
“优胜劣汰”是算法搜索的核心，根据“优胜劣汰”策略的不同，可以获得不同的超启发式算法。
超启发式算法的主要思想来自于人类经过长期对物理、生物、社会的自然现象仔细的观察和实践，以及对这些自然现象的深刻理解，逐步向大自然学习，模仿其中的自然现象的运行机制而得到的。
遗传算法：是根据生物演化，模拟演化过程中基因染色体的选择、交叉和变异得到的算法。
在进化过程中，较好的个体有较大的生存几率[5]。
模拟退火：是模拟统计物理中固体物质的结晶过程。
在退火的过程中，如果搜索到好的解接受;否则，以一定的概率接受不好的解(即实现多样化或变异的思想) ，达到跳出局部最优解得目的[10]。
神经网络：模拟大脑神经处理的过程，通过各个神经元的竞争和协作，实现选择和变异的过程[22]。
禁忌搜索： 模拟人的经验， 通过禁忌表记忆最近搜索过程中的历史信息， 禁忌某些解，以避免走回头路，达到跳出局部最优解的目的[32]。
蚂蚁算法：模拟蚂蚁的行为，拟人拟物，向蚂蚁的协作方式学习。
这几种超启发式算法都有一个共同的特点：从随机的可行初始解出发，才用迭代改进的策略，去逼近问题的最优解[23]。
他们的基本要素： (1)随机初始可行解; (2)给定一个评价函数(常常与目标函数值有关) ; -15- (3)邻域，产生新的可行解; (4)选择和接受解得准则; (5)终止准则。
其中(4)集中反映了超启发式算法的克服局部最优的能力。
虽然人们研究对启发式算法的研究将近50年，但它还有很多不足[5][23]： 1.启发式算法目前缺乏统一、完整的理论体系。
2.由于 NP 理论，各种启发式算法都不可避免的遭遇到局部最优的问题，如何判断 3.各种启发式算法都有个自优点如何，完美结合。
4.启发式算法中的参数对算法的效果起着至关重要的作用，如何有效设置参数。
5.启发算法缺乏有效的迭代停止条件。
6.启发式算法收敛速度的研究等。
由于各种算法对同一个问题都有可能给出最优解，为了判定各种算法的效率，人们给出了算法复杂性的度量。
计算复杂性理论是研究算法有效性和问题难度的一种工具。
它是最优化问题的基础，涉及如何判断一个问题的难易程度。
只有了解了所研究问题的复杂性，才能更有针对性地设计有关算法，提高算法效率。
所谓 P 问题，就是可以被关于问题本身的参数，如维数，约束个数等的多项式时间内求解的问题。
几个多项式和指数的时间复杂性函数的对比[9] 规模 n 时间复杂性 函 数 10 20 30 40 50 60 N 20.00001s 0.00002s 0.00003s 0.00004s 0.00005s 0.00006s N0.0001s 0.0004s 0.0009s 0.0016s 0.0025s 0.0036s N30.001s 0.008s 0.027s 0.064s 0.125s 0.216s N50.1s 3.2s 24.3s 1.7m 5.2m 13.0m 2n0.001s 1.0s 17.9m 12.7d 35.7y 366c 3n0.059s 58m 6.5y 3855c 2x108c 1.3x1013c 图(1) (S:秒 M:分 D:天 Y:年 C:世纪) NP 问题就是对于一个给定的点， 能多项式时间内判定它是否给定问题的解的问题 -15- [9][14]。