BrBRCEEn0101-74382002000300005

Transgenética computacional: uma aplicação ao problema quadrático de alocação

1. Introdução A Computação Evolucionária clássica baseia-se fortemente na utilização do paradigma neodarwiano da evolução gradual e estocástica. Um dos princípios dessa abordagem pode ser resumido pela frase: A natureza não dá saltos. Isso é, contudo, contestado por diversos autores (Marguli & Sagan, 1991; Bourguignon, 1989; Gould, 1993) que apresentam teorias complementares justificando outros mecanismos evolucionários. A Transgenética Computacional ' TC ' se baseia no emprego dessas abordagens mais recentes para construir seus algoritmos computacionais. A proposta amplia o escopo da computação evolucionária clássica pela inclusão de dois novos contextos: o epigenético e o intracelular, e pela utilização do paradigma procariótico de recombinação que é bastante propício à manipulação direta do código ADN e à consideração de informações ambientais ' dentro do processo de evolução.

A abordagem proposta é aplicada a um clássico problema NP-árduo da Otimização Combinatória, o Problema Quadrático de Alocação. Dadas duas matrizes quadradas de coeficientes reais MF = [fij] e MD = [dij], 1£i, j£n, o Problema Quadrático de Alocação consiste em encontrar:

determinando a permutação correspondenterno conjunto Sn de todas as permutações de {1, 2, ..., n}.

Uma das maiores aplicações do PQA é na teoria de localização, onde se deseja instalar facilidades em locais previamente determinados. Considerando-se fr(i)r (j) o fluxo de material que vai da facilidade r (i)para a facilidade r (j) e dij à distância da localidade i à localidade j, o objetivo é determinar o custo mínimo de atribuir, simultaneamente, as facilidadesr(i) e r (j) a pares de locais i e j, respectivamente. Cada custo resulta da soma dos produtos fr(i)r (j)dij, correspondente à alocação definida pela permutaçãorde nelementos. Çela (1998) apresenta um estudo detalhado desse problema.

Os fundamentos da abordagem proposta são apresentados na seção 2. A seção 3 apresenta a Transgenética Computacional. A seção 4 descreve as duas classes de algoritmos transgenéticos. A seção 5 apresenta uma aplicação da técnica ao Problema Quadrático de Alocação e reporta os resultados computacionais.

Finalmente, na seção 6 são apresentadas as conclusões do artigo.

2. Fundamentos da Abordagem A Transgenética Computacional, TC, é uma metaheurística que utiliza a infiltração planejada de informações como uma ferramenta do aperfeiçoamento das informações genéticas. Ela fundamenta sua ação em paradigmas do fluxo intracelular e através de agentes de informação que manipulam o contexto genético. As informações infiltradas através dos agentes são criadas e controladas com base no paradigma epigenético. As informações em formato não genético que são utilizadas para manipular o processo evolucionário são denominadas memes.Face à sua proposta de manipular e guiar o conteúdo genético, a TC utiliza-se de mecanismos mais simples de recombinação genética que imitam o paradigma procariótico de adaptação, isto é, a transferência de genes entre organismos procarióticos realizada através dos processos de transdução, transformação e conjugação (Shapiro, 1988). Os algoritmos da TC estão divididos em duas classes principais. A primeira é a classe dos Algoritmos Transgenéticos Extra-Intracelulares, ATEIs, que baseiam o seu processo evolucionário nos paradigmas extracelular, intracelular e epigenético. A segunda classe é a dos Algoritmos Proto-Gene, ProtoG, que desenvolvem seu processo evolucionário baseando-se apenas nos paradigmas intracelular e epigenético. Como conseqüência disso, o algoritmo ProtoG não realiza a chamada reprodução sexual como base para o compartilhamento de informações entre seus indivíduos.

O fluxo extracelular caracteriza-se pela troca de informações no contexto extracelular, ou seja, entre células. Os Algoritmos Genéticos, apresentados por Holland (1975), são técnicas clássicas da Computação Evolucionária para resolver Problemas de Otimização Combinatória. De modo geral os Algoritmos Genéticos (AGs) utilizam os chamados mecanismos de seleção, cruzamento e mutação para operacionalizar um processo de busca estocástica em um espaço de soluções. Esses mecanismos procuram copiar o processo natural de seleção e reprodução dos cromossomos na formação de novos indivíduos, codificando as soluções de um problema em um formato "cromossômico" e submetendo-as a um processo pseudoevolutivo que unifica estratégias de seleção e reprodução em um só estágio. Nessa estratégia a informação genética dos pais é combinada e repassada aos filhos, que são constituídos como novos indivíduos. Tal via de replicação e alteração genética é conhecia como extracelular (Kargupta, 1998).

