Forward Backward Transformation - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 46

α = 0
while α |< D
i = rand [1 , D ] , i ∈ α
β = { i }

while < D

j = rand [1 , D ] , j ∈ β

β |

Δ ( x , i , j ) < 0; x i = x j
x j = x i

If

β = β ∪{ j }
α = α ∪{ j }

Fig. 3.8. Pseudocode for 2 Opt Local Search

To move away from the point of stagnation, a feasible operation is a neighborhood
or local search, which can be applied to a solution to find better feasible solution in the
local neighborhood. Local search in an improvement strategy. It is usually independent
of the search heuristic, and considered as a plug-in to the main heuristic. The point of
note is that local search is very expensive in terms of time and memory. Local search
can sometimes be considered as a brute force method of exploring the search space.
These constraints make the insertion and the operation of local search very delicate
to implement. The route that EDE has adapted is to check the optimal solution in the
population for stagnation, instead of the whole population. As mentioned earlier five
(5) non-improving generations constitute stagnation. The point of insertion of local
search is very critical. The local search is inserted at the termination of the improvement
module in the EDE heuristic.
Local Search is an approximation algorithm or heuristic. Local Search works on a
neighborhood . A complete neighborhood of a solution is defined as the set of all solu-
tions that can be arrived at by a move. The word solution should be explicitly defined
to reflect the problem being solved. This variant of the local search routine is described
in [24] as is generally known as a 2-opt local search.
The basic outline of a Local Search technique is given in Fig 3.8. A number

α is

chosen equal to zero (0) ( = 0). This number iterates through the entire population,

by choosing each progressive value from the solution. On each iteration of

α

, a random
number i is chosen which is between the lower (1) and upper ( D ) bound. A second
number

α

starts at the position i , and iterates till the end of the solution. In this second
iteration another random number j is chosen, which is between the lower and upper
bound and not equal to value of

β

. The values in the solution indexed by i and j are
swapped. The objective function of the new solution is calculated and only if there is
an improvement given as

β

Δ ( x , i , j ) < 0, then the new solution is accepted.

Illustration :
To understand how this local search operates, consider two solutions x 1 and x 2 .The
operations parameters of these solutions are:
Upper bound x ( hi ) =5
Lower bound x ( lo ) =1
Solution size D =5