7
\$\begingroup\$

Here is the Egg Holder function for \$m\$ dimensions:

$$\displaystyle f(x)=\sum_{i=1}^{m-1}\left[-(x_{i+1}+47)\sin\sqrt{|x_{i+1}+x_i /2 + 47|} -x_i \sin\sqrt{|x_i - (x_{i+1}+47)|}\right]$$

I am trying to find the global minimum of this function using hill climbing. Here's how the algorithm works:

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_1 to M_4, where M = P + random summand
        for each M:
            find fitnesses MF of M
            if MF < F:
                F = MF
                P = M
        if F < BF:
            BF = F
            BP = P

The algorithm will find a position, generate four moves off of that position, then evaluate their fitness. If it's a better fitness than previously, that move becomes the new position and it repeats with four more moves, and so on. If the position becomes unbounded, start again with a new random initial position but keep the global bests stored. Eventually, the best position will creep towards the global best fitness (lower is better, ie. the function minimum).

The bounds for each dimension is [-512.00..512.00] and the random summand is bounded within [-5.00..5.00]. Here's some C++ code using a hardcoded dimensionality of 2:

#include <iostream>
#include <cmath>
#include <signal.h>
#include <unistd.h>
#include <pthread.h>
#include <array>
#include <float.h>
#include <sstream>

// globals
const static unsigned int DIMENSIONS = 2; // how many dimensions
std::array<double, DIMENSIONS> bestPosition; // best position so far
double bestResult = DBL_MAX; // arbitrarily large
volatile bool continuing; // for thread while loop

// function declarations
bool checkInBounds(std::array<double, DIMENSIONS>, int, int);
std::array<double, DIMENSIONS> getRandPosition(int, int);
std::string printBest();

/**
 * Egg Holder function evaluation function
 * @param p - the position to evaluate
 * @return - the fitness of that position (lower is better)
 */
double eggHolderEvaluation(std::array<double, DIMENSIONS> p) {
    double sum; // to aggregate dimensions
    for (unsigned int i = 0; i < DIMENSIONS-1; i++) {
        // split for readability, this is the EH summation
        double subSum = (p[i+1] + 47) * (std::sin(std::sqrt(std::abs((p[i]/2) + p[i+1] + 47))));
        subSum -= (p[i] * std::sin(std::sqrt(std::abs(p[i] - p[i+1] - 47))));
        subSum *= (-1);
        sum += subSum; // append it to aggregate sum
    }
    return sum;
}

/**
 * Hill Climbing worker function
 */
void* hillClimb(void* ignore) {
    std::array<double, DIMENSIONS> position; // position for evaluation later
    std::array<double, DIMENSIONS> stoch; // stochastic element
    double best, tempBest; // best of thread, temporary best used later
    while (continuing) { // while thread alive
        position = getRandPosition(-512, 512); // find a random position -512..512 for each dimension
        best = eggHolderEvaluation(position); // find fitness of that position
        while (checkInBounds(position, -512, 512)) { // while the position is within bounds
            for (unsigned int i = 0; i < 4; i++) { // four possible moves
                stoch = getRandPosition(-5, 5); // stochastic summand position -5..5
                std::array<double, DIMENSIONS> tempPos; // for adding
                // add the stochastic element to the position
                for (unsigned int j = 0; j < DIMENSIONS; j++) { tempPos[j] = stoch[j] + position[j]; }
                tempBest = eggHolderEvaluation(tempPos); // evaluate that new position
                if (tempBest < best) { // if better than loop
                    position = tempPos; // overwrite
                    best = tempBest;
                }
            }
            if (best < bestResult) { // if better than global
                bestPosition = position; // overwrite
                bestResult = best;
                std::cout << "New minimum: " << printBest();
            }
        }
    }
    return 0;
}

/**
 * function to find a random position
 * @param l - lower bound
 * @param h - higher bound
 * @return - a random position in all dimensions l..h
 */
std::array<double, DIMENSIONS> getRandPosition(int l, int h) {
    std::array<double, DIMENSIONS> p;
    for (unsigned int i = 0; i < DIMENSIONS; i++) { // for each dimension
        // generate random position
        p[i] = l + (double)(rand() / (double)RAND_MAX) * (h - l);
    }
    return p;
}

/**
 * function to check if a position is within bounds
 * @param p - the position to check
 * @param l - lower bound
 * @param h - higher bound
 * @return - whether p is within l..h
 */
