传统优化算法及其局限性

Cauchy早在1847年就提出了最速下降法，但对于不可导问题或变量较多的可导问题常常不适用[41]。在以后的很长一段时间内，这一问题一直没有取得实质性进展。直到电子计算机的应用和实际需要的增长，才使这一课题获得了新生。人们发展了导数法，同时也出现了一些从直观几何图形导出的搜索方法，比如，Rosenbrock提出了Rosenbrock法[42]，Hooke和Jeeves提出了模式搜索法[43]，Spendley、Hext和Himsworth于1962年提出并由Nelder和Mead做了改进的单纯形法[44]。另外还有Powell直接方法和Daviden发明的变尺度法（拟Newton法，或简称DFP法）[45]。以上方法都是针对一般目标函数设计的，Marquardt还研究了关于平方和形式的目标函数的优化算法[46]。归纳总结前人研究成果，非线性优化问题常用算法的求解步骤为[5]：

（1）找出一个初始点x0。

（2）分析函数性质，以此给出一个前进方向：x0→x1→x2…。

（3）直到满足某种收敛原则，得到优化结果。

以上优化方法一般称为传统优化方法。传统优化方法在模型优化中得到了广泛的应用，如：张建云等用Rosenbrock法和单纯形法求解了水文模型参数优选问题[47]，Lund和Israel应用两阶段和多阶段线性规划方法优化了城市供水调水规划问题，Reitsma应用大系统分解和典型优化方法解决了水资源管理和决策问题；Slinger和Breen等成功地将非线性规划方法和模型联解应用到水资源综合管理中[5]。

优化问题的求解就是在优化问题的可行解空间进行有效搜索，进而找出其最优解。按照搜索策略的不同，可将传统优化算法分为四类[5]。

1.枚举法

枚举法的搜索策略是对整个可行解空间的所有点的性能进行比较，从而找出最优解。枚举法的搜索策略最简单，计算量也最大。该方法的主要缺点是存在“维数灾”问题，搜索效率不高。枚举法一般只能应用于可行解空间是有限集合的情形。枚举法又包括完全枚举法、隐式枚举法（分枝定界法）和动态规划法等。

2.导数法(www.xing528.com)

导数法（包含用差分代替导数）在搜索过程中主要使用目标函数的一阶导数、二阶导数等进行优化计算，它是从一个初始点出发，根据目标函数的梯度方向来确定下一步的搜索方向以寻找最优点。导数法采用的是“最速下降（上升）”策略，即沿最陡的方向爬向一个局部最优点。当目标函数是复杂的非线性多峰函数时，导数法将会变得非常困难和不稳定，难以找到全局最优点。导数法主要有Newton法、共轭梯度法和变尺度算法等。

3.直接法

直接法（确定性）的搜索策略是从一个初始点出发，通过反射、延伸、收缩、减少棱长或通过探测、模式移动等手段，比较目标函数的大小以确定下一步的搜索方向，从而找出最优解。直接法不需要计算目标函数的导数，其搜索策略简单，计算量也不算大，但当自变量个数较多或目标函数是多峰函数时，往往搜索效率不高。直接法有单纯形法、模式搜索法、方向加速法和Rosenbrock法等。

4.随机法

随机法的搜索策略是在搜索方向上引入随机的变化，通过随机变量的大量抽样，以得到目标函数的变化特性，使得算法在搜索过程中以较大的概率跳出局部最优点。研究表明，随机优化方法也尚无法满足许多复杂水资源系统优化问题求解的要求[21]。

传统的优化方法，如Newton法、共轭梯度法、变尺度算法、单纯形法、模式搜索法、方向加速法和Rosenbrock法等，都是与初始点有关的优化方法，常常是找出初始点附近的一个极值点来，至于它是否为全局极值点，在多数情况下不得而知。但在实际的优化问题中，常常都希望找到给定条件下的全局极值点[5]，而求全局极值的方法，本质上则是一种试探性搜索方法。由于全局极值点在可行域D中的确切位置事先并不知道，而是通过构造序列{xn}来估计的，因此，必然要求{xn}在D中分布均匀且有一定的密度。经典的蒙特卡罗法（Monte Carlo Method）在理论上是能满足这种要求的，优化问题的维数、几何形状、是否离散等对它影响也不大，但在实际中它却没有使用价值，这是因为，在D中分布均匀的前提下，为了提高解的精度，势必在极值点附近加密投点的同时，也在D中盲目地加密了投点，这就导致了其运算量十分浩大，该算法的时间复杂性破坏了算法的可行性条件，因而是不合理的。合理的办法是，发展一些启发式策略或引入领域知识，对投点过程给予指导，即在可能出现全局极值点的地方增加投点密度，而对其他地方只作少量的试探性投点，特别是对已探明无全局极值点的地方不投点，从而可大大节省计算量，对该算法的时间复杂性进行了有效压缩，使该算法可行[2]。后面介绍的智能优化算法就是一种启发式算法，充分积累了搜索的信息，较好地处理了积累信息与探索未知空间的矛盾[5]。

另一方面，传统优化算法属于局部优化方法，而且对于约束非线性规划问题处理比较麻烦[1]。就如何提高非线性规划算法的效率及如何处理好越来越多的各种约束问题，Templeman和Li提出了以信息熵概念为基础的约束非线性规划方法，使得约束处理更加灵活主动，概念更加清晰[48]。李兴斯利用最大熵优化法，使用代理约束与信息熵的概念，建立了代理乘子的迭代公式[49]，在此基础上，用一个称之为“凝聚”函数的光滑函数直接代替不可微的极大值函数，使用这一光滑技术，可把无约束与有约束极大、极小两种问题均转化为光滑函数的无约束优化问题[50]。杨仲侯等在结构优化设计中，将序列二次规划数学模型与最大熵原理结合起来，成功地解决了结构优化设计问题[51]。黄震宇等提出了一类新的熵函数，用于解连续型极大、极小问题[52]。以上方法对最终目标函数都有一定的限制，至少要求目标函数连续或可导，所以该方法应用上发展不快[5]。

在实际中经常遇到的优化问题使人们逐渐认识到，用某种优化方法寻求最优点不是唯一目的，更重要的目标往往是解的不断改进的过程，对于复杂的优化问题更是如此。