O trabalho desenvolvido trata da criação de uma ferramenta de redução automatizada capaz de receber um modelo de RP com entrada e aplicar uma sequência de regras de redução no mesmo (usando o mecanismo de processamento baseado em algoritmos genéticos), com o objetivo de diminuir a quantidade de elementos no modelo e mitigar o problema da grande profusão de elementos, permitindo assim aplicar metodologias de verificação de propriedades baseadas em simulação de modelos ou grafo de alcançabilidade com menor complexidade.
O modelo do sistema de manufatura a ser usado para estruturar indivíduo e operadores genéticos do Algoritmo Genético, bem como, para efetuar a validação da proposta é representado por uma Rede de Petri do tipo Lugar-Transição. As redes são de um tipo clássico não tendo características diferenciadas como, por exemplo, serem coloridas.
As regras de redução escolhidas para compor o algoritmo foram observadas em (Murata, 1989 apud Murata & Koh, 1980; Silva, 1985).
. Para a criação de um protótipo inicial de sistema foram utilizadas seis regras de redução apresentadas no referido trabalho, essas técnicas são: Fusão de Lugares em Série (do inglês, Fusion of Series Places (FSP)), Fusão de Transições em Série (do inglês, Fusion of Series Transitions (FST)), Fusão de Lugares Paralelos (do inglês,
Fusion of Parallel Places (FPP)), Fusão de Transições Paralelas (do inglês, Fusion of Parallel Transitions (FPT)), Elimicação de Lugares com Loop (do inglês, Elimination of Self-loop Places (ESP)) e Eliminação de Transições com Loop (do inglês,Elimination of Self-loop Transitions (EST)).
A Figura 4, exibida no capítulo 2 do presente documento, ilustra as referidas regras de redução que foram usadas para construir a base de regras mostrada no presente capítulo.
As regras de redução apresentadas foram citadas, utilizadas e/ou adaptadas em muitas pesquisas presentes no capítulo 2 do presente documento. Além disso, metodologias para evitar ou detectar deadlocks como grafo de alcançabilidade, por exemplo, podem ser impossíveis de aplicar quando as redes não atendem a propriedade de delimitação. Sabendo disso, reduzir um modelo usando as seis regras citadas pode ser um passo anterior à aplicação desse tipo de metodologia, tendo em vista que a redução usando essas regras mantém inalterada a propriedade de delimitação do modelo e também as propriedades de vivacidade e segurança (MURATA, 1989).
Metodologias para detectar e verificar a existência de deadlocks em modelos de RP usando teoria de regiões também podem ser limitadas pela grande profusão de elementos, dessa forma a estratégia de usar regras de redução antes da metodologia é sempre considerada viável. Na pesquisa conduzida por Uzam, (2004), por exemplo, a referida estratégia é aplicada e as regras escolhidas são as mesmas seis observadas no trabalho de Murata, (1989). Isso acontece porque o foco da pesquisa está na prevenção de deadlocks e as regras mantém propriedades fundamentais para esse escopo de avaliação.
Portanto, decidiu-se pelo uso das seis regras apresentadas por Murata, (1989) devido as propriedades que são mantidas nos modelos e também por observar-se que muitas metodologias relacionadas a prevenção, detecção ou recuperação de deadlocks em modelos de RP necessitam da manutenção dessas propriedades quando optam por reduzir os modelos antes de aplicar a metodologia.
Para o escopo da presente pesquisa não busca-se usar regras de redução para outros tipos de RP’s, por exemplo, as variantes apresentadas por (BERNARDINELLO; FIORELLA, 1992). Para que o método seja utilizado, basta que o modelo se baseie nas redes conhecidas como “lugar-transição”.
A tarefa de aplicar regras de redução nos modelos é realizada por um Algoritmo Genético. Uma matriz de incidência (representando o modelo de Rede de Petri) é usada como entrada pelo Algoritmo Genético que aplica uma sequência de regras de redução no modelo e exibe como resultado a matriz de incidência que representa o modelo
reduzido, tendo ainda um relatório com quais regras foram aplicadas em cada linha/coluna do modelo.
A escolha pela utilização de uma heurística para executar a redução vem de sua capacidade de varrer um espaço de busca amplo (nesse caso referente à estrutura do modelo representada como matriz de incidência) em pouco tempo. Outro fator que insere complexidade no modelo (além do número de elementos) é que ordem de aplicação das regras pode gerar novas características estruturais que permitam aplicar mais regras, ou seja, nesse aspecto o problema pode ser considerado combinatório, tendo em vista que a combinação de regras aplicadas influencia no tamanho final da rede reduzida.
A sequência das regras aplicadas no indivíduo de melhor resultado vai depender exclusivamente da regra de avaliação (Fitness) criada para o AG, ou seja, se a regra de fitness tiver sido criada para privilegiar redes que tenham poucos “lugares”, uma determinada sequência pode ser mais apropriada, se por acaso o objetivo for obter uma rede com uma baixa quantidade de transições, outra sequência pode se mostrar mais apropriada, e isso vai refletir diretamente no melhor indivíduo encontrado ao final da execução. Durante os testes o número que será usado na função de avaliação será relacionado a quantidade de elementos, ou seja, não serão privilegiadas redes com menos lugares ou menos transições, mas sim, redes com menos elementos no total.
Independentemente da regra de avaliação utilizada, após a execução do algoritmo, terá sido varrida uma grande área de busca, criada pela combinação de regras de redução, e uma determinada sequência de regras terá sido proposta (no melhor indivíduo criado). O caráter genérico da proposta vem da possibilidade de se mudar o fitness para que a execução do algoritmo siga um determinado objetivo.