遗传算法

介绍遗传算法之前，先将与遗传相关的生物学概念和计算机中的数据结构对应起来，方便之后进一步进行建模

基因 (Gene)：问题的一个参数或变量。比如一个浮点数 3.14，或者一个布尔值 true
染色体/个体 (Chromosome/Individual)：问题的一个可能解。通常由一串基因组成，比如一个数组 [1.2, 3.4, 5.6]。个体数组中元素的类型由其中每个基因的类型决定
种群 (Population)：一组候选解的集合。每次迭代时维护的多个个体的集合。比如一个多维数组 [[1.2, 3.4, 5.6], [1.1, 3.3, 5.2], [1.0, 3.0, 5.0]]
适应度 (Fitness)：一个评估函数 (Objective Function) 的返回值。用来衡量这个解有多“好”。适应度越高，个体存活并繁衍后代的概率就越大

遗传算法流程

初始化种群：随机生成population_size个个体 （Initialize Population）
评估适应度：对种群中的每个个体进行适应度评估 （Evaluate Fitness）
选择：根据适应度从当前种群中挑选出优秀个体作为父母，适应度高个体更大概率被选入成为父母 （Select）
交叉：被选中的父母的基因进行重新组合生成新的孩子 （Crossover）
变异：随机改变生成的孩子个体上的某些基因 （Mutate）
停止：如果满足以下三个条件之一，算法停止并输出当前最好的个体；否则，用新生成的孩子替换老一代种群，回到第 2 步继续循环）（Stop）
1. 达到了预设的最大迭代次数
2. 找到了满足预期适应度的解
3. 种群连续若干代最优解不再提升

遗传算法编程

INFO

完整代码参考基于Rust重写的遗传算法库genetic-algorithm-rust（目前还在完善...）

数据层

对遗传算法中的使用的数据进行自底向上式的分层建模，最底层是基因类；上面一层是个体类（具有适应度属性）；最顶层是种群类

基因个体种群

rust

#[derive(Debug, Clone, PartialEq)]
/// Runtime representation of a typed gene value.
pub enum GeneValue {
    Isize(isize),
    I8(i8),
    I16(i16),
    I32(i32),
    I64(i64),
    Usize(usize),
    U8(u8),
    U16(u16),
    U32(u32),
    U64(u64),
    F32(f32),
    F64(f64),
}

rust

#[derive(Debug, Clone, PartialEq)]
pub struct Individual {
    /// Chromosome values.
    pub genes: Vec<GeneValue>,
    /// Fitness score, present after evaluation.
    pub fitness: Option<f64>,
}

impl Individual {
    pub fn new(genes: Vec<GeneValue>) -> Self {
        Self {
            genes,
            fitness: None,
        }
    }
}

rust

#[derive(Debug, Clone)]
pub struct Population {
    /// Individuals in the current population.
    pub individuals: Vec<Individual>,
}

impl Population {
    pub fn new(individuals: Vec<Individual>) -> Self {
        Self { individuals }
    }
}

算子层

对遗传算法中的操作算子进行函数式编程，现有算子设计主要有两层，执行引擎内部算子和执行引擎外部算子，不管是内部还是外部算子，它们都是对数据层的内容进行操作，有关执行引擎的介绍详见执行引擎层

执行引擎内部算子执行引擎外部算子

rust

/// Selects parent individuals according to the configured strategy.
pub fn select_parents(
    population: &Population,
    selection_type: &SelectionType,
    num_parents: usize,
    rng: &mut impl Rng,
) -> Vec<Individual> {}

/// Produces offspring from selected parents using the configured crossover operator.
pub fn crossover(
    parents: &[Individual],
    crossover_type: &CrossoverType,
    crossover_probability: f64,
    offspring_count: usize,
    rng: &mut impl Rng,
) -> Vec<Individual> {}

/// Applies mutation to offspring individuals in-place.
pub fn mutate(
    individuals: &mut [Individual],
    config: &EngineConfig,
    mutation_type: &MutationType,
    mutation_probability: f64,
    rng: &mut impl Rng,
) {}

/// Evaluates whether GA execution should stop at the current state.
pub fn should_stop(
    condition: &StopCondition,
    current_generation: usize,
    best_fitness: f64,
    stats: &RunStats,
    max_generations: usize,
) -> bool {}

rust

/// Migrates top individuals between islands according to the configured topology.
pub fn migrate<F>(
    islands: &mut [EngineKernel<F>],
    migration_type: &MigrationType,
    migration_count: usize,
) where
    F: Fn(&[GeneValue]) -> f64 + Sync,
{}

执行引擎层

基于 有状态系统（Stateful System） 的设计范式，对遗传算法执行引擎进行架构建模。系统在启动阶段根据外部配置完成初始化，一旦进入运行状态，便以内部状态为驱动核心，通过迭代演化机制持续推进计算过程，直至满足终止条件后停止执行

