非线性最优化计算方法与算法

毕业论文

题 目 非线性最优化计算方法与算法 学 院 数学科学学院 专 业 信息与计算科学 班 级 计算1201 学 生 陶红 学 号 *********** 指导教师 邢顺来

二〇一六年五月二十五日

济南大学毕业论文

摘 要

非线性规划问题是一般形式的非线性最优化问题。本文针对非线性规划的最优化问题进行方法和算法分析。传统的求解非线性规划的方法有最速下降法、牛顿法、可行方向法、函数逼近法、信赖域法，近来研究发现了更多的求解非线性规划问题的方法如遗传算法、粒子群算法。本文对非线性规划分别从约束规划和无约束规划两个方面进行理论分析。

利用最速下降法和牛顿法两种典型算法求解无约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。另外给出了阻尼牛顿法，探讨其算法的收敛性和稳定性，求解无约束非线性规划比牛顿法的精确度更高，收敛速度更快。惩罚函数是经典的求解约束非线性的方法，本文采用以惩罚函数法为核心的遗传算法求解有约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。并改进遗传算法，给出适应度函数，通过变换适应度函数，提高算法的收敛性和稳定性。

关键词：非线性规划；最速下降法；牛顿法；遗传算法

- I -

济南大学毕业论文

ABSTRACT

Nonlinear programming problem is the general form of the nonlinear optimization problem. In this paper, we carry on the analysis of the method and algorithm aiming at the optimization problem of nonlinear programming. The traditional methods of solving nonlinear programming problems include steepest descent method, Newton method, the feasible direction method, function approximation method and trust region method. Recent studies found more method of solving nonlinear programming problems, such as genetic algorithm, particle swarm optimization (pso) algorithm. In this paper, the nonlinear programming is analyzed from two aspects: the constraint programming and the unconstrained programming.

We solve unconstrained condition nonlinear programming problem by steepest descent method and Newton's method, and get the optimal value through MATLAB. Then the convergence and stability are discussed. Besides, the damped Newton method is furnished. By discussing the convergence and stability of the algorithm, the damped Newton method has higher accuracy and faster convergent speed than Newton's method in solving unconstrained nonlinear programming problems.Punishment function is a classical method for solving constrained nonlinear. This paper solves nonlinear programming problem with constraints by using genetic algorithm method, the core of which is SUMT. Get the optimal value through MATLAB, then the convergence and stability are discussed. Improve genetic algorithm, give the fitness function, and improve the convergence and stability of the algorithm through transforming the fitness function.

Key words：Nonlinear Programming; Pteepest Descent Method; Newton Method; GeneticAlgorithm

- - II

济南大学毕业论文

目 录

摘要 ........................................................................................................................................ I ABSTRACT .......................................................................................................................... II 1 前言 ................................................................................................................................... 1

1.1 引言 ......................................................................................................................... 1 1.2 非线性规划的发展背景 ......................................................................................... 2 1.3 国内外研究现状 ..................................................................................................... 2 1.4 研究主要内容及研究方案 ..................................................................................... 3

1.4.1 研究的主要内容 ........................................................................................... 3 1.4.2 研究方案 ....................................................................................................... 3 1.5 研究难点 ................................................................................................................. 4 2 预备知识 ........................................................................................................................... 5

2.1 向量和矩阵范数 ..................................................................................................... 5

2.1.1 常见的向量范数 ........................................................................................... 5 2.1.2 谱范数 ........................................................................................................... 6 2.2符号和定义 .............................................................................................................. 6 2.3 数值误差 ................................................................................................................. 7 2.4 算法的稳定性 ......................................................................................................... 7 2.5 收敛性 ..................................................................................................................... 9 3 非线性规划模型 ............................................................................................................. 10

3.1 非线性规划模型 ................................................................................................... 10 3.2 无约束非线性规划 ............................................................................................... 11

3.2.1 最速下降法 ................................................................................................. 13 3.2.2 牛顿法 ......................................................................................................... 15 3.2.2 阻尼牛顿法 ................................................................................................. 16 3.3 约束非线性规划 ................................................................................................... 17

3.3.1 惩罚函数法 ................................................................................................. 18 3.3.2 遗传算法 ..................................................................................................... 18 3.3.3 自适应遗传算法 ......................................................................................... 20

结论 ..................................................................................................................................... 23 参考文献 ............................................................................................................................. 24 致谢 ..................................................................................................................................... 25 附录 ..................................................................................................................................... 26

- - III

济南大学毕业论文

1 前言

1.1 引言

我们知道最优化是一门很古老的求极值问题，最优化在求解线性规划，非线性规划，随机规划，多目标规划，非光滑规划，整数规划，几何规划等方面研究得到迅速发展。而且最优化方法在经济计划，交通运输,工程计划，生产管理等方面广泛应用，成为一门比较受欢迎的学科。

最优化方法与算法是在本世纪40年代末形成的一门学科。早在17世纪的时候，牛顿和莱布尼兹研究出微积分的时代，就已经提出了函数的极大极小值得问题[3,4]然后出现了拉格朗日乘子法和柯西的最速下降法，到20世纪30年代的时候，最优化理论才开始迅速的发展，成为一门的学科，1930年苏联数学家提出了小规模的线性规划问题，1939年hitchcocck在生产管理和交通运输方面研究出了什么是线性规划，并且在1947年Dantzing提出了求解线性规划的方法：单纯形法。后来紧接着又提出了线性规划的对偶性理论，K—T条件，奠定了非线性规划的基础，随着时代的发展，非线性最优化问题已经被人们提上了日程，非线性最优化是在20世纪50年代形成了一门数学类的学科。是在线性规划的基础上发展起来的，并且研究出了求解无约束规划的DFP变尺度方法，最速下降法和牛顿法，拟牛顿法，无约束方法研究至今在应用的方法为Powell法，Powell法是一种改进的共轭方向法，也是迄今为止求解无约束非线性规划最有效的方法。而求解约束非线性规划问题最主要的方法主要有可行方向法，惩罚函数法，投影梯度法等方法。最优化计算与方法是一门应用很广泛且很受人欢迎的一门学科，他研究数学意义基础上的问题的最优解，既是对给出的实际问题从很多种方案中选出最优解。最优化理论涉及的内容较为广泛，包括数学分析，数值计算，数值分析，最优化方法，高等代数等学科。且实用性很强，在现实生活中把实际问题转化为最优化问题，在数学建模、数值分析方面上有显著的应用。而我们知道最优化的一般理论是转化为求数学式子的极小值，它的一般形式为：

minf(x),

s.t xX

其中xR是决策变量，f(x)是目标函数，XR为可行域。而最优化的求解过