O processo pseudoevolutivo assim modelado é simples e não implica em grandes obstáculos para a implementação computacional. Todavia, por suas simplificações, replica apenas uma pequena parte dos mecanismos que atuam na seleção das espécies (Lumsden & Wilson, 1981; Brooks & Wiley, 1986).

Por sua vez, o processo de transformação do ADN pode estar sujeito a pressões evolucionárias importantes que não se expressam pela via extracelular. Os seres procarióticos, por exemplo, utilizam uma forma não sexual para compartilhar informações genéticas que podem ser originadas de fissão binária, conjugação ou transdução (Campbell, 1996). A via imunológica e a transferência horizontal também representam outros caminhos para a alteração do ADN celular (Behe, 1996). As interações dessa via de transformação do ADN são ditas intracelulares.

As pressões adaptativas e evolucionárias, no entanto, não são exercidas somente através de contextos físicos. Os seres vivos estão sujeitos a pressões que emergem de interações mais sutis, relacionadas com os indivíduos da própria espécie, e esses, por sua vez, estão imersos em contextos ainda mais complexos ' as sociedades ' que possuem pressões evolutivas próprias. Alguns aspectos das pressões evolutivas que ocorrem fora do contexto genético são abordados em uma disciplina denominada epigenética. A cultura, como a biologia, exibe padrões de evolução ' exploração adaptativa e transformação de um espaço de informações através de variação, seleção e transmissão (Boyd & Richerson, 1985). No entanto a evolução cultural exibe padrões e regras de desenvolvimento diferentes da biológica. Os memes são unidades de informação que podem difundir-se por uma cultura, como os genes disseminam-se por um reservatório gênico (Wright, 2000). O termo "meme" foi sugerido por Dawkins (1976). Na definição de Dawkins um meme pode ser entendido como uma idéia.

A ligação entre genes e memes ocorre uma vez que os genes prescrevem as regras epigenéticas, que são regularidades da percepção sensorial e do desenvolvimento mental que animam e canalizam a aquisição da cultura. A cultura ajuda a determinar quais dos genes prescritos sobrevivem e se multiplicam de uma geração à próxima. Novos genes bem-sucedidos alteram as regras epigenéticas da população. As regras epigenéticas alteradas mudam a direção e a eficácia dos canais de aquisição cultural realimentando o processo de co-evolução gene x meme (Wilson, 1998).

A dificuldade de considerar a epigenética no contexto da Computação Evolucionária é discutida por Chattoe (1998). Na Computação Evolucionária os primeiros trabalhos dentro desse tema simplesmente associaram memes às informações obtidas fora do fluxo extracelular. Nos Algoritmos Meméticos, conforme definidos por Merz & Freisleben (1999) e Radcliffe & Surry (1994), o estágio epigenético é expresso, principalmente, através de um aperfeiçoamento dos cromossomos via procedimentos de busca local. Tais algoritmos também são denominados de Algoritmos Genéticos Híbridos (Houck et al., 1996). O atual trabalho propõe que os memes sejam definidos em conformidade com Plotkin (1996) que considera memes como informações codificadas e transmitidas através de meios não genéticos. Dessa forma, define- se um meme computacional como uma informação que possa ser utilizada para rearranjar um cromossomo ou um bloco de genes. A memética na TC será utilizada no sentido de criar um processo contínuo de obtenção e infiltração de informações para o interior do contexto genético. Além disso, os memes poderão estar sujeitos a processos de competição e seleção pertinentes ao meio cultural.

A informação memética no contexto computacional pode se originar de várias fontes tais como resultados teóricos conhecidos para um problema ou uma instância, heurísticas, análise de cenário, etc, constituindo um banco de memes ou uma base de memes a ser utilizada pelo algoritmo. O processo de infiltração memética no contexto genético é operacionalizado na TC através de agentes computacionais análogos a agentes do fluxo intracelular. As técnicas de manipulação intencional se baseiam nas utilizadas pela Engenharia Genética. A Engenharia Genética, EG, segundo Dudley (1990), é uma parte da ciência que estuda os mecanismos intracelulares de interação genética, bem como seu impacto sobre os organismos. Para facilitar o processo de manipulação a EG tem empregado agentes já existentes na natureza que se especializaram no uso do fluxo intracelular. Tais agentes são chamados de vetores, dentre os quais dois dos mais utilizados são os vírus e as partículas genéticas móveis.

