Cargando…

An Ant Colony Optimization Based on Information Entropy for Constraint Satisfaction Problems

Solving the constraint satisfaction problem (CSP) is to find an assignment of values to variables that satisfies a set of constraints. Ant colony optimization (ACO) is an efficient algorithm for solving CSPs. However, the existing ACO-based algorithms suffer from the constructed assignment with high...

Descripción completa

Detalles Bibliográficos
Autores principales: Guan, Boxin, Zhao, Yuhai, Li, Yuan
Formato: Online Artículo Texto
Lenguaje:English
Publicado: MDPI 2019
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7515295/
https://www.ncbi.nlm.nih.gov/pubmed/33267479
http://dx.doi.org/10.3390/e21080766
_version_ 1783586784271138816
author Guan, Boxin
Zhao, Yuhai
Li, Yuan
author_facet Guan, Boxin
Zhao, Yuhai
Li, Yuan
author_sort Guan, Boxin
collection PubMed
description Solving the constraint satisfaction problem (CSP) is to find an assignment of values to variables that satisfies a set of constraints. Ant colony optimization (ACO) is an efficient algorithm for solving CSPs. However, the existing ACO-based algorithms suffer from the constructed assignment with high cost. To improve the solution quality of ACO for solving CSPs, an ant colony optimization based on information entropy (ACOE) is proposed in this paper. The proposed algorithm can automatically call a crossover-based local search according to real-time information entropy. We first describe ACOE for solving CSPs and show how it constructs assignments. Then, we use a ranking-based strategy to update the pheromone, which weights the pheromone according to the rank of these ants. Furthermore, we introduce the crossover-based local search that uses a crossover operation to optimize the current best assignment. Finally, we compare ACOE with seven algorithms on binary CSPs. The experimental results revealed that our method outperformed the other compared algorithms in terms of the cost comparison, data distribution, convergence performance, and hypothesis test.
format Online
Article
Text
id pubmed-7515295
institution National Center for Biotechnology Information
language English
publishDate 2019
publisher MDPI
record_format MEDLINE/PubMed
spelling pubmed-75152952020-11-09 An Ant Colony Optimization Based on Information Entropy for Constraint Satisfaction Problems Guan, Boxin Zhao, Yuhai Li, Yuan Entropy (Basel) Article Solving the constraint satisfaction problem (CSP) is to find an assignment of values to variables that satisfies a set of constraints. Ant colony optimization (ACO) is an efficient algorithm for solving CSPs. However, the existing ACO-based algorithms suffer from the constructed assignment with high cost. To improve the solution quality of ACO for solving CSPs, an ant colony optimization based on information entropy (ACOE) is proposed in this paper. The proposed algorithm can automatically call a crossover-based local search according to real-time information entropy. We first describe ACOE for solving CSPs and show how it constructs assignments. Then, we use a ranking-based strategy to update the pheromone, which weights the pheromone according to the rank of these ants. Furthermore, we introduce the crossover-based local search that uses a crossover operation to optimize the current best assignment. Finally, we compare ACOE with seven algorithms on binary CSPs. The experimental results revealed that our method outperformed the other compared algorithms in terms of the cost comparison, data distribution, convergence performance, and hypothesis test. MDPI 2019-08-06 /pmc/articles/PMC7515295/ /pubmed/33267479 http://dx.doi.org/10.3390/e21080766 Text en © 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
spellingShingle Article
Guan, Boxin
Zhao, Yuhai
Li, Yuan
An Ant Colony Optimization Based on Information Entropy for Constraint Satisfaction Problems
title An Ant Colony Optimization Based on Information Entropy for Constraint Satisfaction Problems
title_full An Ant Colony Optimization Based on Information Entropy for Constraint Satisfaction Problems
title_fullStr An Ant Colony Optimization Based on Information Entropy for Constraint Satisfaction Problems
title_full_unstemmed An Ant Colony Optimization Based on Information Entropy for Constraint Satisfaction Problems
title_short An Ant Colony Optimization Based on Information Entropy for Constraint Satisfaction Problems
title_sort ant colony optimization based on information entropy for constraint satisfaction problems
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7515295/
https://www.ncbi.nlm.nih.gov/pubmed/33267479
http://dx.doi.org/10.3390/e21080766
work_keys_str_mv AT guanboxin anantcolonyoptimizationbasedoninformationentropyforconstraintsatisfactionproblems
AT zhaoyuhai anantcolonyoptimizationbasedoninformationentropyforconstraintsatisfactionproblems
AT liyuan anantcolonyoptimizationbasedoninformationentropyforconstraintsatisfactionproblems
AT guanboxin antcolonyoptimizationbasedoninformationentropyforconstraintsatisfactionproblems
AT zhaoyuhai antcolonyoptimizationbasedoninformationentropyforconstraintsatisfactionproblems
AT liyuan antcolonyoptimizationbasedoninformationentropyforconstraintsatisfactionproblems