一种改进的演化算法及其在求解复杂优化问题中的应用*

针对传统演化算法在求解函数优化,特别是多峰函数优化问题中出现的早熟现象以及演化后期收敛速度慢等问题,提出了一种新的反序小生境演化算法。该算法采用小生境反序交叉算子,以进一步增强局部寻优的能力;引入一种并行演化算法机制,加强群体寻优能力;同时,根据定义域划分初始种群,增加初始种群的覆盖面积。通过仿真实验表明,与传统的小生境演化算法相比较,利用该算法求解复杂多峰函数优化问题能够明显提高问题的求解精度和收敛速度,而且能够得到所有的全局最优解,更好地避免了求解问题时的早熟现象,达到了较好的效果。     

基于演化算法的SAT问题求解

SAT问题即布尔可满足性问题是逻辑学的一个基本问题,也是计算机科学和人工智能研究的核心问题。寻找求解SAT问题的快速算法不仅在理论研究上而且在许多应用领域都具有极其重要的意义。本文讨论了基于演化算法的SAT问题求解方法。     

二维目标下分布性与收敛性结合的种群维护策略

种群维护是多目标进化算法的重要组成部分。针对传统方法在维护过程中只考虑分布性的情况,提出一种分布性与收敛性结合的种群维护策略,该方法用一种邻近个体间的相对趋近关系来表示其适应值,弥补了单纯Pareto支配关系的“粗糙性”,并用一种可调邻域的方法对种群的密集程度进行控制。将其与NSGA-II和SPEA2进行对比,实验结果表明该算法在有效保持种群分布性的同时,拥有良好的收敛性和速度。     

基于混合演化算法的二维下料问题

介绍了将二维下料问题建模成旅行商问题的方法,指出单纯旅行商问题模型的局限性,认为其是一种启发式方法,理论上找不到全局最优解。针对于此,在原有模型的基础上引入旋转变换,提出了两种混合演化算法捆绑式深化算法和元算法。实例仿表明,该算法可以获得比普通经算法好的结果。     

一种基于相似个体的多目标进化算法

分布性保持是多目标进化算法研究的一个重要方面,一个好的分布性能给决策者提供更多合理有效的选择。Pareto最优解的分布性主要体现在分布广度与均匀性两个方面。提出一种基于相似个体的多目标进化算法（SMOEA）。在种群维护中删除相似程度最大的个体;在进化操作中,选取了相似程度最大的个体进行进化。与目前经典算法NSGA-II和ε-MOEA进行比较,结果表明新算法拥有良好的分布性,同时也较好的改善了收敛性。     

一种基于邻域的多目标进化算法

种群维护是多目标进化算法的重要组成部分。针对维护方法和运行效率的矛盾,提出一种基于邻域的多目标进化算法（NMOEA）。定义了一个反映个体之间邻近程度的指标--邻域包含关系,利用此关系对个体进行分布适应度分级的赋值,并用动态方法快速地对种群进行维护。通过7个测试问题和3个方面的测试标准,结果表明新算法在较快速地接近真实的最优面的同时,拥有良好的分布性。     

多式联运运输问题的混合遗传算法

多式联运运输方式的选择关系到货物运输所需费用、时间等。该文对需经过多式联运过程的运输问题进行了研究。首先分析了多式联运运输问题的数学模型;其次通过引入关于运输量及运输方式的混合编码,结合两种混合遗传算子,提出了一种求解多式联运运输问题的混合遗传算法;最后用数值例子对算法的有效性进行了验证。     

结合远离最差策略的自适应量子进化算法

针对传统的量子进化算法只使用当前最优个体作为指导,存在进化能力不足,易陷入局部极值的问题,提出了一种结合远离最差策略的自适应量子进化算法KSQEA,使个体在进化过程中不仅向最优个体靠近,而且还远离最差个体,这样在最优个体优势不明显时仍有可能获得进化动力。旋转角更新则采用一种新的自适应波浪式衰减方式,以更好地平衡探查和利用。在函数优化和背包问题上的实验结果表明,以上措施有效地增强了算法的搜索能力,提高了解的质量。     

多点交叉学习组织进化算法