A construção de uma metáfora computacional que imite de perto o paradigma biológico é uma pretensão extremamente ambiciosa e, na atualidade, supostamente fora do estado da arte. Apesar disso a TC caminha no sentido da proposta de Moreno (1986) que afirma que a única via para descrever um sistema auto- reprodutor e auto-organizado é unir duas formas de modelagem: a físico- experimental, aqui representada pelas ferramentas, regras e agentes do fluxo intra e extracelular, e a lógico-formal, aqui representada pelo contexto epigenético. Aceitando a premissa de Davies (1998) sobre o fato dos seres vivos poderem ser considerados sistemas de processamento de informações, a proposta da TC aprofunda seu contato com a realidade do mundo natural, porque entende que uma abordagem que se proponha a imitar uma metáfora deve evitar principalmente ser simplista. A metáfora está apoiada no uso de ferramentas de manipulação de cromossomos de modo intencional e planejado e na expressão dos memes através dos agentes do fluxo intracelular.

3. Transgenética Computacional A Transgenética Computacional é uma proposta multi-agente baseada em três idéias centrais: Infiltrar, de forma planejada, informações no processo evolucionário com o objetivo de informá-lo e guiá-lo.

<formula/>Planejar o processo de infiltração de informações e de construção de agentes através do uso do paradigma epigenético.

<formula/>Utilizar a recombinação procariótica como ferramenta complementar de preservação da informação genética.

A metáfora está apoiada no uso de ferramentas de manipulação de cromossomos de modo intencional e planejado e na expressão dos memes através dos agentes do fluxo intracelular. A figura_1 apresenta o fluxograma do ciclo evolucionário da TC. O bloco destacado no quadro resume as inovações introduzidas pela abordagem transgenética.

As regras epigenéticas são utilizadas para gerar propostas de manipulação ' os memes. O conjunto de memes forma um repositório, denominado banco de memes. Os memes, que a princípio são informações não genéticas, são codificados em agentes do fluxo intracelular que, inseridos no processo evolucionário, modificam os cromossomos alterando seus fenótipos. Os fenótipos modificados traduzem novas informações codificadas em meio genético. Tais informações podem gerar novos memes que podem conduzir a alterações nas regras epigenéticas, ou por elas serem selecionados e modificados. O quadro da co-evolução gene x meme caracteriza que o processo de replicação e seleção da informação engloba uma interação entre dois formatos diferentes de informação: genes e memes. O conceito de co-evolução foi introduzido por Paul Ehrlich & Peter Raven (1964) e está fundamentado na ocorrência de adaptações recíprocas entre duas populações (Bowles & Gintis, 1998). A evolução da população, no caso dos algoritmos transgenéticos, pode resultar apenas do processo de manipulação realizado pelos agentes, ou estar agregada simultaneamente a um procedimento de reprodução sexual. Esse fato é determinante para a construção das duas classes básicas de algoritmos da TC: os ProtoG e os ATEIs.

Para que os memes sejam expressos no meio genético são utilizados agentes de informação, chamados de agentes transgenéticos. Esses agentes são utilizados para representar a informação memética através de um código que permita que uma proposta de manipulação possa ser convenientemente expressa no contexto genético. Além disso, os agentes transportam os memes e operacionalizam processos de competição entre memes, e entre os memes e as informações contidas nos cromossomos da população. Um agente transgenético, portanto é composto por um ou mais memes e um método de manipulação, conforme ilustrado na parte relativa ao contexto epigenético na figura_2. O repositório de memes, base para a orientação do processo de manipulação, pode ser constituído com informações obtidas de várias fontes, tanto endógenas como exógenas ao processo evolucionário. Um meme pode ser carregado em um agente transgenético tanto no formato de um fragmento de ADN ' originando um bloco de montagem ' ou como uma regra de manipulação genética. As regras denominadas do "tipo 1" na figura_2 são as responsáveis pela tradução do meme para uma representação compatível com a finalidade do agente transgenético e seu método de atuação, definido pelas regras do "tipo 2".

Um cromossomo da população também pode ser considerado como fonte de obtenção de memes, uma vez que ele próprio pode ser pensado como uma proposta completa de organização. Conseqüentemente, de uma solução podem se originar propostas parciais para o re-arranjo de blocos de genes. A população pode, portanto, contribuir para a alteração do banco de memes e para mudanças na formação dos agentes. A co-evolução gene x meme, nesse caso, tem seus parâmetros de controle definidos pelas regras denominadas do "tipo 3". Os cromossomos, por sua vez, podem estar ou não sujeitos a um processo de recombinação no contexto extracelular, dependendo do algoritmo transgenético adotado.

