探讨启发式算法优化方法

由于多数复杂布局问题具有NP难度，人们在处理这些问题的过程中，降低了目标，不再坚持寻找最优解，而是试图在允许的时间内找到一个相对好的满意解。这些算法常常是根据明显的“经验方法”提出的，所以称之为启发式算法（Heuristic algorithms）。关于启发式算法的文献较多，以下给出一些与本书相关的工作。

国外方面，Tsai等提出一种基于H（水平）和V（垂直）算子共同作用的启发式算法，该算法可适用于多层布局问题。Daniels等通过求解约束一刀切问题的启发式算法，利用递归和返回的特性来加快匹配操作的过程。Yin和Cagan研究了扩展模式搜索方法，对基本模式搜索算法作了5点扩展分别为：待布物和模式方向探索次序随机选择；正常情况下探索步长逐渐减小，但允许小概率增大以充分搜索解空间；只有当平移和旋转均无法找到更优解时，尝试待布物位置交换；搜索方向的构造反映布局问题的特定约束条件；用于干涉检验的八叉树模型精度随步长动态变化。他们将其应用于布局设计问题，计算结果显示，此方法得到相同或相当质量布局方案所需的计算时间比传统的模拟退火算法缩短1～2个数量级，为目前最有效的布局方法之一。

国内较早采用的启发式算法是黄文奇的拟物拟人法。王金敏等的启发式算法将定序-定位函数和八叉树结构结合，并在约束的底盘装载问题中进行了运用。该方法首先确定布局物体放入布局容器中的先后顺序，然后决定布局物体在布局容器中如何摆放，并用改进的八叉树作为数据结构来表达布局问题的状态空间。王金敏、马丰宁等借助机构分析与综合中自由度的概念，提出高层次定序、低层次定位，两层交替进行的启发式求解策略。滕弘飞等提出了拟实验启发式算法，它是针对卫星舱布局方案设计问题，根据卫星舱动特性实验过程并运用敏度分析技术和其他启发式方法构造的，称之为拟实验启发式算法。陆一平和周济等利用膨胀算法来解决齿轮传动系统的带性能约束布局问题。1994年，戴佐等给出了一种启发式的八叉树算法，并用其求解了三维装箱布局问题。2000年，滕弘飞、孙治国等根据卫星舱多子空间物理结构分解，提出了启发式约束魔方变换法进行卫星舱布局问题的初始布局的构造。(www.xing528.com)

启发式算法基于人类经验建立算法的搜索规则，因此在求解某些特定类型设备布局问题较有效，计算速度较快，可以将人类某些专业领域的经验与计算机相结合，更高效地求解复杂问题，基于此，研究基于启发式规则的启发式协调机制来缓解协同进化中各个子问题之间耦合复杂性，加快子问题搜索后期的收敛速度并确定原问题方案。