Sexual selection through mate choice in evolutionary computation

Abstract

Evolutionary Algorithms are valuable optimization tools on a wide range of contexts and with applicability on an increasing number of industries. Their canonical layout is a well justified metaphor of Natural Selection. Overall, it is expected that matching high fitness with proportionate reproductive opportunities will guide the population through the search space, towards areas worth exploiting for possibly optimal solutions. Rewarding competitiveness can bring direct benefits to search efforts. However, on a broader perspective and depending on the characteristics of the target problem, the approach may not be the most appropriate. In multimodal, multidmensional, rough search landscapes, other strategies are worth exploring in hopes of greater benefit to the global search process. This thesis introduces Sexual Selection through Mate Choice as a self-adaptive alternative for the evaluation of mating candidates. The approach looks away from immediate fitness gains and introduces a degree of freedom of choice when selecting mating partners. A much pursued higher evolutionary autonomy is achieved, by allowing individuals to encode and make use of their own evaluation functions, as part of the genotype. This autonomous choice can introduce selective forces that diverge from Natural Selection, potentially producing unorthodox search patterns. Overall, this will impact and benefit the global search effort, despite moving away from objective oriented selection and introducing a degree of open-ended evolution. Still, synergies between Sexual and Natural Selection are relevant. It is proposed that Mate Choice models follow three assumptions: i) individuals must choose who they mate with based on their perception of others and their own mating preferences; ii) mating preferences are subject to descent with modification through inheritance like any other trait; iii) Mate Choice introduces its own selection pressure while being itself subject to pressure. This thesis introduces a framework following these assumptions. Furthermore, two approaches based on Genetic Programming representations of mating preferences, each following its own additional and specific assumptions, are studied. The first approach suggests representing preferences as ideal mating partners to whom candidates can be measured against (PIMP). The second approach suggests the representation of a contextualized mate evaluation function, coupling perception, preferences, and interactions between signals (CMP-GP). It's hypothesized that Evolutionary Algorithms modeling proper Mate Choice mechanisms can improve on optimization by adopting a widening perspective on search and the relaxation of objectives. This hypothesis is addressed both on PIMP and CMP-GP and regarding Mate Choice in general. In order to methodically explore the subject, a number of research questions are introduced, focusing on performance indicators but also on empirically demonstrating and validating the behavioral changes imposed by Mate Choice. Particularly, these research questions focus on aspects of selection and perception, and on the effects that Mate Choice has on populations. This thesis makes several contributions towards integrating and understanding the role of Mate Choice in Evolutionary Computation. It covers theory on the subject, focusing on historical milestones and a modern synthesis, and introduces conditions, principles, and impacts that are associated with Mate Choice. The modeling of Mate Choice as genetic models and its transition to optimization operators is also covered, as well as impacts on search efforts. Furthermore, the state-of-the-art is compiled in comprehensive categories. Supported by the theoretical discussion, this thesis introduces a general framework and two distinct designs, applied to a set of 52 Symbolic Regression instances. An analysis of performance and behavior follows, supported by a number of metrics that are introduced and focus on the different research questions. This analysis is then extended to include impacts of mutation in combination with Mate Choice. Finally, conclusions are drawn on research questions and the proposed hypothesis is confirmed under the discussed setup and assumptions.

A Computação Evolucionaria agrega um conjunto de algoritmos com aplicação em múltiplos contextos e num crescente número de indústrias. No seu formato canónico, os Algoritmos Evolucionários são uma metáfora bem justificada de Selecção Natural. Em suma, é espectável que a combinação entre alto desempenho e um número proporcional de oportunidades de reprodução conduza a população através do espaço de procura e em direcção a zonas onde a procura de soluções potencialmente óptimas seja mais produtivo. Nesta perspectiva, compensar directamente indivíduos altamente competitivos pode trazer benefícios directos ao esforço de procura. No entanto, pode ser argumentado que numa perspectiva mais alargada e dependendo das características do problema alvo, a abordagem pode não ser a mais apropriada. Em problemas multidimensionais, multimodais, cujo espaço de procura seja altamente rugoso, é relevante explorar outras abordagens capazes de potenciar o processo de procura.

Esta tese apresenta Selecção Sexual através da Escolha de Parceiro como um método auto-adaptativo alternativo, para a avaliação de candidatos para reprodução. A abordagem afasta-se dos ganhos imediatos resultantes da avaliação por desempenho e introduz um grau de liberdade de escolha no processo de selecção de parceiros. Ao permitir a cada indivíduo o uso da sua própria função de avaliação, representada no seu genótipo, é alcançada uma maior autonomia evolucionária capaz de introduzir forças divergentes daquela imposta pela Selecção Natural. Como resultado, o processo evolucionário é mais aberto e afasta-se da selecção baseada em aproximação a um ou mais objectivos. O padrão de evolução resultante é fora do convencional e benéfico para o processo global de procura, muito devido às sinergias entre as forças de Selecção Natural e Selecção Sexual. É proposto que modelos de Escolha de Parceiro sigam as seguintes regras: i) cada indivíduo deve escolher o seu parceiro de reprodução baseado na sua própria percepção dos outros e nas suas próprias preferências; ii) as preferências de escolha deverão estar sujeitas a descendência com modificação, de forma semelhante a qualquer outra característica; iii) Escolha de Parceiro introduz a sua própria pressão de selecção e está também sujeita pressão. Esta tese apresenta uma estrutura genérica para um algoritmo que modela este processo e ainda duas abordagens distintas para a representação de preferências usando Programação Genética, cada uma seguindo as suas próprias regras adicionais. A primeira abordagem sugere que as preferências sejam representadas como um parceiro ideal, com o qual candidatos possam ser comparados (PIMP). A segunda abordagem sugere representar uma função que agregue percepção, preferências e interacção entre sinais num contexto de avaliação (CMP-GP).

É estudada a hipótese de que Algoritmos Evolucionários que incluam modelos de Escolha de Parceiro, adoptando assim uma perspectiva mais aberta de procura através do relaxamento de objectivos, podem trazer melhorias a processos de optimização. Este estudo abrange as abordagens PIMP e CMP-GP, abordando ainda mecanismos de Escolha de Parceiro de forma genérica. De forma a estudar o assunto metodicamente, a hipótese é desdobrada em várias questões a investigar e que se focam tanto em indicadores de desempenho como em demonstrar e validar empiricamente os comportamentos introduzidos pela Escolha de Parceiro. Estas últimas direccionam-se a impactos relacionados com selecção, percepção e efeitos a nível de população. Esta tese faz vários contributos no sentido de integrar e compreender o papel da Escolha de Parceiro na Computação Evolucionária. A teoria é amplamente discutida, incluindo macros históricos no seu estudo e uma síntese moderna, assim como princípios e impactos. A modelação de Escolha de Parceiro como um modelo genético e a sua gradual adaptação a um operador com aplicações em optimização é também discutida. O estado da arte da sua aplicação com múltiplos fins é apresentado e categorizado. Usando estas contribuições como base, esta tese apresenta então um modelo genérico de Escolha de Parceiro e duas abordagens distintas, que são aplicadas num conjunto de 52 problemas de Regressão Simbólica. Segue-se a análise dos resultados relativos a desempenho e comportamento, com o apoio de um conjunto de métricas que se focam nas diferentes questões propostas. O estudo é ainda alargado para incluir operadores e mutação e a sua interacção com Escolha de Parceiro. Por fim, são tiradas conclusões em relação às questões investigadas e a hipótese central é abordada, confirmando-se o esperado neste contexto específico.