Transmission function models of finite population genetic algorithms
Infinite population models show a deterministic behaviour. Genetic algorithms with finite populations behave non-deterministicly. For small population sizes, the results obtained with these models differ strongly from the results predicted by the infinite population model. When the population size is increased towards infinity, a convergence to the results predicted by the infinite population models is observed. In real GA's random decisions are used during the run of the GA. These random decisions can lead to a behaviour that results in a deviation of the GA from the expected path of evolution. In this report four sources of non-determinism are identified. Finite population models are generated by explicitly modelling two of these sources. When comparing the results to runs of actual genetic algorithms, similar results are obtained. Hence, this model shows what are the most important sources of non-determinism in the GA for the problem at hand.
|Miscellaneous (acm F.2.m), Optimization (acm G.1.6), Problem Solving, Control Methods, and Search (acm I.2.8)|
|Learning and adaptive systems (msc 68T05), Problem solving (heuristics, search strategies, etc.) (msc 68T20)|
|Software (theme 1), Logistics (theme 3), Energy (theme 4)|
|Software Engineering [SEN]|
|Organisation||Intelligent and autonomous systems|
van Kemenade, C.H.M, Kok, J.N, La Poutré, J.A, & Thierens, D. (1998). Transmission function models of finite population genetic algorithms. Software Engineering [SEN]. CWI.