基于遗传算法的求解约束优化问题的启发式算法研究

摘要

遗传算法是一种有效的随机搜索算法。相对于传统的数学优化方法而言，遗传算法具有适用性强、鲁棒性好等优点。在过去的几十年中，遗传算法被广泛地应用于各个领域。本文主要研究使用遗传算法来求解单目标约束优化问题以及多目标约束优化问题时的约束处理、种群多样性的维护方法以及外部种群的维护方法等相关问题。本研究分为八个部分：
　　 第一章对本文研究的意义、研究的问题以及研究方法进行简要的叙述。第二章对已有的相关研究进行详细的综述。第三章及第四章主要研究使用遗传算法求解单目标约束优化问题时的约束处理方法。第五章至第七章主要研究使用遗传算法求解多目标约束优化问题时的约束处理方法、种群多样性的维护方法以及外部种群的维护方法。
　　 第三章提出一种新的约束处理方法：边界模拟法。边界模拟法是一种模拟算法，这种算法可以有效地生成一个边界点集，从而对可行域的边界进行数值模拟。基于边界模拟法，遗传算法可以直接从可行域的边界或可行域内部开始搜索，从而可有效地提高搜索效率。
　　 第四章提出一种新的求解单目标约束优化问题的遗传算法：BoundarySimulation Genetic Algorithm(BSGA)。该算法使用边界模拟法对可行域的边界进行模拟，进而直接对可行域展开搜索。在搜索过程中，BSGA对搜索过程中生成的不可行解进行丢弃或修复，从而保证种群中个体的可行性。数值实验表明BSGA具有良好的鲁棒性以及寻优能力。
　　 第五章提出一种新的数据结构：Reletive Value Trie树(Rtrie树)。这种新的数据结构可以有效地的将整个种群划分为若干个子种群。在此基础之上，本文提出一种新的基于Rtrie树的种群初始化算予以及一种新的基于Rtrie树的选择算子用于求解多目标约束优化问题。
　　 第六章提出一种新的数据结构：Absolute Value Trie树(Atrie树)。基于这种Atire树数据结构，本文提出一种基于Atrie树的外部种群维护算子。这种外部种群维护算子使用Atrie树对种群中的个体进行过滤，从而去掉种群中某些无法对外部种群进行改进的个体，进而有效地降低了维护外部种群所需的计算成本。
　　 第七章提出一种新求解多目标约束优化问题的混合遗传算法：BoundarySimulation Trie Based Genetic Algorithm(BSTBGA)。这种算法使用边界模拟法从可行域的边界直接展开遗传搜索；使用基于Rtrie树的种群初始化算子及选择算子来维护种群的多样性；使用基于Atrie树的外部种群维护算子来降低维护外部种群所需要的计算成本；使用带有修复不可行解及丢弃劣解策略的交叉及变异算子来形成选择压力。数值实验表明BSTBGA算法可有效地求解带有复杂约束条件的多目标约束优化问题且能保证计算结果分布均匀。
　　 第八章对全文进行总结并提出未来的研究方向。