問題
因工作需要，開始向算法的深水區邁進，其中就涉及到一種混合整數優化問題：CVRPTW 問題
cvrptw問題示例
顧名思義，CVRPTW 就是指帶限制條件和時間視窗限制的車輛路徑規劃問題，而加入了時間視窗的限制條件後，優化目标已不再是簡單的凹凸函數，這就意味着不能使用梯度下降、牛頓法等确定函數方法求解該問題（決策樹、神經網絡統統用不上了）
如果可以将CVRPTW的問題空間可視化的話，想象一下整個場景就是一個“喀斯特地貌”
之前習慣了确定方法求解凹凸問題，突然發現沒有“套路”可循後，頓時思維陷入了混亂
而一般的動态規劃問題求解器，或者混合整數求解器(google ortools、cplex等)，隻能處理小規模(<100)的限制優化問題
而市面上能快速處理1000個節點的求解器已經算是優秀了，但往往都是收費且價格不菲
随着節點數的增長，需要探索的路徑，也會呈幾何級數增長，是以傳統的運籌學求解器，已在性能上無法滿足需求
進化算法
EA進化算法 是一類算法的統稱（包含遺傳算法、粒子群算法、蟻群算法、魚群算法、蝙蝠算法等等）
通過人工産生上千個種群個體、每一個體探索不同的路徑，通過上百次疊代，進而找到帕累托最優解（有限組合方案最優）
進化算法示例
這種設計模式，充分的利用了分析主機多核并行的能力，加快了求解的速度，在性能上能滿足大規模全局優化的需求
在解空間較小時，求解速度也很可觀，兼顧了求解的準确性
關于進化算法，網上已經有了很詳盡的資料，但資訊太多反而容易造成資訊過載，說多了等于沒說
是以進化算法推薦看如下兩篇文章就夠了：
http://geatpy.com/index.php/2019/07/28/%e7%ac%ac%e4%b8%80%e7%ab%a0%ef%bc%9a%e6%a6%82%e8%bf%b0/ https://www.jianshu.com/p/8fa044ed9267其他的文章不是擺公式就是擺代碼，沒什麼意思
如果你覺得看這些文章也太麻煩，那我們就來個極簡版的白話進化算法入門：
這個世界上總有一類很難搞的問題，乍一看沒什麼規律，但各種限制，數學家稱之為NP hard問題
求解NP hard問題，就隻能像探索迷宮一樣，在指定的範圍内不斷探索，速度和方向可能是不斷變化的
指定的範圍就是搜尋空間
而探索可以是多線程的
探索的過程也可以是在之前經驗的基礎上不斷累加的 這就是進化算法最直覺的了解
不管它套上什麼“遺傳”、“粒子群”、“蟻群”等等的現實類比的外衣，都改變不了上述工作原理的本質
這樣看來，進化算法的原理其實是很簡單的
搜尋設計
是以整個進化算法應用的關鍵，就是如何設計搜尋空間和搜尋行為
搜尋空間設計的大小，直接決定了計算量的大小
搜尋行為政策設計的好壞，直接決定了系統的搜尋效率
搜尋設計示例
回到我們最初的話題，CVRPTW 問題該如何設計呢？
談到具體的問題，網上就很少有相關介紹資料了，設計思想大多隐藏在比較學術論文裡，也讓我苦惱了一陣子
CVRPTW 搜尋設計
有幾種主流設計方法：
1.将VRP問題轉換為TSP問題，然後所有目标點逐一排列，形成一個龐大的排序空間，例如：[1,2,3,4,5,……]，然後不斷随機搜尋
顯然，這樣導緻的結果就是會有n!種組合方案，n越大越糟糕，而且沒有考慮到TW時間視窗的限制
2.将VRP問題轉換為QAP問題，通過就近原則等一系列貪婪規則，形成初始可行解，然後不斷随機交換
這樣導緻的問題也是顯而易見的，貪婪規則的主觀性很強，很有可能漏掉部分解
一般設計思路示例
我的設計思路：
1.結合上述兩種思想，将CVRPTW問題轉換為限制優化問題；
2.最大限度的利用限制條件，形成盡可能小的搜尋空間；
3.最大限度的減小系統随機性，搜尋的每一步都盡可能的命中可行解；
4.在代價和目标之間做一個相對平衡的取舍； 總結
說了以上一堆，你也許覺得我啥都沒說 :-)
是的，遇到NP hard問題，是沒有萬金油的，隻能自己coding去嘗試
關鍵把握住進化的四個階段，一切就都清洗了：
1.搜尋空間設計；2.搜尋政策設計；3.評價方法；4.新搜尋空間生成；
對應到術語層面就是：
1.種群初始化；2.基因編碼、種群選擇；3.評價函數設計；4.交換、變異；
最後推薦兩款架構，大家可以自行搜尋：deap, geat
https://github.com/DEAP/deap https://github.com/geatpy-dev/geatpy這兩款架構都能很友善的實作你想要的進化算法
個人推薦deap,各個子產品的設計相對寬松和靈活
遺留問題
1.進化算法的搜尋速度：
疊代次數越多，找到的帕累托最優解更好，但很多生産場景其實是沒有足夠的時間留給模型慢慢摸索的
我也在不斷嘗試加速的可能
之前研究了AlphaGo及AlphaZero等技術，發現也是不能應用的，畢竟下棋或遊戲是确定性政策的動作，而車輛路徑中的上車點卻是不确定的
2.進化算法的計算規模：
不管進化算法怎麼疊代，總會受到計算規模的限制，縮小計算規模是是重中之重的工作
我也在不斷尋找有沒有可靠的降維政策理論和依據
以上，大家如有更好的解法，也請不吝賜教！
最後，祝大家在NP hard難搞的世界裡好運！;->