Simmulated Annealing for Binary Optimization

The function implements simmulated annealing for binary optimization.

The function implements simmulated annealing for binary optimization. At the beginning, random binary vector is prepared. The vector is changed followingly:

1. Two radnom indices i and j are generated
2. Values of i-th and j-th variables are swapped
3. i-th variable is negated if random number (from distribution U[0,1]) is higher that 0.5
4. Step 3 is also carried out for j-th variable

After that, objective function value is calculated. If it is lower than the one found in previous step, the new value and respective solution are preserved. If the objective fuction value is higher than the one in previous step, Metropolis criterion is applied to decide whether to preserve the solution. Since the objective function value can rise, in each iteration, it is checked whether current solution is better than the best one found so far. If so, the best solution is updated.

Note that "Boltzman constant" in the Metropolis criterion is repalced by user-defined parameter (default value is 1) because natural Boltzman constant could be inappropriate for solved task. Higher the "Boltzman constant", higher the probability that the worse solution is preserved.

The process above is repeated until maximal number of iteration (user-defined) is reached. Once that happen, a temperature is decreased by user-defined decrement (i.e. linear cooling schedule is used) and the process starts again with the lower temperature. Note that the maximal temperature is 1.

Once the optimization ends, a curve showing decrease in the objective function value is plotted.

Inputs:

• f: optimized function handler
• N: number of variables
• maxIter: maximal number of iterations for certain temperature T
• tempStep: decrease in temperature after max. number of iterations is reached (a positive number less than 1)
• k_b: "Boltzman constant" in Metropolis criterion (default value is 1)

Output :

• x_best: solution of the task
• f_best: objective function value of the solution x_best