ALGORITMOS GENÉTICOS: ORIGEM E EVOLUÇÃO


Luiz Satoru Ochi

Introdução

O Problema de Steiner em Grafos Direcionados (PSGD)

O Problema do Caixeiro Viajante (PCV)

Algoritmos Genéticos Convencionais

Algoritmos Genéticos Convencionais: Comentários

Um Modelo de um Algoritmo Genético não Convencional

Um Algoritmo Genético não Convencional (AGNC)

Avaliação dos Algoritmos Genéticos Propostos

Algoritmos Genéticos Paralelos

Um Algoritmo Genético Paralelo

Migração de Cromossomos e Terminação

Literatura

Bibliografia


INTRODUÇÃO


A solução de problemas de elevado nível de complexidade computacional (NP- Completo, NP-Árduo) tem sido um desafio constante para os pesquisadores de diversas áreas. Particularmente em Otimização, Pesquisa Operacional, Ciência da Computação, Matemática e Engenharias, nos defrontamos freqüentemente com problemas altamente combinatórios, cuja solução ótima em muitos casos ainda está limitada somente a pequenas instâncias.

Os métodos tradicionais de otimização exata se caracterizam pela rigidez de seus modelos matemáticos representados através de seus Teoremas, dificultando a representação de situações reais cada vez mais complexas e dinâmicas. O problema desta falta de flexibilidade foi um pouco reduzido a partir do momento em que se passou a associar técnicas de Otimização com ferramentas de Inteligência Artificial, mais especificamente, com as ferramentas de busca heurística. De fato, os algoritmos heurísticos, ou simplesmente heurísticas, se caracterizam pela sua flexibilidade e têm como objetivo encontrar soluções de boa qualidade num tempo computacional suportável.

Contudo, as heurísticas isoladamente também possuem suas limitações, e a principal delas é a deficiência histórica de, em muitos casos, não conseguirem superar as armadilhas dos ótimos locais em Problemas de Otimização. Além disso, a falta de uma base teórica dos métodos heurísticos produz algoritmos muito especializados. Ou seja, apesar de sua flexibilidade em incorporar novas situações, o seu desempenho pode oscilar muito com modificações, mesmo pequenas, no problema analisado.

Portanto, a reunião dos modelos rígidos da otimização com os métodos flexíveis da busca heurística proporcionou o surgimento dos chamados Métodos Inteligentemente Flexíveis, que procuram o desenvolvimento de técnicas dotadas de uma certa rigidez matemática e com facilidades em incorporar novas situações, sem no entanto emergir numa flexibilidade às vezes caótica encontrada em métodos heurísticos.

Os anos 80 marcam o surgimento de artigos sobre novos métodos heurísticos com ferramentas adicionais para tentar superar as limitações das heurísticas convencionais. Dentre as várias técnicas produzidas para tentar reduzir o risco de paradas prematuras, destacamos : as Redes Neurais Artificiais (RNs), Simulated Annealing (SA), Tabu Search (TS), GRASP e a Programação Evolutiva incluindo: os Algoritmos Genéticos (AGs) inicialmente propostos por Holland (1975) [1], o Scatter Search (SS), proposto por Fred Glover (1977) [2], a Programação Genética, proposta por Koza (1990) [3], e a Programação Evolutiva proposta por Fogel (1966) [4].

Embora com filosofias distintas, estas metaheurísticas possuem em comum características que as distinguem das heurísticas convencionais, como por exemplo, incluir ferramentas para tentar escapar das armadilhas dos ótimos locais e a facilidade para trabalhar em ambientes paralelos. Dentre estas técnicas, os Algoritmos Genéticos têm se destacado na solução de uma gama de problemas devido a sua simplicidade e sua facilidade em resolver problemas sem exigir muito conhecimento prévio destes.

Os Algoritmos Genéticos (AGs) são algoritmos probabilísticos e foram inicialmente propostos pelo Professor John Holland (1975) [1a] da Universidade de Michigan, mas somente a partir dos anos 80, é que realmente começaram a se popularizar.

A idéia inicial de Holland (1975) [1b] foi tentar imitar algumas etapas do processo de evolução natural das espécies incorporando-as a um algoritmo computacional.

Basicamente, o ponto de referência foi gerar a partir de uma população de cromossomos, novos cromossomos com propriedades genéticas superiores às de seus antecedentes. Esta idéia foi então associada a soluções de um problema onde, a partir de um conjunto de soluções atuais, são geradas novas soluções superiores às antecedentes, sob algum critério pré-estabelecido.

Inicialmente vamos descrever resumidamente o Problema de Steiner em Grafos Direcionados e o Problema do Caixeiro Viajante que serão utilizados como aplicações neste texto. 


O PROBLEMA DE STEINER EM GRAFOS DIRECIONADOS (PSGD)

Este problema é uma generalização do Problema de Steiner em Grafos Simétricos (PSG), já que um grafo não direcionado, mediante a substituição de cada aresta por dois arcos direcionados de igual custo, pode ser transformado num dígrafo. No PSGD além disso considera-se mais um elemento: a raiz (r) do dígrafo.

Figura 1: Exemplo de uma (r) - arborescência geradora

Seja D = (V,E) um dígrafo conexo com raiz r Î V. Cada arco (i,j) Î E tem associado um custo cij ³ 0. O conjunto de nós V é particionado como V = {r} È Vo È S onde Vo é o conjunto de nós obrigatórios ou demanda e S é o conjunto de nós optativos. O objetivo do PSGD consiste em encontrar caminhos de r até cada nó k Î Vo tal que o custo total dos arcos pertencendo a esses caminhos seja mínimo. Em outras palavras queremos encontrar uma arborescência T com raiz r de custo mínimo a qual alcance todos os nós de Vo podendo utilizar os nós de S que forem necessários. O conjunto S* Í S de nós optativos que participam da solução é chamado o conjunto de nós de Steiner. A arborescência mínima do grafo gerado por {r} È Vo È S* é chamado r-arborescência de Steiner. Na figura 2 ilustramos um exemplo de PSGD onde: Vo = {1, 2, 3, 4}, S* = {5, 6, 7, 8, 9} e a r-arborescência de Steiner mínima T = { (r,7), (7,3), (3,6), (6,4), (7,9), (9,1), (8,5), (5,2) } com custo total 27 é mostrada pelos arcos em negrito .