nn程一般是迭代过程，就是给出初始值X（0）Rn按照某种迭代规律进行计算。最后计算出一个点或者一个极限值就是所求的最优解[4,17]。我们所采用的计算工具就是使用MATLAB来完成的，我们知道MATLAB比高级语言执行能力低，但编程效率可读性高于高级语言，对于那些对编程不感兴趣的同学来说，这是一个很好的作弊软件。用

- 1 -

济南大学毕业论文

MATLAB我们可以很容易就得到我们想要的答案，不必再去写那些繁杂又难懂的程序啦。但是我们在计算过程中，会出现数值误差，数值误差对计算结果会产生很大的影响，我们在利用算法求解最优值的时候往往得到的是近似值，他意味在每一次的迭代过程中将会产生数值误差，从而最终的计算结果是不可估量的。算法的稳定性分析对求解非线性的最优值有重要的影响[7，18]。

1.2 非线性规划的发展背景

非线性规划是运筹学的分支之一，直到最近以来发展迅速，应用范围越来越广，并且不断产生新的方法和算法，由传统的最速下降法，牛顿法，可行方向法，函数逼近法，信赖域法，到遗传算法，神经网络，蚁群算法，粒子群算法等发生了量的改变，原本求解非线性规划问题是人们的一大难题，随着时代的发展，求解非线性规划问题也被提上日程，在各个领域都有涉及，如经济，管理，最优设计，质量控制，系统控制等方面得到广泛应用[17]。

非线性规划是在线性规划的基础上发展起来的，在1951年库恩和塔克发表了关于最优性条件的论文标志着非线性规划理论的诞生。为非线性最优化的发展奠定了理论基础。在20世纪50年代得出二次规划，目标规划，多目标规划和可分离规划的多种解法。且他们都是以单纯型法为基础的，随着计算机的发展，非线性最优化得到迅速的发展。出现了很多的求解非线性规划最优化的方法和算法[3,4,7,11]。一般来说非线性规划的建模和求解比较难，大量的研究学者把精力和时间放在这个上面。非线性规划的最优条件，充分和必要条件在1948年被John论证了。后来在1967年被Fromovitz和Mangasarain推广，论证了包含等式和不等式条件的非线性规划。非线性最优化在优化领域是一难点也是重点，而求解非线性最优化的算法也成为人们研究的重点。在非线性最优化中，有些方法的算法收敛速度较慢，计算次数多且较为繁杂，难以满足人们的要求，因而我们需要将无约束优化和约束优化的优点结合起来。得到新的算法，满足问题的要求[3,4,13,16,17] 。 求解非线性的方法有最速下降法，牛顿法，可行方向法，函数逼近法，信赖域法。近来研究发现了更多的求解非线性最优化问题的方法如遗传算法，蚁群算法，粒子群算法，神经网络。很多非线性最优化问题要比线性问题求解要难得多，多种因素结合起来往往比单个因素要难，非线性最优化的求解方法没有统一固定的，因而相比较线性规划而言，求解非线性最优化是比较难的。

1.3 国内外研究现状

自1956年以来已经有人从事非线性规划理论的最优化方法和算法，然而这几年从事非线性规划的优化问题的研究人员越来越多。由于非线性规划有重要的发展前景，使得国内外领先技术工程师在此方面做出了大量的研究国内领先的科研人员主要包括袁亚湘，马昌凤，陈家民，李董辉，贺国平，桂胜华等著名的优化专家，袁亚湘的《最优化理论与方法》以及马昌凤的《最优化方法及其MATLAB程序设计》等书

- 2 -

济南大学毕业论文

刊，成为我们大学课堂上的课本。而国外的一些优化专家有一些典型代表如F.Facchinei，G.Liuzzi，S.Lucidi，P.Spellcci，R.Fletcher，S.Leyffer等在优化领域做出很高的成就。线性最优化经历了从单变量规划到多变量规划，产生了量的改变。从小规模到大规模变化，从无约束的非线性最优化到有约束的非线性最优化。非线性规划在实际生活中解决了很多的问题[7,16,17]，很多的实际问题在构建成数学模型的时候就可以转化为这一问题。而我们在实际生活中所接触的优化问题一般都是含有约束条件的，这也就体现了非线性规划的无约束和有约束条件的最优化问题在被人们逐渐解决，并得到应用。算法也被逐渐的改进，由传统的求解非线性的方法有单纯性法、内点法、拉格朗日法、共轭梯度法、最速下降法、牛顿法、可行方向法、函数逼近法、信赖域法，近来研究发现了更多的求解非线性最优化的智能方法如遗传算法、粒子群算法、神经网络、蚁群算法。最新的研究表示滤子法是一种新的研究非线性规划的方法。但我们知道滤子法还不够成熟，滤子法不具有惩罚函数所拥有的优点，因而更引起了广大学者的注意力。并越来越受人欢迎[11,13,17]。

1.4 研究主要内容及研究方案

1.4.1 研究的主要内容

本文针对非线性规划的最优化问题进行方法和算法分析，非线性规划的最优化方法由从传统的求解非线性的方法有最速下降法，牛顿法，可行方向法，函数逼近法，信赖域法。近来研究发现了更多的求解非线性规划问题的方法如遗传算法，粒子群算法，神经网络，蚁群算法等最优化方法。研究非线性规划问题的方法至今为止多如牛毛，而我们主要是同过给出两个特定的方法和算法求解非线性最优化问题，分别是求解无约束非线性规划的最速下降法和牛顿法，还有就是求解约束非线性规划问题的遗传算法和改进的遗传算法。

研究非线性规划分别从约束规划和无约束线性规划两个方面进行理论分析，无约束条件非线性最优化方法以最速下降法和牛顿法为例求解非线性规划最优化问题。最速下降法和牛顿法是典型的非线性规划问题的方法，在其收敛速度和准确度上值得我们探求。求解有约束条件非线性最优化方法遗传算法和改进的遗传算法和改进的遗传算法，求解约束非线性规划的最优值，收敛性和稳定性。并用MATLAB程序实现，求解出数值解，非线性规划的求解一般是通过迭代法来实现的，从满足条件的初始条件x0一步一步的搜索下去，直到求解出最优解。分析最优化的方法和算法，算法的稳定性和精确性是数值计算的重要研究内容。 1.4.2 研究方案

从数学领域来讲，最优化方法就是一种求极值的方法，利用约束条件和非约束条件求目标函数的极小值问题。非线性最优化就是说约束条件或者目标函数有一个是非

- 3 -

济南大学毕业论文

