论文部分内容阅读
进化算法是一类模拟自然界生物进化的基于种群的元启发式优化算法,如遗传算法、粒子群算法等。与经典的数学优化方法不同,进化算法具有问题依赖小、全局最优化的特点,被广泛应用于解决困难的现实优化问题。传统的进化算法一次只能解决一个优化任务,无法利用任务之间的相关性。近年来一种新兴的进化多任务优化算法,可以利用进化算法同时解决多个优化任务。利用任务间的知识迁移,使从解决一项任务中获得的有用知识可以帮助解决另一项任务,从而提高每个子任务的优化性能。本文主要研究,如何通过设计知识迁移策略来提高多任务优化的整体效率,以及探究如何利用分布式的计算设备来加速进化多任务优化。据我们所知,本文是第一个探究进化多任务优化并行化的工作。主要研究工作包含以下三个方面:(1)提出一种自适应的知识迁移算法,旨在提高多任务优化的整体效率。相比已有的算法,本算法可以根据任务自身优化的效率和知识迁移的效率自适应地调节知识迁移的频率,当面对多个候选任务的知识源选择时,每个任务可以根据不同候选任务的有益性做自适应的知识采样,保证相关任务之间的知识迁移强度。实验表明,在众多的测试问题(21个)上,本文提出的自适应知识迁移算法可以有效的提升多任务优化的整体效率。与其他多个先进的进化多任务优化算法相比,本文提出的算法在求解精度和求解速度上都更优。(2)分析了进化多任务优化并行化的难点,提出了一种简洁的进化多任务优化的并行框架。该框架中,每个任务分配两个线程(同一个进程中),主线程用于任务求解和与其他任务同步,辅助线程负责将当前任务的知识发送给其他知识请求者(其他任务)。设计了一种异步的通信策略,可以保证任务之间的高效通信。在多个多任务优化问题上进行了实验,结果表明,并行算法的求解精度与串行算法没有显著差异,对于子任务求解较复杂的问题具有显著的加速效果。(3)分析了(2)中提出的并行框架在解决拥有海量子任务的多任务优化问题的缺陷,提出了一种弹性可扩展的并行框架。该框架中,每个计算节点由多个CPU核构成,一个计算节点可以解决多个任务,多个计算节点共同解决所有任务。当任务数量超过每个计算节点的计算资源时,多个任务分时共享计算资源。实验中利用32个计算节点(每个节点由8个CPU核组成),并行算法在求解精度与串行算法相近的情况下,将具有2000个任务的多任务优化问题的求解时间从11小时减少到了0.4小时。