Previous [1] [2] [3] [4] [5]

Journal of Inforamtion Science and Engineering, Vol.5 No.2, pp.167-177 (April 1989)
A Neural Network Processing Methodology for
Zero-One Knapsack Problems

Hahn-Ming Lee and Ching-Chi Hsu
Department of Computer Science and Information Engineering
National Taiwan University
Taipei, Taiwan, Republic of China

Neural net models typically consist of many simple neuron-like processing elements interacting via weighted connections. They have been studied to rapidly provide a collectively-computed solution. In this paper, we present a methodology to approximately solve zero-one knapsack problems in near real-time by the use of the characteristic that many neural networks can be shown to minimize an energy function defined for the networks. This methodology includes four stages. They are (1) define an "energy" function, (2) put the problem to the neural network model, (3) choose an appropriate activation function to make the "energy" function be bounded and decreased, and (4) test and adjust parameters. Besides, we also simulate the neural network model with several appropriate activation functions to approximately solve zero-one knapsack optimization problems. The result of the simulation demonstrates how the methodology presented here can work well for zero-one knapsack problems and can be easily extended to other combinatorial optimization problems.

Keywords: neural network, zero-one knapsack problem, combinatorial optimization, energy function, activation function

Received April 2, 1989; revised July 1, 1989.
Communicated by Lin-Shan Lee.