Journal
IEEE TRANSACTIONS ON CYBERNETICS
Volume 45, Issue 5, Pages 1040-1053Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TCYB.2014.2343966
Keywords
Estimation of distribution algorithm; evolutionary algorithms; local search; maximum balanced biclique problem (MBBP); structure mutation
Categories
Funding
- 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
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available