Theory
Hill Climbing was one of the literature's first existing probabilistic optimization algorithms. The Hill Climbing method is also known as a local search method [1].
The iterative procedure continuously improves the solution until the best solution is attained. The process consists of generating random neighbors of the current solution \left(\symbf{x}_i\right), according to equation (1), where \(\symbf{N}\) indicates a Gaussian or Uniform distribution where the mean \(\symbf{x}^{t}\) is the current solution and \(cov\) is the coefficient of variation input by the user. \(k\) is the \(k\)th component of the design variable vector \(\symbf{x}\) and \(t\) is a current iteration.
| \[x_{i,k}^{t+1} \sim \symbf{N}(x_{i,k}^{t}, \sigma)\] | (1) |
| \[\sigma = x_{i,k}^{t} \cdot \frac{cov}{100}\] | (2) |
A small value of \(\sigma\) gives a higher probability for creating ‘near-parent’ solutions and a large value of \(\sigma\) allows distant solutions.
Algorithm
1: Input initial parameters (cov, n_population, x_lower, x_upper, obj_function, n_dimensions)
2: Input initial guess (x_pop)
3: Calculate of and fit (initial population)
4: for iter in range(n_iterations):
5: x_temp = equation (1)
6: if fit(x_temp) > fit(x_pop):
7: x_pop(iter+1) = x_temp
8: else:
9: x_pop(iter+1) = x_pop(iter)
The Hill Climbing algorithm saves a new solution when a new candidate improves the current best solution.
See HC algorithm in METApy Framework.
Example 1
Use the Hill Climbing optimization method to optimize the 2D sphere function. Use a total of 2 iterations to perform the optimization. Consider the limits \(\mathbf{x}_L = [-5.0, -5.0]\) and \(\mathbf{x}_U = [5.0, 5.0]\) for the problem design variables. Consider the initial guess (two agents) \(\mathbf{pop}_0 = [-0.74, 1.25]\) and \(\mathbf{pop}_1 = [3.58, -3.33]\). Use \(cov = 20%\) and Gaussian random generator.
Solution
Hill Climbing 01 - report
Initial population
x0 = [-0.74, 1.25], of_pop 2.1101 - best solution
x1 = [3.58, -3.33], of_pop 23.9053
Iterations
Iteration: 1
Pop id: 0 - particle movement - mutation procedure
current x = [-0.74, 1.25]
Dimension 0: mean = -0.74, sigma = 0.14800000000000002, neighbor = -0.9023477757469192
Dimension 1: mean = 1.25, sigma = 0.25, neighbor = 1.2619927898303909
update x = [-0.9023477757469192, 1.2619927898303909], of = 2.4068573099793054, fit = 0.29352564813055654
fit_i_temp=0.29352564813055654 < fit_pop[pop]=0.3215330696762162 - not accept this solution
Pop id: 1 - particle movement - mutation procedure
current x = [3.58, -3.33]
Dimension 0: mean = 3.58, sigma = 0.716, neighbor = 3.6241680241318215
Dimension 1: mean = -3.33, sigma = 0.6659999999999999, neighbor = -3.2320736729816724
update x = [3.6241680241318215, -3.2320736729816724], of = 23.58089409472079, fit = 0.040682002702854034
fit_i_temp=0.040682002702854034 > fit_pop[pop]=0.040152096140179 - accept this solution
update solutions
x0 = [-0.74, 1.25], of_pop 2.1101 - best solution
x1 = [3.6241680241318215, -3.2320736729816724], of_pop 23.58089409472079
Iteration: 2
Pop id: 0 - particle movement - mutation procedure
current x = [-0.74, 1.25]
Dimension 0: mean = -0.74, sigma = 0.14800000000000002, neighbor = -0.6839602767380419
Dimension 1: mean = 1.25, sigma = 0.25, neighbor = 0.9611420858210487
update x = [-0.6839602767380419, 0.9611420858210487], of = 1.391595769292015, fit = 0.41813086176182296
fit_i_temp=0.41813086176182296 > fit_pop[pop]=0.3215330696762162 - accept this solution
Pop id: 1 - particle movement - mutation procedure
current x = [3.6241680241318215, -3.2320736729816724]
Dimension 0: mean = 3.6241680241318215, sigma = 0.7248336048263643, neighbor = 2.9304941843959953
Dimension 1: mean = -3.2320736729816724, sigma = 0.6464147345963345, neighbor = -3.1041458794450945
update x = [2.9304941843959953, -3.1041458794450945], of = 18.22351780565471, fit = 0.05201961524991249
fit_i_temp=0.05201961524991249 > fit_pop[pop]=0.040682002702854034 - accept this solution
update solutions
x0 = [-0.6839602767380419, 0.9611420858210487], of_pop 1.391595769292015 - best solution
x1 = [2.9304941843959953, -3.1041458794450945], of_pop 18.22351780565471