Modeling distributed coevolution : NKP on a cluster
Kun Chen · The University of Queensland · 2005
One of the key topics in the area of computer science is the research of so callednqdifficult-to-solveq or qhardq problems. These problems always have complicated structures andnlarge numbers of possible solutions, none of which is obviously the right one. During the last twonor three decades, evolutionary and coevolutionary approaches have been deeply applied to thenresearch of these problems.nnnnnnnnnnn The thesis proposes a coevolutionary approach that is basically based on the research ofnKauffman's patches theory. The approach could be described like this: Applies a downsizingnprocedure to a centralised problem by dividing it into decentralised patches that coevolve withneach other after the division. The thesis is NOT written trying to prove that qhardq problems couldnbe solved or optimised through this approach, but to study how this approach is efficiently appliedninto the search of approximate or as good as possible solutions to those qhardq problems underncertain conditions. The main object of this research is to build an experimental model, called thenNKPnet Model, to simulate the procedure of this coevolutionary approach and study how itnimpacts on given problems.nnnnnnnnnn n Current researches normally built their experimental models on uni-processor computer systemsnon which the poor efficiencycost resulting from the low running speed and high construction costnsignificantly limits the further research. In this research, I aim to construct an all-newnmathematical model on a distributed computer system, called the NKPnet model. The scalabilitynof number and scale in the framework assist the model to efficiently address the problems withnincreasing conflicts and difficulties.nnnnnnnnnnn n The simulations generating on the NKPnet model are implemented through parallelncoevolutionary algorithms. The designation of the algorithm for the research and the performancenof the implementation are the central topics in this thesis. In the algorithm, the structure ofnqRandom Interactionsq is brought forward to replace the structure of qNearest Interactionsqnadopted in previous research. During the implementation, various parameters of the model arenadjusted and for optimal performance and effectiveness of the model. In the future, the NKPnetnmodel expects to be developed as a multi-functional and flexible system platform on whichnresearchers could explore further studies.n