« Combinatorial Problem Solving Using Randomized Dynamic Tunneling on A Production System | Main | Constraint Satisfaction by Parallel Optimization of Local Evaluation Functions with Annealing »

Combinatorial Problem Solving Using Randomized Dynamic Composition of Production Rules

Kanada, Y., 1995 Int'l Conference on Evolutionary Computation (ICEC '95), pp. 467-472, (C) Copyright 1995 by IEEE.

[ 日本語のページ ]
[ Paper PDF file] [ Paper postscript file]
[ IEEExplore Paper page ]

Abstract : The present paper proposes a method of solving combinatorial problems using randomized dynamic rule composition. This method is called CCM* and is based on a computational model called Chemical Casting Model (CCM), which is a rule-based computational model for emergent computation. CCM was proposed by the author toward solving dynamic, open and incompletely specified problems using a few simple rules and evaluation functions. By composing a rule from a given production rule dynamically and randomly, CCM* makes it possible to escape from local maxima, which cannot be escaped from by applying the original rule. This method is compared with the original CCM and another extended version of CCM, i.e., CCM with simulated annealing. 0-1 integer programming problems are solved using these methods. Our experiments show that CCM* performs much better than both the original and annealed CCM. In addi-tion, suboptimal solutions can be found in less time than a branch-and-bound method.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Combinatorial optimization, Integer programming, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Annealing

Post a comment

About

This page contains a single entry from the blog posted on November 1, 1995 12:00 AM.

Many more can be found on the main index page or by looking through the archives.

(C) Copyright 2007 by Yasusi Kanada
Powered by
Movable Type 3.36