0

I found this old stackoverflow article that essentially is exactly what I want.

Algorithm to optimize multiple variables more efficiently than trial-and-error

unforunately my more advanced maths are a bit lacking and I have some questions about the answer by ElKamina, if anyone can take a look and advise some of these basic math concepts, hopefully it will help me out.

The answer I am referring to is as follows:

def simAnneal( w, seed_x, numSteps=100000, sigma=0.01 ):
    optimal_x = [i for i in seed_x]
    optimal_w = w(optimal_x)

    cur_w = w(seed_x)

    for i in range(numSteps):
        new_x = [i+random.gauss(0, sigma) for i in seed_x]
        new_w = w(new_x)

        if (new_w > cur_w) or (random.random() > new_w / cur_w) :
            cur_x = new_x
            cur_w = new_w
            if cur_w > optimal_w:
                optimal_w = cur_w
                optimal_x = cur_x
    return optimal_x

I am unfamiliar with seed_x, sigma and gaussian distribution so I am not sure how they are coming up with new_x.

I am attempting to solve a value based on many variables, (>10) and am trying to optimize better than randomly guessing as it would take forever.

Thanks!

user1601716
  • 1,893
  • 4
  • 24
  • 53

1 Answers1

5

Simulated Annealing TLDR: We're trying to find a set of parameters that will maximize a function by adding random noise to parameters. If change leads to improvement, changes are accepted; once in a while we accept negative changes, but the probability of that lowers with time and how bad the change is.

In the snippet above, the function actually uses multiple parameters but accepts them as a list:

  • w is the function which parameters are optimized
  • seed_x is the initial guess of parameters - can be selected at random, but an informed guess would be better
  • Gaussian is just "shape" of the noise, such that small values are more common. random.random()*sigma (all values are equally likely) would work just fine there, too.
  • sigma is the magnitude of noise to be injected. It should not exceed a couple percent of typical param values. If param values vastly differ in magnitude, consider using a list of sigmas specific for each parameter.
  • MISSING: notion of temperature, which will actually make it simulated annealing

Rewriting it with temperature, more descriptive names, and more explicit:

def simAnneal(utility_func, initial_params, numSteps=100000,
              noise_magnitude=0.01, cooling_rate=0.999):
    optimal_params = initial_params
    params = initial_params.copy()  # lists are mutable, so .copy()
    best_utility = utility = utility_func(*initial_params)
    temperature = 1.0
    
    for i in range(numSteps):
        temperature *= cooling_rate
        # consider using numpy/scipy for params and noise
        new_params = [param+random.gauss(0, noise_magnitude) 
                      for param in params]
        # explicitly passing multiple parameters
        new_utility = utility_func(*new_params)

        if (new_utility > best_utility 
            or random.random()*temperature > new_utility / best_utility):
            params, utility = new_params, new_utility
            if new_utility > best_utility:
                optimal_params, best_utility = params, utility
    return optimal_params

Last but not least - unless the problem is extremely non-convex, I'd bet SGD would perform much better.

Marat
  • 15,215
  • 2
  • 39
  • 48