O contexto intracelular permite ainda que a TC possa incorporar o que aqui será referenciado como "ruído". O "ruído" nos contextos intracelulares naturais provém de interferência ambiental aleatória. Através da utilização de agentes transgenéticos constituídos a partir de ruído, a abordagem pode se beneficiar do enriquecimento decorrente da incorporação de informações de diversificação.

Pode-se dizer que a TC é uma técnica de busca informada e co-evolucionária, onde genes e memes são atuadores simultâneos. Ela permite que diversas formas de informação sejam capazes de interagir em um processo de seleção guiado pela melhoria da adequação da população e pelo desempenho dos agentes.

Utilizando o paradigma de recombinação procariótica a TC pode dispensar, eventualmente, o efeito da diversificação genética introduzida pelos operadores de cruzamento, as regras de mutação, os procedimentos de migração, a elitização, etc.

3.1 Os memes na Transgenética Computacional Os agentes transgenéticos (a serem definidos no item 3.2) podem transportar tanto ruído como memes originados de um processo de planejamento definido por regras epigenéticas. Tais regras podem traduzir diversas informações de um problema considerado ou de uma instância específica. Por exemplo, as regras epigenéticas podem expressar informações de um limite inferior, de resultados heurísticos, de análise de características da população, etc. Os memes podem ser constituídos como blocos de montagem ou como procedimentos de manipulação.

Por exemplo, um limite bem conhecido para o PQA é dado pela relaxação que o transforma em um Problema de Alocação Linear, PAL (Abreu, 1984). Em termos da Teoria dos Grafos, essa relaxação corresponde a transformar um problema de alocação de vértices, o PQA, em um problema de alocação de arestas, o PAL. Tal relaxação resulta na solução ótima de qualquer instância de ordem 3. Assim, dado um PQA de ordem n, pode-se construir um meme escolhendo-se três cidades e três facilidades aleatórias e resolvendo o problema de alocação linear associado. Como resultado, tem-se uma solução parcial de comprimento 3 que pode compor um bloco de montagem, isto é, um segmento de ADN. Pode-se também implementar um processo de competição de memes, resolvendo-se para um determinado terno de cidades, todos os PALs associados a quaisquer alocações de três facilidades e escolhendo-se como vencedor, o meme que produzir o menor custo de alocação.

Para exemplificar a concretização de um meme como um procedimento de manipulação, considere ainda a regra epigenética "relaxar o PQA como PAL". Nesse caso, dado um certo cromossomo da população, escolhe-se ao acaso três cidades, verifica-se a alocação de facilidades para as cidades escolhidas em sua configuração e resolve-se o PAL correspondente.

3.2 Agentes da Transgenética Computacional Um agente transgenético pode ser composto por um ou mais memes e deverá possuir um método de operação. No presente trabalho são definidos dois agentes: Vírus e Partícula Genética Móvel.

O agente Vírus foi primeiramente definido no trabalho de Goldbarg et al. (1999) como um agente capaz de alterar diretamente a configuração cromossômica de um indivíduo e, conseqüentemente, sua adequação mantendo a integridade da informação transcrita ao longo de um certo número de iterações do algoritmo. Um Vírus, na metáfora transgenética, é uma cadeia de informação (I) associada a um método de Contaminação (F), e um método de Descontaminação (Ñ), formando uma triplaz = (I,F,Ñ).O processo que vai desde a avaliação da resistência do indivíduo até a invasão e transcrição no cromossomo hospedeiro é denominado contaminação. O processo que controla a extinção dos efeitos da transcrição é denominado descontaminação.

Considere P uma população de N indivíduos, P = {S1, S2,-188;, SN}, onde cada indivíduo Si, i=1,.., N, é uma cadeia ou um conjunto de valores inteiros de comprimento n representando uma solução do problema e f a função adequação que retorna um número real positivo na avaliação de cada indivíduo, onde:

A Contaminação é constituída basicamente de três etapas: ataque, transcrição e duração.

·Ataque (A) Trata-se de uma etapa de avaliação que visa decidir se o cromossomo alvo é sensível ou não a um determinado tipo de manipulação. Essa fase pode ser definida através da função A, A: Si ® {falso, verdadeiro}, i = 1,...,N, que determina a susceptibilidade do cromossomo ao ataque. Essa susceptibilidade depende de características inerentes ao Víruse ao próprio indivíduo. Se o resultado da futura manipulação atender a critérios pré-estabelecidos pelo projetista do algoritmo, então A(Si) = "verdadeiro", caso contrário o valor de A(Si)dependerá de um esquema imunológico de resistência ao ataque. Um exemplo de critério determinante da susceptibilidade à manipulação é a melhoria da adequação do cromossomo.

