algorithm - 我什至无法表达这个问题，我需要从一大组数字中选出 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

一种朴素的模拟退火算法

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

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

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

另一种简单的可能性是将一些目标转化为约束，例如:

• 目标 minimize c - e进入约束e - c < 100 ;
• 目标 minimize c - e进入约束e < 2 * c ;
• 目标 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] ,
]