线性的，求解非线性最优化问题有两种方法，一是解析法，另一个是数值法，本文利用数值法来研究非线性最优化问题。给出特定的方法求解其最优值。并且我们知道算法是方法的精髓和灵魂。我们研究非线性最优化问题就必须的研究算法。利用MATLAB计算非线性最优化问题。本文给出了研究无约束非线性最优化的三种算法和约束非线性最优化的三种算法。我们采用最速下降法，牛顿法，阻尼牛顿法以及惩罚函数法，遗传算法、自适应遗传算法为例探讨非线性最优化问题。

最速下降法和牛顿法是求解无约束非线性规划的算法典例。本文通过对最速下降法，牛顿法，阻尼牛顿法的探究，来了解无约束非线性最优化的方法。本文采用惩罚函数法，遗传算法，自适应遗传算法来求解约束非线性最优化问题，求解约束非线性规划的常用的算法有惩罚函数法，可行分析法，层次分析法而遗传算法是以惩罚函数为核心，其精确度比传统求解约束非线性规划问题的惩罚函数可行方向法更高。而本文给出了改进的遗传算法。利用遗传算法和改进的遗传算法对比，研究约束非线性最优化的方法和算法。

1.5 研究难点

（1）非线性最优化问题一直是受关注的热点话题，在实际生活中应用也很广泛，前人研究较多。

（2）非线性最优化所存在的理论较多，在不同的领域当中有不同的分析方法。 （3）非线性最优化的方法和算法很多，题目太大，研究较为麻烦。 （4）非线性最优化在求解其最优值计算较为复杂需要用专门的工具来完成。

- 4 -

济南大学毕业论文

2 预备知识

2.1 向量和矩阵范数

设Rn表示n维空间向量，Rn*n 表示n阶矩阵所组成的线性空间。在Rn和Rn*n这两个空间中，分别定义向量和矩阵范数

向量xR的范数 ||x|| 是大于等于零的数，它满足以下几个条件 (1) ||x||0,||x||0x0; (2) ||X||||||X||,R; (3) ||xy||||x||||y||.

向量x(x1,x2...xn)的p范数定义为：

n||x||p（|xi|）i1np1p 。

2.1.1 常见的向量范数 1-范数：||x||1|x|;

i1n 2-范数：||x||2(|x|);

i1n122|xi|. -范数：||x||1maxin矩阵ARn*n的范数是一个小于零的实数，它除了满足跟向量范数相同的三条性质外，还满足其他两条

(4) ||AB||||A||||B||,A,BRn*n,

如果一个矩阵范数相对于某向量范数满足下面的不等式，

(5) ||Ax||||A|||x|,xR,

则称矩阵范数||•||和向量范数||•||是相容的，然而若是x0，

||x||maxx0||Ax||max||Ax||,ARn*n ||x||1||x|| - 5 -

济南大学毕业论文

则称矩阵||•||是由向量范数诱导出来的算子范数，也称从属范数||•||的矩阵范数，此时向量范数和算子范数通常采用相同的符号||•||。 因而向量范数||x||1,||x||2,||x||的从属范数为

||A||1max|aij，|1ini1n||A||2max{|（ATA）}, ||A||max|aij|。1jnj1n2.1.2 谱范数

特别在迭代算法中我们知道经常用到谱范数，来讨论其收敛性，则谱范数定义为

[4]

||A||F(aij)tr(ATA) 。

nn122i1j12.2符号和定义

g(x)：f(x)一阶导函数；g(x)f(x)， gk：f(xk)的一阶导函数；gk=f(xk)

，

2f(x)G(x)G(x)：二阶导函数；=f(x)，

Gk：f(xk)的二阶导函数；Gk=2(xk)，

n R：n维空间向量，

Rn*n：n维矩阵空间。

定义 设f:RnR,xRn,如果f在点x处的对于自变量x(x1,x2,,xn)T个

2f(x)二阶偏导数(i,j1,2,3,,n)都存在，则称函数f(x)在点x处是二阶可导

xixj - 6 -

济南大学毕业论文

2f(x)2f(x)2f(x),......2xxxxx121n12f(x)2f(x)2f(x),......[3]22的，并称二阶导数矩阵f(x)x2x1x2x2xn为Hesse矩阵。

....222f(x)f(x)f(x),......2xnxnx1xnx22.3 数值误差

在数值计算过程中往往会出现各种各样的误差，在数值计算过程中总是会产生误差，这有可能是人为造成的，也有可能是算法本身的造成的。而如何减小误差则就成了关键的问题，误差主要是截断误差和舍入误差。截断误差就是算法从连续系统到离散系统的过程的实现。误差是经过几万次的计算形成的，积累形成的误差就很大，因而就有可能导致错误的结果，而初始值的选取就显得尤为重要。舍入误差就是在计算机执行过程中由于位数的就需要四舍五入，因而就产生了舍入误差，计算机所执行的所执行的位数是有限的，舍入误差就是不可避免的。我们知道初始值得选取对数值计算的成败有着重要的影响，在进行计算过程中应该尽可能的减少误差[18,19]。

本文主要是研究算法的舍入误差，舍入误差分析包括定性分析和定量分析，定量分析主要包括概率分析向前误差分析，和向后误差分析，区间误差分析等但是定量误差分析存在着局限性，因而人们不常使用，人们经常使用的是定性误差分析。在误差的定性分析中，核心都是初始数据的误差已经在计算过程中产生的误差对最优值产生额影响，数值的稳定性是对算法的初始值对计算结果不会产生大的变化，而产生大的变化的则说明算法不稳定[18]。

2.4 算法的稳定性

在实际计算过程中，各种数据都会带来误差，即使在计算过程中初值误差很小而经过算法的迭代过程，误差逐渐积累，对最后的结果也会产生一定的影响。而算法的稳定性，是指算法在执行过程中，对误差是否可控[22]。 通过一个例子分析： 例如 ：

Inxnex2dx,n,1,2,3......20.

02先进行分部积分得

Inxenx110|nxn1ex1dx1nIn1

01得到递推公式：In1nIn1,n0,1,2,,20

- 7 -

济南大学毕业论文

1给定初始值I01利用 递推公式可以得到结果如下表所示：

e表2.1

n n 数值结果 数值结果

0 1 2 3 4 5 6 7 8 9 10

0.632121 0.367879 0.2241 0.207271 0.1703 0.145533 0.126802 0.112384 0.100932 0.091612 0.083877 11 12 13 14 15 16 17 18 19 20 0.077352 0,071773 0.066948 0.062731 0.059034 0.0559 0.057192 -0.02945 1.55962 -30.1924

我们知道n=18和n=20的时候为负值这是不可能的，出现了很大的误差我们将现有的递推公式改一下可以有：

In11In,n0,1，2，，20n

xnxnex1xne11In(n1)εn1我们可以推算出 I200.5*(n 20

19 18 17 16 15 14 13 12 11 10

11)/210.032569递推得到数值结果如下表 e表2.2

