REDES DE PROCESADORES GENÉTICOS

Abstract

[EN] In this research, a new model of computing is presented, within the framework of natural computing and computer models inspired by biology: Networks of Genetic Processors (NGP). This new model is based on the one hand, by the family of networks of bio-inspired processors, specifically Networks of Evolutionary Processors (NEP) and Networks of Splicing Processors (NSP), and on the other hand by Genetic Algorithms. We can define the new model as a network of biologically-inspired processors where operations used by processors are crossover and mutation. One of the major interests studying the NGP is the computational power of the operations of crossover and mutation acting together. The NEP is a complete model that uses operations of symbol mutation: insertion, substitution and deletion, the NSP is a complete model that uses splicing operations, but the NEP is no longer a complete model using only substitution operations, as it happens to the NSP if we restrict the context of its splicing rules to the empty context. The study of the new model presented here responds to what happens when we put together in a single model the substitution rules from the NEP (called mutation rules) and the splicing rules with empty context from the NSP (called crossover rules).

When we work with networks of biologically-inspired processors there are two basic types of networks, accepting networks and generating networks. These types of networks are mainly used to work at a theoretical level or to solve decision problems. To work on a more practical level such as solving optimization problems, we propose a new type of network, Networks of Genetic processors as Parallel Genetic Algorithms, inspired by the Parallel Genetic Algorithms.

In this work we prove the computational completeness of our new model by showing that it is equivalent to the Turing machine. We prove the computational completeness of Parallel Genetic Algorithms by using this result and the similarity between the NGP and Parallel Genetic Algorithms. Moreover, we propose a characterization of the Chomsky hierarchy by using the NGP. Here, we simulate every grammar in the language classes of the Chomsky's hierarchy by using a NGP with an small number of processors required for each simulation. Hence, it gives an appreciable idea of the descriptional complexity of the different families of languages.

Finally, in this work there is an experimental study of the behavior of the model for the resolution of some practical problems. First, we design and implement a simulator that allows the execution of networks of Genetic Processors in any of its three defined types: accepting networks, generating networks or as Parallel Genetic Algorithms. This allows us to test the model with different optimization problems. Then, we make a study to see if the new model could solve NP problems in polynomial time. We use the decision problem of Hamiltonian cycle in a graph. Finally, we test the simulator with two optimization problems showing a good computational behavior. The problems are the Multidimensional Knapsack problem and the Traveling Salesman problem.

[ES] Desde la rama de la biocomputación, la computación con modelos inspirados en la biología, esta investigación presenta un nuevo modelo de computación: las Redes de Procesadores Genéticos (NGP). Este nuevo modelo parte, por un lado, de la familia de modelos de redes de procesadores, más concretamente de las Redes de Procesadores Evolutivos (NEP) y las Redes de Procesadores de Splicing (NSP), y por otra parte se inspira en los Algoritmos Genéticos. Así pues, se puede definir de manera informal el nuevo modelo como una red de procesadores bioinspirados donde las operaciones utilizadas por los procesadores son operaciones de cruce y mutación. Uno de los mayores intereses del estudio de las NGP es la capacidad conjunta de las operaciones de cruce y mutación, las NEP son un modelo completo que utiliza operaciones de evolución, es decir, inserción, substitución y borrado, las NSP son un modelo completo que utiliza operaciones de splicing, pero las NEP dejan de ser un modelo completo al usar sólo operaciones de substitución, al igual que le pasa a las NSP si restringimos el contexto de sus reglas de splicing a vacío. El estudio del nuevo modelo aquí presentado da respuesta a qué es lo que pasa cuando juntamos en un sólo modelo las operaciones de sustitución de las NEP (llamadas reglas de mutación) y las operaciones de splicing con contexto vacío de las NSP (llamadas reglas de cruce).

Cuando se trabaja con redes de procesadores bioinspirados se definen principalmente dos tipos de redes, las redes aceptoras y las redes generadoras. Estos tipos de redes sirven principalmente para trabajar a un nivel teórico o para resolver problemas de decisión. Para trabajar a un nivel más práctico como por ejemplo con problemas de optimización, se propone un nuevo tipo de red, las Redes de Procesadores Genéticos como Algoritmos Genéticos Paralelos, llamadas así por inspirarse en los Algoritmos Genéticos Paralelos.

