基于进化强度的蚁群算法过程性能评价

Process performance assessment for ant colony optimization using evolving strength

为了评价蚁群算法的过程性能,提出了一种基于进化强度的蚁群算法性能评价方法。以子集问题为例,引入谷元距离度量解的差异程度,并定义了迭代的相对进化幅度。将一次迭代的相对进化幅度与解的相对差异程度之比定义为进化强度,并据此将迭代区分为进化代与停滞代。通过多次运行算法并计算进化强度的平均值得到蚁群算法的进化强度趋势图,对比进化强度的趋势图进行蚁群算法过程性能评价。以4种求解子集的典型蚁群算法为例,通过标准测试实例验证了评价方法的有效性与合理性。

To assess the process performance of ant colony optimization, an evolution method based on evol- ving strength for ant colony optimization was proposed. By taking the subset problem for example, Tani- moto distance was introduced to measure the difference degree between the two feasible solutions, and the relative evolving range of a generation was defined. The evolving strength of a generation was defined as the ratio of its relative evolving range to the relative difference degree. According to the evolving strength, the generations were classified into two classes, that is, the evolving generation and the stagnating genera- tion. The evolving strength trend charts of the ant colony optimization were obtained by averaging the evolving strength values that come from executing the algorithm multiple times, and the performances of ant colony optimizations were evaluated through their trend charts. Using standard testing cases, the effeetiveness and rationality of the proposed method were tested using four typical ant colony 3ptimizations for subset problems.