For many real-world applications of evolutionary computation, the fitness function is obscured by random noise. This interferes with the evaluation and selection processes and adversely affects the performance of the algorithm. Noise can be effectively eliminated by averaging a large number of fitness samples for each candidate, but the number of samples used per candidate (the resampling rate) required to achieve this is usually prohibitively large and time-consuming. Hence there is a practical need for algorithms that handle noise without eliminating it. Moreover, the amount of noise (noise strength and distribution) may vary throughout the search space, further complicating matters. We study noisy problems for which the noise strength varies throughout the search space. Such problems have generally been ignored by previous work, which has instead generally focussed on the specific case where the noise strength is the same at all points in the search domain. However, this need not be the case, and indeed this assumption is false for many applications. For example, in games of chance such as Poker, some strategies may be more conservative than others and therefore less affected by the inherent noise of the game. This thesis makes three significant contributions in the field of noisy fitness functions: We present the concept of dynamic resampling. Dynamic resampling is a technique that varies the resampling rate based on the noise strength and fitness for each candidate individually. This technique is designed to exploit the variation in noise strength and fitness to yield a more efficient algorithm. We present several dynamic resampling algorithms and give results that show that dynamic resampling can perform significantly better than the standard resampling technique that is usually used by the optimisation community, and that dynamic resampling algorithms that vary their resampling rates based on both noise strength and fitness can perform better than algorithms that vary their resampling rate based on only one of the above. We study a specific class of noisy fitness functions for which we counterintuitively find that it is better to use a higher resampling rate in regions of lower noise strength, and vice versa. We investigate how the evolutionary search operates on such problems, explain why this is the case, and present a hypothesis (with supporting evidence) for classifying such problems. We present an adaptive engine that automatically tunes the noise compensation parameters of the search during the run, thereby eliminating the need for the user to choose these parameters ahead of time. This means that our techniques can be readily applied to real-world problems without requiring the user to have specialised domain knowledge of the problem that they wish to solve. These three major contributions present a significant addition to the body of knowledge for noisy fitness functions. Indeed, this thesis is the first work specifically to examine the implications of noise strength that varies throughout the search domain for a variety of noise landscapes, and thus starts to fill a large void in the literature on noisy fitness functions.

Na última década diversos algoritmos baseados em busca foram desenvolvidos para a geração de níveis em diferentes tipos de jogos. O espaço de busca para geração de níveis geralmente possui restrições, uma vez que a mecânica de um jogo define regras de factibilidade para os níveis. Em alguns métodos, a avaliação de factibilidade requer uma simulação com um agente inteligente que controla o jogo. Esse processo de avaliação geralmente possui ruído, causado por componentes aleatórios no simulador ou na estratégia do agente. Diversos trabalhos têm utilizado simulação como forma de avaliação de conteúdo, no entanto, nenhum deles discutiu profundamente a presença de ruído neste tipo de abordagem. Assim, esse trabalho apresenta um algoritmo genético capaz de gerar níveis factíveis que são avaliados por um agente inteligente em uma simulação ruidosa. O algoritmo foi aplicado a jogos de quebra-cabeças baseados em física com a mecânica do Angry Birds. Uma representação dos níveis em forma de indivíduos é introduzida, a qual permite que o algoritmo genético os evolua com características diferenciadas. O ruído na função de aptidão é tratado por uma nova abordagem, baseada em uma sistema de cache, que auxilia o algoritmo genético a encontrar boas soluções candidatas. Três conjuntos de experimentos foram realizados para avaliar o algoritmo. O primeiro compara o método de cache proposto com outros métodos de redução de ruído da literatura. O segundo mede a expressividade do algoritmo genético considerando as características estruturais dos níveis gerados. O último avalia os níveis gerados considerando aspectos de design (como dificuldade, imersão e diversão), os quais são medidos por meio de questionários respondidos por jogadores humanos via Internet. Os resultados mostraram que o algoritmo genético foi capaz de gerar níveis distintos que são tão imersíveis quanto níveis produzidos manualmente. Além disso, a abordagem de cache lidou apropriadamente com o ruído nos cálculos de aptidão, permitindo uma correta evolução elitista. / In the last decade several search-based algorithms have been developed for generating levels in different types of games. The search space for level generation is typically constrained once the game mechanics define feasibility rules for the levels. In some methods, evaluating level feasibility requires a simulation with an intelligent agent which plays the game. This evaluation process usually has noise, caused by random components in the simulator or in the agent strategy. Several works have used a simulation for content evaluation, however, none of them have deeply discussed the presence of noise in this kind of approach. Thus, this paper presents a genetic algorithm capable of generating feasible levels that are evaluated by an intelligent agent in a noisy simulation. The algorithm was applied to physics-based puzzle games with the Angry Birds mechanics. A level representation in the form of individuals is introduced, which allows the genetic algorithm to evolve them with distinct characteristics. The fitness function noise is handled by a new approach, based on a cache system, which helps the genetic algorithm finding good candidate solutions. Three sets of experiments were conducted to evaluate the algorithm. The first one compares the proposed cache approach with other noise reduction methods of the literature. The second one measures the expressivity of the genetic algorithm considering the structural characteristics of the levels. The last one evaluates design aspects (such as difficulty, immersion and fun) of the generated levels using questionnaires answered by human players via Internet. Results showed the genetic algorithm was capable of generating distinct levels that are as immersive as levels manually designed. Moreover, the cache approach handled properly the noise in the fitness calculations, allowing a correct elitist evolution.

