Abstract: Recently, a new model of computation that is inspired by genetic operations over strings such as mutation and crossover has been proposed. Networks of Genetic Processors (NGPs) are highly related to previously proposed models such as Networks of Evolutionary Processors (NEPs) and Networks of Splicing Processors (NSPs). NGPs are computationally complete and several complexity measures have been proposed to evaluate their computing power with restricted resources (mainly, the time and the number of processors in the network). In this work we evaluate NGPs in an experimental approach. We have selected a NP-complete decision problem, the Hamiltonian Cycle Problem, and we have solved different instances with the proposed model of computation. Our aim is to prove that the selected problem (and all NP problems) can be solved in polynomial time with NGPs. In this case, our experiments show that the problem can be solved in linear time with a fixed number of processors for a given size of the problem.

Keywords: Networks of biologically-inspired processors, Combinatorial Problems, Complexity.

Link:

Solving Combinatorial Problems with Networks of Genetic Processors

Marcelino Campos, José M. Sempere

http://www.foibg.com/ijitk/ijitk-vol07/ijitk07-01-p07.pdf