Na natureza o processo de contaminação por um microorganismo é um evento probabilístico, uma vez que os seres vivos possuem eficientes sistemas de defesa. Esse fato é considerado no modelo de contaminação artificial. No experimento computacional do atual trabalho foi utilizada a fórmula (01)

para determinar a aceitação das transcrições que redundem em diminuição da adequação do cromossomo. As variáveis Val e Val_Cont correspondem à adequação do indivíduo antes e depois da contaminação respectivamente, Média_Adequação é o valor médio das adequações dos indivíduos da população ebé um parâmetro de ajuste que visa tornar o esquema mais ou menos permeável à aceitação de transcrições que pioram a adequação, especialmente importante nos estágios iniciais da evolução da população. O valor de Pfoi comparado com um valor sorteado (Vsor) em uma distribuição uniforme no intervalo [0,1]. Se P>Vsor, então A(Si)="verdadeiro", em caso contrário A(Si)="falso".

No caso do denominador ser menor que o numerador então P=0. A fórmula (01) foi inspirada no trabalho de Moritz (1990) que descreve a difusão de memes em uma população de hospedeiros.

· Transcrição (G) Caso o cromossomo não apresente a necessária resistênciaao ataque viral, isto é A(Sj) = "verdadeiro", então a informação genética transportada pelo agente será transferida para o cromossomo de acordo com um certo Operador de Transcrição ( Gi ) pertencente ao conjuntoG de todos os s possíveis operadores de transcrição do Vírus. O resultado da transcrição é a formação de um novo cromossomo Sj', que incorpora a informação transportada pelo Vírus. Os indivíduos da população que sofrem alterações genéticas decorrentes da ação de um agente do fluxo intracelular são denominados manipulados. A manipulação decorrente da ação de um Vírus é uma transcrição onde:G=(G1,G2,...,Gs),Gi: sj®Sj'j=,...,N ·Duração (y) yé uma função que determina a permanência da transcrição tanto nas futuras gerações, quanto no cromossomo contaminado. Denominando por-um coeficiente que pondera a estratégia de equilíbrio intensificação x diversificação, e porWf(Si) a variação da função adequação caso a contaminação ocorra, então: y: W[Df(Si)] ®Z+ O sucesso da contaminação viral produz, via de regra, uma alteração na adequação do indivíduo. Além disso, pode produzir restrições nas regras reprodutivas no caso do algoritmo contemplar um processo evolucionário que utilize o fluxo extracelular. Para um cromossomo manipulado Sj'a cadeiatranscrita é considerada imutável durante todo o período de validade da contaminação. Em conseqüência os operadores de cruzamento, mutação e demais regras que por ventura sejam utilizadas na constituição evolucionária de blocos de montagem não poderão alterar a cadeia transcrita do Vírus, chamada de cadeia transgenética. A cadeia transgenética é um bloco de montagem geneticamente dominante. No caso do cromossomo manipulado ser submetido a reprodução sexual (ATEIs) pode ocorrer conflito entre as cadeias transgenéticas dos pais na geração de um filho. Nessa hipótese se faz necessário um critério para o desempate da dominância. No caso das implementações do presente trabalho a dominância transgenética foi sempre definida em favor da transcrição que acarretasse a melhor adequação para o cromossomo.

A descontaminaçãofaz cessar os efeitos da manipulação viral. Decorrido o prazo especificado pela funçãoyo cromossomo é liberado de suas restrições, voltando a apresentar um comportamento algorítmico irrestrito. Essa liberação, dependendo do tipo de agente de manipulação utilizado, poderá exigir uma operação específica. O operador responsável por colocar o indivíduo livre das restrições impostas por um agente de manipulação é denominado Operador de Alta (Pi) onde:

Para exemplificar o conceito de Vírus será descrito um dos tipos existentes chamado de vírus esquema, utilizado nos algoritmos do presente trabalho.

O Vírus Esquema (Ve) transporta uma cadeia de informações no formato de bloco de montagem, ou seja uma solução parcial. No caso do PQA, o vírus esquema carrega uma cadeia do tipo pares de alocação cidade x facilidade. Considere a instância Nug5 (Nugent et al., 1968) representada pelas matrizes mostradas na figura_3.