Observe que se |Vo| = 1, então o PSGD se reduz ao clássico Problema do Caminho Direcionado de custo mínimo. Se |Vo| = |V|-1, então o PSGD é o Problema da r-arborescência geradora de custo mínimo.  


O PROBLEMA DO CAIXEIRO VIAJANTE(PCV)


fig2.gif (5982 bytes)

Figura 2: Uma instância do PSGD

O PCV pode ser descrito da seguinte forma: Dado um conjunto de n cidades N = { 1, 2, 3, ......, n}, e uma matriz de distâncias ligando cada par de cidades de N, o objetivo do PCV é partir de uma cidade origem, visitar uma única vez cada uma das n-1 cidades restantes e retornar à cidade origem minimizando a distância total percorrida.  


ALGORITMOS GENÉTICOS CONVENCIONAIS


A estrutura básica dos primeiros modelos de um Algoritmo Genético (aqui denotado Algoritmo Genético Convencional ou simplesmente AG) é formada pelas seguintes etapas:

· Representação de uma solução na estrutura de cromossomo

· Construção de uma população inicial de cromossomos.

· Um mecanismo de avaliar os cromossomos segundo suas aptidões.

· Um mecanismo de reprodução de cromossomos - Operador Genético.

· Definição de parâmetros de uma AG.

REPRESENTAÇÃO DE UMA SOLUÇÃO NA ESTRUTURA DE UM CROMOSSOMO:  Os Algoritmos Genéticos, na sua forma original (AGs convencionais), trabalham normalmente com uma representação binária (zero-um) para associar uma solução/ou componentes de uma solução do problema abordado.

Embora esta representação tenha se mostrado eficiente para vários problemas, observou-se à medida que foram crescendo as aplicações de AGs, que em diversos problemas com um elevado número de restrições, esta representação pode não ser a mais adequada, surgindo daí alternativas, por exemplo, a representação por inteiros, onde um cromossomo é descrito por um vetor de números inteiros.

Independentemente do tipo de representação selecionada, devemos sempre verificar se a representação está corretamente associada com as soluções do problema analisado. Ou seja, que toda solução tenha um cromossomo associado e reciprocamente que todo cromossomo gerado pelo AG esteja associado a uma solução válida do problema analisado.

Um exemplo mostrando os prós e contras da representação binária pode ser ilustrado com dois problemas de Otimização: O Problema do Caixeiro Viajante (PCV) e o Problema de Steiner em Grafos (PSG). No PCV com n = 5 cidades (N = { 1, 2, 3, 4, 5}) onde a cidade origem é dada por i = 1, uma solução viável do tipo S = (1, 2, 3, 4, 5, 1) pode ser representada por um vetor cromossomo da forma: p = ( 001; 010; 011; 100; 101) , onde cada gene (posição) do cromossomo p está associado a um número inteiro de um a cinco codificado na forma binária ou como uma cadeia de é log2 n ù bits . Portanto um cromossomo com n genes é um cadeia de tamanho n é log2 nù . No cromossomo p, é suposto implicitamente que após a cidade i = 5, retorna-se à cidade origem i = 1 como requer uma solução viável do PCV.

A dificuldade deste tipo de representação é no momento de gerar novos cromossomos viáveis, como mostraremos mais adiante. Neste momento só podemos antecipar que um algoritmo genético poderia gerar soluções contendo algumas seqüências de três bits tais como: 000; 111; 110 representando respectivamente os números inteiros: 0, 7, 6 que não estão associados a soluções válidas deste PCV com n = 5 cidades.

Para o PCV, veremos que a representação por números inteiros é a mais adequada. De fato, a solução S = (1, 2, 3, 4, 5, 1) poderia estar associada a um cromossomo p = ( 1, 2, 3, 4, 5), onde o número associado a cada gene do cromossomo representa uma cidade do PCV.

Por outro lado, considere um Problema de Steiner em Grafos onde N = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} representa o conjunto de nós do grafo simétrico associado e S = { 2, 5, 6, 9} o conjunto de nós optativos(facultativos ou candidatos a pontos de Steiner).

Neste caso, uma solução viável do PSG utilizando os nós i =2, i=5 e i=6 como pontos de Steiner pode ser associado facilmente a um vetor de zero/um da forma: p = ( 1, 1, 1, 0). Observe que a posição do cromossomo ocupada por um número zero implica que o ponto optativo associado não é utilizado nesta solução, enquanto uma posição (gene) com valor um implica em dizer que o ponto optativo associado está sendo utilizado pela solução construída. Ou seja, para o PSG, a representação binária é eficiente e o processo de associar um cromossomo com uma solução do PSG é trivial.

CONSTRUÇÃO DE UMA POPULAÇÃO INICIAL DE CROMOSSOMOS:  O problema de gerar uma população inicial de cromossomos num AG normalmente não é uma tarefa das mais difíceis. Pelo contrário, em muitos problemas esta tarefa é muito simples. Por exemplo, no PCV com n cidades, gerar k soluções viáveis na estrutura de k cromossomos usando uma representação por números inteiros significa gerar k vetores com n números inteiros distintos de 1 até n . Neste caso, podemos construir aleatoriamente estes k cromossomos viáveis.

Para o PSG, com t pontos optativos S = { 1 2 3 4 5 6 ....t} , o procedimento é o mesmo, neste caso, podemos pensar em utilizar uma estrutura na forma de um vetor com t posições (genes) associado aos t pontos optativos.

Utilizando representação binária, podemos gerar aleatoriamente k cromossomos válidos para o PSG, como ilustrado a seguir:Considere o vetor de referência R = ( 1 2 3 4 5 6 7) indicando os t = 7 pontos optativos de um PSG, e k vetores de tamanho t = 7 com componentes zero/um gerados aleatoriamente representando k soluções do PSG:

R = (1 2 3 4 5 6 7)

P1 = ( 1 1 0 0 0 1 1)

p2 = ( 0 0 1 1 0 0 1)

p4 = ( 0 1 1 1 0 1 0)

p5 = ( 1 1 1 0 0 0 1)

.

.

.

