Constrained ordered sum of elements

The objective function of this problem is:

\[f(x) = \sum_{i=1}^{|x|}\frac{x_i}{i}\]

From a shuffled set of integers, find the numbers that minimize the sum of fractions, so that the sum of the candidates doesn’t not surpass 15.

In this case, the order of the numbers matter, so we use the Permutation optimizer

• 
• 

Out:

Iteration 0:
   global_best: 302525.633   iteration_best: 302525.633   min_sum: 73.000   l2: 54.434
Iteration 1:
   global_best: 36118.433   iteration_best: 36118.433   min_sum: 37.000   l2: 40.275
Iteration 2:
   global_best: 36116.433   iteration_best: 36116.433   min_sum: 37.000   l2: 31.232
Iteration 3:
   global_best: 36112.433   iteration_best: 36112.433   min_sum: 37.000   l2: 21.078
Iteration 4:
   global_best: 36112.183   iteration_best: 36112.183   min_sum: 37.000   l2: 15.273
Iteration 5:
   global_best: 36111.767   iteration_best: 36111.767   min_sum: 37.000   l2: 10.156
Iteration 6:
   global_best: 3608.617   iteration_best: 3608.617   min_sum: 24.000   l2: 17.971
Iteration 7:
   global_best: 3608.617   iteration_best: 3608.617   min_sum: 24.000   l2: 10.343
Iteration 8:
   global_best: 3608.617   iteration_best: 3608.617   min_sum: 24.000   l2: 9.266
Iteration 9:
   global_best: 3608.617   iteration_best: 3609.133   min_sum: 24.000   l2: 11.410
Iteration 10:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 5.802
Iteration 11:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 7.595
Iteration 12:
   global_best: 3608.567   iteration_best: 3608.617   min_sum: 24.000   l2: 5.680
Iteration 13:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 8.311
Iteration 14:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 4.040
Iteration 15:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 4.928
Iteration 16:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 4.678
Iteration 17:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 8.320
Iteration 18:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 6.327
Iteration 19:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 5.816
Iteration 20:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 3.266
Iteration 21:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 8.390
Iteration 22:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 4.237
Iteration 23:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 6.607
Iteration 24:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 8.702
Iteration 25:
   global_best: 3608.567   iteration_best: 3608.567   min_sum: 24.000   l2: 3.712
Iteration 26:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 4.611
Iteration 27:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 7.041
Iteration 28:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 9.471
Iteration 29:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 6.955
Iteration 30:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 7.431
Iteration 31:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 6.702
Iteration 32:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 11.655
Iteration 33:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 7.531
Iteration 34:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 9.267
Iteration 35:
   global_best: 5.783   iteration_best: 5.833   min_sum: 18.000   l2: 10.305
Iteration 36:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 7.316
Iteration 37:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 5.637
Iteration 38:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 4.793
Iteration 39:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 3.799
Iteration 40:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 6.458
Iteration 41:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 4.297
Iteration 42:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 7.303
Iteration 43:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 6.463
Iteration 44:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 9.889
Iteration 45:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 5.264
Iteration 46:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 6.979
Iteration 47:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 11.294
Iteration 48:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 3.639
Iteration 49:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 4.518
Iteration 50:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 3.762
Iteration 51:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 5.643
Iteration 52:
   global_best: 5.783   iteration_best: 5.783   min_sum: 15.000   l2: 9.958
Iteration 53:
   global_best: 5.783   iteration_best: 5.783   min_sum: 15.000   l2: 7.380
Iteration 54:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 7.580
Iteration 55:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 5.285
Iteration 56:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 9.198
Iteration 57:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 7.356
Iteration 58:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 7.212
Iteration 59:
   global_best: 5.783   iteration_best: 5.783   min_sum: 18.000   l2: 6.179
Iteration 60:
   global_best: 5.050   iteration_best: 5.050   min_sum: 15.000   l2: 7.006
Iteration 61:
   global_best: 5.050   iteration_best: 5.050   min_sum: 15.000   l2: 5.517
Iteration 62:
   global_best: 5.050   iteration_best: 5.467   min_sum: 15.000   l2: 9.800
Iteration 63:
   global_best: 5.050   iteration_best: 5.050   min_sum: 15.000   l2: 7.728
Iteration 64:
   global_best: 5.050   iteration_best: 5.050   min_sum: 15.000   l2: 5.290
Iteration 65:
   global_best: 5.000   iteration_best: 5.000   min_sum: 15.000   l2: 5.358

Iteration completed
==========================
Exit code 2: Algorithm has reached the value threshold of 5.0
Elapsed time 0.217
65 iterations
Best selection: [1, 2, 3, 4, 5]
Best evaluation: 5.0

import random
from psopt import Permutation


def main():
    # define objective function: f([a, b, c, ...]) = a/1 + b/2 + c/3 + ...
    def obj_func(x):
        return sum([a / (i + 1) for i, a in enumerate(x)])

    # seed the pseudo-random number generator
    seed = 5
    random.seed(seed)

    # list of shuffled candidates ranging from 1 to 50
    candidates = random.sample(list(range(1, 51)), 50)

    selection_size = 5

    # constraint: sum of values cannot be greater than 18
    constraint = {
        "fn": sum,
        "type": ">",
        "value": 18,
    }

    # instantiate the optimizer
    def min_sum(particles):
        return min([sum(i) for i in particles])

    opt = Permutation(obj_func, candidates, constraints=constraint, metrics=[min_sum, 'l2'])

    # define a threshold of acceptance for early convergence
    threshold = obj_func(sorted(candidates)[:selection_size])

    # minimize the obj function
    result = opt.minimize(
        selection_size=selection_size, verbose=1, threshold=threshold, population=20, seed=seed
    )

    result.history.plot("min_sum")
    result.history.plot("global_best")


if __name__ == "__main__":
    main()