Example: The Multi-Objective Knapsack Problem

The multi-objective knapsack problem is a classic example in optimization where we aim to select items, each with its own benefits and costs, subject to certain constraints_fn (e.g., weight capacity). In the multi-objective version, we want to optimize more than one objective function simultaneously—often, maximizing multiple benefits or qualities at once.

Mathematical Formulation

Suppose we have \(n\) items. Each item \(i\) has: - A profit \(p_i\). - A quality \(q_i\). - A weight \(w_i\).

Let \((x_i)\) be a binary decision variable where \(x_i = 1\) if item \(i\) is selected and \(x_i = 0\) otherwise. We define a knapsack capacity \(C\). A common multi-objective formulation for this problem is:

\[ \begin{aligned} &\text{Maximize} && f_1(x) = \sum_{i=1}^{n} p_i x_i \\ &\text{Maximize} && f_2(x) = \sum_{i=1}^{n} q_i x_i \\ &\text{subject to} && \sum_{i=1}^{n} w_i x_i \leq C,\\ & && x_i \in \{0, 1\}, \quad i = 1,\dots,n. \end{aligned} \]

RustPython

use ndarray::{Array1, Array2, Axis, stack, Ix1, Ix2};
use ordered_float::OrderedFloat;
use std::collections::HashSet;

use moors::{
    algorithms::{Nsga2, Nsga2Builder},
    duplicates::ExactDuplicatesCleaner,
    operators::{BitFlipMutation, RandomSamplingBinary, SinglePointBinaryCrossover},
    genetic::Population
};

// problem data
const PROFITS: [f64; 5] = [2.0, 3.0, 6.0, 1.0, 4.0];
const QUALITIES: [f64; 5] = [5.0, 2.0, 1.0, 6.0, 4.0];
const WEIGHTS: [f64; 5] = [2.0, 3.0, 6.0, 2.0, 3.0];
const CAPACITY: f64 = 7.0;

fn fitness_knapsack(populationulation_genes: &Array2<f64>) -> Array2<f64> {
    // Calculate total profit
    let profits_arr = Array1::from_vec(PROFITS.to_vec());
    let profit_sum = populationulation_genes.dot(&profits_arr);

    // Calculate total quality
    let qualities_arr = Array1::from_vec(QUALITIES.to_vec());
    let quality_sum = populationulation_genes.dot(&qualities_arr);

    // We want to maximize profit and quality,
    // so in moors we minimize the negative values
    stack(Axis(1), &[(-&profit_sum).view(), (-&quality_sum).view()]).expect("stack failed")
}

fn constraints_knapsack(populationulation_genes: &Array2<f64>) -> Array1<f64> {
    // Calculate total weight
    let weights_arr = Array1::from_vec(WEIGHTS.to_vec());
    // Inequality constraint: weight_sum <= capacity
    populationulation_genes.dot(&weights_arr) - CAPACITY
}

// NOTE: The clone is only needed for the notebook source of this file. Also, most of the cases
// you don't need to specify the Population<Ix2, Ix1> signature
let population: Population<Ix2, Ix1> = {
    let mut algorithm = Nsga2Builder::default()
        .fitness_fn(fitness_knapsack)
        .constraints_fn(constraints_knapsack)
        .sampler(RandomSamplingBinary)
        .crossover(SinglePointBinaryCrossover)
        .mutation(BitFlipMutation::new(0.5))
        .duplicates_cleaner(ExactDuplicatesCleaner)
        .num_vars(5)
        .population_size(16)
        .num_offsprings(16)
        .num_iterations(10)
        .mutation_rate(0.1)
        .crossover_rate(0.9)
        .keep_infeasible(false)
        .build()
        .unwrap();

    algorithm.run().expect("NSGA2 run failed");

    let population = algorithm.population().expect("populationulation should have been initialized");
    population.clone()
};

Warning: Only 15 offspring were generated out of the desired 16.

