J.P. PABICO and E.R.E. Mojica. 28th Annual Philippine-American Academy of Science and Engineering (PAASE) Meeting and Symposium (28th APAMS), Georgetown University, Washington DC, USA, 22-24 May 2008.

Abstract

We present a computational metaphor that uses the dynamics of molecules in chemical systems to solve a set P = {p₁, p₂, ..., p_n} of n unrelated problems simultaneously. The metaphor uses an abstract reactor tank that applies one of (n + 1) catalytic reaction rules to colliding artificial molecular species whose respective structures decode into solutions to the problems being solved. The tank is driven by an stochastic algorithm that simulates the dynamics of an artificial chemical universe resulting into parallel evolution of the solutions encoded into the molecular species. We implemented the metaphor in a two-dimensional tank topology and designed (n + 1) catalytic reaction rules to guide the molecular dynamics. When two molecules that encode solutions to the same problem p_i collide (for all i = 1, 2, ..., n), two new molecules are created encoding new solutions to p_i. When two unrelated molecules collide, two new molecules are created which decode to solutions to two unrelated problems p_i and p_j. When a molecule hits the walls of the reactor, its molecular structure is altered, thereby changing the solutions encoded in the molecule. The objective function value of the encoded solution is treated as the mass of the molecular species and is used as a measure for goodness of solutions. The lighter the mass allows the species to obtain a higher rate of reaction, creating more solutions to the problems being solved. We tested our metaphor in solving two real-world problems: (1) The traveling salesperson problem (TSP); and (2) The optimization of cultivar coefficients in the Ceres-Rice model. The artificial reactor tank was able find solutions to both problems simultaneously, and at the same time obtain solutions with the same quality as with known deterministic algorithms.

Keywords: artificial chemistry, computational metaphor, combinatorial optimization, parametric optimization, self-organizing system

E.R.E. Mojica is Assistant Professor in the Institute of Chemistry, College of Arts and Sciences, University of the Philippines Los Baños and Graduate Research Assistant in the Department of Chemistry, State University of New York, Buffalo, New York.

Submitted 01 March 2008; Accepted 06 March 2008.