« Large-scale Constraint Satisfaction Using Local-information-based Annealing and Its Parallel Processing -- An Application of Emergent Computation Model CCM -- | Main | Combinatorial Problem Solving Using Randomized Dynamic Composition of Production Rules »

Combinatorial Problem Solving Using Randomized Dynamic Tunneling on A Production System

Kanada, Y., IEEE Systems, Man and Cybernetics '95, (C) Copyright 1995 by IEEE.
[ 日本語のページ ]
[ Paper PDF file] [ Paper postscript file]
[ IEEExplore Paper page ]

Abstract : Levy and Montalvo, Yao, and Shima individually pro-posed tunneling algorithms. The tunneling algorithms employ analogy to tunnel effect in physics, and are used to optimize continuous systems. The present paper proposes a method of solving combinatorial problems using a type of randomized dynamic tunneling technique. This method is based on a computational model called CCM*. CCM* is an extended version of the Chemical Casting Model (CCM). CCM was proposed by the author toward developing a method of solving open and incompletely-specified problems that may change while being solved, using self-organizing computation.

The 0-1 integer programming problem is solved using CCM* with a very simple rule and an evaluation function. CCM* allows us to escape from local maxima by composing the rule dynamically and randomly. This cannot be done by using the original production rule as is. Our experiments show that approximate solutions can be found more rapidly by CCM* than by using a branch-and-bound method in the case of 0-1 integer programming.

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

Keywords: CCM, Combinatorial optimization, Integer programming, Emergent Computation, Randomized computation, Randomized problem solving, Tunneling, Rule-based computation, Rule-based problem solving

Post a comment

About

This page contains a single entry from the blog posted on October 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