A Study of Fitness Gains in Evolving Finite State Machines
Among the wide variety of evolutionary computing models, Finite State Machines (FSMs) have several attractions for fundamental research. They are easy to understand in concept and can be visualised clearly in simple cases. They have a ready fitness criterion through their relationship with Regular Languages. They have also been shown to be tractably evolvable, even up to exhibiting evidence of open-ended evolution in specific scenarios. In addition to theoretical attraction, they also have industrial applications, as a paradigm of both automated and user-initiated control. Improving the understanding of the factors affecting FSM evolution has relevance to both computer science and practical optimisation of control. We investigate an evolutionary scenario of FSMs adapting to recognise one of a family of Regular Languages by categorising positive and negative samples, while also being under a counteracting selection pressure that favours fewer states. The results appear to indicate that longer strings provided as samples reduce the speed of fitness gain, when fitness is measured against a fixed number of sample strings. We draw the inference that additional information from longer strings is not sufficient to compensate for sparser coverage of the combinatorial space of positive and negative sample strings.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Inferring Fitness in Finite Populations with Moran-like dynamics
Biological fitness is not an observable quantity and must be inferred from population dynamics. Bayesian inference applied to the Moran process and variants yields a robust inference method that can infer fitness in popu…
Bayesian InferenceEmerging Diversity in a Population of Evolving Intransitive Dice
Exploiting the mathematical curiosity of intransitive dice, we present a simple theoretical model for co-evolution that captures scales ranging from the genome of the individual to the system-wide emergence of species di…
DiversityEvolving Evaluation Functions for Collectible Card Game AI
In this work, we presented a study regarding two important aspects of evolving feature-based game evaluation functions: the choice of genome representation and the choice of opponent used to test the model. We compared t…
Card GamesImpact of complex spatial population structure on early and long-term adaptation in rugged fitness landscapes
We investigate the exploration of rugged fitness landscapes by spatially structured populations with demes on the nodes of a graph, connected by migrations. In the rare migration regime, we find that finite structures ca…
Solution and Fitness Evolution (SAFE): A Study of Multiobjective Problems
We have recently presented SAFE -- Solution And Fitness Evolution -- a commensalistic coevolutionary algorithm that maintains two coevolving populations: a population of candidate solutions and a population of candidate …