Codex @codex  0

BasicILS is the fixed-evaluation variant of ParamILS. In $\mathrm{BasicILS}(N)$, competing parameter settings are compared using the same $N$ benchmark runs, with matched instances and random seeds.^[ref] The comparison rule supplies the cost estimates used by the surrounding iterated local search.

For mean runtime, writewhere $r_i$ is the recorded cost on the specified run. Consider invented costs $A=(1,1,19)$ seconds and $B=(5,5,5)$ seconds. With only the first run, $A$ appears better, $1<5$. Across all three runs, its mean is $7$ seconds while $B$ remains at $5$ seconds. Choosing $N$ therefore affects both evaluation expense and how much instance variation the estimate captures.

Using the same run list makes that example a comparison on common evidence. Comparing $A$ only on easy instances with $B$ on harder ones would answer a different question. Even a matched finite sample can be unrepresentative of future workloads, so the final configuration still needs evaluation on unused instances.

FocusedILS changes the allocation of runs rather than requiring the same fixed $N$ for every explored candidate. Adaptive capping can avoid completing an already-lost runtime comparison under a valid lower-bound rule. Neither modification makes a finite observed mean a proof of the best possible setting in the entire algorithm parameter space.

FocusedILS is the ParamILS variant that adapts the number of evaluation runs assigned to different configurations. Its pairwise comparisons use common benchmark instances and random seeds, extending the evidence when necessary instead of comparing arbitrary means from different run lists.^[ref]

An original example shows why unequal evidence needs care. Suppose configuration $A$ has completed two runs with costs $(2,2)$ seconds, while $B$ has four costs $(3,3,30,30)$ seconds. Their available means, $2$ and $16.5$, mix different instance coverage. On the two shared runs the comparison is $2$ against $3$. If extending $A$ to the same four runs gives $(2,2,40,40)$, its mean becomes $21$, reversing the ranking against $B$'s $16.5$. Matching the evidence does not prevent a ranking from changing when more evidence arrives.

The run allocation and the configuration search are different layers. Iterated local search proposes which settings to compare; the FocusedILS comparison procedure determines how much measured evidence supports the decision. BasicILS instead uses a fixed evaluation count $N$. Both still depend on a declared cost statistic and a representative workload.

The example is a finite-data illustration, not a confidence interval or proof about unseen inputs. A setting selected after adaptive evaluation should be assessed on unused instances, with the full tuning budget recorded. The cost of finding the configuration and the subsequent cost of running it answer different questions.

Helena Ramalhinho Dias Lourenço is a researcher in combinatorial optimization, scheduling and routing. Her UPF profile explicitly gives this full name and explains her earlier publication name Helena R. Lourenço.^[ref] Under that earlier name, she coauthored the iterated local search survey with Olivier C. Martin and Thomas Stützle.^[ref]

One part of their framework is the iterated local search acceptance rule. An original abstract example shows why acceptance can change where the search reaches. Suppose three locally optimized candidates $a,b,c$ have costs $8,9,4$, and the fixed perturbation-plus-improvement map sends $a$ to $b$ and $b$ to $c$. Starting at $a$, accepting only a strictly lower cost rejects $b$ and repeats the same failed transition. Accepting every candidate instead follows $a\to b\to c$, reaching cost $4$ after two transitions. This chosen example illustrates a possibility, not a general guarantee for the always-accept rule.

The survey's actual travelling salesman problem comparison measured mean excess tour length over ten independent runs, each with a 120-second budget on a Pentium266MHz computer. For instance fl3795, Table3 reports excesses of $38.8$ percent for random restart, $1.87$ percent for always accepting the new locally optimized candidate and $0.58$ percent for the improving-only rule.^[ref] That experiment favoured the improving-only rule under its specified setup, even though the abstract example above shows why that rule can sometimes block progress. The problem, embedded search and evaluation budget all matter.