pk = ( 1 1 0 0 0 0 0)

Em problemas onde a geração de uma população inicial não é tão imediata como nos dois problemas aqui citados, normalmente se costuma usar heurísticas simples e rápidas para esta tarefa.

AVALIAÇÃO DOS CROMOSSOMOS NUM AG   Avaliar um cromossomo num AG significa determinar o seu nível de aptidão de sobrevivência. Ou seja, num AG sobrevivem prioritariamente os cromossomos mais aptos.

Em problemas de Otimização, o critério de sobrevivência pode ser determinado pelo valor da sua função objetivo avaliado pelo cromossomo analisado.

Por exemplo no PCV com n = 5 cidades ilustrado anteriormente onde a distância entre as cidades (i, j) é dado por dij, um cromossomo p1 = ( 1 2 3 4 5) possui um custo associado igual à soma das distâncias: D = d12 + d23 + d34 + d45 + d51, neste caso, quanto menor for o valor de D, maior será o nível de aptidão do cromossomo.

No caso do PSG, se tivermos o conjunto Vo de pontos obrigatórios e S = ( 1 2 3 4 5 6 7) indicando os t = 7 pontos optativos, um cromossomo p1 = ( 1 1 0 0 0 1 1) implica que estaremos utilizando o seguinte conjunto de pontos de Steiner S* = ( 1, 2, 6, 7).

Portanto o custo associado ao cromossomo p1 será dado pelo custo da árvore geradora(no caso do PSG simétrico) ou pelo custo da r- arborescência (no caso de PSGD) do grafo formado pelos pontos de Vo È S*(ou VoÈ S*È {r}para o PSGD).

MECANISMO DE REPRODUÇÃO - OPERADOR GENETICO:   O operador genético representa o núcleo de um AG. O objetivo básico de um operador genético, é produzir novos cromossomos que possuam propriedades genéticas superiores às encontradas nos pais.

Em Algoritmos Genéticos Convencionais, os operadores genéticos clássicos são: a mutação e o crossover.

O operador mutação altera um ou mais genes de um cromossomo de acordo com uma função de probabilidade.

Exemplo: Suponha um cromossomo p = ( 1 1 1 0 0 0 1 0) = ( p1, p2, p3, p4, p5, p6, p7, p8) e suponha que os genes p1 e p5 foram escolhidos para a mutação. Neste caso, aplica-se uma função probabilidade para p1 e para p5, caso esta função forneça um valor maior que um mínimo pré-estabelecido, modifica-se o valor de p1 e p5 respectivamente para p1 = 0 e p5 = 1, obtendo um cromossomo filho (offspring) p1 = ( 0 1 1 0 1 0 1 0).

O operador crossover clássico consiste em gerar um ou dois cromossomos filhos(offsprings) a partir das informações dos dois cromossomos pais (parents). Suponha dois cromossomos

P1 = ( 1 1 0 | 0 1 1 0) = ( p11 p12 p13 | p14 p15 p16 p17)

p2 = ( 0 1 1 | 1 0 1 1) = ( p21 p22 p23 | p24 p25 p26 p27)

No operador crossover inicialmente determinamos um ou mais cortes entre dois genes adjacentes de cada cromossomo pai. No nosso exemplo, o corte foi feito entre os genes p3 e p4. A seguir são gerados dois novos cromossomos o 1 e o2 reunindo os genes à esquerda do corte de p1 ( p11 p12 p13) reunidos com os genes à direita do corte de p2 ( p24 p25 p26 p27) para formar o1 e os genes à esquerda do corte de p 2 (p21 p22 p23) reunidos com os genes à direita do corte de p 1 (p14 p15 p16 p17) para formar o2.

o1 = ( 1 1 0 1 0 1 1) = ( o11 o12 o13 o14 o15 o16 o17)

o2 = ( 0 1 1 0 1 1 0) = ( o21 o22 o23 o24 o25 o26 o27)

A eficiência de um operador genético crossover muitas vezes está relacionada com o tipo adequado de representação utilizado. Por exemplo, se utilizarmos uma representação binária num PCV, como ilustrado anteriormente, podemos gerar com freqüência soluções inviáveis como mostra a ilustração a seguir:

Considere dois cromossomos viáveis de um PCV com n = 5 cidades N = { 1, 2, 3, 4, 5 }.

p1 = ( 001 010 | 011 100 101)

p2 = ( 011 100 | 001 101 010)

Neste caso, efetuando um corte entre os genes 2 e 3 de p1 e p2 respectivamente e aplicando o operador crossover, obteremos dois novos cromossomos filhos:

o1 = ( 001 010 | 001 101 010)

o2 = ( 011 100 | 011 100 101)

Os dois cromossomos o1 e o2 não são viáveis para o PCV, pois em o1 as cidades 1= 001 e 2 = 010 estão presentes duas vezes enquanto as cidades 3 = 011 e 4 = 100 não são visitadas. Da mesma forma, em o2, as cidades 3 = 011 e 4 = 100 são visitadas duas vezes enquanto as cidades 1 = 001 e a cidade 2 = 010 não são visitadas.

Este resultado mostra a ineficiência deste tipo de representação (binária) para determinados tipos de problemas tais como o PCV utilizando o operador crossover clássico.

Nos AGs os dois cromossomos clássicos, mutação e crossover, são normalmente utilizados conjuntamente. Em cerca de 80% das reproduções são utilizados o operador crossover e um pequeno percentual destinado ao uso do operador mutação. Normalmente o operador mutação é utilizado dentro de um AG para permitir uma diversificação no processo de busca, tentando com isso escapar de ótimos locais em problemas de otimização.

Estes dois mecanismos de reprodução no entanto, embora muito simples e genéricos, mostraram ser limitados para vários problemas de elevada complexidade como por exemplo problemas de otimização com vários pontos de ótimo local. A experiência tem nos mostrado que nestes casos estes operadores clássicos muitas vezes não analisam muitas regiões promissoras onde podem estar localizadas as melhores soluções do problema tratado.

DEFINIÇÃO DE PARÂMETROS EM UM AG:  Dentro de um AG, existe um conjunto de parâmetros e critérios a serem definidos no momento da implementação. Por exemplo, deveremos definir:

· O tamanho de uma população

