在之前的文章中，老猿已介紹過(guò)APS及規(guī)劃的相關(guān)內(nèi)容，也對(duì)Optaplanner相關(guān)的概念和一些使用示例進(jìn)行過(guò)介紹，接下來(lái)的文章中，我會(huì)自己做一個(gè)規(guī)劃小程序 - 一個(gè)關(guān)于把任務(wù)分配到不同的機(jī)臺(tái)上進(jìn)行作來(lái)的小程序，并在這個(gè)小程序的基礎(chǔ)上對(duì)Optaplanner中更多的概念，功能，及使用方法進(jìn)行講解。但在此之前，我需要先講解一下Optaplanner在運(yùn)行規(guī)則運(yùn)算的原理。所以，本文是講述一些關(guān)于尋找最優(yōu)解的過(guò)程中的原理性的內(nèi)容，作為后續(xù)通過(guò)示例深入講解的基礎(chǔ)。但這些原理知識(shí)不會(huì)涉及過(guò)分深?yuàn)W的數(shù)學(xué)算法，畢竟我們的目標(biāo)不是寫一個(gè)新的規(guī)劃引擎出來(lái)，只是理解一些概念，用于理解Optaplanner是依據(jù)什么找出一個(gè)相對(duì)優(yōu)解的。好讓在接下來(lái)的一系列文章中，可以快速無(wú)障礙地理解我所講解的更細(xì)化的Optaplanner功能。

　　好了，言歸正傳，本文主要是講述Optaplanner是如何在用戶定義的規(guī)則限制條件中，基于約束的限制，對(duì)被規(guī)劃對(duì)象進(jìn)行排列組合，再對(duì)比各個(gè)組合（稱作解，或方案），并找出相對(duì)最優(yōu)的解出來(lái)。在這個(gè)尋優(yōu)過(guò)程中，Optaplanner會(huì)使用到一些相關(guān)算法，例如啟發(fā)式算法（例如First Fit）和延遲接受法（例如禁忌搜索），從而提高尋找相對(duì)最優(yōu)解的效率和防止嵌入局部最優(yōu)解，從而可以在固定的時(shí)間內(nèi)，找到盡可能優(yōu)的方案。

　　在理解Optapalnner是如何實(shí)現(xiàn)之前，我們先復(fù)習(xí)并展開(kāi)一下上一篇提到的概念 - 約束。

約束（Constraint）:

　　也就是對(duì)事物的一種限制，規(guī)定事物的發(fā)展應(yīng)該遵循什么規(guī)則，具體到Optaplanner里，就是用于表達(dá)出什么是對(duì)的，什么是錯(cuò)的，什么情況是最優(yōu)，什么情況次優(yōu)，什么情況較差。從而讓引擎得到各個(gè)解的對(duì)比依據(jù)。

　　在Optapalnner中的約束可以分為硬約束和軟約束兩種，其實(shí)還有更多的約束類型 ，例如中間約束，甚至是無(wú)限層級(jí)的約束，但總結(jié)起來(lái),其作用也就是把約束劃分為不同層級(jí)，從而區(qū)分出不同的優(yōu)等級(jí)而已，如果有軟件開(kāi)發(fā)經(jīng)驗(yàn)的同學(xué)，可以理解不同層級(jí)的約束，分別是SQL語(yǔ)句里Order By子句后面的字段次序。在進(jìn)行記錄排序時(shí)，前面的字段排列的優(yōu)先級(jí)，是從性質(zhì)上優(yōu)先于后面的字段的，大家理解了Order By子句，也就理解了不同層級(jí)約束的問(wèn)題了。拉下來(lái)我們以最簡(jiǎn)單的軟硬約束，來(lái)分析一下約束的作用。

硬約束：

