階實(shí)戰(zhàn)：整數(shù)規(guī)劃、TSP 固定端點(diǎn)與初始種群設(shè)定)
科學(xué)計(jì)算【免費(fèi)下載鏈接】scikit-opt主流群體智能算法差分進(jìn)化算法、遺傳算法、粒子群算法、模擬退火算法、蟻群算法、免疫優(yōu)化算法、魚群算法解決常規(guī)最優(yōu)化問題以及旅行商問題項(xiàng)目地址https://gitcode.com/guofei9987/scikit-opt點(diǎn)擊查看免費(fèi)下載遺傳算法GA在實(shí)際落地時(shí)往往會(huì)遇到三個(gè)經(jīng)典痛點(diǎn)如何讓某些變量嚴(yán)格取整數(shù)、如何在旅行商問題TSP中固定起點(diǎn)與終點(diǎn)、以及如何注入自定義的初始解。本指南以 scikit-opt 倉庫中的 more_ga.md 為骨架結(jié)合 GA.py 的源碼實(shí)現(xiàn)與 demo_ga_tsp.py 等示例逐條給出可直接運(yùn)行的代碼與底層原理讀完即可在自己的優(yōu)化任務(wù)中復(fù)現(xiàn)這三種進(jìn)階玩法。用遺傳算法做整數(shù)規(guī)劃核心用法讓precision為整數(shù)在多維優(yōu)化中想讓哪個(gè)變量被限制為整數(shù)就把對(duì)應(yīng)位置的precision設(shè)為整數(shù)。例如自定義目標(biāo)函數(shù)demo_func希望第一個(gè)變量按步長(zhǎng) 2 取值即整數(shù)且間隔為 2、第二個(gè)變量按步長(zhǎng) 1 取值普通整數(shù)、第三個(gè)變量保持浮點(diǎn)數(shù)精度只需寫precision[2, 1, 1e-7]from sko.GA import GA demo_func lambda x: (x[0] - 1) ** 2 (x[1] - 0.05) ** 2 x[2] ** 2 ga GA(funcdemo_func, n_dim3, max_iter500, lb[-1, -1, -1], ub[5, 1, 1], precision[2, 1, 1e-7]) best_x, best_y ga.run() print(best_x:, best_x, \n, best_y:, best_y)注意precision的語義是該變量的取值粒度整數(shù)模式下第 0 維變量的實(shí)際取值是lb[0] k * 2k 為非負(fù)整數(shù)第 1 維是lb[1] k * 1第 2 維仍按 1e-7 的浮點(diǎn)精度連續(xù)取值。precision支持標(biāo)量自動(dòng)廣播到每個(gè)維度也支持列表或數(shù)組這一點(diǎn)在 GA.py 中通過np.array(precision) * np.ones(self.n_dim)完成。整數(shù)規(guī)劃模式背后的編碼機(jī)制從 GA.py 的源碼可以看到GA用二進(jìn)制染色體Gray Code分段編碼每個(gè)變量段長(zhǎng)由精度決定Lind_raw np.log2((self.ub - self.lb) / self.precision 1) self.Lind np.ceil(Lind_raw).astype(int) self.int_mode_ (self.precision % 1 0) (Lind_raw % 1 ! 0) self.int_mode np.any(self.int_mode_) if self.int_mode: self.ub_extend np.where(self.int_mode_ , self.lb (np.exp2(self.Lind) - 1) * self.precision , self.ub)這里有幾個(gè)可以直接用于調(diào)參的結(jié)論precision為整數(shù)時(shí)該維度進(jìn)入整數(shù)規(guī)劃模式int_modeprecision為浮點(diǎn)如默認(rèn)的 1e-7時(shí)變量按連續(xù)區(qū)間映射。取值個(gè)數(shù)最好是 $2^n$。此時(shí)染色體段長(zhǎng) $Lind\log_2(取值個(gè)數(shù))$ 恰好是整數(shù)每個(gè)取值與一組二進(jìn)制編碼一一對(duì)應(yīng)收斂速度與效果最佳。取值個(gè)數(shù)不是 $2^n$ 時(shí)依然能正常工作代價(jià)是部分編碼會(huì)冗余。從源碼看當(dāng)取值個(gè)數(shù)不是 $2^n$ 時(shí)GA會(huì)自動(dòng)把上界擴(kuò)展到ub_extend lb (2**Lind - 1) * precision見 GA.py使可編碼取值總數(shù)恰好等于 $2^{Lind}$解碼時(shí)再用np.where(X self.ub, self.ub, X)把超出原ub的值裁剪回去見 GA.py。對(duì)取值個(gè)數(shù)不是 $2^n$的場(chǎng)景文檔還提示了另一層約束如果你的等式約束constraint_eq與不等式約束constraint_ueq本身已經(jīng)很多罰函數(shù)帶來的影響會(huì)被放大更推薦先手動(dòng)調(diào)整變量規(guī)避取值個(gè)數(shù)不是 $2^n$ 的情況。這一提示與 base.py 中x2y()的罰函數(shù)實(shí)現(xiàn)相互印證——約束違背會(huì)以1e5量級(jí)的懲罰項(xiàng)疊加到目標(biāo)值上見 GA.py約束越多搜索空間越崎嶇。非整數(shù)precision想用整數(shù)模式怎么辦如果precision不是整數(shù)例如原本是 0.5它不會(huì)進(jìn)入整數(shù)規(guī)劃模式。想沿用整數(shù)模式文檔給出的標(biāo)準(zhǔn)手法是把對(duì)應(yīng)自變量乘以 2使precision變成整數(shù)。例如原變量x ∈ [0, 1]、precision0.5可令新變量y 2x ∈ [0, 2]、precision1參與優(yōu)化最后再把best_x除以 2 還原。本質(zhì)是先縮放再做整數(shù)編碼最后反變換。GA 求解 TSP如何固定起點(diǎn)與終點(diǎn)原理起點(diǎn)終點(diǎn)不參與優(yōu)化TSP 有兩種形態(tài)閉合回路環(huán)與開環(huán)路徑。若路徑是閉合的起點(diǎn)與終點(diǎn)本就在環(huán)上固定與否結(jié)果等價(jià)無需特殊處理只有要求非閉合路徑從指定起點(diǎn)出發(fā)、在指定終點(diǎn)停下時(shí)才需要固定端點(diǎn)。固定起止點(diǎn)的核心思路非常簡(jiǎn)潔設(shè)總共有n 2個(gè)點(diǎn)含起點(diǎn)和終點(diǎn)優(yōu)化的只是中間n個(gè)點(diǎn)的訪問順序起點(diǎn)、終點(diǎn)不進(jìn)入決策變量目標(biāo)函數(shù)按真實(shí)路徑書寫把起點(diǎn)、終點(diǎn)拼接到routine首尾累加相鄰點(diǎn)之間的歐氏距離。例如起點(diǎn)為(0, 0)、終點(diǎn)為(1, 1)則目標(biāo)函數(shù)構(gòu)造如下import numpy as np from scipy import spatial import matplotlib.pyplot as plt num_points 20 points_coordinate np.random.rand(num_points, 2) # generate coordinate of points start_point[[0,0]] end_point[[1,1]] points_coordinatenp.concatenate([points_coordinate,start_point,end_point]) distance_matrix spatial.distance.cdist(points_coordinate, points_coordinate, metriceuclidean) def cal_total_distance(routine): The objective function. input routine, return total distance. cal_total_distance(np.arange(num_points)) num_points, routine.shape # start_point,end_point 本身不參與優(yōu)化。給一個(gè)固定的值參與計(jì)算總路徑 routine np.concatenate([[num_points], routine, [num_points1]]) return sum([distance_matrix[routine[i], routine[i 1]] for i in range(num_points2-1)])注意這里points_coordinate拼接后num_points號(hào)點(diǎn)就是起點(diǎn)(0, 0)num_points1號(hào)點(diǎn)就是終點(diǎn)(1, 1)決策變量routine是中間n個(gè)點(diǎn)的排列長(zhǎng)度恰為num_points。求解與可視化用GA_TSP求解的方式與其他 TSP 場(chǎng)景一致from sko.GA import GA_TSP ga_tsp GA_TSP(funccal_total_distance, n_dimnum_points, size_pop50, max_iter500, prob_mut1) best_points, best_distance ga_tsp.run() fig, ax plt.subplots(1, 2) best_points_ np.concatenate([[num_points],best_points, [num_points1]]) best_points_coordinate points_coordinate[best_points_, :] ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], o-r) ax[1].plot(ga_tsp.generation_best_Y) plt.show()左圖把最優(yōu)排列還原為起點(diǎn) → 中間 n 點(diǎn) → 終點(diǎn)的完整坐標(biāo)序列并連線直觀驗(yàn)證路徑確實(shí)從(0,0)出發(fā)、在(1,1)結(jié)束右圖繪制ga_tsp.generation_best_Y即每一代最優(yōu)距離的收斂曲線可用于判斷max_iter是否足夠。與閉合回路 TSP 的實(shí)現(xiàn)差異對(duì)比倉庫中的閉合回路版本 demo_ga_tsp.py其目標(biāo)函數(shù)用取模實(shí)現(xiàn)首尾相連return sum([distance_matrix[routine[i % num_points], routine[(i 1) % num_points]] for i in range(num_points)])而固定端點(diǎn)版本則用np.concatenate顯式把兩個(gè)固定端點(diǎn)夾在首尾。兩種寫法都對(duì)應(yīng)GA_TSP內(nèi)部的排列編碼從 GA.py 可以看到GA_TSP用tmp.argsort(axis1)生成全排列種群交叉算子采用部分匹配交叉PMX見 crossover.py變異算子采用 2-Opt 式的反轉(zhuǎn)變異mutation_reverse見 mutation.py。PMX 與反轉(zhuǎn)變異都能保證子代仍是合法排列這正是排列類優(yōu)化能正確收斂的結(jié)構(gòu)基礎(chǔ)。另外注意GA_TSP.run()與普通GA.run()的差異前者每一代把父代與子代合并后按適應(yīng)度截取最優(yōu)的size_pop個(gè)個(gè)體精英保留策略見 GA.py因此在同樣代數(shù)下搜索強(qiáng)度更高max_iter可適當(dāng)調(diào)小。如何設(shè)定初始點(diǎn)或初始種群四種核心算法都支持注入初始解做法各不相同算法注入方式說明遺傳算法GAga.Chrom ...直接覆蓋初始二進(jìn)制染色體種群差分進(jìn)化DEde.X ...直接覆蓋初始實(shí)數(shù)種群矩陣模擬退火SA構(gòu)造時(shí)傳x0初始化起始點(diǎn)粒子群PSOpso.X ...后補(bǔ)算歷史最優(yōu)覆蓋粒子位置并同步 pbest / gbestGA覆蓋Chrom對(duì)于GA實(shí)例化ga GA(**params)后直接給Chrom賦值即可設(shè)定初始種群例如ga.Chrom np.random.randint(0, 2, size(80, 20))這里的Chrom是形狀為(size_pop, len_chrom)的 0/1 矩陣行數(shù)80對(duì)應(yīng)種群個(gè)體數(shù)應(yīng)與size_pop一致列數(shù)20對(duì)應(yīng)整條染色體的基因總長(zhǎng)。從源碼看染色體總長(zhǎng)為各變量編碼段長(zhǎng)之和self.len_chrom sum(self.Lind)見 GA.py如果你自定義的列數(shù)小于len_chromchrom2x()解碼時(shí)會(huì)直接越界出錯(cuò)因此手動(dòng)賦值前最好先用默認(rèn)值跑一次檢查ga.len_chrom與ga.size_pop。默認(rèn)初始種群由crtbp()生成即np.random.randint(low0, high2, size(self.size_pop, self.len_chrom))見 GA.py手動(dòng)賦值只是把這一隨機(jī)初始化替換為你的先驗(yàn)知識(shí)。DE覆蓋X差分進(jìn)化算法DE中de.X是形狀為(size_pop, n_dim)的實(shí)數(shù)種群矩陣默認(rèn)由crtbp()在[lb, ub]內(nèi)均勻隨機(jī)采樣生成見 DE.py。要注入初始解直接賦值即可de.X my_initial_population # shape: (size_pop, n_dim)后續(xù)mutation()的變異基向量V[i] X[r1] F * (X[r2] - X[r3])見 DE.py會(huì)自動(dòng)基于你給定的X展開且變異越界時(shí)會(huì)被重新采樣到[lb, ub]內(nèi)因此不必?fù)?dān)心越界問題。SA構(gòu)造時(shí)傳x0模擬退火算法SA的初始點(diǎn)通過構(gòu)造函數(shù)參數(shù)x0傳入。從 SA.py 的源碼看__init__(self, func, x0, T_max100, T_min1e-7, L300, max_stay_counter150, **kwargs)會(huì)執(zhí)行self.n_dim len(x0)、self.best_x np.array(x0)即x0同時(shí)決定了解空間的維度和搜索的出發(fā)點(diǎn)from sko.SA import SA sa SA(funcdemo_func, x0[0.5, 0.5], T_max100, T_min1e-7, L300, max_stay_counter150) best_x, best_y sa.run()PSO覆蓋X并同步 pbest / gbest粒子群算法PSO初始化時(shí)會(huì)在[lb, ub]內(nèi)隨機(jī)生成粒子位置self.X np.random.uniform(lowself.lb, highself.ub, size(self.pop, self.n_dim))見 PSO.py。手動(dòng)注入初始解的正確姿勢(shì)是賦值pso.X之后立即補(bǔ)算三個(gè)狀態(tài)量pso.X my_initial_particles # shape: (pop, n_dim) pso.cal_y() # 重算每個(gè)粒子的適應(yīng)度 Y func(X) pso.update_gbest() # 更新全局最優(yōu) gbest_x / gbest_y pso.update_pbest() # 更新每個(gè)粒子的歷史最優(yōu) pbest_x / pbest_y順序有講究cal_y()先刷新self.Y見 PSO.pyupdate_pbest()用Y更小且滿足約束的粒子更新個(gè)體歷史最優(yōu)見 PSO.pyupdate_gbest()從pbest_y中挑出全局最優(yōu)見 PSO.py。如果只改X不調(diào)用這三個(gè)方法后續(xù)迭代的速度更新V w*V cp*r1*(pbest_x - X) cg*r2*(gbest_x - X)會(huì)基于錯(cuò)誤的 pbest/gbest 進(jìn)行注入的初始解反而可能把種群帶偏。為什么不建議直接復(fù)用.fit()的舊寫法倉庫基類 base.py 中保留了fit()作為run()的兼容別名但會(huì)拋出DeprecationWarning。文檔與示例均推薦統(tǒng)一使用run()例如best_x, best_y ga.run()上文的 TSP 固定端點(diǎn)示例也遵循了這一約定。如果你的歷史代碼仍在用.fit()建議盡快遷移。小結(jié)整數(shù)規(guī)劃把對(duì)應(yīng)維度的precision設(shè)為整數(shù)即可啟用整數(shù)模式取值個(gè)數(shù)盡量取 $2^n$非整數(shù)精度可先對(duì)變量做縮放變換。底層由 GA.py 的段長(zhǎng)計(jì)算、ub_extend擴(kuò)展與裁剪邏輯支撐。固定起止點(diǎn)的 TSP讓起點(diǎn)、終點(diǎn)不進(jìn)入決策變量?jī)H優(yōu)化中間n個(gè)點(diǎn)并在目標(biāo)函數(shù)中把兩端拼接回去配合GA_TSP的 PMX 交叉與反轉(zhuǎn)變異求解用左圖驗(yàn)證路徑、右圖觀察收斂曲線對(duì)比閉合回路版本見 demo_ga_tsp.py。初始解注入GA覆蓋ga.Chrom、DE覆蓋de.X、SA傳參x0、PSO覆蓋pso.X后依次執(zhí)行cal_y()/update_gbest()/update_pbest()。以上三種手法都只涉及求解器的調(diào)用方式目標(biāo)函數(shù)與數(shù)據(jù)準(zhǔn)備完全由你自己掌控因此同樣適用于后續(xù)引入更復(fù)雜的組合約束、先驗(yàn)路徑或多起點(diǎn)重啟策略的工程化場(chǎng)景。贊分享科學(xué)計(jì)算【免費(fèi)下載鏈接】scikit-opt主流群體智能算法差分進(jìn)化算法、遺傳算法、粒子群算法、模擬退火算法、蟻群算法、免疫優(yōu)化算法、魚群算法解決常規(guī)最優(yōu)化問題以及旅行商問題項(xiàng)目地址https://gitcode.com/guofei9987/scikit-opt點(diǎn)擊查看免費(fèi)下載相關(guān)推薦scikit-opt 遺傳算法進(jìn)階實(shí)戰(zhàn)整數(shù)規(guī)劃、TSP 固定端點(diǎn)與初始種群設(shè)定scikit opt 遺傳算法進(jìn)階實(shí)戰(zhàn)整數(shù)規(guī)劃、TSP 固定端點(diǎn)與初始種群設(shè)定 本篇基于 scikit opt 倉庫的 docs/zh/more_ga.md科學(xué)計(jì)算scikit-opt 遺傳算法進(jìn)階實(shí)戰(zhàn)整數(shù)規(guī)劃、TSP 固定起終點(diǎn)與初始種群設(shè)定scikit opt 遺傳算法進(jìn)階實(shí)戰(zhàn)整數(shù)規(guī)劃、TSP 固定起終點(diǎn)與初始種群設(shè)定 遺傳算法GA除了求解連續(xù)變量的最優(yōu)化問題還經(jīng)常需要處理整數(shù)規(guī)劃、旅行商科學(xué)計(jì)算scikit-opt 群體智能算法庫實(shí)戰(zhàn)指南七大算法求解最優(yōu)化問題與 TSP 路線規(guī)劃scikit opt 群體智能算法庫實(shí)戰(zhàn)指南七大算法求解最優(yōu)化問題與 TSP 路線規(guī)劃 scikit opt 是一個(gè)用 Python 實(shí)現(xiàn)的群體智能算法庫基科學(xué)計(jì)算上一篇Relay 查詢變量完全指南從全局變量到 arguments 與 argumentDefinitions下一篇CogVideoX-2b提示詞工程指南10個(gè)技巧讓你的視頻生成效果提升300%創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 scikit-opt 遺傳算法進(jìn)階實(shí)戰(zhàn)：整數(shù)規(guī)劃、TSP 固定端點(diǎn)與初始種群設(shè)定
科學(xué)計(jì)算【免費(fèi)下載鏈接】scikit-opt主流群體智能算法差分進(jìn)化算法、遺傳算法、粒子群算法、模擬退火算法、蟻群算法、免疫優(yōu)化算法、魚群算法解決常規(guī)最優(yōu)化問題以及旅行商問題項(xiàng)目地址https://gitcode.com/guofei9987/scikit-opt點(diǎn)擊查看免費(fèi)下載遺傳算法GA在實(shí)際落地時(shí)往往會(huì)遇到三個(gè)經(jīng)典痛點(diǎn)如何讓某些變量嚴(yán)格取整數(shù)、如何在旅行商問題TSP中固定起點(diǎn)與終點(diǎn)、以及如何注入自定義的初始解。本指南以 scikit-opt 倉庫中的 more_ga.md 為骨架結(jié)合 GA.py 的源碼實(shí)現(xiàn)與 demo_ga_tsp.py 等示例逐條給出可直接運(yùn)行的代碼與底層原理讀完即可在自己的優(yōu)化任務(wù)中復(fù)現(xiàn)這三種進(jìn)階玩法。用遺傳算法做整數(shù)規(guī)劃核心用法讓precision為整數(shù)在多維優(yōu)化中想讓哪個(gè)變量被限制為整數(shù)就把對(duì)應(yīng)位置的precision設(shè)為整數(shù)。例如自定義目標(biāo)函數(shù)demo_func希望第一個(gè)變量按步長(zhǎng) 2 取值即整數(shù)且間隔為 2、第二個(gè)變量按步長(zhǎng) 1 取值普通整數(shù)、第三個(gè)變量保持浮點(diǎn)數(shù)精度只需寫precision[2, 1, 1e-7]from sko.GA import GA demo_func lambda x: (x[0] - 1) ** 2 (x[1] - 0.05) ** 2 x[2] ** 2 ga GA(funcdemo_func, n_dim3, max_iter500, lb[-1, -1, -1], ub[5, 1, 1], precision[2, 1, 1e-7]) best_x, best_y ga.run() print(best_x:, best_x, \n, best_y:, best_y)注意precision的語義是該變量的取值粒度整數(shù)模式下第 0 維變量的實(shí)際取值是lb[0] k * 2k 為非負(fù)整數(shù)第 1 維是lb[1] k * 1第 2 維仍按 1e-7 的浮點(diǎn)精度連續(xù)取值。precision支持標(biāo)量自動(dòng)廣播到每個(gè)維度也支持列表或數(shù)組這一點(diǎn)在 GA.py 中通過np.array(precision) * np.ones(self.n_dim)完成。整數(shù)規(guī)劃模式背后的編碼機(jī)制從 GA.py 的源碼可以看到GA用二進(jìn)制染色體Gray Code分段編碼每個(gè)變量段長(zhǎng)由精度決定Lind_raw np.log2((self.ub - self.lb) / self.precision 1) self.Lind np.ceil(Lind_raw).astype(int) self.int_mode_ (self.precision % 1 0) (Lind_raw % 1 ! 0) self.int_mode np.any(self.int_mode_) if self.int_mode: self.ub_extend np.where(self.int_mode_ , self.lb (np.exp2(self.Lind) - 1) * self.precision , self.ub)這里有幾個(gè)可以直接用于調(diào)參的結(jié)論precision為整數(shù)時(shí)該維度進(jìn)入整數(shù)規(guī)劃模式int_modeprecision為浮點(diǎn)如默認(rèn)的 1e-7時(shí)變量按連續(xù)區(qū)間映射。取值個(gè)數(shù)最好是 $2^n$。此時(shí)染色體段長(zhǎng) $Lind\log_2(取值個(gè)數(shù))$ 恰好是整數(shù)每個(gè)取值與一組二進(jìn)制編碼一一對(duì)應(yīng)收斂速度與效果最佳。取值個(gè)數(shù)不是 $2^n$ 時(shí)依然能正常工作代價(jià)是部分編碼會(huì)冗余。從源碼看當(dāng)取值個(gè)數(shù)不是 $2^n$ 時(shí)GA會(huì)自動(dòng)把上界擴(kuò)展到ub_extend lb (2**Lind - 1) * precision見 GA.py使可編碼取值總數(shù)恰好等于 $2^{Lind}$解碼時(shí)再用np.where(X self.ub, self.ub, X)把超出原ub的值裁剪回去見 GA.py。對(duì)取值個(gè)數(shù)不是 $2^n$的場(chǎng)景文檔還提示了另一層約束如果你的等式約束constraint_eq與不等式約束constraint_ueq本身已經(jīng)很多罰函數(shù)帶來的影響會(huì)被放大更推薦先手動(dòng)調(diào)整變量規(guī)避取值個(gè)數(shù)不是 $2^n$ 的情況。這一提示與 base.py 中x2y()的罰函數(shù)實(shí)現(xiàn)相互印證——約束違背會(huì)以1e5量級(jí)的懲罰項(xiàng)疊加到目標(biāo)值上見 GA.py約束越多搜索空間越崎嶇。非整數(shù)precision想用整數(shù)模式怎么辦如果precision不是整數(shù)例如原本是 0.5它不會(huì)進(jìn)入整數(shù)規(guī)劃模式。想沿用整數(shù)模式文檔給出的標(biāo)準(zhǔn)手法是把對(duì)應(yīng)自變量乘以 2使precision變成整數(shù)。例如原變量x ∈ [0, 1]、precision0.5可令新變量y 2x ∈ [0, 2]、precision1參與優(yōu)化最后再把best_x除以 2 還原。本質(zhì)是先縮放再做整數(shù)編碼最后反變換。GA 求解 TSP如何固定起點(diǎn)與終點(diǎn)原理起點(diǎn)終點(diǎn)不參與優(yōu)化TSP 有兩種形態(tài)閉合回路環(huán)與開環(huán)路徑。若路徑是閉合的起點(diǎn)與終點(diǎn)本就在環(huán)上固定與否結(jié)果等價(jià)無需特殊處理只有要求非閉合路徑從指定起點(diǎn)出發(fā)、在指定終點(diǎn)停下時(shí)才需要固定端點(diǎn)。固定起止點(diǎn)的核心思路非常簡(jiǎn)潔設(shè)總共有n 2個(gè)點(diǎn)含起點(diǎn)和終點(diǎn)優(yōu)化的只是中間n個(gè)點(diǎn)的訪問順序起點(diǎn)、終點(diǎn)不進(jìn)入決策變量目標(biāo)函數(shù)按真實(shí)路徑書寫把起點(diǎn)、終點(diǎn)拼接到routine首尾累加相鄰點(diǎn)之間的歐氏距離。例如起點(diǎn)為(0, 0)、終點(diǎn)為(1, 1)則目標(biāo)函數(shù)構(gòu)造如下import numpy as np from scipy import spatial import matplotlib.pyplot as plt num_points 20 points_coordinate np.random.rand(num_points, 2) # generate coordinate of points start_point[[0,0]] end_point[[1,1]] points_coordinatenp.concatenate([points_coordinate,start_point,end_point]) distance_matrix spatial.distance.cdist(points_coordinate, points_coordinate, metriceuclidean) def cal_total_distance(routine): The objective function. input routine, return total distance. cal_total_distance(np.arange(num_points)) num_points, routine.shape # start_point,end_point 本身不參與優(yōu)化。給一個(gè)固定的值參與計(jì)算總路徑 routine np.concatenate([[num_points], routine, [num_points1]]) return sum([distance_matrix[routine[i], routine[i 1]] for i in range(num_points2-1)])注意這里points_coordinate拼接后num_points號(hào)點(diǎn)就是起點(diǎn)(0, 0)num_points1號(hào)點(diǎn)就是終點(diǎn)(1, 1)決策變量routine是中間n個(gè)點(diǎn)的排列長(zhǎng)度恰為num_points。求解與可視化用GA_TSP求解的方式與其他 TSP 場(chǎng)景一致from sko.GA import GA_TSP ga_tsp GA_TSP(funccal_total_distance, n_dimnum_points, size_pop50, max_iter500, prob_mut1) best_points, best_distance ga_tsp.run() fig, ax plt.subplots(1, 2) best_points_ np.concatenate([[num_points],best_points, [num_points1]]) best_points_coordinate points_coordinate[best_points_, :] ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], o-r) ax[1].plot(ga_tsp.generation_best_Y) plt.show()左圖把最優(yōu)排列還原為起點(diǎn) → 中間 n 點(diǎn) → 終點(diǎn)的完整坐標(biāo)序列并連線直觀驗(yàn)證路徑確實(shí)從(0,0)出發(fā)、在(1,1)結(jié)束右圖繪制ga_tsp.generation_best_Y即每一代最優(yōu)距離的收斂曲線可用于判斷max_iter是否足夠。與閉合回路 TSP 的實(shí)現(xiàn)差異對(duì)比倉庫中的閉合回路版本 demo_ga_tsp.py其目標(biāo)函數(shù)用取模實(shí)現(xiàn)首尾相連return sum([distance_matrix[routine[i % num_points], routine[(i 1) % num_points]] for i in range(num_points)])而固定端點(diǎn)版本則用np.concatenate顯式把兩個(gè)固定端點(diǎn)夾在首尾。兩種寫法都對(duì)應(yīng)GA_TSP內(nèi)部的排列編碼從 GA.py 可以看到GA_TSP用tmp.argsort(axis1)生成全排列種群交叉算子采用部分匹配交叉PMX見 crossover.py變異算子采用 2-Opt 式的反轉(zhuǎn)變異mutation_reverse見 mutation.py。PMX 與反轉(zhuǎn)變異都能保證子代仍是合法排列這正是排列類優(yōu)化能正確收斂的結(jié)構(gòu)基礎(chǔ)。另外注意GA_TSP.run()與普通GA.run()的差異前者每一代把父代與子代合并后按適應(yīng)度截取最優(yōu)的size_pop個(gè)個(gè)體精英保留策略見 GA.py因此在同樣代數(shù)下搜索強(qiáng)度更高max_iter可適當(dāng)調(diào)小。如何設(shè)定初始點(diǎn)或初始種群四種核心算法都支持注入初始解做法各不相同算法注入方式說明遺傳算法GAga.Chrom ...直接覆蓋初始二進(jìn)制染色體種群差分進(jìn)化DEde.X ...直接覆蓋初始實(shí)數(shù)種群矩陣模擬退火SA構(gòu)造時(shí)傳x0初始化起始點(diǎn)粒子群PSOpso.X ...后補(bǔ)算歷史最優(yōu)覆蓋粒子位置并同步 pbest / gbestGA覆蓋Chrom對(duì)于GA實(shí)例化ga GA(**params)后直接給Chrom賦值即可設(shè)定初始種群例如ga.Chrom np.random.randint(0, 2, size(80, 20))這里的Chrom是形狀為(size_pop, len_chrom)的 0/1 矩陣行數(shù)80對(duì)應(yīng)種群個(gè)體數(shù)應(yīng)與size_pop一致列數(shù)20對(duì)應(yīng)整條染色體的基因總長(zhǎng)。從源碼看染色體總長(zhǎng)為各變量編碼段長(zhǎng)之和self.len_chrom sum(self.Lind)見 GA.py如果你自定義的列數(shù)小于len_chromchrom2x()解碼時(shí)會(huì)直接越界出錯(cuò)因此手動(dòng)賦值前最好先用默認(rèn)值跑一次檢查ga.len_chrom與ga.size_pop。默認(rèn)初始種群由crtbp()生成即np.random.randint(low0, high2, size(self.size_pop, self.len_chrom))見 GA.py手動(dòng)賦值只是把這一隨機(jī)初始化替換為你的先驗(yàn)知識(shí)。DE覆蓋X差分進(jìn)化算法DE中de.X是形狀為(size_pop, n_dim)的實(shí)數(shù)種群矩陣默認(rèn)由crtbp()在[lb, ub]內(nèi)均勻隨機(jī)采樣生成見 DE.py。要注入初始解直接賦值即可de.X my_initial_population # shape: (size_pop, n_dim)后續(xù)mutation()的變異基向量V[i] X[r1] F * (X[r2] - X[r3])見 DE.py會(huì)自動(dòng)基于你給定的X展開且變異越界時(shí)會(huì)被重新采樣到[lb, ub]內(nèi)因此不必?fù)?dān)心越界問題。SA構(gòu)造時(shí)傳x0模擬退火算法SA的初始點(diǎn)通過構(gòu)造函數(shù)參數(shù)x0傳入。從 SA.py 的源碼看__init__(self, func, x0, T_max100, T_min1e-7, L300, max_stay_counter150, **kwargs)會(huì)執(zhí)行self.n_dim len(x0)、self.best_x np.array(x0)即x0同時(shí)決定了解空間的維度和搜索的出發(fā)點(diǎn)from sko.SA import SA sa SA(funcdemo_func, x0[0.5, 0.5], T_max100, T_min1e-7, L300, max_stay_counter150) best_x, best_y sa.run()PSO覆蓋X并同步 pbest / gbest粒子群算法PSO初始化時(shí)會(huì)在[lb, ub]內(nèi)隨機(jī)生成粒子位置self.X np.random.uniform(lowself.lb, highself.ub, size(self.pop, self.n_dim))見 PSO.py。手動(dòng)注入初始解的正確姿勢(shì)是賦值pso.X之后立即補(bǔ)算三個(gè)狀態(tài)量pso.X my_initial_particles # shape: (pop, n_dim) pso.cal_y() # 重算每個(gè)粒子的適應(yīng)度 Y func(X) pso.update_gbest() # 更新全局最優(yōu) gbest_x / gbest_y pso.update_pbest() # 更新每個(gè)粒子的歷史最優(yōu) pbest_x / pbest_y順序有講究cal_y()先刷新self.Y見 PSO.pyupdate_pbest()用Y更小且滿足約束的粒子更新個(gè)體歷史最優(yōu)見 PSO.pyupdate_gbest()從pbest_y中挑出全局最優(yōu)見 PSO.py。如果只改X不調(diào)用這三個(gè)方法后續(xù)迭代的速度更新V w*V cp*r1*(pbest_x - X) cg*r2*(gbest_x - X)會(huì)基于錯(cuò)誤的 pbest/gbest 進(jìn)行注入的初始解反而可能把種群帶偏。為什么不建議直接復(fù)用.fit()的舊寫法倉庫基類 base.py 中保留了fit()作為run()的兼容別名但會(huì)拋出DeprecationWarning。文檔與示例均推薦統(tǒng)一使用run()例如best_x, best_y ga.run()上文的 TSP 固定端點(diǎn)示例也遵循了這一約定。如果你的歷史代碼仍在用.fit()建議盡快遷移。小結(jié)整數(shù)規(guī)劃把對(duì)應(yīng)維度的precision設(shè)為整數(shù)即可啟用整數(shù)模式取值個(gè)數(shù)盡量取 $2^n$非整數(shù)精度可先對(duì)變量做縮放變換。底層由 GA.py 的段長(zhǎng)計(jì)算、ub_extend擴(kuò)展與裁剪邏輯支撐。固定起止點(diǎn)的 TSP讓起點(diǎn)、終點(diǎn)不進(jìn)入決策變量?jī)H優(yōu)化中間n個(gè)點(diǎn)并在目標(biāo)函數(shù)中把兩端拼接回去配合GA_TSP的 PMX 交叉與反轉(zhuǎn)變異求解用左圖驗(yàn)證路徑、右圖觀察收斂曲線對(duì)比閉合回路版本見 demo_ga_tsp.py。初始解注入GA覆蓋ga.Chrom、DE覆蓋de.X、SA傳參x0、PSO覆蓋pso.X后依次執(zhí)行cal_y()/update_gbest()/update_pbest()。以上三種手法都只涉及求解器的調(diào)用方式目標(biāo)函數(shù)與數(shù)據(jù)準(zhǔn)備完全由你自己掌控因此同樣適用于后續(xù)引入更復(fù)雜的組合約束、先驗(yàn)路徑或多起點(diǎn)重啟策略的工程化場(chǎng)景。贊分享科學(xué)計(jì)算【免費(fèi)下載鏈接】scikit-opt主流群體智能算法差分進(jìn)化算法、遺傳算法、粒子群算法、模擬退火算法、蟻群算法、免疫優(yōu)化算法、魚群算法解決常規(guī)最優(yōu)化問題以及旅行商問題項(xiàng)目地址https://gitcode.com/guofei9987/scikit-opt點(diǎn)擊查看免費(fèi)下載相關(guān)推薦scikit-opt 遺傳算法進(jìn)階實(shí)戰(zhàn)整數(shù)規(guī)劃、TSP 固定端點(diǎn)與初始種群設(shè)定scikit opt 遺傳算法進(jìn)階實(shí)戰(zhàn)整數(shù)規(guī)劃、TSP 固定端點(diǎn)與初始種群設(shè)定 本篇基于 scikit opt 倉庫的 docs/zh/more_ga.md科學(xué)計(jì)算scikit-opt 遺傳算法進(jìn)階實(shí)戰(zhàn)整數(shù)規(guī)劃、TSP 固定起終點(diǎn)與初始種群設(shè)定scikit opt 遺傳算法進(jìn)階實(shí)戰(zhàn)整數(shù)規(guī)劃、TSP 固定起終點(diǎn)與初始種群設(shè)定 遺傳算法GA除了求解連續(xù)變量的最優(yōu)化問題還經(jīng)常需要處理整數(shù)規(guī)劃、旅行商科學(xué)計(jì)算scikit-opt 群體智能算法庫實(shí)戰(zhàn)指南七大算法求解最優(yōu)化問題與 TSP 路線規(guī)劃scikit opt 群體智能算法庫實(shí)戰(zhàn)指南七大算法求解最優(yōu)化問題與 TSP 路線規(guī)劃 scikit opt 是一個(gè)用 Python 實(shí)現(xiàn)的群體智能算法庫基科學(xué)計(jì)算上一篇Relay 查詢變量完全指南從全局變量到 arguments 與 argumentDefinitions下一篇CogVideoX-2b提示詞工程指南10個(gè)技巧讓你的視頻生成效果提升300%創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考