p. 17, Section 4.6, proof of the Proposition — an elite individual has BF < 1
ProvedVidalHGS.Elitism.elite_biasedFitness_lt_oneelitismgenetic-algorithmp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a subpopulation and with . Let be among the best individuals of in terms of fitness, i.e. fewer than members of have strictly smaller cost than . Then
This is the second sentence of the proof of the elitism Proposition: elite individuals lie strictly outside the removal zone .
Formalization Note. All arithmetic is in . The hypotheses force and , so the denominator is positive. The condition is implicit in the paper (Table 1 gives , and the procedure acts on populations of more than individuals). The intermediate bound is kept in the paper's unsimplified form.
Preamble
import Mathlib import Definitions.Def_VidalHGS_Elitism_SurvivorSelection
Formal statement
namespace VidalHGS.Elitism
/-- Section 4.6, p. 17, proof of the Proposition: an individual `J` among the `nbElit` best
in terms of fitness has
`BF(J) ≤ (nbElit − 1)/(nbIndiv − 1) + 1 − nbElit/(nbIndiv − 1) < 1`,
provided `nbElit ≤ nbIndiv − 1`. -/
theorem elite_biasedFitness_lt_one {α : Type*} [DecidableEq α]
(c : α → ℝ) (Δ : Finset α → α → ℝ) (nbElit : ℕ) (P : Finset α) (J : α)
(hsize : nbElit + 1 ≤ P.card) (hJ : J ∈ P) (helite : IsElite c nbElit P J) :
biasedFitness c Δ nbElit P J ≤
((nbElit : ℝ) - 1) / ((P.card : ℝ) - 1) + 1 - (nbElit : ℝ) / ((P.card : ℝ) - 1) ∧
biasedFitness c Δ nbElit P J < 1 := 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), p. 17, Section 4.6, proof of the Proposition (second sentence)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.