· A seleção dos cromossomos reprodutores.

· O critério de sobrevivência dos cromossomos.

· O critério de parada de um AG.

A definição destes e de outros parâmetros depende de cada autor, mas normalmente nos modelos convencionais de AGs costumam-se adotar critérios "padrões" como explicado a seguir.  


ALGORITMOS GENÉTICOS CONVENCIONAIS: COMENTÁRIOS


Os algoritmos genéticos na sua forma original (convencional) utilizam normalmente uma representação binária para codificar uma solução de um problema na estrutura de um cromossomo. Esta representação, não é a mais eficiente para diversos problemas de otimização, tais como o problema do caixeiro viajante (PCV), como mostrado anteriormente.

Além disso, o processo de seleção de cromossomos reprodutores é muitas vezes aleatório e utiliza mecanismos de mutação aleatória e/ou crossover para a fase de reprodução de novos cromossomos. Ainda na versão original, o critério de sobrevivência de cromossomos é definido a partir de uma função que mede o nível de aptidão de cada cromossomo; e um cromossomo filho ( offspring ) somente ocupa o lugar do pai se este for considerado superior segundo esta função de aptidão.

Os mecanismos assim definidos não são eficientes na solução de diversos problemas complexos de otimização combinatória; em parte pelas próprias deficiências no processo de busca causadas pela escolha aleatória de reprodutores e pela formação prematura de uma população homogênea causada pelo critério de escolha dos cromossomos sobreviventes. Um outro responsável por este baixo desempenho dos AGs convencionais se deve à existência de algoritmos heurísticos muito eficientes para Problemas da área de Otimização, tais como o Problema do Caixeiro Viajante e algumas de suas generalizações.

Com isso, apesar do seu caráter genérico, o desempenho dos AGs na sua forma convencional não se mostra satisfatório para muitos problemas que já possuem algoritmos eficientes para a sua solução aproximada.

Esta é a motivação de, nos últimos anos, diversos pesquisadores terem proposto modificações nos AGs convencionais, incorporando técnicas de busca local, ou ferramentas de outras metaheurísticas tais como: Simulated Annealing, Tabu Search, Scatter Search, entre outros, ou desenvolverem versões paralelas para melhorar o desempenho dos AGs.

Com isso procura-se um certo equilíbrio entre o caráter genérico e simplista dos AGs convencionais com AGs mais especializados e sofisticados encontrados nas versões híbridas (algoritmos genéticos não convencionais), veja: Brown e Scherer (1995) [5], Goonatilake e Khebbal (1995) [6] e Glover (1995a[7a],b[7b],1996).

