Knapsack problem in Scala using the MOEA Framework and Jenetics

JeneticsExample.scala

import java.util.function.{ Function => JFunction }

import scala.collection.JavaConverters

import com.github.beatngu13.gist.knapsack.KnapsackProblem.Capacity
import com.github.beatngu13.gist.knapsack.KnapsackProblem.Items
import com.github.beatngu13.gist.knapsack.KnapsackProblem.OptimalProfit
import com.github.beatngu13.gist.knapsack.KnapsackProblem.OptimalSolution
import io.jenetics.BitChromosome
import io.jenetics.BitGene
import io.jenetics.Genotype
import io.jenetics.engine.Codec
import io.jenetics.engine.Engine
import io.jenetics.engine.EvolutionResult
import io.jenetics.engine.Problem
import io.jenetics.util.ISeq

object JeneticsExample extends App {

  val engine = Engine.builder(new JeneticsExample()).build()
  val result = engine.stream().limit(100).collect(EvolutionResult.toBestPhenotype())
  val binary = result.getGenotype().getChromosome()
  val profit = result.getFitness()
  println("Solution " + binary + " => " + profit)
  println("Optimum  " + OptimalSolution + " => " + OptimalProfit)

}

class JeneticsExample extends Problem[ISeq[BitGene], BitGene, Integer] {

  def codec(): Codec[ISeq[BitGene], BitGene] = {
    Codec.of(
      // Encode: genotype factory to create new solutions.
      Genotype.of(BitChromosome.of(Items.size, 0.5)),
      // Decode: function that converts genotypes to problem domain values.
      (gt: Genotype[BitGene]) => gt.getChromosome().toSeq())
  }

  def fitness(): JFunction[ISeq[BitGene], Integer] = {
    (binary: ISeq[BitGene]) =>
      {
        var profit = 0
        var weight = 0

        // Reverse items since Jenetics' BitChromosome goes from LSB to MSB.
        for ((b, i) <- JavaConverters.iterableAsScalaIterable(binary) zip Items.reverse) {
          if (b.booleanValue()) {
            profit += i.profit
            weight += i.weight
          }
        }

        if (weight <= Capacity) profit else weight - Capacity
      }
  }

}

KnapsackProblem.scala

// Knapsack problem based on P07 from https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html.
object KnapsackProblem {

  case class Item(profit: Int, weight: Int)

  private val Profits = List(
    135, 139, 149, 150, 156,
    163, 173, 184, 192, 201,
    210, 214, 221, 229, 240)

  private val Weights = List(
    70, 73, 77, 80, 82,
    87, 90, 94, 98, 106,
    110, 113, 115, 118, 120)

  val Items = for ((p, w) <- (Profits zip Weights)) yield Item(p, w)

  val Capacity = 750

  val OptimalProfit = 1458

  val OptimalSolution = "101010111000011"

}

MoeaFrameworkExample.Scala

import scala.collection.JavaConverters

import org.moeaframework.Executor
import org.moeaframework.core.Solution
import org.moeaframework.core.variable.EncodingUtils
import org.moeaframework.problem.AbstractProblem

import com.github.beatngu13.gist.knapsack.KnapsackProblem.Capacity
import com.github.beatngu13.gist.knapsack.KnapsackProblem.Items
import com.github.beatngu13.gist.knapsack.KnapsackProblem.OptimalProfit
import com.github.beatngu13.gist.knapsack.KnapsackProblem.OptimalSolution

object MoeaExample extends App {

  val result = new Executor()
    .withAlgorithm("GA")
    .withProblemClass(classOf[MoeaExample])
    .withMaxEvaluations(100)
    .run()

  // Iterable because multi-objective solutions are Pareto-optimal (i.e. trade-offs between the objectives).
  JavaConverters.iterableAsScalaIterable(result)
    .foreach(solution => {
      val binary = solution.getVariable(0)
      val profit = -solution.getObjective(0)
      println("Solution " + binary.toString + " => " + profit.toInt)
      println("Optimum  " + OptimalSolution + " => " + OptimalProfit)
    })

}

// 1 decision variable (item in/out), 1 objective (profit sum), 1 constraint (weight capacity).
class MoeaExample extends AbstractProblem(1, 1, 1) {

  def evaluate(solution: Solution): Unit = {
    // Get current solution as a binary string.
    val binary = EncodingUtils.getBinary(solution.getVariable(0))
    var profit = 0.0
    var weight = 0.0

    // For each present item, sum up the profits and weights.
    for ((b, i) <- (binary zip Items)) {
      if (b) {
        profit += i.profit
        weight += i.weight
      }
    }

    // Invert profit as MOEA tries to minimize, not maximize.
    solution.setObjective(0, -profit)
    // If weight is OK, constraint is 0.0, otherwise the distance to the boundary.
    solution.setConstraint(0, if (weight <= Capacity) 0.0 else weight - Capacity)
  }

  def newSolution: Solution = {
    // Create a new solution with 1 decision variable (as binary string), 1 objective, 1 constraint.
    val solution = new Solution(1, 1, 1)
    solution.setVariable(0, EncodingUtils.newBinary(Items.size))
    solution
  }

}