Optaplanner規劃引擎的工作原理及簡單示例(1)

來自專欄 APS-高級計劃與排程

在之前的文章中，老猿已介紹過APS及規劃的相關內容，也對Optaplanner相關的概念和一些使用示例進行過介紹，接下來的文章中，我會自己做一個規劃小程序 - 一個關於把任務分配到不同的機台上進行作來的小程序，並在這個小程序的基礎上對Optaplanner中更多的概念，功能，及使用方法進行講解。但在此之前，我需要先講解一下Optaplanner在運行規則運算的原理。所以，本文是講述一些關於尋找最優解的過程中的原理性的內容，作為後續通過示例深入講解的基礎。但這些原理知識不會涉及過分深奧的數學演算法，畢竟我們的目標不是寫一個新的規劃引擎出來，只是理解一些概念，用於理解Optaplanner是依據什麼找出一個相對優解的。好讓在接下來的一系列文章中，可以快速無障礙地理解我所講解的更細化的Optaplanner功能。

　　好了，言歸正傳，本文主要是講述Optaplanner是如何在用戶定義的規則限制條件中，基於約束的限制，對被規劃對象進行排列組合，再對比各個組合（稱作解，或方案），並找出相對最優的解出來。在這個尋優過程中，Optaplanner會使用到一些相關演算法，例如啟發式演算法（例如First Fit）和延遲接受法（例如禁忌搜索），從而提高尋找相對最優解的效率和防止嵌入局部最優解，從而可以在固定的時間內，找到儘可能優的方案。

　　在理解Optapalnner是如何實現之前，我們先複習並展開一下上一篇提到的概念 - 約束。

約束（Constraint）:

　　也就是對事物的一種限制，規定事物的發展應該遵循什麼規則，具體到Optaplanner里，就是用於表達出什麼是對的，什麼是錯的，什麼情況是最優，什麼情況次優，什麼情況較差。從而讓引擎得到各個解的對比依據。

　　在Optapalnner中的約束可以分為硬約束和軟約束兩種，其實還有更多的約束類型 ，例如中間約束，甚至是無限層級的約束，但總結起來,其作用也就是把約束劃分為不同層級，從而區分出不同的優等級而已，如果有軟體開發經驗的同學，可以理解不同層級的約束，分別是SQL語句里Order By子句後面的欄位次序。在進行記錄排序時，前面的欄位排列的優先順序，是從性質上優先於後面的欄位的，大家理解了Order By子句，也就理解了不同層級約束的問題了。拉下來我們以最簡單的軟硬約束，來分析一下約束的作用。

硬約束：

　　硬約束是用來規定什麼情況是對的，什麼情況是錯的；什麼組合是好的，什麼組合是不好的......也就是它通常是用來對所得的解進行一些定性的狀態定義。例如一個計劃是否可行，例如會不會同一個機台同一個時間分配了兩個不同的任務（假設每個機台同時只能做同一個任務）。一個員工所排班次是否正確（例如一個員工是否被安排了三個連續的班次）。若出現上種情況，即表示違反了硬約束，這種方案稱作不可行方案。以後的文章里，會提到Optaplanner里有一個明確的概念 - Feasable Solution(可行方案，或稱可行解)，就是表示這個方案是完全符合硬約束的。

軟約束：

　　軟約束規定什麼情況最優，什麼情況次優，什麼情況是差的；它是用來定義方案優劣的定量狀態。例如：一個計劃的成本是否足夠低；一個排班表到底有多大程度上的合理性，例如一個人正常情況下是需要5天工作制的，但如果遇到特殊情況，也可以連續工作6天，但這種情況是特殊的，需要額外付加班費（成本上升）最好不要出現這種情況。那麼在編製這個排班表的時候，如果有一個方案是需要有人員連續工作6天，但如果找到另一個方案，可以令所有人均不需要連續工作6天，那麼，後面這個方案就比那些有人需要連續工作6天的方案更好了。體現在軟約束上，就是後面的排產表，其軟約束上會比前一個排班表更好，違反的軟約束更少。

　　上述講述的是兩種常見約束，那麼這些約束在Optaplanner里是如何生效的呢？那說需要有一種評分機制了，也是我們在使用Optaplanner里，比較難準確把握的一個內容之一。

評分機制：評分是用分數來評價事物特性的一種方法。但如果我們細心觀察總結一下，會發現評份是可以通過兩種方向來評價的；分別是正評分(獎勵性評分)和負評分(懲罰性評分)。

