In this project, we aim to solve hard combinatorial optimization problems (COPs) by incorporating Soft Computing methods. In particular, we use Active Learning Method (ALM), a new fuzzy modeling algorithm, and Reinforcement Learning in solving COPs.

 Previous researches have shown the success of using Reinforcement Learning in solving combinatorial optimization problems. The main idea of these methods is to learn (near) optimal evaluation functions to improve local searches and find (near) optimal solutions. STAGE algorithm, introduced by Boyan & Moore, is one of the most important algorithms in this area.

The main idea of STAGE is to predict the ultimate results of a local search algorithm based on the starting points and then to select the most promising point for doing the local search. For predicting the ultimate result of the local search for new unseen points, STAGE uses a learned model which is trained based on known inputs and outputs. We have used ALM, an instance based fuzzy learning method, to learn the relationship between input and output data, and our results have been great! Furthermore, we have analyzed the effectiveness of different local search algorithms and other learning structures, such as CMAC, in STAGE.


      [PS]  file, size 6499k.   [ZIP] file, size 1535k.


Richard S. Sutton, and Andrew G. Barto, “Reinforcement Learning: An Introduction”, MIT Press, 1998.