Genetic Algorithm in the browser with WebAssembly

This is the second post in my series on Rust and WebAssembly with Genetic Algorithms. In this post I'm going to build on the Genetic Algorithm I have implemented in Rust for the travelling salesman problem. I'll take the Rust implementation and make some adjustments that will allow it to be compiled to WebAssembly and interact with JavaScript and the browser. Then I'll develop a web application that will provide the user interface for running the Genetic Algorithm.

All the code for this post can be found here, and the live demo can be found here.

Photo by Vincent Burkhead on Unsplash

For this project I am using the Rust Webpack Template, which is designed to create monorepo style Web applications which are made up to JavaScript, HTML and Rust-generated WebAssembly. This template relies on a few tools; wasm-pack, npm, and setting up the WebAssembly compile target wasm32-unknown-unknown. More details on the setup can be found in the wasm-pack docs.

To start with, there are a number of changes that need to be made to the Rust code to support compilation to WebAssembly. The first thing is to add wasm-bindgen which will provide the means to define which parts of the Rust code will be exported and accessible from JavaScript. Adding the wasm-bindgen macro to the Simulation struct tells the library to build this as an export from the WebAssembly module, and adding the macro for the constructor allows the Simulation to be created using new Simulation() in JavaScript.

#[wasm_bindgen]
pub struct Simulation {
    population: Vec<Path>,
    city_list: Vec<City>,
    max_iterations: usize,
    crossover_rate: f64,
    mutation_rate: f64,
    survival_rate: f64,
}

#[wasm_bindgen]
impl Simulation {
    #[wasm_bindgen(constructor)]
    pub fn new(
        population_size: usize,
        city_list: String,
        max_iterations: usize,
        crossover_rate: f64,
        mutation_rate: f64,
        survival_rate: f64,
    ) -> Simulation {
        ...
    }
}

The Rust implementation uses the rand crate; luckily the rand crate provides support for the WebAssembly compile target using wasm-bindgen. This can be set in the projects Cargo.toml and as of version 0.7 works seamlessly.

[dependencies.rand]
version = "0.7"
features = [
  "wasm-bindgen",
]

Another useful crate is js_sys, which provides bindings to JavaScripts built-in objects and standard library. This is useful to marshal the results of the simulation to a format the calling JavaScript can understand. The return type of the Simulation's run method becomes Array from js_sys, and an array is constructed with the first entry being the ordered list of nodes visited for the solution, and the second the fitness.

pub fn run(&mut self) -> Array {

      ...

      let array = js_sys::Array::new();
      let order = js_sys::Array::new();
      for o in fittest.order {
          order.push(&JsValue::from(o as u32));
      }

      array.push(&order);
      array.push(&JsValue::from(fittest.fitness));

      array
  }

The web application for running the simulation is designed to be simple; it has inputs for the algorithm parameters, an area where the user may click to add cities, and a preset button which adds a list of default cities.

To prevent the main thread from being blocked while running the WebAssembly, the module is run in a Web Worker. The first step is to change the Webpack config provided by the Rust Webpack template to build the app and worker JavaScript files separately.

const appConfig = {
  target: 'web',
  entry: "./js/index.js",
  output: {
    path: dist,
    filename: '[name].[hash].js',
  },
  devServer: {
    contentBase: dist
  },
  plugins: [
    new HtmlWebpackPlugin({
      template: 'index.html',
      chunks: ['main']
    }),
  ],
  module: {
    rules: [
      {
        test: /\.css$/,
        use: [{ loader: 'style-loader' }, { loader: 'css-loader' }],
      }
    ]
  }
}

workerConfig = {
  target: 'webworker',
  entry: "./js/worker.js",
  output: {
    path: dist,
    filename: 'worker.js',
    globalObject: 'self'
  },
  devServer: {
    contentBase: dist
  },
  resolve: {
    extensions: [".js", ".wasm"]
  },
  plugins: [
    new WasmPackPlugin({
      crateDirectory: path.resolve(__dirname, "crate"),
    }),
  ]
}

module.exports = [appConfig, workerConfig]

The worker code is pretty simple. It imports the WebAssembly module, sets up a message handler to receive data from the main thread with the simulation parameters, runs the Simulation and posts a message back to the main thread with the results.

import("../crate/pkg").then(({ Simulation }) => {

  onmessage = function(msg) {
    const {
      iterations,
      citiesString,
      population_size,
      crossover,
      mutation,
      survival
    } = msg.data

    const s = new Simulation(
      iterations,
      citiesString,
      population_size,
      crossover,
      mutation,
      survival
    )

    const result = s.run()

    self.postMessage({
      path: result[0],
      fitness: result[1]
    })
  }
})

The application code includes a click handler that captures the users clicks inside the drawing space and adds a dot. The position of the dot is stored in data-x and data-y attributes on the DOM elements for passing to the WebAssembly code later.

const draw = document.getElementById('draw')

function addDot(x, y) {
  const dot = document.createElement('div')
  dot.className = 'dot'
  dot.style = `top: ${y}px; left: ${x}px;`
  dot.setAttribute('data-x', x)
  dot.setAttribute('data-y', y)
  draw.appendChild(dot)
}

draw.onclick = function(event) {
  addDot(event.offsetX, event.offsetY)
}

The main part of the application is the onsubmit function for the form. It is responsible for:

• capturing the input parameters for the simulation,
• extracting the co-ordinates of the cities that the user has drawn,
• sending a message to the worker with the parameters,
• setting a message handler to receive the results of the simulation run and draw the solution,
• drawing the cities on the solution canvas.

form.onsubmit = function(event) {
  event.preventDefault()
  const [iterations, population_size, crossover, mutation, survival] = event.target

  const cities = []
  const count = draw.children.length
  for (let c = 0; c < count; c++) {
    cities.push([
      draw.children[c].getAttribute('data-x'),
      draw.children[c].getAttribute('data-y')
    ])
  }

  const citiesString = cities.map(c => c.join(',')).join(';')

  worker.postMessage({
    iterations: parseInt(iterations.value, 10),
    citiesString,
    population_size: parseInt(population_size.value, 10),
    crossover: parseFloat(crossover.value),
    mutation: parseFloat(mutation.value),
    survival: parseFloat(survival.value)
  })

  worker.onmessage = function(msg) {
    const { path, fitness } = msg.data

    for (let p = 0; p < path.length - 1; p++) {
      const start = cities[path[p]]
      const end = cities[path[p+1]]

      ctx.beginPath()
      ctx.moveTo(start[0], start[1])
      ctx.lineTo(end[0], end[1])
      ctx.stroke()
    }
  }

  const ctx = canvas.getContext('2d')

  cities.map(c => {
    ctx.beginPath()
    ctx.arc(c[0], c[1], 2, 0, 2 * Math.PI, false)
    ctx.fillStyle = 'black'
    ctx.fill()
  })
}

The complete code can be found here, as well as the demo here.

In this article I have shown how to modify Rust code for compilation into WebAssembly and build a web application to use the WebAssembly module. In the last article in this series I will take about running this WebAssembly module outside of the browser with Wasmtime.