как минимизировать функцию с дискретными переменными значениями в scipy


Я пытаюсь оптимизировать целевую функцию, которая имеет несколько входных переменных (от 24 до 30). Эти переменные являются выборками из трех различных статистических переменных, а значения целевой функции-значениями вероятности t-критерия. Функция ошибки представляет собой ошибку (сумму квадратов разностей) между желаемой и фактической вероятностями t-критерия. Я могу принимать решения только там, где ошибка меньше 1e-8, для всех трех t-тестов.

Я использовал scipy.optimize.fmin и это сработало отличный. Существует множество решений, в которых целевая функция становится нулевой.

Проблема в том, что мне нужно найти решение, в котором переменные находятся между 0 и 10.0 и являются целыми числами или не имеют более одной дробной части. Примерами допустимых значений являются 0 10 3 5.5 6.8. Примеры недопустимых значений: -3 2.23 30или 0.16666667. Я случайно узнал, что существует по крайней мере одно решение, потому что целевые значения исходят из фактических измеренных данных. Исходные данные были утеряны, и моя задача найти их. Но я не знаю, как это сделать. Использование метода проб и ошибок-это не вариант, потому что для каждой переменной существует около 100 возможных значений, а учитывая количество переменных, число возможных случаев будет равно 100**30, что слишком много. Использование fmin отлично, однако оно не работает с дискретными значениями. Есть ли способ решить эту проблему? Это не проблема, если мне нужно запустить программу в течение многих часов, чтобы найти решение. Но мне нужно найти решения для примерно 10 целевых значений в течение нескольких дней. несколько дней, и у меня закончились новые идеи.

Вот пример MWE:

import math
import numpy
import scipy.optimize
import scipy.stats
import sys

def log(s):
    sys.stdout.write(str(s))
    sys.stdout.flush()

# List of target T values: TAB, TCA, TCB
TARGETS = numpy.array([
    [0.05456834,   0.01510358,    0.15223353   ],  # task 1 to solve
    [0.15891875,   0.0083665,     0.00040262   ],  # task 2 to solve
])
MAX_ERR = 1e-10 # Maximum error in T values
NMIN,NMAX = 8,10 # Number of samples for T probes. Inclusive.

def fsq(x, t, n):
    """Returns the differences between the target and the actual values."""
    a,b,c = x[0:n],x[n:2*n],x[2*n:3*n]
    results = numpy.array([
        scipy.stats.ttest_rel(a,b)[1], # ab
        scipy.stats.ttest_rel(c,a)[1], # ca
        scipy.stats.ttest_rel(c,b)[1]  # cb
    ])
    # Sum of squares of diffs
    return (results - t)

def f(x, t, n):
    """This is the target function that needs to be minimized."""
    return (fsq(x,t,n)**2).sum()

def main():
    for tidx,t in enumerate(TARGETS):
        print "============================================="
        print "Target %d/%d"%(tidx+1,len(TARGETS))
        for n in range(NMIN,NMAX+1):
            log(" => n=%s "%n)
            successful = False
            tries = 0
            factor = 0.1
            while not successful:
                x0 = numpy.random.random(3*n) * factor
                x = scipy.optimize.fmin(f,x0, [t,n], xtol=MAX_ERR, ftol=MAX_ERR )
                diffs = fsq(x,t,n)
                successful = (numpy.abs(diffs)<MAX_ERR).all()
                if successful:
                    log(" OK, error=[%s,%s,%s]n"%(diffs[0],diffs[1],diffs[2]))
                    print " SOLUTION FOUND "
                    print x
                else:
                    tries += 1
                    log(" FAILED, tries=%dn"%tries)
                    print diffs
                    factor += 0.1
                    if tries>5:
                        print "!!!!!!!!!!!! GIVING UP !!!!!!!!!!!"
                        break
if __name__ == "__main__":
    main()
1 7

1 ответ:

То, что вы пытаетесь сделать (если я правильно понял вашу установку), называется целочисленным программированием, и это NP-hard; http://en.wikipedia.org/wiki/Integer_programming я понимаю, что вы не ищете целочисленных решений, но если вы умножите все ваши входные данные на 10 и разделите целевую функцию на 100, вы получите эквивалентную задачу, в которой входные данные-все целые числа. Дело в том, что ваши входные сигналы дискретны.

Целевая функция, с которой вы работаете, является выпуклой, квадратичной функции, и существуют хорошие алгоритмы ограниченной оптимизации, которые быстро решат ее для вещественных входных данных в интервале [0, 10]. Из этого вы можете попытаться округлить или проверить все допустимые точки поблизости, но есть 2^n из них, где n-количество входов. Даже если вы сделаете это, оптимальное решение не будет гарантированно одним из этих пунктов.

Существуют алгоритмы аппроксимации для задач целочисленного программирования, и вы можете обнаружить, что иногда один из них работает хорошо достаточно, чтобы привести вас к оптимальной точке. Есть список вещей, которые вы можете попробовать в статье Википедии, которую я процитировал, но я не знаю, будете ли вы счастливы, пытаясь решить эту проблему.