stratzilla/hill-climbers

Using Hill Climbing to minimize various functions

Hill Climbers

A very rudimentary multidimensional local search using hill climbing to find global minima over various functions. The algorithm is generalized to any dimensionality, although the source code has a dimensionality of 2 chosen for an expectation of common use.

Compilation and Execution

Compile with the below:

$ g++ hillclimb.cpp -pthread -std=c++0x -o hc

And execute as below:

$ ./hc <arg1> <arg2>

Where <arg1> is the function to minimize ([1..8]) and <arg2> is how many hill climbers (threads) to utilize within the range [1..8].

This program is multithreaded (up to eight threads) to expedite and improve finding the solution. This program also has no termination condition other than SIGINT: it will continue trying to find the global minimum until the user chooses to signal interrupt, at which point the best in run fitness and position is outputted to the user.

Dependencies

• gcc/g++
• C++ (0x or higher, may need -std=c++0x flag)
• GNU/Linux

Functions

The included minimizing functions are:

<arg1>	Name	Function	Bounds
1	Egg Holder
2	Schwefel
3	Rastrigin
4	Griewank
5	Sphere
6	Dixon-Price
7	Sum Squares
8	Sum of Different Powers

Hill Climbing

The hill climbing algorithm will take an initial position, evaluate its fitness against one of the included functions, and then generate four possible "moves" away from that position. Repeating the evaluative step, if a fitness is better than previously found, that becomes the new position and additional moves are made from that position. Moves are found using a stochastic summand appended to a position in all dimensions, leading to a random (close) move from the original position.

Some pseudocode:

initialize best fitness BF as arbitrarily high
initialize best position BP as empty
while termination condition not met:
  find a random position P
  find fitness F of P
  while P is within bounds:
    find four moves M, where M = P + random summand
    for each M:
      find fitness MF of M
      if MF < F:
        F = MF
        P = M
    if F < BF:
      BF = F
      BP = P

Eventually, the best fitness will be found and the position at which the fitness was found is stored. This is the global minimum for the function. Typical pitfalls (pun intended) of hill climbing algorithms is getting trapped in local minima: this issue is still prevalent in this program. It it meant only as an exercise in hill climbing, not an improvement upon a vanilla implementation.

Some Changes You May Wish To Make

Some aspects of the program are hardcoded. You may wish to change some of these lines for your own experimentation:

Line	What it Does	Default
11	Dimensionality of problem	2
12	How many moves to make per position	4
13	Min/max number of threads	1, 8