　　硬約束是用來(lái)規(guī)定什么情況是對(duì)的，什么情況是錯(cuò)的；什么組合是好的，什么組合是不好的......也就是它通常是用來(lái)對(duì)所得的解進(jìn)行一些定性的狀態(tài)定義。例如一個(gè)計(jì)劃是否可行，例如會(huì)不會(huì)同一個(gè)機(jī)臺(tái)同一個(gè)時(shí)間分配了兩個(gè)不同的任務(wù)（假設(shè)每個(gè)機(jī)臺(tái)同時(shí)只能做同一個(gè)任務(wù)）。一個(gè)員工所排班次是否正確（例如一個(gè)員工是否被安排了三個(gè)連續(xù)的班次）。若出現(xiàn)上種情況，即表示違反了硬約束，這種方案稱作不可行方案。以后的文章里，會(huì)提到Optaplanner里有一個(gè)明確的概念 - Feasable Solution(可行方案，或稱可行解)，就是表示這個(gè)方案是完全符合硬約束的。

軟約束：

　　軟約束規(guī)定什么情況最優(yōu)，什么情況次優(yōu)，什么情況是差的；它是用來(lái)定義方案優(yōu)劣的定量狀態(tài)。例如：一個(gè)計(jì)劃的成本是否足夠低；一個(gè)排班表到底有多大程度上的合理性，例如一個(gè)人正常情況下是需要5天工作制的，但如果遇到特殊情況，也可以連續(xù)工作6天，但這種情況是特殊的，需要額外付加班費(fèi)（成本上升）最好不要出現(xiàn)這種情況。那么在編制這個(gè)排班表的時(shí)候，如果有一個(gè)方案是需要有人員連續(xù)工作6天，但如果找到另一個(gè)方案，可以令所有人均不需要連續(xù)工作6天，那么，后面這個(gè)方案就比那些有人需要連續(xù)工作6天的方案更好了。體現(xiàn)在軟約束上，就是后面的排產(chǎn)表，其軟約束上會(huì)比前一個(gè)排班表更好，違反的軟約束更少。

　　上述講述的是兩種常見(jiàn)約束，那么這些約束在Optaplanner里是如何生效的呢？那說(shuō)需要有一種評(píng)分機(jī)制了，也是我們?cè)谑褂肙ptaplanner里，比較難準(zhǔn)確把握的一個(gè)內(nèi)容之一。

評(píng)分機(jī)制：評(píng)分是用分?jǐn)?shù)來(lái)評(píng)價(jià)事物特性的一種方法。但如果我們細(xì)心觀察總結(jié)一下，會(huì)發(fā)現(xiàn)評(píng)份是可以通過(guò)兩種方向來(lái)評(píng)價(jià)的；分別是正評(píng)分(獎(jiǎng)勵(lì)性評(píng)分)和負(fù)評(píng)分(懲罰性評(píng)分)。

正評(píng)分：通過(guò)獲得分?jǐn)?shù)的多少，來(lái)體現(xiàn)事物的優(yōu)劣。例如我們?cè)趯W(xué)校考試過(guò)程中，成績(jī)是通過(guò)一種正分?jǐn)?shù)來(lái)體現(xiàn)的，即做對(duì)一題獎(jiǎng)勵(lì)相應(yīng)的分?jǐn)?shù)，分?jǐn)?shù)越高成績(jī)?cè)胶?#xff1b;完美狀態(tài)是獲得滿分。

負(fù)評(píng)分：通過(guò)扣除分?jǐn)?shù)的多少，來(lái)體現(xiàn)事物的優(yōu)劣。例如我們的駕駛證記分制，每違章一次就扣除相應(yīng)的分?jǐn)?shù)，很明顯這種評(píng)份體系中，分?jǐn)?shù)越低越好，也就是扣得越少越好；完美狀態(tài)是扣0分。

