A route to the evolution of cooperation: investigations of multilevel selection in evolutionary computation

To debunk the myth of how cooperation can emerge through the competition induced by Evolutionary Computation, this dissertation, inspired by nature, presents a new route to reach the evolution of cooperation in computational settings. The inspiration is drawn from multilevel selection theory in biology. This theory is an extension of the well-known group selection theory, which explains the evolution of cooperation by considering selection taking place both within and between groups. Although within-group selection encourages individuals to compete, between-group selection posits competition between groups, which leads to cooperation within groups. The concept of individuals and group are relative: groups can be regarded as individuals on a higher level; therefore, multilevel selection claims that selection should take place on every level of this hierarchical structure. -- Indeed, our biological world is hierarchically organized. However, most multilevel selection models in the literature take this hierarchical structure as given. The biological hierarchy, however, has developed gradually: simpler, smaller components appear before more complex, composite systems. Therefore, the new computational multilevel selection model we propose defines a bottom-up process, where entities on new levels are created with the help of a cooperation operator under the guidance of predefined reaction rules. Hence, new entities are able to possess different genotypic or phenotypic traits than their constituents. Evolution is performed on each level to optimize the traits of the entities on that level. Selection pressure from higher levels forces entities on lower levels to cooperate. Between-level selection determines which level to select and controls the growth of the hierarchy. As a result of these features, the model shows an emergent property: the appropriate structure required reaching a predefined cooperative goal, i.e., the number of individuals and the role each individual playing in the cooperation, are automatically developed during evolution. -- After introducing the model, we first experimentally evaluate the feasibility of our proposed multilevel selection model in achieving the evolution of cooperation on the N-player Prisoner's Dilemma (NPD) game. We further explore the transition ability of our model by using division of labor as an example. Our findings reveal that cooperation emerges and persists more easily in this model than in other models from the literature. In fact, the between-group selection is strong enough to ensure groups with all required skills emerging from a population of independent individuals, no matter whether the skills are equally rewarded or not. Next, we validate the cooperation and problem decomposition capability of this model in solving decomposable problems. Two case studies are performed on string covering problems and multi-class classification problems, respectively. The experiment results show that our model evolves faster and finds more accurate solutions than other cooperative evolutionary algorithms. More importantly, problem decomposition emerges through evolution without human intervention. -- The thesis concludes with a discussion of achievements and further work building on our results