Uma solução para uma instância do PQA de ordem n pode ser representada como uma permutação de n na qual o elemento j na i-ésima posição da permutação representa a facilidade que foi atribuída à localidade i. Por exemplo, para a instância Nug5 que é de ordem 5, a solução representada pela permutação (3 2 4 1 5) é aquela na qual as facilidades 3, 2, 4, 1 e 5 foram atribuídas às localidades 1, 2, 3, 4 e 5, respectivamente. Considere o cromossomo S1 = (1 3 4 5 2) com adequação igual a 89 dada pelo valor da função objetivo e um vírus esquema <formula/> carregado com um meme de comprimento 2 representando os pares (1,4) e (4,4) de alocação cidade x facilidade. A figura_4 mostra a transcrição de em S1. Essa transcrição implica fixar os pares representados na cadeia do vírus na configuração do cromossomo. O método de operação do vírus estabelece a forma pela qual o cromossomo será reorganizado de modo a comportar a sua cadeia. No caso exemplificado na figura_4 o operador de transcrição executa operações de 2-troca para inserir a cadeia requerida. A transcrição do vírus implica em uma nova configuração para o cromossomo, S1' = (3 1 5 4 2) com adequação igual a 70. Como a transcrição do vírus melhora a adequação do cromossomo, então A(S1) = "verdadeiro" e S1 é transformado em S1'.

Devido à variedade de tipos e representações possíveis para a informação no formato não genético, é indispensável que existam tipos específicos de vírus que possam incorporar os diferentes métodos necessários à tradução dessa informação em formato genético. Outros exemplos de vírus podem ser encontrados nos trabalhos de Goldbarg & Gouvêa (2000, 2001).

Kubota et al. (1996) e Fukuda et al. (1999) apresentam um algoritmo denominado VEGA ' Virus Evolutionary Genetic Algorithm onde usam também o conceito de Vírus. Os autores utilizam a mesma terminologia, contudo não é possível traçar um paralelo entre esse trabalho e a proposta da TC. VEGA é um algoritmo que trabalha com duas populações ' uma de vírus e outra de hospedeiros. Basicamente os vírus são gerados a partir de subcadeias dos cromossomos e possuem dois operadores: de transcriptase reversa e transdução. A transcrição realizada pelo denominado agente "vírus" pode ser desfeita imediatamente após a sua realização pelo processo de cruzamento dos cromossomos. O trabalho dos autores citados representa uma pequena modificação da proposta dos Algoritmos Genéticos, uma vez que o trabalho dos vírus é fundamentalmente realizar operações parciais de cruzamento, ou seja, são agentes que operacionalizam uma forma especial de operador para as cadeias da população. O trabalho de Fukuda não desenvolve o conceito de "resistência" imunológica como presentemente apresentado, nem elabora o conceito de infiltração de informação pela via intracelular. Além disso, a TC é uma técnica de manipulação planejada que não depende da existência de um algoritmo genético de substrato, uma vez que pode desenvolver seu processo evolucionário exclusivamente com base no paradigma de recombinação procariótica.

Outro agente utilizado neste trabalho é a Partícula Genética Móvel. As partículas genéticas móveis são tipos especiais de vírus esquema. Na natureza, elementos genéticos móveis são fragmentos de ADN que podem ser fagocitados pelas células, acabando por se integrar ao ADN do núcleo. No contexto computacional define-se uma PGM como um agente constituído por uma cadeia de informação (I) e um método de contaminação (C), formando uma dupla PGM = (I, C). A PGM não possui método de descontaminação uma vez que sua cadeia, quando transcrita, não é tornada inviolável, isto é, não fixa a informação transcrita como geneticamente dominante. A regra de resistência imunológica ao ataque da PGM é a da estrita melhoria da adequação. Os operadores de transcrição são semelhantes aos operadores dos Vírus. Portanto, uma PGM pode ser considerada como um caso especial de vírus esquema com tempo de vida igual a zero e critério guloso de resistência imunológica. As PGM podem representar um vetor extremamente eficiente e simples para o transporte de informações. Por não obrigarem que a inviolabilidade de uma certa transcrição seja mantida, permitem ao processo de busca uma maior liberdade de diversificação. Esses agentes constituem a base do paradigma de manipulação proposto pelo algoritmo Proto- Gene.

A idéia da imunologia na TC está representada no fato da população de cromossomos ser capaz de resistir à manipulação dos agentes em função do desenvolvimento do processo evolucionário e da proposta de manipulação do agente. O efeito imunológico é uma ferramenta para operacionalizar a co- evolução agentes x população de cromossomos. Na medida em que as iterações do processo evolucionário se seguem, a população vai se tornando resistente às cepas de um crescente número de agentes transgenéticos. As informações do banco são atualizadas por informações que vão sendo geradas na população de cromossomos durante o processo evolucionário, criando novas e mais eficientes cepas de agentes que mesclam informações exógenas e endógenas. Quando a população se torna extremamente resistente a todas as manipulações propostas pelos agentes, o algoritmo converge por resistência imunológica da população.