　　在對(duì)實(shí)際問(wèn)題進(jìn)行約束規(guī)劃時(shí)，是一種封閉性約束，也就是約定事物往指定的一個(gè)方向發(fā)現(xiàn)，使用負(fù)評(píng)分的方式，很顯然更合理。也就是一個(gè)方案有哪些不好的，我們通過(guò)對(duì)它評(píng)定一些懲罰分?jǐn)?shù)標(biāo)準(zhǔn)，告訴引擎這種組合出現(xiàn)了一些不太好的情況。如此類推，每找到一個(gè)更佳、扣分更少的方案，就離完美就更近一步。無(wú)論是使用正方向評(píng)份還是反方向評(píng)分（或稱負(fù)方向評(píng)分），在Optaplanner里都是可以實(shí)現(xiàn)的，只不過(guò)按我們?nèi)粘５倪壿?#xff0c;在定義方案時(shí)，通常我們只會(huì)根據(jù)業(yè)務(wù)定義出一些規(guī)則，方案是需要守這些規(guī)則，當(dāng)一個(gè)方案出現(xiàn)有違反規(guī)則時(shí)，就作出相應(yīng)的懲罰性扣分；這種方法比當(dāng)出現(xiàn)好的情況就加分更合理。因?yàn)槲覀兊默F(xiàn)實(shí)世界里，"好"是可能無(wú)限好的，當(dāng)問(wèn)題足夠復(fù)雜，數(shù)據(jù)量足夠大，即問(wèn)題規(guī)模夠大時(shí)，描述一個(gè)方案如何個(gè)好法，其實(shí)很難是一個(gè)定數(shù)。比描述一個(gè)方案如何個(gè)差法更難，因?yàn)榍罢呖梢允菬o(wú)限的，而后都就只需要我們定義好什么是差的標(biāo)準(zhǔn)，一但問(wèn)題范圍確定，它的最差情況（也就是最差的扣分情況）就有一個(gè)字?jǐn)?shù)了。所以，在Optaplanner的世界里，常見(jiàn)的做法是，定義一些約束，并設(shè)定相應(yīng)的懲罰分?jǐn)?shù)標(biāo)準(zhǔn)（即將約束量化），用來(lái)描述這個(gè)方案的制約因素，當(dāng)這個(gè)約束實(shí)打破時(shí)，就作出懲罰性記分，那么到最后，扣分越少的方案就越好。這就是Optaplanner實(shí)現(xiàn)尋優(yōu)的最基本原理，但其實(shí)現(xiàn)是非常復(fù)雜的，會(huì)將問(wèn)題劃分為很多種類，將尋優(yōu)的過(guò)程劃分為多個(gè)階段，每個(gè)階段利用不同種類的算法來(lái)提高找到更優(yōu)方案的效率，每個(gè)階段有很多個(gè)步驟，每個(gè)步驟又有多個(gè)移動(dòng)（沒(méi)錯(cuò)，Optaplanner里就有Step與Move的概念，以后會(huì)詳解）；在以后的深入文章中，我會(huì)詳細(xì)把這個(gè)過(guò)程分析出來(lái)。

　　上面描述了硬約束、軟約束和評(píng)份機(jī)制。那么如何將這兩種約束與這種評(píng)分機(jī)制關(guān)聯(lián)起來(lái)，令評(píng)分機(jī)制可以實(shí)現(xiàn)軟、硬約束呢？大家可能已想到，在Optaplanner給出了軟分?jǐn)?shù)，硬分?jǐn)?shù)的概念。在評(píng)分機(jī)制中，當(dāng)出現(xiàn)一個(gè)方案違反了某個(gè)硬約束時(shí)，就給這個(gè)方案扣除這個(gè)約束相應(yīng)的分?jǐn)?shù)；同樣地，當(dāng)該方案違反了一種軟約束時(shí)，就對(duì)該方案扣除該軟約束相應(yīng)的分?jǐn)?shù)。這兩個(gè)分?jǐn)?shù)是分開(kāi)處理的。因?yàn)橥ㄟ^(guò)它們對(duì)應(yīng)的約束類別就知道，它們分別代表的性質(zhì)不一樣，硬分?jǐn)?shù)對(duì)應(yīng)的硬約束，代表的是一種定性評(píng)價(jià)；即描述方案好不好，行不行，可不可取等，一旦被記扣硬分?jǐn)?shù)，那就表示這個(gè)方案的性質(zhì)就變了，由可行方案變成不可行方案。理想的方案是一個(gè)硬分都不能扣的，一旦扣了就是不可行方案了。有人問(wèn)，那么定義硬分?jǐn)?shù)的分值有什么用？直接給一個(gè)標(biāo)識(shí)出來(lái)，將方案的可用性定義為True or False，分別代表是事有硬約束被違反不就行了嗎，多簡(jiǎn)單呀，因?yàn)橐坏镕alse就是不可用了，再去討論它扣了多少分，又有何意義呢？硬約束、硬分?jǐn)?shù)不就是為了給方案定性而設(shè)立的嗎？何必還要記錄它的扣分量，多此一舉呢？

