ads:
ALGORITMOS GENÉTICOS DISTRIBUÍDOS APLICADOS AO PROBLEMA
INVERSO DE ELETROFISIOLOGIA CARDÍACA
Daves Marcio Silva Martins
TESE SUBMETIDA AO CORPO DOCENTE DA COORDENAÇÃO DOS
PROGRAMAS DE PÓS-GRADUAÇÃO DE ENGENHARIA DA UNIVERSIDADE
FEDERAL DO RIO DE JANEIRO COMO PARTE DOS REQUISITOS
NECESSÁRIOS PARA A OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIAS EM
ENGENHARIA CIVIL.
Aprovada por:
________________________________________________
Prof. Nelson Francisco Favilla Ebecken, D.Sc.
________________________________________________
Prof. Rodrigo Weber dos Santos, D.Sc.
________________________________________________
Prof. Antonio Cesar Ferreira Guimarães, D.Sc.
________________________________________________
Prof.ª Beatriz de Souza Leite Pires de Lima, D.Sc.
RIO DE JANEIRO, RJ - BRASIL
MARÇO DE 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ii
MARTINS, DAVES MARCIO SILVA
Algoritmos genéticos distribuídos aplicados
ao problema inverso de eletrofisiologia cardíaca
[Rio de Janeiro] 2008
XXI, 135 p. 29,7 cm (COPPE/UFRJ,M.Sc.,
Engenharia Civil
, 2008)
Dissertação - Universidade Federal do Rio
de Janeiro, COPPE
1. Algoritmo Genético
2. Simulação Cardíaca
I. COPPE/UFRJ II. Título (série)
ads:
iii
Aos meus pais,
Maria Luiza e Márcio, por tudo que eles me
ensinaram, à minha querida esposa Ana, e ao meu
filho Gianluca que veio abrilhantar minha vida no
final deste trabalho.
iv
AGRADECIMENTOS
Aos Professores Nelson Francisco Favilla Ebecken e Rodrigo Weber dos Santos
pela amizade, ensinamentos e orientação precisa e objetiva.
Aos Professores Hélio José Corrêa Barbosa e Beatriz P. de Lima por aceitarem
participar da Banca de avaliação desta tese.
Aos Colegas do Fisiocomp pelo apoio fundamental no desenvolvimento deste
trabalho.
Aos meus familiares principalmente Mãe Maria Luiza, pai Marcio Antonio, que
infelizmente nos deixou no meio da caminhada, a minha esposa Ana, que entendeu
minhas noites em claro e ao meu filho Gianluca que veio a dar um animo novo neste
trabalho.
Aos professores do DCC e aos meus colegas da UFJF, por todo o incentivo
prestado.
v
Resumo da Dissertação apresentada à COPPE/UFRJ como parte dos requisitos
necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)
ALGORITMOS GENÉTICOS DISTRIBUÍDOS APLICADOS AO PROBLEMA
INVERSO DE ELETROFISIOLOGIA CARDÍACA
Daves Marcio Silva Martins
Março/2008
Orientadores: Nelson Francisco Favilla Ebecken
Rodrigo Weber dos Santos
Programa: Engenharia Civil
A modelagem computacional é uma poderosa ferramenta para investigar e
compreender o complexo processo biofísico acerca da eletrofisiologia do coração.
Entretanto, as simulações cardíacas são computacionalmente custosas, em especial com
relação à utilização de memória e aos longos tempos de execução. Este custo tem
historicamente limitado o uso dessa ferramenta ao chamado problema direto. Neste
trabalho, através de técnicas de computação paralela, algoritmos genéticos e modelagem
do coração propõe-se a resolução de um problema inverso associado à eletrofisiologia
cardíaca. O objetivo é estimar valores de condutividade elétrica do tecido cardíaco,
tomando como conhecidas algumas informações elétrica a respeito do coração. Este é
um problema de interesse visto que em muitas patologias cardíacas estes valores
apresentam alterações significativas. Os resultados em um pequeno cluster de sete
computadores sugerem um método promissor. Porem, ainda é necessário continuar com
a pesquisa, o desenvolvimento e a validação desta metodologia para viabilizá-la como
solução para problemas inversos de maior interesse médico-científico.
vi
Abstract of Dissertation presented to COPPE/UFRJ as a partial fulfillment of the
requirements for the degree of Master of Science (M.Sc.)
DISTRIBUTED GENETIC ALGORITHMS APPLIED TO THE INVERSE
PROBLEM OF CARDIAC ELECTROFISIOLOGY
Daves Marcio Silva Martins
March/2008
Advisors: Nelson Francisco Favilla Ebecken
Rodrigo Weber dos Santos
Department: Civil Engineering
Computational modeling is a powerful tool that provides a better understanding
of the biophysical processes involved in cardiac electrophysiology. However, heart
simulations are computationally expensive, especially regarding the use of memory and
at the long execution times. This cost has limited the use of cardiac modeling to the
resolution of direct problems. In this work, using parallel computing, genetic algorithms
and heart modeling we investigate the solution of an inverse problem associated to
cardiac electrophysiology. The goal is to estimate values for the electrical conductivity
of cardiac tissue, taking as known some information concerning the electrical activity of
the heart. This is a problem of interest since in many cardiac pathologies these values
present significant alterations. The results in a small cluster of seven computers suggest
a promising method. However, further research, development and validation of the
proposed methodology are necessary in order to address inverse problems of higher
clinical-scientific interest.
vii
ÍNDICE
Resumo ......................................................................................................................v
Abstract .....................................................................................................................vi
CAPÍTULO 1 INTRODUÇÃO........................................................................................ 1
CAPÍTULO 2 O PROBLEMA PROPOSTO ................................................................... 3
2.1 Modelagem Cardíaca.............................................................................................. 4
2.1.1 Modelos para a Corrente Iônica .................................................................... 10
2.2 EletroCardiograma................................................................................................ 11
2.3 Experimentos tipo “Wedges”................................................................................ 13
2.3.1 Modelagem de um tecido cardíaco normal.................................................... 14
2.3.2 Modelagem de tecidos cardíacos com características de isquemia e infarto. 17
2.4 O Problema Inverso.............................................................................................. 23
CAPÍTULO 3 ALGORITMOS GENÉTICOS............................................................... 24
3.1 Representação dos Cromossomos ........................................................................ 27
3.2 Tipos de Seleções ................................................................................................. 29
3.2.1 Roleta............................................................................................................. 29
3.2.2 Torneio .......................................................................................................... 31
3.2.3 Amostragem Universal Estocástica............................................................... 32
3.3 Tipos de Operadores............................................................................................. 32
3.3.1 Cruzamento (crossover) ................................................................................ 32
3.3.2 Mutação ......................................................................................................... 35
3.4 População ............................................................................................................. 35
3.4.1 Geracional...................................................................................................... 36
3.4.2 Não Geracional.............................................................................................. 36
3.4.3 Elitismo.......................................................................................................... 36
3.5 Parâmetros do AG ................................................................................................ 37
3.5.1 Tamanho da População.................................................................................. 37
3.5.2 Taxa de Cruzamento...................................................................................... 38
3.5.3 Taxa de Mutação ........................................................................................... 38
3.5.4 Condição de Parada ....................................................................................... 38
3.6 Função de Avaliação ............................................................................................ 39
3.7 Algoritmos Genéticos Paralelos ........................................................................... 39
3.8 Modelos de Algoritmos Genéticos Paralelos........................................................ 41
viii
CAPÍTULO 4 METODOLOGIAS E IMPLEMENTAÇÕES COMPUTACIONAIS... 44
4.1 Simulações Cardíacas........................................................................................... 44
4.2 Análise de Sensibilidade....................................................................................... 46
4.3 Algoritmos genéticos............................................................................................ 46
4.4 MPI (Message Passing Interface)......................................................................... 46
4.5 Algoritmo Genético Geracional Síncrono - AGGS.............................................. 47
4.6 Algoritmo Genético Geracional Assíncrono - AGGA ......................................... 49
4.7 Algoritmo Genético Não Geracional Síncrono - AGNGS ................................... 51
4.8 Algoritmo Genético Não Geracional Assíncrono - AGNGA............................... 52
4.9 Evitando a reavaliação de indivíduos ................................................................... 54
4.10 Ambiente de Execução utilizado ........................................................................ 55
4.11 Execuções dos algoritmos genéticos paralelos................................................... 56
CAPÍTULO 5 RESULTADOS ...................................................................................... 58
5.1 Análise de Sensibilidade....................................................................................... 59
5.2 Estudo das Taxas .................................................................................................. 63
5.3 Estudo de Desempenho e Acurácia ...................................................................... 66
5.3.1 Desempenho .................................................................................................. 66
5.3.2 Erro e Aptidão ............................................................................................... 69
5.4 Aplicação de Ruído à base de dados .................................................................... 72
5.4.1 Ruído Branco................................................................................................. 74
5.4.2 Ruído Impulsivo ............................................................................................ 76
5.5 Aplicações, infarto e isquemia.............................................................................. 77
CAPÍTULO 6 DISCUSSÃO .......................................................................................... 83
6.1 Assíncrono x Síncrono ......................................................................................... 84
6.2 Geracional x não Geracional ................................................................................ 85
6.3 Tolerância a Ruído................................................................................................ 86
6.4 Sensibilidade dos parâmetros ............................................................................... 87
6.5 Limitações ............................................................................................................ 88
6.6 Trabalhos Relacionados........................................................................................ 90
6.6.1 The Use of Genetic Algorithms for Solving the Inverse Problem of
Electrocardiography................................................................................................ 90
6.6.2 Application of genetic algorithms to cure heartbeat pathologies .................. 90
6.7 Trabalhos Futuros................................................................................................. 91
6.7.1 Codificação.................................................................................................... 91
ix
6.7.2 MetaModel, Aproximação da função de Aptidão.......................................... 92
6.7.3 Experimentos mais realistas .......................................................................... 93
6.8 Artigos Publicados................................................................................................ 95
6.8.1 Estimating Conductivity Distribution of Transmural Wedges of the Ventricle
Using Parallel Genetic Algorithms......................................................................... 95
6.8.2 Comparing Two Parallel Genetic Algorithms for the Inverse Problem
Associated to the Cardiac Bidomain Equations ..................................................... 95
6.8.3 A computational framework for cardiac modeling based on distributed
computing and web applications ............................................................................ 96
CAPÍTULO 7 CONCLUSÃO........................................................................................ 97
REFERÊNCIAS BIBLIOGRÁFICAS ........................................................................... 99
Anexo A........................................................................................................................ 107
Anexo B........................................................................................................................ 111
Anexo C........................................................................................................................ 116
A Ferramenta de Simulação Cardíaca via WEB – PARACARDIO ........................ 129
Interfaces .................................................................................................................. 131
x
FIGURAS
Figura 2.1 – Visão microscópica do coração.................................................................... 5
Figura 2.2 – Visão da membrana celular (bi-camada lipídica e proteínas que a
permeiam)......................................................................................................................... 6
Figura 2.3 – Modelo da membrana como um capacitor e um resistor em paralelo.......... 6
Figura 2.4 – Esquema de células interconectadas via junções tipo gap ........................... 7
Figura 2.5 – Modelo Bidomínio ....................................................................................... 8
Figura 2.6 – Análise do modelo Bidomínio ..................................................................... 8
Figura 2.7 – Modelo Bidomínio 2D ............................................................................... 10
Figura 2.8 – Medição do ECG........................................................................................ 11
Figura 2.9 - Onda gerada pelo ECG ............................................................................... 12
Figura 2.10 – Esquema para preparação do wedge ........................................................ 13
Figura 2.11 – Potencial Transmembrânico Durante o Estímulo Elétrico no Tecido
Cardíaco.......................................................................................................................... 14
Figura 2.12 – Potencial Transmembrânico no Coração Normal em Instantes Distintos 15
Figura 2.13 – Tecido Simulado ...................................................................................... 16
Figura 2.14 – Gráfico de um ECG Normal em Pontos Distintos ................................... 16
Figura 2.15 – Potencial Transmembrânico no Coração com Isquemia em Instantes
Distintos.......................................................................................................................... 18
Figura 2.16 – Propagação Elétrica no Tecido de Um Coração Doente em Instantes
Distintos.......................................................................................................................... 19
Figura 2.17 – Comparação das Diferenças de Potenciais em Diferentes Partes do Tecido
........................................................................................................................................ 21
Figura 3.1 - Pseudocódigo de um ciclo do Algoritmo Genético .................................... 26
Figura 3.2 – Tipos de representação de cromossomos. .................................................. 28
Figura 3.3 – Representação dos Cromossomos.............................................................. 29
Figura 3.4 – Tabela para seleção roleta .......................................................................... 30
Figura 3.5 – Seleção por torneio..................................................................................... 31
Figura 3.6 – Seleção por Amostragem. .......................................................................... 32
Figura 3.7 – Cruzamento de um ponto ........................................................................... 33
Figura 3.8 – Cruzamento de Multi-Pontos ..................................................................... 34
Figura 3.9 – Cruzamento de Multi-Pontos utilizado. ..................................................... 34
Figura 3.10 – Mutação de intervalo dos Cromossomos ................................................. 35
xi
Figura 3.11 – Esquema de um algoritmo genético paralelo global (mestre-escravo). ... 42
Figura 3.12 – Esquema de um algoritmo genético paralelo de granularidade grossa. ... 42
Figura 3.13 – Esquema de um algoritmo genético paralelo de granularidade fina. ....... 43
Figura 4.1 - Pseudocódigo mestre do AGGS. ................................................................ 48
Figura 4.2 - Pseudocódigo escravo................................................................................. 48
Figura 4.3 – Pseudocódigo mestre do AGGA. ............................................................... 50
Figura 4.4 - Pseudocódigo do AGNGS. ......................................................................... 52
Figura 4.5 - Pseudocódigo do AGNGA. ........................................................................ 53
Figura 4.6 – Implementação da tabela hash. .................................................................. 55
Figura 4.7 – Representação da Arquitetura de um Cluster Assimétrico ........................ 56
Figura 5.1 – ECG traçado com variação do coeficiente intracelular.............................. 59
Figura 5.2 – ECG traçado com variação do coeficiente extracelular ............................. 60
Figura 5.3 - Gráfico da função objetivo ......................................................................... 61
Figura 5.4 - Gráfico do contorno da função objetivo ..................................................... 62
Figura 5.5 - Gráfico da variação extracelular................................................................. 62
Figura 5.6 - Gráfico da variação intracelular.................................................................. 63
Figura 5.7 – Gráfico de estudo dos parâmetros para os algoritmos geracionais. ........... 64
Figura 5.8 – Gráfico de estudo dos parâmetros para os algoritmos não geracionais. .... 65
Figura 5.9 - Evolução da aptidão durante as populações. .............................................. 70
Figura 5.10– Comparativo entre os ECG (0.1, 3.0), (0.051555, 16.380952) e (0.1026,
3.4126)............................................................................................................................ 71
Figura 5.11 – ECG com Ruído Branco........................................................................... 73
Figura 5.12 – ECG com Ruído Impulsivo...................................................................... 74
Figura 5.13 – ECG encontrado na base de dados com ruído branco.............................. 75
Figura 5.14 – ECG encontrado na base de dados com ruído impulsivo......................... 76
Figura 5. 15 - Comparativo entre ECG normal, com isquemia e com infarto. .............. 78
Figura 5.16 – ECG com isquemia e obtido pela simulação. .......................................... 79
Figura 5.17 – Evolução do resultado da aptidão. ........................................................... 79
Figura 5.18 - ECG com infarto e obtido pela simulação................................................ 80
Figura 5.19 - Evolução do resultado da aptidão. ............................................................ 80
Figura 5.20 - ECG normal e obtido pela simulação. ...................................................... 81
Figura 5.21 - Evolução do resultado da aptidão. ............................................................ 81
Figura 6.1 - Gráfico do tempo total em relação ao tempo ocioso do algoritmo............. 84
Figura 6.2 – Codificação Gray. ...................................................................................... 91
xii
TABELAS
Tabela 4.1 – Variáveis importantes para a execução do algoritmo................................ 57
Tabela 5.1 – Parâmetros para a execução do algoritmo. ................................................ 63
Tabela 5.2 – Tempo de execução dos algoritmos........................................................... 67
Tabela 5.3 – Tempo ocioso dos algoritmos.................................................................... 67
Tabela 5.4 – Tempo de avaliação dos indivíduos e das populações............................... 68
Tabela 5.5 – Medidas de desempenho............................................................................ 69
Tabela 5.6 – Pares solução encontrados pelos algoritmos e suas aptidões..................... 69
Tabela 5.7 – Par solução encontrada pelo algoritmo...................................................... 72
Tabela 5.8 – Tabela comparando o resultado obtido sem e com ruído. ......................... 75
Tabela 5.9 – Tabela comparando o resultado obtido sem e com ruído impulsivo. ........ 76
Tabela 5.10 – Tabela comparando os resultados obtidos das doenças cardíacas........... 82
1
CAPÍTULO 1
INTRODUÇÃO
O funcionamento do coração como uma bomba de sangue depende de uma
ótima sincronização da contração das milhares de células cardíacas que formam este
órgão. A contração das células cardíacas, por sua vez, é o resultado de reações
eletroquímicas que ocorrem nas mesmas e em suas vizinhanças. As células do coração
são conectadas de forma a promover a propagação rápida de uma onda eletroquímica
através de todo o órgão, cuja função é a de sincronização. Este fenômeno elétrico que
ocorre no coração está estreitamente relacionado ao fenômeno mecânico da contração.
Diversas cardiopatias estão diretamente relacionadas a problemas na propagação
elétrica no coração, como por exemplo, as arritmias cardíacas, dentre as quais a
fibrilação ventricular é responsável por mais de 300 mil mortes por ano somente nos
Estados Unidos da América. A ferramenta mais utilizada e difundida para o diagnóstico
não invasivo da atividade elétrica do coração é o ECG (Eletrocardiograma). O ECG faz
a medição de potenciais elétricos na superfície do corpo e caracteriza indiretamente a
atividade elétrica cardíaca. Portanto, a interpretação e análise das medidas de ECG é
extremamente difícil e nem sempre possível.
A proposta deste trabalho é investigar uma nova técnica para auxiliar o
diagnóstico de doenças cardiovasculares. Esta técnica se baseia na resolução de um
problema inverso associado à modelagem computacional da atividade elétrica do
coração. Considerando conhecidas algumas medidas do ECG, queremos resolver um
problema inverso para extrair informações mais específicas sobre a passagem de
corrente elétrica pelo tecido cardíaco. Em particular, queremos estimar valores de
condutividade elétrica do tecido cardíaco, visto que em muitas patologias cardíacas
estes valores apresentam alterações significativas.
A modelagem da atividade elétrica do coração foi realizada através da resolução
numérica das equações do Bidomínio para tecidos cardíacos bidimensionais. Foram
utilizadas técnicas de computação paralela e de algoritmos genéticos para a resolução do
problema inverso proposto. O método adotado é baseado em um algoritmo genético que
explora o paralelismo através da técnica mestre-escravo.
2
Os resultados em um pequeno cluster de sete computadores sugerem um método
promissor. Porem, ainda é necessário continuar com a pesquisa, o desenvolvimento e a
validação desta metodologia para viabilizá-la como solução para problemas inversos de
maior interesse médico-científico.
O trabalho que se segue está organizado de maneira a facilitar a compreensão do
assunto. No Capítulo 2 é apresentada uma introdução do conceito de simulação cardíaca
e exposto o problema inverso proposto. No Capítulo 3 a técnica de algoritmo genético é
apresentada, assim como seus principais conceitos. No Capítulo 4 estão
detalhadas a metodologia e as características das implementações computacionais. No
Capítulo 5 são apresentados e discutidos os resultados da aplicação do algoritmo
genético em diagnósticos de doenças do coração. O Capítulo 6 apresenta discussões
sobre vários aspectos relevantes ao trabalho, bem como de trabalhos futuros. O Capítulo
7 é a conclusão do trabalho, com as considerações finais.
3
CAPÍTULO 2
O PROBLEMA PROPOSTO
No homem, a circulação é feita através de um sistema fechado de vasos
sanguíneos, cujo centro funcional é o coração. O coração funciona como uma bomba de
sangue, onde a contração é induzida por impulsos elétricos se movendo entre as células.
Para um ótimo funcionamento, o coração depende da sincronização da contração de
milhares de células cardíacas que formam este órgão. A contração das células cardíacas,
por sua vez, é o resultado de reações eletroquímicas que ocorrem nas mesmas e em suas
vizinhanças. As células do coração são conectadas de forma a promover a propagação
rápida de uma onda eletroquímica através de todo o órgão. Como mencionado, esta
onda elétrica possui a função de sincronização.
A corrente elétrica que flui através dos tecidos cardíacos provoca diferenças de
potenciais em regiões afastadas do coração. A medição dessas diferenças de potencial
na superfície do corpo humano é conhecida como eletrocardiograma (ECG).
Através do ECG diferentes patologias cardíacas podem ser identificadas. Além
disso, o ECG tem a vantagem de ser um exame não invasivo.
Neste Capítulo o objetivo é formular um problema inverso que visa à estimativa
de parâmetros associados a propriedades fisiológicas do tecido cardíaco e envolvem
medidas elétricas não invasivas (ECG) e simulação numérica das atividades elétricas do
coração. Em particular, busca-se estimar a distribuição intracelular e extracelular de
condutividade elétrica de um tecido cardíaco comparando ECGs simulados com um
ECG objetivo. Neste trabalho o ECG objetivo também foi obtido através de simulações
computacionais.
Com este fim, a Seção 2.1 apresenta conceitos e definições para a simulação
computacional cardíaca. A Seção 2.2 mostra os principais conceitos sobre o ECG. A
seção 2.3 apresenta o conceito de “Wedge”, e mostra as vantagens de seu uso em
simulações, além disso, apresenta os resultado da simulação de um coração normal e
corações com patologias cardíacas. E por fim na Seção 2.5 apresenta a formulação do
problema inverso proposto nesse trabalho.
4
2.1 Modelagem Cardíaca
A função do coração é bombear para o corpo o sangue oxigenado pelos
pulmões. O sangue entra pelo átrio e é bombeado para fora através da contração dos
ventrículos. O ventrículo direito fornece sangue para os pulmões enquanto o ventrículo
esquerdo fornece sangue para o resto do corpo.
O tecido dos ventrículos e átrios é formado basicamente de fibras musculares na
forma circular com ramificações que se conectam com as fibras vizinhas. Quando a
célula é eletricamente estimulada, ela rapidamente se despolariza e o potencial no
interior da célula é alterado causando assim a contração da célula. Este sinal elétrico é
passado para as células vizinhas, para que assim, todas as células possam contrair
sincronamente.
O ECG é uma medida de potencial elétrico na superfície do corpo que reflete a
atividade elétrica do coração. Para obter-se uma simulação realista dessa medida é
preciso observar como o sinal elétrico é criado e conduzido no coração. A simulação
cardíaca envolve a resolução de um conjunto de equações diferenciais parciais
acopladas a um grande número de equações diferenciais ordinárias que caracterizam o
comportamento reativo das células.
Vários modelos foram propostos para o coração. Nesse trabalho, será utilizado o
modelo conhecido como Bidomínio (
HOOKE et al, 1994
). Esta formulação é descrita
por um sistema não linear de equações diferenciais parciais que modela os meios
intracelular e extracelular do tecido cardíaco de um ponto de vista eletrostático.
Recentemente, a validação do Bidomínio através de experimentos com animais
(
HENRIQUEZ, 1993) (HENRIQUEZ, VOGEL, ROLF, et al, 2001
) bem como sua
capacidade de reproduzir fenômenos cardíacos (
GESELOWITZ, MILLER, 1983
)
(
HODGKIN, e HUXLEY, 1952
) fazem do Bidomínio um forte candidato para simular o
comportamento elétrico cardíaco.
Para entender o Bidomínio é preciso compreender como as células do coração
estão organizadas. De forma microscópica, um tecido cardíaco, ΩH, é constituído de
meios distintos, o intracelular e o extracelular,
ΩHi e ΩHe respectivamente, que são
5
separados por uma membrana, (DUMAS,
ALAOUI
, 2007). Essa membrana
controla o fluxo das substâncias que entram e saem da célula. A Figura 2.1 mostra uma
visão microscópica do tecido cardíaco.
Figura 2.1 – Visão microscópica do coração.
A Figura 2.2 mostra uma visão esquemática de como as proteínas formam canais
pelos quais íons podem passar pela membrana. Os canais são especializados e somente
uma substância ou um pequeno grupo de moléculas pode passar através de um canal em
particular. Esses são chamados de canais iônicos.
A diferença da composição química e elétrica nos fluídos intracelular e
extracelulares gera uma diferença de potencial na membrana, o potencial
transmembrânico. A Figura 2.2 ilustra uma visão microscópica da membrana.
6
Figura 2.2 – Visão da membrana celular (bi-camada lipídica e proteínas que a permeiam)
A principal característica da membrana seria a de separar cargas. Desta forma, a
membrana pode ser vista como um capacitor, ou seja, duas placas condutoras separadas
por um material isolante. Nesse caso os fluídos intracelular e extracelulares seriam as
placas condutoras, enquanto a membrana seria o material isolante.
O modelo matemático para a membrana deve permitir a passagem de íons
através dos canais iônicos, ou seja, ela não pode ser vista como um simples capacitor. É
mais correto acrescentar ao modelo um resistor ou elemento não linear acoplado em
paralelo ao capacitor, o qual modela a passagem da corrente
ion
I
pelos canais iônicos.
Esse circuito é mostrado na Figura 2.3.
Figura 2.3 – Modelo da membrana como um capacitor e um resistor em paralelo
O modelo matemático da membrana é dado pela equação 2.1:
7
(2.1)
Onde,
Uma vez definida a modelagem da membrana, a atenção deve voltar-se para o
tecido cardíaco, ou seja, a interligação desses modelos celulares. Esse modelo é
conhecido como Bidomínio, descrito por um sistema não linear de EDPs que modela
junto os meios intracelular e extracelular do tecido cardíaco de um ponto de vista
eletrostático.
No Bidomínio o tecido cardíaco é dividido em dois domínios: o intracelular e o
extracelular. Os domínios são contínuos, possuem geometrias idênticas e todo ponto do
músculo cardíaco se encontra em ambos os domínios, os quais estão interligados por
uma membrana semipermeável. A corrente que fluí em cada domínio é puramente
resistiva. Essa é uma suposição razoável para o meio extracelular, onde a corrente pode
fluir num espaço contínuo por entre as células, enquanto no meio intracelular isto pode
ser justificado pelo fato das células estarem interconectadas, possibilitando assim a
passagem de corrente entre células distintas via as chamadas junções tipo gap, canais
protéicos que apresentam resistência efetiva maior que a do interior da célula. A Figura
2.4 ilustra essa visão:
Figura 2.4 – Esquema de células interconectadas via junções tipo gap
dt
d
CII
mionm
φ
+=
8
O circuito apresentado na Figura 2.5, ilustra o modelo Bidomínio.
Figura 2.5 – Modelo Bidomínio
A membrana que separa os dois meios é considerada um dielétrico e é
transpassada por canais iônicos. Como foi discutido anteriormente, a membrana permite
a passagem de correntes capacitiva e iônica entre as duas regiões como ilustrado na
Figura 2.6.
Figura 2.6 – Análise do modelo Bidomínio
O modelo Bidomínio unidimensional é representado na equação 2.2. e 2.3:
xxR
i
∆
)(
i
I
xxR
e
∆
)(
e
I
xxR
i
∆
)(
xxR
e
∆
)(
xxR
i
∆
)(
xxR
e
∆
)(
xxR
i
∆
)(
xxR
e
∆
)(
xxR
i
∆
)(
xxR
e
∆
)(
xI
m
∆ xI
m
∆
xI
m
∆
xI
m
∆
Espaço intracelular
membrana
xxR
i
∆
)(
xxR
i
∆
)(
)(xI
i
)( xxI
i
∆
+
)( xx
i
∆
−
φ
)(x
i
φ
)( xx
i
∆
+
φ
xxR
e
∆
)(
xxR
e
∆
)(
)(xI
e
)( xxI
e
∆
+
)( xx
e
∆
−
φ
)(x
e
φ
)( xx
e
∆
+
φ
xI
m
∆
m
C
Espaço extracelular
9
(2.2)
para o meio intracelular
(2.3)
para o meio extracelular
Onde
ie
φ
φ
φ
,,
são os potenciais transmembrânico, extracelular e intracelular,
respectivamente.
ie
σeσ
são as condutâncias do meio extracelular e intracelular
respectivamente.
χ
é o fator de conversão da área superficial da membrana para o
volume da célula.
ionm
I+
dt
dφ
C
É o modelo da membrana e
ion
I
é o modelo da corrente
iônica.
A generalização bidimensional do Bidomínio é feita considerando-se que as
células estão conectadas em um modelo bidimensional formando um plano (tecido), no
qual cada ponto do meio intracelular está associado a um ponto do meio extracelular
também, como representado na Figura 2.7.
+=
ionm
i
i
I
dt
d
C
dx
d
dx
d
φ
χ
φ
σ
+=
ionm
e
e
I
dt
d
C
dx
d
dx
d
φ
χ
φ
σ
10
Figura 2.7 – Modelo Bidomínio 2D
Com as mesmas suposições feitas anteriormente para os meios intracelular,
extracelular e para membrana, pode-se generalizar o modelo da forma:
(2.4)
(2.5)
2.1.1 Modelos para a Corrente Iônica
Para expressar como a corrente iônica se relaciona com o potencial
transmembrânico será necessário considerar modelos adicionais. Existem vários
modelos celulares para células cardíacas, um deles é o modelo conhecido como
FITZHUGH-NAGUMO (1961) onde o potencial transmembrânico é modelado usando
apenas uma variável extra, n. Este é um modelo qualitativo que infelizmente não
reproduz satisfatoriamente os sinais do ECG.
O modelo para a corrente iônica utilizado nesse trabalho foi o modelo
quantitativo conhecido como TEN TUSSCHER et al. (2004). O modelo matemático
posposto por TEN TUSSCHER et al. (2004) alia alto nível de detalhamento eletro-
( )
+
∂
∂
=∇⋅∇
ionmii
I
t
C
φ
φσ
X
( )
+
∂
∂
−=∇⋅∇
ionmee
I
t
C
φ
φσ
X
11
fisiológico com eficiência computacional. Ele é baseado em dados experimentais
recentes da maioria das correntes iônica: sódio, cálcio, potássio, entre outros. O modelo
pode reproduzir o potencial de diferentes células do coração humano, como as células
do epicárdio, do endocárdio, e as células tipo M.
O modelo é definido da seguinte forma:
(2.7)
Maiores detalhes sobre o modelo podem ser encontrados em TEN TUSSCHER
(1996).
2.2 EletroCardiograma.
O eletrocardiograma (ECG) é amplamente utilizado na clínica médica. O exame
consiste na medição de potenciais que se estabelecem na superfície do corpo resultantes
da atividade elétrica cardíaca. O sinal é medido através de eletrodos que são colocados
em diversos pontos do corpo.
Figura 2.8 – Medição do ECG
Em um ECG é possível distinguir três sinais: A onda P, associada à atividade
elétrica dos átrios. O complexo QRS, que corresponde à despolarização dos ventrículos.
E a onda T, que está associada à repolarização dos ventrículos.
12
Figura 2.9 - Onda gerada pelo ECG
Os sinais medidos são da ordem de milivolt, de modo que, embora sejam
filtrados com o objetivo de libertá-los de freqüências indesejáveis, são, geralmente,
fáceis de se medir. A análise das amplitudes relativas dos picos, relação temporal e
morfologia das ondas é adotada pelos cardiologistas e visam à detecção de anomalias do
funcionamento cardíaco.
13
2.3 Experimentos tipo “Wedges”
Por se tratar do coração um órgão muito complexo, a simulação em toda sua
região seria muito custosa, e inviável com relação ao tempo computacional. Por isso nas
simulações cardíacas costuma-se utilizar uma técnica conhecida como “
Wedge
”. Esta é
homônima à técnica experimental muito utilizado em laboratórios de fisiologia que
consiste em se retirar um pedaço do tecido e realizar um estudo sobre esse tecido
retirado.
A utilização da
wedge
tem se mostrado bastante promissora e contribui para uma
melhor compreensão de determinados fenômenos, como por exemplo, detalhes da fibra
do coração e a distribuição de corrente extracelular e intracelular (YAN, SHIMIZU,
ANTZELEVITCH, 1998). A Figura 2.10 mostra a preparação experimental para o uso
da técnica
wedge
. Nesta figura, vemos em detalhes, os três principais tipos de células
que compõem o tecido do ventrículo humano. Ou seja, as células do epicárdio,
endocárdio e do tipo M.
Figura 2.10 – Esquema para preparação do wedge
As medidas elétricas obtidas em preparações experimentais tipo
Wedge
são
muitos semelhantes aos ECG’s obtidos na superfície do corpo humano. Em particular, a
Posicionar
Eletrodos
.
14
wedge
é capaz de simular algumas patologias cardíacas importantes (YAN, SHIMIZU,
ANTZELEVITCH, 1998).
2.3.1 Modelagem de um tecido cardíaco normal
A partir de um eletrocardiograma (ECG), é possível compreender um pouco
melhor a saúde do coração. Para este trabalho utilizou-se a modelagem cardíaca para
simular os ECGs. As simulações deste trabalho utilizaram um tecido bidimensional
cardíaco com dimensões de 2,0cm x 3,0cm, isto é, as dimensões típicas de um corte
transmural (Wedge) do ventrículo esquerdo humano. A simulação é iniciada através da
aplicação de um estímulo elétrico nesse tecido. A Figura 2.11 ilustra a distribuição do
potencial transmembrânico no tecido no momento do estímulo elétrico.
Figura 2.11 – Potencial Transmembrânico
Durante o Estímulo Elétrico no Tecido
Cardíaco
Após este estímulo inicial o potencial elétrico gerado se propaga ao longo do
coração, este estímulo é iniciado na porção superior esquerda do tecido e se propaga de
cima para baixo e da esquerda para a direita. Em um coração normal essa propagação
deve ser uniforme conforme ilustra a Figura 2.12.
15
Figura 2.12 – Potencial Transmembrânico no Coração Normal em Instantes Distintos
Através destes gráficos pode-se notar que o potencial elétrico não encontra
resistência, ou baixa resistência, para percorrer o tecido cardíaco. Isto se deve ao fato de
que as células cardíacas apresentam uma boa condutividade.
Ao longo desse tecido estudado, são alocados cinco eletrodos em pontos
distintos. O ponto a esquerda é o eletrodo de referência, utilizado em todas as quatro
medidas, estas realizadas com os pontos da direita, como mostrado na Figura 2.13.
Cada par de eletrodos caracteriza um eletrograma e tem como objetivo capturar
a diferença de potencial entre eles em cada instante de tempo.
16
Figura 2.13 – Tecido Simulado
Os gráficos da Figura 2.14 mostram os quatros eletrogramas simulados. Pode-se
perceber que o potencial elétrico não sofre nenhuma diferença brusca de uma medição
para outra, justamente pela forma de propagação da onda não encontrar muita
dificuldade ao longo do tecido.
Figura 2.14 – Gráfico de um ECG Normal em Pontos Distintos
17
Podemos perceber que apesar das ondas serem de tamanhos diferentes, o tempo
na qual elas ocorrem são praticamente os mesmos, isso se deve ao fato da pouca
resistência encontrada pela corrente na passagem pelo coração, uma característica de um
coração normal, saudável.
2.3.2 Modelagem de tecidos cardíacos com características de isquemia e
infarto
A isquemia é provocada pela falta de circulação sanguínea, que impede a
chegada de nutrientes e de oxigênio ao tecido. A isquemia determina redução imediata e
progressiva da contratilidade do miocárdio. A dinâmica da movimentação normal de
íons, em especial potássio, cálcio e sódio, começa a se alterar. Na isquemia o tecido
está, portanto, em sofrimento.
O infarto é a morte de uma área do músculo cardíaco, cujas células ficaram sem
receber sangue com oxigênio e nutrientes. A interrupção do fluxo de sangue para o
coração pode acontecer de várias maneiras. A gordura vai se acumulando nas paredes
das coronárias (artérias que irrigam o próprio coração). Com o tempo, formam-se
placas, impedindo que o sangue flua livremente. Dessa forma, as células no trecho que
deixou de ser banhado pela circulação acabam morrendo.
Tanto na isquemia quanto no infarto, estão presentes dezenas de alterações
fisiológicas importantes. Uma característica comum a essas duas patologias é a
alteração das condutividades elétricas do tecido cardíaco. As observações relatadas por
HOPENFELD (2004) em estudos com tecidos isquêmicos, sugerem uma diminuição da
condutividade intracelular devido a alterações das junções GAP’s. Além disso, foi
observada uma redução do volume extracelular devido ao inchamento do miocárdio, o
que conduz à diminuição da condutividade extracelular. Já o infarto crônico é
caracterizado com a redução do espaço intracelular e da condutividade devido à perda
do miocárdio, e o aumento correspondente do espaço e da condutividade extracelular,
conforme relatado previamente por FALLERT M, MIROTZNIK, (1993).
Foram realizadas simulações com tecidos que apresentam determinada região
com isquemia e outros com característica de infarto. No caso das regiões com isquemia,
a condutividade interna era apenas 10% da condutividade normal, e a externa era de
65% da normal. No tecido infartado, a condutividade interna também era de 10% da
condutividade normal, e a externa era três vezes maior que a normal.
18
A figura 2.15 ilustra a passagem de corrente pelo tecido com isquemia. Pode-se
notar certa resistência à sua passagem pela região afetada.
Figura 2.15 – Potencial Transmembrânico no Coração com Isquemia em Instantes
Distintos
A Figura 2.16 mostra o comportamento do potencial elétrico nesse tecido
infartado.
19
Figura 2.16 – Propagação Elétrica no Tecido de Um Coração Doente em Instantes
Distintos
Pode-se notar que a propagação apresenta um padrão diferente. A propagação
encontra resistência ao passar pela região afetada.
Foram realizadas medidas do potencial extracelular em quatro pontos
específicos, conforme mostra a Figura 2.17.
20
1º Ponto de Medição
2
º Ponto de Medição
21
Figura 2.17 – Comparação das Diferenças de Potenciais em Diferentes Partes do Tecido
Os gráficos da Figura 2.17 mostram que o ECG não teve um comportamento
igual ao de um tecido normal, houve um retardo na passagem do potencial elétrico entre
as células. Isto se deve ao fato da condutividade do tecido ter sofrido alterações.
3
º Ponto de Medição
4
º Ponto de Mediç
ão
22
Percebe-se que, a amplitude da onda T no caso de isquemia é menor do que no
caso do infarto. Além disso, nas duas patologias ocorre o atraso das ondas T e R.
23
2.4 O Problema Inverso
Nesta Seção, formulamos o problema inverso deste trabalho.
Seja conhecida uma sub-região de tecido (como na Figura 2.13) que apresenta
alguma alteração no par de condutividades (
σ
i
, σ
e
), em uma determinada região;
Sejam conhecidos quatro eletrogramas (ECGs) medidos pelos eletrodos
descritos na Figura 2.13 ( , com i = 1...4).
Queremos estimar as condutividades na sub-região afetada, isto é, queremos
estimar α e β, onde (
ασ
i
, βσ
e
) é o par de condutividades da região afetada e (
σ
i
, σ
e
) é o
par de condutividades padrão.
O problema inverso consiste na minimização da função:
(2.8)
Ou seja, queremos estimar o melhor par (
α, β
) que minimiza a Equação 2.8.
(2.9)
Onde i varia de 1 a np, np é o número de eletrogramas. Em nosso caso foram
realizadas quatro medidas, como pode ser visto na Figura 2.13. , é o i-ésimo
eletrograma objetivo observado no tempo jdt, onde dt é a discretização no tempo, j varia
de 1 a nt, sendo nt o número total de discretizações. , é o i-ésimo
eletrograma simulado para um dado par (α,β).
Os ECG’s tomados como objetivo também foram obtidos através de simulações,
o que significa que são também artificiais.
24
CAPÍTULO 3
ALGORITMOS GENÉTICOS
Neste capítulo serão descritos os conceitos e a origem dos algoritmos genéticos,
AG, assim como suas técnicas, operações e utilidades no contexto deste trabalho.
Na natureza, os indivíduos competem entre si por recursos como comida, água e
refúgio. Adicionalmente, entre os animais de uma mesma espécie, aqueles que não
obtêm êxito tendem a ter um número reduzido de descendentes. Conseqüentemente
existe uma menor probabilidade de seus genes serem propagados ao longo de sucessivas
gerações. De acordo com Charles Darwin:
“Quanto melhor um indivíduo se adaptar ao seu meio ambiente, melhor será
sua chance de sobreviver e gerar descendentes”.
Os Algoritmos Genéticos utilizam uma analogia direta deste fenômeno de
evolução na natureza, onde cada indivíduo representa uma possível solução para um
dado problema (
MITCHELL, 1996
).
Os AG’s são uma família de modelos computacionais inspirados na evolução,
que incorporam uma solução potencial para um problema específico, numa estrutura
semelhante à de um cromossomo e aplicam operadores de seleção, cruzamento e
mutação a essas estruturas de forma a preservar informações críticas relativas à solução
do problema. Normalmente os AG's são vistos como otimizadores de funções, embora a
quantidade de problemas para os quais os AG's se aplicam seja bastante abrangente.
Uma das vantagens de um algoritmo genético é a simplificação que eles
permitem na formulação e solução de problemas de otimização. AG's simples
normalmente trabalham com descrições de entrada formadas por cadeias de bits de
tamanho fixo. Outros tipos de AG's podem trabalhar com cadeias de bits de tamanho
variável, como por exemplo, AG's usados para Programação Genética. AG's possuem
um paralelismo implícito decorrente da avaliação independente de cada uma dessas
cadeias de bits, ou seja, pode-se avaliar independentemente a viabilidade de um
conjunto de parâmetros para a solução do problema de otimização em questão.
Os principais conceitos que serão abordados nesta seção estão brevemente
descritos a seguir:
25
Cromossomo – Estrutura de dados formada por uma seqüência de genes.
Codifica uma solução para o problema. Descreve um indivíduo.
Gene – Componente elementar de um cromossomo, geralmente responsável pela
codificação de um parâmetro, ou seja, um elemento do vetor que representa o
cromossomo de acordo com o alfabeto utilizado (binário, inteiro ou real).
Alelo – Representa os valores (dados) que um gene pode assumir.
Indivíduo – Uma solução candidata de um problema.
População – Conjunto de indivíduos que formam uma geração.
Geração – Iteração completa do algoritmo genético que determina os indivíduos
que irão compor a nova população.
Aptidão – saída gerada pela função objetivo para um indivíduo da população.
Para cada indivíduo é atribuída uma pontuação referente à sua aptidão, que será
dada por uma função objetivo
.
Aos mais adaptados é dada a oportunidade de
reproduzir-se mediante cruzamentos com outros indivíduos da população, produzindo
descendentes com características de ambas as partes.
A função objetivo de um problema de otimização é construída a partir dos
parâmetros envolvidos no problema. Ela fornece uma medida da proximidade da
solução em relação a um conjunto de parâmetros. Os parâmetros podem ser conflitantes,
ou seja, quando um aumenta o outro diminui. O objetivo é encontrar o ponto ótimo. A
função objetivo permite o cálculo da aptidão bruta de cada indivíduo. Esta aptidão
influenciará a probabilidade do indivíduo ser selecionado para reprodução.
Os algoritmos genéticos procuram privilegiar indivíduos com melhores aptidões,
com isso tentam dirigir a busca para regiões do espaço de busca onde é provável que os
pontos ótimos estejam.
Os algoritmos genéticos diferem-se dos métodos tradicionais de busca e
otimização principalmente em quatro aspectos:
[1]
Podem trabalhar com uma codificação do conjunto de parâmetros e não com os
próprios parâmetros;
[2]
Trabalham com uma população e não com um único ponto;
26
[3]
Utilizam informações de custo ou recompensa e não derivadas de outro
conhecimento auxiliar;
[4]
Utilizam regras de transição probabilísticas e não determinadas.
O primeiro passo dos algoritmos genéticos é a geração de uma população inicial
de indivíduos (possíveis soluções). Durante o processo evolutivo, esta população é
avaliada e cada indivíduo recebe uma nota (denominada de aptidão), refletindo a
qualidade da solução que ele representa. Em geral, os indivíduos mais aptos são
selecionados e os menos aptos são descartados. Os indivíduos selecionados podem
sofrer modificações em suas características fundamentais através dos operadores de
cruzamento (
crossover
) e mutação, gerando descendentes para a próxima geração. Este
processo é repetido até que uma solução satisfatória seja encontrada. A Figura 3.1
apresenta um ciclo de um Algoritmo Genético.
Figura 3.1 - Pseudocódigo de um ciclo do Algoritmo Genético
Apesar de aparentemente simples, estes algoritmos são capazes de resolver
problemas complexos de uma maneira muito elegante.
27
Deve ser observado que cada cromossomo, chamado de indivíduo no AG,
corresponde a um ponto no espaço de soluções do problema de otimização. O processo
de solução adotado nos algoritmos genéticos consiste em gerar, através de regras
específicas, um grande número de indivíduos, uma população, de forma a promover
uma varredura tão extensa quanto necessária do espaço de soluções.
Existem vários tipos de implementações de algoritmos genéticos que podem ser
combinadas a fim de que se tenha um resultado melhor para cada tipo de problema.
Algumas implementações diferem no que diz respeito à forma de se tratar a população
de indivíduos. O tratamento tradicional leva o nome de geracional. Nesta
implementação a cada geração toda a população é renovada a partir de operações
genéticas aplicadas a indivíduos da população anterior. Pode-se também adotar um
critério de seleção elitista, onde os k melhores pais nunca são substituídos. Outra
implementação é conhecida como
steady-state
ou não geracional. Esta implementação
gera apenas um ou dois filhos por vez que substituem os dois piores cromossomos da
população (WHITLEY, 1989). Neste trabalho o
steady-state
foi implementado de uma
forma modificada.
3.1 Representação dos Cromossomos
Os indivíduos são análogos a cromossomos e podem ter diversas representações
e são sobre esses cromossomos que são realizadas as operações genéticas. A escolha de
uma representação é muito importante para o sucesso de um algoritmo genético. Todo
cromossomo representa um indivíduo candidato à solução do problema.
Existem várias maneiras de se representar um cromossomo, uma das formas
mais utilizadas é a representação binária, na qual os parâmetros são codificados em 0s e
1s, a fim de representar uma solução do problema. Embora esta representação tenha
sido amplamente utilizada e tem se mostrado eficiente para vários problemas, existem
outras representações como, por exemplo, a representação por inteiros, em que um
cromossomo é descrito por um vetor de números inteiros, a representação por reais, ou
até mesmo, a representação por string (
MITCHELL, 1996
).
28
Independentemente do tipo de representação selecionada, deve-se 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.
A Figura 3.2 ilustra exemplos de representações utilizando codificação real,
string e binária respectivamente.
Figura 3.2 – Tipos de representação de cromossomos.
Na representação real cada número representa um gene, ou seja, um parâmetro
para a solução do problema. Na representação por string e na binária, um conjunto de
letras ou bits (0 e 1) pode representar um gene.
Os operadores genéticos devem ser implementados de acordo com a
representação escolhida.
Neste trabalho foi utilizada uma representação binária. Nesta, busca-se saber se
a condutividade aumentou ou diminuiu x vezes, com x entre 1 e 20. Cada parâmetro a
ser estimado é representado por sete bits. Para transformar o número binário usado na
representação para um número real foi utilizada a função:
(3.1)
, onde
P = É o desvio máximo (em nosso caso 20);
T = O tamanho do gene (em nosso caso 7);
Sinal
T
P
MantissaParâmetro
−
−
+=
−
12
1
*1
1
29
Sinal = É dado pelo bit mais significativo do gene, b7. Se b7 = 0 o número será maior
que 1, caso contrario o número gerado será entre 0 e 1.
Mantissa = É um número inteiro que corresponde aos seis bits menos significativo da
representação;
Na Figura 3.3, aplicando a função indicada, os parâmetros são respectivamente
0,102606 e 8,841270. Esta representação foi utilizada em todos os algoritmos genético
apresentados neste trabalho.
Figura 3.3 – Representação dos Cromossomos
3.2 Tipos de Seleções
Na seleção, os indivíduos mais aptos da geração atual são selecionados. Esses
indivíduos são utilizados para gerar uma nova população por cruzamento ou mutação.
Cada indivíduo tem uma probabilidade de ser selecionado proporcional à sua aptidão.
Os métodos de seleção mais conhecidos são:
• Roleta
• Torneiro
• Amostragem Universal Estocástica
3.2.1 Roleta
Esse método de seleção é o mais simples e também o mais utilizado. Os
indivíduos de uma geração são selecionados para a próxima geração utilizando uma
30
roleta. Neste método, cada indivíduo da população é representado na roleta conforme
seu valor de aptidão. Desta forma, os indivíduos com elevada aptidão receberão
intervalos maiores na roleta, enquanto aqueles que têm menores aptidões receberão
menores intervalos na roleta.
Após a distribuição na roleta, são gerados aleatoriamente valores no intervalo
entre 0 e o total do somatório da aptidão de todos os indivíduos da população. Isto é
feito um determinado número de vezes, dependendo do tamanho da população. O
indivíduo que possuir em seu intervalo o valor gerado será selecionado. Os indivíduos
selecionados são inseridos na população intermediária.
Repete-se o sorteio quantas vezes forem necessárias para selecionar a
quantidade desejada de indivíduos para gerar uma nova população.
A Figura 3.4 mostra uma tabela gerada para a seleção por roleta.
Figura 3.4 – Tabela para seleção roleta
31
Neste trabalho foi utilizado este método de seleção. Os indivíduos que possuem
melhores aptidões possuem regiões maiores na “roleta” e, portanto, terão maior
probabilidade de serem selecionados para gerar a população seguinte.
De forma simplificada, o método da roleta é realizado em três passos:
1. Encontre a soma de 1/aptidão de todos os membros da população AT = Σ Ai.
Como o problema é de minimização utilizamos Ai = 1/aptidão.
(0 ≤ i ≤ tamanho da população - 1)
2. Gere um número aleatório 0 ≤ random ≤ AT.
3. Tome o primeiro membro da população k cujo somatório de Ai acumulado é
maior ou igual ao número aleatório gerado.
ΣAi ≥ random (i < k).
Em uma solução do problema a aptidão seria igual a zero e um erro seria
causado nesses cálculos. Para tratar esse erro a aptidão nesse caso foi substituída por 1,
visto que nossos experimentos computacionais não encontraram nenhum experimento
menor que um.
3.2.2 Torneio
Neste método n indivíduos da população são escolhidos aleatoriamente, com a
mesma probabilidade. O indivíduo com maior aptidão dentre estes n indivíduos é
selecionado para a população intermediária. O processo se repete até que a população
intermediária seja preenchida. Figura 3.5.
Figura 3.5 – Seleção por torneio.
32
3.2.3 Amostragem Universal Estocástica
Este método é uma variação do Método da Roleta em que, em vez de uma única
agulha, n agulhas igualmente espaçadas são utilizadas, onde n é o número de indivíduos
a serem selecionados. Assim, em vez de n vezes, a roleta é girada uma única vez.
A figura 3.6 ilustra o método Amostragem sendo utilizado.
Figura 3.6 – Seleção por Amostragem.
3.3 Tipos de Operadores
O algoritmo genético tem grande capacidade de explorar o espaço de busca e
tem a capacidade de intensificar um ponto dentro do espaço de busca. A primeira
característica visa à exploração do espaço de busca e a fuga de mínimos locais. Já a
segunda tem como objetivo a aproximação do mínimo local. Essas características são as
duas grandes vantagens do uso do Algoritmo Genético e são obtidas pela correta
aplicação dos operadores genéticos (GOLDBERG, 1989).
3.3.1 Cruzamento (crossover)
Os indivíduos selecionados na etapa anterior são cruzados da seguinte forma: a
lista de indivíduos selecionados é utilizada para realizar o cruzamento de alguns deles
com os demais indivíduos da população. Os cromossomos de cada par de indivíduos a
33
serem cruzados são particionados, chamado ponto de cruzamento ou corte, sorteado
aleatoriamente. Um novo cromossomo é gerado permutando-se o segmento inicial de
um cromossomo com o segmento final do outro.
O cruzamento utiliza a informação contida em dois ou mais indivíduos pais, para
gerar um ou mais novos indivíduos. Esse processo tende a não acrescentar novas
informações à população, por explorar apenas a região próxima aos indivíduos pais
(
SILVA, 2005
).
Os Tipos de Cruzamento mais utilizados são:
• Cruzamento Um-Ponto;
• Cruzamento Multi-Pontos;
Na reprodução baseada em um ponto de cruzamento, o ponto de quebra do
cromossomo é escolhido de forma aleatória sobre a longitude do cromossomo e a partir
desse ponto se realiza a troca de material cromossômico entre os dois indivíduos. Na
Figura 3.7 tem-se um esquema da representação desse tipo de cruzamento.
Figura 3.7 – Cruzamento de um ponto
Deve-se notar que se o cromossomo for representado por uma cadeia de bits, o
ponto de corte pode incidir em qualquer posição (bit) no interior de um gene, não
importando os limites do gene.
Na reprodução baseada em Multi Pontos, procede-se de maneira similar ao
cruzamento de um ponto, mas a troca de segmentos é realizada a partir dos pontos de
cruzamento conforme ilustra a Figura 3.8.
34
Figura 3.8 – Cruzamento de Multi-Pontos
Neste trabalho foi utilizado um cruzamento multi-pontos, onde um cruzamento
foi feito para cada um dos parâmetros. Ou seja, dois cortes foram utilizados, um para
cada parâmetro, conforme ilustra a Figura 3.9.
Figura 3.9 – Cruzamento de Multi-Pontos utilizado.
35
3.3.2 Mutação
Em genética a mutação pontual é um processo no qual um alelo de um gene é
aleatoriamente substituído (ou modificado) por outro, resultando em um novo
cromossomo. O operador de mutação tem o objetivo de melhorar a diversidade na
população, impedindo problemas de convergência prematura. Em AG a operação de
mutação é utilizada para garantir uma maior varredura do espaço de busca e evitar a
convergência a mínimos locais. Geralmente existe uma baixa probabilidade de mutar
cada gene de um cromossomo: a Taxa de mutação recomendada: 0,1% < pm < 5%
(
LIMA
, 2005).
Há diversas formas de se implementar a mutação. Uma das mais utilizadas, e
adotada neste trabalho, inverte o valor de bits, com uma dada probabilidade, pm. A
mutação somente ocorre naqueles alelos que tiverem o número aleatório associado a
eles menor que a taxa pm. Veja Figura 3.10.
Figura 3.10 – Mutação de intervalo dos Cromossomos
3.4 População
36
3.4.1 Geracional
O Algoritmo genético geracional é aquele que, a cada passo de execução, gera
uma nova população substituindo toda a população anterior. São aplicados os operados,
cruzamento e mutação, a fim de se montar uma nova população e cada indivíduo dessa
nova população terá sua aptidão calculada.
3.4.2 Não Geracional
Algoritmos genéticos
steady-state
são algoritmos onde a cada iteração somente
os indivíduos menos aptos são substituídos. Nesse algoritmo pelo menos um indivíduo
da população é substituído a cada execução. Este indivíduo é selecionado pela sua
aptidão. O novo indivíduo é obtido através da mutação ou cruzamento de outros
membros da população ativa. Qualquer método de seleção pode ser utilizado para
selecionar os indivíduos para gerar o próximo indivíduo. Nesse tipo de algoritmo os
piores indivíduos são sempre eliminados (WHITLEY, 1989).
3.4.3 Elitismo
O elitismo consiste em privilegiar o melhor indivíduo migrando-o para a nova
população, sem que este sofra cruzamento ou mutação. Com isso é garantido que o
melhor indivíduo não será perdido.
Neste trabalho o elitismo foi utilizado com duas abordagens totalmente distintas.
A primeira foi implementada em um algoritmo genético geracional, onde era migrada
somente a melhor solução para a próxima geração. A segunda abordagem foi um
algoritmo genético não geracional, também conhecido como
steady-state
, onde a
população não era toda reciclada. Esta segunda abordagem implementa, portanto, uma
taxa de elitismo superior.
37
3.5 Parâmetros do AG
Existem vários parâmetros do algoritmo genético que podem ser escolhidos para
melhorar o seu desempenho, adaptando-o às características particulares de determinadas
classes de problemas. Entre eles os mais importantes são: o tamanho da população, o
número de gerações, a probabilidade de cruzamento e a probabilidade de mutação. A
influência de cada parâmetro no desempenho do algoritmo depende da classe de
problemas que se está tratando. Assim, a determinação de um conjunto de valores
otimizado para estes parâmetros dependerá da realização de um grande número de
experimentos e testes (CANTÚ-PAZ, 1997) e (GOLDBERG, 1989).
Na maioria da literatura os valores encontrados estão na faixa de 60 a 65% para
a probabilidade de
crossover
e entre 0,1 a 5% para a probabilidade de mutação (
LIMA
,
2005). O tamanho da população e o número de gerações dependem da complexidade do
problema de otimização e devem ser determinados experimentalmente. No entanto,
deve ser observado que o tamanho da população e o número de gerações definem
diretamente o tamanho do espaço de busca a ser coberto. Existem estudos que utilizam
um AG como método de otimização para a escolha dos parâmetros de outro AG, devido
à importância da escolha correta destes parâmetros (MIRANDA, 2007).
3.5.1 Tamanho da População
O tamanho da população determina o número de cromossomos na população,
afetando diretamente o desempenho global e a eficiência dos AG’s. Com uma
população pequena, o desempenho pode cair, pois deste modo a população fornece uma
pequena cobertura do espaço de busca do problema. Uma grande população geralmente
fornece uma cobertura representativa do domínio do problema, além de prevenir
convergências prematuras (tendência da população a evoluir para uma solução não
ótima em razão da existência de um indivíduo com aptidão muito superior às demais
aptidões). No entanto, para se trabalhar com grandes populações, são necessários
maiores recursos computacionais ou que o algoritmo trabalhe por um período de tempo
muito maior.
38
3.5.2 Taxa de Cruzamento
Quanto maior for esta taxa, mais rapidamente novas estruturas serão
introduzidas na população. Mas se esta for muito alta, a maior parte da população será
substituída, e pode ocorrer perda de estruturas de alta aptidão. Com um valor baixo, o
algoritmo pode tornar-se muito lento e demorar a convergir para a solução.
3.5.3 Taxa de Mutação
A taxa de mutação determina a probabilidade com que uma mutação ocorrerá. A
mutação é utilizada para se introduzir nova informação na população e também para
prevenir que a população sature com cromossomos semelhantes (convergência
prematura).
Com uma taxa muito alta a busca se torna essencialmente aleatória, além de
aumentar muito a possibilidade de que uma boa solução seja destruída. A melhor taxa
de mutação é dependente da aplicação, mas, para a maioria dos casos está entre 0,1% e
5% (BÄCK, 1996).
3.5.4 Condição de Parada
A melhor parada para um algoritmo genético seria no ponto ótimo, por ser tratar
de um algoritmo de otimização, mas nem sempre isso é possível ou viável. Porém na
maioria dos casos de interesse, não se pode afirmar com certeza se um dado ponto
corresponde a um ótimo global. Como conseqüência, normalmente usa-se o critério do
número máximo de gerações ou um tempo limite de processamento para parar um
algoritmo genético. Outro critério plausível é parar o algoritmo usando a idéia de
estagnação, ou seja, quando não se observa melhoria da população depois de várias
gerações consecutivas, isto é, quando a aptidão média ou do melhor indivíduo não
melhora ou quando as aptidões dos indivíduos de uma população se tornarem muito
parecidas.
39
3.6 Função de Avaliação
A função de avaliação é a parte mais importante do algoritmo genético. É essa
função que atribui a todos os indivíduos um valor de aptidão, que será utilizado para
ordenar a população e aplicar as operações genéticas para a formação da nova
população. Esse valor de aptidão será de suma importância e decidirá se um indivíduo
continuará ou não a gerar descendentes.
Neste trabalho busca-se estimar as condutividades na sub-região afetada, isto é,
deseja-se estimar α e β, onde (
ασi, βσe
) é o par de condutividades da região afetada e
(
σi,σe
) é o par de condutividades padrão, que descreve tecidos normais.
A função de avaliação do algoritmo genético efetua a comparação de ECGs
simulados com ECGs dados para tentar estimar apenas os parâmetros (α, β). Assume-se
que todos os outros parâmetros que envolvem o modelo são conhecidos e fixados.
Os ECGs tomados como objetivo também são obtidos através de simulações, o
que significa que são também artificiais. A função de avaliação foi apresentada na
equação 2.8, mostrada anteriormente.
No trabalho desenvolvido, tem-se o ECG gerado pela simulação dos parâmetros
objetivo. Os indivíduos candidatos são simulados e geram os seus respectivos ECG’s. A
aptidão do indivíduo será dada pelo erro (norma2) entre esse dois ECG. Quanto menor
for esse erro, melhor será a aptidão do par em avaliação e consequentemente, melhor o
indivíduo será classificado.
3.7 Algoritmos Genéticos Paralelos
Uma das grandes dificuldades encontrada no problema é o longo tempo de
execução do cálculo da função objetivo, ou aptidão. Isto se deve à complexidade de
simulação do tecido cardíaco. Portanto, a utilização de computação paralela tornou-se
essencial.
A computação paralela, ou distribuída, auxilia a resolução de problemas que
envolvem tarefas grandes e complexas, em que é aplicável a estratégia dividir para
40
conquistar. Ela consiste em adicionar o poder computacional de diversos processadores
para processar colaborativamente determinada tarefa de forma coerente e transparente,
ou seja, como se apenas um único e centralizado computador estivesse executando a
tarefa. A união desses diversos computadores com o objetivo de compartilhar a
execução de tarefas é conhecida como sistema distribuído.
A principal meta ao usar uma abordagem paralela para um algoritmo é melhorar
o tempo de computação reduzindo o tempo de processamento global. Contudo a forma
de implementar o paralelismo pode variar e, por vezes, depende das soluções em
hardware disponíveis. De uma forma geral (CARRERA, LOQUES, 1998), há duas
formas de explorar o paralelismo em um algoritmo: através do particionamento de
dados e de tarefas.
● Paralelismo de dados (CARRERA, LOQUES, 1998): uma mesma tarefa é
alocada aos diversos processadores, sendo que cada nó trabalha com uma porção de
dados diferentes do outro nó. Esta abordagem é aplicada a alguns problemas clássicos:
1. Resolução de sistemas de equações
2. Multiplicação de matrizes
3. Integração numérica
4. Mineração de dados
● Paralelismo de tarefas (CARRERA, LOQUES, 1998): tarefas diferentes são
alocadas aos processadores, podendo existir um grupo de processadores responsável por
certa tarefa. Um problema clássico: Problema do produtor-consumidor.
Um ponto importante que vale ressaltar é que o tempo de execução da função
objetivo varia de acordo com os parâmetros passados. Portanto, indivíduos diferentes
têm tempos de execução diferentes, o que pode levar à situações onde há máquinas
ociosas no sistema.
Na próxima seção será apresentado um breve levantamento bibliográfico sobre
algoritmos genéticos paralelos e a comunicação utilizada, síncrona ou assíncrona.
41
3.8 Modelos de Algoritmos Genéticos Paralelos
Os algoritmos genéticos são considerados algoritmos implicitamente paralelos,
sendo esta característica um dos seus pontos fortes. Atualmente existe uma procura cada
vez maior por algoritmos que, além de resolver os problemas de forma aceitável,
também os resolvem de um modo distribuído, pois cada vez mais a tendência está
voltada para a utilização de sistemas paralelos (BERKENBROCK, ROJAS, 2004). Os
algoritmos genéticos possuem uma estrutura computacional altamente paralelizável.
Assim, ao analisar-se a estrutura de algoritmo genético chega-se às seguintes
conclusões:
• Cada indivíduo da população tem uma aptidão x, que pode ser avaliada
independentemente de qualquer outro fator.
• Cada operador e operação genética são independentes e podem ser aplicados
em qualquer ordem a qualquer elemento da população.
Observando mais uma vez a natureza, conclui-se que nela todos os processos são
paralelos, ou seja, os processos seqüenciais é que não são naturais.
De acordo com CANTÚ-PAZ (1997) existem três tipos (modelos) principais de
Algoritmos Genéticos Paralelos. Uma forma é distribuir o cálculo da função objetivo
para cada geração criada por um ciclo de cruzamento e/ou mutação (paralelismo
funcional) dada uma mesma população para cada processador. Nesta abordagem existe:
Modelo de Paralelização Global, Mestre-Escravo (Figura 3.11): normalmente
são versões paralelas de algoritmos genéticos seqüenciais, que operam sobre uma
população global e são síncronos de forma a permitir que em cada processador seja
executada uma parte do AG. Por exemplo, é possível que o processador 1 execute a
combinação (
crossover
), o processador 2 execute a mutação e o processador 3 a
avaliação da função objetivo (aptidão). Esse modelo lembra a execução em pipeling,
comumente utilizada em aplicações como a integração numérica. Normalmente é
necessário uma rede de comunicação muito rápida e grande quantidade de memória no
processador que gerencia a computação. Isto torna o modelo fortemente dependente do
hardware utilizado.
42
Figura 3.11 – Esquema de um algoritmo genético paralelo global (mestre-escravo).
Outra forma é atribuir a cada processador um subconjunto da população
executando paralelamente os ciclos evolutivos e permutando os indivíduos mais
evoluídos (paralelismo de dados). Nesta abordagem existem:
Granularidade Grossa, Modelo das ilhas (Island Model) (Figura 3.12): Neste
procedimento o AG é executado em subpopulações (ilhas) que trocam entre si os
melhores indivíduos (possíveis soluções) de cada geração. Esta comunicação é dada
pela operação de migração, responsável pelas trocas de indivíduos entre as ilhas. Neste
modelo, devido ao alto custo de comunicação, a taxa de migração não deve ser muito
elevada.
Figura 3.12 – Esquema de um algoritmo genético paralelo de granularidade grossa.
Granularidade Fina, Modelo de vizinhança (Neighborhood Mode
l
) (Figura
3.13): Neste modelo uma única população evolui e cada indivíduo é colocado em uma
43
célula de uma grade planar. Os processos de combinação e seleção são aplicados
somente entre vizinhos na grade (de acordo com a topologia adotada).
Figura 3.13 – Esquema de um algoritmo genético paralelo de granularidade fina.
Na granularidade fina existe um alto grau de paralelismo, porém, o overhead de
comunicação, é maior do que ao associado à implementação por ilhas.
Neste trabalho foram implementados versões do modelo de paralelização global
(mestre-escravo), porém com algumas diferenças quanto à distribuição das tarefas.
Nestas implementações, o mestre faz todas as operações genéticas e distribui os
indivíduos para os escravos, que calculam somente a aptidão, que é a tarefa mais
complexa de nossa aplicação.
44
CAPÍTULO 4
METODOLOGIAS E IMPLEMENTAÇÕES
COMPUTACIONAIS
Neste capítulo serão apresentados os detalhes das implementações e da
metodologia adotada. A infra-estrutura computacional será detalhada assim como as
quatro diferentes implementações de algoritmos genéticos para a resolução do problema
inverso proposto.
4.1 Simulações Cardíacas
Em seus trabalhos sobre a propagação de ondas elétricas no coração, SANTOS
(2002) implementou um simulador bidimensional para as equações do Bidomínio. Essa
implementação será utilizada neste trabalho.
O simulador foi desenvolvido para o sistema operacional Linux, em linguagem
C, tendo sua implementação feita sobre a biblioteca PETSc Portable, Extensible Toolkit
for Scientific Computation (SANTOS, 2002). Essa biblioteca fornece um conjunto de
estruturas de dados e rotinas para a solução em paralelo de aplicações científicas
modeladas por equações diferenciais parciais. A biblioteca PETSc utiliza o padrão MPI:
Message Passing Interface para de troca de mensagens entre os processadores.
O simulador cardíaco bidimensional utilizado neste trabalho é formado por um
sistema de equações não lineares, e para a resolução destas equações, foi utilizado um
método semi-implícito. Maiores detalhes sobre o esquema numérico podem ser obtidos
em (
MARTINS, XAVIER e SANTOS, 2006
).
O simulador recebe parâmetros de entrada que descrevem a geometria do tecido
cardíaco, assim como outros parâmetros, como as condutividades
ie
e
σ
σ
.
Como saída, o simulador fornece a variação no tempo e no espaço dos potencias
elétricos.
45
Para facilitar o uso do simulador e disponibilizar o mesmo na web, foi
desenvolvido o Portal Fisiocomp, que possui como principal objetivo promover o
desenvolvimento da modelagem cardíaca, através da disponibilização de diversas
ferramentas numéricas. O simulador cardíaco foi transformado em uma aplicação web.
Esta aplicação web está detalhada no anexo IV, assim como no trabalho publicado
(
MARTINS, XAVIER e SANTOS, 2006
) que se encontra no anexo III.
As simulações cardíacas foram executadas sob um tecido com dimensões de
1,0cm x 2,0cm. Este tecido está imerso em banho, condutor passivo e isotrópico,
formando uma região de 2,0cm x 3,0cm. O tecido apresenta uma região retangular de
0.3 x 0.7 cm, localizada no centro, com condutividades alteradas que reproduzem uma região
patológica.
A Figura 2.13 ilustra o tecido simulado. Todos os parâmetros utilizados na
simulação foram baseados em SANTOS (2006).
A condutividade do banho foi definida como sendo 20 mS/cm. A capacitância
por unidade de área e a razão de área de superfície por volume foram tomadas como
e 2000 cm, respectivamente. Os passos de discretização espacial e
temporal do modelo numérico são e , respectivamente. Todas as
simulações representam 550 ms de atividade elétrica depois que um único estímulo foi
realizado em um local do endocárdio.
A Condutividade na região não afetada é dada pelos tensores de condutividade
intra e extracelular,
ie
e
σ
σ
. As condutividades longitudinais nas direções das
fibras cardíacas para os meios intracelular e extracelular são tomadas como 7.72
mS/cm e 1.62 mS/cm., respectivamente. As condutividades transversais as fibras para
os meios intracelular e extracelular são tomadas como 5.14 mS/cm e 4.52 mS/cm.,
respectivamente.
Na região afetada os tensores de condutividade intracelular e extracelular são
multiplicados pelos escalares
α e β
.
46
4.2 Análise de Sensibilidade
Uma análise de sensibilidade é importante para determinar a contribuição de
cada parâmetro para a solução do problema. Neste caso deseja-se conhecer qual o
impacto das condutividades, intracelular e extracelular no ECG.
Foram realizadas simulações com parâmetros normais (1,1), assim como com
condutividades dobradas ou reduzidas a metade. Além disso, plotamos a função
objetivo em torno da solução, isto é, do mínimo global.
4.3 Algoritmos genéticos
Implementamos quatro algoritmos genéticos paralelos para a resolução do
problema inverso proposto. Os algoritmos diferem entre si pelo tipo de evolução da
população utilizada, geracional ou não geracional, também conhecido como
steady-state
(WHITLEY, 1989), e pela forma de comunicação utilizadas, síncrona ou assíncrona.
Os algoritmos foram implementados foram realizadas na linguagem C++. Para
permitir a troca de mensagens entre processos foi utilizada a biblioteca MPI.
4.4 MPI (Message Passing Interface)
Na implementação do algoritmo paralelo foi utilizado uma biblioteca de rotinas
conhecida por MPI (
Message Passing Interface
). O modelo de programação utilizado
pelo MPI é simples.
A biblioteca de MPI foi desenvolvida para ambientes de memória distribuída,
máquinas paralelas, rede de estações de trabalho e redes heterogêneas. MPI define um
conjunto de rotinas para facilitar a comunicação (troca de dados e sincronização) entre
processos paralelos. A biblioteca MPI é portável para qualquer arquitetura, tem
inúmeras funções para programação e ferramentas para se analisar o desempenho
(MESSAGE, 2007). A biblioteca MPI possui rotinas para programas em Fortran 77 e
ANSI C, portanto pode ser usada também para Fortran 90 e C++. Os programas são
47
compilados e ligados à biblioteca MPI. Todo o paralelismo é explícito, ou seja, o
programador é responsável por identificar o paralelismo e implementar o algoritmo
utilizando chamadas aos comandos da biblioteca MPI. Cada processo, identificado pelo
seu IP ou pelo nome da máquina na rede, recebe uma réplica do código do programa
paralelo como um todo. O trecho de código particular de cada processo (se houver) é
identificado por um comando em que a condição envolve a sua identificação.
As próximas seções apresentam pseudocódigos que contém comandos para
envio de mensagens. Estes foram implementados utilizando a função MPI_Send. Em
outros momentos foi necessário o uso do comando MPI_Waitall, para aguardar o
recebimento de mensagens. A principal característica deste comando é a suspensão da
execução do problema enquanto não tiverem sido recebidos todos os dados enviados. _
utilizamos também o comando MPI_Waitany, o qual causa um bloqueio da execução do
programa até a chegada de alguma mensagem.
4.5 Algoritmo Genético Geracional Síncrono - AGGS
O primeiro algoritmo utilizado no trabalho foi um algoritmo mestre-escravo
clássico. O mestre é o responsável por preparar a população, realizar as operações
genéticas de seleção, cruzamento e mutação, além de distribuir a avaliação dos
indivíduos entre as máquinas escravas. Não há necessidade de comunicação entre os
escravos. A operação de envio do cromossomo do indivíduo para avaliação será aqui
denominada operação de envio de indivíduos. Neste primeiro algoritmo, está operação é
síncrona, ou seja, só são enviados novos indivíduos quando todos os indivíduos
enviados retornarem das máquinas escravas.
Os indivíduos são enviados até que toda a população tenha sido enviada. Após o
cálculo das aptidões de toda a população, a máquina mestre gera uma nova população e
o processo de envio se inicia novamente.
Neste algoritmo as máquinas escravas podem ficar ociosas, pois o tempo de
cálculo da aptidão não é o mesmo para indivíduo distintos, mesmo em um ambiente
computacional homogêneo.
48
O algoritmo é iniciado com a criação da população inicial. Os indivíduos dessa
população devem ser enviados para as máquinas escravas para o cálculo de suas
aptidões. A Figura 4.1 mostra o pseudocódigo do algoritmo.
Figura 4.1 - Pseudocódigo mestre do AGGS.
No pseudocódigo acima, mp indica o numero de máquinas escravas na
execução.
A figura 4.2 mostra o pseudocódigo da máquina escrava.
Figura 4.2 - Pseudocódigo escravo.
O pseudocódigo da máquina escrava foi utlizado em todas as implementações.
49
Após o envio dos primeiros indivíduos, a máquina mestre fica aguardando o
retorno dos proc indivíduos para que possa enviar os próximos indivíduos. Só são
enviados novos indivíduos quando todas as máquinas retornarem seus resultados.
Enquanto isso não ocorre, uma máquina que já tenha terminado seus cálculos fica
ociosa aguardando um novo indivíduo.
Esse processo se repete até que todos os indivíduos da população tenham suas
aptidões calculadas.
Após o cálculo de todos os indivíduos da população, a máquina mestre é
responsável por gerar uma nova população aplicando os operadores genéticos. O AGGS
utiliza os operadores básicos de cruzamento e mutação. Além disso, o algoritmo utiliza
elitismo, perpetuando o melhor indivíduo para as próximas populações. Esse não deverá
ser calculado novamente, portanto a segunda população e as populações seguintes têm
um indivíduo a mais que a primeira.
Esse processo se repete até que o critério de parada seja satisfeito.
4.6 Algoritmo Genético Geracional Assíncrono - AGGA
O segundo algoritmo utilizado no trabalho também foi um algoritmo mestre-
escravo clássico, parecido com o algoritmo anterior, porém mais flexível na forma de
envio dos indivíduos para o cálculo da aptidão. Os envios de indivíduos para as
máquinas escravas são feitos de forma assíncrona, ou seja, são enviados indivíduos e
assim que um retorna, um próximo é enviado.
O conceito de população aqui é mantido e serve como um ponto de
sincronização do algoritmo. Assim, nesta implementação, o envio de indivíduos é
assíncrono. A sincronização ocorre no momento em que todos os indivíduos de uma
população já foram enviados. Neste momento, algumas máquinas podem ficar ociosas
até que as últimas aptidões sejam calculadas e que o mestre processe e gere uma nova
população.
A Figura 4.3 ilustra o pseudocódigo do algoritmo.
50
Figura 4.3 – Pseudocódigo mestre do AGGA.
Após o envio dos primeiros indivíduos, a máquina mestre fica aguardando o
retorno de algum individuo para que possa enviar o próximo.
Esse processo se repete até que todos indivíduo sem aptidão tenham sido
enviados. Nesse caso, máquinas escravas podem ficar ociosas aguardando o cálculo das
últimas aptidões de uma população.
Após o cálculo de todos os indivíduos da população a máquina mestre cria uma
nova população aplicando os operadores genéticos.
Os critérios de parada são os mesmos do algoritmo anterior, ou seja, por número
de populações ou por resultado da aptidão próximo a zero.
51
4.7 Algoritmo Genético Não Geracional Síncrono - AGNGS
O terceiro algoritmo utilizado no trabalho foi um algoritmo mestre-escravo não
geracional, ou seja, o algoritmo não cria uma nova população como nos modelos
anteriores. Agora é criada uma lista de indivíduos que se mantém sempre ordenada e
cada novo indivíduo calculado substitui o pior indivíduo da lista. Dessa forma os
melhores indivíduos são sempre deixados nessa lista e os piores tendem a ser
descartados, não participando assim das operações genéticas. Neste algoritmo,
conforme comenta WHITLEY (1989), os pais convivem numa mesma população com
os descendentes.
O envio dos indivíduos para os cálculos é síncrono, ou seja, só são enviados
novos indivíduos quando as aptidões dos proc indivíduos enviados retornarem. O envio
dos primeiros indivíduos é similar ao feito no algoritmo genético geracional síncrono,
ou seja, os indivíduos são enviados proc a proc até que todos os indivíduos da lista
tenham sido calculados.
Após a lista de indivíduos ter sido toda calculada, são criados novos proc
indivíduos para que sejam enviados às máquinas escravas, onde terão suas aptidões
calculadas. O mestre espera até que todos retornem e retira os proc piores indivíduos da
lista e insere na lista os novos indivíduos gerados. Enquanto isso, não ocorre, uma
máquina que já tenha terminado seus cálculos fica ociosa.
O inicio do algoritmo é similar aos anteriores, até que todos os indivíduos
tenham suas aptidões calculadas, Figura 4.4 mostra o pseudocódigo do algoritmo.
52
Figura 4.4 - Pseudocódigo do AGNGS.
No pseudocódigo acima, naval indica o numero de indivíduos avaliados.
O critério de parada é o mesmo do algoritmo anterior.
4.8 Algoritmo Genético Não Geracional Assíncrono - AGNGA
O quarto e último algoritmo implementado neste trabalho foi um algoritmo
mestre-escravo não geracional. O que difere do algoritmo anterior é a forma de envio
que é assíncrona, ou seja, a cada indivíduo avaliado, um novo é gerado e enviado para
cálculo da aptidão.
O envio dos primeiros indivíduos é similar ao feito no AGNGS. Ou seja, os
indivíduos são enviados proc a proc até que todos os indivíduos da lista inicial tenham
sido calculados.
53
Diferentemente do algoritmo anterior que espera os proc indivíduos chegarem,
agora a cada indivíduo que chega um novo é enviado e a lista é reordenada. Com essa
ação, o tempo ocioso das máquinas é reduzido.
Figura 4.5 apresenta o pseudocódigo desse algoritmo.
Figura 4.5 - Pseudocódigo do AGNGA.
Após o envio dos primeiros indivíduos, a máquina mestre fica aguardando o
retorno de algum indivíduo para que possa enviar outro da lista. .
Após o cálculo de todos os indivíduos da lista, a máquina mestre é responsável
por gerar novos indivíduos aplicando os operadores genéticos em indivíduos dessa
população, onde serão gerados novos indivíduos.
Esses novos indivíduos gerados deverão ser enviados para as máquinas escravas
e quando o primeiro retornar será colocado na lista de indivíduos substituindo o pior. A
lista deve ser então, ordenada pela aptidão, para que os piores fiquem no final.
54
4.9 Evitando a reavaliação de indivíduos
O cálculo da aptidão é uma tarefa custosa e demorada e nos algoritmos
implementados foi percebido que a geração de indivíduos repetidos acontecia com certa
freqüência. Para evitar a reavaliação foi criada uma tabela
hash
.
Tabela
hash
é uma estrutura de dados especial, que associa chaves de pesquisa
(
hash
) a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida
e obter o valor desejado (
HASH, 2008
).
Primeiramente é preciso levar em consideração que um indivíduo possui 14
alelos, como foi utilizada a representação binária, tem-se então 14 bits, 0 ou 1. Assim, é
possível representar 16384 indivíduos diferentes, 2
14
. Esse é o tamanho da tabela
utilizada. O individuo binário, convertido para inteiro foi utilizado como chave de
pesquisa e sem o valor da aptidão armazenado.
Para implementar essa tabela
hash
foi utilizado um vetor onde é possível
armazenar a aptidão calculada ou -1 caso não se tenha o cálculo. O número binário é
transformado para inteiro e indica a posição a ser armazenada. Dessa forma, antes de
enviar um indivíduo para o cálculo, ele é transformado para inteiro. Verifica-se no vetor
se naquela posição já existe um valor diferente de -1. Caso exista, o indivíduo já foi
calculado. Caso contrário, o indivíduo é novo e pode ser calculado. Assim que este novo
indivíduo tiver sua aptidão calculada, este deve ser armazenado na tabela
hash
.
Veja exemplo abaixo, figura 4.6:
55
Figura 4.6 – Implementação da tabela hash.
4.10 Ambiente de Execução utilizado
As implementações e todos os testes realizados nesse trabalho foram feitos no
ambiente distribuído do Laboratório de Fisiologia Computacional (Fisiocomp), na
Universidade Federal de Juiz de Fora.
Esse ambiente corresponde a um cluster de computadores formado por sete
máquinas AMD Athlon 64, com 3 GHz de clock e 2Gb de memória principal. A
conexão entre as máquinas é feita através de um switch 3Com de 1 Gbps.
Um cluster de computadores pode utilizar arquitetura simétrica ou assimétrica.
(TENEMBAUM, 2000).
O cluster utilizado possui uma arquitetura assimétrica. Em clusters assimétricos,
uma máquina, é denominada frontend e as outras máquinas são conectadas a esta
através de um switch. A Figura 4.7 apresenta uma representação de um cluster de
computadores utilizando arquitetura assimétrica. O frontend possui duas interfaces de
comunicação. Uma delas está ligada à rede pública e a outra está ligada à rede interna e,
56
consequentemente, aos nós. Assim, os nós do cluster não se ligam diretamente à rede
pública. Dessa forma, a gerência e a segurança de todo o cluster ficam mais
simplificadas, pois todos os dados trafegados podem ser filtrados pelo frontend, já que
obrigatoriamente passam por ele.
Figura 4.7 – Representação da Arquitetura de um Cluster Assimétrico
Nas execuções de nossos algoritmos o frontend é tratado como máquina mestre
e os demais nós são tratadas como máquinas escravas. Portanto quando for dito uma
execução em sete máquinas, estamos executando com uma máquina mestre e seis
escravas.
4.11 Execuções dos algoritmos genéticos paralelos
Serão apresentados os resultados obtidos a partir das simulações e execuções dos
algoritmos descritos no capítulo anterior.
No próximo capitulo será apresentado um estudo realizado sobre as taxas de
crossover e mutação de cada algoritmo implementado. Este estudo visa escolher as
melhores taxas para execução dos algoritmos genéticos. Será também apresentado um
estudo comparativo do desempenho de cada algoritmo, mostrando informações como
número de avaliações realizadas, número de indivíduos repetidos, tempo ocioso do
57
algoritmo e
throughput computacional.
Os algoritmos também serão comparados com
relação à acurácia dos resultados numéricos obtidos, a aptidão e o erro RRMS. Por fim,
um pequeno estudo será realizado a respeito da tolerância a ruídos da metodologia
proposta.
Todos os resultados apresentados foram obtidos através da simulação de um
tecido de dimensão 2,0cm x 3,0cm imerso em banho, como descrito na Seção 4.1.
Todos os algoritmos foram executados com seguintes parâmetros de
configuração, Tabela 4.1:
Variável Valor Descrição
sizeParent 7 Número de indivíduos a serem selecionados.
numgens 50 Número de gerações executadas.
popsize 24 Tamanho da população no caso do geracional, ou da lista
no caso do não geracional.
l 14 Tamanho do cromossomo, número de bits.
crossoverProb 0.85 Probabilidade de ocorrer o crossover.
mutationProb 0.05 Probabilidade de ocorrer a mutação.
Tabela 4.1 – Variáveis importantes para a execução do algoritmo.
Por uma questão de moneclatura, nos algoritmos não geracionais, também
denominamos de população uma lista de 24 indivíduos com suas aptidões já calculadas.
58
CAPÍTULO 5
RESULTADOS
Neste Capítulo serão apresentados os resultados obtidos a partir das simulações
e execuções dos algoritmos descritos no capítulo anterior.
A Seção 5.1 apresenta um estudo da sensibilidade dos parâmetros que o
algoritmo deseja encontrar. Na Seção 5.2 será apresentado um estudo realizado sobre as
taxas de crossover e mutação de cada algoritmo. Este estudo visa escolher as melhores
taxas para execução dos algoritmos genéticos. A Seção 5.3 apresenta um estudo
comparativo do desempenho de cada algoritmo, mostrando informações como número
de avaliações realizadas, número de indivíduos repetidos, tempo ocioso do algoritmo e
throughput computacional.
Na mesma Seção 5.3 também foram comparados os
algoritmos com relação aos resultados numéricos obtidos, como a aptidão e o erro
RRMS, isto é, a distância entre os parâmetros encontrados e os parâmetros desejados. A
Seção 5.4 faz um estudo a respeito da tolerância a ruído na base de dados. Foram
aplicados dois tipos de ruído: o primeiro é conhecido como ruído branco; o segundo
tipo de ruído é conhecido como impulsivo em que apenas alguns pontos destoam dos
demais.
Todos os resultados apresentados nas Sessões 5.2, 5.3, 5.4 e 5.5, foram obtidos
através da simulação de um tecido de dimensão 2,0cm x 3,0cm imerso em banho. Esse
tecido contém uma região central afetada, ou seja, as condutividades intra e extracelular
são modificadas por um par de parâmetros (α,β). As execuções simulam 550 ms da
atividade elétrica.
Na Seção 5.5, utilizamos modelos que reproduzem características do infarto do
miocárdio e da isquemia cardíaca. Assim poderemos verificar a capacidade do
algoritmo de prever e encontrar tecidos cardíacos com características das doenças
supracitadas.
59
5.1 Análise de Sensibilidade
Uma análise de sensibilidade é geralmente executada no sentido de determinar o
tamanho da contribuição de cada parâmetro para a solução do problema. Neste caso
desejamos conhecer, qual o impacto de cada condutividade, intracelular e extracelular
para o ECG.
Foram realizadas execuções com valores de parâmetros próximos e foram
traçados os ECG’s respectivos.
A Figura 5.1, mostra um ECG de um tecido normal, ou seja, com parâmetros
normais (α,β) = (1,0, 1,0). Em relação a um ECG que teve sua condutividade
intracelular reduzida à metade da condutividade normal, ou seja, (α,β) = (0,5, 1,0). E
ainda comparamos com relação a um ECG que teve sua condutividade intracelular
dobrada da normal, (α,β) = (0,2, 1,0).
Figura 5.1 – ECG traçado com variação do coeficiente intracelular
Podemos perceber que a mudança no primeiro parâmetro causou uma
modificação em todo o ECG, as ondas iniciaram instantes depois do primeiro ECG. Isso
é explicável pelo fato de termos reduzido pela metade à condutividade intracelular a
corrente assim teve mais facilidade para fluir pelo tecido. Já com a segunda mudança,
60
percebemos que as ondas foram iniciadas antes do ECG normal, isto se deve ao fato da
condutividade intracelular ter ficado o dobro da normal.
A partir dos gráficos podemos perceber que o primeiro parâmetro provoca um
deslocamento no inicio da onda R e T, alem de uma mudança na onde R.
Vamos agora aplicar a variação no segundo parâmetro, ou seja, no coeficiente
extracelular. A Figura 5.2 mostra o ECG com as mesmas variações da figura anterior,
mas agora, o coeficiente extracelular reduzido pela metade e duplicado em relação ao
normal.
Figura 5.2 – ECG traçado com variação do coeficiente extracelular
Com a variação do coeficiente extracelular, podemos perceber que a mudança no
ECG foi menor, basicamente, houve uma mudança na altura atingida pela onde T.
Como o coeficiente extracelular foi reduzida pela metade a amplitude da onda T
também foi diminuída.
Assim como aconteceu na redução da condutividade extracelular, o seu aumento
causou uma mudança na onda T, que teve uma amplitude maior que a normal já que seu
coeficiente extracelular foi duplicado.
61
Portanto os ECG’s são mais sensíveis a mudanças na condutividade intracelular.
O mesmo ficou comprovado com o resultado da aptidão em relação aos parâmetros (1,0
e 1,0). Os parâmetros (0,5 e 1,0) apresentaram uma aptidão de 32,8674, já com os
parâmetros (1,0 e 0,5) tiveram aptidão de 15,8766, mostrando assim que uma pequena
variação no primeiro parâmetro tem maior impacto do que no segundo parâmetro.
A Figura 5.3 e 5.4 mostra o gráfico da função objetivo ao redor do ponto
objetivo. Esses gráficos foram gerados com a variação dos parâmetros α e β de 0 a 4. O
eixo x é o coeficiente intracelular, o y é o coeficiente extracelular e z é a aptidão.
Vale ressaltar que o coeficiente intracelular e o extracelular, tiveram sua notação
modificada para facilitar a visualização do gráfico. Foi usada a representação em binário
do cromossomo do indivíduo sendo esta transformada para um número inteiro. Com
essa representação os pontos ficam mais distantes e a função objetivo fica mais simples
de ser visualizada.
Figura 5.3 - Gráfico da função objetivo
62
Figura 5.4 - Gráfico do contorno da função objetivo
Na Figura 5.5 é mostrada a variação da aptidão em relação ao coeficiente
extracelular, o coeficiente intracelular foi fixado em 0.1. Podemos perceber que a
aptidão varia suavemente com a variação do coeficiente extracelular.
0,00
5,00
10,00
15,00
20,00
25,00
30,00
35,00
40,00
45,00
50,00
0
,
0
0
0,20
0
,
4
0
0
,
6
0
0,80
1
,
0
0
1,20
1
,
4
0
1,60
1
,
8
0
2,00
2
,
2
0
2
,
4
0
2
,
60
2
,
8
0
3,00
3
,
2
0
3,40
3
,
6
0
3,80
Coeficiente extracelular
Aptidão
Figura 5.5 - Gráfico da variação extracelular
Já na Figura 5.6 é mostrada a variação da aptidão em relação ao coeficiente
intracelular, o coeficiente extracelular foi fixado em 3.0. Podemos perceber que a
aptidão varia de forma brusca o redor do mínimo.
63
0,00
20,00
40,00
60,00
80,00
100,00
120,00
140,00
0,00
0,0
7
0
,20
0
,50
0,8
0
1
,00
1,30
1,60
1,
90
2
,20
2,5
0
2,8
0
3
,10
3,4
0
3,
70
Coeficiente intracelular
Aptidão
Figura 5.6 - Gráfico da variação intracelular
5.2 Estudo das Taxas
Dois parâmetros que podem influenciar o desempenho do algoritmo são as taxas
de cruzamento e de mutação. Uma pequena mudança nessas taxas pode trazer uma
grande mudança no tempo e no resultado do algoritmo. Por exemplo, uma alta taxa de
mutação pode deixar o algoritmo muito aleatório o que pode ser bom para fuga de
mínimos locais. Nesse trabalho esses parâmetros foram ajustados visando melhorar o
desempenho do algoritmo. Os testes foram realizados com um número de populações
menores, 20 e com um tempo total de simulação menor, 200 ms. A tabela 5.1 apresenta
os parâmetros utilizados.
Variável Valor Descrição
Tempo da
simulação do
ECG
200 ms Tempo de simulação do ECG de um indivíduo.
Taxas de
Mutação
De 5%
a 35%
Taxas de
Combinação
De
70% a
100%
Número máximo
de populações
20 Utilizado no critério de parada.
Tabela 5.1 – Parâmetros para a execução do algoritmo.
64
Nos algoritmos geracionais foram realizados testes com taxas de cruzamento
variando de 70% a 100% e taxas de mutação variando de 5% a 35% com passo de 5%.
A Figura 5.7 apresenta o numero da geração na qual o melhor indivíduo foi obtido
versus a reta valor para o par (taxa de cruzamento, taxa de mutação).
AGGS e AGGA
25
28
27
28
29
32
35
23
23
24
25
25
27
27
10
12
12
12
14
16
16
9
9
10
13
14
18
9
9
11
12
12
14
14
12
12
13
12
15
16
16
8
0
5
10
15
20
25
30
35
40
(70, 5)
(70, 10)
(70, 15)
(70, 20)
(70, 25)
(70, 30)
(70, 35)
(75, 5)
(75, 10)
(75, 15)
(75, 20)
(75, 25)
(75, 30)
(75, 35)
(80, 5)
(80, 10)
(80, 15)
(80, 20)
(80, 25)
(80, 30)
(80, 35)
(85, 5)
(85, 10)
(85, 15)
(85, 20)
(85, 25)
(85, 30)
(85, 35)
(90, 5)
(90, 10)
(90, 15)
(90, 20)
(90, 25)
(90, 30)
(90, 35)
(95, 5)
(95, 10)
(95, 15)
(95, 20)
(95, 25)
(95, 30)
(95, 35)
Figura 5.7 – Gráfico de estudo dos parâmetros para os algoritmos geracionais.
65
Os resultados obtidos sugerem que o melhor par de taxas é (85%, 5%). Portanto,
essas taxas foram utilizadas nas simulações realizadas nas Seções abaixo pelos
algoritmos geracionais.
Já nos algoritmos não geracionais, a taxa de cruzamento considerada foi a de
100%, uma vez que se busca sempre gerar um novo indivíduo para ser calculado. A taxa
de mutação variou de 5% a 35%, com passo de 5%. A Figura 5.8 mostra os resultados
obtidos. Apesar dos algoritmos não geracionais não levarem em consideração o
conceito de população, adotamos a mesma moneclatura, ou seja, cada 24 indivíduos
calculados conta como uma população.
AGNGS e AGNGA
6
9
15
15
20
28
6
0 5 10 15 20 25 30
(100, 5)
(100, 10)
(100, 15)
(100, 20)
(100, 25)
(100, 30)
(100, 35)
Figura 5.8 – Gráfico de estudo dos parâmetros para os algoritmos não geracionais.
Nessa situação, duas taxas de mutação 5% e 10% alcançaram os mesmos
resultados. Foi adotada a taxa de 5¨% nas demais execuções realizadas nas Sessões
seguintes.
66
5.3 Estudo de Desempenho e Acurácia
Os algoritmos genéticos geracionais foram executados com 50 gerações. Em
cada uma das iterações 24 indivíduos são avaliados. Dessa forma, esses algoritmos
avaliam 1200 indivíduos durante sua execução (24 indivíduos x 50 iterações). Foram
realizados testes com cinco e sete máquinas.
Já os algoritmos não geracionais foram executados com a primeira iteração
avaliando todos os 24 indivíduos da população. As iterações seguintes avaliaram
apenas, os seis ou quatro novos indivíduos gerados por cruzamento e mutação dos seis
ou quatro melhores indivíduos, de acordo com o número de máquinas escravas. O
número de iterações varia de acordo com o número de máquinas. Com sete máquinas
foram feitas 196 iterações, já com cinco máquinas foram necessárias 300 iterações.
Assim, esse algoritmo também avalia 1200 indivíduos durante sua execução, 24
indivíduos + 6 indivíduos x 196 iterações ou 24 indivíduos + 4 indivíduos x 300
iterações.
Esses algoritmos possuem um mecanismo, uma tabela hash, para verificar a
avaliação prévia de um indivíduo específico, evitando assim que um indivíduo seja
reavaliado. O uso da tabela hash foi explicado no capítulo anterior.
As execuções dos algoritmos serão analisadas sob dois aspectos, desempenho e
acurácia. Primeiro é preciso investigar o comportamento do algoritmo em relação aos
tempos de execução e consumo de recurso computacional. Já com relação ao erro,
interessa estudar as aptidões encontradas pelos algoritmos, bem como os erros nos
parâmetros de condutividade encontrados.
5.3.1 Desempenho
Como primeira medida de desempenho, tem-se o tempo total de execução dos
algoritmos. A Tabela 5.2 mostra os resultados.
67
Máquinas escravas Tempo de Execução (horas:min)
4 276:05 ≈ 11 dias
AGGS
6 177:28 ≈ 8 dias
4 219:56 ≈ 9 dias
AGGA
6 146:26 ≈ 6 dias
4 248:37 ≈ 10 dias
AGNGS
6 170:10 ≈ 7 dias
4 211:10 ≈ 8 dias
AGNGA
6 130:49 ≈ 5 dias
Tabela 5.2 – Tempo de execução dos algoritmos.
Como é possível perceber o algoritmo não geracional assíncrono foi o mais
rápido nos testes realizados. Como veremos, isto se deve, em parte, ao melhor uso dos
processadores e menor tempo ocioso.
Para calcular o tempo ocioso do algoritmo, foi utilizado o tempo que cada
máquina ficou aguardando o recebimento de um novo indivíduo a ser calculado. Para
isso, utilizou-se a fórmula 5.1:
(5.1)
Máquinas
escravas
% de tempo ocioso
4 21,8 %
AGGS
6 19,9 %
4 3,33 %
AGGA
6 5,2 %
4 15,0 %
AGNGS
6 13,7 %
4 2,02 %
AGNGA
6 4,4 %
Tabela 5.3 – Tempo ocioso dos algoritmos.
A tabela 5.3 mostra os resultados para o tempo ocioso de todas as execuções.
.
.
.
1
execuçãonagastoTempoY
imáquinadaociosoTempoX
execuçãonaescravasmaquinasdeNúmerocpu
onde;
Ycpu
X
=Ociosidade
i
cpu
=i
i
−
−
−
∗
∑
68
Percebe-se nitidamente que os algoritmos assíncronos têm menor ociosidade,
isto se deve ao fato de uma máquina não precisar aguardar o término dos cálculos das
outras.
Outro fator importante no desempenho do algoritmo é o tempo de cálculo dos
indivíduos e das populações. A Tabela 5.4 ilustra esses dados. Para montar essa tabela
foi levado em consideração o maior e menor tempo, tempo médio e desvio padrão.
Tempo de Avaliação por indivíduo (horas) Tempo de Avaliação por População (horas)
Máquinas
escravas
Maior Menor Médio
Desvio
Padrão
Maior Menor Médio
Desvio
Padrão
4 01:00:00 00:42:00 00:51:00 00:05:34 05:39:00 04:22:00 04:58:00 00:25:30
AGGS
6 01:00:00 00:42:00 00:51:00 00:05:34 3:47:00 2:52:00 3:38:00 00:19:15
4 01:00:00 00:42:00 00:51:00 00:05:34 05:02:00 03:34:00 04:23:00 00:23:57
AGGA
6 01:00:00 00:42:00 00:51:00 00:05:34 3:40:00 2:30:00 2:55:00 00:17:36
4 01:15:00 00:42:00 00:52:00 00:08:57 05:20:00 04:00:00 04:40:00 00:24:36
AGNGS
6 01:15:00 00:42:00 00:52:00 00:08:57 3:55:00 2:40:00 3:18:00 00:18:45
4 01:15:00 00:42:00 00:52:00 00:08:57 04:35:00 03:30:00 04:05:00 00:22:19
AGNGA
6 01:15:00 00:42:00 00:52:00 00:08:57 03:00:00 02:10:00 02:40:00 00:15:49
Tabela 5.4 – Tempo de avaliação dos indivíduos e das populações.
Observando os tempos acima, nota-se que o algoritmo não geracional assíncrono
teve um tempo de cálculo bem menor que os anteriores. Vale ressaltar que no tempo de
avaliação das populações está embutido o tempo de ociosidade das máquinas.
Existem duas medidas de desempenho que serão mostradas a seguir. São elas: o
throughput computacional
e a eficiência.
Throughput computacional
é a quantidade de
dados processados em um determinado intervalo de tempo, ou seja, é a quantidade de
indivíduos avaliados pelo algoritmo por unidade de tempo (
THROUGHPUT, 2008
).
A Tabela 5.5 mostra essas medidas de desempenho.
69
Máquinas
escravas
Throughput computacional
(ind/hora)
4
4,32
AGGS
6
6,73
4
5,47
AGGA
6
8,19
4
4,82
AGNGS
6
6,75
4
6,90
AGNGA
6
9,25
Tabela 5.5 – Medidas de desempenho.
Novamente, como era de se esperar, o algoritmo não geracional assíncrono,
AGNGA, apresentou o melhor resultado.
5.3.2 Erro e Aptidão
Nesta seção serão apresentados os resultados numéricos obtidos pelos
algoritmos. O primeiro resultado apresentado é a aptidão encontrada. Cada execução
dos algoritmos genéticos foi inicializada com uma população inicial aleatória. A Tabela
5.6 ilustra o melhor resultado obtido pelos algoritmos depois de 1200 avaliações.
Máquinas
escravas
Par Aptidão RRMS
4 (0.314961,1.574803) 2,579205
89,75%
AGGS
6 (0.099526,3.714286) 1,547914
19,22%
4 0.102606,4.317460 3,54013
30,51%
AGGA
6 (0.099526,2.507937) 1,749118
19,60%
4 (0.099526,2.809524) 0,954099
6,78%
AGNGS
6 (0.096626,3.412698) 1,167019
12,09%
4 (0.102606, 3.714286) 1,009322
19,22%
AGNGA
6 (0.102606, 3,412698) 0,909322
12,09%
Média
(0,12761, 3,18296) 1,682016125
5,81%
Desvio Padrão
(0,07571, 0,85678) 0,935389916
249,19%
Tabela 5.6 – Pares solução encontrados pelos algoritmos e suas aptidões.
Os melhores resultados obtidos foram encontrados pelos AGNGS com quatro
máquinas e pelo AGNGA com seis máquinas. Vale ressaltar que o par esperado era
(0.1, 3.0). Entretanto na representação adotada no trabalho esse valor não pode ser
70
reproduzido. Os valores mais próximos possíveis de 0,1 são 0,099526 e 0,102606 e para
3.0 os mais próximos são 2,809524 e 3,111111.
Na Figura 5.9 mostra-se a evolução da aptidão dos algoritmos AGNGA e
AGGA.
Evolução da Aptidão
0,00
20,00
40,00
60,00
80,00
100,00
0 200 400 600 800 1000 1200
nº de avaliações
A p t id ã o
AGGA AGNGA
v
Figura 5.9 - Evolução da aptidão durante as populações.
Pelo gráfico acima percebe-se que o algoritmo não geracional apresenta uma
convergência mais rápida que o algoritmo geracional, fato também comprovado pelos
artigos de VAVAK (1996) e ROGER (1999).
A seguir será apresentado o ECG da melhor solução encontrada na primeira
população e o ECG da melhor solução encontrada pelo algoritmo. A Figura 5.10 mostra
o ECG do melhor resultado da população inicial (0.051555, 16.380952), da melhor
solução encontrada ao final do algoritmo (0.102606, 3,412698) e o ECG objetivo (0.1,
3.0).
71
Figura 5.10– Comparativo entre os ECG (0.1, 3.0), (0.051555, 16.380952) e (0.1026,
3.4126).
Pode-se observar que o ECG do resultado obtido é similar ao ECG objetivo.
Outra medida importante é o cálculo do erro médio da estimativa do par (α,β).
Para o cálculo desse erro, RRMS, foi empregada a fórmula (5.2):
(5.2)
Onde (α0, β0) é o par objetivo (neste problema estes valores são conhecidos,
visto que os ECG’s objetivos foram também simulados); e o par (α,β) é o estimado. O
par objetivo utilizado na simulação é (0.1, 3.0). A Tabela 5.7 ilustra a evolução do
algoritmo. Cada linha indica uma solução encontrada pelo algoritmo em uma
determinada geração, ou iteração.
72
População Par Aptidão Erro (RRMS)
1 (0,051555, 16,380952) 70,28 81,69%
5 (0,088858, 6,428571) 10,52 53,33%
13 (0,096626, 10,952381) 8,41 72,61%
21 (0,102606, 4,31746) 5,45 30,51%
35 (0,102606, 3,714286) 1,00 19,22%
40 (0,102606, 3,412698) 0,90 12,13%
Tabela 5.7 – Par solução encontrada pelo algoritmo.
Pela tabela acima é possível observar que o fato da aptidão estar baixando não
implica na diminuição do erro. Isto se deve a não-linearidade do problema e da função
de avaliação, como apresenta a figura 5.3. Da mesma forma, o AGNGS encontrou o
resultado (0.099526,2.809524), com aptidão maior do que o encontrado pelo AGNGA.
Porem o erro RRMS dessa solução foi menor, 6,78% contra 12,13% do AGNGS.
5.4 Aplicação de Ruído à base de dados
Neste trabalho foi adicionado ruído à base de dados de estudo, ou seja, às
medidas de ECG. Isto é feito para estudar o desempenho e o comportamento do
algoritmo com relação a ruídos na base. Ruído pode ser definido como sinais aleatórios
que, adicionados à base de dados, podem alterar seu conteúdo.
Foram realizados dois experimentos. O primeiro aplicou um ruído branco.
Nosso ruído branco é um sinal cuja amplitude máxima é de 0,5 mv, ou seja, em torno de
5% da amplitude máxima da onda R.
Já no segundo experimento, foi aplicado um ruído impulsivo em alguns pontos
do ECG. Esses pontos são conhecidos como outlier. Nesse experimento foi aplicado um
ruído mais significativo, com maior amplitude. O ruído impulsivo ou transiente pode ser
definido como qualquer surto de energia que exceda a normalidade dos dados
existentes. A sua principal característica é que não é previsível, variando
consideravelmente em amplitude, freqüência e periodicidade de ocorrência.
A Figura 5.11 mostra o ECG após a aplicação do ruído no primeiro experimento.
73
Figura 5.11 – ECG com Ruído Branco.
A Figura 5.12 mostra o ECG após a aplicação do ruído no segundo experimento.
74
Figura 5.12 – ECG com Ruído Impulsivo.
5.4.1 Ruído Branco
O AGNGA foi utilizado para encontrar um ECG que se aproxime do ECG
objetivo com ruído branco, Figura 5.11. O resultado obtido foi de (0.102606, 5.222222),
erro de 42,54%, lembrando que a base de dados original para o ECG foi de (0.1, 3.0). A
Figura 5.13 mostra o ECG encontrado em relação ao ECG objetivo.
75
Figura 5.13 – ECG encontrado na base de dados com ruído branco.
Observa-se que o ECG encontrado segue bem as características do ECG
objetivo. Com relação à aptidão houve um aumento em seu valor, o que era de se
esperar devido ao fato dos pontos estarem mais distantes. Na simulação sem o ruído,
cujo resultado encontrado foi de (0.102606, 3.412698), a aptidão obtida foi de 0,90, já
na simulação com ruído a aptidão foi de 15,25. A tabela 5.8 mostra os resultados
obtidos.
Sem Ruído Com Ruído
Aptidão
0,90
15,25
Erro
12,13% 42,54%
Par
(0.102606, 3.412698) (0.102606, 5.222222)
Tabela 5.8 – Tabela comparando o resultado obtido sem e com ruído.
76
5.4.2 Ruído Impulsivo
O mesmo algoritmo AGNGA foi utilizado para encontrar um ECG que se
aproxime do ECG objetivo com ruído impulsivo, Figura 5.12. O resultado obtido foi de
(0.102606, 3.412698), o mesmo resultado obtido na simulação sem ruído. A Figura 5.14
mostra o ECG encontrado em relação ao ECG objetivo.
Figura 5.14 – ECG encontrado na base de dados com ruído impulsivo.
Os ruídos impulsivos utilizados na base de dados não foram suficientes para
alterar os parâmetros encontrados pela simulação. Na simulação com ruído a aptidão foi
de 9,45. A tabela 5.9 mostra os resultados obtidos.
Sem Ruído Com Ruído
Aptidão
0,90
9,45
Erro
12,13% 12,13%
Par
(0.102606, 3.412698) (0.102606, 3.412698)
Tabela 5.9 – Tabela comparando o resultado obtido sem e com ruído impulsivo.
77
5.5 Aplicações, infarto e isquemia.
Nesta Seção do trabalho será utilizado o AGNGA para simular a identificação
das condutividades intracelular e extracelular, em cenários que reproduzem algumas
características de patologias cardíacas conhecidas.
Há fortes evidências que os valores e a distribuição da condutividade cardíaca
mudam sob muitas circunstâncias patológicas. Foram encontradas junções gap
danificadas em pacientes com dilatação cardíaca, isquemia cardíaca e miocardites
(inflamação cardíaca) (KOSTIN, RIEGER et all, 2003). A junção gap influência
fortemente na condutividade intracelular e foi observada uma diminuição significativa
de 55% para dilatação cardíaca, 48% para isquemia cardíaca, e de 40% para miocardites
em comparação ao miocárdio humano normal. Em HOPENFELD (2004) a propriedade
passiva da condutividade das regiões afetadas pela isquemia aguda foi estudada.
Verificou-se uma redução na condutividade extracelular. Entretanto, ao contrário da
fase de isquemia aguda, durante o estágio crônico do infarto, a condutividade
extracelular aumenta em conseqüência de necrose e da perda do miocárdio.
Dois casos diferentes foram simulados com parâmetros diferentes. O primeiro
imita a situação da isquemia aguda, (0.1, 0.65), tomadas das observações relatadas por
HOPENFELD (2004) que conduz a uma diminuição da condutividade intracelular, e a
redução do volume extracelular devido ao inchamento do miocárdio, que conduz à
diminuição da condutividade extracelular. A segunda simulação reproduz uma região
com infarto crônico, (0.1, 3.0), isto é, caracterizado com a redução do espaço
intracelular e da condutividade devido à perda do miocárdio, e o aumento
correspondente do espaço e da condutividade extracelular, conforme relatado
previamente por FALLERT M, MIROTZNIK, (1993).
A Figura 5.15 ilustra o ECG das simulações propostas.
78
Figura 5. 15 - Comparativo entre ECG normal, com isquemia e com infarto.
Percebe-se que as doenças causam uma redução da amplitude da onda T e a
onda R tem sua forma alterada, bem como sua amplitude também é diminuída.
A execução do AGNGA para os parâmetros (0.1, 0.65), que imita mudanças da
condutividade sob a isquemia aguda, conseguiu estimar os valores de (0.102600,
0.525000). Assim, o erro RRMS da simulação foi de 23,37%. A execução durou
130:40:00, aproximadamente cinco dias. A execução foi realizada em sete máquinas,
sendo uma mestre e as outras escravas. O algoritmo teve fim após o computo de 1200
avaliações.
A Figura 5.16 mostra os EGC objetivo e o alcançado pela simulação.
79
Figura 5.16 – ECG com isquemia e obtido pela simulação.
A Figura 5.17 mostra a evolução da aptidão ao longo das avaliações. Pode-se
notar que o comportamento do algoritmo foi o mesmo ocorrido em outras simulações,
ou seja, um rápido avanço nos passos iniciais e depois, uma melhora gradual e lenta da
solução.
Evolução da Aptidão
0,00
10,00
20,00
30,00
40,00
50,00
60,00
70,00
80,00
90,00
100,00
0 200 400 600 800 1000
1200
nº de avaliações
Aptidão
AGGA
Figura 5.17 – Evolução do resultado da aptidão.
A segunda execução do AGNGA com os parâmetros (0.1, 3.00), que imita
mudanças da condutividade sob o infarto agudo, conseguiu estimar os valores de
(0.102600, 3.412698). Assim, o erro RRMS da execução foi de 12,13%.
A Figura 5.18 mostra os EGC objetivo e o alcançado pela simulação.
80
Figura 5.18 - ECG com infarto e obtido pela simulação.
A Figura 5.19 mostra a evolução da aptidão ao longo das avaliações.
Evolução da Aptidão
0,00
10,00
20,00
30,00
40,00
50,00
60,00
70,00
80,00
90,00
100,00
0 200 400 600 800 1000
nº de avaliações
Aptidão
AGGA
Figura 5.19 - Evolução do resultado da aptidão.
Os resultados mostram que o método proposto é eficiente para descoberta de
patologias cardíacas. Mas esse é um estudo inicial e precisaria de mais teste,
principalmente com dados reais.
Por último, empregou-se o AGNGA para simular as condutividades de um
tecido normal, sem anomalias. O resultado esperado seria (1.0, 1.0). Após a simulação,
o algoritmo conseguiu alcançar o valor de (1.0, 1.301587), erro de 18,37%. A Figura
5.20 mostra o EGC normal e o alcançado pela simulação.
81
Figura 5.20 - ECG normal e obtido pela simulação.
Percebe-se que apesar de haver uma pequena diferença do coeficiente
extracelular o ECG gerado é idêntico ao ECG normal.
A Figura 5.21 mostra a evolução da aptidão ao longo das avaliações.
Evolução da Aptidão
0,00
20,00
40,00
60,00
80,00
100,00
120,00
140,00
160,00
180,00
0 100 200 300 400 500 600 700 800 900 1000
nº de avaliações
Aptidão
AGNGA
Figura 5.21 - Evolução do resultado da aptidão.
Percebe-se que o valor 1.0 é representável dentro da codificação utilizada no
trabalho, por isso o resultado da aptidão foi bem menor que nas simulações anteriores.
A aptidão obtida foi de 4,58 e foram necessárias apenas 900 avaliações para encontrar
82
este resultado. A tabela 5.10 mostra os resultados obtidos nas simulações de
cardiopatias.
Normal Infarto
Isquemia
Aptidão
4,58 9,45 3,65
Erro
18,37% 12,13% 23,37 %
Par Solução
(1.0,1.0) (0.1, 3.0) (0.1,0.65)
Par Encontrado
(1.0, 1.301587) (0.102, 3.41)
(0.102, 0.525)
Tabela 5.10 – Tabela comparando os resultados obtidos das doenças cardíacas.
83
CAPÍTULO 6
DISCUSSÃO
Neste Capítulo serão discutidos alguns aspectos relevantes com relação ao
trabalho e os resultados apresentados. Algumas das discussões não são conclusivas, mas
servem de orientação para futuros trabalhos.
Na Seção 6.1 serão apresentadas as considerações a respeito dos algoritmos
assíncronos e síncronos, levando-se em conta os prós e contras dos algoritmos aqui
utilizados. Na Seção 6.2 será feito um estudo das vantagens e desvantagens da
abordagem geracional e não geracional para algoritmos genéticos. Na Seção 6.3 será
feita a discussão sobre os testes de tolerância a ruído. A seção 6.4 apresenta uma
discussão a respeito da sensibilidade dos parâmetros. A Seção 6.5 apresenta algumas
limitações deste trabalho. A Seção 6.6 mostra trabalhos relacionados ao assunto tratado.
A Seção 6.7 apresenta uma breve discussão sobre trabalhos futuros.
Por ultimo na Seção 6.8 serão apresentados os artigos gerados a partir deste
trabalho.
84
6.1 Assíncrono x Síncrono
Neste trabalho foram implementados quatros tipos de algoritmo, dois síncronos
e dois assíncronos. Pelo tempo de execução e tempo ocioso das máquinas, os algoritmos
assíncronos levaram uma vantagem em relação aos síncronos. Isto se deve basicamente
ao tempo ocioso presente em excesso nos algoritmos síncronos. TONGCHIM (2000)
também realizou um estudo comparativo entre dois algoritmos, um síncrono e outro
assíncrono para programação genética. O algoritmo assíncrono apresentou melhor
resultado. O artigo deixa claro que o tempo de comunicação não é alterado, mas o maior
ganho de tempo está no tempo de espera do processador que é menor nos algoritmos
assíncronos.
Em nossos experimentos, os algoritmos assíncronos foram em média 15% mais
rápidos que os síncronos. A Figura 6.1 ilustra os tempos obtidos pelos algoritmos.
0
200000
400000
600000
800000
1000000
1200000
1400000
4 (AGGS) 6 (AGGS) 4 (AGGA) 6 (AGGA) 4 (AGNGS) 6 (AGNGS) 4 (AGNGA) 6 (AGNGA)
Algoritmos
Tempo(s)
Tempo Ocioso Tempo Gasto
Figura 6.1 - Gráfico do tempo total em relação ao tempo ocioso do algoritmo.
Como é possível perceber pelo gráfico acima, o tempo ocioso dos algoritmos
assíncronos foram menores que dos síncronos.
85
6.2 Geracional x não Geracional
Outro aspecto importante abordado neste trabalho foi o estudo de dois modelos
de algoritmos genéticos que diferem pela forma com que os indivíduos evoluem. Esses
dois métodos são conhecidos como geracional e não geracional, ou
steady state
.
Uma das maiores vantagens da implementação não geracional se deve ao fato da
população sempre estar com os melhores indivíduos, e esses estarem sempre gerando
novos filhos. Entendemos que este fato é o responsável por provocar uma convergência
mais rápida à solução desejada.
FRANK VAVAK, et al (1996) realizaram uma comparação entre os dois
modelos em um ambiente dinâmico. Os resultados apresentados pelo autor corroboram
com os resultados apresentados neste trabalho. Ou seja, o algoritmo não geracional
apresentou uma convergência mais rápida que o geracional.
BORGES e BARBOSA (2003) apresentam um estudo comparativo entre um
algoritmo não geracional assíncrono e um algoritmo geracional serial. O bom
desempenho do algoritmo não geracional em relação ao outro, encorajou os autores a
aplicá-lo em problemas de engenharia.
86
6.3 Tolerância a Ruído
Uma questão importante está relacionado à qualidade e fidelidade dos dados
medidos, isto é, dos ECG’s. Esses dados, como qualquer outro tipo de informação,
podem estar sujeitos a interferências, como por exemplo, um defeito no aparelho de
medição do ECG.
Nas execuções realizadas neste trabalho, colocou-se em teste a robustez da
técnica com dois tipos de ruído: branco e impulsivo.
Nesse sentido os resultados obtidos com o ruído branco indicam que o AGNGA
apresentou um erro de 42,54%, enquanto que o sem ruído e erro foi de apenas 12,13%.
Apesar de ter havido aumento do erro RRMS e do valor da aptidão, os gráficos dos
ECG’s ficaram bem parecidos, como mostra a Figura 7.13.
Com relação ao ruído impulsivo, o algoritmo conseguiu chegar ao mesmo
resultado obtido sem a aplicação do ruído.
Outro tipo de ruído que poderia ter sido investigado é o relacionado ao
posicionamento dos eletrodos. Nos experimentos realizados neste trabalho, os eletrodos
estavam sempre na mesma posição. Mas uma pequena variação nestes eletrodos poderia
adicionar ruído à medida do ECG.
87
6.4 Sensibilidade dos parâmetros
Conforme mostra o desvio padrão, calculado na Seção 5.3, os resultados
alcançados pelos algoritmos corroboram com a análise de sensibilidade apresentada
neste trabalho. Ou seja, o segundo parâmetro, a condutividade extracelular, tem menor
influência na função objetivo do que o primeiro parâmetro. Este fato também ficou
comprovado na adição de ruído à base de dados. O segundo parâmetro foi o mais difícil
de ser ajustado, provocando assim um resultado mais distante do esperado.
Através da análise de sensibilidade realizada, pode-se verificar que a mudança
no segundo parâmetro tem menor impacto nos valores da função de aptidão do que o
primeiro parâmetro.
88
6.5 Limitações
O algoritmo genético é essencialmente um método estocástico, o que leva a
necessidade de varias execuções para uma melhor avaliação a respeito de seus
resultados. Por outro lado temos a nossa função de aptidão, que é uma função muito
custosa. Para se ter uma idéia, somente com as execuções dos quatro algoritmos em sete
e cinco máquinas, foram gasto quase três meses, fora os testes antes da execução e sem
contar com as execuções para validar as taxas de mutação e
crossover
. Levando está
situação em consideração, não foi possível realizar um maior número execuções a fim
de melhor achar o desempenho dos métodos.
A avaliação do desempenho destas implementações paralelas é outro ponto que
poderia ter sido melhor explorado neste trabalho. Conforme dito anteriormente, a
população inicial não estava fixa, pois optamos por verificar minimamente a
sensibilidade dos algoritmos em relação a população inicial escolhida. Dessa forma, as
diferenças de tempo entre quatro e seis máquinas escravas não é puramente devido a
implementação paralela, visto que a população inicial de indivíduos é distinta. Isso
certamente é um fator limitante com relação à avaliação de desempenho em paralelo dos
métodos geracionais, visto que o computacional desses métodos é exatamente o mesmo,
independente do número de máquinas usadas. Entretanto, acreditamos que este fato é
menos relevante com relação aos métodos não geracionais, pois estes mesmo com
população inicial idêntica possuem um comportamento que varia com o número de
máquinas usadas.
Outro ponto importante que devemos ressaltar é com relação ao problema
inverso escolhido. Trata-se de um problema essencialmente acadêmico com apenas dois
parâmetros a serem estimados. A função objetivo da Figura 5.3 sugere que algoritmos
baseados em derivadas provavelmente seriam mais eficientes, visto que não há mínimos
locais. Entretanto, como mostra a Seção 6.6, para problemas mais complexos em áreas
correlatas, a adoção de algoritmos genéticos foi de fundamental importância para a
solução do problema. Dessa forma, justificamos a adoção de AG neste trabalho, pois
entendemos que este é um primeiro passo importante em direção a resolução de
89
problemas mais complexos e de mais interesse médico cientifico, que também
envolvem a resolução das equações do Bidomínio para a modelagem do coração.
90
6.6 Trabalhos Relacionados
Esta Seção tem por objetivo apresentar dois trabalhos relacionados ao tema
apresentado.
6.6.1 The Use of Genetic Algorithms for Solving the Inverse Problem of
Electrocardiography
Neste artigo os autores, MINGFENG E GUOFA (2006), investigam a
reconstrução do potencial epicardial a partir do potencial do corpo humano.
Neste artigo foi investigado o uso dos algoritmos genéticos para a resolução
deste problema. O resultado mostra que o algoritmo genético, necessita de
condicionamentos adicionais. Combinado com outros métodos ou com informações
adicionais, o algoritmo é uma técnica eficiente para resolver o problema inverso
proposto. No artigo, o algoritmo híbrido é composto por um AG e uma regularização de
Tikhonov. Este artigo sugere que o algoritmo proposto pode fornecer uma ferramenta
útil para estudos em problemas inversos que envolvam ECGs.
6.6.2 Application of genetic algorithms to cure heartbeat pathologies
Os autores deste artigo, DUMAS E ALAOUI (2007), mostram como os
algoritmos genéticos podem melhorar a cura de patologias do batimento cardíaco
otimizando a posição dos elétrodos de um marca passo. Uma primeira simulação em um
coração simplificado mostra como a posição dos eletrodos de marca passo afeta as
propriedades elétricas do coração.
No artigo, um exemplo simples é apresentado e mostra como a otimização pode
fornecer a colocação ideal dos eletrodos.
91
6.7 Trabalhos Futuros
6.7.1 Codificação
Neste trabalho foi utilizada uma representação binária. Nesta representação, a
condutividade pode aumentar ou diminuir x vezes, com x entre 1 e 20. Como é possível
perceber esta representação foi utilizada para diminuir o espaço de busca devido aos
longos tempos de execução. Além disso, ela representa o mesmo número de
possibilidades para o aumento ou redução das condutividades.
Outras formas de representação poderiam ser testadas nesse trabalho como a
codificação gray, e até mesmo a própria codificação real ou ponto flutuante.
A Codificação Gray utiliza dois números inteiros consecutivos que diferem entre
si por um único bit. A Figura abaixo 6.2 mostra a codificação para os primeiros 16
números naturais:
Figura 6.2 – Codificação Gray.
92
SHAFFER e CARUANA (1989) fizeram diversos testes e concluíram que o
código de Gray é superior ao código binário padrão em aplicações utilizando AG.
Talvez pelo fato de o código de Gray possuir a propriedade de dois números inteiros
adjacentes terem distância Hamming de uma unidade (diferença de um bit), este código
tem obtido melhor desempenho do que o código binário padrão.
A codificação ponto flutuante, também seria uma boa representação para este
problema. Segundo JONIKOW e MICHALEWICZ (1991), a codificação real em
determinadas situações apresentou um resultado melhor que a representação binária
padrão.
Outro experimento que poderia ser realizado seria com relação ao critério de
seleção dos indivíduos, já que o utilizado neste trabalho foi a roleta, o qual não tem uma
boa aceitação em problemas de minimização. Outras formas de seleção como o torneio
ou rank poderiam ser utilizadas.
6.7.2 MetaModel, Aproximação da função de Aptidão
A computação evolucionista tem encontrado aplicação em várias áreas da
ciência e da engenharia. Os algoritmos evolucionários estão sendo aplicados cada vez
mais a problemas de otimização. Apesar dos grandes sucessos conseguidos em
aplicações do mundo real, os algoritmos evolucionários encontraram também muitos
desafios. Para a maioria de algoritmos evolucionista é necessário realizar um grande
número avaliações de aptidão antes que uma solução aceitável possa ser encontrada. Há
diversas situações em que a avaliação da aptidão se torna difícil e computacionalmente
custosa.
Enquanto uma simulação computacional pode ser vista como o verdadeiro valor
de aptidão de uma determinada solução, aproximações dessa também podem ser usadas
para o cálculo de aptidão (
meta-models
). Assim, o
meta-model
usa soluções
previamente avaliadas no espaço de busca para predizer a aptidão de novos indivíduos.
Vários modelos são propostos para a aproximação da aptidão. Os mais populares
são as funções polinomiais, o modelo de Kriging, as redes neurais, inclusive perceptrons
de multi-camada, redes baesianas e as máquinas de vetor suporte.
93
Vale ressaltar que os meta-models devem ser usados junto com a função de
aptidão original. Na maioria dos casos, a função de aptidão original está disponível,
embora seja computacionalmente custosa.
Há vários artigos propostos nessa área, como os trabalhos de MARTIKAINEN E
OVASKA (2006), que utilizam uma rede neural para acelerar o cálculo da aptidão. Os
autores chegaram à conclusão de que está metodologia, adiciona erros de aproximação.
Entretanto, estes são suficientemente pequenos. Deste modo, o algoritmo genético pode
tirar proveito da criação de gerações adicionais devido ao tempo economizado nos
cálculos da função de aptidão.
Acreditamos que está técnica pode melhorar o desempenho computacional de
nossos métodos, visto que nossa função de aptidão é extremamente custosa.
6.7.3 Experimentos mais realistas
O objetivo esperado deste trabalho era encontrar a condutividade extracelular e
intracelular de um tecido cardíaco patológico. Nesse aspecto o algoritmo se comportou
de forma satisfatória. Porém, tivemos que adotar algumas hipóteses simplificadoras
como, por exemplo, supor que a localização da região afetada era conhecida. Em
situações reais, a região afetada também deveria ser mais um dos parâmetros do
problema inverso. Outra hipótese simplificadora, diz respeito à modelagem do infarto e
isquemia. Sabe-se que nessas patologias dezenas de parâmetros fisiológicos são
alterados. Por exemplo, as condutividades máximas e a cinética de diversos canais
iônicos sofrem alterações durante essas patologias. A principio, nossos modelos
computacionais são suficientemente complexos e permitiriam a reprodução desses
fenômenos. Porém, por se tratar de um trabalho acadêmico e devido ao custo
computacional de nossas execuções, nos restringimos a estimativa de apenas dois
parâmetros, as condutividades do tecido.
Portanto como trabalho futuro ficaria a possibilidade de incluir novos
parâmetros e verificar a eficiência do algoritmo genético para estimá-los.
Neste trabalho adotamos um simulador bidimensional para tecidos cardíacos
devido ao custo computacional proibitivo dos simuladores tridimensionais existentes
para todo o coração. Porém, a medida que os métodos numéricos e as técnicas de
programação paralela avançam, acreditamos que simulações tridimensionais de órgãos
94
inteiros poderão ser utilizadas em problemas inversos e validadas com dados clínicos
reais.
95
6.8 Artigos Publicados
Três artigos foram publicados durante esta dissertação. Os artigos na integra
estão em anexo.
6.8.1 Estimating Conductivity Distribution of Transmural Wedges of the
Ventricle Using Parallel Genetic Algorithms
Este artigo foi apresentado no CINC, Computers in Cardiology 2006, em
Valencia na Espanha.
Neste artigo é usada a técnica de
wedge
para simular computacional o ventrículo
esquerdo humano. Foram simuladas as condutividades extracelulares e intracelulares
anormais que imitam algumas circunstâncias patológicas conhecidas. Foi proposto um
método baseado em algoritmos genético para estimar as condutividades extracelulares e
intracelulares, comparando as simulações cardíacas com alguns ECG’s conhecidos.
6.8.2 Comparing Two Parallel Genetic Algorithms for the Inverse Problem
Associated to the Cardiac Bidomain Equations
Este artigo foi apresentado no High Performance Computing in the Life
Sciences, 2006, Ouro Preto, Brasil, um evento organizado pela SBC, Sociedade
Brasileira de Computação.
Neste artigo usamos a simulação cardíaca para simular regiões com
condutividade intracelular e extracelular anormais. Foram executados e comparados
dois algoritmos genéticos que estimam a distribuição das condutividades. Os métodos
foram desenvolvidos para sistemas distribuídos e os resultados foram obtidos em um
conjunto composto de oito computadores interconectados. O primeiro método baseado
no modelo
steady-state
, não geracional, onde conseguimos resultados melhores do
speedup
do que o algoritmo genético geracional tradicional.
96
6.8.3 A computational framework for cardiac modeling based on
distributed computing and web applications
Este artigo foi apresentado no VECPAR, Seventh International Meeting on High
Performance Computing for computational science, 2006, Rio de Janeiro, Brasil.
Simulações cardíacas estão sendo usadas em uma variedade de testes que
apóiam a pesquisa de novas drogas, o desenvolvimento de novos dispositivos médicos e
o diagnóstico não invasivo. Modelos computacionais se tornaram valiosas ferramentas
para o estudo e a compreensão destes fenômenos complexos da eletrofisiologia
cardíaca. Porém, a complexidade destes modelos cardíacos ainda restringe seu uso a
alguns centros de pesquisa especializados no mundo. Nesse artigo foi proposto um
framework computational que provê apoio para a modelagem da eletrofisiologia
cardíaca. Este framework integra diversas ferramentas computacionais e permite o uso e
o desenvolvimento de modelos cardíacos. A implementação dos modelos celulares é
feita através do CellML que é executado em um simulador cardíaco paralelo de 2-
dimensional. Todas estas ferramentas estão sendo integradas em um portal de Web que
é conectado a um cluster de computadores. O portal permite que se desenvolva e simule
modelos cardíacos eficientemente através deste ambiente integrado e de fácil uso. Em
conseqüência, todas as técnicas complexas e o know-how atrás de modelagem cardíaca
são gerenciados por uma aplicação web distribuída.
97
CAPÍTULO 7
CONCLUSÃO
Este trabalho teve como objetivo estudar métodos para a estimativa de
parâmetros das equações do bidomínio, que apresentam soluções complexas e
computacionalmente custosas. Para resolver este problema inverso, foram utilizadas
técnicas de algoritmos genéticos, que empregam uma analogia direta com a evolução na
natureza, na qual cada indivíduo representa uma possível solução para um problema
dado.
Devido à complexidade do problema estudado, foram feitas implementações
distribuídas destes algoritmos. Foi utilizada a arquitetura mestre-escravo, na qual
diversos processadores escravos são responsáveis pela execução da função de avaliação
e um processador mestre é responsável pelas demais operações genéticas.
Foram implementadas duas abordagens de algoritmos genéticos: a geracional
clássica, em que a cada geração todos os indivíduos são avaliados, e a abordagem
steady-state
modificada, na qual apenas uma parte da população é avaliada a cada
geração. Além dessas abordagens, avaliamos duas formas de comunicação entre
processos. Na primeira forma, síncrona, somente há envio de indivíduos quando todas
as máquinas escravas estão disponíveis. Na segunda forma, assíncrona, um indivíduo é
enviado assim que uma máquina escrava estiver disponível.
As implementações têm como objetivo, estimar a distribuição intra e extracelular
de condutividade elétrica, possibilitando assim uma base para o diagnóstico de doenças
do coração. Neste trabalho, foram feitas simulações para situações de infarto crônico e
isquemia aguda.
Para a simulação do caso de isquemia aguda, o algoritmo genético estimou
parâmetros com erro RRMS de 23,37%. Para a situação de infarto crônico, a
condutividade foi estimada com erro RRMS de 12,13% já com a simulação do tecido
normal o erro encontrado foi de 18,37%. O método proposto foi capaz de classificar
qualitativamente se os ECG’s eram provenientes de tecidos normais, isquêmicos ou
infartados.
98
Os algoritmos assíncronos foram mais rápidos que os síncronos. Isto se deve ao
menor tempo ocioso das máquinas escravas. Percebe-se que os algoritmos assíncronos
não melhoram a convergência, visto que os algoritmos síncronos obtiveram bons
resultados.
Outra conclusão que podemos chegar com relação aos algoritmos
implementados diz respeito aos algoritmos não geracionais. Estes obtiveram os
melhores resultados e, além disso, conseguiram uma convergência mais rápida até a
solução do problema.
Os resultados em um pequeno cluster de sete computadores sugerem um método
promissor. Porem, ainda é necessário continuar com a pesquisa, o desenvolvimento e a
validação desta metodologia para viabilizá-la como solução para problemas inversos de
maior interesse médico-científico.
99
REFERÊNCIAS BIBLIOGRÁFICAS
ABRAMSON, J. GIDDY AND KOTLER, L. , 2000,
High Performance Parametric
Modeling with Nimrod/G: Killer Application for the Global Grid
, in IPDPS 2000,
pp. 520-528, Cancun Mexico, IEEE CS Press, USA.
BEELER G, REUTER H., 1977, “Reconstruction of the action potential of ventricular
myocardial fibers”. In J Physiol. v 268, pp 177–210.
BERKENBROCK, G. R.; ROJAS, M. A. T., 2004, “Projeto de Caixa-S Utilizando
Algoritmo Genético Paralelo”. Im
I WorkComp
Sul, Florianópolis. Anais do I
WorkComp Sul.
BORGES, C.C.H. & BARBOSA, H.J.C., 2003, “On the behavior of a parallel non-
generational genetic algorithm”. In
XXIV CILAMCE, 24th Iberian Latin-American
Congress on Computational Methods in Engineering
(CD-ROM), October 2003,
UFOP, Ouro Preto, MG, Brasil.
BÄCK, T., 1996, “Evolutionary algorithms in theory and practice”. Oxford University
Press,
CANTÚ-PAZ, E. A., 1997,
survey of parallel genetic algorithms
, Technical
report,Computer Science Department and Illinois Genetic Algorithms Laboratory
- University of Illinois at Urbana-Champaign.
CAMPOS, F., 2005,
Um estudo sobre a modelagem eletrofiologica cardíaca
.
Monografia de graduação, UFJF, juiz de fora, MG, Brasil.
100
CARRERA E. V. AND LOQUES O., 1998, "Integrating Shared Memory, Message
Passing and Configuration". In
Proceedings of the 10th Brazilian Symposium on
Computer Architecture - High Performance Processing
, Brazilian Computer
Society, Búzios - Brazil, pp. 241-244, September.
DUMAS, L. E ALAOUI, L. E, 2007,
APPLICATION OF GENETIC ALGORITHMS TO
CURE HEARTBEAT PATHOLOGIES
, in evolutionary methods for design,
optimization and control. Barcelona, Spain.
EMMERICH, M., GIOTIS, A., OZDEMIR, M. ET AL., 2002. ”Metamodel-assisted
evolution strategies”. J.J. Merelo Guerveros et al. (Eds.): PPSN VII, LNCS 2439,
pp. 361–370, Springer-Verlag Berlin Heidelberg 2002
FITZHUGH, R., 1961, “Impulses and physiological states in theorical models of nerve
membrane”. In Biophys. J. 1961
FALLERT M., MIROTZNIK M., DOWNING S., et al., 1993,. ”Myocardial electrical
impedance mapping of ischemic sheep hearts and healing aneurysms”. In
journal
Circulation,
v 87, n 1, pp 199-207.
GESELOWITZ, D. B. e MILLER W. T., 1983, “A bidomain model for anisotropic
cardiac muscle”. In
Annals of Biomedical Engineering
. v 11, n 3-4 May.
GOLDBERG, D. E., 1989, “Genetic algorithms in search, optimization, and machine
learning”.
Addison Wesley
.
HASH Table, Disponível em: <http://pt.wikipedia.org/wiki/Tabela_hash>. Último
acesso em Janeiro de 2008
101
HENRIQUEZ, A. P., VOGEL, ROLF, et al., 2001, “Influence of Dynamic Gap Junction
Resistance on Impulse Propagation in Ventricular Myocardium: A Computer
Simulation Study”, in
Journal Article
Biophys
. V 81, n 5, pp 2112-2121
HENRIQUEZ, C. S., 1993, “Simulating the electrical behavior of cardiac tissue using
the bidomain model”. In
Crit. Rev. Biomed. Engr,
v 21, pp 1-77.
HODGKIN A., HUXLEY A., 1952, “A quantitative description of membrane current
and its application to conduction and excitation in nerve”. In J Physiol London, v
117, pp 500–544.
HOOKE, N. et al., 1994, “Linear algebraic transformations of the bidomain equations:
implications for numerical methods”. In
Math Biosci
, Duke University, vol. 120,
no. 2.
HOPENFELD B, STINSTRA J, MACLEOD R., 2006, “Mechanism for st depression
associated with contiguous subendocardial ischemia”. In
Journal of
Cardiovascular Electrophysiolog,
v 15, pp1200–1206.
JIN, Y.,2003, “A comprehensive survey of fitness approximation in evolutionary
computation”, in
Soft Comput. J
. , (in press).
JIANG M., XIA L. E SHOU G., 2006, “The Use of Genetic Algorithms for Solving the
Inverse Problem of Electrocardiography”, in
Proceedings of the 28th IEEE EMBS
Annual International Conference
, New York City, USA, Aug 30-Sept 3, 2006
JONIKOW, C.Z. AND MICHALEWICZ, Z. , 1991, “An experimental comparison of
binary and floating point representations in genetic algorithms”, In
International
Conference on Genetic Algorithms
, 31--38.
102
KEENER, J. e SNEYD, J., 1998, “Mathematical physiology”. Springer-Verlag, New
York.
KOSTIN S, RIEGER M, DAMMER S, HEIN S, et al., 2003,
Gap junction remodeling
and altered connexin43 expression in the failing human heart
. In Molecular and
Cellular Biochemistry; v 242: pp 135– 144.
LIMA, B. P., 2005, “Notas de aula: Métodos Computacionais Inspirados na Natureza”,
Disciplina Coppe.
NCBI. GenBank. Disponível em: <http://www.ncbi.nlm.nih.gov/> Acesso em: 6 Fev.
2006.
NANOAGING Institute. Bioinformatics.Org The Open-Access Institute. Disponível
em: <http://bioinformatics.org/> Acesso em: 6 Fev. 2006
MARTIKAINEN, J. AND OVASKA, S. J., 2006, “Fitness Function Approximation by
Neural Networks in the Optimization of MGP-FIR Filters, Adaptive and Learning
Systems”, in IEEE Mountain Workshop on July 2006, pp 7-12
MARTINS, D. M. S., SANTOS, R. W., BARBOSA, C. B., et al., 2006, “A
Computational Framework for Cardiac Modeling Based on Distributed
Computing and Web Applications” In:
Vecpar 2006 Seventh International
Meeting on High Performance Computing for computational science
, Rio de
Janeiro.
MARTINS, D. M. S. ; XAVIER, C. R. ; SANTOS, E. P. et al., 2006, “Estimating
Conductivity Distribution of Transmural Wedges of the Ventricle Using Parallel
103
Genetic Algorithms”. In:
Computers in Cardiology
2006, 2006, Valencia.
Proceedings of IEEE Computers in Cardiology. New York : IEEE, 2006. v. 33.
pp. 577-581.
MESSAGE Passing Interface Forum Disponível em: <http://www.mpi-forum.org>.
Acesso em: 01 jan. 2007.
MICHALEWICZ, Z., 1999, “Genetic Algorithms + Data Structures = Evolution
Programs”, Springer.
MIRANDA, M. N. de., Disponível em: <http://www.gta.ufrj.br/~marcio/genetic.html>.
Último acesso em Novembro de 2007.
MITCHELL M. , 1996,
An Introduction to Genetic Algorithms
. 2 ed, Massachusetts,
MIT Press.
NETO, A. J. S., 2005, “
Problemas Inversos:
Aplicações em Engenharia e Medicina”.
Quartas Científicas Instituto Politécnico,
rio de janeiro, RJ, UERJ, 2005.
RAMOS, F. M., CAMPOS VELHO, H. F., CARVALHO, J. C., et al., 1999, “Novel
approaches on entropic regularization
”
,
Inverse Problems Institute of Physics
Publishing,
v. 15, n. 5, pp. 1139-1148.
ROGERS A. PRÜGEL-BENNETT A., 1999, ”Modelling the Dynamics of a Steady
State Genetic Algorithm.” , in
Foundations of Genetic Algorithms
5 (W. Banzhaf
and C. Reeves, eds.), (San Francisco), pp. 57–68, Morgan Kaufmann,
SANTOS R. W., CAMPOS F. O., CIUFFO L., et al., 2006, “ATX-II Effects on the
Apparent Location of M Cells in a Computational Human Left Ventricular
Wedge”. in
Journal Cardiovasc Electrophysiol
. In press.
104
SANTOS, R. W, 2002,
Modelagem da Eletrofisiologia Cardíaca
. Tese M.Sc,
COPPE/UFRJ, Rio de Janeiro, RJ, Brasil.
SANTOS, R. W. et al., 2004, “Preconditioning techniques for the bidomain equations”.
Lecture Notes in
Computational Science and Engineering
. 2004
SILVA, A. J. M., 2005, Implementação
de um Algoritmo Genético Utilizando o Modelo
de Ilhas
, Tese M.Sc, COPPE/UFRJ, Rio de Janeiro, RJ, Brasil.
SHAFFER, J. D.; CARUANA, R. A.; ESHELMAN L. J.; DAS, R., 1989, “A study of
Control Parameters Affectng Online Performance of Genetic Algorithms for
Functions Optimization.” California: Morgan Kaufmann Publishers, Inc.,
(Proceedings of the Third International Conference on Genetic Algorithms).
George Mason University, United States pp 51 - 60.
SPEEDUP, Disponível em: <http://pt.wikipedia.org/wiki/Lei_de_Amdahl>. Último
acesso em Janeiro de 2008
STILES, J.R., BARTOL, I.M. AND SALPETER, E.E., AND SALPETER, M.M., 1998,
“Monte Carlo Simulation of Neuromuscular Transmitter Release Using MCell, a
General Simulator of Cellular Physiological Processes”. In
Computational
Neuroscience
, pp 279-284
SUNDNES, J. et al., 2002,
Numerical
Methods and Software for Modeling the
Electrical Activity in the Human Heart
. In Simula Research Laboratory, Lysaker -
Norway.
105
SUNDNES, J. et al. , 2001,
Efficient solution of ordinary differential equations
modeling electrical activity in cardiac cells
. In Mathematical biosciences v 172,
pp 55 – 72
TEN TUSSCHER K. H. W. J., et al., 2004,.
A model for human ventricular tissue
. Am J
Physiol Heart Circ Physiol, v 286, pp 1573-1589.
TENEMBAUM, A. S., 2000,
Sistemas Operacionais Modernos
. Prentice Hall do Brasil,
São Paulo, 3ed.
THROUGHPUT , Disponível em: <http://pt.wikipedia.org/wiki/Throughput>. Último
acesso em Janeiro de 2008
TONGCHIM, S. AND CHONGSTITVATANA, P. 2000. “Comparison between
synchronous and asynchronous implementation of parallel genetic programming”.
In
Proceedings of the 5th International Conference for Artificial Life and
Robotics
, pp 251--254, Japan.
VAVAK, F.AND. FOGARTY, T.C., 1996, “Comparison of steady state and
generational genetic algorithms for use in nonstationary environments”. In
IEEE
International Conference on Evolutionary Computation (ICEC)
, pp 192--195.
XAVIER C. R., VIEIRA V. F., MARTINS, D. M. et al., 2006, “Parallel Genetic
Algorithms For The Solution Of The Bidomain Equations”. in
WSCAD 2006,
Workshop on High Performance Computing in the Life Sciences
. 2006.
XAVIER, C. R. ; VIEIRA, V. F. ; MARTINS, D. M. S. et al., 2006, “Comparing Two
Parallel Genetic Algorithms for the Inverse Problem Associated to the Cardiac
Bidomain Equations”. In:
High Performance Computing in the Life Sciences
,
Ouro Preto. High Perfomance Computing in the Life Sciences. Brasilia :
106
Sociedade Brasileira de Computação. Brasilia : Sociedade Brasileira de
Computação, 2006. v. 1. p. 29-34.
WHITLEY, D., 1989, “The GENITOR algorithm and selective pressure”.
Proceedings
of the 3
rd
Int. Conf on Genetic Algorithms and their Applicatins
, pp 116 – 121.
YAN G, SHIMIZUW, ANTZELEVITCH C., 1998 “Characteristics and distribution of
m cells in arterially perfused canine left ventricular wedge preparations”. in
Circulation Research
; v 98: pp 1921–1927.
107
Anexo A
108
109
110
111
Anexo B
112
113
114
115
116
Anexo C
117
118
119
120
121
122
123
124
125
126
127
128
129
Anexo D
A Ferramenta de Simulação Cardíaca via WEB – PARACARDIO
Impulsionada pelo crescente número de usuários e pela constante evolução das
tecnologias de comunicação e informação, é cada vez maior o número de serviços on-
line oferecidos à sociedade através da World Wide Web. Antigos documentos estáticos
com informações meramente institucionais estão dando espaço para páginas dinâmicas
com o objetivo de fornecer informações direcionadas a cada usuário. Aplicações de e-
commerce, e-learning, e-gov, distribuição de notícias e jogos on-line são apenas alguns
exemplos dos serviços atualmente encontrados na Web.
Seguindo a mesma tendência, sites de laboratórios e centros de pesquisa
começam a disponibilizar serviços que visam promover a cooperação entre
pesquisadores, como o GenBank, o banco de dados de seqüências genéticas do National
Center for Biotechnology Information (NCBI, 2006) e o Collaborative Development
Environment (CDE) do Bioinformatics.Org (NANOAGING, 2006).
Neste contexto, desenvolvemos o Portal Fisiocomp que possui três principais
objetivos.
Em primeiro lugar, divulgar e popularizar as tecnologias utilizadas para a
simulação cardíaca. Através do acesso ao portal, os usuários poderão submeter,
configurar e simular modelos cardíacos de forma eficiente. As técnicas complexas e a
expertise necessária para executar as simulações, tais como computação paralela,
métodos numéricos, técnicas de visualização de imagens e até mesmo implementação
de código fonte, serão realizadas por aplicações web fáceis de usar. Tutoriais on-line
também serão usados para instruir os usuários a fazerem uso das ferramentas de forma
eficiente.
Em segundo lugar, promover o compartilhamento e a democratização dos
recursos computacionais. As aplicações web que serão disponibilizadas no portal
permitirão aos usuários executarem suas simulações no cluster de computadores de
nosso grupo de pesquisa. Dessa forma, o acesso ao poder computacional dos clusters de
130
computadores estará disponibilizado para os centros de pesquisa que não dispõe desta
tecnologia, aumentando a capacidade de processamento dessas instituições;
Em terceiro lugar, promover o desenvolvimento da modelagem cardíaca. A
integração de diversas ferramentas em um único portal irá acelerar o desenvolvimento
de novos modelos eletrofisiológicos do coração, integrando cada vez mais os centros de
pesquisa e estimulando a cooperação internacional.
Um primeiro protótipo do portal já se encontra em operação, podendo ser
acessado a partir da URL http://www.fisiocomp.ufjf.br. Foi proposta e implementada
uma arquitetura que permite a integração entre o Portal Fisiocomp, um Cluster
computacional e o simulador cardíaco.
Um breve esquema da implementação dessa integração é descrita a seguir e
apresentada na Figura D.1.
Figura D.1 - Arquitetura de Integração Entre o Portal Fisiocomp e o Cluster Parafisio
Nesse Contexto, surgiu o PARAFISIO uma aplicação para simulação de tecidos
cardíacos via Web. Trata-se de uma versão on-line do simulador cardíaco, uma interface
web onde são configurados parâmetros para a execução do simulador em questão.
O Simulador cardíaco já está disponível de forma local. A intenção é tornar esta
simulação disponível para usuários externos à instituição.
Com base na aplicação já existente, foi desenvolvida uma interface web para,
além de facilitar a sua utilização, disponibilizá-la para uso da comunidade científica
através de website. O resultado final foi a disponibilização na web de uma ferramenta
131
on-line para configuração e submissão de parâmetros e posterior obtenção, para
download, dos resultados que são conseguidos após sua execução no cluster.
O site foi desenvolvido em java para a web, jsp, servlts. Também foi utilizado
um framewok conhecido como struts. A base de dados utilizada foi o my-sql.
Interfaces
Algumas das telas que compõem a interface do Simulador Cardíaco são as
seguintes:
A primeira tarefa a ser realizar é escolher o tipo de projeto a ser realizado,
PARACARDIO, um projeto de simulação cardíaca, conforme a Figura D.2.
Figura D.2 - Interface para Criação de um projeto de simulação Cardíaca.
Ao escolher um projeto de simulação é pedido um nome ao projeto, conforme
Figura D.3, e é pedido também o número de regiões de tecido cardíaco e o número de
estímulos, conforme Figura D.4.
132
Figura D.3 – Criação do projeto de simulação cardíaca.
Figura D.4 – Parâmetros para criação do projeto de simulação o número de folhas e o número de
estímulos.
Feito isso é criada a estrutura de arquivo conforme ilustra a figura D.5. É criado
um arquivo de configuração *.prj; um arquivo para estimulo pedido, *.stl; e um
diretório para cada região *.reg. Por sua vez cada região gera uma configuração do
Projeto AGOS, onde devemos submeter um xml, e ao executá-lo, são obtidos os
resultados.
133
Figura D.5 – Arquivos criados para a execução da simulação.
Para configurar o projeto basta clicar sobre o arquivo prj, que irá exibir a tela
3.6.
Figura D.6 – Configuração do Projeto.
134
Para configurar os estímulos basta clicar sobre cada arquivo prj, que irá exibir a
tela D.7. Como pode ser visto há duas formas do estímulo, o single pulse ou o train of
pulse.
Figura D.7 – Configuração do estimulo.
Cada região também deve ser configurada, conforme mostra a figura D.8. Cada
região pode ser de seis tipos diferentes, que são elas: Tecido Cardíaco Isotropico,
Condução passiva Isotropico, Tecido Cardíaco Ansotropico, Condução passiva
Ansotropico, Tecido Cardíaco Orthotropico, Condução passiva Orthotropico. Também
deve ser configurado o coeficiente da condutividade intracelular e extracelular. O
modelo celular utilizado na simulação deverá ser enviado.
Figura D.8 – Configuração da região.
135
Após o envio a Figura D.9 exibe a tela de configuração do modelo celular
Figura D.9 – Configuração do Modelo Celular.
Feito isso basta executar a simulação e aguardar os resultados.
Figura D.10 – Execução da simulação.
O sistema envia um email avisando a respeito do fim da simulação.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
