Transcript Effective gradient-free methods for inverse problems

Effective gradient-free
methods for inverse
problems
Jyri Leskinen
FiDiPro DESIGN project
Introduction
 Current
research
 Evolutionary algorithms
 Inverse problems
 Case study: Electrical Impedance
Tomography (EIT)
 Future
Current research
 Inverse
problems
– Shape reconstruction
– Electrical Impedance Tomography (EIT)
 Methods
– Evolutionary algorithms (GA, DE)
– Memetic algorithms
– Parallel EAs
 Implementation
of the Game Theory
– Nash GAs, MAs, DEs
Evolutionary algorithms
 Based
on the idea of natural
selection (Darwin)
 Operate a population of solution
candidates (“individuals”)
 New solutions by variation
(crossover, mutation)
 Convergence by selection (parent
selection, survival selection)
Evolutionary algorithms
 Several
methods
– Genetic algorithms (Holland, 1960s;
Goldberg, 1989)
– Evolutionary strategies (Rechenberg,
1960s)
– Differential evolution (Price & Storn,
1995)
Evolutionary algorithms
 Simple
EA
– Generate initial population
– Until termination criteria met,
 Select
parents
 Produce new individuals by crossing over
the parents
 Mutate some of the offspring
 Select fittest individuals for the next
generation
Evolutionary algorithms
 Pros:
– Global search methods
– Easy to implement
– Allows difficult objective functions
 Cons:
– Slow convergence rate
– Many objective function evaluations
needed
Local search methods
 Operate
on neighborhoods using
certain moves
 Pros:
– Fast convergence rate
– Less resource-intensive
 Cons:
– Converges to the nearest optimum
– Gradient methods need “nice” objective
function
Memetic algorithms
 Hybridization
of EAs and LSs
– Global method
– Improved convergence rate
 Memetic
algorithms
– A class of hybrid EAs
– Based on the idea of memes (Dawkins)
– LS applied during the evolutionary
process
Memetic algorithms
 Simple
MA
– Generate initial population
– Until termination criteria met,
 Select
parents
 Produce new individuals by crossing over
the parents
 Mutate some of the offspring
 Improve offspring by local search
 Select fittest individuals for the next
generation
Memetic algorithms
 Typically
Lamarckian
– Acquired properties inherited
– Unnatural
 MAs
not limited to that!
– Parameter tuning
– Local search operators as memes
 Parameters
encoded in chromosomes
 Meme populations
– etc.
Inverse problems
 Inverse
problem:
– Data from a physical system
– Construct the original model using
available data and simulations
 Typical
IPs:
– Image reconstruction
– Electromagnetic scattering
– Shape reconstruction
Inverse problems
 Objective
function for example a sum
of squares
min F(x) = ∑ |x(i) – x*(i)|2
– x: the vector of values from a simulated
solution (forward problem)
– x*: the vector of target values
Inverse problems
 Often
difficult to solve because of illposedness: the acquired data is not
sufficient → the solution is not
unique!
 Extra information needed;
regularization
Electrical Impedance Tomography
 Used
in
– Medicine (experimental)
– Geophysics
– Industrial process imaging
 Simple,
robust, cost-effective
 Poor spatial, good temporal
resolution
Electrical Impedance Tomography
 Data
from electrodes on the surface
of the object
 Inject small current using two of the
electrodes
 Measure voltages using the other
electrodes
 Reconstruct internal resistivity
distribution from voltage patterns
Electrical Impedance Tomography
Source: Margaret Cheney et al. (1999)
Electrical Impedance Tomography
Source: Margaret Cheney et al. (1999)
Electrical Impedance Tomography
Source: The Open Prosthetics Project (http://openprosthetics.org)
Electrical Impedance Tomography
 PDE:
Complete Electrode Model
 Forward
problem: calculate voltage
values Ul using FEM
Electrical Impedance Tomography
 Inverse
problem: minimize F(σh) by
varying the piecewise constant
conductivity distribution σh
Electrical Impedance Tomography
 Mathematically
hard, non-linear ill-
posed problem
 Typically solved using Newton-Gauss
method + regularization (Tikhonov,
…)
 Resulting image smoothed, image
artifacts
Electrical Impedance Tomography
Electrical Impedance Tomography
 Solution:
Reconstruct the image
using discrete shapes?
 Resulting objective function
multimodal, non-smooth
 Solution: Use global methods
Electrical Impedance Tomography
 Simple
test case: Recover circular
homogeneity (6 control parameters)
 Two different memetic algorithms
proposed:
– Lifetime Learning Local Search (LLLSDE)
– Variation Operator Local Search
(VOLSDE)
Electrical Impedance Tomography
Evolutionary framework based on the selfadaptive control parameter differential
evolution (SACPDE)
 LLLSDE:

– Lamarckian MA
– Local search operator Nelder-Mead simplex
method

VOLSDE:
– Weighting factor F improved by onedimensional local search
Electrical Impedance Tomography
 Five
algorithms tested (GA, DE,
SACPDE, LLLSDE, VOLSDE)
 Result:
– GA performed poorly
– DE better, some failures
– LLLSDE best, but the difference to other
adaptive methods minimal
Electrical Impedance Tomography
Now & future
Improve diversity using multiple
populations (“island model”)
 EAs can be used to find Nash equilibria
 Improve convergence rate with virtual
Nash games?
 Can competitive games sometimes
produce better solutions than cooperative
games in multi-objective optimization?

Thank you for your attention!
Questions?