Takeover time in parallel populations with migration

Abstract

The term takeover time regarding selection methods used in evolutionary algorithms denotes the (expected) number of iterations of the selection method until the entire population consists of copies of the best individual, provided that the initial population consists of a single copy of the best individual whereas the remaining individuals are worse. Here, this notion is extended to parallel subpopulations that exchange individuals according to some migration paths modelled by a directed graph. We develop upper bounds for migrations path along uni- and bidirectial rings as well as arbitrary connected graphs where each vertex is reachable from every other vertex.