智能优化算法在高维多约束问题中的进展

遗传算法的主要任务和目的，是设法产生或有助于产生优良的个体成员，且这些成员能够充分表现出解空间中的解，从而使算法效率提高且避免早熟收敛现象。但是，实际应用遗传算法时，往往出现早熟收敛和收敛性能差等缺点。现今的改进方法，大多针对基因操作、种群的宏观操作、基于知识的操作和并行化GA进行。

对于复制操作，De Jong（1975）研究了回放式随机采样复制，其缺点是选择误差较大；同时，他又提出了无回放式随机采样复制以降低选择误差。Brindle（1981）提出了一种选择误差更小、操作简单的确定式采样以及无回放式余数随机采样方法。Back（1992）提出了与适配值大小和正负无关的均匀排序策略；同时又提出全局收敛的最优串复制策略，提高了搜索效率，但不适于非线性较强的问题。在交叉操作方面，有Goldberg（1989）提出的部分匹配交叉算子（partially mapped crossover）、Starkweather等学者（1991）提出的增强边缘重组算子（enhanced edge recombination）、Davis（1991）提出的序号交叉算子（order crossover）和均匀排序交叉算子（uniform order-based crossover）、Smith（1985）提出的循环交叉算子（cycle crossover）、De Jong（1975）提出的单点交叉算子（one-point crossover）和多点交叉算子、Syswerda（1989）提出的双点交叉算子（two-point crossover）.此外常用的交叉算子还有置换交叉、算术交叉、启发式交叉等。变异操作方面主要发展了自适应变异、多级变异等操作。为了改进算法的性能，一些高级的基因操作也得到了发展和应用，譬如双倍体和显性遗传（diploid and dominance）用以延长曾经适配值高而目前较差的基因块的寿命，并且在变异概率低的情况下也能保持一定的多样性；倒位操作（inversion）用以助长有用基因块的紧密形式；优先策略（elitism）用以把目前解群中最好的解直接放入下一代种群中，如此保证各代种群中总会有目前为止最好的解；静态繁殖（steady-state reproduction）用以在迭代过程中用部分优质子串来更新部分父串作为下一代种群以使优质的父串在下一代中得以保留；没有重串的静态繁殖（steady-state without duplication）用以在形成下一代种群时不含重复的串。此外，还有多倍体结构（multiple chromosome structure）、分离（segregation）、异位（translocation）等操作。在种群宏观操作方面，主要是引入小生存环境和物种形成（niche and spectiation）的思想，这在分类问题中得到了应用。在基于知识的操作方面，主要是将问题的特殊信息与GA相结合，包括混合算法的构造以及在遗传算子中增加知识的操作等。

遗传算法的结构也是很值得研究的问题。Krishnakumar（1989）为克服群体数目大造成计算时间长的缺点，提出了所谓GA的小群体方法，仿真结果显示了较高的计算效率和适于动态系统优化的潜力，但尚无严格的理论分析。Schraudolph等学者（1992）针对二进制编码优化精度差的缺点，提出了一种类似于对解空间进行尺度变换的参数动态编码策略，较好地提高了GA的精度，但不适于非线性较强的多极小优化问题。Androulakis等学者（1991）采用实数编码提出了一种扩展遗传搜索算法，把搜索方向作为独立的变量来处理以解决有约束的优化问题。Poths等学者（1994）为克服算法早熟收敛的缺点，提出了类似于并行实现思想的基于变迁和人工选择的遗传算法。Grefenstette（1981）全面研究了GA并行化实现的结构问题，并给出了多种结构形式，主要有同步主仆方法（synchronous master-slave）、亚同步主仆方法（semi-synchronous master-slave）、分布式异步并发方法（distributed asynchronous concurrent）、网络方法（network）。Goldberg学者（1989）提出了基于对象设计GA并行结构的思想。Muhlenbein等（1991）用并行遗传算法求解高维多极小函数的全局最小解，从而提供了GA求解高度复杂优化问题的有力实例。

在函数优化方面，Goldberg（1989）引入分享（sharing）思想将解空间分成若干子空间，然后在子空间中产生子群体成员分别进行优化，以求得整个问题的解，避免算法只收敛到某个局部解；De Jong（1975）提出聚集（crowding）的思想，根据群成员中的相似性来部分替换群体中的个体成员，从而将一些个体成员分别聚集于各个群集中，然后在各个群集中分别求解问题的局部解以实现与分享思想相同的目标。然而，这些方法的应用还有一定的限度，对于解是随机分布的情况就不易奏效。由此，孟庆春等学者（1995）提出门限变换思想，在选择个体成员进入下一代时，引入门限变换函数将某些优良成员周围的成员传到下一代以达到除劣增优的目的，从而避免搜索的盲目性。至于有约束优化问题的求解，目前的处理方法主要有：

（1）把问题的约束在“染色体”的表示形式中体现出来，并设计专门的遗传算子，使“染色体”所表示的解在GA运行过程中始终保持可行性。这种方法最直接，但适用领域有限，算子的设计也较困难。(www.xing528.com)

（2）在编码过程中不考虑约束，而在GA运行过程中通过检验解的可行性来决定解的弃用。这种方法一般只适用于简单的约束问题。

（3）采用惩罚的方法来处理约束越界问题。

但到目前为止，采用GA求解高维、多约束、多目标的优化问题仍是一个没有很好解决的课题，它的进展将会推动GA在许多工程领域的应用。