The Analytic Garden

Genetic Algorithms (GAs) are based on concepts borrowed from biology: selection, crossover, and mutation. Quantum Inspired Evolutionary Algorithms  (QIEAs) borrow concepts from both biology (selection and mutation) and  quantum mechanics (measurement, qubit-style probabilistic encoding, and simple gate-like updates. The key word here is "inspired", QIEAs are not quantum computing. They are quantum by analogy. The Knapsack Problem Suppose you have a container like a knapsack or maybe a shipping container. It has a fixed weight capacity, $C$. You also have a collection of objects. Each object has a weight and a value, $({w_i},{v_i})$. We wish to pack the knapsack with the most value we can without exceeding the weight capacity. We can express this as an optimization problem. \[\max \,\sum\limits_i {{v_i}{x_i}} \] \[\sum\limits_i {{w_i}{x_i} \leqslant C} \] \[{x_i} \in \{ 0,1\} \forall i\] ${x_i}$ is an indicator variable that can take on the value of 1 if the item is inclu...

Genetic Algorithms are a class of  global optimizers that are particularly effective in cases where the objective function is a black box or is discrete and derivatives can't easily be calculated.. They are also effective in cases where the objective function is smooth or convex. It's just that in these cases, the availability of derivatives often makes other methods such as gradient descent faster. Sometimes, the target function might have competing objectives, for example designing a treatment plan that maximizes efficacy while minimizing adverse side-effects. In cases like this, we often want not a local or even global optimal solution, but also what are the tradeoffs among the goals. In other words, there’s no single “best” solution. Instead, you want the Pareto set : solutions where you can’t improve any objective without worsening another. The Pareto set or Pareto front consists of the possible solutions that are not dominated by any other solution. What we mean by...