Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Section 4.6, Proposition — Biased-Fitness survivor selection never removes an elite individual outside X

Proved
VidalHGS.Elitism.elite_not_removed

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

elitismgenetic-algorithmp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1population-management

Consider one subpopulation PPP of the hybrid genetic algorithm HGSADC, with costs ccc, distance δ\deltaδ, diversity contribution Δ\DeltaΔ, elite parameter nbElit\mathit{nbElit}nbElit, and current best solution best\mathit{best}best. The survivor-selection procedure removes λ\lambdaλ individuals one at a time; at each step it recomputes the ranks, the Biased Fitness BFBFBF and the set XXX of non-best individuals having a clone on the current population, and removes an individual of maximum BFBFBF from XXX if X≠∅X \neq \emptysetX=∅, and from the whole population otherwise.

Suppose nbElit+λ≤∣P∣\mathit{nbElit} + \lambda \le |P|nbElit+λ≤∣P∣. If J∈PJ \in PJ∈P, J∉X(P)J \notin X(P)J∈/X(P), and JJJ is among the nbElit\mathit{nbElit}nbElit best individuals of PPP in terms of fitness (fewer than nbElit\mathit{nbElit}nbElit members of PPP have strictly smaller cost), then for every run of the procedure from PPP to the final population P′P'P′,

J∈P′.J \in P'.J∈P′.

In the paper's words: using the Biased Fitness function, an individual I∉XI \notin XI∈/X that is part of the nbElit\mathit{nbElit}nbElit 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 nbElit\mathit{nbElit}nbElit in the Biased Fitness (7).

Formalization Note. The number λ\lambdaλ of removals is called nOff in Lean. The hypothesis nbElit+λ≤∣P∣\mathit{nbElit} + \lambda \le |P|nbElit+λ≤∣P∣ is not written in the Proposition; it comes from the paper's setting (Section 4.6: a subpopulation of μ+λ\mu + \lambdaμ+λ individuals is reduced to μ\muμ; Table 1: nbElit=el×μ\mathit{nbElit} = el \times \munbElit=el×μ with el∈[0,1]el \in [0, 1]el∈[0,1]), 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 PPP (for the infeasible subpopulation it is the incumbent feasible solution); JJJ may itself be the best solution.

Preamble
import Mathlib
import Definitions.Def_VidalHGS_Elitism_SurvivorSelection
Formal statement
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
Source
Vidal, Crainic, Gendreau, Lahrichi and Rei, A Hybrid Genetic Algorithm for Multi-Depot and Periodic Vehicle Routing Problems, CIRRELT-2010-34 (July 2010), pp. 16–17, Section 4.6, Proposition; size condition from p. 16 and Table 1, p. 20
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me