Local search

The methods of descent, or local searches, compose to « slide » along the objective function to find a local optimum, until the descent is no longer possible. There are several types of descent methods that we will describe here.

Simple descent

From an initial solution, the simple descent algorithm chooses a neighboring solution better than the current solution, until it can not make such a choice.
S_O
do
   S(i+1) = neighboor(Si)
   if f(S(i+1)) < f(Si)
      accept S(i+1)
   end
while f(S(i+1)) < f(Si), any S(i+1) = neighboor(Si)
return Rn

 descentesimple

Largest descent

The algorithm is mainly the same as for the simple descent, only a criterion of selection of a neighboring solution is modified:

choose s' from neighboor(s) / f(s') < f(s'') or f(s')=f(s'') for any s'' from neighboor(s)

descenteplus

Multi-start descent

The multi-start descent performs multiple instances of the single descent or greater descent problem.

descentemulti

 

Publicités