论文部分内容阅读
遗传算法是广泛用于求解最优化问题的智能计算方法。由于遗传算法能有效地求解属于NPC类型的组合优化问题及非线性多模型、多目标的函数优化问题,从而得到了多学科的广泛重视,成为了最佳工具之一。然而许多当前的遗传算法在解决复杂问题时存在早熟收敛以及停滞的现象。这可以归因于算法在收敛状态限制其大范围搜索解空间前已经失去了发现新的、有潜力的遗传物质(Genetic Material)的能力。本文在研究分析标准遗传算法因容易陷入早熟收敛而失去多样性导致算法缺乏可持续性的缺陷基础上,受自然界广泛存在的分阶层公平竞争以及“积木块”自组织成复杂系统现象的启发,研究了一种基于分层公平竞争的可持续性进化算法模型——分层公平竞争模型以及由该模型衍生出的可持续的遗传算法。该模型通过将传统收敛进化计算模型转换为非收敛的可持续搜索模型来改善进化算法的可持续性。同时提出了一种基于不同阶层演化情况改进该模型中不同阶层输入阈值更新过程的动态阈值更新公式,该公式使用惯性项来保证输入阈值更新过程的平滑性。然后提出了一种使用多线程并行演化分层公平竞争模型的方法。在分层公平竞争模型中,使用一种按适应值梯度划分子种群等级的流水线结构,在减少子种群选择压力的情况下保持一定的全局选择压力以保证新发现的有潜力的“基因材料”得到充分的开发(exploitation)。与传统的遗传算法尝试从高度演化、包含相似度很高“积木块”的种群中尝试跳出局部最优区域的策略不同,分层公平竞争模型通过不断维护中等适应值群体,确保新的局部最优解不断地被自底向上(bottom-up)培育、加工出来的策略来维持种群的多样性。但是,由于分层公平竞争模型是在标准遗传算法的基础上改进而来的,仍然存在结构上的固有缺陷,例如遗传漂移(Genetic Drift)、采样误差(Sampling Error)等。为了克服这种缺陷并更好地实现可持续性进化,本文在基于分层公平竞争模型的可持续遗传算法中加入了一定的动态机制,从而研究得到了两种改进的HFC算法——自适应性输入阈值的HFC算法(HFC+nor)和加入惯性项的自适应性输入阈值的HFC算法(HFC+adap)。HFC+nor算法能够根据每一层的演化情况自适应的调整分层公平竞争模型中各层的输入阈值;HFC+adap算法引入了惯性项保证阈值更新过程中的平滑性,避免出现阈值更新过程中的阶跃现象。最后,本文通过基于2进制编码的HIFF 128/256问题和基于浮点数编码的De Jong’s Functions系列Benchmark测试函数验证了HFC类算法的有效性以及种群多样性,并从解的质量以及时间复杂度方面将HFc类算法与采用相同选择策略的传统遗传算法进行了比较,证明了本文提出的算法可以有效地缓解传统遗传算法的早熟收敛问题。