正評分：通過獲得分數的多少，來體現事物的優劣。例如我們在學校考試過程中，成績是通過一種正分數來體現的，即做對一題獎勵相應的分數，分數越高成績越好；完美狀態是獲得滿分。

負評分：通過扣除分數的多少，來體現事物的優劣。例如我們的駕駛證記分制，每違章一次就扣除相應的分數，很明顯這種評份體系中，分數越低越好，也就是扣得越少越好；完美狀態是扣0分。

　　在對實際問題進行約束規劃時，是一種封閉性約束，也就是約定事物往指定的一個方向發現，使用負評分的方式，很顯然更合理。也就是一個方案有哪些不好的，我們通過對它評定一些懲罰分數標準，告訴引擎這種組合出現了一些不太好的情況。如此類推，每找到一個更佳、扣分更少的方案，就離完美就更近一步。無論是使用正方向評份還是反方向評分（或稱負方向評分），在Optaplanner里都是可以實現的，只不過按我們日常的邏輯，在定義方案時，通常我們只會根據業務定義出一些規則，方案是需要守這些規則，當一個方案出現有違反規則時，就作出相應的懲罰性扣分；這種方法比當出現好的情況就加分更合理。因為我們的現實世界裡，"好"是可能無限好的，當問題足夠複雜，數據量足夠大，即問題規模夠大時，描述一個方案如何個好法，其實很難是一個定數。比描述一個方案如何個差法更難，因為前者可以是無限的，而後都就只需要我們定義好什麼是差的標準，一但問題範圍確定，它的最差情況（也就是最差的扣分情況）就有一個字數了。所以，在Optaplanner的世界裡，常見的做法是，定義一些約束，並設定相應的懲罰分數標準（即將約束量化），用來描述這個方案的制約因素，當這個約束實打破時，就作出懲罰性記分，那麼到最後，扣分越少的方案就越好。這就是Optaplanner實現尋優的最基本原理，但其實現是非常複雜的，會將問題劃分為很多種類，將尋優的過程劃分為多個階段，每個階段利用不同種類的演算法來提高找到更優方案的效率，每個階段有很多個步驟，每個步驟又有多個移動（沒錯，Optaplanner里就有Step與Move的概念，以後會詳解）；在以後的深入文章中，我會詳細把這個過程分析出來。

　　上面描述了硬約束、軟約束和評份機制。那麼如何將這兩種約束與這種評分機制關聯起來，令評分機制可以實現軟、硬約束呢？大家可能已想到，在Optaplanner給出了軟分數，硬分數的概念。在評分機制中，當出現一個方案違反了某個硬約束時，就給這個方案扣除這個約束相應的分數；同樣地，當該方案違反了一種軟約束時，就對該方案扣除該軟約束相應的分數。這兩個分數是分開處理的。因為通過它們對應的約束類別就知道，它們分別代表的性質不一樣，硬分數對應的硬約束，代表的是一種定性評價；即描述方案好不好，行不行，可不可取等，一旦被記扣硬分數，那就表示這個方案的性質就變了，由可行方案變成不可行方案。理想的方案是一個硬分都不能扣的，一旦扣了就是不可行方案了。有人問，那麼定義硬分數的分值有什麼用？直接給一個標識出來，將方案的可用性定義為True or False，分別代表是事有硬約束被違反不就行了嗎，多簡單呀，因為一旦為False就是不可用了，再去討論它扣了多少分，又有何意義呢？硬約束、硬分數不就是為了給方案定性而設立的嗎？何必還要記錄它的扣分量，多此一舉呢？

