旅行商問(wèn)題^[1] 是優(yōu)化算法的試金石。 可以使用多種方法進(jìn)行求解。比如下面是Will Campbell ?利用遺傳算法求解美國(guó)各州首府旅行商問(wèn)題^[2] 的動(dòng)態(tài)過(guò)程。利用神經(jīng)網(wǎng)絡(luò)中的自組織映射網(wǎng)絡(luò)(SOFM)，連續(xù)Hopfield網(wǎng)絡(luò)也可以進(jìn)行求解。

▲ 使用遺傳算法求解旅行商問(wèn)題

下面是利用自組織特征映射（SOFM）用于求解十個(gè)地點(diǎn)中間的旅行商問(wèn)題的過(guò)程。在SOFM網(wǎng)絡(luò)的競(jìng)爭(zhēng)層采用首尾相連的一維拓?fù)浣Y(jié)構(gòu)，學(xué)習(xí)速率從0.3線性降低到0， 學(xué)習(xí)半徑從2線性減小到0。200步訓(xùn)練過(guò)程網(wǎng)絡(luò)對(duì)應(yīng)的位置的演變過(guò)程如下圖所示：

在上述搜索過(guò)程中，對(duì)于每個(gè)搜索節(jié)點(diǎn)增加了隨機(jī)噪聲和定向游動(dòng)，提高了網(wǎng)絡(luò)搜索的能力。

前面使用SOFM網(wǎng)絡(luò)進(jìn)行優(yōu)化，應(yīng)用的是自組織特征映射網(wǎng)絡(luò)的“保序特性”，也就是網(wǎng)絡(luò)的競(jìng)爭(zhēng)層的神經(jīng)元相互之間的拓?fù)浣Y(jié)構(gòu)與對(duì)應(yīng)訓(xùn)練樣本在數(shù)據(jù)空間中的分布上保持有相似的關(guān)系。

比如下面使用來(lái)自于三角形內(nèi)均勻分布的數(shù)據(jù)點(diǎn)訓(xùn)練一維拓?fù)浣Y(jié)構(gòu)的SOFM，隨著訓(xùn)練過(guò)程的收斂競(jìng)爭(zhēng)網(wǎng)絡(luò)中的神經(jīng)元逐步擴(kuò)展到數(shù)據(jù)所在的三角形。

下面顯示的是二維拓?fù)浣Y(jié)構(gòu)的SOFM網(wǎng)絡(luò)在來(lái)自于 區(qū)間隨機(jī)采樣的數(shù)據(jù)訓(xùn)練下的收斂情況。

下面是一次訓(xùn)練扭曲的分布結(jié)果：

上面的自組織特征映射網(wǎng)絡(luò)是來(lái)自于對(duì)競(jìng)爭(zhēng)算法（WTA：勝者為王）的改進(jìn)。下面顯示的是兩個(gè)節(jié)點(diǎn)的競(jìng)爭(zhēng)網(wǎng)絡(luò)節(jié)點(diǎn)位置（紅點(diǎn)）在五個(gè)訓(xùn)練樣本（藍(lán)點(diǎn)）作用下競(jìng)爭(zhēng)的結(jié)果。

簡(jiǎn)單的使用競(jìng)爭(zhēng)算法，可以完成對(duì)于數(shù)據(jù)內(nèi)部規(guī)律的學(xué)習(xí)。

比如下面是三個(gè)神經(jīng)網(wǎng)絡(luò)初始的位置。

使用下面帶有噪聲的C，I，T字符進(jìn)行訓(xùn)練。三個(gè)神經(jīng)元便可以分別演化到C，I，T的平均結(jié)果。

經(jīng)過(guò)100次競(jìng)爭(zhēng)學(xué)習(xí)之后他們最終演變的形狀。

在競(jìng)爭(zhēng)的結(jié)果上，再增加一層映射，便可以去逼近函數(shù)。下面顯示的是單相對(duì)偶傳播網(wǎng)絡(luò)（CPN）逼近Hermit函數(shù)的演變過(guò)程。

增加競(jìng)爭(zhēng)神經(jīng)元節(jié)點(diǎn)的個(gè)數(shù)，使用雙向CPN可以進(jìn)一步提高逼近函數(shù)的效果。

對(duì)于神經(jīng)網(wǎng)絡(luò)，如果只是依靠競(jìng)爭(zhēng)（無(wú)導(dǎo)師訓(xùn)練）所能夠達(dá)到的精度會(huì)受到數(shù)據(jù)量和分布的影響。對(duì)于只有少數(shù)數(shù)據(jù)量的場(chǎng)景，只有競(jìng)爭(zhēng)往往是無(wú)法達(dá)到很好的效果的，除非是一個(gè)天才。

適當(dāng)引入導(dǎo)師信號(hào)可以在小樣本下提高學(xué)習(xí)的效果。這就是學(xué)習(xí)矢量量化網(wǎng)絡(luò)（LVQ）優(yōu)勢(shì)。下面是一個(gè)極端的例子，可以看到LVQ網(wǎng)絡(luò)對(duì)于小樣本下的學(xué)習(xí)能力是非常強(qiáng)的。

對(duì)于復(fù)雜的非線性映射，最有效的方式就是通過(guò)淺層網(wǎng)絡(luò)的隨機(jī)梯度下降，來(lái)獲得較為可靠的訓(xùn)練結(jié)果。

下面是MATLAB中的Peaks二維函數(shù)。

采集到一些離散的數(shù)據(jù)，對(duì)于有隱層網(wǎng)絡(luò)進(jìn)行訓(xùn)練。如果數(shù)據(jù)采集的足夠多，分布的足夠合理，可以很快獲得其中的映射關(guān)系。

下圖顯示了一個(gè)網(wǎng)絡(luò)在訓(xùn)練過(guò)程中對(duì)應(yīng)的輸入輸出關(guān)系演變過(guò)程。