寻找具有最大函数值的列表的最佳组合

Question

假设我有 N 个列表（向量），我想从中选择 x 1<x<[N]（x 不是预先确定的）所以我将获得 func(lists).

的最大值

例如：

l1 = [3,4,7,-2]
l2 = [0.5,3,6,2.7]
l3 = [0,5,8,3.6]
mat = [l1, l2, l3]

result = maximize(func, mat)

def func(mat):
    # doing some math between lists. For Example:
    sum_list = list(mat[0])
    for li in mat[1:]:
        sum_list = map(operator.add, sum_list, li)
    accum_min_lst = []
    for i, val in enumerate(sum_list):
        x = sum_list[:i + 1]
        accum_min_lst.append(val - max(x))
    return min(accum_min_lst)

可能的结果：

[l1], [l2], [l3], [l1,l2], [l1,l3], [l2,l3], [l1,l2,l3]

如果我写一个天真的解决方案，只写运行所有组合，它将永远花费 2^N。

我正在尝试使用 cvxpy or maybe scipy.optimize.minimize 找到解决方案但我发现很难理解我需要使用哪种函数来解决我的问题，我想也许我应该尝试进化算法来找到一个近似的答案，或者我应该改用 portfolio optimization。

Answer 1

这可以表示为 MILP 并使用任何 MILP 求解器求解，但我在此处使用 PuLP 显示解决方案。

首先，让我们通过完成所有组合，看看示例问题的答案是什么：

import itertools

allfuncs = sum([[func(combs) for combs in itertools.combinations(mat, r)] for r in range(1, 4)], [])

max(allfuncs)

答案是-3.3

这个解决方案给出了相同的答案并且应该扩展到更大的问题：

import pulp

prob = pulp.LpProblem("MaxFunc", pulp.LpMaximize)

allcols = range(0, len(l1))
allrows = range(0, len(mat))

# These will be our selected rows
rowselected = pulp.LpVariable.dicts('rowselected', allrows, cat=pulp.LpBinary)

# Calulate column sums (equivalent to sum_list in the example)
colsums = pulp.LpVariable.dicts('colsums', allcols, cat=pulp.LpContinuous)
for c in allcols:
    prob += colsums[c] == sum(mat[r][c]*rowselected[r] for r in allrows)

# This is our objective - maximimise this
maxvalue = pulp.LpVariable('maxvalue')
prob += maxvalue

# The tricky part - maximise subject to being less than each of these differences
# I'm relatively confident that all these constraints are equivalent
# to calculating the maximum and subtracting that
for c1 in allcols:
    for c2 in allcols[:c1]:
        prob += maxvalue <= colsums[c1] - colsums[c2]

# choose at least one row
prob += pulp.lpSum(rowselected) >= 1

prob.solve()

print(prob.objective.value())

for c in allrows:
    print(rowselected[c].value())

Answer 2

我选择使用我自己的 Evolutionary algorithm 版本，它对我来说更直观，而且你可以玩弄人口规模、世代和变异概率：

from random import choice, random

def stack_overflow_example(self):
    def fitness(trial):
        trial_max = self.func(trial, mat)
        if trial_max > self.best_res:
            self.best_res = trial_max
            return trial_max
        else:
            return -sys.maxint

    def mutate(parent):
        mutation = []
        for p in parent:
            if random() < prob:
                mutation.append(choice([0, 1]))
            else:
                mutation.append(p)
        return mutation

    l1 = [3, 4, 7, -2]
    l2 = [0.5, 3, 6, 2.7]
    l3 = [0, 5, 8, 3.6]
    mat = [l1, l2, l3]

    max_num_of_loops = 1000
    prob = 0.075  # mutation probability
    gen_size = 10  # number of children in each generation
    self.bin_parent = [1] * len(mat)  # first parent all ones
    self.best_res = self.func(self.bin_parent, mat)  # starting point for comparison
    for _ in xrange(max_num_of_loops):
        backup_parent = self.bin_parent
        copies = (mutate(self.bin_parent) for _ in xrange(gen_size))
        self.bin_parent = max(copies, key=fitness)
        res = self.func(self.bin_parent, mat)
        if res >= self.best_res:
            self.best_res = res
            print (">> " + str(res))
        else:
            self.bin_parent = backup_parent
    print("Final result: " + str(self.best_res))
    print("Chosen lists:")
    chosen_lists = self.choose_strategies(self.bin_parent, mat)
    for i, li in enumerate(chosen_lists):
        print(">> list[{}] : values: {}".format(i, li))

def func(self, bin_list, mat):
    chosen_mat = self.bin_list_to_mat(bin_list, mat)
    if len(chosen_mat) == 0:
        return -sys.maxint
    # doing some math between lists:
    sum_list = list(chosen_mat[0])
    for li in chosen_mat[1:]:
        sum_list = map(operator.add, sum_list, li)
    accum_min_lst = []
    for i, val in enumerate(sum_list):
        x = sum_list[:i + 1]
        accum_min_lst.append(val - max(x))
    return min(accum_min_lst)

@staticmethod
def bin_list_to_mat(bin_list, mat):
    chosen_lists = []
    for i, stg in enumerate(mat):
        if bin_list[i] == 1:
            chosen_lists.append(stg)
    return chosen_lists

希望它能对某人有所帮助 :) 因为我花了一段时间才找到这个解决方案。

寻找具有最大函数值的列表的最佳组合

Finding the best combination of lists with maximum function value

python

mathematical-optimization

discrete-mathematics

scipy

cvxopt