遗传算法最佳编码元数与适应度函数周期性的关联特性研究

根据问题的结构特点获取启发式信息是提高进化计算算法效率的关键。本项目拟研究如何根据适应度函数的周期性特点选择整数编码遗传算法的编码元数，旨在探索根据适应度函数设计遗传算法编码的通用原则。项目参考离散傅立叶变换或傅立叶级数形式，以可展开为分立周期的正弦分量线性组合的适应度函数为研究对象，采用积木块数量和结构作为编码性能的评价指标，从函数周期性的角度出发，研究编码对于适应度函数的依赖关系；主要研究内容包括：1) 单周期适应度函数的最佳编码元数与函数周期的关联特性；2)适应度函数的线性组合对最佳编码元数和函数周期性之间关联特性的影响；3）适应度函数周期偏离遗传算法的采样周期对最佳编码元数和函数周期性之间关联特性的影响。本项目将为遗传算法难易性研究提供新的视角，并将拓展高效率启发式搜索方法的可应用性。

空间解耦是降低优化问题难度的主要方法之一，其基本思路在于将全局最优解的搜索分解为在多个耦合程度较低的子空间中部分最优解的并行搜索。对于遗传算法（genetic algorithm，GA）等进化算法，根据问题的结构特点设计编码是实现这种空间解耦最重要的手段。该过程需解决两方面关键问题：1）选取合适的结构特性：通常高epistasis、低fitness distance correlation表示问题是GA难的，但这些指标并未能直接指导编码设计以降低问题的难度。2）选择合适的指标评价编码性能。评价指标和适应度函数结构特征之间缺乏直观联系，故合适的切入点成为研究编码原则以实现解耦的关键。本项目根据遗传算法搜索的多周期采样特点，选择以周期性为切入点进行研究，主要结果包括：1）分别基于模式定理和线性可分性的相关原理，建立了以一阶积木块数量和基因座耦合程度为指标的编码性能评价方法，以便从理论上解释编码性能差异的原因。2）对于以频率为m的正整数幂的正弦函数为基函数线性组合成的适应度函数，分别从一阶积木块数量和基因座耦合程度两方面指出了，二进制编码并非总是最佳选择，而编码元数为m的GAs有助于将最优串的搜索转化为多个基因座较佳取值的并行局部搜索，因而更适合应用于优化这些适应度函数。3）将2）中结果推广至更一般的、基函数频率为正整数的适应度函数，证明了当大部分基函数的频率为m的正整数幂时，相对于其他编码元数的遗传算法，编码元数为m的遗传算法能获得最多的一阶积木块，因而优化性能比其他编码元数的遗传算法更佳；且这种频率的基函数占比越大，这种差别越明显。除理论研究外，项目组成员还积极探索可能的应用前景，以期为今后应用该编码原则设计优化算法打下前期基础。本项目研究具有以下特色：1）与传统的GA研究方法不同，本项目对适应度函数进行三角级数分解，从而将编码研究简化为讨论编码性能与基函数频率等特征量之间的关系，为GA难易性和编码研究提供了一种新的视角，也有助于将泛函分析已有的理论和方法引入后续研究。2）选择基函数周期性为主要结构特征进行研究，发现了编码元数与基函数频率两者之间的关联特性。对于基函数频率为正整数的适应度函数，该关联特性为如何设计编码以降低基因座耦合程度提供了依据。3）所选的编码性能评价指标可在理论上解释编码性能差异的原因，其结论比单纯的经验仿真更能揭示编码的设计原则。