我什至无法表达这个问题，我需要从一大组数字中选出 3 个非常接近的数字

Question

我有一个优化问题：

5个变量a,b,c,d,e;
4 个约束；
5 个目标；
可供选择的“增量”指令列表。

约束条件：

a >= x
b >= y
e > c
e > d

x 和 y 是整数参数。

目标：

maximize (c + d) * 2 + e
minimize a
minimize b
minimize e - c
minimize e - d

说明：

我有大约 80-90 行；第一行是初始化，然后每行最多包含 4 组“增量”指令。解决问题在于每行选择一组指令。这里以第一行为例：

{a = 0; b = 0; c = 0; d = 0; e = 0}

{b += 360} OR {b += 160; c += 160} OR {b += 160; d += 160} OR {b += 160; e += 160}
{a += 360} OR {a += 160; c += 160} OR {a += 160; d += 160} OR {a += 160; e += 160}
{c += 1697; d += 1697} OR {c += 1697; d += 1019; e += 678} OR {c += 1019; d += 1697; e += 678}

例子：

说x = 1200，y = 170，我们有以下六行指令：

{b += 360} OR {b += 160; c += 160} OR {b += 160; d += 160} OR {b += 160; e += 160}
{a += 360} OR {a += 160; c += 160} OR {a += 160; d += 160} OR {a += 160; e += 160}
{c += 1697; e += 1697} OR {c += 1697; e += 1019; d += 678} OR {c += 1019; e += 1697; d += 678}
{b += 360} OR {b += 160; c += 160} OR {b += 160; d += 160} OR {b += 160; e += 160}
{a += 360} OR {a += 160; c += 160} OR {a += 160; d += 160} OR {a += 160; e += 160}
{a += 1149; d += 939} OR {a += 1149; d += 939; e += 678} OR {a += 939; d += 678; e += 1149}

本例中一个可能的解决方案是从每一行中选取第一组指令：

{b += 360},
{a += 360},
{c += 1697; e += 1697},
{b += 360},
{a += 360},
{a += 1149; d += 939}

然后我们得到这些值：

a = 1869, b = 720, c = 1697, d = 939, e = 1697

目标：

(c + d) * 2 + e = 6969 (to be maximized)
a               = 1869 (to be minimized but >= 1200)
b               = 720  (to be minimised but >= 170)
e - c           = 0    (to be minimized but >= 0)
e - d           = 758  (to be minimized but >= 0)

但更好的解决方案是选择这 6 组指令：

{b += 160; d += 160},
{a += 160; d += 160},
{c += 1697; e += 1019; d += 678},
{b += 160; d += 160},
{a += 160; d += 160},
{a += 939; d += 678; e += 1149}

a = 1259, b = 320, c = 1697, d = 1996, e = 2168

(c + d) * 2 + e = 9554 (to be maximized)
a               = 1259 (to be minimized but >= 1200)
b               = 320  (to be minimised but >= 170)
e - c           = 471  (to be minimized but >= 0)
e - d           = 172  (to be minimized but >= 0)

我已经解决了暴力破解它的问题，但是它有 80-90 行指令，它有大约 876488338465357824 种可能的组合，所以这不是一个有效的方法。

我不需要这个非常完美，一个好的近似值就足够了。

任何解决这个问题的工具推荐都有帮助，欢迎任何关键字帮助我搜索合适的算法和类似问题。

Answer 1

你这里有一个“多维多项选择背包问题”的例子*。（从技术上讲，你所描述的也是“multi-objective”，但我怀疑你实际上并不想要一个 multi-objective 答案，它的形式是帕累托前沿而不是而不是单一的解决方案；你只是还没有决定如何将你的 objective 组合在一起。）这个问题当然是 NP 难的，使用像这样的伪多项式方法可能是不切实际的动态规划，给定输入值的大小和维度。

因此，您将不得不使用近似算法。像模拟退火这样的随机方法可能会工作得很好，尽管禁忌搜索对于某些输入可能更有效。

