Authors: Maksimović, Zoran
Kratica, Jozef 
Savić, Aleksandar
Matić, Dragan
Title: Solving the multidimensional maximum bisection problem by a genetic algorithm and variable neighborhood search
Journal: Journal of Multiple-Valued Logic and Soft Computing
Volume: 31
Issue: 4
First page: 323
Last page: 358
Issue Date: 1-Jan-2018
Rank: M22
ISSN: 1542-3980
In this paper, we consider the application of the two metaheuristic approaches: a Genetic Algorithm (GA) and a Variable Neighborhood Search (VNS), on an NP-hard optimization problem: Multi-dimensional Maximum Bisection Problem (MDMBP). MDMBP is a generalization of the Maximum Bisection Problem (MBP), where each graph edge instead of having a singular weight, has a vector of weights. The GA is constructed on a modified integer encoding of individuals, where only the feasible solutions are generated, which allows the application of standard genetic operators. A suitable system of neighborhoods based on changing the component for an increasing number of vertices is implemented in the proposed VNS. Both GA and VNS use two types of local search procedures, both based on swapping the components of pairs of vertices. Our computational results were obtained on MDMBP instances in the literature with up to 1000 vertices and 350000 edges, and the well-known MBP G-set instances with up to 20000 vertices and 41459 edges. The obtained results are statistically analysed and compared with the results of the existing methods for solving MDMBP and MBP.
Keywords: Genetic algorithms | Graph bisection | Multidimensional graph bisection | Variable neighborhood search
Publisher: Old City Publishing
Project: Mathematical Modelas and Optimization Methods on Large-Scale Systems 
Graph theory and mathematical programming with applications in chemistry and computer science 
Ministry of Science and Technology of Republika Srpska, Grant No. 0830905

Show full item record

Page view(s)

checked on May 10, 2024

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.