nsga

nsga 是 NSGA-II (非支配排序遗传算法) 的有意见实现，一种多目标遗传优化算法。

该实现的焦点在于实用性，而不仅仅是优化纯数学函数。

示例

让我们定义一个示例问题

Given an array of integers and a value, find indices of the array elements
that sum up to the given value.

例如，给定一个数组

let a = vec![1, 5, 8, 0, 6, 4];

和一个值 19，解决方案可以是

vec![1, 0, 1, 0, 1, 1]; // 1 + 8 + 6 + 4 = 19

或

vec![0, 1, 1, 0, 1, 0]; // 5 + 8 + 6 = 19

当然，对于如此小的输入，我们不需要复杂的优化器，但当我们处理成千上万甚至数百万个元素时，任务就变得有些具挑战性。

解决方案候选

问题通过实现 Solution 特性来表示。让我们为我们的解决方案候选定义一个基结构

#[derive(Clone, Debug)]
struct Candidate {
  indices: Vec<isize>,
}

由于我们问题的解决方案是一个索引数组，我们可以在我们的结构体中简单地有一个 Vec<isize>。

变异

变异 是一种改变解决方案候选的操作。这是系统增加多样性和避免局部最优的方法。这与变异在真实生物系统进化中所起的作用非常相似。

变异高度依赖于问题，在我们的情况下，我们只是以一定的概率将索引从 0 翻转到 1，反之亦然。

fn mutate(&mut self) {
  let mut rng = thread_rng();

  for i in &mut self.indices {
    if rng.gen_ratio(MUTATION_ODDS.0, MUTATION_ODDS.1) {
      *i = if *i == 0 { 1 } else { 0 }
    }
  }
}

交叉

交叉 是一种操作，它将两个父候选者的“基因”混合。在我们的实现中，我们将两个父代都分成两半，并交换相应的部分。例如，给定两个父代

let a = vec![1, 1, 1, 1, 1, 1];
let b = vec![0, 0, 0, 0, 0, 0];

交叉后，这些将看起来像

vec![1, 1, 1, 0, 0, 0];
vec![0, 0, 0, 1, 1, 1];

fn crossover(&mut self, other: &mut Self) {
  let mut a = &mut self.indices;
  let mut b = &mut other.indices;

   // Use `a` for the longer vector:
   if b.len() > a.len() {
     a = &mut other.indices;
     b = &mut self.indices;
   }

   let a_mid = a.len() / 2;
   let b_mid = b.len() / 2;

   let b_back = &mut b[b_mid..];
   let a_back = &mut a[a_mid..][..b_back.len()];

   a_back.swap_with_slice(b_back);

   let a_len = a_mid + a_back.len();
   b.extend(a.drain(a_len..));
}

目标

为了指导优化器，我们需要实现 Objective 特性。唯一必须的方法是 Objective::value，它接受一个解决方案候选并返回其适应度值。这个值越低，特定的解决方案就越接近理想解决方案。

对于我们这个任务，我们将实现如下

fn value(&self, candidate: &Candidate) -> f64 {
  let res: f64 = candidate
                 .indices
                 .iter()
                 .enumerate()
                 .map(|(i, rec)| if *rec == 1 { self.items[i] } else { 0. })
                 .sum();

  let diff = (self.goal - res).abs();
  if diff < 0. {
    f64::MAX
  } else {
    diff
  }
}

基本上，它会计算在解中索引位被设置的所有值的总和，然后计算总和与目标值之间的差值，这是我们正在寻找的。

当前解的总和越接近我们正在寻找的值，差值就会越小，这正是我们所需要的，因为优化器总是试图找到函数的最小值。

早期终止

当特定目标值已知时，通过不必计算所有迭代步骤，可以显著加快优化过程。

例如，在我们的情况下，我们知道我们正在寻找的确切值，因此一旦我们足够接近期望值，我们就可以停止搜索。

fn good_enough(&self, val: f64) -> bool {
   val <= self.toleration
}

通过调整self.toleration值，我们可以使搜索尽可能精确。

元数据

我们需要向优化器提供一组额外的元参数。我们通过实现一个Meta特质来完成此操作。

Meta::population_size

种群大小是优化器使用的内部候选人池的大小。默认值为20，在大多数情况下，可以保持不变。

Meta::crossover_odds

此方法应返回应用交叉操作的概率。它通常应该相对较高，大约50%左右。

Meta::mutation_odds

此方法应返回应用变异操作的概率。它通常应该小于交叉值，大约20-30%左右。

Meta::random_solution

返回随机解决方案候选者的方法。在我们的例子中，我们将只返回索引的零向量。

fn random_solution(&mut self) -> Candidate {
  let indices: Vec<isize> = (0..self.records_length).map(|_| 0).collect();

  Candidate { indices }
}

Meta::objectives

此方法返回用于优化的目标向量。在我们的例子中，它将是我们SumObjective的一个实例。

fn objectives(&self) -> &Vec<Box<dyn Objective<Candidate>>> {
  vec![
    Box::new(SumObjective {
      goal: 19.,
      items: vec![1, 5, 8, 0, 6, 4],
      toleration: 0.0,
    }),
  ]
}

Meta::constraints

此方法返回用于优化的可选约束向量。在我们的小例子中，我们不需要约束。

多个目标

现在，能够针对一个目标进行优化是很好的，但NSGA-II是一种多目标优化算法，这意味着它可以在同一时间针对许多目标进行优化。其中一些甚至可能相互冲突！这些细节超出了本教程的范围，如果您想了解更多，请随时在维基百科上阅读。

let a = vec![1, 5, 8, 0, 6, 4];

let s1 = vec![1, 0, 1, 0, 1, 1]; // 1 + 8 + 6 + 4 = 19
let s2 = vec![0, 1, 1, 0, 1, 0]; // 5 + 8 + 6 = 19

pub struct OnesObjective {}

impl Objective<Candidate> for OnesObjective {
    fn value(&self, candidate: &Candidate) -> f64 {
        candidate.indices.iter().filter(|i| **i == 1).count() as f64
    }
}

fn objectives(&self) -> &Vec<Box<dyn Objective<Candidate>>> {
    vec![
        Box::new(SumObjective {
            goal: 19.,
            items: vec![1, 5, 8, 0, 6, 4],
            toleration: 0.0,
        }),
        Box::new(OnesObjective{}),
    ]
}