n 数值结果 数值结果

0.932569

0.048372 0.050086 0.052773 0.055719 0.059018 0.062732 0.066948 0.071773 0.077352 0.083877

- 8 -9

8 7 6 5 4 3 2 1 0 0.091612 0.100932 0.112384 0.126802 0.145533 0.1703 0.207277 0.2241 0.367879 0.632121

济南大学毕业论文

分析表4.1和表4.2得 由于表4.1的初始值精度很高，但是到了n=8的时候出现了误差。表4.2给出了n=20时的估计值，虽然精度不如表4.1但是准确度很高，这两种算法是完全等价的，但是最后的数值结果上却存在一定的差距。表4.1的初始误差很小，但是在递推过程中产生的误差逐渐累积，误差值逐渐变大，最后的数值结果也就出错了，表4.2在刚开始的时候是由于估算得到的结果，存在一定的误差，但是随着递推的次数的增加，精确度提高了。在数值计算中，舍入误差是累积增加的，这样的说是不稳定，表4.1的就是递推公式就是稳定的，表4.2的递推公式就是稳定的[18,19]。

2.5 收敛性

定义：设点列{xk}收敛到点x满足方程式||xk1x||c||xkx||,0c1, 则称点列{xk}线性收敛到点x则满足

||xk1x||lim0, k||xkx||则称点列{xk}超线性收敛到点x则满足

||xk1x||limc,c0 k||xkx||则称点列{xk}的收敛速度是二次的。

若一个算法有二次的有限终止性，这个算法所产生的点列xk是超线性收敛或者是二次的收敛速度，这是衡量一个算法的优劣的一个方面[3,4]。

- 9 -

济南大学毕业论文

3 非线性规划模型

非线性规划是指从多种优化方案中选出最优的那一个，随着时代的发展，最优化方法和算法得到人们的重视。并且得到了一些的理论成果。 最优化的数学模型：

minf(x)

s.txX (3.1) 其中满足：

X{xRn|gi(x)0,iE;hj(x)0,jI},E{1,2,,l},I{l1,l2,,ln},

g(x)，并且有f(x)，h(x)是连续的函数[5]。

g(x),h(x)至少存在一个是非线性的。非线性规划是指f(x)，包含无约束规划和约

束规划问题。而约束规划又包含等式约束和不等式约束，在此我们仅讨论无约束规划问题和约束规划问题，这两个方面。并通过简单的方法和算法讨论其极值，收敛性，稳定性[3,4]。

3.1 非线性规划模型

本文主要考虑的是非线性规划，数学模型为：

minf(x)

s.t hi(x)0, i1,,l (3.2)

gj(x)0， j1,,m

其中f(x)，hi(x)(i1,,l)以及gj(x)(j1,,m)都是定义在Rn上的连续可微的多元实值函数。并且至少有一个是非线性的。

记：

E{i|hi(x)0},I{i|gj(x)0}.

我们在此把非线性规划问题化为有约束条件的非线性规划，和无约束条件的非线性规划。

这里我们先定义两个极值，即局部极小值和全局极小值。

- - 10

济南大学毕业论文

局部极小值定义：若对于xN(x,){xRn|||xx||δ},有

f(x)f(x)

则称x为局部极小值点，其中为非负的常数，要想满足f(x)f(x)成立，即要求xx，则称x为严格局部极小值点。

n全局极小值定义：若对于xR有：

f(x)f(x)

则称x为全局极小值点，要想满足f(x)f(x)成立，即要求xx，则称x为严格全局极小值点。

由定义可以知道，全局极小值点一定是局部极小值点，（在实际生活中我们只求局部极小值点）[4]。

3.2 无约束非线性规划

无约束非线性规划的数学模型：

minf(x),

f:RnR (3.3) 其中f(x)是定义在Rn上的连续函数，且是非线性的。 无约束优化问题：

minf(x)

的最优化条件，有一阶和二阶条件，我们主要研究是二阶无约束最优。 无约束的极小的最优化条件 定理3.2.1(必要条件)

如果f(x)是可微函数，点x是非线性规划最优化问题(3.3)局部极小值点或局部极大值点的必要条件是 f(x)0 。 (3.4)

我们称作满足方程 (3.4) 的点为无约束非线性规划的一个稳定点。举例说明稳定点存在不同的位置

- - 11

济南大学毕业论文

图3.1

在图片中“”表示极大值点，“•”表示极小值点。还有一类点不是极大值也不是极小值，被称作为鞍点。 定理3.2.2（充分条件）

设f(x)为二阶可微函数，且点x满足方程式f(x)0并且有

yH(x)y0,yRn,y0,则称作点为严格局部极小值点，这里的H(x)是f(x)的

Hesse矩阵。

定理3.2.3（二阶必要条件）

设f(x)为二阶可微函数，且点x是f(x)的局部极小值点，则：

f(x)0，

yH(x)y0,yRn,

定理3.2.4（二阶充分条件）

设为f(x)是Rn中的二阶可微函数且是连续的，若有点x满足f(x)0并且x的一个邻域x(x)有yH(x)y0,yRn,x(x)则称点x是目标函数f(x)的局部极小值点[4]。

无约束非线性最优化问题一般的算法都是迭代法，一系列的点x0,x1,x2,x3通

- - 12

济南大学毕业论文

常作为最优值点或者平稳点。算法关于目标函数f(x)可以产生一系列的点列

x0,x1,x2,x3柯收敛到最优点或平稳点[4]。在数值计算中我们一般采用迭代法求解

无约束非线性优化问题，本文介绍了两种求解无约束非线性优化问题的数值计算方法，最速下降法和牛顿法（阻尼牛顿法）这两种方法是最典型的求解无约束非线性规划问题的方法。迭代求极值是求解无约束优化问题的基本思想，即是给定一个初值，按照迭代准则，求出f(x)的极小值点（若为无穷的点列是，其极限值就是其极小值）

[3,4]

。

3.2.1 最速下降法

最速下降法是较早的求解最优化问题的计算方法，使用的是负梯度法。最速下降法也叫梯度法，负梯度方向dg(xk)，设f(x)为xk的连续函数。最速下降法的理论是根据一阶泰勒展开，f(xαd)f(x)g(x)TdO(α||d||) 即：f(xd)f(x)g(x)TdO(||d||).

由于f(xd)f(x)0,则αg(x)TdO(α||d||)0

而实际中我们要求：αg(x)Td0的，可以选择合适的d使得αg(x)Td0最速下降法的d取的是dg(x)可近似看作f(xd)f(x)g(x)d，

取dg(x)可得到：f(xαd)f(x)g(x)Tg(x) 由于g(x)Tg(x)0则g(x)Tg(x)0。

