159
旅行商問題[1] 是優(yōu)化算法的試金石。 可以使用多種方法進行求解。比如下面是 Will Campbell ?利用遺傳算法求解美國各州首府旅行商問題[2] 的動態(tài)過程。利用神經(jīng)網(wǎng)絡(luò)中的自組織映射網(wǎng)絡(luò)(SOFM)，連續(xù) Hopfield 網(wǎng)絡(luò)也可以進行求解。
▲ 使用遺傳算法求解旅行商問題
?
下面是利用自組織特征映射（SOFM）用于求解十個地點中間的旅行商問題的過程。在 SOFM 網(wǎng)絡(luò)的競爭層采用首尾相連的一維拓撲結(jié)構(gòu)，學(xué)習(xí)速率從 0.3 線性降低到 0， 學(xué)習(xí)半徑從 2 線性減小到 0。200 步訓(xùn)練過程網(wǎng)絡(luò)對應(yīng)的位置的演變過程如下圖所示：
▲ 循環(huán)和增加噪聲兩種效果下的搜索結(jié)果
在上述搜索過程中，對于每個搜索節(jié)點增加了隨機噪聲和定向游動，提高了網(wǎng)絡(luò)搜索的能力。
前面使用 SOFM 網(wǎng)絡(luò)進行優(yōu)化，應(yīng)用的是自組織特征映射網(wǎng)絡(luò)的“保序特性”，也就是網(wǎng)絡(luò)的競爭層的神經(jīng)元相互之間的拓撲結(jié)構(gòu)與對應(yīng)訓(xùn)練樣本在數(shù)據(jù)空間中的分布上保持有相似的關(guān)系。
比如下面使用來自于三角形內(nèi)均勻分布的數(shù)據(jù)點訓(xùn)練一維拓撲結(jié)構(gòu)的 SOFM，隨著訓(xùn)練過程的收斂競爭網(wǎng)絡(luò)中的神經(jīng)元逐步擴展到數(shù)據(jù)所在的三角形。
?
下面顯示的是二維拓撲結(jié)構(gòu)的 SOFM 網(wǎng)絡(luò)在來自于區(qū)間隨機采樣的數(shù)據(jù)訓(xùn)練下的收斂情況。
▲ 2D 拓撲結(jié)構(gòu)的 SOFM 的訓(xùn)練結(jié)果
?
下面是一次訓(xùn)練扭曲的分布結(jié)果：
▲ 發(fā)生扭曲的訓(xùn)練過程
?
上面的自組織特征映射網(wǎng)絡(luò)是來自于對競爭算法（WTA：勝者為王）的改進。下面顯示的是兩個節(jié)點的競爭網(wǎng)絡(luò)節(jié)點位置（紅點）在五個訓(xùn)練樣本（藍點）作用下競爭的結(jié)果。
▲ 變學(xué)習(xí)速率的訓(xùn)練過程
?
簡單的使用競爭算法，可以完成對于數(shù)據(jù)內(nèi)部規(guī)律的學(xué)習(xí)。
比如下面是三個神經(jīng)網(wǎng)絡(luò)初始的位置。
▲ 三個神經(jīng)元初始化后的情況
?
使用下面帶有噪聲的 C，I，T 字符進行訓(xùn)練。三個神經(jīng)元便可以分別演化到 C，I，T 的平均結(jié)果。
▲ 添加噪聲后的訓(xùn)練樣本
?
經(jīng)過 100 次競爭學(xué)習(xí)之后他們最終演變的形狀。
▲ 競爭演變過程
?
在競爭的結(jié)果上，再增加一層映射，便可以去逼近函數(shù)。下面顯示的是單相對偶傳播網(wǎng)絡(luò)（CPN）逼近 Hermit 函數(shù)的演變過程。
?
增加競爭神經(jīng)元節(jié)點的個數(shù)，使用雙向 CPN 可以進一步提高逼近函數(shù)的效果。
▲ 雙向 CPN 函數(shù)逼近結(jié)果
?
對于神經(jīng)網(wǎng)絡(luò)，如果只是依靠競爭（無導(dǎo)師訓(xùn)練）所能夠達到的精度會受到數(shù)據(jù)量和分布的影響。對于只有少數(shù)數(shù)據(jù)量的場景，只有競爭往往是無法達到很好的效果的，除非是一個天才。
適當引入導(dǎo)師信號可以在小樣本下提高學(xué)習(xí)的效果。這就是學(xué)習(xí)矢量量化網(wǎng)絡(luò)（LVQ）優(yōu)勢。下面是一個極端的例子，可以看到 LVQ 網(wǎng)絡(luò)對于小樣本下的學(xué)習(xí)能力是非常強的。
▲ LVQ 訓(xùn)練過程
?
▲ LVQ 訓(xùn)練中隱層節(jié)點演變過程
?
對于復(fù)雜的非線性映射，最有效的方式就是通過淺層網(wǎng)絡(luò)的隨機梯度下降，來獲得較為可靠的訓(xùn)練結(jié)果。
下面是 MATLAB 中的 Peaks 二維函數(shù)。
▲ peaks 函數(shù)圖像
?
采集到一些離散的數(shù)據(jù)，對于有隱層網(wǎng)絡(luò)進行訓(xùn)練。如果數(shù)據(jù)采集的足夠多，分布的足夠合理，可以很快獲得其中的映射關(guān)系。
▲ 采集到的數(shù)據(jù)樣本
?
下圖顯示了一個網(wǎng)絡(luò)在訓(xùn)練過程中對應(yīng)的輸入輸出關(guān)系演變過程。
▲ 神經(jīng)網(wǎng)絡(luò)輸入輸出對應(yīng)函數(shù)曲面演變過程