4.Algoritmos Transgenéticos O presente trabalho aborda duas possibilidades de compor o processo de manipulação transgenética. A primeira utiliza as três vias de evolução consideradas pela TC. Tais algoritmos são denominados Algoritmos Transgenéticos Extra-Intracelulares (ATEIs). Uma segunda classe utiliza-se somente da evolução memética e da evolução por recombinação procariótica. Essa classe é denominada Proto-Gene (ProtoG). Nela os cromossomos atendem ao paradigma de recombinação procariótica sendo exclusivamente expostos a ataques de agentes do fluxo intracelular. Os ProtoG, portanto, propõem que a manipulação via agentes seja o único mecanismo de compartilhamento e difusão de informações no processo evolucionário.

Os Algoritmos Transgenéticos permitem que vários níveis de competição sejam viabilizados no contexto do processo evolucionário. Conforme descrito no item 3.1, memes podem competir para formar agentes. Também, diversos agentes podem competir para transcrever sua informação em um cromossomo. Uma competição no contexto dos agentes é um processo de concorrência que julga o efeito de várias propostas de manipulações pretendidas. Os critérios de julgamento podem incluir a melhoria na adequação dos cromossomos ou outros tais como uma maior alteração da configuração cromossômica. Finalmente, um agente compete com a informação já incorporada nos cromossomos. A fórmula (01) representa um modelo para o julgamento dessa competição. Agentes vencedores nessa etapa conseguem a transcrição.

4.1 Algoritmos Transgenéticos Extra e Intracelular (ATEIs) De uma forma geral pode-se descrever os ATEIs como nos quadros_I e II, sendo eles de três tipos básicos: ATEI, ATEI-I e ATEI-IT. As setas marcam os passos que correspondem aos de um algoritmo genético clássico. Não há necessidade, porém, da inclusão da mutação, uma vez que os agentes transgenéticos, se requerido, podem ser projetados especificamente para promover a diversificação.

O quadro_I descreve um ATEI que não comporta evolução imunológica, ou seja, o banco de memes desse algoritmo não é atualizado com informações geradas na população. Cabe ressaltar que as informações geradas no processo evolucionário não são apenas as geradas nas novas configurações de cromossomos que surjam na população. Tais informações podem, por exemplo, advir do controle de diversidade na população. No caso específico do PQA, pode-se detectar que um certo par cidade x facilidade não está representado ou possui pouca representação na população. O quadro_II descreve um ATEI que possui um critério para atualização do seu banco de memes durante o processo evolucionário. O ATEI-IT é basicamente igual ao ATEI-I, com a diferença que existe competição entre os agentes para o ataque a um cromossomo (conforme é mostrado no item 5.3). Para tornar simples a descrição do algoritmo, o critério adotado é o surgimento de uma solução melhor que todas as existentes até uma determinada iteração do algoritmo.

4.2 Algoritmos Proto-Gene (ProtoG) Uma metáfora adequada à descrição do ProtoG é a da "sopa primordial" ou o caldo de aminoácidos do oceano primitivo. Nesse algoritmo os cromossomos são expostos a um ataque direto dos agentes do fluxo intracelular que devem competir entre si e com as defesas dos cromossomos para concretizarem a transcrição de seus códigos. Nesse cenário evolucionário existe um grande espaço para construção de um processo de competição entre agentes do fluxo intracelular e aberto à inclusão do ruído.

Os Algoritmos ProtoG são compostos de duas fases. A primeira inclui a obtenção de memes e a construção dos agentes. Na segunda fase, os agentes carregados com os memes vencedores do processo de competição na primeira fase, atuam sobre os cromossomos da população tentando introduzir suas informações. Também na segunda fase ocorre o ataque dos agentes carregados com ruído. A cada iteração, um ou mais agentes percorrem a população manipulando os cromossomos sensíveis.

No caso do surgimento de uma informação de boa qualidade, o algoritmo poderá realimentar o banco de memes com informações derivadas desse código genético. A Figura_5 mostra um quadro geral da arquitetura dos algoritmos ProtoG, resumindo as duas fases e sua interação.

Os algoritmos ProtoG podem ser descritos, de uma forma geral, como apresentados no quadro_III.

Para esclarecer a execução dos passos descritos no quadro_III será apresentado um exemplo numérico considerando uma aplicação ao Problema do Caixeiro Viajante, PCV, sobre o grafo G=(N,A) caracterizado pela matriz de distância mostrada na tabela_1.

Supondo que algumas das regras epigenéticas do contexto epigenético sejam: 1. Incluir no banco de memes estruturas de conexão minimal ' Árvores Geradoras Mínimas.