最速下降法的线性收敛和全局收敛，算法较为简单，最开始的时候计算则快速而准确，但往往会出现跑偏现象，远离正确答案，不能得到正确解，如图所示：

（2） x

•

x(k) （1） x

（•） •x

图3.2

- - 13

济南大学毕业论文

1. 算法： 设定误差0；

给定初始值x，令k0； 计算gk=f(xk)；

（k）若||gk||，则x•x(k)停止计算，否则p=gk，则由得：

（0）f(x(k)kp(k))minf(x(k)kp(k))

令x(k1)x(k)kp(k)，kk1,转步骤2[3,4] 2. MATLAB实现程序：（见附录1） 3. 求解无约束问题：

2min f(x)100(x1x2)2（x11） xR2

2有精确解(x1,x2)=(1,1) f(x)0求解目标函数 ①目标函数 function f=fun(x)

f=100*(x(1)^2-x(2))^2+(x(1)-1)^2; ②M梯度文件 function gf=gfun(x)

gf=[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1), -200*(x(1)^2-x(2))]';

终止准则取：||g(xk)||105,取不同的初始值，可以得到如下结果：

表3.1

迭代次数：k 1159 611

T初始值x0 （0，0） （2, 1） （1，-1） （-1，-1） （-1.2, 1） （10，-10）

4. 调用方式：

TTTTT目标函数值f(x) 1.163*10 1.1416*10 1.2251*10 9.2536*10 1.1985*10 1.0156*10

-10-10-10-10-10-101551 1499 1435 1025

- - 14

济南大学毕业论文

x0(1.2.1);[x,val,k]grad('fun','gfun',x0)

其中fun和gfun是求解目标函数和梯度。

最速下降法求无约束非线性最优化问题，收敛是较为缓慢，且计算误差值也比较大，一般不选择采用这种方式，我们求解无约束非线性最优化问题，一般采用的是牛顿法。牛顿法在求解过程无论是从收敛性以及其稳定性来看要好于最速下降法。阻尼牛顿法是改进的牛顿法。 3.2.2 牛顿法

牛顿算法是最传统的求解无约束最优化的算法，也是收敛速度比较快的一种算法。牛顿算法发展经历了牛顿算法、阻尼牛顿法以及拟牛顿法。阻尼牛顿法和拟牛顿法在收敛速度和计算次数上明显比之牛顿法要好，收敛更快一些，计算次数更少。本文研究非线性优化问题采用的是牛顿法和阻尼牛顿法。

牛顿法是利用迭代点xk的一阶导数和二阶导数对目标函数f(x)进行二次函数逼近，然后把二次函数的极小值点作为新的迭代点，一直持续这一做法，直到达到所要求的精度要求，迭代完成。 牛顿法的迭代公式：

设f(x)，Hesse矩阵G(x)连续，取f(x)的泰勒展开的前三项：

[4]

1h（x）（fx）g（xx）(xxk)TG（xxk）， kkkk2其中f(xk)是点xk的函数值，gk是一阶导数，Gk是二阶导数，求h(xk)的稳定点。

Gk非奇异，那上面线性方程的牛顿公式为：

xk1xk-Gkgk

牛顿法算法[3,4]：

(1)给定终止误差01，初始点，x0Rn.令k0;(2)计算gkf(x).若||gk||ε,停止运算，输出xxk;2(3)计算Gf(x),求解线性方程得解dk：k

-1

Gkd-gk;

(4)令xk1xkd,kk1,转2。

牛顿法最突出的优点 就是收敛速度快，且具有二阶收敛的特性。而我们对于求

- - 15

济南大学毕业论文

解无约束优化问题，最常采用的算法是阻尼牛顿法，它的算法和牛顿法相似，但收敛速度和计算的准确性方面要更好一些，下面是阻尼牛顿法的算法。 3.2.2 阻尼牛顿法 阻尼牛顿法算法：

(1)给定误差值01，(0,1)，(0.0.5)，初始点x0Rn，令k0； (2)计算dkf(xk)。若||gk||ε，停止运算，输出xxk,； (3)计算Gk2f(xk)并求解非线性方程组的解dk;；

Gkdgk

(4)记mk满足下列不等式的最小非负整数m；

f(xkmdk)f(xk)mTgkdk

3. 阻尼牛顿法MATLAB程序（见附录2） 4. 求解无约束最优化问题

xR(5)令kmk，xk1xkαkdk,kk1,转步骤2.[4,5]

222minf(x)100*(xx)(x1); 121n我们可知其中一个精确解x(1,1)T,f(x)0

目标函数

function f=fun(x)

f=100*(x(1)^2-x(2))^2+(x(1)-1)^2;

②M梯度文件

function gf=gfun(x)

gf=[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1), -200*(x(1)^2-x(2))]'; ③Hesse矩阵文件 function He=Hess(x) n=length(x); He=zeros(n,n);

He=[1200*x(1)^2-400*x(2)+2, -400*x(1); -400*x(1), 200 ];

根据阻尼牛顿法，终止准则取||f(xk)||105，取几个不同的初始点， 得到数值结果如下表

- - 16

济南大学毕业论文

初始点x0 （0,0） （0.5,0.5） （2,2） （-1,-1） （1,10） （10,10） （20,20）

5. 调用方式：

x0[-1.2，1]；

表3.2 迭代次数k

13 11 14 20 1 47 73

目标函数值f(xk) 9.6238*1015 3.5183*1019 1.6322*1014 3.6221*1017 4.9039*1028 3.3426*1017 3.0386*1017

[x,val,k]dampnm('fun','gfun','Hesse',x0)

其中fun,gfun,Hesse分别为目标函数、梯度、Hesse矩阵

阻尼牛顿法求解无约束问题收敛速度是比较可观的，阻尼牛顿法是牛顿法的优化，求解无约束非线性规划的精确度也更准确，收敛速度比最速下降法和牛顿法要好。精确度较最速下降法和牛顿法更准确。

3.3 约束非线性规划

约束非线性规划的数学模型

min f(x),

s.t h(x)0， i1，2，，l

i gj(x)0， j1,2,,m

有l个等式约束条件；有m个不等式约束条件；

