ISSN : 2319-7323

INTERNATIONAL JOURNAL OF COMPUTER SCIENCE ENGINEERING

ABSTRACT

Title	:	Comparing performance ofparallel genetic algorithm and niching methods on partitioning connected, weighted graph
Authors	:	S. M. Mansourfar, FardinEsmaeeliSangari, MehrdadNabahat
Keywords	:	partitioning problem; genetic algorithm; graphs; GPBM
Issue Date	:	May 2014
Abstract	:	In this paper, partitioning problem on graphs will be studied, whose decision problem is known to be NP-complete. Graphs used in this paper are connected and weighed. We have reviewed parallel genetic algorithm and niching methods, focusing on basic and important parameters; moreover we chose Deterministic Crowding (DC) of niching methods as main target of review. Deterministic Crowding is an implicit neighborhood technique that makes competition between parents and children of identical niche. We applied both parallel genetic algorithm and deterministic crowding on specified problem, then compared performance of these two methods. In addition, a new mutation algorithm named GPBM has been proposed. GPBM mainly focuses on balancing vertices between clusters of graph. As results showing GPBM rate have direct impact on finding better solutions. Tests applied for couple of times with different values so that obtained results be more mature. Some important characteristics of genetic algorithms were also reviewed.
Page(s)	:	160-167
ISSN	:	2319-7323
Source	:	Vol. 3, No.3