|
有很多不同的方法可以解決數(shù)學(xué)優(yōu)化問題。你可以使用貪心算法（Greedy algorithms）、約束規(guī)劃（Constraint programming）、混合整數(shù)規(guī)劃（Mixed integer programming）、遺傳算法（Genetic algorithms）、局部搜索（Local search）等。根據(jù)問題的規(guī)模和類型，以及期望的解的質(zhì)量，不同的技術(shù)可能會有不同的效果。 這篇文章概述不同的用于解決離散優(yōu)化問題的啟發(fā)式方法。首先，我將解釋描述一個優(yōu)化問題所需的三個組成部分。然后，我將解釋一些常見的且效果良好的搜索啟發(fā)式方法。 優(yōu)化問題 要數(shù)學(xué)地定義一個優(yōu)化問題，你需要以下三個組成部分：決策變量（Decision variables）、約束（Constraints）和目標(biāo)（Objective）。 讓我們來看一個簡單的例子。你是一家小型快遞公司老板，每送一個包裹你都會賺取不同的金額。送貨車的空間是有限的?？爝f公司希望在每次送貨中盡可能地送出總價值最高的包裹。你應(yīng)該選擇哪些包裹來配送呢？
決策變量 決策變量可以取不同的值。目標(biāo)是找到?jīng)Q策變量的最佳值。什么是最佳值？這取決于目標(biāo)和約束條件。在快遞例子中，每個包裹都有一個二元決策變量。如果包裹不會被送出，則變量為0；如果包裹會被送出，變量為1。 約束條件 約束條件是指限制解的范圍或規(guī)定哪些情況是不可接受的。通過正確地設(shè)置這些條件，你可以確保找到一個既符合實(shí)際需求又能夠在現(xiàn)實(shí)中實(shí)施的解決方案。在快遞例子中，你不能送出所有的包裹，因?yàn)樗拓涇嚨目臻g是有限的。如果送貨車的最大容量為600，你需要添加一個約束條件，確保選擇的包裹總和不超過這個限制。 目標(biāo) 目標(biāo)是在優(yōu)化問題中你想要最大化或最小化的部分?？爝f公司的目標(biāo)是選擇最有價值的包裹進(jìn)行配送。在目標(biāo)函數(shù)中，你希望最大化所選擇包裹的總價值。 如果問題定義得當(dāng)（即存在可行解），那么優(yōu)化問題總是存在至少一個最優(yōu)解的。找到這些最優(yōu)解之一可能很困難，尤其是當(dāng)問題規(guī)模大且復(fù)雜時。本文討論的所有技術(shù)并不能保證找到最優(yōu)解，但如果你正確應(yīng)用它們于大型問題，它們可能比使用約束或混合整數(shù)規(guī)劃技術(shù)的解更快。 優(yōu)化技術(shù) 你可以使用不同的啟發(fā)式方法（Heuristics）來解決優(yōu)化問題。這里，我將解釋其中一些方法。 我假設(shè)你已經(jīng)熟悉暴力求解法，它是嘗試所有可能的解并跟蹤最佳解的過程。另一種你可能知道的技術(shù)是動態(tài)規(guī)劃，它將問題分解為較小的子問題。當(dāng)問題規(guī)模較小時，暴力求解和動態(tài)規(guī)劃是完全可以使用的。但當(dāng)問題規(guī)模增加時，它們會耗時過長且效率低下。暴力求解和動態(tài)規(guī)劃并不是啟發(fā)式方法，因?yàn)樗鼈儾⒉粫p少搜索空間。你可以選擇將暴力求解與局部搜索或遺傳算法結(jié)合起來，通過系統(tǒng)地測試一個較小子集中的所有可能解（暴力求解）。 貪心算法 要解決快遞公司的問題，一個簡單的方法是使用貪心算法。它們提供了一個基線，并且能夠非?？焖俚亟o出解決方案。貪心算法的思路是，你不斷選擇包裹裝進(jìn)送貨車，但不是隨意選擇，而是從價值最高的包裹開始。你重復(fù)這個過程，依次選擇價值較高的包裹，直到送貨車的容量被完全利用。假設(shè)送貨車的最大容量是60，以下是我們選擇的包裹：
還有其他方法可以決定下一個包裹。通過將每個包裹的價值與其大小相除，可以得到每個包裹的單位尺寸的價值。你可以將其描述為價值密度。通過選擇單位尺寸價值最高的包裹，有可能提出更好的解決方案。
貪心算法的一個優(yōu)點(diǎn)是它速度快。但對于更復(fù)雜的問題，在大多數(shù)情況下，解遠(yuǎn)非最優(yōu)。 局部搜索 局部搜索非常直觀。它的工作原理如下：你從一個初始解開始，通過逐步對這個解進(jìn)行小幅調(diào)整來提高它的效果。每次調(diào)整都是為了使目標(biāo)函數(shù)的值更高。你不斷重復(fù)這個過程，直到找不到任何進(jìn)一步提高目標(biāo)函數(shù)的小調(diào)整為止。 讓我們再次來看快遞的例子。我們可以從一個解開始：
局部移動可以是用一個未選中的包裹替換一個已選中的包裹。我們時刻注意容量限制，嘗試在每次局部移動時都滿足這個約束條件。一個移動的例子可以是：
通過這個移動，新的目標(biāo)值為115。我們將值較低的包裹從選擇中移除，并添加值較高的包裹，同時仍然保持一個可行的解。 所有你可以通過應(yīng)用一個局部移動達(dá)到的可能解被稱為當(dāng)前解的鄰域。 你不能超出送貨車的容量限制。因此在這種情況下，如果一個包裹比任何其他包裹都大，即使其價值很高，我們也永遠(yuǎn)不會選擇這個包裹！ 這是局部搜索的一個缺點(diǎn)：你可能會陷入局部最優(yōu)解：
為了克服這個問題，有一些方法。你可以選擇一次交換多個包裹，并將其視為一個移動。通過這樣做，鄰域擴(kuò)大了，可以達(dá)到更多的解。 你也可以選擇從多個解開始，而不是僅僅一個。然后你對每個解重復(fù)交換的過程，這稱為迭代局部搜索。 另一種方法是選擇以一定概率使目標(biāo)變差的操作：
如果溫度參數(shù)較高，接受使目標(biāo)值下降的移動的概率就高。如果溫度較低，這個概率就低。模擬退火（Simulated annealing）利用了這種概率。它以高溫開始，然后逐漸降低。這意味著在開始時，你是在解空間中進(jìn)行隨機(jī)游走。當(dāng)溫度降低時，搜索變得局部化。模擬退火在困難的基準(zhǔn)測試上表現(xiàn)出色。 最后，我想提到的一種逃避局部最優(yōu)解的技術(shù)是禁忌搜索（Tabu search）。禁忌搜索的想法是記錄你已經(jīng)訪問過的解，不允許再次回到它們。將所有之前的解保存在內(nèi)存中可能會很昂貴。你可以選擇存儲過渡狀態(tài)或保持固定大小的禁忌列表。 可以將迭代局部搜索、模擬退火和禁忌搜索等技術(shù)結(jié)合起來使用。 遺傳算法 你也可以選擇使用遺傳算法。遺傳算法的核心概念是模仿自然選擇的過程，每個解都被稱為一個個體。算法從一個由多個個體組成的初始種群開始。然后，你計(jì)算每個個體的適應(yīng)度，它表示解的優(yōu)劣。適應(yīng)度最高的個體，即表現(xiàn)最好的解，會被選出來進(jìn)行繁殖，以產(chǎn)生下一代的解。 在快遞例子中，每個包裹是一個基因，可以取0或1的值。初始種群包含四個個體，可能如下所示：
現(xiàn)在我們選擇適應(yīng)度最高的個體（目標(biāo)值最高的）來產(chǎn)生后代。在這個例子中，個體2和4具有最高的適應(yīng)度。產(chǎn)生后代的常見方法是隨機(jī)選擇一個交叉點(diǎn)，并在這個交叉點(diǎn)之前交換基因。 下一步是突變。我們以較低的隨機(jī)概率翻轉(zhuǎn)一些基因，在這個例子中，取0.14（1除以7，7是包裹的數(shù)量）。這是一個重要的步驟，因?yàn)槲覀兿Ｍ３侄鄻有裕⒎乐惯^早收斂。我們將突變后代1：
現(xiàn)在，我們將計(jì)算新個體的適應(yīng)度。種群的大小是固定的。適應(yīng)度最低的個體將被淘汰。
這里是完整的算法：
使用遺傳算法時，也有可能陷入局部最優(yōu)?？梢酝ㄟ^多種方式克服這一問題。你可以創(chuàng)建初始種群的子集，并在選擇階段進(jìn)行隨機(jī)化。這可以防止在選擇過程中一再使用相同的種群。避免局部最小值的另一種方法是給予那些存活時間較長的個體和/或與其他個體更為獨(dú)特的個體額外的獎勵，因?yàn)樗鼈兛赡苡兄谡业揭粋€更具普遍性的解。 混合技術(shù) 最后討論的快速找到高質(zhì)量解的方法是結(jié)合不同的技術(shù)。 例如，大鄰域搜索就是將局部搜索與約束規(guī)劃（CP）或混合整數(shù)規(guī)劃（MIP）結(jié)合在一起。CP和MIP的缺點(diǎn)是它們在面對大規(guī)模問題時可能會遇到困難，并且需要大量時間來獲得最優(yōu)解。通過將局部搜索與CP或MIP結(jié)合起來，可以得到兩者的優(yōu)點(diǎn)。你可以用CP或MIP解決小型子問題，并通過局部搜索選擇新的子問題。 大鄰域搜索的步驟是：
在求解過程中，你要跟蹤最佳解。鄰域可以通過例如固定一組變量來定義。 混合方法的另一個例子是記憶算法。記憶算法結(jié)合了遺傳算法和局部搜索。 在這篇文章中，你看到了不同的用于解決數(shù)學(xué)優(yōu)化問題的啟發(fā)式方法。希望你可以通過局部搜索、遺傳算法或混合方法快速找到優(yōu)化問題的解決方案！還有其他有趣且表現(xiàn)良好的搜索啟發(fā)式方法，如粒子群優(yōu)化、蟻群優(yōu)化和隨機(jī)隧道。 |
|
|
