-LGP: an improved version of linear genetic programming evaluated in the Ant Trail problem

Autor(es)

Dal Piccol Sotto, Leo Francoso ; de Melo, Vinicius Veloso ; Basgalupp, Marcio Porto

• Tipo de documento: Artigo Científico
• Fonte: KNOWLEDGE AND INFORMATION SYSTEMS; v. 52, n. 2, p. 445-465, AUG 2017.
• Citações Web of Science: 2

Resumo

The Ant Trail problem has been widely investigated as a benchmark for automatic design of algorithms. One must design the program of a virtual ant to collect all pieces of food located in different places of a map, which may have obstacles, in a predefined limit of steps. This is a challenging problem, but several evolutionary computation (EC) researchers have reported methods with good results. In this paper, we propose an EC method called -linear genetic programming (-LGP), a variation of the well-known linear genetic programming (LGP) algorithm. Starting with an LGP based only on effective macro- and micro-mutations, the -LGP proposed in this work consists in extending how the individuals are chosen for reproduction. In this model, a number () of mutations is applied to each individual, trying to explore its neighboring fitness regions; such individual might be replaced by one of its children according to different criteria. Several configurations were tested over three different trails: the Santa Fe, the Los Altos Hill, and the John Muir. Results show a very significant improvement over LGP by using this proposed variation. Also, -LGP outperformed not only LGP, but also other state-of-the-art methods from the literature. (AU)

• Processo FAPESP: 13/20606-0 - Evolução automática de árvores de comportamento para um agente inteligente
• Beneficiário: Léo Françoso Dal Piccol Sotto
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Processo FAPESP: 16/07095-5 - Desenvolvimento da técnica programação genética linear probabilística e aplicação em programação Kaizen para aprendizado de máquina supervisionado
• Beneficiário: Léo Françoso Dal Piccol Sotto
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto