Using case-based reasoning as a reinforcement learning framework for optimization with changing criteria

Abstract

Practical optimization problems such as job-shop scheduling often involve optimization criteria that change over time. Repair-based frameworks have been identified as flexible computational paradigms for difficult combinatorial optimization problems. Since the control problem of repair-based optimization is severe, reinforcement learning (RL) techniques can be potentially helpful. However, some of the fundamental assumptions made by traditional RL algorithms are not valid for repair-based optimization. Case-based reasoning compensates for some of the limitations of traditional RL approaches. We present a case-based reasoning RL approach, implemented in the C/sub A/B/sub I/NS system, for repair-based optimization. We chose job-shop scheduling as the testbed for our approach. Our experimental results show that C/sub A/B/sub I/NS is able to effectively solve problems with changing optimization criteria which are not known to the system and only exist implicitly in a extensional manner in the case base.