　　如果這樣想，就是一種不全面的想法了。因?yàn)榇蠹倚枰靼?#xff0c;現(xiàn)實(shí)世界往往是很大程度是不完美的，但而對(duì)不完美，我們是放棄這個(gè)世界，還是在不完美中進(jìn)行堅(jiān)持，對(duì)這個(gè)不完美的世界，朝完美的方向進(jìn)行改造呢？上面的說(shuō)法就比較抽象比較虛了，舉個(gè)大家容易理解的例子。例如：刑法是用來(lái)懲罰犯罪的，在正常的法治社會(huì)中，犯罪對(duì)于一個(gè)人說(shuō)，就相當(dāng)于違反了硬約束（刑事處罰記錄是終身跟隨的）。也就是對(duì)于一個(gè)人來(lái)說(shuō)，一生中是否觸犯過(guò)刑法，是一個(gè)定性的問(wèn)題。那么既然是定性問(wèn)題，我們?cè)谠O(shè)立刑法的時(shí)候，其對(duì)應(yīng)的懲罰是不是只有一種就足夠了呢？例如凡是觸犯刑法，全部判死刑，那不就簡(jiǎn)單得多啦？事實(shí)上人類社會(huì)是不可能這樣的，因?yàn)榫退闶怯|犯了刑法（這個(gè)已經(jīng)是定性問(wèn)題），但罪行也有輕重之分的、對(duì)應(yīng)了刑法的不同條款，有些罪名經(jīng)過(guò)對(duì)罪犯的懲戒，是可以再給他一次機(jī)會(huì)的，也說(shuō)就是說(shuō)觸犯的刑法，是有輕重之分的，但性質(zhì)不會(huì)變，他在國(guó)家司法機(jī)關(guān)的檔案里，永遠(yuǎn)留有普被刑事處理的記錄。所以，這可以稱該種情況為定性范圍內(nèi)的定量問(wèn)題。就是一個(gè)人做錯(cuò)了就是錯(cuò)了，其性質(zhì)已經(jīng)定了，但犯的錯(cuò)誤有多大，還得是一個(gè)定量問(wèn)題。因此，硬約束對(duì)應(yīng)的扣除硬的分?jǐn)?shù)有多有少就不難理解了。就是我們的方案如果出現(xiàn)了違反硬約束、被扣除了硬分?jǐn)?shù)的，它在Optaplanner上就是一個(gè)不可行方案了。但是在眾多的不可行方案里，其實(shí)還要區(qū)分哪個(gè)是更不可行，哪些其實(shí)只是違反了一點(diǎn)點(diǎn)，還是“稍為可行的”。回到我們的實(shí)際排程問(wèn)題中，有可能客觀條件限制，我們所有排出來(lái)的方案（例如生產(chǎn)計(jì)劃、排班表、車輛調(diào)試線路圖）都是不可行的，例如：我們排生產(chǎn)計(jì)劃的時(shí)候，將交貨期延誤作為一種硬約束，但是現(xiàn)實(shí)的生產(chǎn)活動(dòng)中，確確實(shí)實(shí)有可能無(wú)論你怎么排，因?yàn)楫a(chǎn)能、資源限制等因素，你是不可能找到一個(gè)完完全全符合交期的生產(chǎn)計(jì)劃的，那么這個(gè)時(shí)間我們就需要找出一個(gè)違反得最小的計(jì)劃出來(lái)，作為可行計(jì)劃，視情況進(jìn)行相應(yīng)的修改并執(zhí)行了。也就是說(shuō)兩害相遇取其輕。

　　對(duì)于硬約束，除了上述講到，當(dāng)出現(xiàn)有可能確實(shí)需要使用不可行方案作為執(zhí)行計(jì)劃的情況外，在Optaplanner進(jìn)行規(guī)則的過(guò)程中，其實(shí)也起到非常大作用的。先不說(shuō)optaplanner引來(lái)來(lái)排程；如果讓你來(lái)排，對(duì)于各種硬約束，全都不給出一個(gè)分?jǐn)?shù)，而是給一個(gè)定性的標(biāo)識(shí)，就是一旦出現(xiàn)違反了，就報(bào)一個(gè)違反硬約束的消息出來(lái)，你會(huì)怎么樣?你肯定會(huì)抱怨提示的信息太簡(jiǎn)陋了，只有一個(gè)標(biāo)識(shí)，最多只是知道哪里違反了，再也沒(méi)有更詳細(xì)的信息供你參考了。那你接下來(lái)的排產(chǎn)活動(dòng)，其實(shí)就是一個(gè)組合一個(gè)組合逐一地去碰彩了。因?yàn)楦鱾€(gè)方案之間是否有關(guān)聯(lián)，你是無(wú)法得知的，所以你根本找不到什么好的辦法去將各種情況下的方案進(jìn)行歸類、比較進(jìn)行往指定的一個(gè)方向收斂。但如果在一個(gè)硬約束被違反時(shí)，會(huì)出現(xiàn)一些明確的信息，是哪個(gè)硬約束被違反了。違反和程度是多少，扣了多少分，是因?yàn)槟膫€(gè)被規(guī)則的對(duì)象，放在哪里，或與哪個(gè)對(duì)象相鄰從而導(dǎo)致的硬約束被違反。這樣就形成了一個(gè)很明確指導(dǎo)方向，對(duì)于人而言，通過(guò)歸納統(tǒng)計(jì)就知道某些情況肯定會(huì)出現(xiàn)，或極大可能會(huì)出現(xiàn)違反硬約束的情況，那我們就可以在排列新方案時(shí)，盡力去避免這種情況了；也就是有了參考方向 。對(duì)于Optaplanner引擎來(lái)說(shuō)也是同理，盡管它不像人這么聰明（但最從近的消息來(lái)看，Optapalnner團(tuán)隊(duì)已經(jīng)著手思考人工智能引入到引擎中，從而實(shí)現(xiàn)如上述人類一樣對(duì)這類問(wèn)題進(jìn)行歸納思考），但也能夠作為其尋找更佳方案的過(guò)程中的一些很重要的參考，從而為尋優(yōu)算法所用，進(jìn)而提高尋優(yōu)效率。例如遺傳算法。

　　軟分?jǐn)?shù)對(duì)應(yīng)的軟約束，代表的是一種定量評(píng)價(jià)；即描述方案有多好、有多差，成本有多高、有多低。它是一種優(yōu)化約束，即在定義它的時(shí)候，就已經(jīng)知道它必然是被違反的（也有可能完全不違反，那當(dāng)然是好的，但如果是這樣的話，就脫離了軟約束的初充了）。所以，軟件約束、軟件分?jǐn)?shù)的扣分值用途相對(duì)來(lái)說(shuō)就容易理解得多了。

　　?綜上所述，Optaplanner就是通過(guò)一種體現(xiàn)為分?jǐn)?shù)的約束機(jī)制，進(jìn)行尋找最優(yōu)組合。當(dāng)一個(gè)排產(chǎn)問(wèn)題中，設(shè)定的軟硬兩種約束時(shí)，它會(huì)優(yōu)先滿足硬約束的要求，再滿足軟約束的要求，也就是說(shuō)，軟約束被扣為1萬(wàn)分，也不及硬約束被扣了1分重要，聯(lián)系上面的SQL語(yǔ)句中的Order By子句的例子。

　　Optaplanner其利用途徑有以下兩點(diǎn)：

1. 用分?jǐn)?shù)來(lái)確定，一個(gè)方案是否可行，是優(yōu)是劣；

2. 在決定每一步的時(shí)候，參考上一點(diǎn)的扣分情況，來(lái)確定下一次生成方法時(shí)，應(yīng)該考慮哪此因素（想想遺傳算法）.

　　這一篇我們先講解一下原理，打一下基礎(chǔ)，下一篇將用一個(gè)任務(wù)與機(jī)臺(tái)的例子來(lái)說(shuō)明一下這些原理在Optaplanner中是如何體現(xiàn)的。

?

一個(gè)IT老農(nóng)，先盡力好當(dāng)兒子、丈夫和父親的責(zé)任，然后做點(diǎn)有趣的事。

總結(jié)

以上是生活随笔為你收集整理的Optaplanner规划引擎的工作原理及简单示例(1)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。