*从技术上讲，这不是相当 KP，因为其中两个约束涉及多个变量，但这不会对您可用的方法产生重大影响。）

Answer 2

一种朴素的模拟退火算法

通过从列表中选择随机指令来初始化 N 个随机候选解决方案；
循环：
对于池中的每个解决方案，通过随机修改一些指令来生成一些新的候选；
剔除不满足约束条件的候选人；
使用 objective 函数作为权重，随机将池中的内容裁剪到 N，这样好的解决方案更有可能存活下来；
经过大量迭代后，停止并 return 获得最高 objective 的候选人。

注意你的问题是多objective问题。上面的算法假设单个 objective。有许多不同的方法可以将多 objective 问题转化为或多或少相似的单 objective 问题，选择如何做到这一点将导致不同的解决方案。

为简单起见，我写了一个单objective函数作为5个objective的加权和：objective现在最大化10 * ((c+d)*2+e) - a - b - (e-c) - (e-d)。

另一种简单的可能性是将某些 objective 变成约束条件，例如：

objective minimize c - e 进入约束 e - c < 100;
objective minimize c - e 进入约束 e < 2 * c;
objective minimize a 进入约束 a < 2 * x.

您可以通过修改下面代码中的系数 params['objective'] 和函数 satisfies_constraints 来尝试这些更改。

Python代码

from more_itertools import random_product
import random
from itertools import chain

raw_data = '''{b += 360} OR {b += 160; c += 160} OR {b += 160; d += 160} OR {b += 160; e += 160}
{a += 360} OR {a += 160; c += 160} OR {a += 160; d += 160} OR {a += 160; e += 160}
{c += 1697; e += 1697} OR {c += 1697; e += 1019; d += 678} OR {c += 1019; e += 1697; d += 678}
{b += 360} OR {b += 160; c += 160} OR {b += 160; d += 160} OR {b += 160; e += 160}
{a += 360} OR {a += 160; c += 160} OR {a += 160; d += 160} OR {a += 160; e += 160}
{a += 1149; d += 939} OR {a += 1149; d += 939; e += 678} OR {a += 939; d += 678; e += 1149}'''

# input: string "{a += 1149; d += 939}"
# output: list [1149, 0, 0, 939, 0]
def parse_instructionset(s):
    instructions_list = [instruction.split('+=') for instruction in s.strip()[1:-1].split(';')]
    instructions_dict = { k.strip(): int(v) for k,v in instructions_list }
    return [instructions_dict.get(k, 0) for k in 'abcde']

# output: list of lists of lists
# representing lines of disjonctions of instruction sets
def parse_data(raw_data):
    rows = [line.split('OR') for line in raw_data.split('\n')]
    return [[parse_instructionset(s) for s in row] for row in rows]

# for r in parse_data(raw_data):
#     print(r)
# [[0, 360, 0, 0, 0], [0, 160, 160, 0, 0], [0, 160, 0, 160, 0], [0, 160, 0, 0, 160]]
# [[360, 0, 0, 0, 0], [160, 0, 160, 0, 0], [160, 0, 0, 160, 0], [160, 0, 0, 0, 160]]
# [[0, 0, 1697, 0, 1697], [0, 0, 1697, 678, 1019], [0, 0, 1019, 678, 1697]]
# [[0, 360, 0, 0, 0], [0, 160, 160, 0, 0], [0, 160, 0, 160, 0], [0, 160, 0, 0, 160]]
# [[360, 0, 0, 0, 0], [160, 0, 160, 0, 0], [160, 0, 0, 160, 0], [160, 0, 0, 0, 160]]
# [[1149, 0, 0, 939, 0], [1149, 0, 0, 939, 678], [939, 0, 0, 678, 1149]]

