局部敏感哈希驱动的进化多任务优化算法

作     者：于拓彬 

作者单位：华南理工大学 

学位级别：硕士

导师姓名：龚月姣

授予年度：2023年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：进化多任务 局部敏感哈希 对位学习 信息迁移 

摘      要：进化算法是一类由生物界所引发灵感的、基于种群的元启发式算法,其包含蚁群优化算法、模拟退火算法等。随着当前科学技术的快速发展,现代社会对于算法的需求越来越高,由于进化算法具有较强的适用性及鲁棒性,其在目前受到了学术界及工业界的关注并得到了广泛应用。传统的进化算法每次都是从头开始进行搜索过程,每次仅能求解一个实际问题,但在现实生活中,各类问题很少单独存在,多个待求解的问题之间通常都存在一些联系。受到这一点的启发,有学者提出了进化多任务优化(Evolutionary Multitasking Optimization,EMTO)算法,该算法通过利用各个待求解的问题之间的相似性,从而高效地在个体之间传递遗传信息,进而加速对问题的求解,极大提高了求解效率。该领域最著名的算法就是多因素进化算法(Multifactorial Evolutionary Algorithm,MFEA)。然而,目前几乎所有的进化多任务优化算法在求解问题时,都只考虑了个体在目标空间的特性(即目标函数值),但却忽略了其在决策空间的信息。基于这一事实,本文提出的算法通过高效使用个体在决策空间和目标空间的信息,然后通过个体之间遗传信息的传递,从而提高进化多任务优化算法的效率。本文的主要工作及贡献总结如下:(1)本文对当前进化多任务优化算法所存在的优势与不足进行了分析,然后使用局部敏感哈希(Locality Sensitive Hashing,LSH)算法,生成若干个基于p-stable分布的哈希函数,接下来使用这些哈希函数将种群中的个体在决策空间的信息映射为哈希码,确保在决策空间相似的个体有较大概率被映射为同一个哈希码,而不相似的个体的哈希码则有较大概率不同,然后利用个体的哈希码来分析它们在决策空间中的分布信息。为了提高这些个体在演化过程中的探索能力,从而使其能够更快地找到最优解,本文引入了对位学习(Opposition-based Learning,OBL)策略,该策略通过在搜索空间中生成当前解的对位解,一定程度上了扩大种群中个体的搜索范围,提高了探索概率。(2)依据局部敏感哈希算法和对位学习策略,本文对MFEA进行了改进,具体来说,通过判断种群中待配对的个体的哈希码及其技能因素是否相同,本文针对性地设计了四种不同的繁殖与评估策略,然后给出了具体的算法框架,并在单目标多任务优化领域提出了LSH-MFEA。(3)为了验证算法的效率与有效性,本文在单目标多任务基准测试集上将LSHMFEA与其它算法进行了实验对比,实验结果证明了算法的效率。此外,本文还进行了消融实验与参数敏感性分析实验,探究各个模块的有效性及参数的不同取值对算法性能的影响。进一步,为了探究所提框架的泛化性,本文还将该框架拓展到了多目标多任务优化领域,通过对比试验证明了其具有良好的泛化性。