Поиск наилучшей комбинации списков с максимальным значением функции

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 или, может быть, scipy.optimize.minimize , но я считаю, что это трудно понять вид функции мне нужно использовать для моей проблемы, мысли, может быть, я должен попробовать эволюционный алгоритм, чтобы найти приблизительный ответ, Или, может быть, я должен использовать вместо этого portfolio optimization.

Answer 1

Я решил использовать свою собственную версию 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 

Надеюсь, что это поможет кому-то :), потому что мне понадобилось некоторое время, чтобы найти это решение.

Answer 2

Это можно сформулировать как 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())