Graduate School of Technology, Industrial and Social Sciences, Tokushima University, 2-1 Minami Josanjima, Tokusima, 770-8506, Japan
Evol Comput. 2020 Winter;28(4):595-619. doi: 10.1162/evco_a_00268. Epub 2020 Feb 13.
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 -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.
为了保持遗传算法（GA）的种群多样性，我们需要采用适当的种群多样性度量方法。然而，通常用于排列问题的种群多样性度量方法并没有考虑种群中个体变量之间的依赖关系。我们提出了三种类型的种群多样性度量方法，用于解决变量之间的高阶依赖关系，以研究考虑高阶依赖关系的有效性。第一种方法是基于 -th--阶马尔可夫模型，从种群中估计个体的概率分布的熵。第二种方法是第一种方法的扩展。第三种方法类似于第一种方法，但它基于变量阶马尔可夫模型。所提出的种群多样性度量方法被纳入旅行商问题的 GA 的评估函数中，以保持种群多样性。实验结果表明，三种基于高阶熵的种群多样性度量方法在对抗常用的种群多样性度量方法方面是有效的。