为了提高组织进化算法(organizational evolutionary algorithm,简称OEA)在高维多模函数全局优化中陷入局部极值,分析了OEA 算法早熟收敛的原因,提出了多点交叉学习组织进化算法(mOEA).设计了一个多个组织的领导交叉学习策略来提高组织领导种群多样性,避免早熟收敛;结合社会群体认知和学习的习性,改进OEA 中的吞并算子,使得同一组织内的个体成员有的在其领导周围爬山运动,有的在搜索范围内随机变异,既提高成员群体的适应度值,又增强成员群体的多样性,不易陷入局部极值.与OEA     

A cascade evolutionary algorithm for the bodyguard allocation problem

The bodyguard allocation problem (BAP) is an optimization problem that illustrates the behavior of processes with contradictory individual goals in some distributed systems. The objective function of this problem is the maximization of a parameter called the social welfare. Although the main method proposed to solve this problem, known as CBAP, is simple and time efficient, it lacks the ability to generate a diverse set of solutions, which is one of the most important feature to improve the chances to reach the global optimum. To overcome this drawback, we address the BAP with an evolutionary algorithm, the EBAP. Later, we take advantage of the best properties of both algorithms, EBAP and CBAP, to generate a two-stage cascade evolutionary algorithm called FFC-BAP. Extensive experimental results show that the algorithm FFC-BAP outperforms both the EBAP and the CBAP, in terms of quality of solutions.     

DNTrans:基于Transformer的黑产域名变换生成方法

目前很多黑产团伙为了对抗监管部门对其网站域名的封锁,会批量搭建黑产网站和注册大量的黑产域名。这些批量注册的域名之间存在着一定的相似性,这种相似性使得研究者可以对已知域名进行分析,进而研究未知域名的生成。本文研究区别于以往研究对黑产域名生成的处理方法,我们将域名生成任务转变为翻译任务。首先,我们采用Bi-LSTM将训练数据中的域名转为表征向量后进行层次聚类,将相似的域名聚为一类,并且通过参数设置,使得聚类簇中的域名个数尽量分布均匀。然后,根据聚类结果生成翻译模型所需的域名对数据。最后,使用Transformer模型自动学习相似域名之间潜在的变化规则进行黑产域名的变换生成。其中域名生成结果检验采用的是我们自己提出的两阶段黑产网站检测模型,模型通过设置置信度阈值的方式控制检测模型大小以及所需数据来平衡识别准确率和效率。实验表明,生成算法生成的域名中,可访问域名中黑产域名比率为19.1%,黑产域名的扩展倍数达到了359.98,即通过一个黑产域名可以平均扩展出近360个新的黑产域名。实验结果证明了该方法在黑产域名变换生成上的有效性,并解决了现有公害域名生成方法难以控制域名生成的范围,存在大量的无效域名的问题。     

一种基于多智能体进化的广义图染色算法

基于对广义图染色问题的研究,提出了一种求解广义图染色问题的多智能体进化算法(multiagent evolutionary algorithm for T-coloring problem,简称MAEA-TCP),并将该算法应用到实际中的频率分配问题上,取得了良好的效果.该方法中每个智能体作为一个候选解被固定在智能体网格上,为了增加自身能量而与邻域当中的智能体展开竞争或者合作,同时智能体也可以利用自身的知识进行自学习来增加能量.根据广义图染色问题的特点,为智能体设计了3种算子:竞争算子、自学习算子和变异算子,以引导其进化,并用进化的方式来控制各算子,以协调智能体之间的相互作用.在实验中,分别使用大规模的随机图实例和费城实例来测试算法性能,同时给出参数测试结果和最佳取值区间.比较结果表明,该算法优于其他方法,具有良好的收敛性和实用价值.     

一种改进的求解TSP问题的演化算法

演化算法是解决组合优化问题的高效搜索算法．该文在现有求解TSP问题的演化算法的基础上,通过引入映射算子、优化算子以及增加一些控制策略,提出了一种高效的演化搜索算法．实验表明,该算法是有效的,通过对CHN144以及国际通用的TSPLIB中不同城市规模的数据进行测试表明,其中实例CHN144得到的最短路径为30353．860997,优于吴斌等运用分段算法得到的最短路径30354．3,亦优于朱文兴等人的结果,实例st70和kroB150得到的最短路径分别与运用分段算法得到的最短路径值相同,实例pr136得到的最短路径值为96770．924122,优于TSPLIB中提供的最短路径96772,对于其它实例也均能快速地得到和TSPLIB中提供的最优路径相同或更优的路径,该算法不仅很容易收敛到问题的最优解,而且求解速度极快．     