Na última década diversos algoritmos baseados em busca foram desenvolvidos para a geração de níveis em diferentes tipos de jogos. O espaço de busca para geração de níveis geralmente possui restrições, uma vez que a mecânica de um jogo define regras de factibilidade para os níveis. Em alguns métodos, a avaliação de factibilidade requer uma simulação com um agente inteligente que controla o jogo. Esse processo de avaliação geralmente possui ruído, causado por componentes aleatórios no simulador ou na estratégia do agente. Diversos trabalhos têm utilizado simulação como forma de avaliação de conteúdo, no entanto, nenhum deles discutiu profundamente a presença de ruído neste tipo de abordagem. Assim, esse trabalho apresenta um algoritmo genético capaz de gerar níveis factíveis que são avaliados por um agente inteligente em uma simulação ruidosa. O algoritmo foi aplicado a jogos de quebra-cabeças baseados em física com a mecânica do Angry Birds. Uma representação dos níveis em forma de indivíduos é introduzida, a qual permite que o algoritmo genético os evolua com características diferenciadas. O ruído na função de aptidão é tratado por uma nova abordagem, baseada em uma sistema de cache, que auxilia o algoritmo genético a encontrar boas soluções candidatas. Três conjuntos de experimentos foram realizados para avaliar o algoritmo. O primeiro compara o método de cache proposto com outros métodos de redução de ruído da literatura. O segundo mede a expressividade do algoritmo genético considerando as características estruturais dos níveis gerados. O último avalia os níveis gerados considerando aspectos de design (como dificuldade, imersão e diversão), os quais são medidos por meio de questionários respondidos por jogadores humanos via Internet. Os resultados mostraram que o algoritmo genético foi capaz de gerar níveis distintos que são tão imersíveis quanto níveis produzidos manualmente. Além disso, a abordagem de cache lidou apropriadamente com o ruído nos cálculos de aptidão, permitindo uma correta evolução elitista. / In the last decade several search-based algorithms have been developed for generating levels in different types of games. The search space for level generation is typically constrained once the game mechanics define feasibility rules for the levels. In some methods, evaluating level feasibility requires a simulation with an intelligent agent which plays the game. This evaluation process usually has noise, caused by random components in the simulator or in the agent strategy. Several works have used a simulation for content evaluation, however, none of them have deeply discussed the presence of noise in this kind of approach. Thus, this paper presents a genetic algorithm capable of generating feasible levels that are evaluated by an intelligent agent in a noisy simulation. The algorithm was applied to physics-based puzzle games with the Angry Birds mechanics. A level representation in the form of individuals is introduced, which allows the genetic algorithm to evolve them with distinct characteristics. The fitness function noise is handled by a new approach, based on a cache system, which helps the genetic algorithm finding good candidate solutions. Three sets of experiments were conducted to evaluate the algorithm. The first one compares the proposed cache approach with other noise reduction methods of the literature. The second one measures the expressivity of the genetic algorithm considering the structural characteristics of the levels. The last one evaluates design aspects (such as difficulty, immersion and fun) of the generated levels using questionnaires answered by human players via Internet. Results showed the genetic algorithm was capable of generating distinct levels that are as immersive as levels manually designed. Moreover, the cache approach handled properly the noise in the fitness calculations, allowing a correct elitist evolution.