遗传算法

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

基因 (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. 种群连续若干代最优解不再提升

Rust设计遗传算法

INFO

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

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

基因个体种群

rust

#[derive(Debug, Clone, PartialEq)]
/// 单个基因的真实值表示
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 {
    /// 个体的基因序列，代表一组待优化的变量
    pub genes: Vec<GeneValue>,
    /// 个体的适应度评分。`None` 表示该个体尚未被评估或基因已发生更改
    pub fitness: Option<f64>,
}

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

rust

#[derive(Debug, Clone)]
pub struct Population {
    /// 构成当前种群的个体列表
    pub individuals: Vec<Individual>,
}

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

下一步基于 有状态系统（Stateful System） 的设计范式，对遗传算法执行引擎进行架构设计。首先，核心结构体 GeneticAlgorithm 用于表示一个“运行中的遗传算法系统”，因此其设计需要同时包含两类要素： 构造输入（Constructor Input） 和 运行状态（Runtime State）

在构造阶段，应遵循最小构造原则（Minimal Constructor Principle），即构造函数仅接收那些“不可推导、不可默认”的外部输入。对于遗传算法而言，这些必要输入包括：配置参数 config（定义算法行为）和适应度函数 fitness_fn（定义优化目标）

而其他组件（如 population、generation、stats、rng）属于运行状态，可以根据配置进行初始化，并在算法执行过程中不断演化与更新，因此不应作为构造函数的输入参数。

遗传算法执行引擎遗传算法流程

rust

pub struct GeneticAlgorithm<F>
where
    F: Fn(&[GeneValue]) -> f64 + Sync,
{
    /// 遗传算法的运行配置参数
    pub config: GaConfig,
    /// 适应度评估函数（闭包）。用于计算每个个体的优劣程度
    pub fitness_fn: F,
    /// 当前代的种群状态
    pub population: Population,
    /// 当前已演化的代数（从 `0` 开始计数）
    pub generation: usize,
    /// 算法运行过程中的统计信息（如历代最优适应度、平均适应度等）
    pub stats: RunStats,
    /// 内部使用的标准随机数生成器
    rng: StdRng,
}

impl<F> GeneticAlgorithm<F> 
{
	pub fn new(config: GaConfig, fitness_fn: F) -> Result<Self, GaError> {
		config.validate()?;
		let rng = build_rng(config.random_seed);
	
		Ok(Self {
			config,
			fitness_fn,
			population: Population::empty(),
			generation: 0,
			stats: RunStats::default(),
			rng,
		})
	}	
}

rust

// 在遗传算法执行引擎里实现遗传算法流程
impl<F> GeneticAlgorithm<F>
where
    F: Fn(&[GeneValue]) -> f64 + Sync,
{
	/// 随机初始化初代种群（第 0 代）
	///
    /// 新生成的个体默认没有适应度（`fitness` 为 `None`）
	pub fn initialize_population(&mut self) -> Result<(), GaError>{}
	
	/// 对当前种群中的所有个体执行适应度评估
    ///
    /// 该方法会并行遍历 `population` 中的每一个个体，将其基因序列提取并传递给
    /// 用户定义的 `fitness_fn`，计算结果会被写回个体的 `fitness` 字段中
	pub fn evaluate_population(&mut self){}
	
	/// 根据配置的选择策略，从当前种群中挑选父代
    ///
    /// 返回的父代列表将被完全克隆，准备用于后续的交叉繁育
	pub fn select_parents(&mut self) -> Vec<Individual>{}
	
	/// 对选出的父代执行交叉操作，生成子代
	pub fn crossover(&mut self, parents: &[Individual]) -> Vec<Individual>{}
	
	/// 对交叉生成的子代群体执行变异操作
    ///
    /// 变异是原地（in-place）发生的。如果个体的基因发生了变异，其适应度将被重置为 `None`
    pub fn mutate(&mut self, offspring: &mut [Individual]){}
	
	/// 步进执行一个完整的世代演化（Generation）
    ///
    /// 此方法封装了遗传算法单次迭代的核心流水线：
    /// 1. 选择
    /// 2. 交叉
    /// 3. 变异
    /// 4. 评估种群个体
	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(())
    }	
    
    /// 启动并自动运行遗传算法，直到满足停止条件
	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)
	}
}

部分Rust技术栈

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

遗传算法

遗传算法流程 ​

Rust设计遗传算法 ​

部分Rust技术栈 ​

遗传算法流程

Rust设计遗传算法

部分Rust技术栈