Hill climbing algorithms

Got it! This site uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website.nbsp; Note: This appears on each machine/browser from which this site is accessed.

c go java js lua py vbs rkt scm pro

Many algorithms can be described as hill-climbing algorithms.

That is, they go from some point in solution space to a "better" point in solution space by "hill climbing".

That is, based on the slope of a change, the algorithm takes the change that would increase (or decrease) some objective function.

Here is the Python code.

import matplotlib.pyplot as plt
import rsPlot

import numpy as np

plot1 = rsPlot.plot("hill21-1")
print("Generating curve ...")
thick1 = 6
xData1 = np.linspace(0, 16, 100)
yData1 = np.sin(xData1) * np.exp(-xData1 / 4.0)
plt.plot(xData1,yData1,linewidth=thick1)

plot1.save()

Here is the output of the Python code.

(module rsPlot imported)
Generating curve ...
	./hill21-1-01.png : 574 x 414 , 23,991 bytes

Here are two ways to make decisions.

Global decisions: Global decisions have global consequences and need to be made early in the design stage. Making good global decisions lowers overall cost and increases effectiveness. Poor global decisions have the opposite effect.
Local decisions. Local decisions are often called a greedy strategy in that the optimum decision at a local level, when scaled up, does not always result in an optimum effect at a global level.

A "greedy" algorithm is an algorithm that always takes the best local approach to improving a solution.

When a greedy algorithm works, it usually works well.

However, "hill climbing" algorithms may not work so well with a greedy approach as they may get stuck on a "local" hill and not find a "global" optimum solution.

This greedy approach as is often in algorithms should not be confused with lazy and eager approaches.

Eager strategy - do it now in case it is needed - JIC (Just In Case) strategy.
Lazy strategy - delay until just when it is needed - JIT (Just In Time) strategy.

Aside: My Ph.D. dissertation was Issues in the implementation of lazy functional languages (1990), and which was intimately involved with the ideas of copy-update problems, sharing properties, and eager and lazy evaluation in both sequential and parallel modes of execution for functional languages.

Back to the problem of a greedy strategy not yielding an optimal global solution.

In many cases, some form of randomization helps in avoiding local minimum (or maximum) solutions.