数值优化方法及MATLAB实现（一）

本文作者：过冷水

读者朋友大家好！我是过冷水，最近在学习的过程中遇到极值寻优问题，觉得寻优问题是很多人关注的一个知识点，于是就准备开一个新的连载和大家一起来解决极值寻优过程中遇到的问题。

在现实生活中，经常会遇到某类实际问题，要求在众多的方案中选择一个最优方案。例如，在工程设计中，如何平衡成本和收益在满足要求的前提下达到效益;在产品加工过程中，如何搭配各种原料的比例才能既降低成本，又提高产品质量。这一类问题的特点，就是要在可能的方案中，选出最合理的，以达到事先规定的最优目标的方案，即最优化方案。寻找最优方案的方法称为最优化方法，为解决这类问题所需的数学计算方法及处理手段即为优化算法。最优化问题是个古老的问题，早在17世纪欧洲就有人提出了求解最大值最小值的问题，并给出了一些求解法则。随着科学的发展，人们逐渐提出了许多优化算法并由此形成了系统的优化理论，如线性规划、非线性规划、整数规划和动态规则等，但由于这些传统的优化算法，一般只适用于求解小规模间题，不适合在实际工程中应用，所以自20世纪80年代以来，一些新颖的优化算法，如人工神经网络、混池、遗传算法、进化规划、模拟退火、禁忌搜索及其混合策略等，通过模拟或揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智能和统计力学等学科，为解决复杂问题提供了新的思路和手段。

优化问题举例

1.最优化：假设人的身高体重方程为

H=a*W+b;

式中，W: Wight体重。H:Hight 身高.a、b：修正参数。

为了确定参数a和b，通常采集大量体重对应的身高数据。问应该怎样根据m个实验数据来确定参数a和b。如果将参数a和b确定，那就确定了W对H的一个函数关系，我们的目的是使得实际身高体重最大程度上符合这是函数关系。实际身高和计算出来的身高偏差越小越好。因此问题的数学模型为

2.数学规划

2数学规划

在一些等式或不等式约束条件下，求一个目标高数的极大(或极小）的优化模型为数学规划。视有、无约束条件而分别称为约束数学规划和无约束规划。约束数学规划的一般形式为

若目标函数f(x)和约東条件中的函数h(x)、g(x)均为线性函数，则称数学规划为线性规划，否则称非线性规划。若数学规划中的变量x限取整数值则称为整数规划。

在数学规划中，把满足所有约東条件的点x称为可行点(或可行解)，所有可行点组成的点集称为可行域，若把可行域记为S，即

S＝{x|hi(x)＝0，i＝1，2，…，l ; gj(x)≥0，j＝1，2，…，m}

于是数学规划即求x*∈S,且使f(x*)在S上达到最大(或最小),把x*称为最优点(最优解)，f(x*)称为最优值。

在线性规划和非线性规划中，如所研究的问题都只含有一个目标函数，则这类问题常称为单目标规划;如果含有多个目标函数，则称为多目标规划。

3 组合优化问題

组合优化问题通常可描述为:令Ω＝{s1，s2，…，sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值,要求寻找最优解s*，使得si∈Ω，C(si)＝minC(si)。组合优化问题往往涉及排序、分割、筛选等问题，是运筹学的一个重要分支。

旅行商问题:给定n个城市和两两城市间的距离，要求确定一条经过各城市一次并回到起始城市的最短路径。

0-1背包问题:对于n个体积分别为ai、价值分别为ci的物品,如何将它们装入总体积为b的背包中，使得所选物品的总价值最大。

聚类问题:m维空间上的n个模式｛Xili＝1，2，…,n)要求聚成k类,使得各类本身内的点相距最近，例如要求

式中:Rp为第p类的中心,即

式中:p＝1，2…k;np为第P类中的点数.

优化算发展状况

随着应用和需求的不断发展，优化算法理论和研究也得到了较大的发展。就优化算法的原理而言，目前工程常用的优化算法主要有经典算法、构造型算法、改进型优化算法、基于系统动态演化的算法、混合型算法和群智能算法等现代优化算法。

经典算法：经典算法包括线性规划、动态规划、整数规划和分支定界等运筹学中的传统算法。这些算法在求解小规模问题中已得到很大成功，但在现代工程中往往不实用。

改进型算法：从任一解出发，通过对其邻域的不断搜索和对当前解的判断替换来实现优化。根据搜索行为，又可分为局部搜索法和指导性搜索法。前者有爬山法、最陡下降法等;后者有模拟退火、遗传算法、禁忌算法、进化算法、群智能算法等。

基于系统动态演化的方法：基于系统动态演化的方法是将优化过程转化为系统动态的演化过程，然后基于系统动态演化来实现优化，如神经网络法和混沌搜索法等。

混合型算法：混合型算法是将上述各算法从结构或操作上进行混合而产生的各类算法，如遗传一神经网络算法等。现代实际工程问题往往具有大规模、强约束、非线性、多极值、多目标、建模困难等特点，寻种适合于现代工程问题的具有智能特征的优化算法已成为引人注目的研究方向。一个优化算法要取得优异的优化质量、快速的优化效率、鲁棒和可靠的优化性能，必须具有以下能力:①全局搜索能力，以适应问题的非线性和多极值性;②一定优化质量意义下的高效搜索能力，以适应问题的大规模性以及NP类等问题的复杂性;③对各目标的合理平衡能力，以适应题的多目标性和强约東性;④良好的鲁棒性，以适应问题的不确定性和算法本身的参数;⑤搜索操作的灵活性和有效性，以适应问题中连续与离散变量共存的特点。

值得指出的是，对于所有函数集合，并不存在万能的最佳优化算法。所有算法在整个函数类上的平均表现度量是相同的。为此关于优化算法的研究应从寻找所有可能函数上的通用优化算法转变为以下两个方面:

①以算法为导向，确定其适用的问题类。对于每一个算法，都有其适用的和不适用的问题，对于给定的算法，要尽可能通过理论分析和实际应用，找出其适用的范围，归纳特定的问题类，使其成为一个指示性算法。

②以问题为导向，确定其适用的算法。对于较小的特定问题类或特定的实际应用同题，设计出具有针对性的适用算法。实际上，大多数在优化算法方面的研究都属于这一范，因为它们主要是根据进化的原理设计新的算法，或者将现有算法进一步优化改造，以期对若干特定的函数类取得较好的优化效果。

关于极值寻优的背景介绍就这么多，下期开始就开始过冷水特有的学习风格——理论+案例+代码的模式了。感兴趣的读者请持续关注，有疑问的地方欢迎共同讨论。