文章基本信息

标题：Solving the Maximally Balanced Connected Partition Problem in Graphs by Using Genetic
本地全文：下载
作者：Djurić, Brankica ; Kratica, Jozef ; Tošić, Dušan 等
期刊名称：COMPUTING AND INFORMATICS
印刷版ISSN：1335-9150
出版年度：2008
卷号：27
期号：3
页码：341-354
语种：English
出版社：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.
关键词：Balanced partitions; evolutionary computation; metaheuristics; combinatorial optimization