bool checkInBounds(std::array<double, DIMENSIONS> p, int l, int h) {
    for (unsigned int i = 0; i < DIMENSIONS; i++) { // for each dimension
        // first dimension proc chance may come earlier; return F on per dimension basis
        if (p[i] > h || p[i] < l) { return false; }
    }
    // if it gets here, it's all within bounds
    return true;
}

/**
 * function to print the best to user
 * @return - the function with params and its evaluation
 */
std::string printBest() {
    std::stringstream toReturn;
    toReturn << "f(";
    for (unsigned int i = 0; i < DIMENSIONS; i++) {
        toReturn << bestPosition[i];
        if (i < DIMENSIONS - 1) { toReturn << ", "; }
    }
    toReturn << ") = " << bestResult << "\n";
    return toReturn.str().c_str();
}

// interrupt handler
void interrupted(int signal) {
    continuing = false;
}

int main (int argc, char* argv[]) {
    srand(time(NULL));
    signal(SIGINT, interrupted);
    pthread_t thread;
    continuing = true;
    pthread_create(&thread, NULL, &hillClimb, NULL);
    while (continuing) { sleep(1); }
    std::cout << "\nBest in run: " << printBest();
    return 0;
}

Compile with g++ -pthread -std=c++0x source.cpp -o eghc and execute with ./eghc. Here's a sample execution:

$ g++ -pthread -std=c++0x source.cpp -o eghc && ./eghc
New minimum: f(-431.589, -362.496) = 146.096
New minimum: f(-431.215, -363.239) = 137.753
New minimum: f(-432.044, -367.541) = 96.1419
New minimum: f(-433.497, -379.378) = -73.8794
New minimum: f(-433.581, -379.858) = -81.7316
New minimum: f(-429.106, -386.805) = -328.96
New minimum: f(-423.988, -389.813) = -513.774
New minimum: f(-422.713, -394.128) = -628.416
New minimum: f(-420.314, -398.311) = -726.148
New minimum: f(-416.017, -397.849) = -755.885
New minimum: f(-417.356, -401.802) = -766.056
New minimum: f(-415.791, -401.4) = -766.095
New minimum: f(-415.792, -401.024) = -766.201
New minimum: f(-417.295, -402.015) = -766.299
New minimum: f(-417.054, -402.14) = -766.429
New minimum: f(-417.055, -402.156) = -766.43
New minimum: f(-416.905, -402.017) = -766.43
New minimum: f(-417.038, -402.159) = -766.43
New minimum: f(-416.974, -402.094) = -766.431
New minimum: f(-416.962, -402.077) = -766.431
New minimum: f(-416.979, -402.091) = -766.431
New minimum: f(-416.971, -402.085) = -766.431
New minimum: f(-416.976, -402.09) = -766.431
^C
Best in run: f(-416.976, -402.09) = -766.431

A thread is initialized to perform the hill climbing; there's no termination condition other than SIGINT, which will exit the program after outputting the best in run fitness. I only use a thread so it could be scaled to >1 thread at a later date if I wish.

I can't find much literature for the function minimum for the Egg Holder function in >2 dimensions, so I can't verify how >2 dimensions performs, but for 2-dimensions, it does get caught in local minima. Optimal is f(512, 404.2319) = -959.6407, however.

How could this be improved to get out of local extremum?

\$\endgroup\$
  • 1
    \$\begingroup\$ To begin with, double sum; is not initialized. It may also be beneficial to explain what the Egg Holder function is, a significance of 47, and why do you expect the hill climbing to find the global minimum. \$\endgroup\$ – vnp Nov 19 '19 at 5:27
  • \$\begingroup\$ @vnp nice catch, but it does compile even without double sum = 0.00;. None of -Wall, -Wpedantic, or -Wextra catch it. \$\endgroup\$ – gator Nov 19 '19 at 5:29
  • 1
    \$\begingroup\$ A not initialized automatic variable invokes an undefined behavior, and C++ is not required to (in fact, in most cases unable to) diagnose it. \$\endgroup\$ – vnp Nov 19 '19 at 5:32
  • \$\begingroup\$ @vnp interesting, thanks for the info! \$\endgroup\$ – gator Nov 19 '19 at 5:38
  • \$\begingroup\$ Some compiler warnings are only enabled at higher optimization levels, such as -O2. Detection of unassigned variables may be one of them. You should also compile the code with CLang and with Intel C++ and with MSVC and enable all warnings for them as well, just to get more checks and warnings. \$\endgroup\$ – Roland Illig Nov 19 '19 at 21:45
3
\$\begingroup\$

The code already follows a good programming practice, which is to make all statements contained by if, then and loops logic blocks rather than single statements.

Portability

