組合優(yōu)化問題概念
從廣義上講，組合優(yōu)化問題是涉及從有限的一組對象中找到"最佳"對象的問題?！白罴选笔峭ㄟ^給定的評估函數(shù)來測量的，該函數(shù)將對象映射到某個(gè)分?jǐn)?shù)或者成本，目標(biāo)是找到最高評估分?jǐn)?shù)和最低成本的對象。組合優(yōu)化往往涉及排序、分類、篩選等問題。以離散的COP問題來講，目標(biāo)就是從所有可行解中尋找一個(gè)集合、一個(gè)排列或者一個(gè)圖。
典型的組合優(yōu)化問題
旅行商問題（Traveling Salesman Problem - TSP)
加工調(diào)度問題（Scheduling Problem，如Flow-Shop，Job-Shop）
0-1背包問題（Knapsack Problem）
裝箱問題（Bin Packing Problem）
圖著色問題（Graph Coloring Problem）
聚類問題（Clustering Problem）
著名的旅行商問題（TSP）：假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑長度為所有路徑之中的最小值。TSP是一個(gè)典型的組合優(yōu)化問題，且是一個(gè)NP完全難題，關(guān)于NP的這個(gè)概念本文就不做詳細(xì)介紹了，但簡單的說就是：TSP問題目前尚不能找到一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的算法來求解。例如，下圖顯示了美國所有州所在城市的最佳旅游：
對于旅行商問題，計(jì)算的復(fù)雜度為O(n!)，在現(xiàn)實(shí)世界中出現(xiàn)TSP的實(shí)際實(shí)例通常具有數(shù)千個(gè)城市，所以是一個(gè)相當(dāng)高維的最優(yōu)求解問題。類比到其他的COP問題，又由于各類問題具有細(xì)微差別和約束，方案難以直接借用，對應(yīng)于這些問題的解決方案探索是漫長而艱巨的，并且可能需要領(lǐng)域?qū)＜业墓ぷ鱽頇z測特定問題的組合搜索空間中的某些結(jié)構(gòu)。
由于近年來深度學(xué)習(xí)在許多領(lǐng)域取得了巨大成功，讓機(jī)器學(xué)會如何自己解決問題的可能性聽起來非常有希望。將算法設(shè)計(jì)為自動化，可以為解決困難的COP問題可以節(jié)省大量的金錢和時(shí)間，也許可以產(chǎn)生比人類設(shè)計(jì)的方法更好的解決方案，正如我們在AlphaGo的成就中看到的那樣，這些成就擊敗了數(shù)千年的人類經(jīng)驗(yàn)。
對項(xiàng)目的想法：
BIOS配置尋優(yōu)也可以理解為組合優(yōu)化問題，是一個(gè)NP-hard問題，具有高維的離散動作空間。
組合優(yōu)化求解算法
傳統(tǒng)算法
- 精確算法
精確算法是指能夠求出問題最優(yōu)解的算法。當(dāng)問題的規(guī)模較小時(shí)，精確算法能夠在可接受的時(shí)間內(nèi)得到最優(yōu)解；當(dāng)問題的規(guī)模較大時(shí)，精確算法一方面可以提供問題的可行解，另一方面可以為啟發(fā)式算法提供初始解，以便搜索到更好的解。
常用的精確算法有分支定界法、割平面法、動態(tài)規(guī)劃法等。 - 近似算法
近似算法是指用近似方法來解決優(yōu)化問題的算法，通常與 NP-hard 問題相關(guān)，由于無 法有效地在多項(xiàng)式時(shí)間內(nèi)精確地求得最優(yōu)解，所以考慮在多項(xiàng)式時(shí)間內(nèi)求得一個(gè)有質(zhì)量保 證的近似解。
貪婪算法、局部搜索算法、松弛算法、動態(tài)規(guī)劃法等都可用于構(gòu)建近似算法求解。
- 啟發(fā)式算法
啟發(fā)式算法是一種基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，能在可接受的計(jì)算成本內(nèi)盡可能地逼近最優(yōu)解，得到一個(gè)相對優(yōu)解，但無法預(yù)計(jì)所得解與最優(yōu)解的近似程度。
啟發(fā)式算法可分為傳統(tǒng)啟發(fā)式算法和元啟發(fā)式算法，傳統(tǒng)啟發(fā)式算法包括構(gòu)造性方法、局部搜索算法、松弛方法、解空間縮減算法等
- 元啟發(fā)式算法
元啟發(fā)式算法主要指一類通用型的啟發(fā)式算法，它對啟發(fā)式算法進(jìn)行了改進(jìn)，是隨機(jī) 算法與局部搜索算法相結(jié)合的產(chǎn)物。這類算法的優(yōu)化機(jī)理不過分依賴與算法的組織結(jié)構(gòu)信 息，可以廣泛地應(yīng)用到函數(shù)的組合優(yōu)化和函數(shù)計(jì)算中。
元啟發(fā)式算法包括禁忌搜索算法、模擬退火算法、遺傳算法、蟻群算法、粒子群算 法、人工神經(jīng)網(wǎng)絡(luò)等。
強(qiáng)化學(xué)習(xí)解決組合優(yōu)化問題
組合優(yōu)化問題由于多半屬于NP-hard問題，傳統(tǒng)的數(shù)學(xué)優(yōu)化方法目前很難求到精確解。神經(jīng)網(wǎng)絡(luò)是否能幫助組合優(yōu)化問題的求解一直以來都是一個(gè)非常有趣和前沿的話題。
組合優(yōu)化問題大多數(shù)情況下都是涉及到?jīng)Q策順序，即序列的決策問題，例如對于TSP問題就是決定以什么順序訪問每一個(gè)城市，例如對于Job shop問題（加工車間調(diào)度問題）就是決定以什么順序在機(jī)器上加工工件。而深度神經(jīng)網(wǎng)絡(luò)里邊的遞歸神經(jīng)網(wǎng)絡(luò)恰好可以完成從一個(gè)序列到另一個(gè)序列的映射問題，因此可以借用遞歸神經(jīng)網(wǎng)絡(luò)來直接求解組合優(yōu)化問題完全是一種可行的方案。另外一套方案就是采用強(qiáng)化學(xué)習(xí)，強(qiáng)化學(xué)習(xí)天生就是做序列決策用的，那么組合優(yōu)化問題里邊的序列決策問題完全也可以用強(qiáng)化學(xué)習(xí)來直接求解，其難點(diǎn)是怎么定義state, reward。
強(qiáng)化學(xué)習(xí)方法小結(jié)
2015年，O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks使用監(jiān)督學(xué)習(xí)訓(xùn)練了一個(gè)深度神經(jīng)網(wǎng)絡(luò)(DNN)來解決歐幾里德TSP，作者通過實(shí)驗(yàn)證明了神經(jīng)網(wǎng)絡(luò)能夠在具有大動作空間的domains中參數(shù)化競爭策略。文章引入了指針網(wǎng)絡(luò)，這是一種能夠輸出輸入序列的置換的神經(jīng)架構(gòu)。盡管文章看起來十分promising，但使用監(jiān)督學(xué)習(xí)來解決組合問題并不簡單，因獲得一個(gè)訓(xùn)練集意味著我們求得大量組合實(shí)例的最優(yōu)解，這實(shí)在太耗費(fèi)計(jì)算資源了+很多COP足量的訓(xùn)練集太難找了.
專為組合優(yōu)化求解而誕生的神經(jīng)網(wǎng)絡(luò) -- Pointer Network介紹
組合優(yōu)化問題很多時(shí)候就是進(jìn)行序列決策，而Pointer Network就是非常適合求解組合優(yōu)化問題的一種神經(jīng)網(wǎng)絡(luò)。Pointer Network（后面簡稱Ptr-Net）是基于Sequence-to-Sequence網(wǎng)絡(luò)生成的一種新的網(wǎng)絡(luò)架構(gòu)。Ptr-Net與Sequence-to-Sequence類似，都是解決從一個(gè)序列到另一個(gè)序列的映射問題，不同的是Ptr-Net針對的序列問題更加特殊：輸出序列的內(nèi)容與輸入序列的內(nèi)容完全一致，只是序列的順序發(fā)生了改變。這種問題在實(shí)際中常見的應(yīng)用就是組合優(yōu)化問題，因此Ptr-Net首次建立了神經(jīng)網(wǎng)絡(luò)與組合優(yōu)化問題的聯(lián)系。
2016年，I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940給出了NCO框架，并首次實(shí)現(xiàn)了用RL方法求解組合問題。作者采用了Vinyals引入的指針網(wǎng)絡(luò)，并將其用于演員-評論家體系結(jié)構(gòu)來解決TSP問題。實(shí)驗(yàn)證明，在沒有人工干預(yù)的情況下，學(xué)習(xí)有競爭力的heuristics是可能的。不過他們還是應(yīng)用了大量的采樣和搜索技術(shù)來改善神經(jīng)網(wǎng)絡(luò)本身產(chǎn)生的解。
到目前為止，很多工作都有很大的相似之處: 它們都是基于序列到序列模型，這是最初為監(jiān)督學(xué)習(xí)而設(shè)計(jì)的架構(gòu)。在這些模型中，解僅基于與問題的單一交互而被立即解碼。相反，M. Nazari, A. Oroojlooy, L. Snyder, and M. Takác. Reinforcement learning for solving the vehicle routing problem將車輛路徑問題(VRP)視為MDP問題。具體來說，他們構(gòu)建的解是與環(huán)境交互做出一系列決策后的結(jié)果。這種算法可以專注于環(huán)境的演變過程以構(gòu)建最終解，論文中說算法能處理問題的隨機(jī)版本。
