（2）给出了几个标准测试函数。

（3）在不同的测试函数上分别对算法性能进行了测试。

（4）通过对实验结果的分析总结，得出各个算法的特点。

1。5 本章小结

本章主要介绍了局部搜索算法的研究背景和国内外研究现状，以及最优化理论的基 本概念。同时本章还简单的介绍了本论文主要的研究内容，方法及其实际意义。

第二章 局部搜索算法

2。1 背景知识

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

在解决各类优化问题的算法中局部搜索算法是一中有效且渐变通用算法。它的框架 是这样的：先选定一个初始解作为出发点，然后利用函数持续在当前解的领域中选定一 个新解来取代当前解，然后不断的重复以上过程，直到算法满足停止条件为止，最终得 到的解就是算法找到的近最优解。局部搜索算法简便灵活，能够在有限的时间内解决比 较复杂的优化问题，因此有非常广泛的适用面。 

在计算机科学中，局部搜索算法是用来解决优化问题的元启发算法，它具有以下几 个特点： 

1、原理简单，结构灵活通用易于实现。

2、解得质量与初始解的选取和领域的结构密切相关。

2、缺点是具有局部优化特性，易陷入局部最优。 但是对于单模问题，由于不存在局部最优的可能性，所以局部搜索算法是解决这类

为题最有效的方法。 局部搜索算法的五个要素： 1、目标函数

2、领域的定义

3、初始解的选择

4、新解的产生和接受准则

5、终止准则 目标函数是用来判断解的质量的标准，领域的定义和初始解的产生对算法的性能有

着决定性的而影响。新解得产生和接受准则与算法的终止准则是不同局部搜索算法产生 的依据。

根据算法原理的不同，一般将局部搜索算分为三类，将只适用因变量的方法叫做零 阶方法。将使用目标函数一阶偏导数的方法叫做一阶方法，这也是局部搜索算法最常使 用的方法，常见的一阶方法有：爬山法、最速下降法等。将不仅使用一阶偏导而且使用

二阶偏导的放法叫做二阶方法，如牛顿法。除此之外，我们又将零阶方法称为直接搜索 法，简称直接法。将一阶和二阶方法称为间接法或解析法，直接法不涉及导数和 Hessian 矩阵，适应性强，但收敛速度一般较慢；间接法收敛速度一般较快，但是需要计算导数 甚至 Hessian 矩阵，所以计算量较大。

2。1。1 无约束最优化文献综述

一般来说，最优化问题可以归结为求解函数极小值问题：

其中，x ∈ D叫做决策变量，�(�)为目标函数，D ∈ Rn称为可行域。

根据变量类型的不同，可以将最优化问题分为连续型最优化问题和离散型最优化问

题，其中，连续优化问题又可以分为约束函数和目标函数都是线性时的线性优化问题， 和这两者至少有一个为非线性的非线性规划问题[8]。在实际生产管理和一些其他领域中， 有一部分实际的优化问题是线性规划的，但是更多的属于非线性优化问题。因此，非线 性优化有着广泛的研究背景和重要的研究意义，并且已经成为最优化理论中的重要分支。 根据可行域 D 的类型，非线性规划又分为有约束最优化问题和无约束最优化问题。这两 种优化问题是实际应用最广的优化问题。从某种意义上来讲，处理无约束最优化问题的 方法也是解决约束最优化问题的基本方法，不仅因为一些约束最优化问题可以转化为无 约束最优化问题来处理，而且还可以把一些解决无约束最优化问题的方法直接应用到解 决约束最优化问题中去。由此可见，无约束最优化的计算方法与约束最优化的处理方法 有着紧密的联系。因此，对无约束最优化问题的解决和研究有着十分重大的意义。