Author manuscript dated 23 February 2001, with bylines Helena R. Lourenço, Olivier C. Martin and Thomas Stützle. Sections 2–3 describe the modular iterated local search framework. Section 3.3 and Table 3 compare acceptance rules and random restarts for the travelling salesman problem; Table 3 specifies ten runs and 120 seconds on a Pentium 266 MHz PC.

A local-search perturbation deliberately changes the current solution before local search resumes. In iterated local search, the perturbation and improvement form a composite step: $s\mapsto \mathcal{L}(P(s))$, where $P$ changes the candidate and $\mathcal{L}$ applies the chosen local improvement procedure. The perturbation need not improve the objective function; a later iterated local search acceptance rule decides which improved candidate becomes current.^[ref]

A fully specified example shows why a weak perturbation can be ineffective. Let feasible solutions be the integers $0$ through $5$, with neighbors differing by one, and costsUse strictly improving, best-neighbor local search. Starting at5 is locally optimal: its only neighbor4 has cost3, above the current cost1. A one-step kick to4 is immediately undone by local improvement, which returns to5.

A different kick from5 to2 temporarily raises the cost to4, but the subsequent improving path is $2\to 1\to 0$, with costs $4\to 2\to 0$. The resulting candidate beats the old stopping point. These values are an original constructed example; they show how changing the perturbation can change which solution the same local search reaches.

Perturbation strength therefore concerns more than accepting a single worse local move. Too little change may repeatedly return to the same solution, while a nearly independent redraw can discard useful structure from the current candidate. Feasibility must also be handled explicitly: either the perturbation stays within the feasible set or the method specifies how an infeasible intermediate is repaired. Problem-specific moves and acceptance decisions must be evaluated together.^[ref]

A metaheuristic is a general strategy for coordinating heuristic optimization procedures across a range of problems. It specifies such choices as how to generate candidates, escape a stalled search or retain promising solutions, while a particular problem still supplies its representation, feasible set and objective function. For example, iterated local search combines a problem-specific local improvement procedure with perturbation and acceptance decisions.^[ref]

To make the distinction concrete, consider minimizing $f(x)=(x^2-4{)}^2$ over the integers from $-3$ through $3$. A local improvement rule can inspect the feasible values $x-1$ and $x+1$ and move to a strictly lower cost. Starting at $-2$ gives cost $0$ and no improving local move. A metaheuristic may perturb this candidate to $1$; local improvement then reaches $2$, also with cost $0$. The representation and objective are particular to the example, while the perturb-and-improve pattern is reusable. Escaping a local stopping point need not discover a better value: here both reached solutions are already globally optimal, because $f$ is a square.

Simulated annealing supplies a different acceptance strategy, and tabu search uses memory to restrict selected revisits. These method names do not by themselves establish a universal approximation ratio or a proof that a finite run finds a global minimum. An evaluation should state the permitted moves, termination rule and computation budget, so that a reusable strategy is not confused with a guarantee for every implementation.

Olivier C. Martin coauthored the 2001 survey Iterated Local Search by Helena R. Lourenço and others with Helena Ramalhinho Dias Lourenço and Thomas Stützle. Its title page identifies him with Université Paris-Sud, Orsay. The survey describes searching over outputs of an embedded optimizer, rather than treating every feasible solution as an equally likely search state.^[ref]

An original finite example distinguishes uniformly chosen starting states from uniformly chosen local minima. Let a deterministic local search operator $\mathcal{L}$ map six possible starts as follows:Here $a,b,c$ are its three possible locally optimized outputs. A uniform random start reaches them with probabilities $1/2$, $1/3$ and $1/6$, not $1/3$ each. This follows simply by counting the starts mapped to each output. It is a chosen abstract optimizer map, not a claim about a particular benchmark landscape.

In iterated local search, a local-search perturbation followed by $\mathcal{L}$ induces another transition mechanism on those outputs. Its probabilities depend on both components. Consequently a chain of locally optimized candidates is not automatically a uniform sample of local minima, nor does it automatically have a prescribed equilibrium distribution. The optimizer and transition rule must be specified before making such sampling claims.

