Section 4.6, Proposition — Biased-Fitness survivor selection never removes an elite individual outside X
ProvedVidalHGS.Elitism.elite_not_removedConsider one subpopulation of the hybrid genetic algorithm HGSADC, with costs , distance , diversity contribution , elite parameter , and current best solution . The survivor-selection procedure removes individuals one at a time; at each step it recomputes the ranks, the Biased Fitness and the set of non-best individuals having a clone on the current population, and removes an individual of maximum from if , and from the whole population otherwise.
Suppose . If , , and is among the best individuals of in terms of fitness (fewer than members of have strictly smaller cost), then for every run of the procedure from to the final population ,
In the paper's words: using the Biased Fitness function, an individual that is part of the best individuals of the subpopulation in terms of fitness will not be removed by the survivor-selection procedure. This is the elitism guarantee that justifies the parameter in the Biased Fitness (7).
Formalization Note. The number of removals is called nOff in Lean. The hypothesis is not written in the Proposition; it comes from the paper's setting (Section 4.6: a subpopulation of individuals is reduced to ; Table 1: with ), and without it the statement is false. The conclusion holds for every run, whatever tie-breaking is used in the maximum. The diversity contribution is an arbitrary function of (population, individual), which includes the paper's (5). The best solution is a parameter and need not belong to (for the infeasible subpopulation it is the incumbent feasible solution); may itself be the best solution.
import Mathlib import Definitions.Def_VidalHGS_Elitism_SurvivorSelection
namespace VidalHGS.Elitism
/-- Section 4.6, pp. 16–17, Proposition: using the Biased Fitness function, an individual
`J ∉ X` that is part of the `nbElit` best individuals of the subpopulation `P` in terms of
fitness is not removed by the survivor-selection procedure, which removes `nOff` (the paper's
`λ`) individuals, provided `nbElit + nOff ≤ |P|` (Table 1: `nbElit = el × μ ≤ μ`, and the
procedure reduces `μ + λ` individuals to `μ`). -/
theorem elite_not_removed {α : Type*} [DecidableEq α]
(c : α → ℝ) (δ : α → α → ℝ) (Δ : Finset α → α → ℝ) (nbElit : ℕ) (best : α)
(nOff : ℕ) (P P' : Finset α) (J : α)
(hrun : SurvivorRun c δ Δ nbElit best nOff P P') (hsize : nbElit + nOff ≤ P.card)
(hJ : J ∈ P) (hJX : J ∉ cloneSet c δ best P) (helite : IsElite c nbElit P J) :
J ∈ P' := by sorry
end VidalHGS.Elitism
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.