Complex network analysis of evolutionary algorithms applied to combinatorial optimisation problem

Abstract

This research analyses the development of a complex network in an evolutionary algorithm (EA). The main aim is to evaluate if a complex network is generated in an EA, and how the population can be evaluated when the objective is to optimise an NP-hard combinatorial optimisation problem. The population is evaluated as a complex network over a number of generations, and different attributes such as adjacency graph, minimal cut, degree centrality, closeness centrality, betweenness centrality, k-Clique, k-Club, k-Clan and community graph plots are analysed. From the results, it can be concluded that an EA population does behave like a complex network, and therefore can be analysed as such, in order to obtain information about population development. © Springer International Publishing Switzerland 2014.