一种求解NP-难问题的并行协同大规模差分进化算法

摘要

NP-难问题在实际生活中随处可见,随着问题规模的增大,维度的升高,优化问题的特性变得越来越复杂.为了有效解决大规模优化问题,新型大规模优化算法亟待提出.首先提出了一种求解NP-难问题的并行协同大规模差分进化算法,将高维度优化问题降解为多个低维度的子问题,进而能够获得更加准确的分组;其次,针对获得的维度分组,独立优化每个子问题,基于获得的维度分组,大大加快算法的运行速度.结果表明,与串行进化算法相比,并行协同差分进化算法能够获得更好的性能,同时随着核数的增加,并行协同进化算法的加速呈近线性增加,而其获得的解的质量却在下降,加速比的提高与解的质量提高存在着冲突.