在构造引擎阶段，应遵循最小构造原则（Minimal Constructor Principle），即构造函数仅接收那些“不可推导、不可默认”的外部输入。对于遗传算法而言，这些必要输入包括：配置参数 config（定义算法行为）和适应度函数 fitness_fn（定义优化目标）。而其他组件（如 population、generation、stats、rng）属于运行状态，可以根据配置进行初始化，并在算法执行过程中不断演化与更新，因此不应作为构造函数的输入参数

遗传算法执行引擎

rust

/// Single Island execution kernel.
pub struct EngineKernel<F>
where
    F: Fn(&[GeneValue]) -> f64 + Sync,
{
    pub config: EngineConfig,
    pub fitness_fn: F,
    pub population: Population,
    pub generation: usize,
    pub stats: RunStats,
    rng: StdRng,
}

impl<F> EngineKernel<F>
where
    F: Fn(&[GeneValue]) -> f64 + Sync,
{
    pub fn new(config: EngineConfig, fitness_fn: F) -> Result<Self, GaError> {
        config.validate()?;
        let rng = Self::build_rng(config.random_seed);

        Ok(Self {
            config,
            fitness_fn,
            population: Population::empty(),
            generation: 0,
            stats: RunStats::default(),
            rng,
        })
    }
}

在执行引擎中，可以实现遗传算法流程方法：首先对种群进行初始化；随后在每一代中对个体进行适应度评估，并基于适应度执行选择、交叉和变异操作以生成新一代种群；该过程不断迭代，直至满足终止条件

遗传算法流程

rust

impl<F> EngineKernel<F>
where
    F: Fn(&[GeneValue]) -> f64 + Sync,
{
	/// Initializes the first population by sampling genes.
	pub fn initialize_population(&mut self) -> Result<(), GaError>{}
	
	/// Evaluates fitness for all individuals in parallel.
	pub fn evaluate_population(&mut self){}
	
	/// Selects parents using the configured selection policy.
	pub fn select_parents(&mut self) -> Vec<Individual>{}
	
	/// Produces offspring by applying crossover.
	pub fn crossover(&mut self, parents: &[Individual]) -> Vec<Individual>{}
	
	/// Applies mutation to offspring.
    pub fn mutate(&mut self, offspring: &mut [Individual]){}
	
	/// Advances one generation and records run statistics.
	pub fn next_generation(&mut self) -> Result<(), GaError> {
        let parents = self.select_parents();
        let mut offspring = self.crossover(&parents);
        self.mutate(&mut offspring);

        let mut next_individuals = Vec::new();
        next_individuals.extend(offspring);

        self.population = Population::new(next_individuals);
        self.evaluate_population();
        self.stats.record(&self.population)?;
        Ok(())
    }	
    
    /// Runs evolution until the configured stop condition is met.
	pub fn run(&mut self) -> Result<&RunStats, GaError> {
		self.initialize_population()?;
		self.evaluate_population();
		self.stats.record(&self.population)?;

		while !stop::should_stop(
			...
		) {
			self.next_generation()?;
			self.generation += 1;
		}
		Ok(&self.stats)
	}
}

岛屿模型编程

采用 岛屿模型（Island Model） 扩展遗传算法执行引擎，将整体种群划分为多个相互独立的子种群（islands），每个子种群由独立的遗传算法实例进行演化。同样岛屿模型执行层构造过程遵循最小构造原则

岛屿模型执行引擎

rust

/// Island model genetic algorithm.
pub struct IslandEngine<F>
where
    F: Fn(&[GeneValue]) -> f64 + Sync + Clone,
{
    pub num_islands: usize,
    pub migration_count: usize,
    pub migration_interval: usize,
    pub migration_type: MigrationType,
    pub islands: Vec<EngineKernel<F>>,
}

impl<F> IslandEngine<F>
where
    F: Fn(&[GeneValue]) -> f64 + Sync + Clone,
{
    /// Builds an island model from one shared island configuration.
    pub fn new(config: EngineConfig, fitness_fn: F) -> Result<Self, GaError> {
        if config.num_islands <= 1 {
            return Err(GaError::InvalidConfig(
                "num_islands must be greater than 1 for IslandEngine::new".into(),
            ));
        }

        config.validate()?;

        let mut islands = Vec::with_capacity(config.num_islands);
        for i in 0..config.num_islands {
            let mut config_mut = config.clone();
            config_mut.random_seed = config
                .random_seed
                .map(|seed| seed.wrapping_add(i as u64));
            islands.push(EngineKernel::new(config_mut, fitness_fn.clone())?);
        }

        Ok(Self {
            num_islands: config.num_islands,
            migration_count: config.migration_count,
            migration_interval: config.migration_interval,
            migration_type: config.migration_type.clone(),
            islands,
        })
    }
}