// Get genes
>>> population.genes
[[1.0, 0.0, 0.0, 1.0, 1.0],
 [1.0, 1.0, 0.0, 1.0, 0.0],
 [0.0, 1.0, 0.0, 0.0, 1.0],
 [1.0, 0.0, 0.0, 0.0, 1.0],
 [1.0, 0.0, 0.0, 1.0, 0.0],
 [0.0, 0.0, 0.0, 1.0, 1.0],
 [0.0, 0.0, 1.0, 0.0, 0.0],
 [1.0, 1.0, 0.0, 0.0, 0.0],
 [0.0, 1.0, 0.0, 1.0, 0.0],
 [0.0, 0.0, 0.0, 1.0, 0.0],
 [0.0, 0.0, 0.0, 0.0, 1.0],
 [1.0, 0.0, 0.0, 0.0, 0.0],
 [0.0, 1.0, 0.0, 0.0, 0.0],
 [0.0, 0.0, 0.0, 0.0, 0.0]], shape=[14, 5], strides=[5, 1], layout=Cc (0x5), const ndim=2

// Get fitness
>>> population.fitness
[[-7.0, -15.0],
 [-6.0, -13.0],
 [-7.0, -6.0],
 [-6.0, -9.0],
 [-3.0, -11.0],
 [-5.0, -10.0],
 [-6.0, -1.0],
 [-5.0, -7.0],
 [-4.0, -8.0],
 [-1.0, -6.0],
 [-4.0, -4.0],
 [-2.0, -5.0],
 [-3.0, -2.0],
 [-0.0, -0.0]], shape=[14, 2], strides=[2, 1], layout=Cc (0x5), const ndim=2

// Get constraints
>>> population.constraints
[0.0, 0.0, -1.0, -2.0, -3.0, -2.0, -1.0, -2.0, -2.0, -5.0, -4.0, -5.0, -4.0, -7.0], shape=[14], strides=[1], layout=CFcf (0xf), const ndim=1

// Get rank (for Nsga2)
>>> population.constraints
[0.0, 0.0, -1.0, -2.0, -3.0, -2.0, -1.0, -2.0, -2.0, -5.0, -4.0, -5.0, -4.0, -7.0], shape=[14], strides=[1], layout=CFcf (0xf), const ndim=1

Note that in this example there is just one individual with rank 0, i.e Pareto optimal. Algorithms in moors store all individuals with rank 0 in a special attribute best

>>> let best = population.best();
>>> best
Population { genes: [[1.0, 0.0, 0.0, 1.0, 1.0]], shape=[1, 5], strides=[5, 1], layout=CFcf (0xf), const ndim=2, fitness: [[-7.0, -15.0]], shape=[1, 2], strides=[2, 1], layout=CFcf (0xf), const ndim=2, constraints: [0.0], shape=[1], strides=[1], layout=CFcf (0xf), const ndim=1, rank: Some([0], shape=[1], strides=[1], layout=CFcf (0xf), const ndim=1), survival_score: Some([inf], shape=[1], strides=[1], layout=CFcf (0xf), const ndim=1), constraint_violation_totals: Some([0.0], shape=[1], strides=[1], layout=CFcf (0xf), const ndim=1) }

// Get the best individual (just 1 in this example)
>>> best.get(0)
Individual { genes: [1.0, 0.0, 0.0, 1.0, 1.0], shape=[5], strides=[1], layout=CFcf (0xf), const ndim=1, fitness: [-7.0, -15.0], shape=[2], strides=[1], layout=CFcf (0xf), const ndim=1, constraints: 0.0, shape=[], strides=[], layout=CFcf (0xf), const ndim=0, rank: Some(0), survival_score: Some(inf), constraint_violation_totals: Some(0.0) }

import numpy as np

from pymoors import (
    Nsga2,
    RandomSamplingBinary,
    BitFlipMutation,
    SinglePointBinaryCrossover,
    ExactDuplicatesCleaner,
)
from pymoors.typing import TwoDArray


PROFITS = np.array([2, 3, 6, 1, 4])
QUALITIES = np.array([5, 2, 1, 6, 4])
WEIGHTS = np.array([2, 3, 6, 2, 3])
CAPACITY = 7


def knapsack_fitness(genes: TwoDArray) -> TwoDArray:
    # Calculate total profit
    profit_sum = np.sum(PROFITS * genes, axis=1, keepdims=True)
    # Calculate total quality
    quality_sum = np.sum(QUALITIES * genes, axis=1, keepdims=True)

    # We want to maximize profit and quality,
    # so in pymoors we minimize the negative values
    f1 = -profit_sum
    f2 = -quality_sum
    return np.column_stack([f1, f2])


def knapsack_constraint(genes: TwoDArray) -> TwoDArray:
    # Calculate total weight
    weight_sum = np.sum(WEIGHTS * genes, axis=1, keepdims=True)
    # Inequality constraint: weight_sum <= capacity
    return weight_sum - CAPACITY


