An exploratory research of elitist probability schema and its applications in evolutionary algorithms
An exploratory research of elitist probability schema and its applications in evolutionary algorithms
复制标题
DOI：
10.1007/s10489-013-0494-9
复制
发表时间：
2014-01
影响因子：
5.3
通讯作者：
Hongguang Zhang;Yuan’an Liu;B. Tang;Kaiming Liu
中科院分区：
文献类型：
--
作者：
Hongguang Zhang;Yuan’an Liu;B. Tang;Kaiming Liu
进化算法研究中的一个重要问题是如何连续预测有希望的解，同时摆脱局部最优解。在本文中，我们首次提出了一个精英概率模式（EPS），据我们所知。我们的模式是二进制字符串的索引，表示精英群体在每个字符串位置的相似性。EPS表示适应度选择对种群编码相似度的累积效应。对于每一代，EPS可以客观、快速地量化种群的编码相似度。我们的关键创新之一是，EPS可以持续预测有希望的解决方案，同时在大多数情况下摆脱局部最优。为了证明EPS的能力，我们设计了一个精英概率模式遗传算法和一个精英概率模式紧凑遗传算法。这些算法是分布算法（EDAs）的估计。针对0-1背包问题，我们与持续精英紧致遗传算法（PeCGA）、量子进化算法（QEA）和粒子群算法（PSO）进行了比较。该算法的收敛速度比PeCGA、QEA和粒子群算法快，尤其适用于大型背包问题。此外，该算法的计算时间比一些基于建立显式概率模型的eda要短，与QEA和PSO近似。这对于进化算法来说是可以接受的，对于eda来说是令人满意的。所提出的算法在收敛性能和计算时间方面都是成功的，这表明EPS是令人满意的。
An important problem in the study of evolutionary algorithms is how to continuously predict promising solutions while simultaneously escaping from local optima. In this paper, we propose an elitist probability schema (EPS) for the first time, to the best of our knowledge. Our schema is an index of binary strings that expresses the similarity of an elitist population at every string position. EPS expresses the accumulative effect of fitness selection with respect to the coding similarity of the population. For each generation, EPS can quantify the coding similarity of the population objectively and quickly. One of our key innovations is that EPS can continuously predict promising solutions while simultaneously escaping from local optima in most cases. To demonstrate the abilities of the EPS, we designed an elitist probability schema genetic algorithm and an elitist probability schema compact genetic algorithm. These algorithms are estimations of distribution algorithms (EDAs). We provided a fair comparison with the persistent elitist compact genetic algorithm (PeCGA), quantum-inspired evolutionary algorithm (QEA), and particle swarm optimization (PSO) for the 0–1 knapsack problem. The proposed algorithms converged quicker than PeCGA, QEA, and PSO, especially for the large knapsack problem. Furthermore, the computation time of the proposed algorithms was less than some EDAs that are based on building explicit probability models, and was approximately the same as QEA and PSO. This is acceptable for evolutionary algorithms, and satisfactory for EDAs. The proposed algorithms are successful with respect to convergence performance and computation time, which implies that EPS is satisfactory.