8.4 Outro

8.4.1 Remarks


For any \(p\ge 1\), the search space type determines the problem class:

  • \(D\subseteq\mathbb{R}^p\)continuous optimisation

    In particular:
    • \(D=\mathbb{R}^p\) – continuous unconstrained
    • \(D=[a_1,b_1]\times\dots\times[a_n,b_n]\) – continuous with box constraints
    • constrained with \(k\) linear inequality constraints

      \(a_{1,1} x_1 + \dots + a_{1,p} x_p \le b_1\), …, \(a_{k,1} x_1 + \dots + a_{k,p} x_p \le b_k\)


However, there are other possibilities as well:

  • \(D\subseteq\mathbb{Z}^p\) (\(\mathbb{Z}\) – the set of integers) – discrete optimisation

    In particular:
    • \(D=\{0,1\}^p\) – 0–1 optimisation (hard!)
  • \(D\) is finite (but perhaps large, its objects can be enumerated) – combination optimisation

    For example:
    • \(D=\) all possible routes between two points on a map.

These optimisation tasks tend to be much harder than the continuous ones.

Genetic algorithms might come in handy in such cases.


Specialised methods, customised to solve a specific problem (like Lloyd’s algorithm) will often outperform generic ones (like SGD, genetic algorithms) in terms of speed and reliability.

All in all, we prefer a suboptimal solution obtained by means of heuristics to no solution at all.

Problems that you could try solving with GAs include variable selection in multiple regression – finding the subset of features optimising the AIC (this is a hard problem to and forward selection was just a simple greed heuristic).


Other interesting algorithms:

  • Hill Climbing (a simple variation of GD with no gradient use)
  • Simulated annealing
  • CMA-ES
  • Tabu search
  • Particle swarm optimisation
  • Artificial bee/ant colony optimisation
  • Cuckoo Search

8.4.2 Further Reading

Recommended further reading:

Other:

  • (Simon 2013)
  • (Boyd & Vandenberghe 2004)