A. Likas et al., DISCRETE OPTIMIZATION-BASED ON THE COMBINED USE OF REINFORCEMENT AND CONSTRAINT SATISFACTION SCHEMES, NEURAL COMPUTING & APPLICATIONS, 3(2), 1995, pp. 101-112
Citations number
14
Categorie Soggetti
Computer Sciences, Special Topics","Computer Science Artificial Intelligence
A new approach is presented for finding near-optimal solutions to disc
rete optimisation problems that is based on the cooperation of two mod
ules: an optimisation module and a constraint satisfaction module, The
optimisation module must be able to search the problem state space th
rough an iterative process of sampling and evaluating the generated sa
mples. To evaluate a generated point, first a constraint satisfaction
module is employed to map that point to another one satisfying the pro
blem constraints, and then the cost of the new point is used as the ev
aluation of the original one, The scheme that we have adopted for test
ing the effectiveness of the method uses a reinforcement learning algo
rithm in the optimisation module and a general deterministic constrain
t satisfaction algorithm in the constraint satisfaction module. Experi
ments using this scheme for the solution of two optimisation problems
indicate that the proposed approach is very effective in providing fea
sible solutions of acceptable quality.