Dal Piccol Sotto, Leo Francoso [UNIFESP]
de Melo, Vinicius Veloso [UNIFESP]
Basgalupp, Marcio Porto [UNIFESP]
MetadataShow full item record
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 regionssuch 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.
CitationKnowledge And Information Systems. London, v. 52, n. 2, p. 445-465, 2017.
KeywordsAnt Trail problem
Linear genetic programming
Automatic design of algorithms
SponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
Fundação de Amparo a Pesquisa do Estado de São Paulo (FAPESP)
- ICT - Artigos