PUBLICACAO ARTIGO (1)

Prévia do material em texto

SÍNTESE E OTIMIZAÇÃO COMBINATÓRIA DE MÁQUINAS DE
ESTADOS FINITOS UTILIZANDO ALGORITMOS EVOLUTIVOS
Willyãn Arruda de Araújo1, Prof Me. Tiago da Silva Almeida2
1Aluno do Curso de Ciência da Computação; Campus de Palmas; e-mail:
willyan.arruda@uft.edu.br ; PIBIC/UFT;
2Orientador do Curso de Ciência da Computação; Campus de Palmas; e-mail:
tiagoalmeida@uft.edu.br
RESUMO
Para obter sistemas digitais menores, como microprocessadores, controladores etc., é necessário projetá-
los com uma pequena área e tratar a dissipação de energia. Essas questões são importantes porque
podem prolongar o tempo de uso do equipamento e reduzir os custos de fabricação. Para fazer isso,
os circuitos digitais podem ser modelados como máquinas de estados finitos com muitos estados para a
maioria dos problemas práticos. Para obter um resultado mı́nimo, é necessário otimizar uma atribuição
de estado. Encontrar uma solução que atenda a essas caracteŕısticas, ou seja, encontrar as atribuições de
estado ideais é uma tarefa complexa porque é um problema NP-Completo. Assim, esta pesquisa analisou
o Algoritmo Genético para obter uma otimização na atribuição de estados em um tempo razoável.
Nos experimentos, o Algoritmo Genético foi capaz de encontrar uma boa solução para os benchmarks
testados. Porém, é necessário estudar um melhor critério de parada para Algoritmo Genético. Outro
problema é o desempenho do Algoritmo Genético. Observou-se um longo tempo para se chegar à solução
para uma máquinas de estados finitos com muitos estados.
Palavra-chave: Śıntese; Otimização; Máquina de estados finitos; Algoritmo Genético;
INTRODUÇÃO
Muitas vezes, pesquisadores em computação e em outras áreas levam em conta que o aumento do
poder de processamento genérico e armazenamento em hardware é suficiente para criação de softwares
mais robustos e complexos, como por exemplo, sistemas de otimização e baseados em aprendizado.
Entretanto, esses sistemas sem um processamento adequado à complexidade do software, leva a gargalos
Página 1
no desempenho. Logo, é necessário que o hardware evolua, e muitas vezes em uma velocidade maior
que a do software.
O aperfeiçoamento do hardware não é trivial. E demanda um grande esforço em pesquisa, não só para
arquitetos e engenheiros de hardware, mas também de f́ısicos e qúımicos que possam levar a elementos
f́ısicos menores e mais rápidos. Mais rápidos pela demanda das aplicações, como dito, e menor pela
comodidade humana.
As etapas de projeto são basicamente divididas em ńıveis de abstração diferentes do projeto. Ou seja,
são representações diferentes do mesmo projeto em ńıveis diferentes de detalhes, sejam eles lógicos ou
f́ısicos. Entre esses ńıveis, o foco de estudo desse projeto, são as Máquinas de Estados Finitos (MEF).
MEFs são abstrações do comportamento de um determinado circuito, seja ele uma parte ou o todo
de ASIC (Application Specific Integrated Circuits) ou de um processador convencional. Nós humanos
pensamos no comportamento de um sistema computacional em termos de algoritmos, e esse algoritmo
pode ser descrito como uma máquina abstrata, com estados diferentes de funcionamento e transições
entre esses estados de acordo com est́ımulos externos ou internos (entradas).
A partir dessa representação do comportamento é posśıvel chegar a um modelo f́ısico de maneira bem
estabelecida. Esse modelo f́ısico da MEF pode ser śıncrono em relação ao comportamento interno ou
externo, como também pode ser asśıncrono. A escolha entre um e outro depende da aplicação.
O projeto ótimo ou menor posśıvel de uma MEF pode levar a estruturas mais eficientes, sem
necessariamente diminuir o tamanho dos transistores. Isso pode auxiliar tanto projeto de ASICs como
de processadores convencionais. Contudo, o custo desses é alto devido ao tamanho do espaço de busca.
Isto é, os objetivos de otimização de uma MEF, seja ele alocação ótima de estados, eficiência
energética, tamanho das expressões booleanas que representam o comportamento, elemento de
memória a ser utilizado etc.
Dada essa complexidade, muitos projetos simplesmente desconsideram essas possibilidades de otimização
em algum ńıvel. Contudo, é necessária a investigação cont́ınua, para se chegar a métodos eficientes de
otimização em projetos de hardware.
Nesse sentido, o objetivo desse projeto foi realizar uma investigação em torno do projeto e otimização
de MEFs. Por se tratar de problema NP-Completo, metaheuŕısticas são estratégias mais indicadas para
tentar encontrar uma boa solução para o problema. Assim, foi estudado e implementado o Algoritmo
Genético (AG) para esse processo de otimização.
AGs são amplamente utilizados em uma variada gama de problemas e já possuem algumas aplicações
para esse mesmo tipo de problema (ALMAINI et al., 1995; HONG et al., 1994; AVEDILLO;
QUINTANA; HUERTAS, 1994; SIROHI et al., 2018; SOTOMAYOR; HAMPEL; VáZQUEZ, 2018;
RAY; MISRA, 2019). Contudo, algumas adaptações da estrutura convencional também surgiram para
Página 2
tentar aprimorar os AGs convencionais (LING; POTTER, 2012; AMARAL; HRUSCHKA, 2014;
SNASELOVA; ZBORIL, 2015; STANOYEVITCH, 2010; AMIRJANOV, 2016; JAFARI-MARANDI;
SMITH, 2017; TAO; ZHANG; ZHANG, 2015; ZHOU et al., 2016; CURTINHAS et al., 2017; DAS et
al., 2016; BARBIERI; PAULO; RODRIGUES, 2015; STERGIOU; DASKALAKIS;
PAPAKONSTANTINOU, 2004; KALATHAS; VOUDOURIS; PAPAKONSTANTINOU, 2006; LIN;
GENG, 2009).
Assim, indaga-se o quão benéfico é a utilização de Algoritmos Evolutivos (classe mais geral dos AGs,
levando em conta ou não alterações em relação ao seu comportamento canônico) para encontrar uma
solução ótima para o problema de alocação de estados de uma MEF.
Com base na contextualização exposta, o projeto pode ser metodologicamente melhor detalhado da
seguinte forma: i) Tema de pesquisa: otimização de MEF para aplicação em circuitos digitais; ii)
Problema de pesquisa: o AG consegue obter MEFs ainda menores?; iii) Hipótese: o AG consegue
obter melhores resultados de otimização para MEFs. Contudo, não em grande percentual e à um
custo computacional menor; iv) Objetivo geral: avaliar o custo computacional e o percentual de
ganho no processo de otimização de MEFs com o AG canônico e v) Objetivos espećıficos: avaliar os
resultados de implementação do AG canônico aplicado à otimização de MEFs; avaliar os resultados de
implementação do AG aplicado à otimização de MEFs; comparar e verificar o quão melhor, ou não, em
termos de resultados avaliados estatisticamente.
MATERIAIS E MÉTODOS
CIRCUITOS SEQUENCIAIS E DEFINIÇÕES
Uma MEF possui um número finito de entradas, constituindo o conjunto das variáveis de entrada
N = N1, N2, ..., Nn. Assim, o circuito tem um número finito de sáıdas, determinado pelo conjunto de
variáveis de sáıda M = M1,M2, ...,Mm. O valor contido em cada elemento de memória é chamado
de variáveis de estado, formando o conjunto das variáveis de estado K = K1, K2, ..., Kk. Os valores
contidos nos K elementos de memória definem o estado atual da máquina. As funções de transições
internas geram o conjunto de próximo estado S = S1, S2, ..., Ss, que dependem das N entradas e dos
K estados atuais da máquina e são definidas através de circuitos combinacionais. Os valores de S, que
aparecem na função de transição da MEF no instante t, determinam os valores das variáveis de estado
no instante t+ 1, e, portanto, definem o próximo estado da MEF (FLOYD, 2009; TAUB, 1984).
A atribuição de estado é um mapeamento do conjunto de estados de uma MEF para o conjunto de
códigos binários. Encontrar uma solução ótima para alocação de estados é uma tarefa complexa, pois,
devem-se testar todos os arranjos posśıveis para obter a alocação ótima, o número total de posśıveis
atribuições únicas para uma MEFé dada por
Página 3
A(n, b) =
(2b − 1)!
(b!(2b − n)!)
(1)
portanto, trata-se de um problema NP-Completo. Especificamente para máquinas com muitos estados,
um bit diferente entre duas atribuições para o mesmo estado pode alterar o bloco lógico que define o
próximo estado e a lógica de sáıda, gerando um circuito diferente.
Para demonstrar a complexidade do problema de alocação de estados, considera-se uma MEF que possui
7 estados, é posśıvel obter 840 atribuições distintas para esta MEF, com base na Equação (1). Já para
uma MEF que possui 10 estados o número total de atribuições exclusivas passa a ser 75.675.600, o
espaço de busca para encontrar a solução ótima cresce de maneira fatorial.
ALGORITMO GENÉTICO E APLICAÇÕES
Os AG trabalham em um conjunto de pontos chamado de “população” e não a partir de pontos isolados.
Trabalham também em um espaço de soluções codificadas, e não diretamente no espaço de busca, e
necessitam como informação somente o valor de uma função objetivo chamada de “fitness”. O “fitness”
pode ser visto como a probabilidade de que o organismo viva e possa se reproduzir ou a viabilidade da
solução. Também pode ser uma função de número de indiv́ıduos filhos que o organismo possui ou a
fertilidade do indiv́ıduo. Outra definição importante é o “cromossomo”, que representa um indiv́ıduo na
população, isto é, uma configuração ou solução do problema.
Os operadores genéticos permitem a manipulação dos cromossomos e as duas operações básicas são:
o operador de “crossover” ou cruzamento que permite a obtenção de indiv́ıduos filhos a partir da
combinação dos cromossomos pais, caracterizando a reprodução sexuada, e o operador de “mutação”
que permite a produção de um novo indiv́ıduo por alterações diretas no cromossomo pai e/ou filho,
caracterizando a reprodução assexuada (HOLLAND, 1975; GOLDBARG; LUNA, 2005; BOCCATO
et al., 2009; KUMAR; ROCKETT, 2002; GOLDBARG; LUNA, 2005; BURJORJEE, 2013; AHMED,
2013).
Pode-se definir um AG da seguinte forma: AG = (N,P, F,Θ,Ω,Ψ), onde P é uma população de N
indiv́ıduos, P = {S1, S2, . . . , SN}. Cada indiv́ıduo Si, i = 1, . . . , N , é um conjunto de valores inteiros de
comprimento n que representa uma solução do problema. F representa a função de fitness que retorna
um valor positivo e real na avaliação de cada indiv́ıduo. Θ é um operador de seleção de pais que escolhe
r indiv́ıduos de P . Ω é um conjunto de operadores genéticos incluindo o crossover, denominado ΩC , e
a mutação, denominado ΩM ou qualquer outro operador espećıfico que produza s filhos a partir de r
pais.
Os parâmetros necessários para a execução do algoritmo genético proposto são: o arquivo da MEF, a
Página 4
qual será submetida ao algoritmo; tamanho da população (P ), que é definido com base na quantidade
de estados da MEF seguindo P = 2 × e × b, onde e é quantidades de estados que a MEF possui e b
é a quantidade de bits necessários para representar os estados. A quantidade de gerações (G), que é
estabelecida com base no tamanho da MEF da seguinte forma: G = (T
1
2 )
b
, onde T é quantidade de
transições da MEF.
ABORDAGEM PROPOSTA
A fase inicial do projeto consiste em ler um arquivo que contém as informações de uma MEF, como
transição de estados, total de estados, bits de entrada e sáıda. O template é gerado apenas uma vez, para
uma determinada MEF, porém, a cada indiv́ıduo gerado pelo AG, as lacunas em branco são atualizadas
com os valores contidos no indiv́ıduo correspondente a cada estado representado no template.
As colunas correspondentes ao estado atual e próximo estado, possui duas lacunas, uma é preenchida
com os valores literais lidos do arquivo. A segunda lacuna será posteriormente preenchida com valores
binários atribúıdos a cada estado respectivamente. Na etapa de geração do indiv́ıduo os valores
atribúıdos aos estados estão na base decimal, porém ao inserirmos no template o valor alocado ao
respectivo estado, é feita a conversão deste valor para base binária.
O AG implementado possui uma matriz de tamanho 2 × n + 1, sendo n a quantidade de estados da
MEF. Na primeira linha cada posição de 0 a n corresponde a um estado lido do arquivo, a posição
n+1 refere-se ao custo deste indiv́ıduo. A segunda linha contém os valores atribúıdos a cada estado
respectivamente, e o valor do custo, estes valores estão na base decimal.
A codificação foi realizada utilizando números decimais, pois, deste modo o tratamento da infactibilidade
do problema de atribuição de estados torna-se mais simples, a infactibilidade ocorre quando dois ou
mais estados são alocados com valores iguais.
Nesta etapa calcula-se, através de uma determinada função, o valor de aptidão de cada indiv́ıduo da
população. É através desta função que se mede quão próximo um indiv́ıduo está da solução desejada
ou quão boa é esta solução.
A função objetivo do algoritmo implementado leva em consideração o custo de cada indiv́ıduo. Busca-
se a melhor alocação de estados para uma MEF, com o objetivo de minimizar o tamanho da área e a
dissipação de energia, logo, os melhores indiv́ıduos são aqueles que possuem o menor custo.
O custo mı́nimo do indiv́ıduo é calculado utilizando a biblioteca SymPy (linguagem Python), após analisar
as funções de próximo estado, presente no template para o respectivo indiv́ıduo. A biblioteca SymPy
é responsável por minimizar as expressões booleanas que representam as funções de próximo estado e
sáıda, então atribui-se o peso estipulado a cada termo e literal da expressão mińıma.
A geração da população inicial é realizada aleatoriamente, pois, a qualidade das soluções apresentadas
Página 5
deve ser independente da população inicial.
O número de indiv́ıduos que formam a população é obtido por I = 3 · n · v, sendo, I a quantidade
de indiv́ıduos da população, n o número de estados e v a quantidade mı́nima de variáveis de estados
necessárias para alocar os n estados, e v o menor inteiro maior ou igual a log2 n
Devido a aleatoriedade na geração da população inicial, podem surgir indiv́ıduos infact́ıveis. Para
evitar este problema utilizou-se um recurso, para que os indiv́ıduos não violem a restrição. Este recurso
consiste em montar um mapa que contém todos os valores posśıveis que v variáveis de estados podem
assumir, para determinar o tamanho do mapa utiliza-se t = 2v à cada atribuição de um valor para um
estado do indiv́ıduo, este valor é retirado do mapa para evitar que outro estado do mesmo indiv́ıduo
possa assumi-lo. O processo é repetido até que todos os estados recebam um valor, um novo mapa é
gerado para cada indiv́ıduo.
Neste trabalho foi utilizado o método de seleção por roleta, este método funciona da seguinte maneira,
cada indiv́ıduo da população é representado na roleta proporcionalmente ao seu ı́ndice de aptidão.
Assim, para indiv́ıduos com alta aptidão é dada uma porção maior da roleta, enquanto aos indiv́ıduos
de aptidão mais baixa, é dada uma porção relativamente menor. Como o interesse é encontrar a melhor
alocação de estados, os indiv́ıduos com maior aptidão e os quais consequentemente ocuparão uma porção
maior da roleta, são aqueles que tem os menores custos.
O crossover implementado neste algoritmo foi o de um ponto, após a execução do crossover os indiv́ıduos
gerados podem ser infact́ıveis, ou seja, ter dois ou mais estados com o mesmo valor, para resolver isto
utilizamos o mesmo procedimento aplicado na geração da população inicial. Este processo de tratar a
infactibilidade do indiv́ıduo, é considerado o operador de mutação, pois, uma informação aleatória é
inserida no indiv́ıduo.
O indiv́ıduo com maior aptidão de cada geração, ou seja, o que possui menor custo é armazenado. A
solução é o indiv́ıduo mais apto após xiterações.
RESULTADOS E DISCUSSÃO
O AG proposto foi avaliado utilizando o benchmark LGSynth’89 (YANG, 1988). O benchmark
LGSynth’89 é conjunto de exemplos com 41 MEFs apresentados no International Workshop on Logic
Synthesis em 1989. Os resultados para seis casos analisados são listados na Tabela 1.
A segunda coluna na Tabela 1 denota o número de bits de entrada, terceira coluna número de bits de
sáıda, na quarta coluna o número de termos produto (foi considerado as expressões booleanas na forma
de soma de produtos) e na quinta coluna os estados para o determinado benchmark na primeira coluna.
O conjunto de resultados produzidos pelo AG é dado na sexta e sétima coluna. “Ter” denota o número
de mintermos e “Lit” o número de literais.
Página 6
Tabela 1 – Resultados do AG proposto para seis casos contidos no benchmark
LGSynth’89.
MEF Entradas Sáıdas Produtos Estados
AG
Ter Lit
beecount 3 4 28 7 20 66
dk14 3 5 56 7 43 130
ex3 2 2 36 10 26 81
mc 3 5 10 4 16 58
tav 4 4 49 4 21 62
train11 2 1 25 11 28 100
Os resultados foram obtidos utilizando taxa de mutação = 0,02, taxa de crossover = 0,4, taxa de
seleção = 0,6 (porcentagem de indiv́ıduo será selecionada para compor a nova geração) e 300 para o
número de gerações. Todas as taxas foram usadas em valores totais e o indiv́ıduo espećıfico e o gene
são selecionados aleatoriamente.
A Figura 1 mostra a curva do comportamento do algoritmo durante as 300 iterações, notamos a evolução
em busca de menores custos durante a execução. Cada curva se refere a um benchmark espećıfico
conforme indicado na legenda.
Figura 1 – Curva de comportamento do AG para os casos analisados em 300 gerações.
Nos experimentos percebeu-se a diminuição dos custos nas gerações finais do AG. Talvez seja mais
adequado ajustar o critério de parada para melhorar os resultados. Da mesma forma, MEFs com mais
estados podem exigir mais gerações para alcançar melhores resultados.
A Figura 2 mostra a distribuição normal dos custos do melhor indiv́ıduo de cada geração.
Este gráfico foi constrúıdo para mostrar a densidade de probabilidade de a solução ser uma boa solução.
Para traçar o gráfico foi usado f(x) = 1
σ
√
2π
ε−
1
2
(x−µ
σ
)2 , onde x é o valor do custo, µ é a média da
distribuição e σ é o desvio padrão da distribuição.
Na Figura 2, nos benchmarks train11, beecount e dk14 as curvas são muito baixas, o que significa que
o resultado pode ser melhorado. Assim, esse fato corrobora com a hipótese de utilizar mais gerações
Página 7
Figura 2 – Densidade de probabilidade da solução ser uma boa solução para cada um dos
casos analisados para o AG proposto.
(a) Caso beecount (b) Caso dk14 (c) Caso ex3
(d) Caso mc (e) Caso tav (f) Caso train11
para obter melhores resultados. O melhor resultado foi com o benchmark tav.
Outra hipótese é usar diferentes parâmetros no AG, outras taxas de crossover, mutação e seleção.
CONSIDERAÇÕES FINAIS
Este trabalho analisou a implementação de AG em Python para resolver o problema de atribuição de
estado para MEF. Nos experimentos, o AG foi capaz de encontrar uma boa solução para os benchmarks
testados. Porém, é necessário estudar um melhor critério de parada para AG.
Outro problema é o desempenho do AG. Observou-se um longo tempo para se chegar à solução para
MEF com muitos estados. Assim, a complexidade do algoritmo é exponencial.
O grande problema para esse tempo é a avaliação da função de aptidão, ou seja, o custo do MEF. Em
nossos experimentos foram usados uma biblioteca externa e não há controle sobre sua implementação.
Isso significa que todas as combinações de expressão são testadas para cada bit, em cada atribuição, em
cada cromossomo, em cada geração.
Uma posśıvel solução é dividir as fases em vários threads e /ou em outra unidade funcional (CPU) para
dividir a sobrecarga e obter mais desempenho. Ou tentar implementar uma função de custo melhor
com outro critério ou outro algoritmo.
AGRADECIMENTOS
Página 8
O presente trabalho foi realizado com o apoio da UFT.
LITERARURA CITADA
AHMED, Z. H. A hybrid genetic algorithm for the bottleneck traveling salesman problem. ACM
Trans. Embed. Comput. Syst., ACM, New York, NY, USA, v. 12, n. 1, p. 9:1–9:10, 2013.
ALMAINI, A. E. A. et al. State assignment of finite state machines using a genetic algorithm. IEE
Proceedings - Computers and Digital Techniques, v. 142, n. 4, p. 279–286, July 1995. ISSN
1350-2387.
AMARAL, L. R.; HRUSCHKA, E. R. J. Transgenic: An evolutionary algorithm operator.
Neurocomputing, v. 127, n. Supplement C, p. 104 – 113, 2014. ISSN 0925-2312.
AMIRJANOV, A. Modeling the dynamics of a changing range genetic algorithm. Procedia Computer
Science, v. 102, p. 570 – 577, 2016. ISSN 1877-0509. 12th International Conference on Application of
Fuzzy Systems and Soft Computing, ICAFS 2016, 29-30 August 2016, Vienna, Austria. Dispońıvel em:
.
AVEDILLO, M. J.; QUINTANA, J. M.; HUERTAS, J. L. State merging and state splitting via
state assignment: a new fsm synthesis algorithm. IEE Proceedings - Computers and Digital
Techniques, v. 141, n. 4, p. 229–237, July 1994. ISSN 1350-2387.
BARBIERI, C. D. P. do N.; PAULO, J. V. D.; RODRIGUES, A. C. Aperfeiçoamento do método
clause-column table para a geração eficiente de implicantes primos. A, v. 1, p. M2, 2015.
BOCCATO, L. et al. Um estudo da aplicação de algoritmos bio-inspirados ao problema de estimação
de direção de chegada. Revista Controle e Automação, São Paulo, SP, Brazil, v. 20, n. 4, p.
609–626, 2009.
BURJORJEE, K. M. Explaining Optimization in Genetic Algorithms with Uniform
Crossover. Adelaide, Australia: ACM, 2013. 37-50 p.
CURTINHAS, T. et al. State assignment of direct output synchronous fsms using genetic algorithm.
In: 2017 IEEE XXIV International Conference on Electronics, Electrical Engineering and
Computing (INTERCON). [S.l.: s.n.], 2017. p. 1–4.
DAS, S. R. et al. An algorithm for generating prime implicants. In: IEEE. Instrumentation and
Measurement Technology Conference Proceedings (I2MTC), 2016 IEEE International.
[S.l.], 2016. p. 1–6.
FLOYD, T. Sistemas digitais: fundamentos e aplicações. [S.l.]: Bookman Editora, 2009.
GOLDBARG, M. C.; LUNA, H. P. L. Otimização Combinatória e Programação Linear. Rio de
Janeiro, RJ, Brazil: Campus, 2005. v. 2.
HOLLAND, J. H. Adaptation in natural and artificial systems: An introductory analysis
with applications to biology, control, and artificial intelligence. Oxford, England: Michigan
Press, 1975. v. 1. 183 p.
HONG, S. K. et al. State assignment in finite state machines for minimal switching power consumption.
Electronics Letters, v. 30, n. 8, p. 627–629, April 1994. ISSN 0013-5194.
Página 9
http://www.sciencedirect.com/science/article/pii/S1877050916326242
JAFARI-MARANDI, R.; SMITH, B. K. Fluid genetic algorithm (fga). Journal of Computational
Design and Engineering, v. 4, n. 2, p. 158 – 167, 2017. ISSN 2288-4300. Dispońıvel em:
.
KALATHAS, M.; VOUDOURIS, D.; PAPAKONSTANTINOU, G. A heuristic algorithm to minimize
esops for multiple-output incompletely specified functions. In: ACM. Proceedings of the 16th
ACM Great Lakes symposium on VLSI. [S.l.], 2006. p. 357–361.
KUMAR, R.; ROCKETT, P. Improved sampling of the pareto-front in multiobjective genetic
optimizations by steady-state evolution: A pareto converging genetic algorithm. Evol. Comput.,
MIT Press, Cambridge, MA, USA, v. 10, n. 3, p. 283–314, 2002.
LIN, Y.; GENG, R. Mlbm: Machine-learning-based minimization algorithm for boolean functions. In:
IEEE. Industrial Electronics, 2009. ISIE 2009. IEEE International Symposium on. [S.l.],
2009. p. 1160–1165.
LING, W.; POTTER, W. D. Virus transmission genetic algorithm. Contemporary Challenges and
Solutions in Applied Artificial Intelligence, v. 489, p. 41–46,2012.
RAY, S. S.; MISRA, S. Genetic algorithm for assigning weights to gene expressions using functional
annotations. Computers in Biology and Medicine, v. 104, p. 149 – 162, 2019. ISSN 0010-4825.
Dispońıvel em: .
SIROHI, R. et al. Application of genetic algorithm in modelling and optimization of cellulase
production. Bioresource Technology, v. 270, p. 751 – 754, 2018. ISSN 0960-8524. Dispońıvel em:
.
SNASELOVA, P.; ZBORIL, F. Genetic algorithm using theory of chaos. Procedia Computer
Science, v. 51, n. Supplement C, p. 316 – 325, 2015. ISSN 1877-0509.
SOTOMAYOR, G.; HAMPEL, H.; VáZQUEZ, R. F. Water quality assessment with emphasis in
parameter optimisation using pattern recognition methods and genetic algorithm. Water Research,
v. 130, p. 353 – 362, 2018. ISSN 0043-1354. Dispońıvel em: .
STANOYEVITCH, A. Homogeneous genetic algorithms. International Journal of Computer
Mathematics, v. 87, n. 3, p. 476–490, 2010.
STERGIOU, S.; DASKALAKIS, K.; PAPAKONSTANTINOU, G. A fast and efficient heuristic esop
minimization algorithm. In: ACM. Proceedings of the 14th ACM Great Lakes symposium on
VLSI. [S.l.], 2004. p. 78–81.
TAO, Y.; ZHANG, L.; ZHANG, Y. An evolutionary strategy based state assignment for area-
minimization finite state machines. In: 2015 IEEE Symposium Series on Computational
Intelligence. [S.l.: s.n.], 2015. p. 1491–1498.
TAUB, H. Circuitos Digitais e Microprocessadores. [S.l.]: Editora McGraw-Hill, 1984. 37-301 p.
YANG, S. Logic Synthesis and Optimization Benchmarks. 1988. Dispońıvel em: .
ZHOU, C. et al. An efficient solution of circuit state assignment with immune algorithm. In: 2016
6th International Conference on Electronics Information and Emergency Communication
(ICEIEC). [S.l.: s.n.], 2016. p. 38–41. ISSN 2377-844X.
Página 10
http://www.sciencedirect.com/science/article/pii/S2288430016300458
http://www.sciencedirect.com/science/article/pii/S0010482518303731
http://www.sciencedirect.com/science/article/pii/S0960852418313580
http://www.sciencedirect.com/science/article/pii/S0043135417310059
http://www.sciencedirect.com/science/article/pii/S0043135417310059
https://ddd.fit.cvut.cz/prj/Benchmarks/index.php?page=download
https://ddd.fit.cvut.cz/prj/Benchmarks/index.php?page=download
	RESUMO
	Introdução
	Materiais e Métodos
	Circuitos sequenciais e definições
	Algoritmo genético e aplicações
	Abordagem Proposta
	Resultados e Discussão
	Considerações Finais
	Agradecimentos
	Literarura Citada