EUVIMEDEUVIMED entdecken
Crossref

High-Order Entropy-Based Population Diversity Measures in the Traveling Salesman Problem

Yuichi Nagata

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsComputer SimulationEntropyHeuristicsHumansInformation TheoryMarkov ChainsPopulation DensityPopulation DynamicsProbabilityUncertainty

Stichwörter der Autor:innen

Genetic algorithmentropyhigh-order dependenciespopulation diversitytraveling salesman problem.

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}
}
Kostenlos starten →