MOP (Many OPtimizations)

MOP 是一个灵活且模块化的框架，用于解决具有不同求解器的不同 NP 问题。通过其默认管道，您可以定义自己的自定义问题并选择任何受支持的求解器组合。

查看 这篇博客文章 了解更多详情或享受使用 在线沙盒 的乐趣。

示例

Binh 和 Korn 的定义和结果，一个具有两个硬约束和两个目标的 多目标问题。

图片来自 https://en.wikipedia.org/wiki/Test_functions_for_optimization#Test_functions_for_multi-objective_optimization。

// Binh T. and Korn U. (1997) MOBES: A Multiobjective Evolution Strategy for Constrained Optimization Problems

use core::cmp::Ordering;
use mop::{
  blocks::{
    gp::{new_defsb_o_ref, GpOperations, MpVec, MphDefinitionsBuilder, MphMpMph, MphOrRef, MphVec},
    objs::MinCstrsRslts,
    quality_comparator::ObjsAvg,
    ObjDirection, Pct,
  },
  facades::opt::OptFacade,
  solvers::genetic_algorithm::{
    operators::{
      crossover::MultiPoint, mating_selection::Tournament, mutation::RandomDomainAssignments,
    },
    GeneticAlgorithmParamsBuilder, Spea2,
  },
};

const RSLTS_NUM: usize = 200;

type Solution = [f64; 2];

fn f1(s: &Solution) -> f64 {
  4.0 * s[0].powi(2) + 4.0 * s[1].powi(2)
}

fn f2(s: &Solution) -> f64 {
  (s[0].powi(2) - 10.0 * s[0] + 25.0) + (s[1].powi(2) - 10.0 * s[1] + 25.0)
}

fn g1(s: &Solution) -> usize {
  let lhs = (s[0].powi(2) - 10.0 * s[0] + 25.0) + s[1].powi(2);
  match lhs.partial_cmp(&25.0) {
    Some(Ordering::Equal) | Some(Ordering::Less) => 0,
    _ => 1,
  }
}

fn g2(s: &Solution) -> usize {
  let lhs = (s[0].powi(2) - 16.0 * s[0] + 64.0) + (s[1].powi(2) + 6.0 * s[1] + 9.0);
  match lhs.partial_cmp(&7.7) {
    Some(Ordering::Equal) | Some(Ordering::Greater) => 0,
    _ => 1,
  }
}

fn print_result(result: MphOrRef<f64, Solution>) {
  let solution = result.solution();
  let objs = result.obj_rslts();
  let hcs = result.hard_cstr_rslts();
  println!("x0: {}, x1: {}", solution[0], solution[1]);
  println!("f1: {}, f2: {}", objs[0], objs[1]);
  println!("g1: {}, g2: {}", hcs[0], hcs[1]);
  println!();
}

#[tokio::main] // Or any other runtime
async fn main() -> Result<(), mop::blocks::Error> {
  // Problem definitions and results
  let mut mph = MphVec::with_capacity(
    MphDefinitionsBuilder::default()
      .domain([0.0..=5.0, 0.0..=3.0])
      .name("Binh and Korn")
      .push_hard_cstr(g1 as fn(&Solution) -> usize)
      .push_hard_cstr(g2 as fn(&Solution) -> usize)
      .push_obj((ObjDirection::Min, f1 as fn(&Solution) -> f64))
      .push_obj((ObjDirection::Min, f2 as fn(&Solution) -> f64))
      .build()?,
    RSLTS_NUM,
  );
  let (mph_defs, mut mph_rslts) = mph.parts_mut();

  // SPEA2 is an unconstrained solver but Binh and Korn is a constrained problem. To workaround
  // this incompatibility, our `mph` problem is converted to a `mp` problem by adding an objective
  // that minimizes all constraints violations.
  //
  // It is possible to define your own converstion procedure with any desired set of objectives.
  let mcr = MinCstrsRslts::from_gp_hcs(mph_defs);
  let mp_defs_ref = new_defsb_o_ref(mph_defs, mph_rslts).push_obj(&mcr as &_).build()?;
  let mut mp_ref = MpVec::with_random_solutions(mp_defs_ref, 100)?;

  // SPEA2 and overall genetic algorithm parameters are specified here.
  let spea2 = Spea2::new(
    Pct::from_percent(50),
    GeneticAlgorithmParamsBuilder::default()
      .crossover(MultiPoint::new(1, Pct::from_percent(70)))
      .mating_selection(Tournament::new(10, ObjsAvg))
      .mutation(RandomDomainAssignments::new(1, Pct::from_percent(30)))
      .build()?,
    &mp_ref,
    RSLTS_NUM,
  )?;

  // Generic criterias to inspect or stop the solving process.
  let of = OptFacade::new(50)
    .set_opt_hooks(())
    .set_quality_comparator(ObjsAvg)
    .set_stagnation(Pct::from_percent(2), 10)?
    .solve_problem_with(&mut mp_ref, spea2)
    .await?;

  // Transfers all solutions and objectives results of `mp` to `mph`.
  MphMpMph::transfer(&mph_defs, &mut mph_rslts, &mp_ref).await?;

  for (result_idx, result) in mph_rslts.iter().enumerate() {
    println!("***** Result #{} *****", result_idx + 1);
    print_result(result);
  }

  if let Some(best_idx) = of.curr_best_idx() {
    if let Some(result) = mph.rslts().get(best_idx) {
      println!("***** Best result *****");
      print_result(result);
    }
  }

  Ok(())
}

求解器

• SPEA2 (Zitzler 和 Thiele; SPEA2: 改进强度帕累托进化算法)

功能

• 默认启用 no_std
• 不同的存储（数组、Vec、切片等！）
• 模糊测试
• 无 unsafe

可选功能

• std
• 绑定（wasm-bindgen）
• 并发评估（futures）
• 反序列化/序列化（serde）
• 多维存储（ndsparse）