Improving search in geometric semantic genetic programming
Luiz Otávio V. B. Oliveira · Americanae (AECID Library) · 2016
Nos últimos anos diversos trabalhos surgiram na tentativa de introduzir informação semântica no processo evolutivo da Programação Genética (PG). Em particular, a PG Semântica Geométrica (PGSG) foi proposta como um método que atua sobre a sintaxe dos programas pais, produzindo descendentes respeitando algum critério semântico.Nesta tese, focamos nas questões em aberto existentes na PGSG e métodos relacionados, aplicados à regressão simbólica. Apresentamos a definição de semântica adotada nesta tese e uma visão geral dos métodos que exploram a semântica enquadrados nesta definição. Em seguida, apresentamos e atacamos questões relativas à PGSG. Em primeiro lugar, investigamos o impacto do cruzamento semântico geométrico com diferentes funções de distância sobre a busca, e a possibilidade de ajustar de forma ótima seus coeficientes em vez de escolhê-los aleatoriamente. Os resultados mostram que a distância de Manhattan tem melhor desempenho em termos de erro no teste, e que a optimização dos coeficientes do cruzamento não conseguem melhorar significativamente a busca.Também apresentamos a Regressão Sequencial Simbólica (RSS), uma tentativa de controlar o crescimento exponencial do tamanho dos indivíduos causado pela utilização do cruzamento semântico geométrico. Depois de gerar uma função subótima com PG canônica, a RSS aproxima os erros de saída através de outra função, em uma iteração posterior, e concatena-as com o operador de cruzamento. Uma análise experimental mostra que a RSS tem um desempenho semelhante à PGSG, gerando soluções menores. Em adição, esta tese explora um arcabouço heurístico, chamado de dispersão geométrica (DG), para a construção de operadores que movem os indivíduos para áreas menos densas do espaço de busca, ao redor do vetor de saída alvo. Os resultados experimentais indicam que os operadores de dispersão geométrica podem melhorar a busca e espalhar as soluções ao redor da solução alvo. Por último, apresentamos um estudo do impacto da seleção de instâncias de treinamento, a fim de reduzir a dimensionalidade do espaço semântico. Duas abordagens são consideradas: (i) aplicar métodos de seleção de instâncias como uma etapa de pré-processamento, antes que os pontos de treinamento sejam apresentados à PGSG; (ii) incorporar a seleção de instâncias na evolução realizada pela PGSG. A análise experimental mostra que o desempenho da PGSG melhora com a redução de instâncias durante a evolução.