Portal de Periódicos da CAPES

COMBINATORIAL SEARCH ALGORITHMS WITH META-CONTROL: MODELING AND IMPLEMENTATIONS

1992; World Scientific; Volume: 01; Issue: 03 Linguagem: Inglês

10.1142/s0218213092000259

1793-6349

Benjamin W. Wah, Lon-Chan Chu,

Machine Learning and Algorithms

In this paper, we model search algorithms with meta-control, allowing resource constraints, approximation, and parallel processing to be incorporated easily in the search process. The basic building block of the model is a hierarchical search process (HSP) consisting of context-free and context-sensitive grammars classified according to problem-independent and problem-dependent parts. The context-sensitive components are used mainly for evaluating decision parameters and in ordering production rules in the context-free grammar. The execution of the grammars for given initial conditions may invoke other HSPs already defined in the system. We describe ISE (acronym for Integrated Search Environment), a tool that implements hierarchical searches with meta-control. By separating the problem-dependent and problem-independent components in ISE, new search methods based on a combination of existing methods can be developed easily by coding a single master control program. Further, new applications solved by searches can be developed by coding the problem-dependent parts and reusing the problem-independent parts already developed. We describe the organization of ISE and present experiments carried out on the system.