【摘要】 本文提出一种求解最大独立集问题(MIS)的启发式神经网络算法。该算法基于MIS问题的特点,有效地限制神经网络初始点的选择范围,并利用神经网络快速收敛能力获得问题的解。与标准神经网络算法相比,该算法显示了较高的全局优化性态与计算效率。模拟计算实例表明了该算法的有效性。更多还原

【Abstract】 Maximum independent set problem is of great significance, but is NP-hard to solve. Apart from algorithms for some specific graphs, we hope to find a generally purposed method for the problem. In this paper, A kind of heuristic neural network algorithm for this problem is proposed. First, the maximum independent problem is described by combinatorial optimization model, with quadratic objective function, so Hopfield network can be used to obtain local optimum solutions. Next, the analytic results of the problem is presented to guide the choice of start-points of Hopfield network. Doing this can greatly deduct the searching space and imporove the possibility of obtaining global optimum solution. At the same time, the fast convergence speed of neural network guarantee the algorithm is very effective. Comparing to standard neural network algorithm, the proposed algorithm shows quite high global optimization and computing effciency. The simulation computation results show the efficiency of the proposed algorithm.更多还原