Solving the Maximally Balanced Connected Partition Problem in Graphs by Using Genetic Algorithm
Brankica Djurić ; Jozef Kratica ; Dušan Tošić ; Vladimir Filipović
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
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.
Publié le : 2012-01-26
Classification:  Balanced partitions; evolutionary computation; metaheuristics; combinatorial optimization 
@article{cai253,
     author = {Brankica Djuri\'c and Jozef Kratica and Du\v san To\v si\'c and Vladimir Filipovi\'c},
     title = {Solving the Maximally Balanced Connected Partition Problem in Graphs by Using Genetic Algorithm},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai253}
}

Brankica Djurić; Jozef Kratica; Dušan Tošić; Vladimir Filipović. Solving the Maximally Balanced Connected Partition Problem in Graphs by Using Genetic Algorithm. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai253/