大规模集装箱装载问题

对于大规模三维装箱问题,利用区域分裂法的基本思想,将复杂的大规模装箱问题通过货物的重组分解为若干个小区域上的问题,然后通过合并小区域之间的解得到整个区域的解。该方法能分解大型问题为小型问题,复杂区域问题为简单区域问题。在传统演化算法的基础上,引入了模拟退火产生新个体思想对其进行改进,提高了算法的运行效率和解的有效性。通过对某港口案例进行测试,结果证实该算法能满足实际装载需求。     

用多目标演化优化算法解决约束选址问题

约束选址问题是一个多目标约束优化问题,传统算法（加权法）一次只能得到一个候选解,用多目标演化优化算法对其进行求解,可以一次得到多个候选解,给决策者提供更多的选择余地,以期获得更大的利益,数字试验表明,该方法优于传统多目标优化方法。     

基于概率分布的多峰演化算法

演化算法通过模拟自然界生物迭代演化的智能现象来求解优化问题,因其不依赖于待解问题具体数学模型特性的优势,已成为求解复杂优化问题的重要方法.分布估计算法是一类新兴的演化算法,它通过估计种群中优势个体的分布状况建立概率模型并采样得到子代,具有良好的搜索多样性,且能通用于连续和离散空间的优化问题.为进一步推动基于概率分布思想的演化算法发展,概述了多峰优化演化算法的研究现状,并总结出2个基于概率分布的演化算法框架：面向多解优化的概率分布演化算法框架和基于概率分布的集合型离散演化算法框架.前者针对现有的演化算法在求解多峰多解的优化难题时缺乏足够的搜索多样性的缺点,将广义上基于概率分布的演化策略与小生境技术相结合,突破多解优化的搜索多样性瓶颈;后者围绕粒子群优化等部分演化算法在传统上局限于连续实数向量空间的不足,引入概率分布估计的思想,在离散的集合空间重定义了算法的演化操作,从而提高了算法的可用性.     

一种改进的非支配排序多目标遗传算法

多目标进化算法的研究目标主要是使算法快速收敛,并且广泛而均匀分布于问题的非劣最优域。在NSGA-II算法的基础上,提出了一种新的构造种群的策略——按照聚集距离选取部分非支配个体,并选取部分较好的支配个体形成下一代种群。该策略与原算法相结合后的算法（NSGA-II+IMP）与原NSGA-II进行比较,结果表明新算法较好地改善了分布性和收敛性。     

可求解多目标优化问题的演化博弈优化算法

借鉴演化博弈的思想和选择机制,提出了一种新的基于演化博弈的优化算法(EGOA)用于多目标问题的求解.算法框架具备对该类问题的通用性.为了对算法性能进行评估,采用了一组多目标优化问题(MOPs)的测试函数进行实验.实验结果表明,使用本算法搜索得到的演化稳定策略集合能够很好地逼近多目标优化问题的帕累托前沿,与一些经典的演化算法相比具有良好的问题求解能力.     

MaOEA/d2:一种基于双距离构造的高维多目标进化算法

传统的基于Pareto支配关系的多目标进化算法(MOEA)难以有效求解高维多目标优化问题(MaOP). 提出一种利用PBI效用函数的双距离构造的支配关系, 且无需引入额外的参数. 其次, 利用双距离定义了一种多样性保持方法, 该方法不仅考虑了解个体的双距离, 而且还可以根据优化问题的目标数目自适应地调整多样性占比, 以较好地平衡高维目标解群的收敛性和多样性. 最后, 将基于双距离构造的支配关系和多样性保持方法嵌入到NSGA-II算法框架中, 设计了一种基于双距离的高维多目标进化算法MaOEA/d². 该算法与其他5种代表性的高维多目标进化算法一同在5-、10-、15-和20-目标的DTLZ和WFG基准测试问题上进行了IGD和HV性能测试, 结果表明, MaOEA/d²算法具有较好的收敛性和多样性. 由此表明, MaOEA/d²算法是一种颇具前景的高维多目标进化算法.