A nivel teórico, se ha podido demostrar la completitud computacional del modelo, con lo que su potencia de computación se sitúa al mismo nivel que el de las maquinas de Turing. A raíz de este resultado y dada la gran similitud entre las NGP y los Algoritmos Genéticos Paralelos, en este trabajo se demuestra que éstos también son un modelo de computación completo. Por otra parte se ha podido realizar una caracterización de la jerarquía de Chomsky utilizando las NGP, para ello se simula cada una de las gramáticas que definen las cuatro familias de lenguajes de dicha jerarquía observando el mínimo número de procesadores necesarios para cada simulación, lo cual da una idea apreciable de la diferencia de complejidad entre las diferentes familias.

No falta en este trabajo un estudio de la parte más práctica del modelo con la realización de algunas tareas. Primero se ha diseñado e implementado un simulador que permite la ejecución de Redes de Procesadores Genéticos en cualquiera de sus tres vertientes aquí definidas, como aceptoras, como generadoras o como Algoritmos Genéticos Paralelos, esto permite realizar pruebas con diferentes problemas de optimización. A continuación se ha realizado un estudio para ver si el nuevo modelo era capaz de resolver problemas NP en tiempo polinómico, para ello se ha trabajado con el problema de ver si existe algún ciclo Hamiltoniano en un grafo. Finalmente se ha probado el simulador con dos problemas de optimización en los que se ha detectado un buen comportamiento del mismo, los problemas utilizados han sido el problema de la mochila multidimensional y el problema del viajante de comercio.

[CA] Des de la branca de la biocomputació (la computació amb models inspirats amb la biologia) aquesta investigació presenta un nou model de computació: Les Xarxes de Processadors Genètics (NGP). Aquest nou model ve, d'una banda, de la família de models de xarxes de processadors, més concretament de les Xarxes de Processadors Evolutius (NEP) i de les Xarxes de Processadors de Splicing (NSP) i d'altra banda s'inspira als Algoritmes Genètics. Així doncs, es pot definir d'una manera informal el nou model com una xarxa de processadors bioinspirats on les operacions utilitzades per els processadors són operacions de creuament i mutació. Un dels elements més interessants de l'estudi de les NGP és la capacitat conjunta de les operacions de creuament i mutació, les NEP són un model complet que utilitza operacions evolutives, és a dir, insercions, substitucions i esborrats, les NSP són un model complet que utilitza operacions de splicing, però les NEP deixen de ser un model complet al gastar sols operacions de substitució, al igual que li passa a les NSP si restringim el context de les seues regles de splicing a buit. L'estudi del nou model presentat ací dóna resposta a què és el que passa quan ajuntem a un sol model les operacions de substitució de les NEP (anomenades regles de mutació) i les operacions de splicing amb context buit de les NSP (anomenades regles de creuament).

Quan es treballa amb xarxes de processadors bioinspirats es defineixen principalment dos tipus de xarxes, les xarxes aceptores i les xarxes generadores. Aquests tipus de xarxes s'utilitzen principalment per a treballar a nivell teòric o per a resoldre problemes de decisió. Per treballar a un nivell més pràctic, com per exemple amb problemes d'optimització, es proposa un nou tipus de xarxa, les Xarxes de Processadors Genètics com Algoritmes Genètics Paral·lels, anomenats així per estar inspirats en els Algoritmes Genètics Paral·lels.

A nivell teòric, s'ha pogut demostrar la completitut computacional del model, amb el que la seua potència computacional es situa al mateix nivell que les màquines de Turing. Degut a aquest resultat i donada la gran similitud entre les NGP i els Algoritmes genètics Paral·lels, en aquest treball es demostra que aquestos també són un model computacional complet. D'altra banda, s'ha pogut realitzar una caracterització de la jerarquia de Chomsky utilitzant les NGP, aquest procés es realitza simulant cada una de les gramàtiques que defineixen les quatre famílies de llenguatges d'aquesta jerarquia observant el mínim nombre de processadors necessaris per a cada simulació, el que ens dóna una idea apreciable de la diferència de complexitat entre les diferents famílies.

No falta a aquest treball un estudi de la part més pràctica del model com la realització d'algunes tasques. Primer s'ha dissenyat i implementat un simulador que permet l'execució de Xarxes de Processadors Genètics a qualsevol de les seues tres varietats ací definides, com aceptores, com a generadores o com a Algoritmes Genètics Paral·lels, amb el que podem realitzar proves amb diferents problemes d'optimització. A continuació s'ha realitzat un estudi per vore si el nou model era capaç de resoldre problemes NP en un temps polinòmic, estudi que hem realitzat utilitzant el problema de saber si existeix algun cicle Hamiltonià en un graf. Finalment s'ha provat el simulador amb dos problemes d'optimització als que s'ha comprovat que té un bon comportament, els problemes utilitzats són el problema de la motxilla multidimensional i el problema del viatjant de comerç.