Performance Analysis of the (1+1) Evolutionary Algorithm for the Multiprocessor Scheduling Problem
Performance Analysis of the (1+1) Evolutionary Algorithm for the Multiprocessor Scheduling Problem
复制标题
DOI：
10.1007/s00453-014-9898-0
复制
发表时间：
2015-09
期刊：
影响因子：
1.1
通讯作者：
Yuren Zhou;Jun Zhang;Yong Wang
中科院分区：
文献类型：
--
作者：
Yuren Zhou;Jun Zhang;Yong Wang
近年来，离散优化问题的进化算法理论研究取得了长足的进展。然而，结果的性能分析的EA NP难问题是罕见的。本文对进化算法在NP难多处理机调度问题上的应用有了理论上的认识。给出了多处理机调度问题（1+1）进化算法的最坏情况界，并给出了最坏情况的例子。证明了（1+1）EA算法在求解$Q2\mid\mid C_max $$Q2最大可达Cmax问题时，在期望时间$$O（n^2）$$O（n2）内达到了$$\frac{1+\sqrt{5}}{2}$$1+52的逼近比。最后，对三个多处理机调度问题的实例进行了理论分析，结果表明进化算法在这些实例上的性能优于局部搜索算法。
In recent years, there has been considerable progress in the theoretical study of evolutionary algorithms (EAs) for discrete optimization problems. However, results on the performance analysis of EAs for NP-hard problems are rare. This paper contributes a theoretical understanding of EAs on the NP-hard multiprocessor scheduling problem. The worst-case bound on the (1+1)EA for the multiprocessor scheduling problem and a worst-case example are presented. It is proved that the (1+1)EA on $$Q2\mid \mid C_\mathrm{max}$$Q2∣∣Cmax problem achieves an approximation ratio of $$\frac{1+\sqrt{5}}{2}$$1+52 in expected time $$O(n^2)$$O(n2). Finally, the theoretical analysis on three selected instances of the multiprocessor scheduling problem shows that EAs outperform local search algorithms on these instances.