求图控制集问题的模拟退火算法的改进

An Improved Simulated Annealing Algorithm for Graph Dominating Set Problem

图控制集问题要求确定任意简单无向图的最小控制集,是NP 难度的问题。本文针对已有的求解此问题的模拟退火算法进行了两个方面的改进:一是给出了一个更为合理的解的评估函数;二是提出了一个产生邻解的加权随机策略。仿真实验表明,改进后的模拟退火算法在稠密图的随机实例上明显提高了收敛速度。

The Graph Dominating Set (GDS) problem requines to determine the minimal dominating sets in a simple undirected graph, which is known to be NPhard. An improvement has been made upon the known simulated annealing algorithm for GDS: a more reasonable evaluation function for solutions and a weighted random strategy for generating a neighbor solution are proposed. Simulated experiments show that for dense graphs the improved simulated annealing algorithm can converge more quickly to a good solution.