New Approaches to Combinatorial Problems and Scheduling Problems. Neural Networks with the Linked State Transition for Constraint Satisfaction and Their Applications to Combinatorial Optimization Problems.

概要

論文の詳細を見る
In the solution to combinatorial optimization problems with constraints by using neural networks, the penalty approach is adopted in which the constraint functions are combined with the minimization function. In the transformation of a constrained problem into a unconstrained one, it is feared that a lot of feasible combinatorial states satisfying the constraints corrupt into discrete local optimal solutions in a neighborhood with a radius of one Hamming distance. The paper presents the new fundamentals of the neural network whose states transit so as to satisfy the constraints. The feasibility of the state transition for constraints is kept by the linked transition mode in which some of the neurons change their states cooperatively and simultaneously. In this paper, in order to get off from a local optimum among the feasible states, a stochastic version of the linked state transition rule is proposed as well as deterministic rule. In the stochastic transition, increase of the function value to be minimized is accepted in a ratio. The simulation results for the simple 0-1 combinatorial problems demonstrate effectiveness of these transition manners.
公益社団法人計測自動制御学会の論文