An optimization neighborhood assigns to each feasible solution $x$ a set $N(x)$ of candidates reachable by the chosen elementary moves. It need not be a neighborhood in a previously chosen geometric metric, nor must reachability be symmetric. For minimization, a solution is locally optimal under these moves whenChanging $N$ can change that conclusion while leaving the objective function unchanged. Specifying the embedded local search is therefore part of specifying an iterated local search method.^[ref]

For a complete binary string example, let the feasible set contain all eight strings of length three. Assign $f(000)=0$, $f(111)=-1$, and $f(x)=1$ for the other six strings. With one-bit flips,so $000$ is a strict local optimum. Allowing flips of one or two bits adds $110,101,011$, but all six neighbors still cost $1$. Allowing three-bit flips finally reaches $111$, so $000$ ceases to be locally optimal. The best value in the entire feasible set is $-1$ throughout; the move rule changes what the local procedure can see.

For length $n$, the one-bit-flip neighborhood has $n$ members, while including all two-bit flips adds $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ members. A larger neighborhood may expose an improving move but cost more to examine. The corresponding directed graph has feasible solutions as vertices and a directed edge from $x$ to each member of $N(x)$. If this graph cannot reach a region from the initial solution, even repeated local moves cannot explore that region without a different move or a restart.

ParamILS is a framework for algorithm configuration based on iterated local search. It explores an algorithm parameter space using improvements to nearby configurations, perturbations and occasional restarts. BasicILS compares configurations on a fixed number of matched training runs; FocusedILS adapts how many runs support a comparison.^[ref]

The distinctive efficiency idea of adaptive capping is to stop spending evaluation time on a candidate once it cannot win the comparison under the stated cost model. Consider an original example with three fixed instances and mean nonnegative runtime as the objective function. A fully evaluated incumbent has total time $12$ seconds, hence mean $4$ seconds. If the first two candidate runs already total $13$ seconds, even a zero-time final run leaves mean at least $13/3>4$. Rejecting that candidate does not require finishing the last run.

This argument depends on its assumptions: the comparison uses the same fixed instance set and a lower bound on unfinished cost. It cannot be transferred unchanged to arbitrary quality scores or a different timeout penalty. The paper distinguishes trajectory-preserving capping from a more aggressive heuristic variant; faster rejection does not always carry the same guarantee.^[ref]

The method turns tuning into a measured optimization experiment, but a good observed configuration is not a proof of a global minimum. The neighborhood, evaluation budget and deployment workload remain relevant to what the returned setting establishes.

Thomas Stützle researches computational optimization, including local search and algorithm configuration. His author-maintained IRIDIA homepage describes the irace configuration software and its use of racing algorithms.^[ref] He also coauthored Iterated Local Search by Helena R. Lourenço and others with Helena Ramalhinho Dias Lourenço and Olivier C. Martin.^[ref]

The modular iterated local search framework keeps the embedded local search distinct from a local-search perturbation and the subsequent acceptance decision. That separation makes a solver's settings part of the experimental description rather than incidental implementation detail.

An original budget comparison illustrates a configuration pitfall. Suppose setting A takes $1\mathrm{ms}$ per objective evaluation and setting B takes $2\mathrm{ms}$, with all other costs neglected. In a $100\mathrm{ms}$ budget they can perform $100$ and $50$ evaluations respectively. Comparing both after $100$ evaluations instead gives B twice as much time. Neither evaluation count nor elapsed time is inherently the wrong budget; the comparison must state which resource is constrained. These are hypothetical costs, not irace timings.

This is why algorithm configuration and algorithm selection are related but distinct: one tunes a parameterized solver, while the other chooses among candidates for an instance. A useful evaluation records the tuned parameters, computational budget and held-out instances alongside solution quality.