Add Simulated Annealing to website via WASM

[Glitchy-Tozier]

A great asset could be a website that employs some optimization-algorithm.

This pull request will focus on Simulated Annealing (SA) because (using https://github.com/argmin-rs/argmin,) it seems to allow compilation to WASM.

To-Do's

• [x] Add Rust function that can be called from JS
• [x] Implement SA into JS
• [x] Find way to make SA and the Genetic Algorithm coexist. Currently, the Code seems to be heavily geared towards the Genetic Algorithm, which makes it slightly difficult to implement SA
• [ ] ~Share one cache between all optimization-implementations (so far it'd be SA and a Genetic Algorithm) to speed up optimizing when repeating runs with only little modifications or switching between algorithms.~
• [x] Automatically evaluate&display the new, optimized layout's stats
• [x] UI-improvements and bug-fixes
  • [x] Give feedback when saving optimization parameters
  • [x] Properly highlight the config-textboxes' parameters
  • [x] Disable Save-buttons as long as nothing in the config-file has changed
  • [x] Autofocus textfields

[Glitchy-Tozier]

@dariogoetz What structure do you think would be opportune?

A homepage that links to those three options?

• Evaluate a layout (https://dariogoetz.github.io/keyboard_layout_optimizer/)
• Optimize a layout (new)
• Database (https://keyboard-layout-optimizer.herokuapp.com/)

Or should the first two options be part of the same website and the same workflow? That would make sense, too.

[dariogoetz]

@dariogoetz What structure do you think would be opportune?

A homepage that links to those three options?

* **Evaluate a layout** (https://dariogoetz.github.io/keyboard_layout_optimizer/)

* **Optimize a layout** (new)

* **Database** (https://keyboard-layout-optimizer.herokuapp.com/)

Or should the first two options be part of the same website and the same workflow? That would make sense, too.

Yes, I would prefer having the evaluation and optimization in the same webapp. They both rely on WASM and the exploration of the solutions could use the same frontend components.

[dariogoetz]

I have implemented the layout evaluation to be performed within a web worker thread. That way, the main (GUI) thread can keep running while heavy computation is being done.

This should enable us to have a long-running optimization running while still retaining a responsive page.

[dariogoetz]

I could not resist and try myself on this task (for the genevo-based optimization). I had to split the layout_optimization crate in order to manage the dependencies (some were not compatible with WASM, num_cpus, most notably).

I think that it would still be nice to have a simulated annealing version, though. It might be a better fit to the web setting, where computational resources are a little more scarce.

[Glitchy-Tozier]

I, too, think that adding Simulated Annealing! Sometime the next few days I'll start working on it. :)

Also, nice job!

[Glitchy-Tozier]

Do you know how to resolve those new conflicts with the new commits you pushed? Or should I just create a new PR?

[dariogoetz]

This should work.

[Glitchy-Tozier]

@dariogoetz To avoid repeated PR-conflicts, could you maybe focus on adding commits to this PR during the next few days? For example, you could implement some elegant method of choosing whether genOptimization() or saOptimization() should get called.

Additionally, you could work on skipping the "Under what name do you want to publish the layout"-pop-up, if the layout already exists. Maybe turn the publish-button into an "already published"-button that then triggers the alert/message.

---

What did you use to style this website? I saw you imported bootstrap and i recognize the styling as being bootstrap-like, but all the commands you use are different than what I'm used to.

[dariogoetz]

@dariogoetz To avoid repeated PR-conflicts, could you maybe focus on adding commits to this PR during the next few days? For example, you could implement some elegant method of choosing whether genOptimization() or saOptimization() should get called.

I will probably not commit much during the coming days.

Additionally, you could work on skipping the "Under what name do you want to publish the layout"-pop-up, if the layout already exists. Maybe turn the publish-button into an "already published"-button that then triggers the alert/message.

This would require a fetch call to the other website for each evaluated layout. I prefer not loading the other website with this; in particular as it "goes to sleep" when it is idle and it takes some time to wake up. As it currently is, the fetch call is only made when it is actually used.

What did you use to style this website? I saw you imported bootstrap and i recognize the styling as being bootstrap-like, but all the commands you use are different than what I'm used to.

I use bootstrap vue: https://bootstrap-vue.org

[Glitchy-Tozier]

Currently, it's feels difficult to implement Simulated Annealing, as the whole current structure of app.js and worker.js is based off of the genevo-optimization and its steps.

I'll try to figure out how to separate those two (app.js&html and whatever optimization we choose to perform)

That being said, I, too, might take it easy the next two days.

[Glitchy-Tozier]

This would require a fetch call to the other website for each evaluated layout. I prefer not loading the other website with this; in particular as it "goes to sleep" when it is idle and it takes some time to wake up. As it currently is, the fetch call is only made when it is actually used.

Doesn't this happen about once every few seconds at max? (after evaluation or after optimization is finished)

I use bootstrap vue: https://bootstrap-vue.org

Got it!

[Glitchy-Tozier]

Currently there are two errors:

1. the errors showing up in the checks. It seems to hate env.
2. some "can't sleep"-error when not supplying None as the starting temperature.

The second one probably is connected to that "Currently the --greedy-option is bugged"-warning, where a sleep(7) exists. I can remove that line. I'm not sure how to fix the first error though...

[Glitchy-Tozier]

Ok, so all that is needed to stop the error from occuring is commenting out this command:

let res = Executor::new(problem, solver, init_layout)
    // Optional: Attach a observer
    .add_observer(best_observer, ObserverMode::NewBest)
    .add_observer(iter_observer, iter_observer_mode)
    // Optional: Set maximum number of iterations (defaults to `std::u64::MAX`)
    .max_iters(params.max_iters)
    .run()
    .unwrap();

(Which turns it into this codeblock:)

/* let res = Executor::new(problem, solver, init_layout)
    // Optional: Attach a observer
    .add_observer(best_observer, ObserverMode::NewBest)
    .add_observer(iter_observer, iter_observer_mode)
    // Optional: Set maximum number of iterations (defaults to `std::u64::MAX`)
    .max_iters(params.max_iters)
    .run()
    .unwrap(); */

The reason why this might be caused by argmin itself is that even if we use the most simple setup I can think of, the error still rears its head: (Those are the simplified parts of the code)

struct AnnealingStruct {}

impl ArgminOp for AnnealingStruct {
    type Param = Vec<usize>;
    type Output = f64;
    type Hessian = ();
    type Jacobian = ();
    type Float = f64;

    /// Evaluate param (= the layout-vector).
    fn apply(&self, param: &Self::Param) -> Result<Self::Output, Error> {
        Ok(12.5)
    }

    /// Modify param (~the layout).
    fn modify(&self, param: &Self::Param, _temp: f64) -> Result<Self::Param, Error> {
        Ok(param.clone())
    }
}

/// Performs one run of Simulated Annealing, then returns the best layout found.
pub fn optimize(
    process_name: &str,
    params: &Parameters,
    layout_str: &str,
    fixed_characters: &str,
    layout_generator: &NeoLayoutGenerator,
    start_with_layout: bool,
    evaluator: &Evaluator,
    optional_init_temp: Option<f64>,
    log_everything: bool,
    result_cache: Option<Cache<f64>>,
) -> Layout {
    let pm = PermutationLayoutGenerator::new(layout_str, fixed_characters, layout_generator);
    // Get initial Layout.
    let init_layout = pm.generate_random();
    let init_temp = 13.6;

    let problem = AnnealingStruct {};
    // Create new SA solver with some parameters (see docs for details)
    // This essentially just prepares the SA solver. It is not run yet, nor does it know anything about the problem it is about to solve.
    let solver = SimulatedAnnealing::new(init_temp).unwrap();
    // Create and run the executor, which will apply the solver to the problem, given a starting point (`init_param`)
    let res = Executor::new(problem, solver, init_layout).run().unwrap();

    pm.generate_layout(&pm.generate_random())
}

Basically what I did is remove our observers, and all unnecessary code that was connected to problem, solver, and res.

[Glitchy-Tozier]

I also removed all unnecessary imports. Here's the full code:

use keyboard_layout::layout::Layout;
use keyboard_layout::layout_generator::NeoLayoutGenerator;
use layout_evaluation::evaluation::Evaluator;

use layout_optimization::common::{Cache, PermutationLayoutGenerator};

use anyhow::Result;
use serde::Deserialize;

use argmin::prelude::{ArgminOp, Error, Executor};
use argmin::solver::simulatedannealing::SimulatedAnnealing;

#[derive(Deserialize, Debug)]
pub struct Parameters {
    /// In each modification of the layout, swap this many key-pairs.
    pub key_switches: usize,

    // Parameters for the solver.
    /// Stop if there was no accepted solution after this many iterations
    pub stall_accepted: u64,

    // Parameters for the [Executor].
    /// Set maximum number of iterations (defaults to `std::u64::MAX`)
    pub max_iters: u64,
}

impl Default for Parameters {
    fn default() -> Self {
        Parameters {
            key_switches: 1,
            // Parameters for the solver.
            stall_accepted: 5000,
            // Parameters for the [Executor].
            max_iters: 100_000,
        }
    }
}

impl Parameters {
    pub fn from_yaml(filename: &str) -> Result<Self> {
        let f = std::fs::File::open(filename)?;
        Ok(serde_yaml::from_reader(f)?)
    }
}

struct AnnealingStruct {}

impl ArgminOp for AnnealingStruct {
    type Param = Vec<usize>;
    type Output = f64;
    type Hessian = ();
    type Jacobian = ();
    type Float = f64;

    /// Evaluate param (= the layout-vector).
    fn apply(&self, param: &Self::Param) -> Result<Self::Output, Error> {
        Ok(12.5)
    }

    /// Modify param (~the layout).
    fn modify(&self, param: &Self::Param, _temp: f64) -> Result<Self::Param, Error> {
        Ok(param.clone())
    }
}

/// Performs one run of Simulated Annealing, then returns the best layout found.
pub fn optimize(
    process_name: &str,
    params: &Parameters,
    layout_str: &str,
    fixed_characters: &str,
    layout_generator: &NeoLayoutGenerator,
    start_with_layout: bool,
    evaluator: &Evaluator,
    optional_init_temp: Option<f64>,
    log_everything: bool,
    result_cache: Option<Cache<f64>>,
) -> Layout {
    let pm = PermutationLayoutGenerator::new(layout_str, fixed_characters, layout_generator);
    // Get initial Layout.
    let init_layout = pm.generate_random();
    let init_temp = 13.6;

    let problem = AnnealingStruct {};
    // Create new SA solver with some parameters (see docs for details)
    // This essentially just prepares the SA solver. It is not run yet, nor does it know anything about the problem it is about to solve.
    let solver = SimulatedAnnealing::new(init_temp).unwrap();
    // Create and run the executor, which will apply the solver to the problem, given a starting point (`init_param`)
    let res = Executor::new(problem, solver, init_layout).run().unwrap();

    pm.generate_layout(&pm.generate_random())
}

[Glitchy-Tozier]

The problem seems to lie in this line:

        let total_time = if self.timer {
            Some(instant::Instant::now()) // Causes the error. If replaced by `None`, no errors occur.
        } else {
            None
        };

This line only runs if self.timer == true. The problem is that even setting that "field" to false still produces the error. I tried two different methods:

1. Using the built-in .timer(false)-method on the executor.
2. Hard-coding self.timer to always be false.

Neither method worked. Even this didn't work:

        let total_time = if false {
            Some(instant::Instant::now())
        } else {
            None
        };

Not sure what to do about this.

Another remark: instant::Instant::now() is being used. I don't know in what way it's different from std::time::Instant::now(). Unfortunately, using std::time::Instant::now() did not fix the issue.

[Glitchy-Tozier]

I think I may have found our solution!

I read a little bit into the instant::Instant::now()-thing, and it seems like switching out one feature for another in argmin's Cargo.toml seems to do the trick:

- instant = { version = "0.1", features = ["now"] }
+ instant = { version = "0.1", features = ["wasm-bindgen"] } # New, working solution.

(a small remark: here's what instant's Readme.md says about the feature "now": Note: The old feature, now, has been deprecated. instant::now() is always exported and the now feature flag no longer has any effect. It remains listed in Cargo.toml to avoid introducing breaking changes and may be removed in future versions.)

That could be turned into a pull-request, I think. I could do that, but I'd like to first hear your thoughts on this whole appearant fix.

[Glitchy-Tozier]

Also, do you know what this code does? (line 214 in executor.rs)

            if self.timer {
                total_time.map(|total_time| self.state.time(Some(total_time.elapsed())));
            }

I just can't figure out what that time()-function does... I can't find it anywhere, neither inside the project nor outside on the web.

[dariogoetz]

This sounds like good work in digging into the issue. I think filing a pull request that replaces the "now" feature with either one of "wasm-bindgen" or "stdweb" (I don't know exactly what the difference is; we use wasm-bindgen) or even go for enabling the "transitively" (as described in their readme) is a good move.

Regarding the .time(…) function, this is a setter method generated by a macro:

macro_rules! setter {
    ($name:ident, $type:ty, $doc:tt) => {
        #[doc=$doc]
        pub fn $name(&mut self, $name: $type) -> &mut Self {
            self.$name = $name;
            self
        }
    };
}

in the file src/core/iterstate.rs

[Glitchy-Tozier]

So...I found out another thing. Argmin has those lines in its Cargo.toml:

[features]
default = []
nalgebral = ["nalgebra"]
ndarrayl = ["ndarray", "ndarray-linalg", "ndarray-rand"]
visualizer = ["gnuplot"]
wasm-bindgen = ["instant/wasm-bindgen"]
stdweb = ["instant/stdweb"]

Meaning, that the fix existed from the beginning. All we had to do was use

argmin = { version = "0.4.7", features = ["wasm-bindgen"] }

instead of

argmin = "0.4.7"

Maybe a pull-request editing Argmin's Readme.md would be a good idea, as this feature isn't metioned anywhere.

[dariogoetz]

A great asset could be a website that employs some optimization-algorithm.

This pull request will focus on Simulated Annealing (SA) because (using https://github.com/argmin-rs/argmin,) it seems to allow compilation to WASM.

To-Do's

• [x] Add Rust function that can be called from JS
• [ ] Implement SA into JS
• [ ] Find way to make SA and the Genetic Algorithm coexist. Currently, the Code seems to be heavily geared towards the Genetic Algorithm, which makes it slightly difficult to implement SA
• [ ] Share one cache between all optimization-implementations (so far it'd be SA and a Genetic Algorithm) to speed up optimizing when repeating runs with only little modifications or switching between algorithms.
• [ ] Automatically evaluate&display the new, optimized layout's stats

• [ ] UI-improvements and bug-fixes

  • [ ] Give feedback when saving optimization parameters
  • [ ] By default, make the fixed-keys-textbox empty, but add a placeholder-text such as "abc.,"
  • [ ] Properly highlight the config-textboxes' parameters

I have some remarks regarding the todo list:

1. I would prefer to not have automatic evaluation of intermediate solutions. It would be okay for the optimization result, though.
2. The fixed keys should be kept as ",." by default. This is in line with the neo family layouts (at least those on the official web page). I also believe that this is, what most people look for. (I know that KOY and it's derivatives do not have it).
3. I had a look at styling the yaml textinput fields. This is, unfortunately, not trivial. There are some ways with overlaying transparent layers on top of each other, but I did not get it to work (maybe you have more luck, see https://css-tricks.com/creating-an-editable-textarea-that-supports-syntax-highlighted-code/)

[Glitchy-Tozier]

I would prefer to not have automatic evaluation of intermediate solutions. It would be okay for the optimization result, though.

I agree that intermediate layouts shouldn't (visually) be evaluated, at least it shouldn't use our current standard. That would flood the website with layouts that don't interest anyone.

The fixed keys should be kept as ",." by default. This is in line with the neo family layouts (at least those on the official web page). I also believe that this is, what most people look for. (I know that KOY and it's derivatives do not have it).

I still really dislike that thought, but I guess there's nothing I can do about it. I'll delete it from the list. Maybe after revisiting our optimization of .&, (at a later point in time), we can return to this topic.

[Glitchy-Tozier]

@dariogoetz Could you take a look at this? No of the usual commands (like Worker.terminate()) seem to work, even throw "someErrorMessage"; so I went ahead and tried produce a rust-panic if this.optCancel is true. The panic seems to stop the worker, the problem is, after hours of fighting, that I couldn't figure out how to actually get the value of this.optCancel into Rust. The callback-function that is supposed to return this.optCancel instead returns some JSValue(Promise). I couldn't find any way to extract the Promise out of JSValue.