　　如果這樣想，就是一種不全面的想法了。因為大家需要明白，現實世界往往是很大程度是不完美的，但而對不完美，我們是放棄這個世界，還是在不完美中進行堅持，對這個不完美的世界，朝完美的方向進行改造呢？上面的說法就比較抽象比較虛了，舉個大家容易理解的例子。例如：刑法是用來懲罰犯罪的，在正常的法治社會中，犯罪對於一個人說，就相當於違反了硬約束（刑事處罰記錄是終身跟隨的）。也就是對於一個人來說，一生中是否觸犯過刑法，是一個定性的問題。那麼既然是定性問題，我們在設立刑法的時候，其對應的懲罰是不是只有一種就足夠了呢？例如凡是觸犯刑法，全部判死刑，那不就簡單得多啦？事實上人類社會是不可能這樣的，因為就算是觸犯了刑法（這個已經是定性問題），但罪行也有輕重之分的、對應了刑法的不同條款，有些罪名經過對罪犯的懲戒，是可以再給他一次機會的，也說就是說觸犯的刑法，是有輕重之分的，但性質不會變，他在國家司法機關的檔案里，永遠留有普被刑事處理的記錄。所以，這可以稱該種情況為定性範圍內的定量問題。就是一個人做錯了就是錯了，其性質已經定了，但犯的錯誤有多大，還得是一個定量問題。因此，硬約束對應的扣除硬的分數有多有少就不難理解了。就是我們的方案如果出現了違反硬約束、被扣除了硬分數的，它在Optaplanner上就是一個不可行方案了。但是在眾多的不可行方案里，其實還要區分哪個是更不可行，哪些其實只是違反了一點點，還是「稍為可行的」。回到我們的實際排程問題中，有可能客觀條件限制，我們所有排出來的方案（例如生產計劃、排班表、車輛調試線路圖）都是不可行的，例如：我們排生產計劃的時候，將交貨期延誤作為一種硬約束，但是現實的生產活動中，確確實實有可能無論你怎麼排，因為產能、資源限制等因素，你是不可能找到一個完完全全符合交期的生產計劃的，那麼這個時間我們就需要找出一個違反得最小的計划出來，作為可行計劃，視情況進行相應的修改並執行了。也就是說兩害相遇取其輕。

　　對於硬約束，除了上述講到，當出現有可能確實需要使用不可行方案作為執行計劃的情況外，在Optaplanner進行規則的過程中，其實也起到非常大作用的。先不說optaplanner引來來排程；如果讓你來排，對於各種硬約束，全都不給出一個分數，而是給一個定性的標識，就是一旦出現違反了，就報一個違反硬約束的消息出來，你會怎麼樣?你肯定會抱怨提示的信息太簡陋了，只有一個標識，最多只是知道哪裡違反了，再也沒有更詳細的信息供你參考了。那你接下來的排產活動，其實就是一個組合一個組合逐一地去碰彩了。因為各個方案之間是否有關聯，你是無法得知的，所以你根本找不到什麼好的辦法去將各種情況下的方案進行歸類、比較進行往指定的一個方向收斂。但如果在一個硬約束被違反時，會出現一些明確的信息，是哪個硬約束被違反了。違反和程度是多少，扣了多少分，是因為哪個被規則的對象，放在哪裡，或與哪個對象相鄰從而導致的硬約束被違反。這樣就形成了一個很明確指導方向，對於人而言，通過歸納統計就知道某些情況肯定會出現，或極大可能會出現違反硬約束的情況，那我們就可以在排列新方案時，儘力去避免這種情況了；也就是有了參考方向 。對於Optaplanner引擎來說也是同理，儘管它不像人這麼聰明（但最從近的消息來看，Optapalnner團隊已經著手思考人工智慧引入到引擎中，從而實現如上述人類一樣對這類問題進行歸納思考），但也能夠作為其尋找更佳方案的過程中的一些很重要的參考，從而為尋優演算法所用，進而提高尋優效率。例如遺傳演算法。

　　軟分數對應的軟約束，代表的是一種定量評價；即描述方案有多好、有多差，成本有多高、有多低。它是一種優化約束，即在定義它的時候，就已經知道它必然是被違反的（也有可能完全不違反，那當然是好的，但如果是這樣的話，就脫離了軟約束的初充了）。所以，軟體約束、軟體分數的扣分值用途相對來說就容易理解得多了。

　　 綜上所述，Optaplanner就是通過一種體現為分數的約束機制，進行尋找最優組合。當一個排產問題中，設定的軟硬兩種約束時，它會優先滿足硬約束的要求，再滿足軟約束的要求，也就是說，軟約束被扣為1萬分，也不及硬約束被扣了1分重要，聯繫上面的SQL語句中的Order By子句的例子。

　　Optaplanner其利用途徑有以下兩點：

1. 用分數來確定，一個方案是否可行，是優是劣；

2. 在決定每一步的時候，參考上一點的扣分情況，來確定下一次生成方法時，應該考慮哪此因素（想想遺傳演算法）.

　　這一篇我們先講解一下原理，打一下基礎，下一篇將用一個任務與機台的例子來說明一下這些原理在Optaplanner中是如何體現的。

推薦閱讀：