SciPy (сай бялуу гэж нэрлэдэг) нь C болон Fortran номын сангуудыг багтаасан numpy-д суурилсан математикийн багц юм. SciPy нь таны интерактив Python сессийг MATLAB, IDL, Octave, R, эсвэл SciLab гэх мэт бүрэн мэдээллийн шинжлэх ухааны орчин болгон хувиргадаг.
Энэ нийтлэлд бид математикийн програмчлалын үндсэн аргуудыг авч үзэх болно - scipy.optimize багцыг ашиглан хэд хэдэн хувьсагчийн скаляр функцийн нөхцөлт оновчлолын асуудлыг шийдвэрлэх. Хязгаарлагдаагүй оновчлолын алгоритмуудыг аль хэдийн хэлэлцсэн . Scipy функцуудын талаар илүү нарийвчилсан, сүүлийн үеийн тусламжийг help() команд, Shift+Tab товчийг ашиглан авах боломжтой. .
Танилцуулга
Scipy.optimize багц дахь нөхцөлт болон хязгаарлалтгүй оновчлолын асуудлыг шийдвэрлэх нийтлэг интерфейсийг функцээр хангадаг. minimize(). Гэсэн хэдий ч бүх асуудлыг шийдэх бүх нийтийн арга байдаггүй нь мэдэгдэж байгаа тул зохих аргыг сонгох нь үргэлж судлаачийн мөрөн дээр унадаг.
Тохирох оновчлолын алгоритмыг функцийн аргументыг ашиглан тодорхойлно minimize(..., method="").
Хэд хэдэн хувьсагчийн функцийг нөхцөлт оновчлохын тулд дараах аргуудыг хэрэгжүүлэх боломжтой.
trust-constr- итгэлцлийн бүсэд орон нутгийн доод хэмжээг хайх. , ;SLSQP— хязгаарлалттай дараалсан квадрат програмчлал, Лагранжийн системийг шийдэх Ньютоны арга. .TNC- Таслагдсан Ньютон Хязгаарлагдмал, давталтын тоо хязгаарлагдмал, олон тооны бие даасан хувьсагчтай шугаман бус функцүүдэд сайн. .L-BFGS-B— Бройден-Флетчер-Голдфарб-Шанно багийн арга, Хессиан матрицаас векторуудыг хэсэгчлэн ачаалсны улмаас санах ойн зарцуулалт багассан. , .COBYLA— Шугаман ойролцоолсон MARE хязгаарлагдмал оновчлол, шугаман ойролцоолсон хязгаарлагдмал оновчлол (градиент тооцоололгүйгээр). .
Сонгосон аргаас хамааран асуудлыг шийдвэрлэх нөхцөл, хязгаарлалтыг өөр өөрөөр тогтооно.
- ангийн объект
BoundsL-BFGS-B, TNC, SLSQP, trust-constr аргуудын хувьд; - Жагсаалт
(min, max)ижил аргуудын хувьд L-BFGS-B, TNC, SLSQP, trust-constr; - объект эсвэл объектын жагсаалт
LinearConstraint,NonlinearConstraintCOBYLA, SLSQP, trust-constr аргуудын хувьд; - толь бичиг эсвэл толь бичгийн жагсаалт
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}COBYLA, SLSQP аргуудын хувьд.
Нийтлэлийн тойм:
1) Итгэлцлийн бүсэд нөхцөлт оновчлолын алгоритмыг (method="trust-constr") объект болгон тодорхойлсон хязгаарлалттай ашиглах талаар авч үзэх. Bounds, LinearConstraint, NonlinearConstraint ;
2) Толь бичигт заасан хязгаарлалттай хамгийн бага квадратын аргыг (арга = "SLSQP") ашиглан дараалсан програмчлалыг авч үзье. {'type', 'fun', 'jac', 'args'};
3) Вэб студийн жишээг ашиглан үйлдвэрлэсэн бүтээгдэхүүнийг оновчтой болгох жишээнд дүн шинжилгээ хийх.
Нөхцөлт оновчлолын арга = "trust-constr"
Аргын хэрэгжилт trust-constr дээр суурилсан тэгш байдлын хэлбэрийн хязгаарлалттай асуудлууд болон бусад тэгш бус байдлын хэлбэрийн хязгаарлалттай асуудлуудын хувьд. Энэ хоёр аргыг итгэлийн бүсэд локал минимумыг олох алгоритмаар хэрэгжүүлдэг бөгөөд том хэмжээний асуудалд тохиромжтой.
Минимумыг олох асуудлыг ерөнхий хэлбэрээр математикийн томъёолол:
Тэгш байдлын хатуу хязгаарлалтын хувьд доод хязгаар нь дээд хязгаартай тэнцүү байна 
.
Нэг талын хязгаарлалтын хувьд дээд эсвэл доод хязгаарыг тогтооно np.inf харгалзах тэмдэгтэй.
Хоёр хувьсагчийн мэдэгдэж буй Розенброк функцийн хамгийн бага утгыг олох шаардлагатай болно.
Энэ тохиолдолд түүний тодорхойлолтод дараах хязгаарлалтууд тавигдана.
Манай тохиолдолд цэг дээр өвөрмөц шийдэл байдаг 
, зөвхөн эхний болон дөрөв дэх хязгаарлалт хүчинтэй байна.
Хязгаарлалтуудыг доороос дээш авч үзээд scipy дээр хэрхэн бичихийг харцгаая.
Хязгаарлалтууд 
и 
Bounds объектыг ашиглан тодорхойлъё.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Хязгаарлалтууд 
и 
Үүнийг шугаман хэлбэрээр бичье.
Эдгээр хязгаарлалтуудыг LinearConstraint объект гэж тодорхойлъё:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Эцэст нь матриц хэлбэрийн шугаман бус хязгаарлалт:
Бид энэ хязгаарлалтын хувьд Якобын матрицыг тодорхойлж, дурын вектортой Гессийн матрицын шугаман хослолыг тодорхойлно. 
:
Одоо бид шугаман бус хязгаарлалтыг объект гэж тодорхойлж болно NonlinearConstraint:
from scipy.optimize import NonlinearConstraint
def cons_f(x):
return [x[0]**2 + x[1], x[0]**2 - x[1]]
def cons_J(x):
return [[2*x[0], 1], [2*x[0], -1]]
def cons_H(x, v):
return v[0]*np.array([[2, 0], [0, 0]]) + v[1]*np.array([[2, 0], [0, 0]])
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=cons_H)Хэрэв хэмжээ нь том бол матрицыг сийрэг хэлбэрээр зааж өгч болно:
from scipy.sparse import csc_matrix
def cons_H_sparse(x, v):
return v[0]*csc_matrix([[2, 0], [0, 0]]) + v[1]*csc_matrix([[2, 0], [0, 0]])
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
jac=cons_J, hess=cons_H_sparse)эсвэл объект байдлаар LinearOperator:
from scipy.sparse.linalg import LinearOperator
def cons_H_linear_operator(x, v):
def matvec(p):
return np.array([p[0]*2*(v[0]+v[1]), 0])
return LinearOperator((2, 2), matvec=matvec)
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
jac=cons_J, hess=cons_H_linear_operator)Hessian матрицыг тооцоолохдоо 
маш их хүчин чармайлт шаарддаг, та анги ашиглаж болно . Дараах стратегиудыг ашиглах боломжтой. BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Хессианыг мөн хязгаарлагдмал зөрүүг ашиглан тооцоолж болно:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Хязгаарлалтын Якобын матрицыг мөн төгсгөлийн ялгааг ашиглан тооцоолж болно. Гэхдээ энэ тохиолдолд Хессийн матрицыг хязгаарлагдмал ялгааг ашиглан тооцоолох боломжгүй. Hessian нь функцээр эсвэл HessianUpdateStrategy классыг ашиглан тодорхойлогдох ёстой.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Оновчлолын асуудлыг шийдэх арга нь дараах байдалтай байна.
from scipy.optimize import minimize
from scipy.optimize import rosen, rosen_der, rosen_hess, rosen_hess_prod
x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)`gtol` termination condition is satisfied.
Number of iterations: 12, function evaluations: 8, CG iterations: 7, optimality: 2.99e-09, constraint violation: 1.11e-16, execution time: 0.033 s.
[0.41494531 0.17010937]Шаардлагатай бол Hessian-ийг тооцоолох функцийг LinearOperator класс ашиглан тодорхойлж болно.
def rosen_hess_linop(x):
def matvec(p):
return rosen_hess_prod(x, p)
return LinearOperator((2, 2), matvec=matvec)
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess_linop,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)эсвэл Hessian-ийн үржвэр ба параметрээр дамжуулан дурын вектор hessp:
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hessp=rosen_hess_prod,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)Эсвэл оновчтой болгож буй функцийн эхний болон хоёр дахь деривативуудыг ойролцоолж болно. Жишээлбэл, Гессианыг функцийг ашиглан ойролцоолуулж болно SR1 (бага Ньютоны ойролцоолсон). Градиентыг хязгаарлагдмал зөрүүгээр ойртуулж болно.
from scipy.optimize import SR1
res = minimize(rosen, x0, method='trust-constr', jac="2-point", hess=SR1(),
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)Нөхцөлт оновчлолын арга "SLSQP"
SLSQP арга нь функцийг багасгах асуудлыг шийдвэрлэхэд зориулагдсан:
Хаана 
и 
- тэгш буюу тэгш бус байдлын хэлбэрээр хязгаарлалтыг тодорхойлсон илэрхийллийн индексүүдийн багц. 
- функцийн тодорхойлолтын домэйны доод ба дээд хязгаарын багц.
Шугаман болон шугаман бус хязгаарлалтыг товчлуур бүхий толь бичиг хэлбэрээр дүрсэлсэн байдаг type, fun и jac.
ineq_cons = {'type': 'ineq',
'fun': lambda x: np.array ([1 - x [0] - 2 * x [1],
1 - x [0] ** 2 - x [1],
1 - x [0] ** 2 + x [1]]),
'jac': lambda x: np.array ([[- 1.0, -2.0],
[-2 * x [0], -1.0],
[-2 * x [0], 1.0]])
}
eq_cons = {'type': 'eq',
'fun': lambda x: np.array ([2 * x [0] + x [1] - 1]),
'jac': lambda x: np.array ([2.0, 1.0])
}Хамгийн бага хайлтыг дараах байдлаар гүйцэтгэнэ.
x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='SLSQP', jac=rosen_der,
constraints=[eq_cons, ineq_cons], options={'ftol': 1e-9, 'disp': True},
bounds=bounds)
print(res.x)Optimization terminated successfully. (Exit mode 0)
Current function value: 0.34271757499419825
Iterations: 4
Function evaluations: 5
Gradient evaluations: 4
[0.41494475 0.1701105 ]Оновчлолын жишээ
Тав дахь технологийн бүтцэд шилжсэнтэй холбогдуулан бага боловч тогтвортой орлого авчирдаг вэб студийн жишээн дээр үйлдвэрлэлийн оновчлолыг авч үзье. Бид өөрсдийгөө гурван төрлийн бүтээгдэхүүн үйлдвэрлэдэг галлерийн захирал гэж төсөөлөөд үз дээ.
- x0 - буух хуудас зарах, 10 tr-аас.
- x1 - корпорацийн вэбсайтууд, 20 tr-аас.
- x2 - онлайн дэлгүүрүүд, 30 tr-аас.
Манай найрсаг ажлын багт дөрвөн бага, хоёр дунд, нэг ахлах зэрэг багтдаг. Тэдний сарын ажлын цагийн сан:
- Зургадугаар сар:
4 * 150 = 600 чел * час, - дунд хэсэг:
2 * 150 = 300 чел * час, - дарга:
150 чел * час.
Эхний боломжтой бага насныханд (x0, x1, x2), дунд (10, 20, 30), ахлах (7, 15, 20) төрлийн нэг сайтыг хөгжүүлэх, байрлуулахад (5, 10, 15) цаг зарцуул. ) таны амьдралын хамгийн сайхан цаг.
Аливаа энгийн захирлын нэгэн адил бид сар бүр ашгаа нэмэгдүүлэхийг хүсдэг. Амжилтанд хүрэх эхний алхам бол зорилгын функцийг бичих явдал юм value сард үйлдвэрлэсэн бүтээгдэхүүний орлогын хэмжээгээр:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Энэ нь алдаа биш бөгөөд хамгийн ихийг хайхдаа зорилгын функцийг эсрэг тэмдгээр багасгадаг.
Дараагийн алхам бол ажилчдаа хэт их ажиллахыг хориглож, ажлын цагийг хязгаарлах явдал юм.
Үүнтэй ижил зүйл юу вэ:
ineq_cons = {'type': 'ineq',
'fun': lambda x: np.array ([600 - 10 * x [0] - 20 * x [1] - 30 * x[2],
300 - 7 * x [0] - 15 * x [1] - 20 * x[2],
150 - 5 * x [0] - 10 * x [1] - 15 * x[2]])
}Албан ёсны хязгаарлалт нь бүтээгдэхүүний гарц нь зөвхөн эерэг байх ёстой.
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Эцэст нь хэлэхэд, хамгийн ягаан таамаглал бол хямд үнэ, өндөр чанараас болж сэтгэл ханамжтай үйлчлүүлэгчдийн дараалал бидний төлөө байнга зогсдог. Хязгаарлагдмал оновчлолын асуудлыг шийдвэрлэхэд үндэслэн бид сарын үйлдвэрлэлийн хэмжээг өөрсдөө сонгох боломжтой scipy.optimize:
x0 = np.array([10, 10, 10])
res = minimize(value, x0, method='SLSQP', constraints=ineq_cons, bounds=bnds)
print(res.x)[7.85714286 5.71428571 3.57142857]Бүхэл тоо хүртэл дугуйруулж, бүтээгдэхүүний оновчтой хуваарилалтаар сэлүүрчдийн сарын ачааллыг тооцоолъё. x = (8, 6, 3) :
- Зургадугаар сар:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - дунд хэсэг:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - дарга:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Дүгнэлт: Захирал зохих дээд хэмжээгээ авахын тулд сард 8 буух хуудас, 6 дунд хэмжээний сайт, 3 дэлгүүр байгуулах нь оновчтой юм. Энэ тохиолдолд ахмад нь машинаас дээш харалгүйгээр хагалах ёстой, дунд хэсгийн ачаалал ойролцоогоор 2/3, багачууд хагасаас бага байх болно.
дүгнэлт
Нийтлэлд багцтай ажиллах үндсэн аргуудыг тусгасан болно scipy.optimize, нөхцөлт багасгах асуудлыг шийдвэрлэхэд ашигладаг. Би хувьдаа ашигладаг scipy Энэ нь зөвхөн эрдэм шинжилгээний зорилгоор хийгдсэн тул өгөгдсөн жишээ нь ийм комик шинж чанартай байдаг.
Олон тооны онол, виртуал жишээг жишээлбэл, И.Л.Акуличийн "Жишээ ба бодлого дахь математикийн програмчлал" номноос олж болно. Илүү хатуу програм scipy.optimize зурагны багцаас 3D бүтцийг бүтээх () -ээс үзэх боломжтой .
Мэдээллийн гол эх сурвалж нь энэ болон бусад хэсгийг орчуулахад хувь нэмрээ оруулах хүсэлтэй хүмүүс scipy Тавтай морил .
Спасибо хэвлэлийг бэлтгэхэд оролцсоны төлөө.
Эх сурвалж: www.habr.com