Dentre as técnicas híbridas envolvendo Algoritmos Genéticos destacamos a reunião de AGs com Tabu Search (TS)(Glover (1996) [7]; Rochat and Taillard(1995) [8] e Scatter Search (SS)(Glover (1995a[7a], b[7b],1996). O primeiro tem se mostrado como uma das melhores opções para a solução aproximada de problemas de elevado nível de complexidade, principalmente na área de Otimização. Tabu Search utiliza basicamente: listas de informações para proibir a análise de soluções geradas anteriormente durante um certo número de iterações, além de trabalhar com ferramentas de intensificação de buscas em regiões mais promissoras e diversificação de regiões de buscas, utilizando conceitos de "short term memory" e "long term memory".

Scatter Search (SS) pode ser visto como uma versão determinística dos Algoritmos Genéticos, incorporando além disso conceitos de TS. No SS, também são geradas populações de soluções como nos AGs, mas as etapas de seleção de cromossomos pais e de reprodução são efetuadas através de critérios determinísticos. A geração de novas soluções a partir de informações de um conjunto de soluções atuais é feita através de combinações lineares das soluções atuais. Diversos trabalhos publicados recentemente têm mostrado a superioridade desta técnica quando comparada com outras metaheurísticas, incluindo AGs convencionais (veja: Ochi, Figueiredo e Drummond (1997) [9], Ochi, Drummond e Vianna (1998a [9a],b[9b]), Reeves (1994) [10], Rochat e Taillard (1995) [8a].  


UM MODELO DE UM ALGORITMO GENÉTICO NÃO CONVENCIONAL

Um modelo de um novo Algoritmo Genético incorporando técnicas de busca local, mecanismos de busca intensiva em regiões promissoras e técnicas de diversificação cujo objetivo é a de efetuar buscas em novas regiões ainda não exploradas é descrito a seguir:

Etapas deste Algoritmo Genético não Convencional :

· Representação de uma solução na estrutura de um cromossomo.

· Construção de uma população inicial de cromossomos.

· Critério de avaliação dos cromossomos.

· Operadores Genéticos não Convencionais.

· Mecanismos de refinamento de cromossomos elite.

· Mecanismos de diversificação de populações.

· Critérios de parada e definição de parâmetros.  


UM ALGORITMO GENÉTICO NÃO CONVENCIONAL (AGNC)


Descrevemos a seguir um modelo de um AGNC aplicado ao problema de Steiner em Grafos Direcionados (PSGD):

Representação de um Cromossomo: No AGNC, cada cromossomo pode ser representado na estrutura de um vetor ( x1 , x2 ,...,xk), xi Î {0,1} i=1,2,...,k , k = |V-Vo|-1 (número de nós optativos). Cada xi está relacionado um a um com os nós optativos { v1 , v2 ,. . . ,vk } do dígrafo. O conjunto de nós optativos selecionados para gerar uma solução é dado por: So = { vi Î V-(Vo È {r }) : xi = 1 }.

Por exemplo, para o dígrafo da figura 2 temos: V-(Vo È {r}) = {v1, v2, ... ,v5} = { 5, 6, 7, 8, 9 }, k = 5 (tamanho do cromossomo). Neste caso, o cromossomo (0 1 1 0 1) representará a r-arborescência de Steiner do dígrafo induzido pelo conjunto de nós Vo\ È {r } È So , So = {6, 7, 9 }, veja figura 3.


fig3.gif (3754 bytes)

Figura 3: Arborescência de Steiner para o grafo da Figura 2


POPULAÇÃO INICIAL:   A população inicial do AGNC normalmente é construída aleatoriamente ou utilizando uma heurística simples e rápida. No caso do PSGD, cromossomos podem ser vetores cujo tamanho representa o número de pontos optativos. Cada posição (gene) de um cromossomo neste caso é preenchida por um número inteiro um/zero, onde o número um significa que o ponto optativo associado foi selecionado como um ponto de Steiner e o número zero implica o contrário.

AVALIAÇÃO DE CROMOSSOMOS:  Observe que um cromossomo como definido anteriormente para o PSGD não mostra de imediato uma solução deste problema. Um cromossomo neste caso somente define quais pontos optativos serão pontos de Steiner.

Desta forma, o processo de decodificação de um cromossomo na forma de uma solução válida do PSGD exige neste caso a solução de um problema de árvore geradora mínima (no caso de PSG simétrico) ou a solução de um problema de caminho mínimo entre a raiz r e todos os pontos obrigatórios utilizando os pontos de Steiner selecionados (no PSGD). O custo deste problema estará relacionado com o nível de aptidão do cromossomo associado.

MECANISMOS DE REPRODUÇÃO DE CROMOSSOMOS:  No processo de reprodução do AGNC, costuma-se utilizar uma generalização do operador genético clássico crossover e o operador mutação.

No operador generalizado(OG), ao invés de a cada reprodução selecionarmos 2 cromossomos pais para gerar um ou dois filhos, seleciona-se a cada reprodução, r(r ³ 2) cromossomos pais (ou aleatoriamente ou pelo método da roleta), para gerar r cromossomos filhos combinando os r pais. Esta combinação normalmente utiliza critérios de Otimização local para selecionar os genes de cada um dos r cromossomos filhos (offsprings) a partir dos r cromossomos pais (parents).

Na mutação o processo é idêntico ao modelo tradicional onde seleciona-se um cromossomo pai e gera-se um filho alterando um ou mais genes do pai.

O número de reproduções normalmente é no mínimo igual ao número de cromossomos de uma população. O critério para escolher os cromossomos que permanecerão na população é como se segue: No OG, existem normalmente dois critérios de sobrevivência; um inicial quando a taxa de renovação de uma população estiver acima de um mínimo pré-estabelecido, neste caso seleciona-se dentre as 2r soluções remanescentes de uma reprodução(r pais e r filhos), as r melhores sendo os r piores descartadas; quando a taxa de renovação de uma população estiver abaixo da taxa mínima, os r cromossomos filhos substituem automaticamente os r cromossomos pais independentemente do nível de aptidão. Este procedimento se justifica nesta etapa para se tentar diversificar a região de busca num momento onde a melhoria alcançada não está sendo significativa (taxa de renovação é pequena, ou seja quando temos um sintoma de que estamos num ótimo local).

Na mutação, seleciona-se dentre as duas soluções (um pai e um filho), a melhor solução, sendo descartada a outra.

MECANISMO DE REFINAMENTO DE CROMOSSOMOS ELITE / DIVERSIFICAÇÃO DE POPULAÇÕES:   Após gerar uma nova população de cromossomos, os s (onde s é um inteiro positivo pré definido) melhores cromossomos (soluções elite) são refinados através de um procedimento de busca intensiva, utilizando por exemplo um algoritmo do tipo 2 -optimal.

No caso do PSGD, a etapa de refinamento utilizando um método 2 - optimal consiste em retirar cada dois pontos de Steiner presentes na atual solução, incluindo a seguir dois novos pontos optativos. Tal procedimento é efetuado para cada par de pontos de Steiner presentes na solução analisada.

Um procedimento alternativo de busca local ao redor das soluções elite é descrita da seguinte forma:No AGNC quando se tem uma população muito homogênea, pode-se construir uma nova população formada por cromossomos que são cópias dos s melhores cromossomos (soluções elite) gerados até o momento pelo algoritmo. O número de cópias de cada cromossomo elite dependerá do seu nível de aptidão e do tamanho da população.

A idéia é: quanto melhor a aptidão de um cromossomo elite, mais cópias serão geradas deste cromossomo. Para cada cromossomo desta população abrimos uma janela de tamanho e posição aleatória, e somente dentro destas janelas selecionamos novamente alternativas para cada nó optativo. Desta maneira teremos uma população diversificada mas com características das s melhores soluções geradas até o momento.

Observe que quanto maior for o tamanho da janela a ser aberta em cada cópia, maior será a diversificação obtida, desta forma, este será considerado um parâmetro a mais no AGNC.

Finalmente note que este procedimento em torno de cada uma das s soluções elite pode ser visto como um método de busca local ao redor desta s solução, mas do ponto de vista de uma população de um AG, é na verdade um procedimento de diversificação aproveitando informações das s melhores soluções até então geradas.

CRITÉRIOS DE PARADA E DEFINIÇÃO DE PARÂMETROS:  Um dos critérios de parada utilizados com sucesso nos Algoritmos Genéticos Não Convencionais, funciona da seguinte forma: Quando uma população de cromossomos passa a ter cromossomos muito semelhantes (isso pode ser detectado comparando os seus níveis de aptidão), neste caso possivelmente teremos uma taxa de renovação baixa.

Neste momento aciona-se um critério de parada interna do AGNC, partindo para uma etapa de diversificação da população mas aproveitando informações das s soluções elite.

Feita a atualização da população, reinicia-se o operador genético para a construção de novas populações. Se, após k diversificações consecutivas, o melhor cromossomo não for atualizado, o critério de parada do algoritmo é acionado.  


AVALIAÇÃO DOS ALGORITMOS GENÉTICOS PROPOSTOS


Para se ter uma idéia do desempenho dos dois modelos de algoritmos genéticos aqui propostos, em Arroyo (1998) [11], foi feita uma série de testes computacionais para avaliar o algoritmo genético convencional e o algoritmo genético não convencional aqui descritos comparando os seus resultados com a solução ótima e com os resultados da heurística híbrida HTM reunindo os conceitos da heurística de Takahashi e Matsuyama (1980) e as propostas de Lawler (1976), veja Arroyo (1998) [11a]. Foram analisadas 38 instâncias do PSGD disponíveis na literatura e os resultados obtidos foram os seguintes:

· A heurística HTM obteve 8 soluções ótimas em 38 testes.

· O Algoritmo Genético convencional obteve solução ótima em 18 casos.

· O Algoritmo Genético Não Convencional obteve solução ótima em 34 casos.

Por outro lado, a heurística convencional HTM baseada em noções de caminho

mínimo gera somente uma solução do PSGD e obviamente foi a mais rápida das três versões.

Os tempos médios dos dois algoritmos genéticos foram semelhantes. Entretanto ressaltamos que o número de iterações utilizadas nos dois algoritmos genéticos não foi a mesma. Este procedimento pode ser justificado pela forma como foram efetuados os testes. Inicialmente foi testado o AG convencional e posteriormente o AGNC ambos utilizando os mesmos critérios de parada descritos nos seus respectivos algoritmos. Posteriormente repetimos os testes colocando como critério de parada o momento onde foi encontrado a melhor solução. Em muitas situações o AGNC atingiu o ótimo (ou a sua melhor solução) em um número menor de iterações que os do AG convencional. Este resultado propiciou uma observação interessante ao final dos testes, ou seja a de que o AGNC passou a exigir tempos menores que os do AG convencional na medida em que cresciam as dimensões dos problemas.

A conclusão a que chegamos é de que os algoritmos genéticos convencionais são modelos genéricos e simples, mas em muitos problemas de elevada complexidade não conseguem superar, em termos da qualidade da melhor solução gerada, os melhores métodos heurísticos já existentes, principalmente em problemas de otimização onde existem métodos muito eficientes baseados em Tabu Search e metaheurísticas híbridas.

Por outro lado, algoritmos genéticos não convencionais perdem o caráter genérico mas, em compensação, podem oferecer soluções aproximadas comparáveis às melhores existentes na literatura.  


ALGORITMOS GENÉTICOS PARALELOS


Uma das deficiências dos Algoritmos Genéticos seqüenciais, é o tempo de execução requerido, quando comparado com aqueles exigidos por outras

heurísticas. Tais limitações têm em parte se resolvido com a introdução dos Algoritmos Genéticos não Convencionais, onde são incluídas outras técnicas para melhorar o desempenho também no tempo computacional exigido. Contribuições nesta área foram obtidas também através de um melhor controle dos seus parâmetros e de critérios de parada mais eficientes.

Mas com certeza o caminho mais promissor para resolver este problema é aproveitar o paralelismo intrínseco existente nos algoritmos genéticos.

De fato, os algoritmos genéticos são inspirados em um processo evolutivo paralelo de uma população de indivíduos. Contudo, devemos alertar que o processo de paralelização dos AGs não são imediatos pois necessitam de um controle global no passo de seleção, o que requer uma interação entre processadores podendo produzir com isso altos custos de comunicação.

Existem vários modelos propostos que procuram reduzir estes problemas viabilizando o processo de paralelização. Estes modelos em geral se agrupam em três grandes categorias:

O ISLAND MODEL (MODELO ILHA OU MODELO DE GRANULARIDADE GROSSA):  Neste modelo várias subpopulações isoladas evoluem em paralelo e periodicamente trocam informações através da migração dos seus melhores indivíduos para subpopulações vizinhas. Implementações seguindo o modelo Island são assíncronas e mais adequadas a máquinas MIMD.

O FINE-GRAINED MODEL(MODELO DE GRANULARIDADE FINA):  Também conhecido como neighbourhood model, onde uma única população evolui e cada indivíduo é colocado em uma célula de uma grade planar. O processo de seleção e do crossover é aplicado somente entre indivíduos vizinhos na grade (de acordo com a topologia definida). Este modelo é mais adequado a arquiteturas SIMD paralelas como os "array processors" e "connection machines".

PANMITIC MODEL:  São essencialmente versões paralelas de algoritmos genéticos seqüenciais ordinários. Eles operam sobre uma população global, são normalmente síncronos e apresentam granularidade de média para grossa. Este modelo é adequado a arquiteturas paralelas com memória compartilhada.

Nos últimos anos, além de significativas contribuições sobre desenvolvimento da Teoria e de novos Algoritmos seqüenciais para AGs - veja Back(1996) [12], Radcliffe (1994) [13] e Reeves (1993) [10a] -, encontramos muitos trabalhos sobre Algoritmos Genéticos Paralelos, muitos deles utilizando um modelo do tipo "island" e utilizando sistemas paralelos do tipo: PVM (Parallel Virtual Machine) ou MPI (Message Passing Interface) veja: Gorges-Schleuter (1989)[14], Levine (1994) [15], Ochi, Figueiredo e Drummond (1997) [91], Ochi, Drummond e Vianna (1998a) [9a1], Ribeiro(1993) [16], Shapiro e Navetta (1994) [17], Shonkwiler (1993) [18], Wang e Korfhage (1995) [19], Snir e outros(1995) [26].  


UM ALGORITMO GENÉTICO PARALELO


Apresentamos a seguir uma versão paralela do AGNC descrito anteriormente.

A versão paralela denominada AGPNC utiliza o sistema MPI (Message Passing Interface) e inclui novos critérios de migração e terminação propostos em Ochi, Drummond e Vianna (1998a) [9a2].

O algoritmo AGPNC é baseado no modelo Island , onde existem diversos processos trabalhando sobre subpopulações que evoluem em paralelo. As populações iniciais são geradas de modo idêntico à da sua versão seqüencial AGNC.

O modelo de paralelização Island introduz um operador de migração, além das três etapas básicas (seleção, mutação e operador generalizado). O operador migração é usado para enviar indivíduos de uma subpopulação para outra.

Devido aos elevados custos de comunicação neste tipo de sistema, a freqüência de migração não deve ser muito alta. Desta forma, no algoritmo AGPNC o operador de migração é apenas executado quando existir a necessidade de uma renovação de uma subpopulação (fase de diversificação de uma população).

O critério de terminação local dos processos é baseado em uma condição global que envolve todos os processos que compõem o algoritmo paralelo; impedindo com isso, que um processador fique ocioso enquanto os demais permaneçam executando.

Os processos executados por cada processador e a comunicação entre eles pode ser melhor entendida através da ilustração da figura 0.4, onde cada par de processos mi e qi compartilham um mesmo processador, que é comutado entre os dois para a execução.

Inicialmente cada processo mi recebe uma população e executa um algoritmo genético similar ao AGNC sequencial. O processo qi tem a função de realizar a migração e controlar a terminação do algoritmo genético paralelo.


Figura 4: Comunicação entre os processos no AGPNC para três processadores

 




MIGRAÇÃO DE CROMOSSOMOS E TERMINAÇÃO


A estratégia adotada no algoritmo consiste em associar a cada processo mi (módulo principal), que compões o algoritmo genético paralelo do modelo Island, um processo qi. Os processos qi , para 1 leq i leq n (onde n é o número de processadores), se comunicam apenas por troca de mensagens e possuem a característica descrita abaixo.

O processo qi é ativado pelo processo mi correspondente nos seguintes casos:

1) Quando, por um período de w iterações consecutivas, não existir renovação num percentual mínimo exigido da população, disparando neste caso o processo de migração de indivíduos, onde w é um parâmetro de entrada.

2) Quando o processo mi está habilitado a terminar, dando início ao processo de terminação do algoritmo genético.

No primeiro caso (conforme Figura 0.5), qi envia pedidos a todos os outros processos do tipo q para que os mesmos lhe enviem suas melhores soluções correspondentes. Baseando-se nas soluções recebidas em resposta ao seu pedido, qi repassa as soluções recebidas ao mi associado, efetuando-se deste modo a migração de indivíduos.


Clique na figura

fig5.gif (5355 bytes)

Figura 5: Migração de indivíduos iniciada pelo processo m1 no caso de três processadores


No segundo caso, quando o processo mi está habilitado a terminar, ou seja, depois de realizado um número k de diversificações (veja o critério de parada do modelo seqüencial), este ativa o processo qi que mantém um vetor de n elementos representando o estado do sistema. Cada posição i do vetor de estado pode assumir o valor verdadeiro ou falso indicando que o processo mi está habilitado a terminar ou não. Ao ser ativado, o processo qi atualiza a posição i do vetor de estado com verdadeiro e inicia um broadcast a fim de que os demais vetores representem o estado atual do sistema. Um processo mi, ainda que habilitado a terminar, continuará sua execução até que todos os outros processos também possam terminar. Isto impedirá que um processador fique ocioso enquanto os demais permaneçam ativos, e ainda possibilita a melhora de sua solução ótima enquanto o sistema não termina.

Um processo mi, a cada geração do algoritmo genético, informa a qi a sua melhor solução gerada até o momento.

Caso a finalização seja detectada, isto é, todos os elementos do vetor de estado sejam verdadeiros, mi é informado a fim de que possa terminar sua execução.

A estratégia descrita acima permite que o processo responsável pela execução do processo genético não se ocupe com a comunicação com os demais processos, necessária para o controle da migração de indivíduos, e com a finalização do algoritmo genético paralelo, simplificando o seu projeto e implementação.  


LITERATURA


A literatura sobre Algorimos Genéticos, desde o seu surgimento, numa publicação de J. Holland(1975) [1c], inclui diversos livros textos, dos quais podemos destacar:     Genetic Algorithms + Data Structures = Evolution Programs: Third Edition de Z. Michalewicz(1996), Genetic Algorithms in Molecular Modeling de J. Devillers(editor)(1996), Genetic Algorithms and Investment Strategies de R. J. Bauer,Jr.(1994) [22], Handbook of Genetic Algorithms de L. Davis(editor)(1991) [28], Foundations of Genetic Algorithms I e II de L.D. Whitley (editor)(1993) [20], Handbook of Evolutionary Computation de Back, Fogel e Michalewicz(1996) [21], Genetic Algorithm and Simulated Annealing de Davis(editor)(1987), Evolutionary Computation de De Jung(1993) [23], Genetic Algorithm in Search, Optimization and Machine Learning de D.E. Goldberg(1989), Genetic Programming 1 e 2 de J.R.Koza(1992,1994), Parallel Genetic Algorithms(1993) [25] cujo editor é J.Stender.

Além disso, atualmente existem diversos congressos/simpósios específicos sobre o assunto, entre os quais: IEEE Int. Conference on Evolutionary Computation, International Conference on Genetic Algorithms, Int. Conference on Parallel Problem Solving from Nature, Annual Conference on Evolutionary Programming, Metaheuristic International Conference, Int. Conf. on Intelligence Systems for Molecular Biology e IEEE World Congress on Comp. Intelligence além de outros eventos da área de Ciência da Computação que incluem Seções especiais em Algoritmos Genéticos e Algoritmos Evolutivos.  


BIBLIOGRAFIA


à [11] Arroyo, J.C.E.(1998); Um algoritmo genético não convencional para o problema de Steiner em grafos direcionados - Tese de Mestrado - Programa de Pós-Graduação em Ciência da Computação - UFF.  

à [11a] ibidem  

à [12] Back,T.(1996), Evolutionary Algorithms in Theory and Practice, Oxford University Press.  

à [21]  Back,T.; D.Fogel and Z. Michalewicz (Editors) (1997), Handbook of Evolutionary Computation, Oxford University Press.  

à [23]  Battle,D.L. & M.D.Vose(1993), Isomorphisms of Genetic Algorithms, Artificial Intelligence 60, pp: 155-165, Elsevier.  

à [22] Bauer,R.J.(1994), Genetic Algorithms and Investment Strategies - Wiley.  

à [24] Béssiere, P. and E.G.Talbi(1991), A parallel Genetic Algorithm for the Graph Partitioning Problem. In ACM Int. Conf. on Supercomputing ICS91, Cologne- Germany.  

à [5] Brown, D.E. and W.T.Scherer(Editors)(1995), Intelligence Scheduling Systems, Kluwer Academic Publishers.  

à [26] Cantú-Paz, E.(1995), A summary of research on Parallel Genetic Algorithms, IlliGAL Report, 95007, University of Illinois at Urbana-Champaign.  

à [25] Chen, R.J., R.Meyer and J.Yeckel(1993), A genetic algorithm for diversity minimization and its parallel implementation,Proc. of the Fifty Int. Conf. on GA,pp: 163-170, San Mateo, CA, Morgan Kaufmann Publishers.  

à [?] De Jong,K.A.(Ed.)(1993), Evolutionary Computation, MIT Press.  

à [?]  Devillers,J.(ed.)(1996), Genetic Algorithms in Molecular Modeling - Principes of Qsar and Drug Design 1, Academic Press.  

à [28] Davis, L.(1991), Handbook of Genetic Algorithms, Van Nostrand Reinhold, NY.  

à [?] Fogel, L.J.(1966), Evolutionary Programming in Perspective: The Top-Down View - Comp. Intelligence - IEEE Press.  

à [2]  Glover, F.(1977), Heuristics for Integer Programming using surrogate constraints, Decision  .

à [?] Glover, F.(1994), Tabu Search for Nonlinear and Parametric Optimization with links to Genetic Algorithms, Discrete Applied Mathematics, 49, pp: 231-255.  

à [7a] Glover, F.(1995a), Scatter Search and Star-Paths: Beyond the Genetic Metaphor, OR SPEKTRUM, vol.17.  

à [7b] Glover, F.(1995b), Tabu Search Fundamentals and uses, University of Colorado at Boulder.  

à [7] Glover,F.(1996), Tabu Search and Adaptive memory programming: Advances, applications and challenges, Interfaces in Computer Science and Oper. Res., Kluwer Academic Publ., pp: 1-75.  

à [?] Goldberg,D.E.(1989) Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA.  

à [?]  Goldberg,D.E., H. Kargupta and E. Cantú-Paz(1995), Critical deme size for serial and parallel genetic algorithms. Technical Report IlliGAL 95002, University of Illinois at Urbana.  

à [6] Goonatilake,S. and S.Khebbal(Editors)(1995), Intelligence Hybrid Systems, John Wiley \& Sons.  

à [14]  Gorges-Schleuter,M.(1989), ASPARAGOS: An asynchronous parallel genetic optimization strategy. In Proc. of the Third Int.Conf.on GA, Morgan Kaufmann Publ.  

à [1] Holland, J.H.(1975), Adaptation in natural and artificial systems, Univ. of Michigan Press, AnnArbor  .

à [1a] ibidem  

à [1b] ibidem  

à [1c] ibidem  

à [?] Koza,J.R.(1992), Genetic Programming, MIT Press, MA.  

à [?]  Koza, J.R.(1994), Genetic Programming - 2, MIT Press, MA.  

à [15]  Levine,D.(1994), A Parallel Genetic Algorithm for the Set Partitioning Problem, PhD Thesis, Illinois Institute of Technology.  

à [?] Michalewicz,Z.(1996), Genetic Algorithms + Data Structures = Evolution Programs(Third edition), Springer.  

à [9a] Ochi,L.S.; L.M.A.Drummond and D.S.Vianna(1998a), A Parallel Evolutionary Algorithm for the Vehicle Routing Problems, in Lecture Notes in Computer Science - Springer-Verlag( a ser publicado)  

à [9a1] ibidem  

à [9a2] ibidem  

à [9b] Ochi,L.S.; L.M.A.Drummond and D.S.Vianna(1998b), An Evolutionary Hybrid Metaheuristic for solving the Vehicle Routing Problem with Heterogeneous Fleet, in Lecture Notes in Computer Science 1391 pp: 187-195 - Editors: W.Banzhat; R. Poli; M. Schoenaver and T.C. Fogarty - Springer-Verlag.  

à [9] Ochi,L.S.; R.M.V.Figueiredo and L.M.A.Drummond(1997), Design and Implementation of a PParallel Genetic Algorithm for the Traveling Purchaser Problem, APPLIED COMPUTING'97/ACM-SAC- (Eds: B.Bryant; J.Carroll; D.Oppenhein &K.George), Association for Comp.Machinery,Inc.  

à [91] ibidem  

à [?] Ochi,L.S.; P.G.Rabelo and N.Maculan(1997), A new genetic metaheuristic for the clustered TSP- Proc. of the III Metaheuristic Int.Conference(MIC'97)  

à [?]  Ochi,L.S.; A.M.Santos and E.Marques(1997), Design and Implementation of a Timetable System using Genetic Algorithm, Proc. of the 2nd Int. Automated Timetabling Conference - Toronto.  

à [13] Radcliffe,N.J.(1994), The Algebra of Genetic Algorithms, In Annals of Mathematics and Artificial Intelligence 10, pp: 339-384.  

à [10]  Reeves,C.R.(1993), Diversification in Genetic Algorithms: some connections with Tabu Search, Conventry University, U.K.  

à [10a] ibidem  

à [16] Ribeiro Filho,J.L.(1993), GAME's LIbrary Structure. In Parallel Genetic Algorithms:Theory and Applications(Ed. J.Stender), IOS Press Holland.  

à [8] Rochat, Y. and E. Taillard(1995), Probabilistic Diversification and Intensification in Local Search for Vehicle Routing, Centre de Recherche sur les Transports, Universite de Montreal(To appear in Journal of Heuristics).  

à [8a] ibidem  

à [17] Shapiro,B. and J.Navetta(1994), A massively parallel genetic algorithm for RNA secondary structure prediction. The Journal of Supercomputing 8, pp: 195-207.  

à [18] Shonkwiler, R.(1993), Parallel Genetic Algorithms, Proc. of the Fifth Int. Conf. on GA, University of Illinois at Urbana.  

à [?]  Stender,J., E.Hillebrand and J.Kingdon(Ed.)(1994), Genetic Algorithms in Optimization, Simulation and Modeling, IOS Press.  

à [?] Surry,P.D. and N.J.Radcliffe(1994), RPL2: A language and Parallel Framework for Evolutionary Computing, In: Parallel Problem Solving From Nature.  

à [19]  Wang,P.C. and W. Korfhage(1995), Process scheduling using genetic algorithms, IEEE Symposium on Parallel and Distributed Processing, San Antonio, USA, pp: 638-641 

à [20]  Whitley, D.(editor)(1993), Foundations of Genetic Algorithms-2, Morgan Kaufamann Publish.,San Mateo, CA.    







Luiz Satoru Ochi
Universidade Federal Fluminense - UFF
Profesor do Departamento de Ciência da Computação do Instituto de Matemática
E-mail: satoru@pgcc.uff.br



casa(5).gif (1005 bytes)