Metaheuristics: Cheat Sheets Cheat Sheet by jlobera.up

Evolut­ionary Computing is a research area within computer science. As the name suggests, it is inspired by Darwin's theory of natural evolution.
In an enviro­nment with limited resources, the fittest indivi­duals survive. Also, they have more chances to have offspring.

In the classical example of EP, predictors were evolved in the form of finite state machines.
A finite state machine (FSM) is a transducer that can be stimulated by a finite alphabet of input symbols and can respond in a finite alphabet of output symbols.
It consists of a number of states S and a number of state transi­tions.
The state transi­tions define the working of the FSM: depending on the current state and the current input symbol, they define an output symbol and the next state to go to.

Inspired by the movement of a flock of birds when searching for food.

Each particle 𝑖 represents a solution for the problem. In the time t, it has a position 𝑥𝑖 (𝑡) ∈ ℝ𝑑 and a velocity 𝑣𝑖 ∈ ℝ𝑑.

The positions and velocities are updated following the next equations, where 𝑃𝑏𝑒𝑠𝑡 𝑖 is the best position where the particle 𝑖 has been, 𝐺𝑏𝑒𝑠𝑡 is the best location founded until the moment, 𝑟1 𝑎𝑛𝑑 𝑟2 are random numbers between 0 and 1, and 𝑤, 𝑐1, 𝑎𝑛𝑑 𝑐2 are hyper parame­ters. Those last values can be initia­lized at 0.9 and gradually reducing it until 0.1.

John Holland proposed genetic Algorithms in the 1970s. Initially, they were called “Repro­ductive Plans.” These algorithms are maybe the most famous of the evolutive algorithms family.

The inspir­ation comes from the DNA structure, which is people's genetic code. All the inform­ation is stored in chromo­somes that have a lot of genes. Holland’s proposal consists of repres­enting the solutions by binary arrays.

It is a robust algorithm for solving continuous multid­ime­nsional optimi­zation problems. In this algorithm, indivi­duals as seen as vectors.
The novelty is the mutation operator, that uses three indivi­duals for mutate another one, and the mutation depends on the distance

In general, the presence of constr­aints will divide the space of potential solutions into two or more disjoint regions, the feasible region, containing those candidate solutions that satisfy the given feasib­ility condition, and the infeasible region containing those that do not.

Takes an infeasible point and generates a feasible solution based on it. In some problems, this technique is relatively simple.

The goal is to solve continuous multid­ime­nsional optimi­zation problems.
The main charac­ter­istic is the self-a­dap­tation of parameters. It means that some evolutive algorithm parameters change during the execution.
Those parameters are included in the individual repres­ent­ation and evolve at the same time that the solution.

Automa­tically solves problems without requiring the user to know or specify the structure of the solution in advance.
The main idea of GP is to evolve a population of computer programs, where indivi­duals are commonly repres­ented as syntax trees.

Solves problems of finding paths in graphs. It is inspired by the ants' behavior when searching for food. The ants leave pheromones that allow other ants to follow the path to food. The more ants go for a specific path, the more pherom­ones.