A new evolutionary algorithm with structure mutation for the maximum balanced biclique problem

Bo YUAN, Bin LI, Huanhuan CHEN, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

19 Citations (Scopus)

Abstract

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. © 2013 IEEE.
Original languageEnglish
Article number6878426
Pages (from-to)1054-1067
Number of pages14
JournalIEEE Transactions on Cybernetics
Volume45
Issue number5
Early online date14 Aug 2014
DOIs
Publication statusPublished - May 2015
Externally publishedYes

Keywords

  • Estimation of distribution algorithm
  • evolutionary algorithms
  • local search
  • maximum balanced biclique problem (MBBP)
  • structure mutation

Fingerprint

Dive into the research topics of 'A new evolutionary algorithm with structure mutation for the maximum balanced biclique problem'. Together they form a unique fingerprint.

Cite this