使用谷歌OR-工具的數(shù)學(xué)優(yōu)化指南
圖片由作者提供，表情符號(hào)由 OpenMoji(CC BY-SA 4.0)
線性編程是一種優(yōu)化具有多個(gè)變量和約束條件的任何問(wèn)題的技術(shù)。這是一個(gè)簡(jiǎn)單但強(qiáng)大的工具，每個(gè)數(shù)據(jù)科學(xué)家都應(yīng)該掌握。
想象一下，你是一個(gè)招募軍隊(duì)的戰(zhàn)略家。你有
- 三種資源。食物、木材和黃金
- 三個(gè)單位：?劍客，弓箭手，和馬兵。
騎士比弓箭手更強(qiáng)，而弓箭手又比劍客更強(qiáng)。下表提供了每個(gè)單位的成本和力量。
圖片由作者提供
現(xiàn)在我們有1200食物，800木材，600黃金。考慮到這些資源，我們應(yīng)該如何最大化我們的軍隊(duì)的力量？
我們可以簡(jiǎn)單地找到能效/成本比最好的單元，盡可能多地取用它們，然后用另外兩個(gè)單元重復(fù)這一過(guò)程。但這種 "猜測(cè)和檢查 "的解決方案甚至可能不是最優(yōu)的......
現(xiàn)在想象一下，我們有數(shù)以百萬(wàn)計(jì)的單位和資源：以前的貪婪策略很可能完全錯(cuò)過(guò)了最佳解決方案。使用機(jī)器學(xué)習(xí)算法（如遺傳算法）來(lái)解決這個(gè)問(wèn)題是可能的，但我們也不能保證解決方案是最優(yōu)的。
幸運(yùn)的是，有一種方法可以以最佳方式解決我們的問(wèn)題：線性編程（或稱線性優(yōu)化），它屬于 operations research(OR)的一部分。在這篇文章中，我們將用它來(lái)尋找劍客、弓箭手和騎兵的最佳數(shù)量，以建立具有最高力量的軍隊(duì)。
I. 求解器
在Python/ target=_blank class=infotextkey>Python中，有不同的線性編程庫(kù)，如多用途的SciPy、適合初學(xué)者的PuLP、詳盡的Pyomo，以及其他許多庫(kù)。
今天，我們將使用 google OR-Tools，它對(duì)用戶非常友好，帶有幾個(gè)預(yù)包裝的求解器，可以通過(guò)以下方式運(yùn)行本教程中的代碼 Google Colab notebook.
如果安裝不成功，請(qǐng)重新啟動(dòng)內(nèi)核并再試一次：它有時(shí)會(huì)失敗。¯_(ツ)_/¯
!python -m pip install --upgrade --user -q ortools
所有這些庫(kù)都有一個(gè)隱藏的好處：它們作為接口，可以用不同的求解器使用同一個(gè)模型。解算器如 Gurobi, Cplex，或 SCIP有他們自己的API，但是他們所創(chuàng)建的模型是與特定的求解器相聯(lián)系的。
OR-Tools允許我們使用一種抽象的（而且是相當(dāng)pythonic的）方式來(lái)為我們的問(wèn)題建模。然后我們可以選擇一個(gè)或幾個(gè)求解器來(lái)找到一個(gè)最佳解決方案。因此，我們建立的模型是高度可重復(fù)使用的
圖片由作者提供
OR-Tools帶有自己的線性規(guī)劃求解器，稱為GLOP（谷歌線性優(yōu)化包）。它是一個(gè)開源項(xiàng)目，由谷歌的運(yùn)籌學(xué)團(tuán)隊(duì)創(chuàng)建，用C++編寫。
其他求解器也是可用的，比如SCIP，這是一個(gè)優(yōu)秀的非商業(yè)求解器，創(chuàng)建于2005年，并更新和維護(hù)至今。我們也可以使用流行的商業(yè)選項(xiàng)，如Gurobi和Cplex。然而，我們需要將它們安裝在OR-Tools之上，并獲得適當(dāng)?shù)脑S可（這可能相當(dāng)昂貴）。現(xiàn)在，讓我們?cè)囋嘒LOP。
# Import OR-Tools wrApper for linear programming
from ortools.linear_solver import pywraplp
# Create a solver using the GLOP backend
solver = pywraplp.Solver('Maximize army power', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
II.變量
我們使用GLOP創(chuàng)建了一個(gè)OR-Tools求解器的實(shí)例。現(xiàn)在，如何使用線性編程？我們要定義的第一件事是我們要優(yōu)化的變量。
在我們的例子中，我們有三個(gè)變量：軍隊(duì)中的?劍士、弓箭手和馬兵的數(shù)量。OR-Tools接受三種類型的變量。
- NumVar用于連續(xù)變量。
- IntVar用于整數(shù)變量。
- BoolVar用于布爾變量。
我們正在尋找單位的整數(shù)，所以讓我們選擇IntVar。然后我們需要為這些變量指定下限和上限。我們希望至少有0個(gè)單位，但我們并沒(méi)有真正的上限。所以我們可以說(shuō)，我們的上界是無(wú)窮大（或任何我們永遠(yuǎn)不會(huì)達(dá)到的大數(shù)字）。它可以被寫成。
讓我們把它翻譯成代碼。在OR-Tools中，Infinity被solver.infinity()所取代。除此以外，語(yǔ)法是非常直接的。
# Create the variables we want to optimize
swordsmen = solver.IntVar(0, solver.infinity(), 'swordsmen')
bowmen = solver.IntVar(0, solver.infinity(), 'bowmen')
horsemen = solver.IntVar(0, solver.infinity(), 'horsemen')
?? III.限制條件
我們定義了我們的變量，但約束條件也同樣重要。
也許與直覺相反的是，增加更多的約束條件有助于求解器更快地找到最優(yōu)解。為什么會(huì)出現(xiàn)這種情況呢？把求解器想象成一棵樹：約束條件幫助它修剪分支，減少搜索空間。
在我們的案例中，我們可以用來(lái)生產(chǎn)單位的資源數(shù)量有限。換句話說(shuō)，我們不能花費(fèi)超過(guò)我們所擁有的資源：例如，用于招募單位的食物不能高于1200。木材（800）和黃金（600）的情況也是如此。
根據(jù)我們的表格，單位有以下成本。
- 1個(gè)劍客 = 60 + 20。
- 1弓箭手 = 80 + 10 + 40。
- 1個(gè)騎士=140 + 100。
我們可以為每個(gè)資源寫一個(gè)約束條件，如下所示。
在OR-Tools中，我們只需用solver.Add()將約束添加到我們的求解器實(shí)例中。
# Add constraints for each resource
solver.Add(swordsmen*60 + bowmen*80 + horsemen*140 <= 1200) # Food
solver.Add(swordsmen*20 + bowmen*10 <= 800) # Wood
solver.Add(bowmen*40 + horsemen*100 <= 600) # Gold
IV.目標(biāo)
現(xiàn)在我們有了我們的變量和約束條件，我們要定義我們的目標(biāo)（或目標(biāo)函數(shù)）。
在線性編程中，這個(gè)函數(shù)必須是線性的（就像約束條件一樣），所以形式為ax + by + cz + d。在我們的例子中，目標(biāo)很明確：我們想招募具有最高力量的軍隊(duì)。表格給了我們以下的力量值。
- 1個(gè)劍客=70。
- 1個(gè)弓箭手=95。
- 1個(gè)騎士=230。
軍隊(duì)力量的最大化相當(dāng)于每個(gè)單位的力量之和的最大化。我們的目標(biāo)函數(shù)可以寫成。
一般來(lái)說(shuō)，只有兩種類型的目標(biāo)函數(shù)：最大化或最小化。在OR-Tools中，我們用以下方式聲明這個(gè)目標(biāo) solver.Maximize()或 solver.Minimize().
solver.Maximize(swordsmen*70 + bowmen*95 + horsemen*230)
然后我們就完成了!對(duì)任何線性優(yōu)化問(wèn)題進(jìn)行建模有三個(gè)步驟。
- 用下限和上限 聲明要優(yōu)化的變量。
- 為這些變量 添加約束。
- 定義最大化或最小化的 目標(biāo)函數(shù)。
現(xiàn)在已經(jīng)很清楚了，我們可以要求求解器為我們找到一個(gè)最佳解決方案。
五、優(yōu)化!
計(jì)算最優(yōu)解是通過(guò) solver.Solve() .這個(gè)函數(shù)返回一個(gè)狀態(tài)，可以用來(lái)檢查解決方案是否確實(shí)是最優(yōu)的。
讓我們以最佳的軍隊(duì)配置來(lái)打印我們能得到的最高總能效
status = solver.Solve()
# If an optimal solution has been found, print results
if status == pywraplp.Solver.OPTIMAL:
print('================= Solution =================')
print(f'Solved in {solver.wall_time():.2f} milliseconds in {solver.iterations()} iterations')
print()
print(f'Optimal power = {solver.Objective().Value()} power')
print('Army:')
print(f' - ?Swordsmen = {swordsmen.solution_value()}')
print(f' - Bowmen = {bowmen.solution_value()}')
print(f' - Horsemen = {horsemen.solution_value()}')
else:
print('The solver could not find an optimal solution.')
================= Solution =================
Solved in 87.00 milliseconds in 2 iterations
Optimal power = 1800.0 power
Army:
- ?Swordsmen = 6.0000000000000036
- Bowmen = 0.0
- Horsemen = 5.999999999999999
很好!解算器找到了一個(gè)最優(yōu)解：我們的軍隊(duì)總兵力為1800，有6個(gè)?劍士和6個(gè)騎兵（對(duì)不起，弓箭手！）。
讓我們來(lái)解讀這個(gè)結(jié)果。
- 解算器決定采取最大數(shù)量的騎兵（6，因?yàn)槲覀冎挥?00，而且他們每個(gè)人都要花費(fèi)100）。
- 剩余的資源用于?劍客：我們還有1200-6*140=360食物，這就是為什么解算器選擇6?劍客的原因 。
- 我們可以推斷出，騎兵是最好的單位，而弓箭手是最差的，因?yàn)樗麄兏緵](méi)有被選中。
好的，但有一點(diǎn)很奇怪：這些數(shù)字不是圓的，盡管我們指定要整數(shù)（IntVar）。那么發(fā)生了什么？
不幸的是，回答這個(gè)問(wèn)題需要深入研究線性編程......為了在這個(gè)介紹中保持簡(jiǎn)單，讓我們說(shuō)這是因?yàn)镚LOP的原因。解算器有我們必須考慮到的特性，而GLOP并不處理整數(shù)。這又證明了建立可重復(fù)使用的模型不僅僅是方便。
我們將解釋為什么GLOP會(huì)有這種奇怪的行為，以及如何在 "我的 "中修復(fù)它。
總結(jié)
我們通過(guò)這個(gè)例子看到了任何線性優(yōu)化問(wèn)題的五個(gè)主要步驟。
- 選擇一個(gè)求解器：在我們的案例中，為了方便，我們選擇了GLOP。
- 聲明變量：要優(yōu)化的參數(shù)是劍士、弓箭手和騎兵的數(shù)量。
- 宣布約束條件：這些單位中的每一個(gè)都有成本。總成本不能超過(guò)我們有限的資源。
- 定義目標(biāo)：要最大化的標(biāo)準(zhǔn)是這支軍隊(duì)的總力量。它也可以是其他的東西，比如單位的數(shù)量。
- 優(yōu)化。GLOP在不到一秒鐘的時(shí)間內(nèi)找到了這個(gè)問(wèn)題的最佳解決方案。
圖片由作者提供
這是線性規(guī)劃的主要好處：算法給我們一個(gè)保證，即找到的解決方案是最優(yōu)的（有一定誤差）。這種保證很強(qiáng)大，但也有代價(jià)：模型可能非常復(fù)雜，以至于求解器需要花費(fèi)數(shù)年（或更多）的時(shí)間來(lái)找到一個(gè)最優(yōu)解。在這種情況下，我們有兩個(gè)選擇。
- 我們可以在一定時(shí)間后停止求解器（并可能得到一個(gè)次優(yōu)答案）。
- 我們可以使用像遺傳算法這樣的元啟發(fā)式方法，在短時(shí)間內(nèi)計(jì)算出一個(gè)優(yōu)秀的解決方案。
