对遗传算法困难度测量的基因关联法的研究

Study on epistasis for measuring GA-hardness

针对基因关联测度法的本质及意义进行了详细的理论剖析和实证研究.首先分析了反映遗传算法基因关联程度的标准化的基因关联方差与基因关联相关系数,进一步归纳出两个基本定理,并给予了严格的数学证明.最后用一些初等函数及NNK-模型对这一方法进行了实证分析,实验结果表明,对于困难问题该方法能够给予准确的判别,而对于某些较为容易的问题可能产生误判.

Epistasis is an important index reflecting the extent of GA-Hardness. This paper is to analyze the essence of epistasis and its significance in measuring GA-hardness from both aspects of theory and practice. Based on analysis of the Euclidean normalization of the epistasis variance and the epistasis correlation coefficient, which reflect the extent of epistasis of GA, two theorems are formulated and proved. Then the method is verified by experiments using some elementary functions and NK-models. The obtained results show that the method can determine the difficult GA-hardness problems, however, it may classify some easy problems to a wrong category.