1。4  本论文主要研究内容 4

1。5  本章小结 4

第二章 局部搜索算法 5

2。1 背景知识 5

2。1。1 局部搜索算法的含义 5

2。1。1 无约束最优化 6

2。2  最速下降法 7

2。2。1 最速下降法简介 7

2。2。2 最速下降法基本原理 7

2。3  牛顿法 8

2。3。1  牛顿法简介 8

2。3。2 牛顿法基本原理 9

2。4 拟牛顿法 11

2。4。1  拟牛顿法简介 11

2。4。2  拟牛顿法法基本原理 12

2。5 共轭梯度法 16

2。5。1  共轭梯度法简介 16

2。5。2  共轭梯度法基本原理 17

2。6  本章小结 19

第三章 测试函数 21

3。1Sphere 函数 21

3。2Weighted Sphere 函数 21

3。3Quadric 函数 23

3。4Rosenbrock 函数 24

3。5Sum of different powers 函数 25

3。6  本章小结 26

第四章 算法性能研究比较 27

4。1  最优参数选择测试 27

4。1。2 测试结果 27

4。2  函数性能对比研究 30

4。2  优化过程 32

4。3 本章小结 34

结论 35

致 谢 36

参考文献 37

第一章 绪 论

1。1 研究背景

在我们的生活中经常会碰到一些优化问题，对于简单的优化问题，仅仅通过数值计 算的方法就能将其解决，但是对于复杂的优化问题，想要通过人力来解决该类问题几乎 是不可能的。近似算法的提出为这类问题的解决，提供了一个有效的方法。Dorit Hochbaum 在她的文章中对近似算法给出了这样的描述：对于一个复杂的非确定性问题， 没有一个确定性算法能够在多项式时间内给出最优解，但是近似算法却可以在有限的时 间内，对这样的问题给出一个近似最优解[1]。 

近些年来随着工业的飞速发展，各类优化问题变得越发复杂，主要体现在需要优化 变量的数量变得非常多。这些问题主要分为多模问题和单模问题两大类，多模问题存在 局部极值，而单模问题只有一个全局极值而且中间不存在局部极值。对于低维的多模问 题，很多群体智能算法已经有了一些探索的进展，而且部分算法已经能够得到很好的性 能，但是对于高维的多模问题，目前仍然没有找到很好的解决办法。但是对于单模问题 来说，因为不存在局部极值点，所以不存在陷入局部极值这样的一种可能，那么对于单 模问题，目前唯一追求的性能指标就是收敛的速度。在解决单模问题的背景下，群体智 能算法又被称为零阶算法，这类在解决优化问题的时候具有很强的随机性，而且不能很 好的利用问题本身的梯度信息，仅仅只利用了函数本身并向各个方向试探，所以搜索的 速度很慢。但是对于局部搜索算法来说，同样在解决单模问题的时候，它利用了问题的 一阶甚至二阶信息，所以其在搜索的时候更具有方向性，因此，在收敛速度上局部搜索 算法远远优于群体智能算法。局部搜索算法在解决大规模的单模问题的时候显得非常有 效。但在实际的工程设计中，遇到的问题往往是多维的，对于一个多模问题，我们可以 用化整为零的思想，将其分解为若干的单模问题来解决，将局部搜索算法作为一个算子 嵌入群体智能算法之中，这样就可以很好的提升群体智能算法的工作效率，使问题的解 决更加有效。