在执行引擎中可以实现岛屿模型的演化过程：各个岛屿周期性地进行个体迁移（migration），在不同引擎之间交换部分优秀个体，从而实现信息共享与多样性增强。该机制在保持各子系统独立探索能力的同时，通过跨岛通信有效避免早熟收敛，提高全局搜索性能

NSGA-II算法流程

初始化种群：随机生成 population_size 个个体，并计算每个个体的多目标函数值 （Initialize Population）
非支配排序：根据 Pareto 支配关系将种群划分为不同等级的非支配前沿（Non-dominated Sorting）
计算拥挤距离：计算同一前沿中各个个体的拥挤距离，用于衡量解的分布稀疏程度（Crowding Distance Calculation）
选择：按照“非支配等级优先、拥挤距离次之”的原则选择父代个体（Select）
交叉：将父代个体进行基因重组，生成新的子代 （Crossover）
变异：随机改变子代个体的部分基因 （Mutate）
父子代合并与精英保留：将父代与子代合并后重新排序，并保留最优的 population_size 个个体进入下一代 NSGA-II 专属（Elitist Replacement）
停止：若满足终止条件，则输出 Pareto 最优解集；否则继续循环 （Stop）

NSGA-II算法编程

对 NSGA-II 的编程实现建立在已有遗传算法框架的基础之上，整体扩展主要体现在 数据层、算子层和执行层 三个方面。

首先，在数据层中，为了支持多目标优化，个体 Individual 在原有基因与评估结果的基础上，新增了两个与 NSGA-II 直接相关的属性：非支配前沿等级 rank 和 拥挤距离 crowding_distance。其中，rank 用于表示个体所属的 Pareto 前沿层级，crowding_distance 用于衡量个体在目标空间中的稀疏程度。这两个属性共同构成了 NSGA-II 中个体优劣比较的核心依据。

其次，在算子层中，对原有遗传算法算子进行了面向多目标场景的扩展。一方面，在选择算子中新增了专属于 NSGA-II 的父代选择函数，通过二元锦标赛方式，按照“非支配等级优先，拥挤距离次之”的规则选择父代个体；另一方面，将原本零散的排序与优劣比较逻辑统一下沉到选择算子内部，使 NSGA-II 的个体比较方式能够在算子层中独立完成。除此之外，还新增了一个专用于 种群评估 的 NSGA-II 算子，用于计算种群中每个个体的非支配前沿等级和拥挤距离，并据此完成种群元数据更新。

最后，在执行层中，实现了完整的 NSGA-II 演化流程，包括：种群初始化、多目标函数评估、非支配排序、拥挤距离计算、基于 NSGA-II 规则的父代选择、交叉、变异、父子代合并以及环境选择等步骤。同时，在配置层面扩展了算法运行参数，使执行引擎能够区分单目标模式与多目标模式，从而在同一套遗传算法框架下兼容普通 GA 和 NSGA-II 两类优化任务。

NSGA-II算法增加逻辑

rust

//------------ 数据层 -------------
/// A candidate solution with genes and optional fitness.
#[derive(Debug, Clone, PartialEq)]
pub struct Individual {
    /// Chromosome values.
    pub genes: Vec<GeneValue>,
    /// Unified evaluation payload, present after evaluation.
    pub evaluation: Option<Evaluation>,
    /// Pareto front rank used by NSGA-II.
    pub rank: Option<usize>,
    /// Crowding distance used by NSGA-II.
    pub crowding_distance: Option<f64>,
}

//------------ 算子层 -------------
/// Recomputes NSGA-II ranks and crowding distances in-place.
pub fn assign_population_metadata(population: &mut Population) -> Result<Vec<Vec<usize>>, GaError> {}
/// Selects parents using NSGA-II binary tournament rules.
pub fn select_nsga2_parents(
    population: &Population,
    num_parents: usize,
    rng: &mut impl Rng,
) -> Result<Vec<Individual>, GaError> {}

//------------ ... -------------

部分Rust技术栈

不可变变量的借用&和可变变量的借用&mut，在不转移所有权的基础上是否修改借用变量的值：比如对种群中每个个体计算适应度时传入参数应该使用不可变借用，对种群进行交叉变异操作传入参数应该使用可变借用
利用编译器为类型自动实现接口（auto impl）#[derive(trait_1, trait_2, ...)]，比如为基因类、个体类和种群类自动实现接口；为类型实现方法
利用函数接口Fn实现要优化的目标函数的调用、使用Result进行错误处理以及使用Optional处理空值None...

遗传算法

遗传算法流程 ​

遗传算法编程 ​

数据层 ​

算子层 ​

执行引擎层 ​

岛屿模型编程 ​

NSGA-II算法流程 ​

NSGA-II算法编程 ​

部分Rust技术栈 ​

遗传算法流程

遗传算法编程

数据层

算子层

执行引擎层

岛屿模型编程

NSGA-II算法流程

NSGA-II算法编程

部分Rust技术栈