期刊
IEEE TRANSACTIONS ON CYBERNETICS
卷 45, 期 5, 页码 1040-1053出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TCYB.2014.2343966
关键词
Estimation of distribution algorithm; evolutionary algorithms; local search; maximum balanced biclique problem (MBBP); structure mutation
类别
资金
- National Natural Science Foundation of China [61071024, 61331015, 61329302, 61175065, 61203292, 61311130140]
- European Union 7th Framework Program [247619, 257906]
- National Natural Science Foundation of Anhui Province [1108085J16]
- EPSRC [EP/I010297/1]
- Royal Society Wolfson Research Merit Award
- One Thousand Young Talents Program
- EPSRC [EP/I010297/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/I010297/1] Funding Source: researchfish
The maximum balanced biclique problem (MBBP), an NP-hard combinatorial optimization problem, has been attracting more attention in recent years. Existing node-deletion-based algorithms usually fail to find high-quality solutions due to their easy stagnation in local optima, especially when the scale of the problem grows large. In this paper, a new algorithm for the MBBP, evolutionary algorithm with structure mutation (EA/SM), is proposed. In the EA/SM framework, local search complemented with a repair-assisted restart process is adopted. A new mutation operator, SM, is proposed to enhance the exploration during the local search process. The SM can change the structure of solutions dynamically while keeping their size (fitness) and the feasibility unchanged. It implements a kind of large mutation in the structure space of MBBP to help the algorithm escape from local optima. An MBBP-specific local search operator is designed to improve the quality of solutions efficiently; besides, a new repair-assisted restart process is introduced, in which the Marchiori's heuristic repair is modified to repair every new solution reinitialized by an estimation of distribution algorithm (EDA)-like process. The proposed algorithm is evaluated on a large set of benchmark graphs with various scales and densities. Experimental results show that: 1) EA/SM produces significantly better results than the state-of-the-art heuristic algorithms; 2) it also outperforms a repair-based EDA and a repair-based genetic algorithm on all benchmark graphs; and 3) the advantages of EA/SM are mainly due to the introduction of the new SM operator and the new repair-assisted restart process.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据