组合优化问题算法研究论文

遗传算法的运行机理：对GA运行机理的解释有两类: 一是传统的模式理论；二是1990 年以后发展起来的有限状态马尔可夫链模型。（1）模式理论：由Holland创建，主要包括模式定理，隐并行性原理和积木块假说三部分。模式是可行域中某些特定位取固定值的所有编码的集合。模式理论认为遗传算法实质上是模式的运算，编码的字母表越短，算法处理一代种群时隐含处理的模式就越多。当算法采用二进制编码时，效率最高，处理规模为N的一代种群时，可同时处理O(N3)个模式。遗传算法这种以计算少量编码适应度而处理大量模式的性质称为隐并行性。模式理论还指出，目标函数通常满足积木块假说，即阶数高，长度长，平均适应度高的模式可以由阶数低，长度短，平均适应度高的模式(积木块)在遗传算子的作用下，接合而生成。而不满足积木块假说的优化问题被称为问题(deceptive problem)。模式理论为遗传算法构造了一条通过在种群中不断积累、拼接积木块以达到全局最优解的寻优之路。但近十多年的研究，特别是实数编码遗传算法的广泛应用表明，上述理论与事实不符。（2）有限状态马尔可夫链模型：由于模式理论的种种缺陷，研究者开始尝试利用有限状态马尔可夫链模型研究遗传算法的运行过程。对于遗传算法可以解决的优化问题，问题的可行域都是由有限个点组成的，即便是参数可以连续取值的问题，实际上搜索空间也是以要求精度为单位的离散空间，因此遗传算法的实际运行过程可以用有限状态马尔可夫链的状态转移过程建模和描述。对于有 m 个可行解的目标函数和种群规模为N的遗传算法，N 个个体共有 种组合，相应的马尔可夫模型也有 个状态。实际优化问题的可行解数量 m 和种群规模 N 都十分可观，马尔可夫模型的状态数几乎为天文数字，因此利用精确的马尔可夫模型计算种群的状态分布是不可能的。为了换取模型的可执行性，必须对实际模型采取近似简化，保持算法的实际形态，通过对目标函数建模，简化目标函数结构实现模型的可执行性。遗传算法优化的过程，可以看作算法在循环过程中不断对可行域进行随机抽样，利用前面抽样的结果对目标点的概率分布进行估计，然后根据估计出的分布推算下一次的抽样点。马尔可夫模型认为遗传算法是通过对搜索空间不同区域的抽样，来估计不同区域的适应度，进而估计最优解存在于不同区域的概率，以调整算法对不同区域的抽样密度和搜索力度，进而不断提高对最优解估计的准确程度。可见，以邻域结构为依据划分等价类的马尔可夫模型更符合实际，对问题的抽象更能体现优化问题的本质。