Optimization

• An optimization problem has the goal to find the best solution from a set of candidate solutions $\mathcal D$. That is, to find an $\hat x \in \mathcal D$ such that $$ \hat x = \text{argmax}_{x \in \mathcal{D}} f(x)$$ for a real-valued function $f : \mathcal D \to \mathbb{R}$.

• Example: linear optimization with a system $A\mathbf{x} = \mathbf{b}$ can be written as: $$ \text{argmin}_{\mathbf{x} \in \mathbb{R^n}} \|A\mathbf{x} - \mathbf{b}\|_2^2 $$
• In this case, $f := \|A\mathbf{x} - \mathbf{b}\|_2^2$ and $\mathcal{D} := \mathbb{R^n}$.

• Another example: combinatorial optimization. Assume a collection of $m$ objects with weights $w_0, \dots, w_{m-1}$ and a bag (Knapsack) to carry $M$ weight. Which objects should be taken to be as close to $M$ as possible?

• For the Knapsack problem: define a bitstring $\mathbf{b}:=[b_0, \dots, b_{m-1}]$ with $b_i \in \{0, 1\}$, and each $b_i$ indicating whether or not to take item $i$.
• Find a $\mathbf{b}$ with maximum total weight: $$ \text{argmax}_{\mathbf{b} \in \mathcal{D}} \, \sum_{i=0}^{m-1} b_i w_i. $$
• $\mathcal D$ is the set with bitstrings that yield weight less than $M$: $$\mathcal{D} := \left\{\mathbf{b}\,\, \bigg\vert \,\,\sum_{i=0}^{m-1} b_i w_i \leq M\right\}$$

• Last example: Travelling Salesman Problem. Assume $n$ cities, and distances given between each. What is the shortest possible round trip visiting all cities?

Genetic Algorithms

• Genetic Algorithms are a general way to solve optimization problems.
  • No restrictions on $f$ (e.g., smooth, linear, convex, differentiable, ...).
  • Genetic Algorithms are a metaphor, not really related to evolutionary biology.
• Basic idea: a subset of $\mathcal D$ is evolved through many generations.
  • The subset $\mathcal{G} := \{x_0, \dots, x_n\} \subseteq \mathcal D$ is called a population or generation.
  • Solutions $x_i \in \mathcal G$ are called members or chromosomes.
• The representation of a chromosome $x_i$ can be a vector, a bitstring (e.g. $[0, 1, 1, 1, 0, 0, 1, \dots ]$) or other datastructures.

• The iterative cycle of a genetic algorithm is:
  • Selection: choose $x_i \in \mathcal G$ that you want to keep.
  • Combination: create new $x_i$ by recombining favorable properties.
  • Mutation: (random) not-optimal perturbation to diversify the solutions.

• Selection of members $x_i$ is based on their fitness, a "relative importance" value based on the objective value $f(x_i)$. Existing ideas are:
  • truncation selection,
  • tournament selection,
  • and, roulette wheel selection.

• The operations of combination and mutation depend, generally, on the underlying datastructure. The most illustrative example is the bitstring:
  • Combination is achieved by merging two solutions $x_i$ and $x_j$ through a crossover operator $\mathcal C$. An example is 2-point crossover (see picture).
  • Chromosomes $x_i$ are mutated by flipping bits in the bitstring randomly.

Project outline

• Exercise 4.1 start with a GA library and a bitstring problem:
  
  • Use the coursebook chapter 4, and given example code.
  • Test problem: integer maximization.
  • Implement a GA concept called elitism.

• Exercise 4.2 is a project of choice:
  • Either Travelling Salesman Problem or a problem/project of your own. May be more technically, mathematically or application-oriented.
  • Discuss project proposal before starting it!
  • Teaming up is allowed.
• Small, individual presentation at the end of the course:
  • ~5 minutes, and just a couple of slides, really suffice.
  • Pick a technical topic that you liked, highlight a result, or explain what you have been working on.