Page 145 - Data Science Algorithms in a Week

Simulation Optimization Using a Hybrid Scheme … 129

POWELL HILL-CLIMBING ALGORITHM

Hill-climbing methods are heuristics that use an iterative improvement technique and
are based on a single solution search strategy. These methods can only provide local
optimum values, and they depend on the selection of the starting point (Michalewicz and
Fogel, 2000). Some advantages of hill-climbing-based approaches include: (1) very easy
to use (Michalewicz and Fogel, 2000), (2) do not require extensive parameter tuning, and
(3) very effective in producing good solutions in a moderate amount of time (DeRonne
and Karypis, 2007).
The Powell hill-climbing algorithm was developed by Powell (1964) and it is a hill-
climbing optimization approach that searches the objective in a multidimensional space
by repeatedly using single dimensional optimization. The method finds an optimum in
one search direction before moving to a perpendicular direction in order to find an
improvement (Press et al. 1992). The main advantage of this algorithm lies in not
requiring the calculation of derivatives to find an unconstraint minimum of a function of
several variables (Powell, 1964). This allows using the method to optimize highly
nonlinear problems where it can be laborious or practically impossible to calculate the
derivatives. Moreover, it has been shown that a hybrid strategy that uses a local search
method such as hill-climbing can accelerate the search towards the global optimum,
improving the performance of the searching algorithm (Yin et al. 2006; Özcan & Yilmaz,
2007).

OPTIMIZATION ALGORITHM

The method used to solve the optimization problem is a hybrid algorithm that
combines the advantage of PSO optimization to determine good regions of the search
space with the advantage of local optimization to find quickly the optimal point within
those regions. In other words, the local search is an improvement procedure over the
solution obtained from the PSO algorithm that assures a fast convergence of the ADE.
The local search technique selected was the Powell hill-climbing algorithm. This method
was chosen because: (1) it can be applied to solve multi-dimensional optimization
problems, (2) it is a relatively simple heuristic that does not require the calculation of
derivatives.
The general structure of the method is illustrated in Figure 1. This figure indicates
that the solution to the optimization problem obtained by the PSO algorithm becomes the
initial point to perform a local search using the PHC algorithm. Finally, if the ADE has
converged then the solution provided by the PHC method is the stabilization policy;
otherwise the parameter settings of the PSO algorithm have to be changed in order to
improve the search that makes ADE to converge.