POPULATION-BASED LEARNING - A METHOD FOR LEARNING FROM EXAMPLES UNDER RESOURCE CONSTRAINTS
In this paper, we study a learning model for designing heuristics automatically under resource constraints. We focus on improving performance related heuristic methods (HM's) in knowledge lean application domains. We assume that learning is episodic, that the performance measures of an episode are dependent only on the final state reached in evaluating the corresponding test case and are independent of the intermediate decisions and internal states, and that the aggregate performance measures of the HM's involved are independent of the order of evaluation of test cases. The learning model is based on testing a population of competing HM's for an application problem, and switches from one to another dynamically, depending on the outcome of previous tests. Its goal is to find a good HM within the resource constraints, with proper trade-off between cost and quality. It complements existing point-based machine learning models that maintain only one incumbent HM, and that test the HM extensively before switching to alternative ones. It extends existing work on classifier systems by addressing issues related to delays in feedback, scheduling of tests of HM's under limited resources, anomalies in performance evaluation, and scalability of HM's. Finally, we describe our experience in applying the learning method on five application problems.
population-based learning learning from examples heuristic method performance evaluation knowledge-lean application point-based learning resource scheduling