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

　　在之前的文章中，老猿已介紹過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中是如何展現的。

一個IT老農，先盡力好當兒子、丈夫和父親的責任，然後做點有趣的事。