The code is specifically using Unix/Linux headers and is not portable to other systems, such as Windows. On Windows the code won't compile due to the headers #include <unistd.h> and #include <pthread.h>. The use of the function sleep() also prevents portability.

Use C++ Random Number Generator Over C Random Number Generator

The code is currently using the C programming language random number generation technique. Since C++11 the C++ programming language has had it's own random number generator that provides a better distribution of random numbers.

#include <random>
#include <iostream>

int main()
{
    std::random_device dev;
    std::mt19937 rng(dev());
    std::uniform_int_distribution<std::mt19937::result_type> dist6(1,6); // distribution in range [1, 6]

    std::cout << dist6(rng) << std::endl;
}

This is discussed in more detail in this stackoverflow question.

Initialize Variables

As noted by @vnp a best practice in C++ is to always initialize variables. Local variables in a function is memory allocated from the stack and may contain previous values, the C++ programming standard does not require local variables to be initialized by the compiler. This has caused many bugs over the years. This stackoverflow question discusses when a variable will or will not be initialized.

Magic Numbers

As noted by @vnp there are Magic Numbers in the double eggHolderEvaluation(std::array<double, DIMENSIONS> p) function (47), there are also magic numbers in the function void* hillClimb(void* ignore) (-512, 512, -5, 5 and 4). Tt might be better to create symbolic constants for them to make the code more readble and easier to maintain. These numbers may be used in many places and being able to change them by editing only one line makes maintainence easier.

Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them. There is a discussion of this on stackoverflow.

Proper Include Headers

This program uses the C programming include files #include <signal.h> and #include <float.h>. The C++ version of these headers can be used by removing the dot h and prepending the file name with 'c'.

#include <csignal>
#include <cfloat>

The code is missing the header file ctime which is used to to initialize the random number generator.

Exit Status

The return 0; is not absolutely necessary, C++ will do the proper thing without it. If there were possible failure modes as well as successful exits, it might be better to include cstdlib and use EXIT_SUCCESS and EXIT_FAILURE rather than return 0.

Readability

The code might be more readable if it contained more vertical spacing. While there is vertical spacing between functions, the more complex functions could use vertical spacing to show separate logic blocks. Here is an example

void* hillClimb(void* ignore) {
    std::array<double, DIMENSIONS> position; // position for evaluation later
    std::array<double, DIMENSIONS> stoch; // stochastic element
    double best, tempBest; // best of thread, temporary best used later

    while (continuing) { // while thread alive
        position = getRandPosition(-512, 512); // find a random position -512..512 for each dimension
        best = eggHolderEvaluation(position); // find fitness of that position
        while (checkInBounds(position, -512, 512)) { // while the position is within bounds
            for (unsigned int i = 0; i < 4; i++) { // four possible moves
                stoch = getRandPosition(-5, 5); // stochastic summand position -5..5
                std::array<double, DIMENSIONS> tempPos; // for adding
                // add the stochastic element to the position
                for (unsigned int j = 0; j < DIMENSIONS; j++) {
                    tempPos[j] = stoch[j] + position[j];
                }
                tempBest = eggHolderEvaluation(tempPos); // evaluate that new position

                if (tempBest < best) { // if better than loop
                    position = tempPos; // overwrite
                    best = tempBest;
                }
            }

            if (best < bestResult) { // if better than global
                bestPosition = position; // overwrite
                bestResult = best;
                std::cout << "New minimum: " << printBest();
            }
        }
    }

    return 0;
}

By breaking it up this way, it becomes obvious that the variables best, tempBest position and stoch can actually be declared within the loops themselvers rather than the top of the function.

If statements and loops become more readable if they are not on one line as shown above.

\$\endgroup\$
  • \$\begingroup\$ Excellent writeup, thank you. One thing: is 47 considered a magic number if it is part of the function and not arbitrary? \$\endgroup\$ – gator Nov 19 '19 at 21:20
  • \$\begingroup\$ @gator The code doesn't explain what 47 is in a comment, and there is no symbolic name. Let's say you coded this professionally and then won 4 million dollars, or moved to another city; the person that has to maintain this code has no idea what that 47 represents. It wasn't clear to me or vnp. \$\endgroup\$ – pacmaninbw Nov 19 '19 at 22:47
  • \$\begingroup\$ That's fair. To be frank, I'm not even sure what it represents myself. It's part of the definition of the Egg Holder function, something some mathematician of antiquity came up with. \$\endgroup\$ – gator Nov 19 '19 at 23:05
  • 1
    \$\begingroup\$ @gator Truly a magic number, LOL. \$\endgroup\$ – pacmaninbw Nov 19 '19 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.