Ant colony systems optimization applied to BNF grammars Rule Derivation (ACORD Algorithm)

Mingo Lopez, Fernando De and Gomez Blas, Nuria and Morales Lucas, Clemencio (2020). Ant colony systems optimization applied to BNF grammars Rule Derivation (ACORD Algorithm). "Soft Computing", v. 24 ; pp. 3141-3154. ISSN 1432-7643. https://doi.org/10.1007/s00500-020-04670-9.

Description

Title: Ant colony systems optimization applied to BNF grammars Rule Derivation (ACORD Algorithm)
Author/s:
  • Mingo Lopez, Fernando De
  • Gomez Blas, Nuria
  • Morales Lucas, Clemencio
Item Type: Article
Título de Revista/Publicación: Soft Computing
Date: January 2020
ISSN: 1432-7643
Volume: 24
Subjects:
Freetext Keywords: Grammatical swarm; Ant colony optimization; Particle swarm optimization; Grammatical evolution
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (9MB)

Abstract

Ant Colony Systems have been widely employed in optimization issues primarily focused on path finding optimization, such as Travelling Salesman Problem. The main advantage lies in the choice of the edge to be explored, defined using pheromone trails. This paper proposes the use of Ant Colony Systems to explore a Backus-Naur form grammar whose elements are solutions to a given problem. Similar models, without using Ant Colonies, have been used to solve optimization problems or to automatically generate programs such as Grammatical Swarm (based on Particle Swarm Optimization) and Gramatical Evolution (based on Genetic Algorithms). This work presents the application of proposed Ant Colony Rule Derivation algorithm and benchmarks this novel approach in a well-known deceptive problem, the Santa Fe Trail. Proposed algorithm opens the way to a new branch of research in Swarm Intelligence, which until now has been almost non-existent, using ant colony algorithms to generate solutions of a given problem described by a BNF grammar with the advantage of genotype phenotype mapping, described in Grammatical Evolution. In this case, such mapping is performed based on the pheromone concentration for each production rule.The experimental results demonstrate proposed algorithm outperforms Grammatical Evolution algorithm in the Santa Fe Trail problem with higher success rates and better solutions in terms of the required steps.

Funding Projects

TypeCodeAcronymLeaderTitle
Government of SpainTRA2016-78886-C3-3-RCAVUniversidad Politécnica de Madrid - Instituto Universitario de Investigación del Automóvil (INSIA)Integración de sistemas cooperativos para vehículos autónomos en tráfico compartido: Unidad de control inteligente
Horizon 2020INEA/CEF/TRAN/M2015/1143746UnspecifiedUnspecifiedRegulation study in the adoption of the autonomous driving in the European Urban Nodes (AUTOCITS)
Horizon 20202015-EU-TM-0243-SUnspecifiedUnspecifiedAUTOCITS: Regulation study for interoperability in the adoption of autonomous driving in Urban Nodes

More information

Item ID: 68015
DC Identifier: https://oa.upm.es/68015/
OAI Identifier: oai:oa.upm.es:68015
DOI: 10.1007/s00500-020-04670-9
Official URL: https://link.springer.com/article/10.1007/s00500-020-04670-9#citeas
Deposited by: Memoria Investigacion
Deposited on: 02 Mar 2022 14:07
Last Modified: 30 Nov 2022 09:00
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM