Improving Diversity in Evolutionary Algorithms: New Best Solutions for Frequency Assignment
针对频率分配问题中进化算法过早收敛和中性网络处理不当的问题，提出一种基于替换的多样性管理策略，将单目标转化为多目标优化，在44个公开实例上取得11个新最优解。
Metaheuristics have yielded very promising results for the frequency assignment problem (FAP). However, the results obtainable using currently published methods are far from ideal in complex, large-scale instances. This paper applies and extends some of the most recent advances in evolutionary algorithms to two common variants of the FAP, and shows how, in traditional techniques, two common issues affect their performance: 1) premature convergence and 2) the way in which neutral networks are handled. A recent replacement-based diversity management strategy is successfully applied to alleviate the premature convergence drawback. Additionally, by properly defining a distance metric, the performance in the presence of neutrality can also be greatly improved. The replacement strategy combines the principle of transforming a single-objective problem into a multiobjective one by considering diversity as an additional objective, with the idea of adapting the balance induced between exploration and exploitation to the requirements of the different optimization stages. Tests with 44 publicly available instances yield very competitive results. New best-known frequency plans were generated for 11 instances, whereas in the remaining ones the best-known solutions were replicated. Comparisons with a large number of strategies designed to delay convergence of the population clearly show the advantages of our novel proposals.