Two metaheuristics for solving the connected multidimensional maximum bisection problem
Zoran Maksimović 1 - Personal Name
Jozef Kratica 2 - Personal Name
Aleksandar Savić 3 - Personal Name
In this paper, a connected multidimensional maximum bisection problem is considered. This problem is a generalization of a standard NP-hard maximum bisection problem, where each graph edge has a vector of weights and induced subgraphs must be connected. We propose two metaheuristic approaches, a genetic algorithm (GA) and an electromagnetism-like metaheuristic (EM). The GA uses modified integer encoding of individuals, which enhances
the search process and enables usage of standard genetic operators. The EM, besides standard attraction–repulsion mechanism, is extended with a scaling procedure, which additionally moves EM points closer to local optima. A specially constructed penalty function, used for both approaches,
is performed as a practical technique for temporarily including infeasible solutions into the search process. Both GA and EM use the same local search procedure based on 1swap improvements. Computational results were obtained on instances from literature with up to 500 vertices and 60,000
edges. EM reaches all known optimal solutions on smallsize instances, while GA reaches all known optimal solutions except for one case. Both proposed methods give results on medium-size and large-scale instances, which are out of reach for exact methods.
the search process and enables usage of standard genetic operators. The EM, besides standard attraction–repulsion mechanism, is extended with a scaling procedure, which additionally moves EM points closer to local optima. A specially constructed penalty function, used for both approaches,
is performed as a practical technique for temporarily including infeasible solutions into the search process. Both GA and EM use the same local search procedure based on 1swap improvements. Computational results were obtained on instances from literature with up to 500 vertices and 60,000
edges. EM reaches all known optimal solutions on smallsize instances, while GA reaches all known optimal solutions except for one case. Both proposed methods give results on medium-size and large-scale instances, which are out of reach for exact methods.
Availability
| EB00000003022K | Available |
Detail Information
Series Title
-
Call Number
-
Publisher
: ,
Collation
-
Language
ISBN/ISSN
-
Classification
NONE
Detail Information
Content Type
E-Jurnal
Media Type
-
Carrier Type
-
Edition
-
Subject(s)
Genetic algorithms
Electromagnetism-like approach
Evolutionary computation
Graph bisection
Combinatorial optimization
Specific Detail Info
-
Statement of Responsibility
-
No other version available
File Attachment
