Artificial Chemistry

From H+Pedia
Jump to: navigation, search

Artificial Chemistry is a subfield of Artificial Life research that studies artificial chemistries, artificial systems that resemble real chemical systems in their behaviour, generally in the context of artificial biochemistries, their organization, and the means through which they can self-assemble, self-replicate, and self-improve.

History

Not much.

Formal Definition

An artificial chemistry is a triple (S,R,A) where S is the set of all possible molecules (Not the molecules in the system being modeled), R is a set of reaction rules, and A is an algorithm describing how the rules are applied to the molecules. Both S and R can be defined implicitly, for example, if S is infinite and R is a mathematical or logical expression that takes arbitrary arguments.

The Set of Molecules

The first step in defining an artificial chemistry is the definition of the set of possible molecules that may exist in it. In an abstract setting, the set <math>S = {S_1, S_2, ... S_n}</math>, where n may be infinite, may be a set of symbols [1], strings [2],[3],[4][5], numbers[6][7], lambda expressions [8], or any arbitrary data structure. This definition is the molecule's structure.

The Set of Reactions

The set of reaction rules R describes how every molecule <math>S_i \in S</math> interacts with the others. A rule <math>r \in R</math> can be written in simplified chemical notation:

<math>S_1 + S_2 + ... S_n \rightarrow S'_1 + S'_2 + ... + S'_m</math>

The reaction determines how the n reagents are replaced with m products. n is also known as the order of the reaction. Note that the + here is simply a separator. This simple definition requires only that all molecules of the set of reagents are present. This definition can be modified to, for example, compute a probability of the reaction happening based on how many and which components are available, even if not all are present; or it may be added to by introducing special considerations for the spatial distribution of reagents or other molecules, (Or, in the case that the chemical environment is not explicitly spatial, other more abstract properties), energy consumption, colission checking for angle and energy (Again, this is only valid in a explicitly spatial world), the 'age' of the molecules, or any other property of the molecules or their environment. The purpose of the AC determines which parameters will be used.

The Reactor

An algorithm A determines how the rules R are applied to the set of molecules used in the simulation, <math>P \subseteq S</math>. A depends on how P is represented: When there is no spatial structure and P is simply a vector or a matrix, A may be a simple set of matrix operations.

The following is a summary of artificial molecular dynamics methods, which can be characterized by the representation of P:

Stochastic Molecular Collisions

This system is at the lowest level of description, and is analogous to ab-initio calculations in ordinary computational chemistry (Although the simplicity of the model described below makes this method closer in appearance to molecular dynamics, except that this computes reactions, while analogous behaviour is impossible in molecular dynamics due to the lack of considerations for electronic properties). Every molecule is explicitly simulated and P is a multiset (That is, there can be more than one molecule of every kind). The algorithm A randomly (Or iteratively) draws a number n of molecules from P and checks whether there exists a rule <math>r \in R</math> with order n that can be applied to the molecules. If true, the molecules are replaced with the products of the corresponding rule. Further side effects have to be inserted as new parameters (Energy, spatial information, rate constants, temperature, diffusion rates, et cetera) are added. The following algorithm computes an Artificial Chemistry of second-order reactions (n = 2):

<math> Simulate(S,R,A,P,t) = \begin{cases} \underline{while} (\neg{terminate()})\\ \quad \underline{do} \\ \quad \quad s_1 := draw(P) \\ \quad \quad s_2 := draw(P) \\ \quad \quad \quad \underline{if}~\exists \in R ~\underline{then}\\ \quad \quad \quad \quad \quad P := remove(P,s_1,s_2); \\ \quad \quad \quad \quad \quad P := insert(P,s'_1,s'_2,...,s'_m); \\ \quad \quad \quad \underline{fi} \\ \quad \underline{od} \\ \end{cases} </math>

The function draw returns a randomly or iteratively chosen molecule from P (Without removing it). The probability that a particular molecule will be chosen is proportional to its concentration in the population, although the definition of draw can be modified to include increasingly complex selection mechanisms.

The memory consumption is generally of the order O(M), that is, the memory is linearly dependent on the total number of molecules M (The size of P).

While the most accurate, this level of simulation is slow for large P.

Continuous or Discrete Differential Equations

Metadynamics

Mixed Approaches

Symbolic Analysis of the Equations

Computing Costs

Sample Implementation

(defparameter S
  '(
      hydrogen oxygen water
      silver sulphur silver-sulfide
      iron oxygen iron-oxide
      methane carbon-dioxide      
      glucose ethyl-alcohol)
  "The set of all possible molecules.")

