T

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Description

The Use of Genetic Algorithms for Solving the Inverse Problem of Electrocardiography

Tags

Transcript

The Use of Genetic Algorithms for Solving theInverse Problem of Electrocardiography
Mingfeng Jiang
1, 2
, Ling Xia
1
and Guofa Shou
11
Department of Biomedical Engineering, Zhejiang University, Hangzhou 310027, P.R. China
2
The College of Electronics and Informatics, Zhejiang Sci-Tech University, Hangzhou, P.R. China
Abstract—
Reconstruction of the epicardial potentials from thebody surface potentials constitutes one form of the ill-posedinverse problem of electrocardiography (ECG). In this paper, weinvestigate the use of genetic algorithms (GAS) for regularizingill-posed ECG inverse problem. The result shows that, GAScannot be used to regularized ill-posed problem withoutadditional constraints, but combined with other methods oradditional information about solutions, GAS is an efficientoptimization technique for solving the ill-posed inverse problem.We adopt the Tikhonov regularized solutions as the additionalinformation to construct the initial populations. Thisinvestigation suggests that the GAS may provide a useful tool forECG inverse problem studies.
Keywords
—
genetic algorithms, inverse problem, Tikhonovregularization, discrepancy principle
I. I
NTRODUCTION
The inverse problem of electrocardiography (ECG) has asits goal the reconstruction of cardiac electrical events frominformation obtained noninvasively at the body surface. Ateach instant of time throughout the cardiac cycle, the potentialdistribution over the entire torso constitutes the complete setof data in noninvasive electrocardiography. The ability tononinvasively relate surface potential patterns to regionalcardiac events is of great physiological and clinicalimportance, and epicardial potentials accurately mirror detailsof the electrical events within the myocardium with highresolution. The problem of noninvasively computing the potentials on the heart’s epicardial surface from surface potentials recorded on the body constitutes one form of theinverse problem of ECG [1]. With the source determined, our specific inverse problem is to describe potentials on theepicardial surface as a function of those on the surface of thethorax, together with the knowledge of the geometric andresistive features of the intervening volume conductor. Todescribe the relationships mathematically, we use the cardiacsources in terms of epicardial surface potentials, and solve ageneralized Laplace’s equation with Cauchy boundaryconditions:
00
T BT
innonon
find
E
on
T
(
1
)
where
are the electrostatic potentials,
is the conductivitytensor,
T
and
represent the surface and the volume of thethorax,
and
E
is the surface of epicedium. Boundaryelement method (BEM) is used to seek the transfer matrix
A
:
BE
=A
(
2
)
However, the A gotten by the BEM is ill-posed in that smallmeasurement errors in the surface potentials, or any geometryerror in the volume conductor model used in the inversion procedure, lead to large perturbations in the epicardialdistributions. This renders a conventional least square error inverse, characterized by the minimization of the functional:
2
()min
E B
A M
(3)
We note that many of the inverse problems encountered inengineering may be reformulated as optimization problems butoften the corresponding object function may be highlynonlinear or nonmonotonic, may have a very complex form or its analytical expression may be unknown. Genetic algorithmsdo not require knowledge of the gradient of the objectfunctions, which make them particularly suitable for optimization problems for which an analytical expression of the object function is unknown. Mera et al has done someresearch on the use of genetic algorithms for solving ill-posed problem [2]. The use of genetic algorithms in ECG inverse problem, however, has not been reported yet. Thus the purposeof this study is to investigate how to use the genetic algorithmsfor solving the ill-posed ECG inverse problems.II. M
ETHODOLOGY
A. Genetic Algorithms
Genetic algorithms are stochastic optimization techniquesthat attempt to model the process of natural evolution, thesurvival of the fittest individual and the strive for survival. Agenetic algorithm performs a multi-directional search. It startswith a randomly initialized population of candidate solutionsand implements a probabilistic, parallel search in the solutionspace to form a new population of candidate solutions. The population undergoes a simulated evolution process. At eachgeneration the relatively “good” solutions reproduce, while therelatively “bad” solutions die. To distinguish between differentsolutions we use a fitness (evaluation) function which playsthe role of an environment [3, 4]. In order to solve the ECG
inverse problem by applying genetic algorithms, we consider float number encoded genetic algorithm which is usingtournament selection, scatter crossover, uniform mutation, andelitist selection. The genetic operators and the parameters usedfor the genetic algorithms are taken to be
Population size
n
pop
= 200
Scatter crossover
Tournament selection, tournament size
k
= 2, tournament probability
p
t
= 0.8
Proceedings of the 28th IEEEEMBS Annual International ConferenceNew York City, USA, Aug 30-Sept 3, 2006
FrEP6.51-4244-0033-3/06/$20.00 ©2006 IEEE.3907
Uniform mutation, mutation probability
p
m
= 0.02
Elitism, elitism parameter
n
e
= 2The offspring is produced from the current population usingthe above listed genetic operators. Next, the parents’ population and the children population is merged and usingtournament selection,
n
pop
individuals are selected for survivalto the next generation.The ill-posed problems of the form (2) considered in this paper were reformulated as optimization problem byminimizing the object function, such as the formulation of (3).The number of generations to be performed cannot be a priori determined, but it is determined during the evolution byusing the discrepancy principle.
B. Tikhonov Regularization Methods
Acommon approach used to overcome the instability of thesolution is via zero-order Tikhonov regularization [5, 6], in
which instead of the functional in
(3),
the alternativefunctional (4) (4)is minimized. Here, the squared norms of both the surface potential residual and the solution are minimized together, theidea being
to
suppress unwanted oscillations in the solution.The corresponding solution is
1
()
TT EB
AAA I
(5)
where
I
is
an
n
x
n
identity matrix and the parameter (>0),known as the regularization parameter, serves to determine therelative weight accorded to each of the two terms in (4).Adifferent solution,
E
,
results for each choice of . When theepicardial distribution is known ahead of time (as occurs insimulation studies), it is possible to gauge the correctness of the solution by either relative error (RE), namely
()
t E E
RE t
(6)
or the correlation coefficient (CC), given by
1
[()][()]()
nt i t E i E i t t E E
CC t
(7)
In (6) and (7),
E
denotes the known epicardial distribution,and
t
the computed one. The quantities
E
and
t
are,respectively, the mean values of
E
and
t
, over the
n
epicardial sites.There exist different ways of choosing the regularization parameter. Here we employ the L-curve technique [6, 7]. The
L-curve approach involves a plot using a log-log scale of thenorm of the solution
E
on the ordinate, against the norm of the residual
EB
A
, on the abscissa, withas a parameter along the resulting curve. As long as theuncorrelated Gaussian noise present in
B
dominates thecorrelated geometric noise in
A,
this curve is in the form of an“L” and the value, , at the corner of the “
L
” is selected. Atthe corner, both
EB
A
and
E
simultaneously attainlow values, intuitively suggesting a reasonable solution. Anumerical algorithm to compute the site of the corner as the point of maximum curvature can be found in Hansen [7].
C. Discrepancy Principle
Discrepancy principle [8], in all simplicity, amounts tochoosing regularization parameter such that the residual normsfor the regularized solution satisfy:
22
EB
Ae
(8)where
2
e
is an estimate of noise present in the inverse problem, i.e.,
22
ˆ
BB
e
,
ˆ
B
is the exact potentialwithout noise, and
B
is potential with arbitrary small noiselevel
2
e
.
In
this
paper, the discrepancy principle may be used for choosing the generations by stopping the reproduction process when
22
kB
Axe
(9)where
k
x
is the numerical solution obtained after
k
reproductions.
D. Simulation Protocol
The simulation protocol is used to test the validity of genetic algorithms for solving the ECG inverse problem. Weadopt a concentric sphere model to represent the heart and body surfaces, with known analytical distributions on both being induced by placing a current dipole within center of theinner sphere. In this way, 2
cos
(
theta
)
mv
potential distributionon the inner surface is produced, and here
theta
is the anglewith Z-axis. To be somewhat representative of the epicardiumand human torso, the radii of the inner and the outer spheresare chosen as 4
cm
and 10
cm
, respectively [9]. The inner andouter spheres are discretized using uniform sphericalcoordinate grids consisting of 120 points and 190 points,respectively. Two additional grid points are added, one at thetop and the other at the bottom, so that the resultingtriangularized surfaces are closed, as shown in Fig. 1. Theouter surface comprises 192 nodes and 380 triangles, and thereare 122 nodes and 240 triangles in the inner surface. The boundary element method, based on a triangular mesh with alinear variation in potential [10], is used to derive the 192 ×122 transfer matrix A, which is adopted in the inversecomputation. Next, outer surface potentials at its 192 surfacenodes are computed from these 122 inner surface potentialsusing the 192 × 122 A matrix, determined again by the boundary element method. In the inverse direction, however, potentials are sought at 122 uniformly distributed inner points,to be computed from 192 outer surface sites distributed, and
22
()min
E
EE V EB
MA
3908
an additional 10
dB
white Gaussian noise
e
is added to theouter surface potentials, where
2
e
equals to 1.8955.
Fig. 1. The triangularized surfaces of the concentric spheres model, the outer surface comprised 192 nodes and 380 triangles, the inner surface consisting of 122 nodes and 240 triangles.
III. R
ESULTS
From Fig. 2, we can see that after only 20 iterations thefittest individuals in the population give a very good fit to thedata which satisfy the discrepancy principle(
2
()1.9242
M e
), but the solutions of the ill-posed arenot exact which attain a high relative error, (RE=1.0264,CC=0.7122). Once such an unstable solution is generated inthe genetic algorithm, since it gives a better fit to the data thanthe exact solution, then it will prevent the exact solutions andthe solutions close to it from being considered solutions to the problem as the fittest individuals of a generation. Furthermore, by providing a very good fit to the data, then solutions have avery high fitness value and therefore may force the geneticalgorithm search to focus around it or similar incorrectsolutions. As shown in Table1, after 200 iterations, we still getthe “false” solutions with RE= 0.9347, CC= 0.7491. Moreover,since the initial population and some of the individuals createdduring the early generations are randomly generated, theglobal optimum of the problem, which is a highly unstable anda non-smooth solution could appear in the population at anearly stage causing the genetic algorithm to be stationary fromthat point onward. However, for ill-posed problems thesolution to the problem is not the global optimum of thefitness function but a solution to satisfy the optimum balance between the stability (smoothness) and the fit to the data.Therefore in the approach considered here genetic algorithmscannot be used to regularize ill-posed problems since they may produce highly unstable solutions at the very first generationsand then they may stagnate around these solutions.However, if additional information about the solution of the problem is available, then such information should be used toadd constraints that can prevent unstable solutions from beinggenerated within the genetic algorithm. Once such constraintshave been added, a genetic algorithm can be successfullyapplied to find the global optimum of the problem and will getgood solution with low relative error and high correlationcoefficient. Here we use the Tikhonov regularization methodto find the information about the solution of the inverse problem, and use the regularized solution to construct theinitial populations which can be acted as the constraints. After adding such constrains, we can get relative good solutionswith RE= 0.2276, CC= 0.9739, and
2
()1.8752
M e
, asshown in Fig. 3.
Fig. 2. The error
M()
as function of the number of generations performed,
M()
on the ordinateand generations on the abscissa.Table.1 Comparison of the object function
M()
,
RE
,and
CC
on differentgenerations
Generations
M( )
RE CC
201.92421.02640.7122501.87210.91550.74521001.86541.03940.69942001.84910.93470.7491
IV. D
ISCUSSION
A
ND
C
ONCLUSION T
he use of the genetic algorithms for solving ill-posed ECGinverse problem has been investigated. The results show thatgenetic algorithms do not have a regularizing character andtherefore they cannot be used to regularize an ill-posed problem if the ill posedness is not dealt with by another method. However, it was found that GAS could be applied tosolve the ill-posed inverse problem if additional informationabout the solutions or other additional constraints is available.Those additional information and constraints can prevent thefalse solutions from being generated within the geneticalgorithms. How to find the available information andconstrains plays a key role in using the GAS for solving theill-posed inverse problem. In this paper, we adopt theTikhonov regularized solutions as the additional informationabout solutions, and the results shows that we can get thestable solutions with low relative error and high correlationcoefficient. Therefore, GAS may be a useful tool for solvingECG inverse problem.
3909
Fig. 3. The error
M()
as function of the number of generations performed,
M()
on the ordinateand generations on the abscissa. The initial populationis made up from the regularized methods.
A
CKNOWLEDGMENT
This project is supported by the 973 National Key BasicResearch & Development Program (2003CB716106), the National Natural Science Foundation of China (30370400) andthe Program for New Century Excellent Talents in University(NCET-04-0550).
R
EFERENCES[1]Robert S. Macleod and Dana H. Brooks, “Recent Progress in InverseProblems in Electrocardiology”, IEEE Eng. in Medicine and Biology, pp.73 -83,1998[2]N.S. Mera1, L. Elliott, D.B. Ingham, “On the use of genetic algorithmsfor solving ill-posed problems”, Inverse Problems in Engineering, Vol 11, No 2, pp105-121, 2003.[3]Melanie Mitchel, “An introduction to genetic algorithms”, MIT PressCambridge, MA, USA, 1996.[4]Lothar M. Schmitt, “Theory of genetic algorithms II: models for geneticoperators over the string-tensor representation of populations andconvergence to global optima for arbitrary fitness function under scaling”, Theoretical Computer Science, v.310 n.1-3, p.181-231, 01January 2004.[5]O. Skipa, M. Nalbach, F.B. Sachse, O. Dossel, “Comparison of regularization techniques for the reconstruction of transmembrane potentials in the heart”, Biomed Tech (Berl)., vol47 Suppl 1 Pt 1:pp.246-8, 2002.[6]P.R. Johnston, R.M. Gulrajani, “Selecting the corner in the L-curveapproach to Tikhonov regularization”, IEEE Trans Biomed Eng. Vol47(9): pp.1293-6, 2000.[7]P.C. Hansen, “Rank-Deficient and Discrete Ill-Posed Problems. Numerical Aspects of Linear Inversion”, SIAM Monogr. Math. ModelComput., SIAM, Philadelphia, (1998).[8]Ronny Ramlau, “Morozovs Discrepancy Principle for Tikhonov-Regularization Nonlinear Operators”, Numerical Functional Analysisand Optimization, Vol 23(1-2): PP147 – 172, 2002.[9]P.R. Johnson, R.M. Gulrajani, “A New Method for RegularizationParameter Determination in the Inverse Problem of Electrocardio-graphy”, IEEE Tran. Biomed. Eng., 44(1): pp.19-39, 1997.[10]G. Fischer, B. Tilg, P. Wach, G. Lafer, W. Rucker, “Analyticalvalidation of the BEM--application of the BEM to theelectrocardiographic forward and inverse problem”, Comput MethodsPrograms Biomed, vol. 55(2): pp.99-106, 1998.
3910

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks