利用自組織映射解決旅行推銷員問題
作者：Diego Vicente
編譯：Bing
編者按：本文原作者為Diego Vicente，他用自組織映射（SOM）方法對經典的旅行推銷員問題找出了解決方法。論智已獲原作者授權，以下是編譯版本。
旅行推銷員問題是一項有名的計算機視覺挑戰，即在地圖上給定一系列城市和各城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。雖然聽起來很簡單，它是組合優化中的一個NP困難問題。這意味著，城市的數量越多，解決起來困難就越大，而且針對這一問題並沒有通用的解決方法、所以，現在只要能找到任何次優解的方法都已經很滿足了（但大多數情況下我們無法驗證返回的結果是否為最優解）。
為了找出解決方法，我們可以試著在自組織映射技術上進行調整。首先來了解一下這一技術都包含什麼，只有充分理解它，才能將其應用到這一問題上。
對自組織映射的一些見解
1998年，Teuvo Kohonen發表的論文中，對這一技術進行了簡要卻精準的描述。在論文中，他解釋道，自組織映射通常是一個二維的節點網路，靈感來自神經網路。與映射密切相關的是模型的概念，即映射試圖反應真實的情況。該技術的目的是用盡量少的維度表現模型，同時保持節點中相似性之間的關係。
為了捕捉這種相似性，地圖上的節點在空間上的位置越接近，相似性就越高。因此，SOM是圖形可視化、組織數據的好方法。為了獲得這個結構，映射上應用了回歸操作，修改節點的位置以便更新節點。一次從模型中選取一個元素，用於回歸的表達式為：
上述公示表明，將節點n中的距離添加到給定元素中，再乘以獲勝神經元（winner neuron）we的近鄰因素，該節點的位置就被更新。一個元素中的獲勝神經元就是地圖中與相近節點相似度較高的節點，通常用歐幾里得距離測量（儘管可以使用不同的相似度測量）。
另一方面，近鄰節點被定義為獲勝神經元周圍映射的卷積似的核。這樣一來，我們就能更新獲勝神經元和靠近元素的神經元，獲得一個均衡的結果。函數通常呈高斯分布，其他實現也是如此。值得一提的是泡沫鄰域，它更新了獲勝者神經元半徑範圍內的神經元（基於離散克羅內克三角函數），這是最簡單的鄰域函數。
調整技術
用神經網路解決旅行推銷員問題，主要任務就是理解如何修正鄰域函數。如果我們將神經元排列成圓形而不是網格，每個節點只會注意到前面和後面的神經元。也就是說，內在的相似性只能在一個維度上起作用。只需要稍作修改，在鄰域函數的作用下，自組織映射就會像一個彈性圓圈，不斷靠近城市，同時盡量縮小總長度。
雖然這種修改是該技術最重要的部分，但是這樣仍然無法工作，因為該演算法幾乎不會收斂。為了保證演算法的收斂性，我們可以用一個學習速率α來控制演算法的探索和運用。首先要實現高水平的探索，然後才能運用。為實現上述二者，我們必須在鄰域函數和學習速率中添加衰減。學習速率的降低能讓模型周圍的神經元不過度移動。同時，對鄰域函數進行衰減，對模型每個部分局部最小值的利用也就更合理。那麼回歸函數可以表示為：
這裡α是特定時間的學習速率，g是以獲勝神經元為中心、具有領域分散h的高斯函數。衰減函數中分別乘以兩個給定的值γ，分別代表學習速率和鄰近距離。
上述表達式有點像Q-Learning，並且收斂方式也類似。在無監督學習任務中，對參數進行衰減可以用於之前提到過的任務。另外，它和Teuvo Kohonen開發的學習式向量量化（Learning Vector Quantization）技術也很相似。
最後，為了獲取SOM得出的路線圖，只需要將某一城市與其獲勝神經元相連，從任意一點開始，按獲勝神經元的出現順序依次連接城市。如果幾個城市映射到同一個神經元，那是因為SOM因為缺乏與最終距離的相關性或者精度不夠，而沒有考慮到穿過其他這些城市的情況。
安裝並測試SOM
在本次任務中，安裝所述技術的方法可以在Python3中找到。它能夠解析和載入任何建模為TSPLIB文件的2D實例問題，並利用回歸獲取最短路線。選擇這種形式是因為滑鐵盧大學在「全國旅行推銷員問題」的實際情況中提供了這一例子的最優路線，從而能讓我們測試和評估我們的方案。
在較低層級時，包能讓計算矢量化同時性能出色，代碼也更簡潔，所以用來計算。另外，能輕鬆將文件載入到內存中；用於繪製圖形。這些都能在Python發行版Anaconda中使用，或者用輕鬆安裝。
我們將用滑鐵盧大學提供的實例驗證安裝效果，這些實例來自真實國家，評估策略包括運行中的幾個問題和學習指標：
評估過程中所用的參數：
這些參數在以下情況中使用：
如果某些變數衰減到有效閾值以下，則模型也會停止工作。運行該演算法的同一方式就是測試，儘管每一實例可能有更細的參數。下表為每個評估結果，評估結果為運行5次的平均值。
結果不錯，我們能在400秒內得到次優方案，結果總體來說可以接受。例如在烏拉圭的734各城市裡，模型最快能在25秒內找到僅比最優路線長7.5%的解決方案。
結語
雖然還未進行徹底的測試，但這一項目非常有趣，結果也表現得不錯。最後附上GitHub和原文地址，可在其中找到代碼。
原文地址：diego.codes/post/som-tsp/
GitHub地址：github.com/DiegoVicen/som-tsp
TAG:全球大搜羅 |