(defparameter R
  '(
    ((hydrogen oxygen)		(water))
    ((silver sulphur)		(silver-sulfide))
    ((iron oxygen)		(iron-oxide))
    ((methane oxygen)		(carbon-dioxide water))
    ((glucose oxygen)		(ethyl-alcohol carbon-dioxide))
    ((silver-sulphide iron)	(methane)) ;;Lol whut
   )
  "The set of all possible reactions.")

(defparameter P '()
  "The set of molecules used for the simulation.")

(defun draw (population)
  "Draws a random molecule from the population."
  (nth (random (1- (length population))) population))

(defun remove-molecules (population &rest molecules)
  "Removes the specified molecules from the population,
  returning it."
  (loop for molecule in molecules do
    (if (not (null (position molecule population)))
      (setf population
	(append (subseq population 0 (position molecule population))
		(subseq population (1+ (position molecule population)))))))
  population)

(defun insert-molecules (population &rest molecules)
  "Inserts the specified molecules into the given population,
  returning it."
  (nconc population molecules))

(defun rule-checker (ruleset &rest molecules)
  (loop for rule in ruleset do
    (if (equal molecules (car rule))
      (return-from rule-checker (cadr rule)))))

(defun make-population (population &rest pairs)
  "Create a population by taking input in the form:
   '(n x) '(m y) ... Where n and m are the number of molecules
   and x and y are their names. For example, (make-population P
   '(40 water)) creates a population with 40 water molecules."
   (loop for pair in pairs do
      (loop for n from 0 to (first pair) do
	(setf population (append population (last pair)))))
   population)

(defun algorithm (S R P md-time)
  (let ((current-time 0))
    (loop while (not
		  (if (eq md-time current-time)
		    t
		    (progn (incf current-time)
			   nil))) do
      (let* ((s1 (draw P))
	     (s2 (draw P))
	     (replacement-molecules
	      (rule-checker R s1 s2)))
	(if (not (null replacement-molecules))
	  (progn (setf P (remove-molecules P s1 s2))
		 (format t "~&*** REACTION: Replacing ~s and ~s with~{ ~a~}." s1 s2 replacement-molecules)
		 (loop for molecule in replacement-molecules do
		   (setf P (append P (list molecule)))))))))
  P)
  
(defun sample-run ()
  (algorithm
    S R
    (make-population P
      '(50 hydrogen)
      '(40 oxygen)
      '(25 silver)
      '(60 iron)
      '(75 glucose)
      '(100 glucose)
      '(5 carbon-dioxide)
      '(16 sulphur))
    100000))

See Also

References

</references>
  1. Eigen, M., & Schuster, P. (1979). The hypercycle—a principle of natural self-organization. Berlin: Springer.
  2. Bagley, R. J., & Farmer, J. D. (1992). Spontaneous emergence of a metabolism. In C. G. Langton, C. Taylor, J. D. Farmer & S. Rasmussen (Eds.), Articial Life II (pp. 93–140). Redwood City, CA: Addison-Wesley.
  3. Farmer, J. D., Kauffman, S. A., & Packard, N. H. (1986). Autocatalytic replication of polymers. Physica D, 22, 50–67.
  4. Kauffman, S. A. (1993). The origins of order: Self-organization and selection in evolution. New York: Oxford Universit y Press.
  5. McCaskill, J. S., Chorongiewski, H., Mekelburg , D., Tangen, U., & Gemm, U. (1994). Con gurable computer hardware to simulate long-time self-organization of biopolymers. Berichte der Bunsen-Gesellschaft-Physical Chemistry, 98, 1114–1114.
  6. Banzhaf, W., Dittrich, P., & Rauhe, H. (1996). Emergent computation by catalytic reactions. Nanotechnology, 7, 307–314.
  7. Dittrich, P., Liljeros, F., Soulier, A., & Banzhaf, W. (2000). Spontaneous group formation in the seceder model. Physical Review Letters, 84, 3205–3208.
  8. Fontana, W. (1992). Algorithmic chemistry. In C. G. Langton, C. Taylor, J. D. Farmer, & S. Rasmussen (Eds.), Arti cial Life II (pp. 159–210). Redwood City, CA: Addison-Wesley.