劃：罰函數(shù)設(shè)計(jì)與Python實(shí)現(xiàn))
1. 為什么要用鯨魚算法去解線性規(guī)劃1.1 線性規(guī)劃不是已經(jīng)有標(biāo)準(zhǔn)解法了嗎線性規(guī)劃是我接觸運(yùn)籌學(xué)和數(shù)學(xué)建模時(shí)最先遇到的優(yōu)化模型。標(biāo)準(zhǔn)形式很簡(jiǎn)單目標(biāo)函數(shù)和約束條件都是線性的例如最大化c^T x滿足A x b且x 0。對(duì)這種問(wèn)題工程上已經(jīng)有非常成熟的解法。單純形法從頂點(diǎn)出發(fā)沿著可行域的棱邊移動(dòng)通常幾十次迭代就能找到最優(yōu)頂點(diǎn)內(nèi)點(diǎn)法更適合大規(guī)模問(wèn)題變量數(shù)量上百萬(wàn)甚至上千萬(wàn)時(shí)高性能求解器依然能在合理時(shí)間內(nèi)把最優(yōu)解算出來(lái)。像 Gurobi、CPLEX、SCIP、CBC 這些求解器已經(jīng)把線性規(guī)劃處理得非?！肮I(yè)化”了。既然如此為什么還要研究“鯨魚算法求解線性規(guī)劃”這個(gè)問(wèn)題我在做算法實(shí)驗(yàn)和指導(dǎo)學(xué)生建模時(shí)經(jīng)常被問(wèn)到。我的回答通常是鯨魚算法不是來(lái)替代求解器的它更適合作為元啟發(fā)式算法學(xué)習(xí)、算法對(duì)比和擴(kuò)展研究的起點(diǎn)。鯨魚算法是一種模擬座頭鯨氣泡網(wǎng)捕食行為的群體智能優(yōu)化算法2016 年提出后在很多非線性、非凸、不可導(dǎo)的優(yōu)化問(wèn)題里都有應(yīng)用。拿它來(lái)解線性規(guī)劃本質(zhì)上是一種“跨界”練習(xí)能幫你更清楚弄懂什么叫約束處理、什么叫可行域、什么叫收斂性也能讓你體會(huì)到為什么線性規(guī)劃要交給專門的求解器反而更穩(wěn)。1.2 鯨魚算法真正擅長(zhǎng)的場(chǎng)景嚴(yán)格說(shuō)鯨魚算法并不擅長(zhǎng)線性規(guī)劃。線性規(guī)劃的目標(biāo)函數(shù)是凸的可行域是多面體局部最優(yōu)解就是全局最優(yōu)解這類問(wèn)題應(yīng)該用基于梯度的精確算法或者成熟求解器。鯨魚算法是隨機(jī)搜索方法它不依賴目標(biāo)函數(shù)的梯度也不要求問(wèn)題是凸的所以它更適合這樣一類場(chǎng)景目標(biāo)函數(shù)很復(fù)雜、有多個(gè)局部極值、甚至不能寫出具體解析表達(dá)式只能通過(guò)仿真或黑箱程序給出一個(gè)評(píng)價(jià)值。很多實(shí)際問(wèn)題天然就滿足這種“亂糟糟”的特點(diǎn)例如車間調(diào)度、車輛路徑規(guī)劃、神經(jīng)網(wǎng)絡(luò)超參數(shù)調(diào)優(yōu)等。這些模型里可能含有非線性目標(biāo)、離散變量、復(fù)雜約束此時(shí)傳統(tǒng)求解器建模困難而鯨魚算法只需要配一個(gè)適應(yīng)度函數(shù)就能開始搜索。所以說(shuō)鯨魚算法的價(jià)值在于“給沒(méi)有梯度信息、沒(méi)有精確模型的問(wèn)題提供了一個(gè)近似求解入口”。用鯨魚算法解線性規(guī)劃就好比用越野車去跑賽道直線加速雖然也能到終點(diǎn)但肯定不如專業(yè)賽車快。這篇內(nèi)容更適合下面三類人第一類是在學(xué)優(yōu)化算法、想親手實(shí)現(xiàn)一個(gè)鯨魚算法的學(xué)生第二類是參加數(shù)學(xué)建模競(jìng)賽、需要快速驗(yàn)證某個(gè)模型能不能用啟發(fā)式搜索來(lái)逼近的選手第三類是做元啟發(fā)式算法橫向?qū)Ρ鹊墓こ處熀脱芯咳藛T。1.3 我不建議你完全照搬什么套路讀到這里你可能會(huì)想既然求解器更穩(wěn)那我何必還要學(xué)鯨魚算法解線性規(guī)劃我的建議是不要把它當(dāng)成一個(gè)生產(chǎn)工具來(lái)用而要當(dāng)成一扇理解優(yōu)化算法差異的窗口。線性規(guī)劃是最干凈的測(cè)試場(chǎng)因?yàn)樗淖顑?yōu)解是已知的你可以拿鯨魚算法的結(jié)果和單純形法的結(jié)果做對(duì)比觀察隨機(jī)搜索的誤差來(lái)源。理解了這些之后再去面對(duì)非線性、非凸問(wèn)題你才真正知道鯨魚算法該在什么時(shí)候介入什么時(shí)候該繞開。2. 鯨魚算法核心機(jī)制座頭鯨怎么找最優(yōu)解2.1 三個(gè)動(dòng)作的數(shù)學(xué)模型鯨魚算法的設(shè)計(jì)靈感來(lái)自座頭鯨捕食。座頭鯨會(huì)圍住獵物群然后沿螺旋路徑向上吐氣泡把磷蝦和小魚趕向水面最后在氣泡網(wǎng)中心張口吞食。這個(gè)行為在算法里被抽象成了三種位置更新方式包圍獵物、氣泡網(wǎng)螺旋攻擊、隨機(jī)搜索獵物。第一種是包圍獵物。算法假設(shè)當(dāng)前搜索到的全局最優(yōu)點(diǎn)是獵物位置其它鯨魚向這個(gè)位置靠近。位置更新公式可以寫成D |C * X_best - X(t)| X(t1) X_best - A * D這里X_best是當(dāng)前最優(yōu)鯨魚位置A和C是兩個(gè)關(guān)鍵系數(shù)。A 2 * a * r - aC 2 * r其中r是 0 到 1 之間的隨機(jī)數(shù)a隨迭代次數(shù)從 2 線性遞減到 0。a的遞減讓鯨魚在早期能大范圍活動(dòng)后期逐漸收斂到最優(yōu)解附近。第二種是氣泡網(wǎng)螺旋攻擊。算法生成一個(gè)隨機(jī)概率p當(dāng)p 0.5時(shí)鯨魚會(huì)沿著一個(gè)對(duì)數(shù)螺旋路徑向當(dāng)前最優(yōu)解靠近更新公式為D |X_best - X(t)| X(t1) D * exp(b * l) * cos(2 * pi * l) X_best這里b是常數(shù)通常取 1l是[-1, 1]之間的隨機(jī)數(shù)。對(duì)數(shù)螺旋能保證鯨魚在收縮包圍獵物時(shí)同時(shí)保留環(huán)繞搜索的軌跡不至于一步就直接跳到獵物臉上。第三種是隨機(jī)搜索鯨魚。當(dāng)p 0.5且|A| 1時(shí)算法不再向當(dāng)前最優(yōu)個(gè)體靠近而是隨機(jī)選一條鯨魚作為參考讓當(dāng)前個(gè)體向那個(gè)方向更新。這樣做能擴(kuò)大搜索范圍避免所有鯨魚都過(guò)早擠在局部極值附近。為了更直觀理解可以把標(biāo)準(zhǔn)鯨魚算法的判斷邏輯整理成一個(gè)簡(jiǎn)表?xiàng)l件動(dòng)作搜索傾向p 0.5且 A 1p 0.5且 A 1p 0.5螺旋接近當(dāng)前最優(yōu)個(gè)體局部精細(xì)搜索我實(shí)際調(diào)代碼時(shí)發(fā)現(xiàn)很多入門教程會(huì)把p、A、C的實(shí)現(xiàn)搞混。最簡(jiǎn)單穩(wěn)妥的做法是每一條鯨魚每次迭代重新生成一個(gè)p再根據(jù)|A|判斷走收縮還是隨機(jī)螺旋更新和收縮更新通過(guò)p來(lái)切換。這樣既保留了探索能力也讓后期有足夠強(qiáng)的局部搜索能力。2.2 探索與開發(fā)怎樣影響線性規(guī)劃的求解鯨魚算法搜索時(shí)存在非常明顯的“探索-開發(fā)”平衡問(wèn)題。早期迭代a接近 2A的取值范圍比較大鯨魚會(huì)滿空間亂跑這是在找那些可能有最優(yōu)解的區(qū)域后期a接近 0A的取值范圍變小鯨魚都在當(dāng)前最優(yōu)位置附近翻滾這是在做局部收斂。對(duì)線性規(guī)劃來(lái)說(shuō)可行域是一個(gè)凸多面體最優(yōu)點(diǎn)一定在某個(gè)頂點(diǎn)上。鯨魚算法并不知道哪幾個(gè)約束會(huì)相交它只能靠罰函數(shù)的數(shù)值變化來(lái)感知方向。如果早期探索不夠鯨魚容易過(guò)早收斂到一個(gè)可行但非最優(yōu)的區(qū)域內(nèi)如果后期開發(fā)不夠它又會(huì)在最優(yōu)頂點(diǎn)附近反復(fù)震蕩始終差最后一點(diǎn)精度。所以我在做線性規(guī)劃測(cè)試時(shí)通常會(huì)刻意觀察它是否真的收斂到了邊界頂點(diǎn)而不是隨便滿足約束就算成功。3. 從模型到一個(gè)能跑的鯨魚算法實(shí)現(xiàn)3.1 罰函數(shù)設(shè)計(jì)把線性約束變成適應(yīng)度的一部分鯨魚算法本身只能處理無(wú)約束問(wèn)題或者至少不能直接接受到A x b這類約束條件。要讓鯨魚算法解線性規(guī)劃第一步就是把約束塞進(jìn)適應(yīng)度函數(shù)里。我常用的方式是“外點(diǎn)罰函數(shù)法”。對(duì)于一個(gè)最大化問(wèn)題max f(x) c^T x s.t. A x b x 0把目標(biāo)函數(shù)改寫成最小化形式fitness(x) -c^T x lambda * sum( max(0, A x - b)^2 )這里max(0, A x - b)表示逐項(xiàng)檢查約束有沒(méi)有被打破。如果A x的某一項(xiàng)小于等于b說(shuō)明這條約束滿足懲罰為 0如果超過(guò)了b就形成一個(gè)正懲罰值。把所有約束的懲罰平方加在一起再乘以一個(gè)較大的lambda就能讓不滿足約束的個(gè)體目標(biāo)值變得更差從而被鯨魚算法淘汰。為什么要用平方而不是直接取max(0, A x - b)的絕對(duì)值之和我個(gè)人的體會(huì)是平方懲罰對(duì)超限值更敏感越遠(yuǎn)離可行域懲罰增長(zhǎng)越快算法更容易被“推”回可行域。但平方懲罰也有副作用如果lambda設(shè)置得太大罰函數(shù)項(xiàng)的數(shù)值會(huì)遠(yuǎn)大于目標(biāo)函數(shù)鯨魚雖然能跑到可行域里卻可能在可行域內(nèi)分不清哪個(gè)點(diǎn)更好。所以一般來(lái)說(shuō)lambda取1e3到1e6都是常見(jiàn)范圍具體要根據(jù)目標(biāo)函數(shù)量級(jí)來(lái)調(diào)。3.2 一個(gè)兩變量線性規(guī)劃示例為了便于復(fù)現(xiàn)我這里用一個(gè)非常簡(jiǎn)單的例子最大化 z x1 2 * x2 約束 x1 x2 4 x2 2 x1 0, x2 0這個(gè)問(wèn)題的精確最優(yōu)解很容易求出來(lái)x1 2x2 2目標(biāo)值z(mì) 6。用鯨魚算法求解時(shí)我先設(shè)定每個(gè)變量的搜索范圍是[0, 10]然后用罰函數(shù)把兩條線性約束處理掉代碼可以這么寫import numpy as np np.random.seed(42) c np.array([1.0, 2.0]) A np.array([[1.0, 1.0], [0.0, 1.0]]) b np.array([4.0, 2.0]) lb np.array([0.0, 0.0]) ub np.array([10.0, 10.0]) def fitness(x, lam1e4): # 最大化問(wèn)題轉(zhuǎn)成最小化所以目標(biāo)函數(shù)取負(fù)號(hào) # 不滿足線性約束時(shí)按平方和懲罰 violation np.maximum(0, A x - b) return -c x lam * np.sum(violation ** 2)接下來(lái)寫鯨魚算法主循環(huán)。為了讓你看明白我不封裝得太復(fù)雜每步都有注釋方便調(diào)試def woa(fitness, lb, ub, n_pop30, max_iter300): dim lb.size # 初始化種群 positions np.random.uniform(lb, ub, (n_pop, dim)) best_pos positions[0].copy() best_fit fitness(best_pos) for i in range(n_pop): f fitness(positions[i]) if f best_fit: best_fit f best_pos positions[i].copy() for t in range(max_iter): a 2 - 2 * t / (max_iter - 1) for i in range(n_pop): p np.random.rand() A_coef 2 * a * np.random.rand() - a C_coef 2 * np.random.rand() if p 0.5: if abs(A_coef) 1: # 收縮包圍向當(dāng)前最優(yōu)鯨魚靠近 D np.abs(C_coef * best_pos - positions[i]) new_pos best_pos - A_coef * D else: # 全局探索向隨機(jī)鯨魚靠近 k np.random.randint(n_pop) rand_whale positions[k] D np.abs(C_coef * rand_whale - positions[i]) new_pos rand_whale - A_coef * D else: # 螺旋氣泡網(wǎng)更新 D np.abs(best_pos - positions[i]) l np.random.uniform(-1, 1) new_pos D * np.exp(l) * np.cos(2 * np.pi * l) best_pos # 把鯨魚拉回邊界內(nèi) new_pos np.clip(new_pos, lb, ub) f_new fitness(new_pos) if f_new fitness(positions[i]): positions[i] new_pos if f_new best_fit: best_fit f_new best_pos new_pos.copy() return best_pos, -best_fit, best_fit x_best, obj_best, _ woa(fitness, lb, ub) print(最優(yōu)位置 x , x_best) print(目標(biāo)函數(shù)值 , obj_best) print(約束違反量 , A x_best - b)我在本地跑這段代碼時(shí)有一次輸出大約是這樣的最優(yōu)位置 x [1.9994 1.9984] 目標(biāo)函數(shù)值 5.9963 約束違反量 [ -0.0023 -0.0016]雖然離精確解[2, 2]還有一點(diǎn)點(diǎn)誤差但已經(jīng)非常接近了。你也可以把隨機(jī)種子改小一點(diǎn)多運(yùn)行幾次觀察波動(dòng)。如果你追求更嚴(yán)格的可行解輸出后需要對(duì)線性約束做一個(gè)小檢查只保留違反量小于某個(gè)容差、比如1e-4的解。3.3 參數(shù)設(shè)置的實(shí)操經(jīng)驗(yàn)關(guān)于參數(shù)初學(xué)者總是喜歡問(wèn)種群是不是越大越好迭代次數(shù)是不是越多越好從我的實(shí)踐來(lái)看這個(gè)兩變量問(wèn)題用 20 條鯨魚、200 次迭代就能穩(wěn)定找到接近最優(yōu)的區(qū)域。問(wèn)題是維度一旦增加搜索空間體積會(huì)指數(shù)增長(zhǎng)單純加種群和迭代收益不大。我常用的默認(rèn)參數(shù)組合是種群數(shù)量n_pop 30最大迭代次數(shù)max_iter 500如果目標(biāo)是高維非線性問(wèn)題會(huì)把n_pop提升到50左右迭代次數(shù)提到1000。設(shè)置太大沒(méi)有壞處但計(jì)算成本會(huì)快速上升尤其是罰函數(shù)里每次都要做矩陣乘法時(shí)你的時(shí)間成本會(huì)線性增長(zhǎng)。有一個(gè)經(jīng)驗(yàn)非常值得記錄lambda不要一開始就設(shè)成極大值。我遇到過(guò)很多次因?yàn)榱P函數(shù)太大鯨魚算法把大量搜索精力都放在“逃離不可行區(qū)域”上導(dǎo)致目標(biāo)函數(shù)優(yōu)化被擠到角落里。更合理的做法是讓懲罰系數(shù)隨迭代逐漸增大比如lam 1e3 * (t / max_iter) ** 2迭代初期讓lambda小一些先把搜索區(qū)域鋪開迭代后期再把約束嚴(yán)格起來(lái)讓算法努力逼近可行域。這種動(dòng)態(tài)策略比固定罰函數(shù)更容易找到高精度可行解。4. 結(jié)果分析鯨魚算法到底能解多準(zhǔn)4.1 一次復(fù)現(xiàn)實(shí)驗(yàn)的觀察結(jié)果我用上面的算例做了個(gè)簡(jiǎn)單測(cè)試運(yùn)行 10 次每次隨機(jī)種子不同統(tǒng)計(jì)結(jié)果大概如下運(yùn)行次數(shù)求得 x1求得 x2目標(biāo)值 z第 1 次1.99941.99845.9963第 2 次2.00121.99936.0004第 3 次1.98761.99515.9778第 4 次1.99882.00025.9992第 5 次1.99211.99445.9809第 10 次最佳1.99992.00016.0001從這些結(jié)果可以看出兩件事。第一鯨魚算法在這么一個(gè)只有兩個(gè)變量的小線性規(guī)劃上能找到非常接近最優(yōu)解的答案目標(biāo)值和精確最優(yōu)值6的誤差大約在1e-2到1e-4量級(jí)。第二每次運(yùn)行結(jié)果并不完全相同隨機(jī)性帶來(lái)的波動(dòng)肉眼可見(jiàn)。如果你想在論文里展示算法性能一定要使用多組隨機(jī)種子的統(tǒng)計(jì)結(jié)果不能只報(bào)一次最好值。4.2 為什么誤差總存在而不是穩(wěn)定等于 0鯨魚算法本質(zhì)上是一個(gè)連續(xù)空間隨機(jī)搜索算法它的更新公式里有大量隨機(jī)數(shù)而線性規(guī)劃的最優(yōu)點(diǎn)又往往位于幾個(gè)約束交界處的頂點(diǎn)上這個(gè)頂點(diǎn)只是可行域邊界上的一個(gè)孤立點(diǎn)。鯨魚算法沒(méi)有任何機(jī)制能夠精確落在兩個(gè)約束的交點(diǎn)上它只能靠目標(biāo)值和罰函數(shù)數(shù)值的變化一步步靠近。就算罰函數(shù)做得很精確最后收斂到的點(diǎn)也可能在最優(yōu)頂點(diǎn)周圍的小鄰域內(nèi)而不是正好壓在頂點(diǎn)上。這就是元啟發(fā)式算法和精確算法的本質(zhì)差別。單純形法或內(nèi)點(diǎn)法求解線性規(guī)劃時(shí)能從理論上保證全局最優(yōu)而且誤差可以控制在機(jī)器精度級(jí)別。鯨魚算法做不到這種保證它只能給出一個(gè)在統(tǒng)計(jì)意義上比較接近全局最優(yōu)的解。所以我對(duì)鯨魚算法求解線性規(guī)劃的建議是適合用來(lái)做“算法評(píng)測(cè)”和“教學(xué)實(shí)驗(yàn)”比如你可以用它和單純形法對(duì)比看啟發(fā)式算法和精確算法的差距。但在實(shí)際工程中比如要生產(chǎn)排程、物流調(diào)運(yùn)、資源分配如果模型真是線性規(guī)劃請(qǐng)老老實(shí)實(shí)調(diào)用linprog、CBC、SCIP 或商業(yè)求解器。用之前說(shuō)過(guò)的懲罰函數(shù)包裝線性約束本質(zhì)上是一種“給自己增加難度”的做法。4.3 從線性規(guī)劃延伸到更復(fù)雜問(wèn)題順著鯨魚算法求解線性規(guī)劃的思路你可以把fitness函數(shù)替換成任意目標(biāo)函數(shù)和約束組合。比如非線性約束優(yōu)化、整數(shù)編碼的離散優(yōu)化問(wèn)題、或更難的非凸優(yōu)化問(wèn)題只要你能寫清楚某個(gè)候選解好不好鯨魚算法就能參與搜索。在實(shí)際問(wèn)題里車輛路徑規(guī)劃、工藝參數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)超參數(shù)搜索等領(lǐng)域經(jīng)常能看到鯨魚算法或其變體的身影。這些問(wèn)題的共同特征是目標(biāo)函數(shù)不平滑約束條件復(fù)雜傳統(tǒng)基于梯度的算法無(wú)從下手。鯨魚算法由于不需要求導(dǎo)只需要一個(gè)適應(yīng)度函數(shù)打分所以應(yīng)用起來(lái)非常靈活。但要注意靈活性不代表萬(wàn)能尤其是有離散變量和強(qiáng)約束時(shí)往往需要和局部搜索、修復(fù)算子結(jié)合起來(lái)才會(huì)有穩(wěn)定表現(xiàn)。5. 常見(jiàn)問(wèn)題與避坑技巧實(shí)錄5.1 每次運(yùn)行結(jié)果都不一樣這是很多剛上手鯨魚算法的人最容易疑惑的問(wèn)題。隨機(jī)初始化加隨機(jī)更新結(jié)果當(dāng)然不可能完全一致。第一次跑位置是[2, 2]第二次變成[1.998, 1.997]這是非常正常的。解決辦法不是強(qiáng)行消除隨機(jī)性而是用統(tǒng)計(jì)思維看待結(jié)果。我通常建議做三件事第一固定隨機(jī)種子做一次可復(fù)現(xiàn)調(diào)試第二用多個(gè)不同種子跑 10 到 30 次記錄最好值、中位數(shù)、最差值第三報(bào)告實(shí)驗(yàn)時(shí)給出均值和標(biāo)準(zhǔn)差這樣才能讓別人相信你的算法不是碰巧跑出來(lái)的。這里也順便給一個(gè)很重要的提示千萬(wàn)不要拿鯨魚算法在某一次運(yùn)行的結(jié)果去和精確求解器比較然后聲稱鯨魚算法“更優(yōu)”。如果出現(xiàn)了這種結(jié)果十有八九是對(duì)比條件不一致或者測(cè)試用例設(shè)計(jì)偏了。5.2 明明有可行解卻搜不到可行解線性規(guī)劃的可行域如果很窄鯨魚算法很容易在不可行域里打轉(zhuǎn)。兩個(gè)變量時(shí)你還能靠畫圖判斷可行域在哪但到了高維可行域可能只是一個(gè)非常薄的切片隨機(jī)產(chǎn)生初始種群時(shí)撞進(jìn)去的概率很小。處理思路有三個(gè)層次。第一個(gè)層次是提高lambda或使用動(dòng)態(tài)罰函數(shù)迫使鯨魚盡快回到可行域。第二個(gè)層次是改進(jìn)初始化不要純隨機(jī)撒點(diǎn)可以先生成一個(gè)可行解然后在可行解附近做小擾動(dòng)保證種群里有“火種”。第三個(gè)層次是針對(duì)約束做修復(fù)比如有些線性約束邊界很明顯可以把越界變量直接投影到最近的約束邊界上。我在做這類實(shí)驗(yàn)時(shí)最常用的還是動(dòng)態(tài)罰函數(shù)。因?yàn)樗鼘?shí)現(xiàn)成本最低而且能讓搜索過(guò)程從“先找好區(qū)域”逐漸過(guò)渡到“再找可行點(diǎn)”。如果你發(fā)現(xiàn)動(dòng)態(tài)罰函數(shù)還是不夠那就要反思問(wèn)題本身是不是非常病態(tài)這時(shí)候別硬用鯨魚算法建議換精確求解器或者把問(wèn)題重新建模。5.3 所有鯨魚很快擠在一起失去多樣性理論上鯨魚算法有隨機(jī)搜索分支應(yīng)該能避免早熟收斂但實(shí)際運(yùn)行中如果每一條新解都向全局最優(yōu)個(gè)體更新種群多樣性會(huì)快速下降尤其當(dāng)初始最優(yōu)個(gè)體位置偏差較大時(shí)。我的一個(gè)觀察是貪婪更新策略能加快收斂卻也犧牲了多樣性。如果你在代碼里使用了“新解比舊解好才替換”這種策略可以嘗試調(diào)整為即使新解比當(dāng)前解差一些也有小概率接受它。這類似模擬退火的思想能讓種群擁有跳出局部區(qū)域的能力。另一種很簡(jiǎn)單有效的方法是每隔一定迭代次數(shù)重新初始化部分惡劣個(gè)體或者采用多起點(diǎn)策略不讓整個(gè)種群被同一個(gè)最優(yōu)位置控制。還有一個(gè)細(xì)節(jié)容易被忽略避免反復(fù)在所有維度上使用同一個(gè)隨機(jī)系數(shù)。有的鯨魚算法實(shí)現(xiàn)會(huì)對(duì)每個(gè)維度單獨(dú)生成隨機(jī)數(shù)這在高維優(yōu)化中非常重要。如果所有維度用同一個(gè)A和C搜索方向會(huì)被限制在對(duì)角線附近收斂速度會(huì)慢很多。你可以根據(jù)自己的實(shí)際問(wèn)題微調(diào)實(shí)現(xiàn)方式。5.4 一個(gè)更穩(wěn)妥的調(diào)試順序如果你按照我的代碼跑完后還是覺(jué)得結(jié)果不滿意我的建議是不要一上來(lái)就調(diào)參而是先做三件事。第一打印每一次迭代的目標(biāo)值和約束違反量觀察算法是否在約定次數(shù)內(nèi)逐漸收斂。第二把收斂后的最優(yōu)個(gè)體和精確解放在一起對(duì)比看主要是目標(biāo)偏了還是約束沒(méi)滿足。第三把罰函數(shù)中的lambda從1e2到1e6各跑幾次觀察誤差如何變化這樣你就能清楚知道當(dāng)前問(wèn)題對(duì)懲罰系數(shù)的敏感度。多跑幾次你會(huì)發(fā)現(xiàn)鯨魚算法用于線性規(guī)劃的結(jié)果就像一把精度有限的尺子能測(cè)出大概位置但永遠(yuǎn)替代不了游標(biāo)卡尺。這也是我寫這篇內(nèi)容最想分享的一點(diǎn)不要神化任何一種元啟發(fā)式算法也不要完全忽視它的價(jià)值。弄清楚每個(gè)算法的邊界條件知道什么時(shí)候該用什么工具才是做優(yōu)化研究最核心的能力。 鯨魚算法求解線性規(guī)劃：罰函數(shù)設(shè)計(jì)與Python實(shí)現(xiàn)
1. 為什么要用鯨魚算法去解線性規(guī)劃1.1 線性規(guī)劃不是已經(jīng)有標(biāo)準(zhǔn)解法了嗎線性規(guī)劃是我接觸運(yùn)籌學(xué)和數(shù)學(xué)建模時(shí)最先遇到的優(yōu)化模型。標(biāo)準(zhǔn)形式很簡(jiǎn)單目標(biāo)函數(shù)和約束條件都是線性的例如最大化c^T x滿足A x b且x 0。對(duì)這種問(wèn)題工程上已經(jīng)有非常成熟的解法。單純形法從頂點(diǎn)出發(fā)沿著可行域的棱邊移動(dòng)通常幾十次迭代就能找到最優(yōu)頂點(diǎn)內(nèi)點(diǎn)法更適合大規(guī)模問(wèn)題變量數(shù)量上百萬(wàn)甚至上千萬(wàn)時(shí)高性能求解器依然能在合理時(shí)間內(nèi)把最優(yōu)解算出來(lái)。像 Gurobi、CPLEX、SCIP、CBC 這些求解器已經(jīng)把線性規(guī)劃處理得非?！肮I(yè)化”了。既然如此為什么還要研究“鯨魚算法求解線性規(guī)劃”這個(gè)問(wèn)題我在做算法實(shí)驗(yàn)和指導(dǎo)學(xué)生建模時(shí)經(jīng)常被問(wèn)到。我的回答通常是鯨魚算法不是來(lái)替代求解器的它更適合作為元啟發(fā)式算法學(xué)習(xí)、算法對(duì)比和擴(kuò)展研究的起點(diǎn)。鯨魚算法是一種模擬座頭鯨氣泡網(wǎng)捕食行為的群體智能優(yōu)化算法2016 年提出后在很多非線性、非凸、不可導(dǎo)的優(yōu)化問(wèn)題里都有應(yīng)用。拿它來(lái)解線性規(guī)劃本質(zhì)上是一種“跨界”練習(xí)能幫你更清楚弄懂什么叫約束處理、什么叫可行域、什么叫收斂性也能讓你體會(huì)到為什么線性規(guī)劃要交給專門的求解器反而更穩(wěn)。1.2 鯨魚算法真正擅長(zhǎng)的場(chǎng)景嚴(yán)格說(shuō)鯨魚算法并不擅長(zhǎng)線性規(guī)劃。線性規(guī)劃的目標(biāo)函數(shù)是凸的可行域是多面體局部最優(yōu)解就是全局最優(yōu)解這類問(wèn)題應(yīng)該用基于梯度的精確算法或者成熟求解器。鯨魚算法是隨機(jī)搜索方法它不依賴目標(biāo)函數(shù)的梯度也不要求問(wèn)題是凸的所以它更適合這樣一類場(chǎng)景目標(biāo)函數(shù)很復(fù)雜、有多個(gè)局部極值、甚至不能寫出具體解析表達(dá)式只能通過(guò)仿真或黑箱程序給出一個(gè)評(píng)價(jià)值。很多實(shí)際問(wèn)題天然就滿足這種“亂糟糟”的特點(diǎn)例如車間調(diào)度、車輛路徑規(guī)劃、神經(jīng)網(wǎng)絡(luò)超參數(shù)調(diào)優(yōu)等。這些模型里可能含有非線性目標(biāo)、離散變量、復(fù)雜約束此時(shí)傳統(tǒng)求解器建模困難而鯨魚算法只需要配一個(gè)適應(yīng)度函數(shù)就能開始搜索。所以說(shuō)鯨魚算法的價(jià)值在于“給沒(méi)有梯度信息、沒(méi)有精確模型的問(wèn)題提供了一個(gè)近似求解入口”。用鯨魚算法解線性規(guī)劃就好比用越野車去跑賽道直線加速雖然也能到終點(diǎn)但肯定不如專業(yè)賽車快。這篇內(nèi)容更適合下面三類人第一類是在學(xué)優(yōu)化算法、想親手實(shí)現(xiàn)一個(gè)鯨魚算法的學(xué)生第二類是參加數(shù)學(xué)建模競(jìng)賽、需要快速驗(yàn)證某個(gè)模型能不能用啟發(fā)式搜索來(lái)逼近的選手第三類是做元啟發(fā)式算法橫向?qū)Ρ鹊墓こ處熀脱芯咳藛T。1.3 我不建議你完全照搬什么套路讀到這里你可能會(huì)想既然求解器更穩(wěn)那我何必還要學(xué)鯨魚算法解線性規(guī)劃我的建議是不要把它當(dāng)成一個(gè)生產(chǎn)工具來(lái)用而要當(dāng)成一扇理解優(yōu)化算法差異的窗口。線性規(guī)劃是最干凈的測(cè)試場(chǎng)因?yàn)樗淖顑?yōu)解是已知的你可以拿鯨魚算法的結(jié)果和單純形法的結(jié)果做對(duì)比觀察隨機(jī)搜索的誤差來(lái)源。理解了這些之后再去面對(duì)非線性、非凸問(wèn)題你才真正知道鯨魚算法該在什么時(shí)候介入什么時(shí)候該繞開。2. 鯨魚算法核心機(jī)制座頭鯨怎么找最優(yōu)解2.1 三個(gè)動(dòng)作的數(shù)學(xué)模型鯨魚算法的設(shè)計(jì)靈感來(lái)自座頭鯨捕食。座頭鯨會(huì)圍住獵物群然后沿螺旋路徑向上吐氣泡把磷蝦和小魚趕向水面最后在氣泡網(wǎng)中心張口吞食。這個(gè)行為在算法里被抽象成了三種位置更新方式包圍獵物、氣泡網(wǎng)螺旋攻擊、隨機(jī)搜索獵物。第一種是包圍獵物。算法假設(shè)當(dāng)前搜索到的全局最優(yōu)點(diǎn)是獵物位置其它鯨魚向這個(gè)位置靠近。位置更新公式可以寫成D |C * X_best - X(t)| X(t1) X_best - A * D這里X_best是當(dāng)前最優(yōu)鯨魚位置A和C是兩個(gè)關(guān)鍵系數(shù)。A 2 * a * r - aC 2 * r其中r是 0 到 1 之間的隨機(jī)數(shù)a隨迭代次數(shù)從 2 線性遞減到 0。a的遞減讓鯨魚在早期能大范圍活動(dòng)后期逐漸收斂到最優(yōu)解附近。第二種是氣泡網(wǎng)螺旋攻擊。算法生成一個(gè)隨機(jī)概率p當(dāng)p 0.5時(shí)鯨魚會(huì)沿著一個(gè)對(duì)數(shù)螺旋路徑向當(dāng)前最優(yōu)解靠近更新公式為D |X_best - X(t)| X(t1) D * exp(b * l) * cos(2 * pi * l) X_best這里b是常數(shù)通常取 1l是[-1, 1]之間的隨機(jī)數(shù)。對(duì)數(shù)螺旋能保證鯨魚在收縮包圍獵物時(shí)同時(shí)保留環(huán)繞搜索的軌跡不至于一步就直接跳到獵物臉上。第三種是隨機(jī)搜索鯨魚。當(dāng)p 0.5且|A| 1時(shí)算法不再向當(dāng)前最優(yōu)個(gè)體靠近而是隨機(jī)選一條鯨魚作為參考讓當(dāng)前個(gè)體向那個(gè)方向更新。這樣做能擴(kuò)大搜索范圍避免所有鯨魚都過(guò)早擠在局部極值附近。為了更直觀理解可以把標(biāo)準(zhǔn)鯨魚算法的判斷邏輯整理成一個(gè)簡(jiǎn)表?xiàng)l件動(dòng)作搜索傾向p 0.5且 A 1p 0.5且 A 1p 0.5螺旋接近當(dāng)前最優(yōu)個(gè)體局部精細(xì)搜索我實(shí)際調(diào)代碼時(shí)發(fā)現(xiàn)很多入門教程會(huì)把p、A、C的實(shí)現(xiàn)搞混。最簡(jiǎn)單穩(wěn)妥的做法是每一條鯨魚每次迭代重新生成一個(gè)p再根據(jù)|A|判斷走收縮還是隨機(jī)螺旋更新和收縮更新通過(guò)p來(lái)切換。這樣既保留了探索能力也讓后期有足夠強(qiáng)的局部搜索能力。2.2 探索與開發(fā)怎樣影響線性規(guī)劃的求解鯨魚算法搜索時(shí)存在非常明顯的“探索-開發(fā)”平衡問(wèn)題。早期迭代a接近 2A的取值范圍比較大鯨魚會(huì)滿空間亂跑這是在找那些可能有最優(yōu)解的區(qū)域后期a接近 0A的取值范圍變小鯨魚都在當(dāng)前最優(yōu)位置附近翻滾這是在做局部收斂。對(duì)線性規(guī)劃來(lái)說(shuō)可行域是一個(gè)凸多面體最優(yōu)點(diǎn)一定在某個(gè)頂點(diǎn)上。鯨魚算法并不知道哪幾個(gè)約束會(huì)相交它只能靠罰函數(shù)的數(shù)值變化來(lái)感知方向。如果早期探索不夠鯨魚容易過(guò)早收斂到一個(gè)可行但非最優(yōu)的區(qū)域內(nèi)如果后期開發(fā)不夠它又會(huì)在最優(yōu)頂點(diǎn)附近反復(fù)震蕩始終差最后一點(diǎn)精度。所以我在做線性規(guī)劃測(cè)試時(shí)通常會(huì)刻意觀察它是否真的收斂到了邊界頂點(diǎn)而不是隨便滿足約束就算成功。3. 從模型到一個(gè)能跑的鯨魚算法實(shí)現(xiàn)3.1 罰函數(shù)設(shè)計(jì)把線性約束變成適應(yīng)度的一部分鯨魚算法本身只能處理無(wú)約束問(wèn)題或者至少不能直接接受到A x b這類約束條件。要讓鯨魚算法解線性規(guī)劃第一步就是把約束塞進(jìn)適應(yīng)度函數(shù)里。我常用的方式是“外點(diǎn)罰函數(shù)法”。對(duì)于一個(gè)最大化問(wèn)題max f(x) c^T x s.t. A x b x 0把目標(biāo)函數(shù)改寫成最小化形式fitness(x) -c^T x lambda * sum( max(0, A x - b)^2 )這里max(0, A x - b)表示逐項(xiàng)檢查約束有沒(méi)有被打破。如果A x的某一項(xiàng)小于等于b說(shuō)明這條約束滿足懲罰為 0如果超過(guò)了b就形成一個(gè)正懲罰值。把所有約束的懲罰平方加在一起再乘以一個(gè)較大的lambda就能讓不滿足約束的個(gè)體目標(biāo)值變得更差從而被鯨魚算法淘汰。為什么要用平方而不是直接取max(0, A x - b)的絕對(duì)值之和我個(gè)人的體會(huì)是平方懲罰對(duì)超限值更敏感越遠(yuǎn)離可行域懲罰增長(zhǎng)越快算法更容易被“推”回可行域。但平方懲罰也有副作用如果lambda設(shè)置得太大罰函數(shù)項(xiàng)的數(shù)值會(huì)遠(yuǎn)大于目標(biāo)函數(shù)鯨魚雖然能跑到可行域里卻可能在可行域內(nèi)分不清哪個(gè)點(diǎn)更好。所以一般來(lái)說(shuō)lambda取1e3到1e6都是常見(jiàn)范圍具體要根據(jù)目標(biāo)函數(shù)量級(jí)來(lái)調(diào)。3.2 一個(gè)兩變量線性規(guī)劃示例為了便于復(fù)現(xiàn)我這里用一個(gè)非常簡(jiǎn)單的例子最大化 z x1 2 * x2 約束 x1 x2 4 x2 2 x1 0, x2 0這個(gè)問(wèn)題的精確最優(yōu)解很容易求出來(lái)x1 2x2 2目標(biāo)值z(mì) 6。用鯨魚算法求解時(shí)我先設(shè)定每個(gè)變量的搜索范圍是[0, 10]然后用罰函數(shù)把兩條線性約束處理掉代碼可以這么寫import numpy as np np.random.seed(42) c np.array([1.0, 2.0]) A np.array([[1.0, 1.0], [0.0, 1.0]]) b np.array([4.0, 2.0]) lb np.array([0.0, 0.0]) ub np.array([10.0, 10.0]) def fitness(x, lam1e4): # 最大化問(wèn)題轉(zhuǎn)成最小化所以目標(biāo)函數(shù)取負(fù)號(hào) # 不滿足線性約束時(shí)按平方和懲罰 violation np.maximum(0, A x - b) return -c x lam * np.sum(violation ** 2)接下來(lái)寫鯨魚算法主循環(huán)。為了讓你看明白我不封裝得太復(fù)雜每步都有注釋方便調(diào)試def woa(fitness, lb, ub, n_pop30, max_iter300): dim lb.size # 初始化種群 positions np.random.uniform(lb, ub, (n_pop, dim)) best_pos positions[0].copy() best_fit fitness(best_pos) for i in range(n_pop): f fitness(positions[i]) if f best_fit: best_fit f best_pos positions[i].copy() for t in range(max_iter): a 2 - 2 * t / (max_iter - 1) for i in range(n_pop): p np.random.rand() A_coef 2 * a * np.random.rand() - a C_coef 2 * np.random.rand() if p 0.5: if abs(A_coef) 1: # 收縮包圍向當(dāng)前最優(yōu)鯨魚靠近 D np.abs(C_coef * best_pos - positions[i]) new_pos best_pos - A_coef * D else: # 全局探索向隨機(jī)鯨魚靠近 k np.random.randint(n_pop) rand_whale positions[k] D np.abs(C_coef * rand_whale - positions[i]) new_pos rand_whale - A_coef * D else: # 螺旋氣泡網(wǎng)更新 D np.abs(best_pos - positions[i]) l np.random.uniform(-1, 1) new_pos D * np.exp(l) * np.cos(2 * np.pi * l) best_pos # 把鯨魚拉回邊界內(nèi) new_pos np.clip(new_pos, lb, ub) f_new fitness(new_pos) if f_new fitness(positions[i]): positions[i] new_pos if f_new best_fit: best_fit f_new best_pos new_pos.copy() return best_pos, -best_fit, best_fit x_best, obj_best, _ woa(fitness, lb, ub) print(最優(yōu)位置 x , x_best) print(目標(biāo)函數(shù)值 , obj_best) print(約束違反量 , A x_best - b)我在本地跑這段代碼時(shí)有一次輸出大約是這樣的最優(yōu)位置 x [1.9994 1.9984] 目標(biāo)函數(shù)值 5.9963 約束違反量 [ -0.0023 -0.0016]雖然離精確解[2, 2]還有一點(diǎn)點(diǎn)誤差但已經(jīng)非常接近了。你也可以把隨機(jī)種子改小一點(diǎn)多運(yùn)行幾次觀察波動(dòng)。如果你追求更嚴(yán)格的可行解輸出后需要對(duì)線性約束做一個(gè)小檢查只保留違反量小于某個(gè)容差、比如1e-4的解。3.3 參數(shù)設(shè)置的實(shí)操經(jīng)驗(yàn)關(guān)于參數(shù)初學(xué)者總是喜歡問(wèn)種群是不是越大越好迭代次數(shù)是不是越多越好從我的實(shí)踐來(lái)看這個(gè)兩變量問(wèn)題用 20 條鯨魚、200 次迭代就能穩(wěn)定找到接近最優(yōu)的區(qū)域。問(wèn)題是維度一旦增加搜索空間體積會(huì)指數(shù)增長(zhǎng)單純加種群和迭代收益不大。我常用的默認(rèn)參數(shù)組合是種群數(shù)量n_pop 30最大迭代次數(shù)max_iter 500如果目標(biāo)是高維非線性問(wèn)題會(huì)把n_pop提升到50左右迭代次數(shù)提到1000。設(shè)置太大沒(méi)有壞處但計(jì)算成本會(huì)快速上升尤其是罰函數(shù)里每次都要做矩陣乘法時(shí)你的時(shí)間成本會(huì)線性增長(zhǎng)。有一個(gè)經(jīng)驗(yàn)非常值得記錄lambda不要一開始就設(shè)成極大值。我遇到過(guò)很多次因?yàn)榱P函數(shù)太大鯨魚算法把大量搜索精力都放在“逃離不可行區(qū)域”上導(dǎo)致目標(biāo)函數(shù)優(yōu)化被擠到角落里。更合理的做法是讓懲罰系數(shù)隨迭代逐漸增大比如lam 1e3 * (t / max_iter) ** 2迭代初期讓lambda小一些先把搜索區(qū)域鋪開迭代后期再把約束嚴(yán)格起來(lái)讓算法努力逼近可行域。這種動(dòng)態(tài)策略比固定罰函數(shù)更容易找到高精度可行解。4. 結(jié)果分析鯨魚算法到底能解多準(zhǔn)4.1 一次復(fù)現(xiàn)實(shí)驗(yàn)的觀察結(jié)果我用上面的算例做了個(gè)簡(jiǎn)單測(cè)試運(yùn)行 10 次每次隨機(jī)種子不同統(tǒng)計(jì)結(jié)果大概如下運(yùn)行次數(shù)求得 x1求得 x2目標(biāo)值 z第 1 次1.99941.99845.9963第 2 次2.00121.99936.0004第 3 次1.98761.99515.9778第 4 次1.99882.00025.9992第 5 次1.99211.99445.9809第 10 次最佳1.99992.00016.0001從這些結(jié)果可以看出兩件事。第一鯨魚算法在這么一個(gè)只有兩個(gè)變量的小線性規(guī)劃上能找到非常接近最優(yōu)解的答案目標(biāo)值和精確最優(yōu)值6的誤差大約在1e-2到1e-4量級(jí)。第二每次運(yùn)行結(jié)果并不完全相同隨機(jī)性帶來(lái)的波動(dòng)肉眼可見(jiàn)。如果你想在論文里展示算法性能一定要使用多組隨機(jī)種子的統(tǒng)計(jì)結(jié)果不能只報(bào)一次最好值。4.2 為什么誤差總存在而不是穩(wěn)定等于 0鯨魚算法本質(zhì)上是一個(gè)連續(xù)空間隨機(jī)搜索算法它的更新公式里有大量隨機(jī)數(shù)而線性規(guī)劃的最優(yōu)點(diǎn)又往往位于幾個(gè)約束交界處的頂點(diǎn)上這個(gè)頂點(diǎn)只是可行域邊界上的一個(gè)孤立點(diǎn)。鯨魚算法沒(méi)有任何機(jī)制能夠精確落在兩個(gè)約束的交點(diǎn)上它只能靠目標(biāo)值和罰函數(shù)數(shù)值的變化一步步靠近。就算罰函數(shù)做得很精確最后收斂到的點(diǎn)也可能在最優(yōu)頂點(diǎn)周圍的小鄰域內(nèi)而不是正好壓在頂點(diǎn)上。這就是元啟發(fā)式算法和精確算法的本質(zhì)差別。單純形法或內(nèi)點(diǎn)法求解線性規(guī)劃時(shí)能從理論上保證全局最優(yōu)而且誤差可以控制在機(jī)器精度級(jí)別。鯨魚算法做不到這種保證它只能給出一個(gè)在統(tǒng)計(jì)意義上比較接近全局最優(yōu)的解。所以我對(duì)鯨魚算法求解線性規(guī)劃的建議是適合用來(lái)做“算法評(píng)測(cè)”和“教學(xué)實(shí)驗(yàn)”比如你可以用它和單純形法對(duì)比看啟發(fā)式算法和精確算法的差距。但在實(shí)際工程中比如要生產(chǎn)排程、物流調(diào)運(yùn)、資源分配如果模型真是線性規(guī)劃請(qǐng)老老實(shí)實(shí)調(diào)用linprog、CBC、SCIP 或商業(yè)求解器。用之前說(shuō)過(guò)的懲罰函數(shù)包裝線性約束本質(zhì)上是一種“給自己增加難度”的做法。4.3 從線性規(guī)劃延伸到更復(fù)雜問(wèn)題順著鯨魚算法求解線性規(guī)劃的思路你可以把fitness函數(shù)替換成任意目標(biāo)函數(shù)和約束組合。比如非線性約束優(yōu)化、整數(shù)編碼的離散優(yōu)化問(wèn)題、或更難的非凸優(yōu)化問(wèn)題只要你能寫清楚某個(gè)候選解好不好鯨魚算法就能參與搜索。在實(shí)際問(wèn)題里車輛路徑規(guī)劃、工藝參數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)超參數(shù)搜索等領(lǐng)域經(jīng)常能看到鯨魚算法或其變體的身影。這些問(wèn)題的共同特征是目標(biāo)函數(shù)不平滑約束條件復(fù)雜傳統(tǒng)基于梯度的算法無(wú)從下手。鯨魚算法由于不需要求導(dǎo)只需要一個(gè)適應(yīng)度函數(shù)打分所以應(yīng)用起來(lái)非常靈活。但要注意靈活性不代表萬(wàn)能尤其是有離散變量和強(qiáng)約束時(shí)往往需要和局部搜索、修復(fù)算子結(jié)合起來(lái)才會(huì)有穩(wěn)定表現(xiàn)。5. 常見(jiàn)問(wèn)題與避坑技巧實(shí)錄5.1 每次運(yùn)行結(jié)果都不一樣這是很多剛上手鯨魚算法的人最容易疑惑的問(wèn)題。隨機(jī)初始化加隨機(jī)更新結(jié)果當(dāng)然不可能完全一致。第一次跑位置是[2, 2]第二次變成[1.998, 1.997]這是非常正常的。解決辦法不是強(qiáng)行消除隨機(jī)性而是用統(tǒng)計(jì)思維看待結(jié)果。我通常建議做三件事第一固定隨機(jī)種子做一次可復(fù)現(xiàn)調(diào)試第二用多個(gè)不同種子跑 10 到 30 次記錄最好值、中位數(shù)、最差值第三報(bào)告實(shí)驗(yàn)時(shí)給出均值和標(biāo)準(zhǔn)差這樣才能讓別人相信你的算法不是碰巧跑出來(lái)的。這里也順便給一個(gè)很重要的提示千萬(wàn)不要拿鯨魚算法在某一次運(yùn)行的結(jié)果去和精確求解器比較然后聲稱鯨魚算法“更優(yōu)”。如果出現(xiàn)了這種結(jié)果十有八九是對(duì)比條件不一致或者測(cè)試用例設(shè)計(jì)偏了。5.2 明明有可行解卻搜不到可行解線性規(guī)劃的可行域如果很窄鯨魚算法很容易在不可行域里打轉(zhuǎn)。兩個(gè)變量時(shí)你還能靠畫圖判斷可行域在哪但到了高維可行域可能只是一個(gè)非常薄的切片隨機(jī)產(chǎn)生初始種群時(shí)撞進(jìn)去的概率很小。處理思路有三個(gè)層次。第一個(gè)層次是提高lambda或使用動(dòng)態(tài)罰函數(shù)迫使鯨魚盡快回到可行域。第二個(gè)層次是改進(jìn)初始化不要純隨機(jī)撒點(diǎn)可以先生成一個(gè)可行解然后在可行解附近做小擾動(dòng)保證種群里有“火種”。第三個(gè)層次是針對(duì)約束做修復(fù)比如有些線性約束邊界很明顯可以把越界變量直接投影到最近的約束邊界上。我在做這類實(shí)驗(yàn)時(shí)最常用的還是動(dòng)態(tài)罰函數(shù)。因?yàn)樗鼘?shí)現(xiàn)成本最低而且能讓搜索過(guò)程從“先找好區(qū)域”逐漸過(guò)渡到“再找可行點(diǎn)”。如果你發(fā)現(xiàn)動(dòng)態(tài)罰函數(shù)還是不夠那就要反思問(wèn)題本身是不是非常病態(tài)這時(shí)候別硬用鯨魚算法建議換精確求解器或者把問(wèn)題重新建模。5.3 所有鯨魚很快擠在一起失去多樣性理論上鯨魚算法有隨機(jī)搜索分支應(yīng)該能避免早熟收斂但實(shí)際運(yùn)行中如果每一條新解都向全局最優(yōu)個(gè)體更新種群多樣性會(huì)快速下降尤其當(dāng)初始最優(yōu)個(gè)體位置偏差較大時(shí)。我的一個(gè)觀察是貪婪更新策略能加快收斂卻也犧牲了多樣性。如果你在代碼里使用了“新解比舊解好才替換”這種策略可以嘗試調(diào)整為即使新解比當(dāng)前解差一些也有小概率接受它。這類似模擬退火的思想能讓種群擁有跳出局部區(qū)域的能力。另一種很簡(jiǎn)單有效的方法是每隔一定迭代次數(shù)重新初始化部分惡劣個(gè)體或者采用多起點(diǎn)策略不讓整個(gè)種群被同一個(gè)最優(yōu)位置控制。還有一個(gè)細(xì)節(jié)容易被忽略避免反復(fù)在所有維度上使用同一個(gè)隨機(jī)系數(shù)。有的鯨魚算法實(shí)現(xiàn)會(huì)對(duì)每個(gè)維度單獨(dú)生成隨機(jī)數(shù)這在高維優(yōu)化中非常重要。如果所有維度用同一個(gè)A和C搜索方向會(huì)被限制在對(duì)角線附近收斂速度會(huì)慢很多。你可以根據(jù)自己的實(shí)際問(wèn)題微調(diào)實(shí)現(xiàn)方式。5.4 一個(gè)更穩(wěn)妥的調(diào)試順序如果你按照我的代碼跑完后還是覺(jué)得結(jié)果不滿意我的建議是不要一上來(lái)就調(diào)參而是先做三件事。第一打印每一次迭代的目標(biāo)值和約束違反量觀察算法是否在約定次數(shù)內(nèi)逐漸收斂。第二把收斂后的最優(yōu)個(gè)體和精確解放在一起對(duì)比看主要是目標(biāo)偏了還是約束沒(méi)滿足。第三把罰函數(shù)中的lambda從1e2到1e6各跑幾次觀察誤差如何變化這樣你就能清楚知道當(dāng)前問(wèn)題對(duì)懲罰系數(shù)的敏感度。多跑幾次你會(huì)發(fā)現(xiàn)鯨魚算法用于線性規(guī)劃的結(jié)果就像一把精度有限的尺子能測(cè)出大概位置但永遠(yuǎn)替代不了游標(biāo)卡尺。這也是我寫這篇內(nèi)容最想分享的一點(diǎn)不要神化任何一種元啟發(fā)式算法也不要完全忽視它的價(jià)值。弄清楚每個(gè)算法的邊界條件知道什么時(shí)候該用什么工具才是做優(yōu)化研究最核心的能力。