2. Incluir no banco de memes as estruturas genéticas dos melhores indivíduos da população.

3. Selecionar as estruturas que vão fornecer as cadeias que serão transportadas pelos agentes transgenéticos através de critérios convenientes de competição.

4. Selecionar, através de critérios convenientes de competição, as cadeias que serão escolhidas como memes de manipulação.

5. Utilizar cadeias de comprimento C, C £ 2, para formar os memes dos agentes transgenéticos.

6. Utilizar a Partícula Genética Móvel como agente de manipulação.

Os passos do quadro_III podem ser assim calculados: <formula/>Carregar um Banco de Memes.

Conforme as regras anteriores, o banco de memes poderá conter blocos de uma Árvore Geradora Mínima (AGM) e de um ou mais dos melhores indivíduos da população. Neste exemplo o passo 1 poderia representar a colocação dos códigos abaixo transcritos e representados por seqüências de arestas, em que, para o primeiro passo do algoritmo, o melhor indivíduo é obtido por uma busca na população de cromossomos. Denominado por Estrutura_Global_1 o melhor indivíduo da população tem-se, por exemplo: Estrutura_Global_1: (4-5)(5-6)(6-8)(8-2)(2-1)(1-3)(3-7)(7-9)(9-4). A adequação é dada pelo somatório dos pesos das arestas do ciclo que é igual a 77.

Estrutura_Global_2: (2-3)(3-8)(8-4)(8-7)(7-1)(7-9)(7-5)(5-6) obtida de uma AGM do grafo que representa a instância estudada. O valor dessa árvore é 35.

<formula/>Gerar e avaliar uma população inicial de cromossomos.

Supondo que a população inicial seja gerada aleatoriamente, pode-se considerar que os seguintes cromossomos, além do melhor indivíduo anteriormente listado em Estrutura_Global_1 fazem parte da população: Cromossomo_1: (1-2)(2-3)(3-4)(4-5)(5-6)(6-7)(7-8)(8-9)(9-1) com adequação igual a 78.

Cromossomo_2: (3-9)(9-4)(4-5)(5-8)(8-1)(1-6)(6-2)(2-7)(7-3) com adequação igual a 108.

<formula/>Gerar um agente através de competição de memes do banco.

O primeiro nível de competição do algoritmo é caracterizado pela seleção das estruturas que serão utilizadas como doadoras de memes. Supondo que a estrutura Hamiltoniana de melhor adequação e a AGM do banco com menor grau fossem selecionadas, as cadeias mostradas na tabela_2 poderiam ser obtidas para compor a proposta de manipulação da partícula genética móvel. Cada cadeia possui comprimento 2 e seu valor é calculado pelo somatório dos pesos das arestas que a compõem.

Supondo agora que o critério de seleção das subcadeias fosse o menor custo, nesse caso o meme vencedor seria a cadeia (3-8)(8-7), com valor 6. Pode-se observar que a cadeia selecionada coincide, por motivos fortuitos, com as duas menores arestas do grafo.

<formula/>  Se o cromossomo é sensível à manipulação então A verificação da sensibilidade dos cromossomos à manipulação da PGM é realizada a partir do cálculo do benefício causado pela possível transcrição, conforme prevê o método de atuação das PGM. Considerando-se ainda que a PGM incorpora um procedimento simples de transcrição, com base na permutação da cadeia do cromossomo ' válido para o caso do grafo completo ' então, são possíveis as seguintes transcrições do meme vencedor sobre os dois cromossomos da população selecionados para exemplificar o procedimento.

No cálculo da adequação dos cromossomos da figura_6 está sendo considerada a aresta de retorno (9-1) e (7-3) e (3-9). O operador de transcrição utilizado pela PGM da figura 9 encontra o vértice intermediário da PGM no cromossomo atacado e simplesmente introduz a cadeia da PGM a partir de seu vértice central, eliminando de suas posições originais no cromossomo, os vértices que constam da PGM.

5.Resultados Computacionais

A abordagem da TC foi testada através do desenvolvimento e implementação de quatro algoritmos transgenéticos aplicados ao Problema Quadrático de Alocação.

Utilizou-se como banco de testes as instâncias do QAPLIB (QAPLIB, 2000) com tamanho maior ou igual a 20. Embora exista um número grande de instâncias do PQA na literatura, não se conhece um método para diferenciá-las em relação a sua dificuldade de solução. Alguns autores apresentaram trabalhos que visam estabelecer uma medida de dificuldade de solução de uma instância do PQA por um algoritmo Branch-and-bound (Vollman & Buffa, 1966; Abreu et al., 2002).