2，，l)以及gi(x)(j1,2,,m)都是定义在Rn上的连其中f(x)，hi(x) (i1，续可微函数。并且至少存在一个是非线性的。

对于求解约束非线性最优化问题，可行方向法，惩罚函数法计算繁琐且误差较大，精度不高，本文采用遗传算法来求解约束非线性最优化问题，更好的提高了它的收敛速度，精度以及稳定性。其遗传算法的核心是惩罚函数法。惩罚函数是指根据约束条件特点构造特定的罚函数加到目标函数中去，从而得到增广目标函数，将约束优化问题转化为求极小值优化问题。遗传算法是新的改进之后的惩罚函数法，在收敛速度和计算的精确度上远大于惩罚函数法，因而遗传算法又叫做新的惩罚函数法[8,13，16]。

- - 17

济南大学毕业论文

3.3.1 惩罚函数法

惩罚函数法的基本思想是根据约束条件的特点，将其转化为某种惩罚函数加到目标函数中去，从而将约束优化问题转化为一系列的无约束问题来求解。

惩罚函数算法：

(1)给定初始点x0Rn,终止误差01，11,1,令k:1.

(2)以xk1为初始点求解子问题

minP(x,k)f(x)kP(x) nxR (3)若kP(xk),停算，输出xxk作为近似极小点。(4)令k1:k,k:k1,转2。

惩罚函数作为经典的求解约束非线性最优化问题的方法，在求解其最优值时的收敛速度以及其收敛的准确度还存在不足的地方，而遗传算法作为改进的惩罚函数法，精确度更高，收敛也更快。 3.3.2 遗传算法

遗传算法是一种生物自然遗传和生物自然选择机制的优化方法，具有易操作性和全局优化性的特点，适应于很多的领域，在数学领域中求解约束非线性规划最优化问题是人们常用的方法[8,14]。 定义：

根据生物演化，模拟演化过程中基因染色体的选择、交叉和变异得到的算法。因而在整个进化过程中，自然选择，优胜劣汰，较好的个体则较容易存活下来。 遗传算法一种适者生存和选择机制中抽象出来的一种算法，又叫做基因算法。

1. 遗传算法和以往的最优化算法有不同的地方 遗传算法不是解集本身，而是一种解集的编码， 遗传算法不是一个解，而是始于解得一个群，

遗传算法不是使用的目标函数和约束函数的导数，而是使用目标函数本身，

遗传算法不是确定的状态转移规则，而是使用概率。 2. 遗传算法有三种遗传操作

(1)选择算子(2)交叉算子 (3)变异算子然而对于遗传算法的收敛性研究人员对进化算法的运行机理进行研究表明，一般遗传算法不一定是收敛的，只有每一次迭代保存了其最优种子时，才是收敛的，研究

- - 18

济南大学毕业论文

人员利用通过对遗传算法构造马尔柯夫链来证明的，并且证明是正确的。因而我们可以知道遗传算法的发展进化过程是一个马尔柯夫过程。当遗传算法收敛时，解通常只是最优解的一个近似解，我们知道数学分析中收敛时一个无限逼近的得到近似值，而遗传算法所得到的解就是一个近似值，因而会产生一定的误差，为了减少误差的范围，遗传算法采用的是二进制编码[14,15]。

遗传算法是无论在收敛性还是稳定性方面都比较好的一种求解最优值的算法，存在多种不同的算法，然而几种算法又有共同的特点： (1) 随机初始可行解； (2) 给定一个评价函数； (3) 产生新的可行解； (4) 迭代；

(5) 选择和接受可行解的准则； (6) 终止准则； 遗传算法的运算：

遗传算法应用于很多领域但是遗传算法还需要完善其不足的地方，用遗传算法研究最优化问题，通过调用遗传算法的程序求解非线性规划最优化问题，本文给出遗传算法的MATLAB程序，利用遗传算法来研究非线性最优化方法和算法。并提出一些改进机理，提高了算法的收敛性和稳定性。

- - 19

编码和产生初始群体 计算各个体的适应度 算法收敛准则满足输出搜索结果 执行选择操作 执行交叉操作 执行变异操作 济南大学毕业论文

3. 遗传算法MATLAB程序（见附录3） 3.3.3 自适应遗传算法

本文对现有的遗传算法进行改进，提出了一些改进机理，提高了算法的运行效率，收敛性。

遗传算法的改进主要有下面几点：

1. 遗传算法的搜索的主要方法是终止的适应度值，更深层次的研究了适应度函数的特点，和遗传算法目标函数的变化规律，提出基于线性变换的适应度函数，通过实验及一般的线性变换进行比较，利用适应度函数提高遗传算法的收敛性，精确度。

对遗传算子进行改进，分析了算法的优缺点，提出最优保存策略，随机遍历抽样以及混合选择策略。并且提出了适应度线性逼近的策略，可以提高子代的适应度，研究析了变异概率对遗传算法的影响。并通过程序分析，提出了改进的遗传算法优于现再遗传算法，并提高了其收敛性，精确度等[20,22]。

2. 自适应遗传算法：自适应遗传算法是根据适应度调整变异概率和交叉概率，当种群中的个体趋于局部最优时增加变异概率和交叉概率，当适应度分散是较少变异概率和交叉概率，自适应的交叉概率和变异概率提供个体最佳的交叉概率和变异概率，这样既保持物种的多样性，有保持了全局收敛[22]。

3. 自适应遗传算法MATLAB程序（见附录4）

4. 适应度函数的分析：通过改进的遗传水分，利用群体的适应度来进行分析，因而适应度函数的选取尤为重要，它影响到遗传算法的收敛速度以及精确度。一般的适度函数是根据目标函数来确定的。由于适应度为大于零的数，适应度函数经过变换得到，变换方法有幂函数变换法，线性变换法以及指数函数变换法等[22]。本文主要运用线性变换法。

5. 线性变换法

假设由原来的适应度函数为F(x)经过变换的到的适应度函数F(x)aF(x)b，

a,b要满足条件，变换之后的适应度的最大值应该等于变换之前的平均值的特定的c

倍，从而控制下一代的复制数Fmaxc*Favg，变换之后的适应度应该等于变换之前的平均值。即：

（c1）Favg（FmaxcFavg）Favga，bFmaxFavgFmaxFavg

Favg：平均适应度，Fmax：最大适应度，c：控制参数的最佳期望复制数。一般是1-2.，当群体规模是50-100时是1.2-2。如图3.3所示：

- - 20

济南大学毕业论文

图3.3

线性变换法变换了适应度的差距，保持了多样性，且计算简单容易实现。自适应遗传算法是基于线性变换的适应度函数得到的，提高了算法的准确度和收敛性。 求解约束非线性规划问题：

minFx12*x2*x32x3，

x1x2x34，s.t x1-x22x32，

22232x1,x2,x30.用遗传算法和自适应遗传算法求解非线性最优化问题。

表3.3

变量：x X1 X2 X3 F

满足约束条件的自适应遗传算法的MATLAB图像。如图3.4所示

myGA算法 0.57 3.69 0.0000 0.18035

AdapGA算法 0.0000 4.0000 0.0000 0.0000

精确解 0.0000 4.0000 0.0000 0.0000

图3.4 myGA算法

- - 21

济南大学毕业论文

自适应遗传算法求解非线性规划最优化问题，可以得到更精确的解。

maxf(x)2x12x26x2,

222x1x20;s.t x15x25;

x1,x20.求解约束非线性最优值，运用惩罚函数法，可行性方向法，遗传算法，自适应遗传算法来求解。

表3.4

变量：x

X1 X2 F

满足约束条件的MATLAB的图像。如图3.5所示

惩罚函数法 0.5 0.869 6,566

可行方向法 0.630 0.874 6.4

myGA算法

0.858 0.868 6.6129

AdapGA 算法

0.65 0,8682 6.6130

图3.5 AdapGA 算法

自适应遗传算法求解约束非线性最优值问题比遗传算法要好，已经非常的接近精确值，由于遗传算法的解是随机生成的，因而运行的结果是不一样，但误差都限定在一定的范围内，因而遗传算法对解决约束非线性最优化问题是可行的，并且得到的解优于惩罚函数得到的解。但是myGA算法的变异，选择，交叉操作都是完成的，虽然可以搜索到最优解，但是不一定可以收敛到最优解，对于一些的单峰函数和严格单调的函数，myGA是可以满足收敛到最优解的，myGA收敛缓慢，且收敛不一定能得到最优解，稳定性较差，本文针对这一问题提出了自适应遗传算法，提高了收敛速度和准确度。

- - 22

济南大学毕业论文

结 论

传统的求解非线性最优化的方法有最速下降法，牛顿法，可行方向法，函数逼近法，信赖域法等等，近来研究发现了更多的求解非线性最优化问题的方法如遗传算法，蚁群算法，神经网络，粒子群算法。本文主要将非线性最优化问题分成了两部分来解决，一是带有约束条件非线性最优化问题，另一种是无约束条件非线性最优化问题。

解决无约束非线性最优化问题主要以最速下降法和牛顿法，阻尼牛顿法为例求解非线性最优值，最速下降法和牛顿法是传统意义上的求解无约束非线性最优值。最速下降法收敛速度较慢并且需要大量的计算才能得到其近似值。牛顿法在收敛性方面要优于最速下降法，而阻尼牛顿法在收敛和精确性方面较最速下降法和牛顿法收敛更快也更准确。本文通过这三种方法来求解无约束非线性最优化问题。并且给出了各种方法的一种算法。使人们对无约束非线性最优化问题有初步的了解。

求解无约束的非线性最优化方法相比较于求解约束非线性规划问题是比较简单的。解决约束非线性问题一直是求解最优化问题的难题，对于求解这个问题的传统方法已经有很多，但是计算结果往往不令人满意，误差太大，或者偏离主题如可行方向法，惩罚函数法等方法这些方法繁杂难以理解，结果误差太大不精确。而我们知道遗传算法的核心是惩罚函数法，惩罚函数是求解约束非线性最优化的所熟知的经典方法，但存在收敛性差精确度不高等问题，遗传算法作为改进的惩罚函数法，在根本上从很大程度上提高了算法的收敛性和稳定性。本文以惩罚函数法，遗传算法，自适应遗传算法为例，分析了约束非线性最优化的方法和算法。使人们对约束非线性规划的最优化问题有初步的了解。而遗传算法作为一种高效的求解非线性最优化的方法，已经被广大领域应用。强大的数学理论和计算工具，使得最优化问题得到更好的研究。

- - 23

济南大学毕业论文

参 考 文 献

[1] F.Facchinei, A. Fischer, C.Kanzow. On the accurate identification of active constraints[J]．SIAM

Journal on Optimization, 1999, 9(1):14-32

[2] G. Di Pillo, L. Grippo. On the exactness of a class of nondifferentiable penalty function[J]. Optim

Theory and App. 1988, 57(3): 339-410

[3] 马昌凤. 最优化方法及其matlab程序设计[M], 科学出版社 [4] 袁亚湘，孙文瑜. 最优化理论与方法[M]，北京，科学出版社, 1997 [5] 黄雍检，陶冶, 钱祖平. 最优化方法——matlab应用[M]，人民邮电出版社 [6] 刘兴高，胡云卿. 应用最优化方法及MATLAB实现[M]，科学出版社 [7] 陈加民. 非线性约束规划问题的算法研究[D]. 太原科技大学, 2008. [8] 王兴华. 惩罚函数法的改进算法及应用研究[D]. 燕山大学, 2009.

[9] 王银河. 非线性优化问题的罚函数算法和拟Newton算法[D]. 重庆大学, 2010.

[10] 陈征，沈丹红. 基于Matlab软件的《最优化方法》教学[J]. 宁波工程学院学报, 2011, 23(3): 101-103.

[11] 周晓冬. 非线性约束规划的若干算法研究[D]. 西安建筑科技大学, 2009. [12] 刘芳. 具有不等式约束非线性规划问题的改进算法[D]. 燕山大学, 2008. [13] 杨懿. 线性约束非线性规划问题的一新算法[D]. 重庆大学, 2005.

[14] 倪金林. 遗传算法求解约束非线性规划及Matlab实现[J]. 大学数学, 2005,01:91-95. [15] 金芬. 遗传算法在函数优化中的应用研究[D]. 苏州大学, 2008. [16] 刘牧华. 约束非线性规划的两种算法[D]. 河南科技大学, 2012.

[17] 韩继业. 非线性规划方法简介[J]. 曲阜师院学报(自然科学版), 1982,01:3-13.

[18] 朱小明，张慧斌. PSO算法的稳定性分析及算法改进[J]. 计算机科学, 2013, 03:275-278. [19] 景杨,陈艳. 基于MATLAB探讨舍入误差对数值计算的影响[J]. 信息通信, 2015, 05:39-41. [20] 袁晓辉. 基于遗传算法的非线性规划问题求解[D]. 武汉理工大学, 2002. [21] 杨林美. 一种改进的遗传算法在非线性规划中的应用[D]. 成都理工大学, 2003. [22] 高娟. 遗传算法及其在非线性规划中的应用研究[D]. 西安建筑科技大学, 2010.

- - 24

济南大学毕业论文

致 谢

首先，对于本人的论文指导老师邢顺来老师的用心指导和建议表示诚挚的感谢，我作为一名经验匮乏的本科生，由于知识结构的局限导致出现许多问题和考虑不全的方面，很难想象我可以完成这篇论文如果没有邢顺来老师的帮助，督促和指导。在论文的整个撰写过程中，不论是从论文选题到参考资料的提供，从中期检查到论文初稿的修改意见和敲定，邢顺来老师都给我提供了非常细致和实际的帮助，可行的意见和耐心的指导。邢顺来老师对待学术非常严谨，对待同学也十分平易近人，在我心中烙下了深深的印迹，对我今后的学习和工作也将会有深深的影响。在此谨向邢顺来老师表达最诚挚的感谢。

其次，我要感谢济南大学数学科学学院的各位老师，我对专业的数学知识的系统了解都得益于老师们平时认真负责的教导，因此，我才具备了良好的学习素质和知识结构，最终能够完成了论文撰写工作。

再次，我要感谢学校为我们提供了非常完善的学习设施，图书馆和电子阅览室的丰富资源都为我提供了非常充分的参考资料。

最后，我要感谢我的同学和我的室友，在论文写作过程中给了我许多中肯的建议，最终让我能够高效率地完成论文．感谢所有帮助过和关心过我的同学和朋友，为我完成论文提供了信心和动力。

- - 25

济南大学毕业论文

附 录

1、最速下降法MATLAB程序

% 功能: 用最速下降法求解无约束问题: minf(x)

function [x,val,k]=grad(fun,gfun,x0) maxk=1000; %最大迭代次数 rho=0.5;sigma=0.4; k=0; epsilon=1e-5; while(kg=feval(gfun,x0); %梯度 d=-g; %搜索方向

if(norm(d)if(feval(fun,x0+rho^m*d)x0=x0+rho^mk*d; k=k+1; end

x=x0;

val=feval(fun,x0);

2、阻尼牛顿法MATLAB程序

用阻尼牛顿法求解无约束问题: min f(x)

function [x,val,k]=dampnm(fun,gfun, Hess,x0)

maxk=100; %最大迭代次数

rho=0.55;sigma=0.4; k=0; epsilon=1e-5; while(kgk=feval(gfun,x0); %梯度

Gk=feval(Hess,x0); %Hesse矩阵

dk=-Gk\\gk; %解方程组Gk*dk=-gk, 、搜索方向 if(norm(gk)- - 26

济南大学毕业论文

m=0; mk=0;

while(m<20) % 用Armijo搜索求步长

if(feval(fun,x0+rho^m*dk)m=m+1; end

x0=x0+rho^mk*dk; k=k+1; end x=x0;

val=feval(fun,x);

3、myGA遗传算法

function [xv,fv]=myGA(fitness,a,b,NP,NG,Pc,Pm,eps) L = ceil(log2((b-a)/eps+1)); x = zeros(NP,L);

for i=1:NP

x(i,:) = Initial(L); %种群初始化

fx(i) = fitness(Dec(a,b,x(i,:),L)); %种子适应值 end

for k=1:NG

sumfx = sum(fx); %所有种子适应值之和

Px = fx/sumfx; %所有种子适应值的平均值

PPx = 0;

PPx(1) = Px(1);

for i=2:NP %用于轮盘赌策略的概率累加

PPx(i) = PPx(i-1) + Px(i); end

- - 27

济南大学毕业论文

for i=1:NP

sita = rand();

for n=1:NP

if sita <= PPx(n)

SelFather = n; %根据轮盘赌策略确定的父亲

break; end end

Selmother = floor(rand()*(NP-1))+1; %随机选择母亲

posCut = floor(rand()*(L-2)) + 1; %随机确定交叉点

r1 = rand();

if r1<=Pc %交叉

nx(i,1:posCut) = x(SelFather,1:posCut);

nx(i,(posCut+1):L) = x(Selmother,(posCut+1):L);

r2 = rand();

if r2 <= Pm %变异

posMut = round(rand()*(L-1) + 1);

nx(i,posMut) = ~nx(i,posMut); end else

nx(i,:) = x(SelFather,:); end

- - 28

济南大学毕业论文

end

x = nx;

for i=1:NP

fx(i) = fitness(Dec(a,b,x(i,:),L)); %子代适应值 end end

fv = -inf;

for i=1:NP

fitx = fitness(Dec(a,b,x(i,:),L));

if fitx > fv

fv = fitx; xv = Dec(a,b,x(i,:),L); end end

function result = Initial(length) %初始化函数

for i=1:length

r = rand();

result(i) = round(r); end

function y = Dec(a,b,x,L) %二进制编码转换为十进制编码

base = 2.^((L-1):-1:0);

y = dot(base,x);

y = a + y*(b-a)/(2^L-1);

- - 29

济南大学毕业论文

4、AdapGA 自适应遗传算法

function [xv,fv]=AdapGA(fitness,a,b,NP,NG,Pc1,Pc2,Pm1,Pm2,eps) L = ceil(log2((b-a)/eps+1));

x = zeros(NP,L);

for i=1:NP

x(i,:) = Initial(L);

fx(i) = fitness(Dec(a,b,x(i,:),L)); end

for k=1:NG

sumfx = sum(fx);

Px = fx/sumfx;

PPx = 0;

PPx(1) = Px(1);

for i=2:NP

PPx(i) = PPx(i-1) + Px(i); end

for i=1:NP

sita = rand();

for n=1:NP

if sita <= PPx(n)

SelFather = n;

break; end

- - 30

济南大学毕业论文

end

Selmother = round(rand()*(NP-1))+1;

posCut = round(rand()*(L-2)) + 1;

favg = sumfx/NP;

fmax = max(fx);

Fitness_f = fx(SelFather);

Fitness_m = fx(Selmother);

Fm = max(Fitness_f,Fitness_m);

if Fm>=favg

Pc = Pc1*(fmax - Fm)/(fmax - favg); else

Pc = Pc2; end

r1 = rand();

if r1<=Pc

nx(i,1:posCut) = x(SelFather,1:posCut);

nx(i,(posCut+1):L) = x(Selmother,(posCut+1):L);

fmu = fitness(Dec(a,b,nx(i,:),L));

if fmu>=favg

Pm = Pm1*(fmax - fmu)/(fmax - favg);

else

Pm = Pm2;

- - 31

济南大学毕业论文

end

r2 = rand();

if r2 <= Pm

posMut = round(rand()*(L-1) + 1);

nx(i,posMut) = ~nx(i,posMut); end else

nx(i,:) = x(SelFather,:); end end

x = nx;

for i=1:NP

fx(i) = fitness(Dec(a,b,x(i,:),L)); end end

fv = -inf;

for i=1:NP

fitx = fitness(Dec(a,b,x(i,:),L));

if fitx > fv

fv = fitx;

xv = Dec(a,b,x(i,:),L); end

- - 32

济南大学毕业论文

end

function result = Initial(length)

for i=1:length

r = rand();

result(i) = round(r); end

function y = Dec(a,b,x,L)

base = 2.^((L-1):-1:0);

y = dot(base,x);

y = a + y*(b-a)/(2^L-1);

- - 33