# used a weighted sum to turn the multiobjective into one objective
params = {
    'objective': [-1, -1, 20+1, 20+1, 10-2], # 10 * ((c+d)*2+e) - a - b - (e - c) - (e - d)}
    'x': 1200, # lower bound for 'a'
    'y': 170, # lower bound for 'b'
    'poolsize': 50, # number of candidate solutions to keep at each iteration
    'nbupgrades': 5, # number of new solutions to generate from each candidate
    'distance': 2, # number of instruction sets to randomly modify to get a new solution
    'nbiter': 100 # number of iterations
}

# sum increments to get a,b,c,d,e from the chosen instruction sets
def get_abcde(solution):
    return [sum(increment[k] for increment in solution) for k in range(5)]

# return boolean to check that candidate is valid
def satisfies_constraints(abcde, x=params['x'], y=params['y']):
    a,b,c,d,e = abcde
    return a >= x and b >= y and e > c and e > d

# compute value of objective function for candidate
def get_objective(abcde, objective_coeffs=params['objective']):
    return sum(c*v for c,v in zip(objective_coeffs, abcde))

# populate pool with <pool_size> random candidates
def initialise_pool(data, pool_size=params['poolsize']):
    solutions = [random_product(*data) for _ in range(pool_size)]
    abcdes = [get_abcde(sol) for sol in solutions]
    return [(get_objective(abcde), abcde, sol) for abcde,sol in zip(abcdes, solutions)]

# build pool of new candidates from current pool of candidates
def upgrade_pool(pool, data, nb_upgrades=params['nbupgrades'], distance=params['distance']):
    # copy current candidates
    new_pool = list(pool)
    # add new candidates
    for _,abcde,solution in pool:
        for _ in range(nb_upgrades):
            for row_index in [random.randrange(len(data)) for _ in range(distance)]:
                new_instruction = random.choice(data[row_index])
                new_abcde = [[abcde[k] + new_instruction[k] - solution[row_index][k]] for k in range(5)]
                new_solution = list(chain(solution[:row_index], [new_instruction], solution[row_index+1:]))
            abcde = get_abcde(new_solution)
            if satisfies_constraints(abcde):
                new_pool.append((get_objective(abcde), abcde, new_solution))
    # crop down to <pool_size>
    new_pool = crop(new_pool, len(pool))
    return new_pool

# remove excess candidates
# candidates to keep are chosen randomly
# using value of objective as weight
# randomness is very important here, DO NOT simply keep the n candidates with highest objective
def crop(pool, n):
    return random.choices(pool, weights=[obj for obj,_,_ in pool], k=n)

def main_loop(data, nb_iter=params['nbiter'], pool=None):
    if not pool:
        pool = initialise_pool(data)
    for _ in range(nb_iter):
        pool = upgrade_pool(pool, data)
    return pool

if __name__ == '__main__':
    data = parse_data(raw_data)
    pool = main_loop(data)
    pool.sort(key=lambda triplet:triplet[0], reverse=True)

    print('Best 2 and worst 2:')
    for objective, abcde, _ in pool[:2] + pool[-2:]:
        print(objective, abcde)
    print()
    print('Best:')
    obj, abcde, sol = pool[0]
    print('objective={}'.format(obj))
    print('(c+d)*2+e=', (abcde[2]+abcde[3])*2+abcde[4])
    print('a,b,c,d,e={}'.format(abcde))
    print('increments=[')
    for increment in sol:
        print('  ', increment, ',')
    print(']')

输出

objective=93318
(c+d)*2+e= 9554
a,b,c,d,e=[1259, 320, 2017, 1676, 2168]
increments=[
   [0, 160, 0, 160, 0] ,
   [160, 0, 0, 160, 0] ,
   [0, 0, 1697, 678, 1019] ,
   [0, 160, 160, 0, 0] ,
   [160, 0, 160, 0, 0] ,
   [939, 0, 0, 678, 1149] ,
]

我什至无法表达这个问题，我需要从一大组数字中选出 3 个非常接近的数字

I can't even phrase the question, I need 3 closely equal number from a huge set of numbers

algorithm

math

optimization

minizinc

一种朴素的模拟退火算法

Python代码

输出