Abstract
This paper exposes a research of the NP-hard Maximally Balanced Connected Partition problem (MBCP). The proposed solution comprises of a genetic algorithm (GA) that uses: binary representation, fine-grained tournament selection, one-point crossover, simple mutation with frozen genes and caching technique. In cases of unconnected partitions, penalty functions are successfully applied in order to obtain the feasible individuals. The effectiveness of presented approach is demonstrated on the grid graph instances and on random instances with up to 300 vertices and 2 000 edges.
Keywords
Cite this article
@article{cai-1669,
author = {Brankica Djurić and Jozef Kratica and Dušan Tošić and Vladimir Filipović},
title = {Solving the Maximally Balanced Connected Partition Problem in Graphs by Using Genetic Algorithm},
journal = {Computing and Informatics},
volume = {27},
number = {3},
pages = {341--354},
year = {2008},
issn = {1335-9150},
url = {https://cai.type.sk/content/2008/3/solving-the-maximally-balanced-connected-partition-problem-in-graphs-by-using-genetic-algorithm/}
}
TY - JOUR AU - Brankica Djurić AU - Jozef Kratica AU - Dušan Tošić AU - Vladimir Filipović TI - Solving the Maximally Balanced Connected Partition Problem in Graphs by Using Genetic Algorithm JO - Computing and Informatics VL - 27 IS - 3 SP - 341 EP - 354 PY - 2008 SN - 1335-9150 UR - https://cai.type.sk/content/2008/3/solving-the-maximally-balanced-connected-partition-problem-in-graphs-by-using-genetic-algorithm/ KW - Balanced partitions KW - evolutionary computation KW - metaheuristics KW - combinatorial optimization. ER -
Djurić, B., Kratica, J., Tošić, D., & Filipović, V. (2008). Solving the Maximally Balanced Connected Partition Problem in Graphs by Using Genetic Algorithm. Computing and Informatics, 27(3), 341–354. https://cai.type.sk/content/2008/3/solving-the-maximally-balanced-connected-partition-problem-in-graphs-by-using-genetic-algorithm/