我有一個優化問題：
- 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)
But a better solution would be to pick these 6 sets of instructions:
{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)
I already tought about bruteforcing it, but with 80-90 lines of instructions it has about 876488338465357824 possible combinations, so that's not a valid way to do this.
I don't need this to be exactly perfect, a good approximation might suffice.
Any recommendation of tools to solve this problem is helpful, and any keyword to help me search for an appropriate algorithm and for similar problems is welcome.
uj5u.com熱心網友回復：
一種樸素的模擬退火演算法
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] ,
]
uj5u.com熱心網友回復：
您所擁有的是“多維多項選擇背包問題”* 的示例。（從技術上講，您所描述的也是“多目標”，但我懷疑您實際上并不想要多目標答案，這將采用帕累托前沿的形式而不是單一解決方案；您只是沒有尚未決定如何將您的目標組合在一起。）當然，這個問題是 NP 難的，考慮到輸入值的大小和維度，使用動態規劃等偽多項式方法可能是不切實際的。
因此，您必須使用近似演算法。像模擬退火這樣的隨機方法可能會很好地作業，盡管禁忌搜索可能對某些輸入更有效。
*從技術上講它不是相當一個KP因為兩個約束涉及多個變數，但不會做出什么方法是提供給你一個顯著的差異。）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359113.html
標籤：algorithm math optimization minizinc
上一篇：移零邏輯分解Javascript