This paper describes a novel algorithm for numerical optimization, called Simple Adaptive Climbing (SAC). SAC is a simple efficient single-point approach that does not require a careful fine-tunning of its two parameters. SAC algorithm shares many similarities with local optimization heuristics, such as random walk, gradient descent, and hill-climbing. SAC has a restarting mechanism, and a powerful adaptive mutation process that resembles the one used in Differential Evolution. The algorithms SAC is capable of performing global unconstrained optimization efficiently in high dimensional test functions. This paper shows results on 15 well-known unconstrained problems. Test results confirm that SAC is competitive against state-of-the-art approaches such as micro-Particle Swarm Optimization, CMA-ES or Simple Adaptive Differential Evolution.
In the most general case, global numerical optimization is the task of finding the point (x∗) with the smallest (minimization case) or bigger (maximization case) function value (f(x∗)). There exists special cases where the search space is highly constrained, it means that the solution found by the algorithm must be optimal, and it must satisfy the defined problem’s constrains too ( Cruz-Cortés et al., 2005, Coello Coello and Cruz-Cortés, 2002 and Coello Coello and Cruz-Cortés, 2004). Other kind of numerical optimization problems are the called Multi-Objective Optimization with more than one objective functions to be optimized at the same time (Coello Coello & Cruz-Cortés, 2005). In this work we are interested on designing an algorithm for non-linear unconstrained single-objective optimization problems.
The Evolutionary Algorithms have been widely utilized to find optimal solutions to non-linear optimization problems. The Evolutionary Algorithms are population-based, e.g. they handle a set of possible solutions, further they are probabilistic methods. On the other hand, single-point optimizers such as hill-climbing, and random walks handle one point at a time. Random as well as deterministic versions of the hill-climbing algorithms can be found in the specialized literature.
Most of the recent efficient optimizers for solving unconstrained optimization, such as restart Covariance Matrix Adaptation Evolution Strategy (CMA-ES) (Auger & Hansen, 2005), can be considered complex approaches because they use Hessian and covariance matrix. Those approaches are very effective and greatly overcome more of the simple heuristic approaches, as shown in events such as Congress on Evolutionary Computation (Hansen, 2006) and the Black-Box Optimization Benchmarking workshop (Hansen, Auger, Finck, & Ros, 2010). However, we consider that a simpler approach capable of giving quality results is sufficient for most of the times. This paper presents a novel approach based on the idea of having one single point but with a powerful and adaptive mutation strategy: Simple Adaptive Climbing (SAC). It is a single-point approach similar to hill-climbing or random walk algorithms. Hill-climbing like algorithms are known for having difficulties solving global optimization problems with multiple local optimum values (as explained further in Section 2). Our algorithm can solve these problems due to the following features:
•
It can move to all the possible search directions.
•
Its search radius is adaptively adjusted, i.e. it is adjusted depending on the current situation.
•
It has a restarting mechanism that allows the algorithm to resume its process when getting stuck in a solution.
We tested our approach on 15 well-known unconstrained problems. Test results show that the algorithm works as well as more complex state-of-the-art approaches, such as micro-Particle Swarm Optimization, CMA-ES, or Simple Adaptive Differential Evolution.
The contents of this paper are organized as follows: First, we give a brief introduction on hill-climbing algorithm in Section 2. Section 3 contains the SAC description. Section 4 contains the experimental design. Section 5 presents a comparison of SAC against four state-of-the-art approaches: Elitist Evolution, micro-Particle Swarm Optimization, Simple Adaptive Differential Evolution, and Restart CMA-ES. Finally, Section 6 concludes this paper.
In this paper we presented a novel optimizer called SAC and tested it on 15 benchmark functions. SAC is a simple technique that uses a single exploration point and adaptive step sizes. Its main features are: (1) easy implementation, (2) competitive against approaches like: μ-PSO, SADE and CMA-ES, (3) easy parameter configuration, (4) fast solution speed, and (5) high success rate.
SAC requieres configuration of two parameters: B and R. B is reference search radius of SAC. Large B values encourage global exploration and small B values encourage local exploitation. R controls SAC’s searching time over the current location. Small R values allow SAC to move often, while larger values cause a more extensive exploration over the current minimum value.
More comparative studies and further analysis should be carried out to provide a more detailed understanding of SAC. We also plan to test SAC in constrained and multi-objective optimization problems.
