A HYBRID NEURAL NETWORK MODEL FOR SOLVING OPTIMIZATION PROBLEMS

被引:20
作者
SUN, KT [1 ]
FU, HC [1 ]
机构
[1] NATL CHIAO TUNG UNIV,DEPT COMP SCI & INFORMAT ENGN,HSINCHU 30050,TAIWAN
关键词
ENERGY FUNCTIONS; FEASIBLE SOLUTIONS; NEURAL NETWORK; OPTIMIZATION PROBLEMS;
D O I
10.1109/12.204794
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 [计算机科学与技术];
摘要
In this paper, we propose a hybrid neural network model for solving optimization problems. We first derive an energy function, which contains the constraints and cost criteria of an optimization problem, and we then use the proposed neural network to find the global minimum (or maximum) of the energy function, which corresponds to a solution of the optimization problem. The proposed neural network contains two subnets: a Constraint network and a Goal network. The Constraint network models the constraints of an optimization problem and computes the gradient (updating) value of each neuron such that the energy function monotonically converges to satisfy all constraints of the problem. The Goal network points out the direction of convergence for finding an optimal value for the cost criteria. These two subnets ensure that our neural network finds feasible as well as optimal (or near-optimal) solutions. We use two well-known optimization problems-the Traveling Salesman Problem and the Hamiltonian Cycle Problem-to demonstrate our method. Our hybrid neural network successfully finds 100 % of the feasible and near-optimal solutions for the Traveling Salesman Problem and also successfully discovers solutions to the Hamiltonian Cycle Problem with connection rates of 40% and 50%.
引用
收藏
页码:218 / 227
页数:10
相关论文
共 31 条
[1]
Aiyer S B, 1990, IEEE Trans Neural Netw, V1, P204, DOI 10.1109/72.80232
[2]
SELF-ORGANIZING FEATURE MAPS AND THE TRAVELING SALESMAN PROBLEM [J].
ANGENIOL, B ;
VAUBOIS, GD ;
LETEXIER, JY .
NEURAL NETWORKS, 1988, 1 (04) :289-293
[3]
SENSITIVITY ANALYSIS IN NEURAL NET SOLUTIONS [J].
DAVIS, GW .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1989, 19 (05) :1078-1082
[4]
DURBIN R, 1989, NEURAL COMPUTAT, V1, P384
[5]
FU HC, 1989, JUN P IJCNN 89 WASH
[6]
Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[7]
GUTZMANN KM, 1987, 1ST P IEEE INT C NEU, P721
[8]
HOPFIELD JJ, 1985, NEURAL COMPOSITION D, V55, P141
[9]
Horowitz E., 1978, FUNDAMENTALS COMPUTE
[10]
JOHNSON JJ, 1989, J PARALLEL DISTRIBUT, P435