摘 要非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用。传统的解决非线性规划问题的方法，如梯度法、罚函数法、拉格朗日乘子法等，稳定性差，对函数初值和函数性态要求较高，且容易陷入局部最优解。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法是一种全局搜索算法，简单、通用、鲁棒性强，对目标函数既不要求连续，也不要求可导，适用于并行分布处理，应用范围广。本文在分析传统的非线性规划算法的不足和遗传算法的优越性的基础上，将遗传算法应用于非线性规划。算法引进惩罚函数的概念，构造带有惩罚项的适应度函数；通过实数编码，转轮法选择，双点交叉，均匀变异，形成了求解非线性规划问题的遗传算法。与传统的非线性规划算法外点罚函数法的比较结果表明该算法在一定程度上有效地克服了传统的非线性规划算法稳定性差，对函数初值和函数性态要求较高，且容易陷入局部最优解的缺陷，收敛更合理，性能更稳定。关键词：非线性规划；遗传算法；罚函数法ABSTRACTNon-linear programming has a wide range of applications in engineering, management, economic, scientific, and military aspects. Traditional methods to solve the non-linear programming problem, such as the gradient method, penalty method, Lagrange multiplier method, have poor stability. They are sensitive to the function initial value and request the objective function to be continuous and differential. The results are also easily trapped into local optimal solution.Genetic algorithm is a kind of calculate model which simulates Darwins genetic selection and biological evolution of natural selection. Genetic algorithm is a global search algorithm. It has simple, universal, robust features, and does not request the objective function to be continuous and differential, and is suitable in parallel distribution processing. Genetic algorithm is widely applied in many areas.Based on the analysis of the disadvantage of traditional non-linear programming algorithm and the advantage of genetic algorithm, genetic algorithm is applied to non-linear programming in this paper. The introduction of the concept of penalty function is used to construct the fitness function with punishment. By using real-coded, Roulette Wheel selection method, two-point crossover, uniform mutation, we formed a genetic algorithm to solve the non-linear programming problem. Compared with the most classical and widely used traditional non-linear programming problem algorithm SUMT algorithm, the results show that the new algorithm could effectively overcome the defect of the traditional algorithm in a certain extent. The new algorithm is more stable, less sensitive to the function initial value and conditions, and always could receive the optimal solution or approximate optimal solution. Its convergence results are more reasonable, the performance is more stable.Key Words: Non-linear Programming; Genetic Algorithm; SUMT Algorithm 目 录1 概论11.1 背景介绍11.1.1 非线性规划简介11.1.2 遗传算法简介11.2 研究内容22 非线性规划32.1 非线性规划的概念32.2 非线性规划的数学模型32.3 非线性规划的求解方法42.3.1 一维最优化方法42.3.2 无约束最优化方法42.3.3 约束最优化方法52.4 非线性规划的应用53 传统非线性规划算法外点罚函数法63.1 算法概述63.2 算法描述63.3 算法性能分析73.4 外点罚函数法的程序设计83.4.1程序步骤83.4.2程序流程图84 遗传算法104.1 遗传算法概述104.1.1 遗传算法的生物学基础104.1.2 遗传算法的一般结构104.1.3 遗传算法的特点124.1.4 遗传算法的应用124.2 遗传算法实现的关键技术135 求解非线性规划问题的遗传算法设计165.1 实用遗传算法设计165.2 求解非线性规划问题的遗传算法程序设计215.2.1 算法过程描述215.2.2 遗传算法程序流程图225.2.3 遗传算法中所设计的辅助算法的设计226 算法的结果分析246.1 概述246.2 结果比较247 总结28致谢29参考文献30II1 概 论1.1 背景介绍1.1.1 非线性规划简介具有非线性约束条件或目标函数的数学规划，称为非线性规划。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的关于最优性条件(后来称为库恩塔克条件)的论文是非线性规划正式诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优化设计提供了有力的工具。随着计算机的产生与发展，非线性规划作为一门独立的学科越来越受到人们的重视。在非线性规划理论研究的基础上，人们日益重视非线性规划问题求解方法的研究。传统的解决非线性规划问题的方法有多种，如搜索法、梯度法、变尺度法、罚函数法、拉格朗日乘子法、可行方向法等，虽然解法很多，非线性规划目前还没有能适用于各种问题的算法，各个方法都有自己特定的适用范围。1.1.2 遗传算法简介遗传算法（Genetic Algorithm），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法是一种特别有效的算法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程，从而得到最优解或准最优解。它的主要特点是简单、通用、鲁棒性强，对目标函数既不要求连续，也不要求可导，适用于并行分布处理，应用范围广。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多领域，如函数优化、组合优化、生产调度问题、自动控制、机器人智能控制、图像处理，人工生命、遗传编程、机器学习等。并且取得了令人瞩目的成果。1.2 研究内容传统的非线性规划算法的缺陷是计算烦琐且精度不高，稳定性差，对函数初值和函数性态要求较高，且容易陷入局部最优解。而遗传算法是一种鲁棒性很强的种全局搜索算法，理论上可以克服传统非线性规划算法的缺陷。本文的主要内容就是应用遗传算法的基本思想，结合本次实验的实际情况，对基本遗传算法加以改进，将遗传算法应用于求解非线性规划问题，形成求解非线性规划问题的遗传算法。具体内容包括编码方法设计，适应度函数设计，选择算子、交叉算子、变异算子等遗传算子设计，算法流程设计，并在设计的基础上用MATLAB语言实现该算法的程序，运行并调试程序，直至得到正确的结果。并对实验所得结果进行分析，比较求解非线性规划问题的遗传算法与传统的非线性规划算法的优缺点。2 非线性规划2.1 非线性规划的概念具有非线性约束条件或目标函数的数学规划，称为非线性规划。非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。2.2 非线性规划的数学模型对实际规划问题作定量分析，必须建立数学模型。建立数学模型首先要选定适当的目标变量和决策变量，并建立起目标变量与决策变量之间的函数关系，称之为目标函数。然后将各种限制条件加以抽象，得出决策变量应满足的一些等式或不等式，称之为约束条件4。非线性规划问题的一般数学模型可表述为求未知量，使满足约束条件： （2.1）并使目标函数达到最小值(或最大值)。其中，诸和诸都是定义在n维向量空间的某子集(定义域)上的实值函数，且至少有一个是非线性函数。 上述模型可简记为： （2.2） （2.3）其中属于定义域，符号min表示“求最小值”，符号s.t.表示“受约束于”。定义域中满足约束条件的点称为问题的可行解。全体可行解所成的集合称为问题的可行集。对于一个可行解，如果存在的一个邻域，使目标函数在处的值优于(指不大于或不小于)该邻域中任何其他可行解处的函数值，则称为问题的局部最优解（简称局部解）。如果优于一切可行解处的目标函数值，则称x*为问题的整体最优解（简称整体解