SciPy (сай бялуу гэж нэрлэдэг) нь C болон Fortran номын сангуудыг багтаасан numpy-д суурилсан математикийн багц юм. SciPy нь таны интерактив Python сессийг MATLAB, IDL, Octave, R, эсвэл SciLab гэх мэт бүрэн мэдээллийн шинжлэх ухааны орчин болгон хувиргадаг.
Энэ нийтлэлд бид математикийн програмчлалын үндсэн аргуудыг авч үзэх болно - scipy.optimize багцыг ашиглан хэд хэдэн хувьсагчийн скаляр функцийн нөхцөлт оновчлолын асуудлыг шийдвэрлэх. Хязгаарлагдаагүй оновчлолын алгоритмуудыг аль хэдийн хэлэлцсэн
Танилцуулга
Scipy.optimize багц дахь нөхцөлт болон хязгаарлалтгүй оновчлолын асуудлыг шийдвэрлэх нийтлэг интерфейсийг функцээр хангадаг. minimize()
. Гэсэн хэдий ч бүх асуудлыг шийдэх бүх нийтийн арга байдаггүй нь мэдэгдэж байгаа тул зохих аргыг сонгох нь үргэлж судлаачийн мөрөн дээр унадаг.
Тохирох оновчлолын алгоритмыг функцийн аргументыг ашиглан тодорхойлно minimize(..., method="")
.
Хэд хэдэн хувьсагчийн функцийг нөхцөлт оновчлохын тулд дараах аргуудыг хэрэгжүүлэх боломжтой.
trust-constr
- итгэлцлийн бүсэд орон нутгийн доод хэмжээг хайх.Wiki нийтлэл ,Хабрегийн тухай нийтлэл ;SLSQP
— хязгаарлалттай дараалсан квадрат програмчлал, Лагранжийн системийг шийдэх Ньютоны арга.Wiki нийтлэл .TNC
- Таслагдсан Ньютон Хязгаарлагдмал, давталтын тоо хязгаарлагдмал, олон тооны бие даасан хувьсагчтай шугаман бус функцүүдэд сайн.Wiki нийтлэл .L-BFGS-B
— Бройден-Флетчер-Голдфарб-Шанно багийн арга, Хессиан матрицаас векторуудыг хэсэгчлэн ачаалсны улмаас санах ойн зарцуулалт багассан.Wiki нийтлэл ,Хабрегийн тухай нийтлэл .COBYLA
— Шугаман ойролцоолсон MARE хязгаарлагдмал оновчлол, шугаман ойролцоолсон хязгаарлагдмал оновчлол (градиент тооцоололгүйгээр).Wiki нийтлэл .
Сонгосон аргаас хамааран асуудлыг шийдвэрлэх нөхцөл, хязгаарлалтыг өөр өөрөөр тогтооно.
- ангийн объект
Bounds
L-BFGS-B, TNC, SLSQP, trust-constr аргуудын хувьд; - Жагсаалт
(min, max)
ижил аргуудын хувьд L-BFGS-B, TNC, SLSQP, trust-constr; - объект эсвэл объектын жагсаалт
LinearConstraint
,NonlinearConstraint
COBYLA, 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 матрицыг тооцоолохдоо маш их хүчин чармайлт шаарддаг, та анги ашиглаж болно HessianUpdateStrategy
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