algorithm = Nsga2(
    sampler=RandomSamplingBinary(),
    crossover=SinglePointBinaryCrossover(),
    mutation=BitFlipMutation(gene_mutation_rate=0.5),
    fitness_fn=knapsack_fitness,
    constraints_fn=knapsack_constraint,
    duplicates_cleaner=ExactDuplicatesCleaner(),
    num_vars=5,
    population_size=16,
    num_offsprings=16,
    num_iterations=10,
    mutation_rate=0.1,
    crossover_rate=0.9,
    keep_infeasible=False,
    verbose=False,
)

algorithm.run()

In this small example, the algorithm finds a single solution on the Pareto front: selecting the items (A, D, E), with a profit of 7 and a quality of 15. This means there is no other combination that can match or exceed both objectives without exceeding the knapsack capacity (7).

Once the algorithm finishes, it stores a population attribute that contains all the individuals evaluated during the search.

>>> population = algorithm.population
# Get genes
>>> population.genes
array([[1., 0., 0., 1., 1.],
       [1., 1., 0., 1., 0.],
       [0., 1., 0., 0., 1.],
       [1., 0., 0., 0., 1.],
       [1., 0., 0., 1., 0.],
       [0., 0., 0., 1., 1.],
       [0., 0., 1., 0., 0.],
       [1., 1., 0., 0., 0.],
       [0., 1., 0., 1., 0.],
       [1., 0., 0., 0., 0.],
       [0., 0., 0., 0., 1.],
       [0., 0., 0., 1., 0.],
       [0., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0.]])

# Get fitness
>>> population.fitness
array([[ -7., -15.],
       [ -6., -13.],
       [ -7.,  -6.],
       [ -6.,  -9.],
       [ -3., -11.],
       [ -5., -10.],
       [ -6.,  -1.],
       [ -5.,  -7.],
       [ -4.,  -8.],
       [ -2.,  -5.],
       [ -4.,  -4.],
       [ -1.,  -6.],
       [ -3.,  -2.],
       [ -0.,  -0.]])

# Get constraints
>>> population.constraints
array([[ 0.],
       [ 0.],
       [-1.],
       [-2.],
       [-3.],
       [-2.],
       [-1.],
       [-2.],
       [-2.],
       [-5.],
       [-4.],
       [-5.],
       [-4.],
       [-7.]])

# Get rank (for Nsga2)
>>> population.rank
array([0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6], dtype=uint64)

>>> best = population.best
>>> best
[<pymoors.schemas.Individual at 0x1c6699386e0>]

>>> best[0].genes
array([1., 0., 0., 1., 1.])

>>> best[0].fitness
array([ -7., -15.])

ℹ️ Note – Population Size and Duplicates

Note that although the specified population_size was 16, the final population ended up being 13 individuals, of which 1 had rank = 0. This is because we used the keep_infeasible=False argument, removing any individual that did not satisfy the constraints_fn (in this case, the weight constraint). We also used a duplicate remover called ExactDuplicatesCleaner that eliminates all exact duplicates—meaning whenever genes1 == genes2 in every component.

💡 Tip – Variable Types in pymoors

In pymoors, there is no strict enforcement of whether variables are integer, binary, or real. The core Rust implementation works with f64 ndarrays. To preserve a specific variable type—binary, integer, or real—you must ensure that the genetic operators themselves maintain it.

It is the user's responsibility to choose the appropriate genetic operators for the variable type in question. In the knapsack example, we use binary-style genetic operators, which is why the solutions are arrays of 0 s and 1 s.

Info

Note that although the specified population_size was 16, the final population ended up being 13 individuals, of which 1 had rank = 0. This is because we used the keep_infeasible argument was set in false, removing any individual that did not satisfy the constraints_fn (in this case, the weight constraint). We also used a duplicate remover called ExactDuplicatesCleaner that eliminates all exact duplicates—meaning whenever genes1 == genes2 in every component.

💡 Tip – Variable Types

In pymoors, there is no strict enforcement of whether variables are integer, binary, or real. The core Rust implementation works with f64 ndarrays. To preserve a specific variable type—binary, integer, or real—you must ensure that the genetic operators themselves maintain it.

It is the user's responsibility to choose the appropriate genetic operators for the variable type in question. In the knapsack example, we use binary-style genetic operators, which is why the solutions are arrays of 0 s and 1 s.