scipy

Question

'da kesikli değişken değerleri olan bir işlevi en aza indirme nasıl birden fazla giriş değişkenine sahip bir hedef işlevi en iyi duruma getirmeye çalışıyorum (24 ile 30 arası). Bu değişkenler üç farklı istatistiksel değişkenin örnekleridir ve hedef fonksiyon değerleri t-testi olasılık değerleridir. Bir hata fonksiyonu, istenen ve gerçek t-testi olasılıkları arasındaki hatayı (farkların kareleri toplamını) temsil eder. Sadece üç t-testinin tümü için hatanın 1e-8'den daha az olduğu çözümleri kabul edebilirim.

scipy.optimize.fmin kullanıyordum ve harika çalıştı. Hedef fonksiyonun sıfır olduğu birçok çözüm var. Sorun, değişkenlerin 0 ile 10.0 arasında olduğu ve tam sayılar olduğu veya birden fazla rakamlı kesirli kısma sahip olmadığı bir çözüm bulmam gerektiğidir. Geçerli değerlerin örnekleri 0 10 3 5.5 6.8'dur. Geçersiz değer örnekleri: -3 2.23 30 veya 0.16666667.

En az bir çözümün olduğunu biliyorum çünkü hedef değerler gerçek ölçülen verilerden geliyor. Orijinal veriler kayboldu ve benim görevim onları bulmak. Ama nasıl olduğunu bilmiyorum. Deneme/hata kullanmak bir seçenek değildir, çünkü her değişken için yaklaşık 100 olası değer vardır ve değişken sayısı göz önüne alındığında, olası vaka sayısı 100 ** 30 olacaktır ve bu çok fazladır. Fmin kullanmak harikadır, ancak gizli değerler ile çalışmaz.

Bunu çözmenin bir yolu var mı? Bir çözüm bulmak için bir saatlerce program çalıştırmam gerekirse sorun değil. Ancak, birkaç gün içinde yaklaşık 10 hedef değer için çözümler bulmam gerekiyor ve yeni fikirlerin dışındayım. İşte

bir örnek MWE geçerli:

tamsayı programlama denir ve NP-zor olduğunu Ne (Ben senin kurulum anlaşılan varsa) yapmak çalışıyorsunuz

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=%d\n"%tries) 
        print diffs 
        factor += 0.1 
        if tries>5: 
         print "!!!!!!!!!!!! GIVING UP !!!!!!!!!!!" 
         break 
if __name__ == "__main__": 
    main() 

Answer 1

; http://en.wikipedia.org/wiki/Integer_programming. Tamsayı çözümleri aradığınızı anlıyorum, ancak tüm girişlerinizi 10 ile çarptığınızda ve hedef işlevinizi 100'e bölerseniz, girişlerin tam sayı olduğu durumlarda eşdeğer bir sorun elde edersiniz. Önemli olan, girişleriniz ayrık.

Üzerinde çalıştığınız hedef işlev, dışbükey, ikinci dereceden bir işlevdir ve [0, 10] aralığında gerçek değerli girişler için hızlı bir şekilde çözecek iyi kısıtlı optimizasyon algoritmaları vardır. Buradan yakındaki tüm kabul edilebilir noktaları yuvarlamayı veya kontrol etmeyi deneyebilirsiniz, ancak bunların n'si giriş sayısıdır. Bunu yapsanız bile, en uygun çözümün bu noktalardan biri olduğu garanti edilmez.

Tam sayı programlama sorunları için yaklaşık algoritmalar vardır ve bazen bunlardan birinin sizi en uygun noktaya getirecek kadar iyi çalıştığını görebilirsiniz. Aktardığım Vikipedi makalesinde deneyebileceğiniz bir şeyler listesi var, ancak bu sorunu çözmeye çalışmaktan mutluluk duyacağınızı bilmiyorum.