High-Order Entropy-Based Population Diversity Measures in the Traveling Salesman Problem
Evolutionary Computation · 2020-12 · 28 (4) · 595-619
DOI: 10.1162/evco_a_00268 ↗Kurz gefasst
Fachartikel in der Zeitschrift Evolutionary Computation, 2020-12. Verfasst von Yuichi Nagata. Beteiligte Einrichtung: Graduate School of Technology, Industrial and Social Sciences, Tokushima University, 2-1 Minami Josanjima, Tokusima, 770-8506, Japan nagata@is.tokush…. Hauptthemen laut MEDLINE: Algorithms. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 23 Literaturangaben.
Abstract (Originalsprache)
To maintain the population diversity of genetic algorithms (GAs), we are required to employ an appropriate population diversity measure. However, commonly used population diversity measures designed for permutation problems do not consider the dependencies between the variables of the individuals in the population. We propose three types of population diversity measures that address high-order dependencies between the variables to investigate the effectiveness of considering high-order dependencies. The first is formulated as the entropy of the probability distribution of individuals estimated from the population based on an [Formula: see text]-th--order Markov model. The second is an extension of the first. The third is similar to the first, but it is based on a variable order Markov model. The proposed population diversity measures are incorporated into the evaluation function of a GA for the traveling salesman problem to maintain population diversity. Experimental results demonstrate the effectiveness of the three types of high-order entropy-based population diversity measures against the commonly used population diversity measures.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Graduate School of Technology, Industrial and Social Sciences, Tokushima University, 2-1 Minami Josanjima, Tokusima, 770-8506, Japan nagata@is.tokushima-u.ac.jp.
Zitieren
APA
Nagata, Y. (2020). High-Order Entropy-Based Population Diversity Measures in the Traveling Salesman Problem. Evolutionary Computation, 28(4), 595-619. https://doi.org/10.1162/evco_a_00268
Vancouver
Nagata Y. High-Order Entropy-Based Population Diversity Measures in the Traveling Salesman Problem. Evolutionary Computation. 2020;28(4):595-619. doi:10.1162/evco_a_00268
BibTeX
@article{Nagata2020,
author = {Nagata, Yuichi},
title = {High-Order Entropy-Based Population Diversity Measures in the Traveling Salesman Problem},
journal = {Evolutionary Computation},
year = {2020},
volume = {28},
number = {4},
pages = {595--619},
doi = {10.1162/evco_a_00268}
}
EUVIMED