RapidSolve

此库提供了解决组合优化问题的元启发式框架。

概述

元启发式算法

以下元启发式算法包括：

• 局部搜索（具有几种邻域探索策略）
• 并行局部搜索（使用 rayon 并行探索邻域）
• 阈值接受
• 模拟退火
• 禁忌搜索（以及一个更快的 并行版本）

分层目标

框架支持 分层目标，即由多个线性组合构成的多个层次的目标。首先最小化第一层，只有当出现平局时才考虑下一层。这对于将硬约束建模为具有高优先级的软约束（通过违规度量）很有用，这样通常不可行的解也被认为是可行的。求解器首先最小化这些约束，直到违规为零，然后开始优化剩余的目标层次。

示例

例如，我们提供了一个使用 3-opt 邻域的简单 旅行商问题 (TSP) 的实现。

如何使用此库（逐步示例）

假设你有一个组合优化问题并定义了一个解类型。要运行局部搜索求解器，你需要执行以下四个步骤

1. 通过定义 Objective 和构建由这些指标组成的 LinearCombinations 的层次目标来定义你问题的 Indicators。
2. 定义你解决方案类型的修改。解决方案类型不应是可变的，而应返回一个修改后的克隆。
3. 实现局部搜索的 Neighborhood。
4. 初始化 LocalSearchSolver 并运行它。

我们通过一个简单（但完全是人为的）示例来演示这些步骤，其中解决方案类型由一个固定大小的整数向量组成。

struct Solution(Vec<i64>);

1. 定义你问题的 Objective。

对于本例，我们想要找到排列（即，0到10应恰好出现一次），其中相邻元素（循环）的平方差之和最小化。

因此，我们定义了两个 Indicators，即 PermutationViolation 和 SquaredDifference，并构建了一个层次目标，其中首先最小化 PermutationViolation，只有在平局时才考虑 SquaredDifference。

use rapid_solve::objective::{BaseValue, Indicator, Objective};

struct PermutationViolation;

impl Indicator<Solution> for PermutationViolation {
    fn evaluate(&self, solution: &Solution) -> BaseValue {
        let violation: i64 = (0..solution.0.len())
            .map(|i| (solution.0.iter().filter(|&n| *n == i as i64).count() as i64 - 1).abs())
            .sum();
        BaseValue::Integer(violation)
    }
    fn name(&self) -> String {
        String::from("PermutationViolation")
    }
}

struct SquaredDifference;

impl Indicator<Solution> for SquaredDifference {
    fn evaluate(&self, solution: &Solution) -> BaseValue {
        let squared_diff: i64 = (0..solution.0.len())
            .map(|i| (solution.0[i] - solution.0[(i + 1) % solution.0.len()]).pow(2))
            .sum();
        BaseValue::Integer(squared_diff)
    }
    fn name(&self) -> String {
        String::from("SquaredDifference")
    }
}

fn build_objective() -> Objective<Solution> {
    Objective::new_single_indicator_per_level(vec![
        Box::new(PermutationViolation),
        Box::new(SquaredDifference),
    ])
}

2. 定义你解决方案类型的修改。

在我们的示例中，我们使用了两种修改

• 将一个条目更改为一个介于0和10之间的数字。
• 交换两个条目。

解决方案类型不应是可变的，而应返回一个修改后的克隆。对于较大的解决方案类型，不可变数据结构 crate im 可能会增加性能。

impl Solution {
    fn change_entry(&self, index: usize, new_value: i64) -> Self {
        let mut new_values = self.0.clone();
        new_values[index] = new_value;
        Solution(new_values)
    }
    fn swap(&self, index1: usize, index2: usize) -> Self {
        let mut new_values = self.0.clone();
        new_values.swap(index1, index2);
        Solution(new_values)
    }
}

3. 实现 Neighborhood。

在我们的示例中，我们首先尝试更改所有条目，然后尝试所有交换。

use rapid_solve::heuristics::local_search::Neighborhood;

struct ChangeEntryThenSwapNeighborhood;

impl Neighborhood<Solution> for ChangeEntryThenSwapNeighborhood {
    fn neighbors_of<'a>(
        &'a self,
        solution: &'a Solution,
    ) -> Box<dyn Iterator<Item = Solution> + Send + Sync + 'a> {
        let change_entry = (0..solution.0.len()).flat_map(move |i| {
            (0..10).map(move |new_value| solution.change_entry(i, new_value))
        });
        let swap = (0..solution.0.len())
            .flat_map(move |i| (0..solution.0.len()).map(move |j| solution.swap(i, j)));
        Box::new(change_entry.chain(swap))
    }
}

4. 初始化 LocalSearchSolver 并运行它。

在示例中，只找到了局部最优解，这比全局最优解差。

use rapid_solve::heuristics::local_search::LocalSearchSolver;
use std::sync::Arc;

let objective = Arc::new(build_objective());
let neighborhood = Arc::new(ChangeEntryThenSwapNeighborhood);
let solver = LocalSearchSolver::initialize(neighborhood, objective);

let initial_solution = Solution(vec![0; 10]);

let evaluated_local_minimum = solver.solve(initial_solution);
assert_eq!(
    *evaluated_local_minimum.objective_value().as_vec(),
    vec![BaseValue::Integer(0), BaseValue::Integer(36)]
);
assert_eq!(
    *evaluated_local_minimum.solution().0,
    vec![1, 0, 2, 4, 5, 7, 9, 8, 6, 3]
);
// one global optimum is [0, 2, 4, 6, 8, 9, 7, 5, 3, 1] with a squared differences of 34.

对于更不人为的演示，请参阅 tsp-example。