再上一篇:《用 于 最 优 化 的 计 算 智 能》
上一篇: 第 1 章  引  言
主页
下一篇:1. 3  本书的结构
再下一篇:1. 4  习题
文章列表

1. 2  最优化技术综述

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

这一节简要介绍各种最近发展起来的最优化新方法。

1.2.1  启发式搜索

启发式搜索最初是作为人工智能中问题求解程序的搜索器而被开发出来的[117]。在多数情况下,待解问题可以用状态空间加以表达,并用状态空间或图搜索算法求解。宽度优先和深度优先等图搜索算法的应用范围有限。不过,与待解问题相关的(启发)信息一般来说是可获取并运用于搜索过程。这使得最佳优先算法通常会有较好的表现。 * 算法[73]适

A

于求解状态空间中从起始节点到终止节点的最小代价路径。它依据代价函数来选择下一个被搜索或扩展的节点。代价函数计算出从起始节点到当前节点路径的代价,并用启发知

① 非确定性计算机是一类计算模型,例如非确定性图灵(Turing)机。

#第3页-

识估计出到终止节点的余下路径的代价。在满足“可容性”的条件下,如果存在最小代价路径,A* 一定可以找到。

1.2.2  霍普费尔德神经网络

自从霍普费尔德( )揭示了他所提出的计算网络的运算能力[84]以来,大量的

Hopfield

工作被投入霍普费尔德神经网络(简称霍氏网)的分析和应用。虽然最初的网络结构有它的弱点,霍普费尔德开创性的成果仍旧在某种程度上打通了一条神经网络的复兴之路。霍氏网的收敛性和稳定性已经被证明。加以适当改进后,霍氏网可用于求解旅行商问题等许多有约束条件的最优化问题。

将一个有约束条件的最优化问题抽象为可由霍氏网解决的形式,需要

(1) 将代价函数和约束条件转换为霍普费尔德能量函数;

(2) 确定拉格朗日(Lagrange)参数。

上述步骤往往是成功应用霍氏网的关键。许多研究人员未能复现霍普费尔德求解旅行商问题的结果,毛病经常就出在这里。在后续章节中,我们将讨论霍氏网的稳定性及其应用。

1.2.3  模拟退火与随机机

模拟退火算法最初由科克派特里克(Kirkpatrick)、小哥拉特(Gelatt Jr.)和瓦克奇(Vecchi)发明[98]。它模仿了液体结晶的过程:

(1) 在高温下,粒子能量较高,可以自由运动和重新排序;

(2) 随着温度的下降,粒子能量减弱,运动减少;

(3) 粒子最终进入平衡态,固化为具有最小能量的晶体。

模拟退火算法需要两个主要操作: 一个是热静力学操作,用于安排降温过程; 另一个是随机张弛操作,用于搜索在特定温度下的平衡态。模拟退火算法的长处在于它具有跳离局部最优解的能力。在给定温度下,模拟退火算法不但进行局部搜索,而且可以在一定概率下“爬山”到代价更高的解答以防止搜索进程陷入局部最小解。应用模拟退火算法以及各种不同的统计特性于霍氏网,可以得到波尔兹曼(Boltzmann)、高斯(Gaussian)、柯西(Cauchy)等随机机。类似于霍氏网的是,能量函数的拉格朗日参数对随机机的性能有重要影响。

1.2.4  均场退火

为了能以比随机机中的随机张弛操作更快的速度达到热平衡态,神经元的值可以由它们的平均值来加以近似。这时,在每一温度下,对神经元施加的是一个确定性的而不是随机性的操作。与随机机相比,这一网络只需较少的迭代次数便可在每一温度下达到热平衡态。在退火过程中,这一近似方法被称为均场退火。它在性能和计算复杂度二者之间作了一个很好的折衷。

#第4页-

1.2.5  遗传算法

遗传算法是一种模拟自然选择和遗传的随机搜索算法。它由贺兰德(Holland)提出[83],最初用于研究自然系统的适应过程和设计具有自适应性能的软件。遗传算法的基本形式要求有一个染色体表示用来对参数空间编码、一个适度函数用于估价所有的染色体、一组遗传操作用于产生新的染色体和一组概率用于控制遗传操作。遗传算法已被非常成功地应用于解决许多最优化问题并越来越流行。