之前的文章中，分别從APS，排産到規劃引擎叙述了一些理論基礎；并介紹了一些Optaplanner大概的情況；并一步步将Optaplanner的示例運作起來，将示例源碼導進Eclipse分析了一下它的Hello world入門示例，從本篇開始，我們将分步學習它的一些概念及用法。
什麼是Optaplanner
其實這個名稱是作者将這個引擎貢獻給了Jboss社群後，才使用的名，之前叫做Drools planner。沒錯，它就是結合Drools（一個開源規則引擎）一起應用的(也可以單獨使用)，Drools在這裡的作用主要是用來作編寫計分腳本，事實上完全可以抛開Drools，直接使用Optaplanner自己的API，通過Java代碼自己來計分，但這個難度就大得多。詳細情況計到相應的章節再細說。
名稱的字首應該是Optimize的詞根，或取近音吧，因為Optaplanner其實就是一個對待規劃的方案組合進行優化的引擎。好了，關于它的名稱就不花費太多的口水去深究，我們看看官方是怎麼定義Optaplanner的。"OptaPlanner is a constraint solver. It optimizes business resource planning use cases, such as Vehicle Routing, Employee Rostering, Cloud Optimization, Task Assignment, Job Scheduling, Bin Packing and many more. " - Optaplanner 是一個限制解決器，它可以優化業務資源，規劃各種案例，例如工廠中的房間排程，職員排班，雲優化，任務配置設定，工作排程，裝箱等相關的問題，例如下圖。
而我對Optaplanner的了解，它是一個Planning Engine - 規劃引擎，針對各行各業的業務需求，開發人員需要将一些業務規則翻譯成限制，并對業務場景中的實體進行抽象模組化，規劃引擎根據上述限制和模型對象進行規劃，找出一個相對最優化的方案出來傳回給使用者。其實如果需要規劃的業務對象不多（種類和數量都不多），規則不太複雜，人類是可以通過自己的經驗、推算和規則運作，得到一個可行方案的，甚至當問題規模足夠小的時候，是可以找到一個最優方案的。關于規劃問題，大家可以參考這個系統文章中的一篇入門介紹
《Optaplanner - 入門介紹》，裡面講到，規劃問題其實就是數學上的NP問題或NPC問題，目前資料世界對于這種問題，是沒有可用算法直接實作的，當問題足夠大的時候，隻能夠通過一些尋優算法（例如爬山算法，模拟退火及遺傳算法等）提高找到問題相對優解的機率。而Optaplanner正是一個內建了這類算法，實作快速趕尋找相對最優方案的引擎。它是一個輕量級的，可嵌入的規劃引擎，也就是說你可以在自己的程式中通過Jar包直接和相關的配置項來直接使用Optapalnner. 當然，當你需要一個獨立的，具有良好擴充性的規劃服務元件時，可以直接使用Optaplanner建立自己的規劃伺服器，通過Spring等架構，對外提供規劃服務。
Optaplanner是基于
Apache Software License.協定的，你可以直接使用它作為商業用途。并且它是使用純Java編寫的，最低功能要求下，隻需安裝一個JVM即可以使用Optapalnner了。并且它所有的包都可以從
Maven中央庫中獲得，即隻需要建立一個Maven項目，簡單配置好依賴項，就可以開始基于Optaplanner的開發了。
下面，就開始對Optaplanner中概念進行逐一講解.
什麼是規劃問題(Planning Problem)
規劃問題是 - 基于有限資源，及指定限制條件下達到優化目标（包括資源、排程安排等優化）.，例如：
- 最大化利潤
- 最小化對生态環境的影響
- 提高員工及客戶的滿意度
- ........
要實作這些目标，需要以下條件：
- 人員
- 時間
- 預算（資金)
- 實體資産（例如機台、汽車，電腦，建築等等）
下圖是Optaplanner官網對規劃問題的定義：
上面是對官網的一些翻譯。通俗地講,規劃問題就是：
1. 存在一堆對象，例如：任務、人員、資源等，以後稱作規劃實體 - 官方稱planning entity；
2. 還存在一些條件規則，例如：任務最遲需要什麼時候完成，人員每天最多隻能上班8小時，在指定的時間段内資源是有限的。以後稱限制 - 官方稱Constraint
3. 根據上述第2點的條件，對第1點所述的規劃實體進行資源配置設定和時間安排，例如,哪個任務應該安排在哪個機台上，在什麼時候開始作業；哪個人員安排在哪個工廠中的房間的哪個班次；哪種資源（例如：機台、原料等）需要確定在哪個時間送到哪個工廠中的房間等。
上述第3點所做的工作就是一個規劃的過程，也就是引擎會根據限制的限制和規劃實體的特性，對這些規劃實體進行時間或/和空間上的規劃；這個就是規劃過程。而我們面對的這些規劃實體和這些限制的結合體，就稱作規劃問題。例如：排定下個學期每個年級的課程表，令每個課程的老師不會出現同一時候配置設定到不同的班級上課。現有一堆外賣，規劃好各個騎手的取餐、送餐路線，令每個騎手都以盡量小的路程和時間成本送最多的單。這些都可以被視作規劃問題。
規劃實體與規劃變量（Planning Entity & Planning Variable）
我們知道，規劃問題，就是對一些規劃實體進規劃預計配置設定。例如編造排班表，是一個規劃問題，那麼抽象出來，一個勞工就是一個規劃實體(Planning Entity)了，它是被規劃的對象。而勞工在指定的時間在哪個工廠中的房間上班，就是這個規劃實體的規劃變量(Planning vaiable)了。是以，其實解決這個規劃問題的過程，就是針對每一個規劃實體，根據限制及每個規劃實體的情況，來給它的規劃變量設定适當的值，令到所有規劃實體的所有規劃變量的組合達到整體最優。即是設定每個勞工（規劃實體），在哪個時間，去哪個工廠中的房間上班（上班時間和工廠中的房間就是規劃變量）。
問題事實(Problem Fact)
問題事實是相對規則實體而言的，它也是一個業務實體，與規劃實體不同的是，它隻反映出業務情況，而在規劃的過程中，不會被規劃引擎進行修改。也就是說，問題事實隻是用于提供資料，輔助規劃引擎進行規劃運算的。在整個規劃過程，問題事實是隻讀的。例如規則班次計劃的時間，其中的班次是在開始規則之前已經确定的，是以“班次”這個業務實體隻會在規劃過程中，提供每個班次具體的時間等資訊，而不會改變的。那麼“班次”這個業務實體，就是一個問題事實。
限制（硬限制與軟限制）
上而我們把業務規則定義為限制，其實目前針對排程方面的規劃問題，主要是通過限制進行評分機制的尋優方法。限制就是根據業務規則抽象出來，針對規劃變量，在求解規劃問題時候的一種限制，或懲罰機制。也就是說，限制是用來制約引擎對規劃變量的指派行為的。例如一個人不可能有超過24個小時的可用時間。
硬限制：硬限制是指那些不能違反的限制，違反了就會出現不符合常理，即業務可能出現絕不允許的情況出現。例如上面提高，一個人不可能有超過24小時的可用時間（常理）；機台運作過程中，機修工不能進行維修工作（涉及安全生産問題，法律及業務有硬性要求。）。是以，硬限制可以被人視為是用于對規則行為進行定義的。
軟限制：軟限制是相對硬限制而言的，它是可違反的。設立軟限制之目的并不是不允許它違反，而是定量地制約規劃結果（結果，即是下面講到的解或方案）的發展方向，起到對規劃結果的偏向作用，即讓規則結果盡量向指定的一個方向偏衙。也就是說在滿足了硬限制的前提下，再對軟限制進行判斷，如果軟限制能不違反就最好，要是必須違反，違反得越少，所得的方案就越好。例如成本高低就是一種軟限制，生産營運中不可能不産生成本，那麼如果成本越低，那麼方案肯定越好，當然是在滿足了硬限制的前提下。
規劃問題其實是NP問題或NP-Hard問題
其實在
中已經有講解過關于NP或NP-Hard（那講到NPC問題），大家可以去參考一下那篇文章。這時概括地重述一下，NP或NP-Hard問題是問題以下條件的：
- 對于一個給定的規劃的結果（官網中稱作solution, 即是解），很容易在合理的時間内對其進行驗證是否可行。例如：課程表編排得正不正确，可以根據限制來核對一下就可以确定了，例如有沒有出現同一個時間内，一個老師被配置設定到不同的班級上課。
- 不存在一個可确定的方法，在合理的時間内找到一個最優解（這裡指的是絕對最優解）。這個也不難了解，對于這種沒有任何快捷方法找最優解的規劃問題，我們唯一的辦法就是把所有不同的組合情況全部排列出來，一個一個比較（即逐一枚舉），那必然是可以找到最優解的。但是，因為這種方法其實是一種暴力窮舉法，當問題非常複雜、且需要規劃的實體數量非常多時，它的時間複雜度是随着組合情況的增加，逞指數式上升的，暴力窮舉的方法是不可取的。
規劃問題布在巨量搜尋空間
搜尋空間：因為目前針對規劃問題，隻能通過搜尋的方式去尋找相對最優解，因為相對一些直接通過算法操作得到的辦法而言，規劃問題隻能将它的解一個一個地對比，逐漸收斂逼近的辦法來得到相對最優解。是以，你可以認為規劃問題的相對最優解是搜尋出來的，而且每一步搜尋都需要對限制進行運算；從所有經曆過的解中，找到相對最優一個。是以規劃問題存在一個搜尋空間的問題，即有多少種可能的解，就表示搜尋空間有多大。例如将3個任務配置設定到兩個機台上，存在多少種可能？大家可以自己去算，其實就是排列組合問題。
而對實際問題時，稍複雜的限制，稍多一點的規劃實體，最後得出的可能解的數量都是非常巨大的，很多問題其搜尋空間輕易就是一個天文數字。是以，如果對于所有規則問題，都是使用這些暴力枚舉的辦法，以現有世界上的計算機的算力，很多問題是沒辦法找到最優解的。
規劃問題的規模，即是規劃實體及每個實體的規劃變量的組合，例如時間、空間，及影響因素，及這些因素的所有情況組合。例如，如果上述所有實體，規劃的變量和所有因素，展開後的數量是M，而一個解是對其中的N個變量進行規劃，那麼有多少個解呢？其實就是M到N的排列P(M->N).當遇到實際問題的，這些組合的數量就是天文數字了。
可能解，可行解，相對最優解與絕對最優解
在規則問題中，需要清楚解的概念，在Optaplanner裡稱作solution, 即方案。在本系列文章中，解與方案是相同的意義，請注意。本猿隻是根據中文表達的習慣，在不同的場合以最順口的方式，視情況确定到底應用用“解”，還是“方案”來表述。
在接下來的一系列文章中，我在講解這些方案的過程中，會用到以下概念：
可能解：一個規劃問題的任意一個解都稱為可能解，也就是所有規則實體的所有規則變量，任意一個組合，都稱作一個可能解。例如配置設定勞工A，在1月20日晚班，到1号工廠中的房間；配置設定勞工A在1月20日晚班到2号工廠中的房間；分别是兩個不同的可能解，盡管它們的差别隻是配置設定到不同的工廠中的房間.而每個勞工的每個班次的工作工廠中的房間，正好是規劃變量。是以任意一個規劃變量的不同，都會産生不同的可能解。現在知道為什麼規劃問題存在巨量搜尋空間了吧？
可行解：可行解就是那些完全符合硬限制的解。即若存在一個解，它對任何一個硬限制都是符合的，則稱這個解為可行解。可行解是可能解的一個子集。可行解是可驗證的，隻要根據目前所有的硬限制，對解中的每一個規劃實體中的每個規劃變量，逐一核對，看是否符合所有硬限制，如果符合，那就表示這個解是可行解。
相對最優解：上面已經提，規劃問題的搜尋空間非常巨量，大多數情況下是不可能計算并比較所有解的值，再取得最佳方案（這個解就是絕對最優解）的。那以在我們固定的時間内，Optaplanner引擎幫我們找到的最優方案，就是稱作相對最優解了。大家來思考一下，相對最優解必然是可行解嗎？
絕對最優解：同樣的上面提到，就是所有可能解中最優的那個解，目前是沒有直接确定的算法，通過運算在合理的時間内去找到一個問題的絕對最優解的，是以要得到絕對最優解，隻有一個辦法，就是将所有可能解都周遊一次才能找到。當問題規模不算大的時候，以目前的CPU速度還是能實作的。但如果問題稍複雜一點，規劃實體和規劃變量稍多一點，那麼可能解的數量就是一個天文數字了，這種情況下是沒辦法完全周遊的。是以，在我們現實中，我們是無法得到絕對最優解的。其實更貼切地說，我們所得到的相對最優解，我們不知道它是不是絕對最優解。因為現在數學上還沒有辦法（除了周遊）證明一個相對最優解是否絕對最優。
本篇先介紹一下上述兩個概念，下一篇将我們再具體介紹其它概念。
原創不易，如果覺得文章對你有幫助，歡迎點贊、評論。文章有疏漏之處，歡迎批評指正。
歡迎轉載，轉載請注明原文連結：http://www.cnblogs.com/kentzhang/p/8800725.html
一個IT老農，先盡力好當兒子、丈夫和父親的責任，然後做點有趣的事。