| 1 | package Physics::Ellipsometry::VASE::Optimizer; | ||
| 2 | use strict; | ||
| 3 | use warnings; | ||
| 4 | use PDL; | ||
| 5 | use Exporter 'import'; | ||
| 6 | |||
| 7 | our @EXPORT_OK = qw(differential_evolution grid_search); | ||
| 8 | |||
| 9 | our $VERSION = '1.04'; | ||
| 10 | |||
| 11 | =encoding utf8 | ||
| 12 | |||
| 13 | =head1 NAME | ||
| 14 | |||
| 15 | Physics::Ellipsometry::VASE::Optimizer - Global optimization algorithms | ||
| 16 | for ellipsometry model fitting | ||
| 17 | |||
| 18 | =head1 SYNOPSIS | ||
| 19 | |||
| 20 | use PDL; | ||
| 21 | use Physics::Ellipsometry::VASE::Optimizer qw(differential_evolution | ||
| 22 | grid_search); | ||
| 23 | |||
| 24 | # Define an objective function (e.g., MSE from a VASE model) | ||
| 25 | my $objective = sub { | ||
| 26 | my ($params_pdl) = @_; | ||
| 27 | # ... evaluate model, return scalar cost (chi², MSE, etc.) | ||
| 28 | }; | ||
| 29 | |||
| 30 | # Differential Evolution — find global minimum | ||
| 31 | my ($best, $cost) = differential_evolution( | ||
| 32 | objective => $objective, | ||
| 33 | bounds => [ [0, 500], [1, 4], [0, 1] ], | ||
| 34 | verbose => 1, | ||
| 35 | ); | ||
| 36 | printf "DE result: cost=%.4f params=%s\n", $cost, $best; | ||
| 37 | |||
| 38 | # Grid Search — scan a 1-D or 2-D landscape | ||
| 39 | my ($best_g, $cost_g) = grid_search( | ||
| 40 | objective => $objective, | ||
| 41 | base_params => pdl([100, 2.0, 0.01]), | ||
| 42 | grid => [ { index => 0, min => 10, max => 300, steps => 30 } ], | ||
| 43 | ); | ||
| 44 | |||
| 45 | =head1 DESCRIPTION | ||
| 46 | |||
| 47 | Levenberg-Marquardt (LM) is a local optimizer — it converges quickly | ||
| 48 | but can get trapped in local minima, especially when the initial | ||
| 49 | parameter guesses are far from the true values. This is a common | ||
| 50 | problem in ellipsometry, where the cost surface often has multiple | ||
| 51 | minima due to thin-film interference periodicity (thickness ambiguity) | ||
| 52 | and correlations between dispersion parameters. | ||
| 53 | |||
| 54 | Physics::Ellipsometry::VASE::Optimizer provides B<global> search | ||
| 55 | strategies that explore the parameter space broadly and return a | ||
| 56 | good starting point for subsequent LM refinement. The typical | ||
| 57 | workflow is: | ||
| 58 | |||
| 59 | 1. Global search → approximate minimum | ||
| 60 | 2. LM refinement → precise, converged fit | ||
| 61 | |||
| 62 | =head1 FUNCTIONS | ||
| 63 | |||
| 64 | =head2 differential_evolution | ||
| 65 | |||
| 66 | my ($best_pdl, $best_cost) = differential_evolution(%args); | ||
| 67 | |||
| 68 | B<Differential Evolution> (DE/rand/1/bin) is a population-based | ||
| 69 | stochastic optimizer introduced by Storn and Price (1997). It | ||
| 70 | maintains a population of candidate solutions and evolves them through | ||
| 71 | mutation, crossover, and selection — similar in spirit to a genetic | ||
| 72 | algorithm, but operating directly on real-valued vectors with no | ||
| 73 | encoding step. | ||
| 74 | |||
| 75 | B<How it works:> | ||
| 76 | |||
| 77 | =over 4 | ||
| 78 | |||
| 79 | =item 1. B<Initialisation> — random population within the bounds. | ||
| 80 | |||
| 81 | =item 2. B<Mutation> — for each member I<x_i>, create a mutant vector: | ||
| 82 | |||
| 83 | v = x_r0 + F · (x_r1 − x_r2) | ||
| 84 | |||
| 85 | where r0, r1, r2 are distinct random population members and I<F> is | ||
| 86 | the mutation factor controlling the step size. | ||
| 87 | |||
| 88 | =item 3. B<Crossover> — mix the mutant with the current member using | ||
| 89 | binomial crossover with probability I<CR>. | ||
| 90 | |||
| 91 | =item 4. B<Selection> — keep the trial if it has lower cost. | ||
| 92 | |||
| 93 | =item 5. B<Convergence> — stop when the population diversity (relative | ||
| 94 | spread across each dimension) falls below the tolerance, or after | ||
| 95 | C<maxiter> generations. | ||
| 96 | |||
| 97 | =back | ||
| 98 | |||
| 99 | B<Arguments:> | ||
| 100 | |||
| 101 | =over 4 | ||
| 102 | |||
| 103 | =item C<objective> (required) | ||
| 104 | |||
| 105 | Code reference. Receives a PDL piddle of parameters and returns a | ||
| 106 | scalar cost value (lower is better). | ||
| 107 | |||
| 108 | =item C<bounds> (required) | ||
| 109 | |||
| 110 | Arrayref of C<[min, max]> pairs, one per parameter dimension. | ||
| 111 | |||
| 112 | =item C<pop_size> | ||
| 113 | |||
| 114 | Population size. Default: 30, but automatically raised to at least | ||
| 115 | 5× the number of dimensions. | ||
| 116 | |||
| 117 | =item C<F> | ||
| 118 | |||
| 119 | Mutation factor (0 to 2). Default: 0.7. Higher values explore more | ||
| 120 | aggressively; lower values exploit locally. | ||
| 121 | |||
| 122 | =item C<CR> | ||
| 123 | |||
| 124 | Crossover probability (0 to 1). Default: 0.9. Higher values mix | ||
| 125 | more dimensions per trial. | ||
| 126 | |||
| 127 | =item C<maxiter> | ||
| 128 | |||
| 129 | Maximum number of generations. Default: 200. | ||
| 130 | |||
| 131 | =item C<tol> | ||
| 132 | |||
| 133 | Convergence tolerance on population diversity. Default: 1e-6. | ||
| 134 | |||
| 135 | =item C<seed> | ||
| 136 | |||
| 137 | Optional random seed for reproducibility. | ||
| 138 | |||
| 139 | =item C<verbose> | ||
| 140 | |||
| 141 | Print progress every 20 generations. Default: 0. | ||
| 142 | |||
| 143 | =back | ||
| 144 | |||
| 145 | B<Returns:> C<($best_pdl, $best_cost)>. | ||
| 146 | |||
| 147 | B<Example — find thickness and Cauchy A for a single-layer film:> | ||
| 148 | |||
| 149 | use Physics::Ellipsometry::VASE; | ||
| 150 | use Physics::Ellipsometry::VASE::Optimizer qw(differential_evolution); | ||
| 151 | use Physics::Ellipsometry::VASE::TMM qw(psi_delta); | ||
| 152 | use Physics::Ellipsometry::VASE::Dispersion qw(cauchy_nk); | ||
| 153 | |||
| 154 | my $vase = Physics::Ellipsometry::VASE->new(layers => 1); | ||
| 155 | $vase->load_data('sample.dat'); | ||
| 156 | |||
| 157 | my $objective = sub { | ||
| 158 | my ($p) = @_; | ||
| 159 | my $d = $p->at(0); | ||
| 160 | my $A = $p->at(1); | ||
| 161 | my ($n, $k) = cauchy_nk($vase->{wavelength}, $A, 0.01, 0.0); | ||
| 162 | my $N_film = $n + i() * $k; | ||
| 163 | my ($psi, $delta) = psi_delta( | ||
| 164 | $vase->{wavelength}, $vase->{angle}, | ||
| 165 | [$vase->{N_air}, $N_film, $vase->{N_sub}], [$d], | ||
| 166 | ); | ||
| 167 | my $resid = ($psi - $vase->{psi_data})**2 | ||
| 168 | + ($delta - $vase->{delta_data})**2; | ||
| 169 | return sum($resid)->sclr; | ||
| 170 | }; | ||
| 171 | |||
| 172 | my ($best, $cost) = differential_evolution( | ||
| 173 | objective => $objective, | ||
| 174 | bounds => [ [1, 500], [1.3, 3.0] ], # thickness, Cauchy A | ||
| 175 | pop_size => 50, | ||
| 176 | maxiter => 300, | ||
| 177 | verbose => 1, | ||
| 178 | seed => 42, | ||
| 179 | ); | ||
| 180 | |||
| 181 | printf "Best: d=%.1f nm, A=%.4f (cost=%.4f)\n", | ||
| 182 | $best->at(0), $best->at(1), $cost; | ||
| 183 | |||
| 184 | # Now refine with LM | ||
| 185 | $vase->set_model(sub { ... }); | ||
| 186 | my $refined = $vase->fit($best); | ||
| 187 | |||
| 188 | =head2 grid_search | ||
| 189 | |||
| 190 | my ($best_pdl, $best_cost) = grid_search(%args); | ||
| 191 | |||
| 192 | B<Grid search> systematically evaluates the objective function at | ||
| 193 | every point on a regularly spaced grid over one or more parameter | ||
| 194 | dimensions. All parameters not included in the grid are held at | ||
| 195 | their C<base_params> values. | ||
| 196 | |||
| 197 | This is a brute-force method best suited for: | ||
| 198 | |||
| 199 | =over 4 | ||
| 200 | |||
| 201 | =item * B<1-D scans> — e.g., sweeping thickness to find the correct | ||
| 202 | interference order before LM refinement. | ||
| 203 | |||
| 204 | =item * B<2-D maps> — e.g., scanning thickness + refractive index to | ||
| 205 | visualise the cost landscape. | ||
| 206 | |||
| 207 | =back | ||
| 208 | |||
| 209 | For three or more parameters the number of evaluations grows | ||
| 210 | exponentially and DE is usually a better choice. | ||
| 211 | |||
| 212 | B<Arguments:> | ||
| 213 | |||
| 214 | =over 4 | ||
| 215 | |||
| 216 | =item C<objective> (required) | ||
| 217 | |||
| 218 | Code reference. Receives a PDL piddle of parameters and returns a | ||
| 219 | scalar cost value. | ||
| 220 | |||
| 221 | =item C<base_params> (required) | ||
| 222 | |||
| 223 | PDL piddle of default parameter values. Grid dimensions override | ||
| 224 | their respective elements; all others stay fixed. | ||
| 225 | |||
| 226 | =item C<grid> (required) | ||
| 227 | |||
| 228 | Arrayref of grid axis specifications, each a hashref: | ||
| 229 | |||
| 230 | { index => $param_index, # 0-based position in params PDL | ||
| 231 | min => $lower_value, | ||
| 232 | max => $upper_value, | ||
| 233 | steps => $number_of_points } | ||
| 234 | |||
| 235 | =item C<verbose> | ||
| 236 | |||
| 237 | Print the best cost at the end. Default: 0. | ||
| 238 | |||
| 239 | =back | ||
| 240 | |||
| 241 | B<Returns:> C<($best_pdl, $best_cost)>. | ||
| 242 | |||
| 243 | B<Example — 1-D thickness scan:> | ||
| 244 | |||
| 245 | my ($best, $cost) = grid_search( | ||
| 246 | objective => $objective, | ||
| 247 | base_params => pdl([100.0, 2.1, 0.01]), | ||
| 248 | grid => [ | ||
| 249 | { index => 0, min => 10, max => 500, steps => 100 }, | ||
| 250 | ], | ||
| 251 | verbose => 1, | ||
| 252 | ); | ||
| 253 | printf "Best thickness = %.1f nm (cost = %.4f)\n", | ||
| 254 | $best->at(0), $cost; | ||
| 255 | |||
| 256 | B<Example — 2-D thickness × refractive index map:> | ||
| 257 | |||
| 258 | my ($best, $cost) = grid_search( | ||
| 259 | objective => $objective, | ||
| 260 | base_params => pdl([100.0, 2.1, 0.01]), | ||
| 261 | grid => [ | ||
| 262 | { index => 0, min => 10, max => 500, steps => 50 }, | ||
| 263 | { index => 1, min => 1.3, max => 3.0, steps => 50 }, | ||
| 264 | ], | ||
| 265 | verbose => 1, | ||
| 266 | ); | ||
| 267 | printf "Best: d=%.1f nm, n=%.3f (cost=%.4f)\n", | ||
| 268 | $best->at(0), $best->at(1), $cost; | ||
| 269 | |||
| 270 | =head1 CHOOSING A STRATEGY | ||
| 271 | |||
| 272 | =over 4 | ||
| 273 | |||
| 274 | =item B<Few parameters (1–2), known ranges> → L</grid_search> | ||
| 275 | |||
| 276 | Fast, deterministic, easy to visualise. | ||
| 277 | |||
| 278 | =item B<Many parameters (3+), or unknown ranges> → L</differential_evolution> | ||
| 279 | |||
| 280 | Handles high dimensions, robust against local minima, stochastic. | ||
| 281 | |||
| 282 | =item B<Hybrid approach> (recommended) | ||
| 283 | |||
| 284 | Use grid search or DE to find the basin of attraction, then pass the | ||
| 285 | result to L<Physics::Ellipsometry::VASE/fit> for LM refinement: | ||
| 286 | |||
| 287 | my ($coarse, $_) = differential_evolution(...); | ||
| 288 | my $precise = $vase->fit($coarse); | ||
| 289 | |||
| 290 | =back | ||
| 291 | |||
| 292 | =head1 SEE ALSO | ||
| 293 | |||
| 294 | L<Physics::Ellipsometry::VASE>, | ||
| 295 | L<Physics::Ellipsometry::VASE::Parameter> | ||
| 296 | |||
| 297 | R. Storn and K. Price, "Differential Evolution — A Simple and Efficient | ||
| 298 | Heuristic for Global Optimization over Continuous Spaces", | ||
| 299 | I<J. Global Optim.> B<11>, 341 (1997). | ||
| 300 | |||
| 301 | =cut | ||
| 302 | |||
| 303 | # Differential Evolution (DE/rand/1/bin) | ||
| 304 | # $objective->($params_pdl) returns scalar cost (e.g., chi²) | ||
| 305 | # $bounds: arrayref of [min, max] pairs for each parameter | ||
| 306 | # Returns: best parameter PDL | ||
| 307 | sub differential_evolution { | ||
| 308 | my (%args) = @_; | ||
| 309 | die "Need objective function" unless defined $args{objective}; | ||
| 310 | die "Need parameter bounds" unless defined $args{bounds}; | ||
| 311 | my $objective = $args{objective}; | ||
| 312 | my $bounds = $args{bounds}; | ||
| 313 | my $np = $args{pop_size} // 30; | ||
| 314 | my $F = $args{F} // 0.7; | ||
| 315 | my $CR = $args{CR} // 0.9; | ||
| 316 | my $maxiter = $args{maxiter} // 200; | ||
| 317 | my $tol = $args{tol} // 1e-6; | ||
| 318 | my $seed = $args{seed}; | ||
| 319 | my $verbose = $args{verbose} // 0; | ||
| 320 | |||
| 321 | srand($seed) if defined $seed; | ||
| 322 | |||
| 323 | my $ndim = scalar @$bounds; | ||
| 324 | $np = $ndim * 10 if $np < $ndim * 5; # ensure adequate population | ||
| 325 | |||
| 326 | # Initialize population randomly within bounds | ||
| 327 | my @population; | ||
| 328 | my @costs; | ||
| 329 | for my $i (0 .. $np - 1) { | ||
| 330 | my @individual; | ||
| 331 | for my $d (0 .. $ndim - 1) { | ||
| 332 | my ($lo, $hi) = @{$bounds->[$d]}; | ||
| 333 | push @individual, $lo + rand() * ($hi - $lo); | ||
| 334 | } | ||
| 335 | my $ind_pdl = pdl(\@individual); | ||
| 336 | push @population, $ind_pdl; | ||
| 337 | push @costs, $objective->($ind_pdl); | ||
| 338 | } | ||
| 339 | |||
| 340 | # Find initial best | ||
| 341 | my $best_idx = 0; | ||
| 342 | for my $i (1 .. $#costs) { | ||
| 343 | $best_idx = $i if $costs[$i] < $costs[$best_idx]; | ||
| 344 | } | ||
| 345 | my $best_cost = $costs[$best_idx]; | ||
| 346 | my $best = $population[$best_idx]->copy; | ||
| 347 | |||
| 348 | printf " DE: initial best cost = %.4f\n", $best_cost if $verbose; | ||
| 349 | |||
| 350 | # Evolution loop | ||
| 351 | for my $gen (1 .. $maxiter) { | ||
| 352 | my $improved = 0; | ||
| 353 | |||
| 354 | for my $i (0 .. $np - 1) { | ||
| 355 | # Select 3 distinct random indices ≠ i | ||
| 356 | my @r; | ||
| 357 | while (@r < 3) { | ||
| 358 | my $idx = int(rand($np)); | ||
| 359 | next if $idx == $i || grep { $_ == $idx } @r; | ||
| 360 | push @r, $idx; | ||
| 361 | } | ||
| 362 | |||
| 363 | # Mutation: v = x_r0 + F*(x_r1 - x_r2) | ||
| 364 | my $v = $population[$r[0]] + $F * ($population[$r[1]] - $population[$r[2]]); | ||
| 365 | |||
| 366 | # Clip to bounds | ||
| 367 | for my $d (0 .. $ndim - 1) { | ||
| 368 | my ($lo, $hi) = @{$bounds->[$d]}; | ||
| 369 | my $val = $v->at($d); | ||
| 370 | $val = $lo if $val < $lo; | ||
| 371 | $val = $hi if $val > $hi; | ||
| 372 | $v->set($d, $val); | ||
| 373 | } | ||
| 374 | |||
| 375 | # Crossover: binomial | ||
| 376 | my $trial = $population[$i]->copy; | ||
| 377 | my $j_rand = int(rand($ndim)); | ||
| 378 | for my $d (0 .. $ndim - 1) { | ||
| 379 | if (rand() < $CR || $d == $j_rand) { | ||
| 380 | $trial->set($d, $v->at($d)); | ||
| 381 | } | ||
| 382 | } | ||
| 383 | |||
| 384 | # Selection | ||
| 385 | my $trial_cost = $objective->($trial); | ||
| 386 | if ($trial_cost < $costs[$i]) { | ||
| 387 | $population[$i] = $trial; | ||
| 388 | $costs[$i] = $trial_cost; | ||
| 389 | $improved++; | ||
| 390 | |||
| 391 | if ($trial_cost < $best_cost) { | ||
| 392 | $best_cost = $trial_cost; | ||
| 393 | $best = $trial->copy; | ||
| 394 | } | ||
| 395 | } | ||
| 396 | } | ||
| 397 | |||
| 398 | if ($verbose && $gen % 20 == 0) { | ||
| 399 | printf " DE gen %d: best=%.4f, improved=%d/%d\n", | ||
| 400 | $gen, $best_cost, $improved, $np; | ||
| 401 | } | ||
| 402 | |||
| 403 | # Convergence check: population diversity | ||
| 404 | if ($gen > 10) { | ||
| 405 | my $spread = 0; | ||
| 406 | for my $d (0 .. $ndim - 1) { | ||
| 407 | my @vals = map { $_->at($d) } @population; | ||
| 408 | my $min_v = (sort { $a <=> $b } @vals)[0]; | ||
| 409 | my $max_v = (sort { $b <=> $a } @vals)[0]; | ||
| 410 | my ($lo, $hi) = @{$bounds->[$d]}; | ||
| 411 | $spread += ($max_v - $min_v) / (($hi - $lo) || 1); | ||
| 412 | } | ||
| 413 | $spread /= $ndim; | ||
| 414 | last if $spread < $tol; | ||
| 415 | } | ||
| 416 | } | ||
| 417 | |||
| 418 | printf " DE: final best cost = %.4f\n", $best_cost if $verbose; | ||
| 419 | return ($best, $best_cost); | ||
| 420 | } | ||
| 421 | |||
| 422 | # Grid search over specified parameter dimensions | ||
| 423 | # $objective->($params_pdl) returns scalar cost | ||
| 424 | # $base_params: PDL with default parameter values | ||
| 425 | # $grid_spec: arrayref of {index => param_idx, min => val, max => val, steps => N} | ||
| 426 | sub grid_search { | ||
| 427 | my (%args) = @_; | ||
| 428 | die "Need objective function" unless defined $args{objective}; | ||
| 429 | die "Need base_params PDL" unless defined $args{base_params}; | ||
| 430 | die "Need grid specification" unless defined $args{grid}; | ||
| 431 | my $objective = $args{objective}; | ||
| 432 | my $base_params = $args{base_params}; | ||
| 433 | my $grid_spec = $args{grid}; | ||
| 434 | my $verbose = $args{verbose} // 0; | ||
| 435 | |||
| 436 | my $best_cost = 1e30; | ||
| 437 | my $best_params = $base_params->copy; | ||
| 438 | |||
| 439 | # For 1D or 2D grid search | ||
| 440 | my @axes; | ||
| 441 | for my $spec (@$grid_spec) { | ||
| 442 | my $step = ($spec->{max} - $spec->{min}) / ($spec->{steps} - 1); | ||
| 443 | my @values; | ||
| 444 | for my $i (0 .. $spec->{steps} - 1) { | ||
| 445 | push @values, $spec->{min} + $i * $step; | ||
| 446 | } | ||
| 447 | push @axes, { index => $spec->{index}, values => \@values }; | ||
| 448 | } | ||
| 449 | |||
| 450 | # Recursive grid evaluation | ||
| 451 | _grid_recurse(\@axes, 0, $base_params->copy, $objective, | ||
| 452 | \$best_cost, \$best_params); | ||
| 453 | |||
| 454 | printf " Grid: best cost = %.4f\n", $best_cost if $verbose; | ||
| 455 | return ($best_params, $best_cost); | ||
| 456 | } | ||
| 457 | |||
| 458 | sub _grid_recurse { | ||
| 459 | my ($axes, $depth, $params, $objective, $best_cost_ref, $best_params_ref) = @_; | ||
| 460 | |||
| 461 | if ($depth >= scalar @$axes) { | ||
| 462 | my $cost = $objective->($params); | ||
| 463 | if ($cost < $$best_cost_ref) { | ||
| 464 | $$best_cost_ref = $cost; | ||
| 465 | $$best_params_ref = $params->copy; | ||
| 466 | } | ||
| 467 | return; | ||
| 468 | } | ||
| 469 | |||
| 470 | my $axis = $axes->[$depth]; | ||
| 471 | for my $val (@{$axis->{values}}) { | ||
| 472 | my $p = $params->copy; | ||
| 473 | $p->set($axis->{index}, $val); | ||
| 474 | _grid_recurse($axes, $depth + 1, $p, $objective, $best_cost_ref, $best_params_ref); | ||
| 475 | } | ||
| 476 | } | ||
| 477 | |||
| 478 | 1; |