摘要局部搜索算法是一类重要的优化算法，被广泛应用于计算机科学、数学、运筹学、 工程学、生物信息学中各种很难找到全局最优解的计算问题。简单来说，局部搜索算法 是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为 当前解，直到达到一个局部最优解。鉴于单纯的局部搜索算法无法解决多极值函数优化 问题，局部搜索算法常常与其他全局优化算法相结合以提高整体效率。近二十年来,局 部搜索算法在各个领域的应用非常广泛,特别是针对一些比较复杂的优化问题。局部搜 索算法的主要优点在于它是一种比较通用的优化算法,可以比较方便地应用于具体的优 化问题，而且局部搜索算法的运行时间和优化程度可以由用户通过参数来控制。论文主 要完成以下几方面工作：84390

1）介绍了局部搜索算法的相关内容。

2）简单介绍了函数最优化的理论和方法，以及其在某些领域中的应用。

3）着重介绍了本论文研究的最速下降法、牛顿法、拟牛顿法（SR1、BFGS）和共轭梯 度法这五个局部搜索算法的基本原理，以及几个测试函数。

4）将测试函数在各个算法上进行测试通过横向比较这五个局部搜索算法，分析常见局 部搜索算法的性能特点，并加以总结,找出这几种局部搜索算法的适用领域。

毕业论文关键词：局部搜索算法、最优化、比较研究、最速下降法、牛顿法、SR1、BFGS、共轭梯度法

ABSTRACT Local search algorithm is a kind of important optimization algorithm, which is widely used in computer science, mathematics, operations research, engineering, bioinformatics to search the global optimal。 In simple terms, the local search algorithm is a simple greedy search algorithm, the algorithm selects an optimal solution from the solution space of the current solution to the current solution, until it reaches a local optimal solution。 In view of the simple local search algorithm can not solve the multi extremum function optimization problem, local search algorithm is often combined with other global optimization algorithms to improve the overall efficiency。 In recent twenty years, the local search algorithm is widely used in many fields, especially for some complex optimization problems。 Local search algorithm for the main advantage lies in it is a general optimization algorithm, can be conveniently applied to a specific optimization problem, and local search the running time of the algorithm and the optimization degree by the user through the parameters to control。 The paper mainly completes the following several aspects work:

(1)Introducing the related content of local search algorithm。

(2)A brief introduction to the theory and method of function optimization, and its application in some fields。

(3)The basic principles of the five local search algorithms, which are the steepest descent method, Newton method, quasi Newton method (SR1, BFGS) and conjugate gradient method, are introduced in this paper。

(4)Useing the test function in each algorithm and compare the five local search algorithm, analyzing the performance characteristics of common local search algorithm, and summarized, to find out the field of application of these local search algorithms。

Keywords：Local Search Algorithm、optimize 、compare research 、Steepest descent method、 Newton method、 SR1、BFGS、 conjugate gradient method

目 录

第一章 绪 论 1

1。1  研究背景 1

1。2  局部搜索算法研究现状 1

1。3  最优化理论 3