我們有一個(gè)必須在n個(gè)城市之間旅行的推銷員。他不在乎什么順序。他最先或最后訪問(wèn)的城市除外。他唯一關(guān)心的是他會(huì)去拜訪每一個(gè)人，每個(gè)城市只有一次，最后一站是他得家。

每個(gè)城市都是一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)通過(guò)一條邊與其他封閉節(jié)點(diǎn)相連(可以將其想象成公路、飛機(jī)、火車、汽車等)

每個(gè)連接都有一個(gè)或多個(gè)權(quán)值與之相關(guān)，我們稱之為成本。

成本描述了沿著該連接旅行的困難程度，如機(jī)票成本、汽車所需的汽油量等。

他的首要任務(wù)是盡可能降低成本和旅行距離。

對(duì)于那些學(xué)過(guò)或熟悉圖論的人，希望你們還記得無(wú)向加權(quán)圖。

城市是頂點(diǎn)，路徑是邊，路徑距離是邊的權(quán)值。本質(zhì)上，我們有一個(gè)最小化的問(wèn)題，即在訪問(wèn)了其他每個(gè)頂點(diǎn)一次之后，從一個(gè)特定的頂點(diǎn)開始和結(jié)束。實(shí)際上，當(dāng)我們完成的時(shí)候，可能會(huì)得到一個(gè)完整的圖，其中每一對(duì)頂點(diǎn)都由一條邊連接起來(lái)。

接下來(lái)，我們必須討論不對(duì)稱和對(duì)稱的問(wèn)題，因?yàn)檫@個(gè)問(wèn)題最終可能是其中之一。到底是什么意思?我們有一個(gè)非對(duì)稱旅行推銷員問(wèn)題或者一個(gè)對(duì)稱旅行推銷員問(wèn)題。這完全取決于兩座城市之間的距離。如果每個(gè)方向上的距離相等，我們有一個(gè)對(duì)稱的旅行推銷員問(wèn)題，對(duì)稱性幫助我們得到可能的解。如果兩個(gè)方向上的路徑不存在，或者距離不同，我們就有一個(gè)有向圖。下圖顯示了前面的描述: 

旅行推銷員問(wèn)題可以是對(duì)稱的，也可以是非對(duì)稱的。讓我們從對(duì)將要發(fā)生的事情從最簡(jiǎn)描述開始。

在生物界，當(dāng)我們想要?jiǎng)?chuàng)建一個(gè)新的基因型時(shí)，我們會(huì)從父a那里取一點(diǎn)，從父b那里取一點(diǎn)。這叫做交叉突變。在這之后，這些基因型就會(huì)受到輕微的干擾或改變。這被稱為突變。這就是遺傳物質(zhì)產(chǎn)生的過(guò)程。

接下來(lái)，我們刪除原始代，代之以新的代，并測(cè)試每個(gè)基因型。更新的基因型，作為其先前組成部分的更好部分，現(xiàn)在將向更高的適應(yīng)度傾斜;平均而言，這一代人的得分應(yīng)該高于上一代人。

這一過(guò)程將持續(xù)許多代，隨著時(shí)間的推移，人口的平均適應(yīng)度將不斷進(jìn)化和提高。在現(xiàn)實(shí)生活中，這并不總是有效的，但一般來(lái)說(shuō)，它是有效的。

在后面會(huì)有一個(gè)遺傳算法編程的講解，以便讓我們深入研究我們的應(yīng)用程序。

下面是我們的示例應(yīng)用程序。它是基于Accord.NET框架的。在定義了需要訪問(wèn)的房屋數(shù)量之后，只需單擊生成按鈕:

在我們的測(cè)試應(yīng)用程序中，我們可以非常容易地更改我們想要訪問(wèn)的房屋的數(shù)量，如高亮顯示的區(qū)域所示。

我們可以得到一個(gè)非常簡(jiǎn)單的空間問(wèn)題或者更復(fù)雜的空間問(wèn)題。這是一個(gè)非常簡(jiǎn)單的空間問(wèn)題的例子:

這是一個(gè)更復(fù)雜的空間問(wèn)題的例子：

最后，設(shè)置我們希望算法使用的迭代總數(shù)。點(diǎn)擊計(jì)算路線按鈕，假設(shè)一切順利，我們的地圖看起來(lái)應(yīng)該像這樣:

讓我們看看當(dāng)我們選擇我們想要的城市數(shù)量，然后點(diǎn)擊生成按鈕，會(huì)發(fā)生什么:

   /// <summary>
        /// 重新生成地圖
        /// </summary>
        private void GenerateMap()
        {
            Random rand = new Random((int)DateTime.Now.Ticks);

            // 創(chuàng)建坐標(biāo)數(shù)組
            map = new double[citiesCount, 2];

            for (int i = 0; i < citiesCount; i++)
            {
                map[i, 0] = rand.Next(1001);
                map[i, 1] = rand.Next(1001);
            }

            //設(shè)置地圖
            chart.UpdateDataSeries("cities", map);
            //刪除路徑
            chart.UpdateDataSeries("path", null);
        }

我們要做的第一件事就是初始化隨機(jī)數(shù)生成器并對(duì)其進(jìn)行種子化。接下來(lái)，我們得到用戶指定的城市總數(shù)，然后從中創(chuàng)建一個(gè)新數(shù)組。最后，我們繪制每個(gè)點(diǎn)并更新地圖。這張地圖是來(lái)自Accord.NET的圖表控件，它將為我們提供大量可視化繪圖。完成這些之后，我們就可以計(jì)算路徑并解決問(wèn)題了。

接下來(lái)，讓我們看看我們的主要搜索解決方案是什么樣的:

// 創(chuàng)建網(wǎng)絡(luò)
            DistanceNetwork network = new DistanceNetwork(2, neurons);

            // 設(shè)置隨機(jī)發(fā)生器范圍
            foreach (var neuron in network.Layers.SelectMany(layer => layer?.Neurons).Where(neuron => neuron != null))
            {
                neuron.RandGenerator = new UniformContinuousDistribution(new Range(0, 1000));
            }


            // 創(chuàng)建學(xué)習(xí)算法
            ElasticNetworkLearning trainer = new ElasticNetworkLearning(network);

            double fixedLearningRate = learningRate / 20;
            double driftingLearningRate = fixedLearningRate * 19;

            double[,] path = new double[neurons + 1, 2];
            double[] input = new double[2];
            int i = 0;

            while (!needToStop)
            {
                // 更新學(xué)習(xí)速度和半徑
                trainer.LearningRate = driftingLearningRate * (iterations - i) / iterations + fixedLearningRate;
                trainer.LearningRadius = learningRadius * (iterations - i) / iterations;

                // 設(shè)置網(wǎng)絡(luò)輸入
                int currentCity = rand.Next(citiesCount);
                input[0] = map[currentCity, 0];
                input[1] = map[currentCity, 1];

                // 運(yùn)行一個(gè)訓(xùn)練迭代
                trainer.Run(input);

                // 顯示當(dāng)前路徑
                for (int j = 0; j < neurons; j++)
                {
                    path[j, 0] = network.Layers[0].Neurons[j].Weights[0];
                    path[j, 1] = network.Layers[0].Neurons[j].Weights[1];
                }
                path[neurons, 0] = network.Layers[0].Neurons[0].Weights[0];
                path[neurons, 1] = network.Layers[0].Neurons[0].Weights[1];

                chart.UpdateDataSeries("path", path);

                i++;

                SetText(currentIterationBox, i.ToString());

                if (i >= iterations)
                    break;
            }

現(xiàn)在我們已經(jīng)解決了問(wèn)題，讓我們看看是否可以應(yīng)用我們?cè)谇懊骊P(guān)于自組織映射(SOM)一章中學(xué)到的知識(shí)，從不同的角度來(lái)處理這個(gè)問(wèn)題。

我們將使用一種叫做彈性網(wǎng)絡(luò)訓(xùn)練的技術(shù)來(lái)解決我們遇到的問(wèn)題，這是一種很好的無(wú)監(jiān)督的方法。

首先簡(jiǎn)單介紹一下什么是彈性映射。

彈性映射為創(chuàng)建非線性降維提供了一種工具。它們是數(shù)據(jù)空間中的彈性彈簧系統(tǒng)，近似于低維流形。利用這種能力，我們可以從完全無(wú)結(jié)構(gòu)聚類(無(wú)彈性)到更接近線性主成分分析流形（高彎曲/低拉伸）的彈簧。

在使用我們的示例應(yīng)用程序時(shí)，您將看到這些線并不一定像在以前的解決方案中那樣僵硬。在許多情況下，它們甚至不可能進(jìn)入我們所訪問(wèn)的城市的中心(這條線從中心生成)，而是只接近城市邊界的邊緣，如前面的示例所示。

接下來(lái)，介紹下神經(jīng)元。這次我們將有更多的控制，通過(guò)指定我們的學(xué)習(xí)速率和半徑。與前面的示例一樣，我們將能夠指定銷售人員今天必須訪問(wèn)的城市總數(shù)。

首先，我們將訪問(wèn)50個(gè)城市，使用0.3的學(xué)習(xí)率和0.75的半徑。最后，我們將運(yùn)行50,000次迭代(不用擔(dān)心，這很快的)。我們的輸出是這樣的:

現(xiàn)在，如果我們改變半徑為不同的值，比如0.25，會(huì)發(fā)生什么?注意我們?cè)谝恍┏鞘兄g的角度變得更加明顯:

接下來(lái)，我們將學(xué)習(xí)率從0.3改為0.75:

盡管得到路線最終看起來(lái)非常相似，但有一個(gè)重要的區(qū)別。在前面的示例中，直到所有迭代完成，才繪制銷售人員的路由路徑。

我們所做的第一件事就是創(chuàng)建一個(gè)DistanceNetwork對(duì)象。這個(gè)對(duì)象只包含一個(gè)DistanceLayer，它是一個(gè)距離神經(jīng)元的單層。距離神經(jīng)元將其輸出計(jì)算為其權(quán)值與輸入值之間的距離，即權(quán)值與輸入值之間的絕對(duì)差值之和。所有這些組成了SOM，更重要的是，我們的彈性網(wǎng)絡(luò)。

接下來(lái)，我們必須用一些隨機(jī)權(quán)值來(lái)初始化我們的網(wǎng)絡(luò)。我們將為每個(gè)神經(jīng)元?jiǎng)?chuàng)建一個(gè)均勻連續(xù)的分布。均勻連續(xù)分布，或稱矩形分布，是一種對(duì)稱的概率分布，對(duì)于族中的每一個(gè)成員，在分布的支撐點(diǎn)上相同長(zhǎng)度的所有區(qū)間具有相同的概率。你通常會(huì)看到這寫成U(a, b)參數(shù)a和b分別是最小值和最大值。

// 設(shè)置隨機(jī)發(fā)生器范圍
            foreach (var neuron in network.Layers.SelectMany(layer => layer?.Neurons).Where(neuron => neuron != null))
            {
                neuron.RandGenerator = new UniformContinuousDistribution(new Range(0, 1000));
            }

接下來(lái)，我們創(chuàng)建彈性學(xué)習(xí)對(duì)象，它允許我們訓(xùn)練我們的距離網(wǎng)絡(luò):

// 創(chuàng)建學(xué)習(xí)算法
            ElasticNetworkLearning trainer = new ElasticNetworkLearning(network);

下面是ElasticNetworkLearning構(gòu)造函數(shù)內(nèi)部的樣子:

現(xiàn)在我們計(jì)算學(xué)習(xí)速率和半徑:

double fixedLearningRate = learningRate / 20;
            double driftingLearningRate = fixedLearningRate * 19;

最后，進(jìn)入我們的主循環(huán):

while (!needToStop)
            {
                // 更新學(xué)習(xí)速度和半徑
                trainer.LearningRate = driftingLearningRate * (iterations - i) / iterations + fixedLearningRate;
                trainer.LearningRadius = learningRadius * (iterations - i) / iterations;

                // 設(shè)置網(wǎng)絡(luò)輸入
                int currentCity = rand.Next(citiesCount);
                input[0] = map[currentCity, 0];
                input[1] = map[currentCity, 1];

                // 運(yùn)行一個(gè)訓(xùn)練迭代
                trainer.Run(input);

                // 顯示當(dāng)前路徑
                for (int j = 0; j < neurons; j++)
                {
                    path[j, 0] = network.Layers[0].Neurons[j].Weights[0];
                    path[j, 1] = network.Layers[0].Neurons[j].Weights[1];
                }
                path[neurons, 0] = network.Layers[0].Neurons[0].Weights[0];
                path[neurons, 1] = network.Layers[0].Neurons[0].Weights[1];

                chart.UpdateDataSeries("path", path);

                i++;

                SetText(currentIterationBox, i.ToString());

                if (i >= iterations)
                    break;
            }

在前面的循環(huán)中，訓(xùn)練器每次循環(huán)增量運(yùn)行一個(gè)epoch(迭代)。這是trainer.Run函數(shù)的樣子，我們可以看到發(fā)生了什么?；旧?，該方法找到獲勝的神經(jīng)元(權(quán)重值最接近指定輸入向量的神經(jīng)元)。然后更新它的權(quán)重以及相鄰神經(jīng)元的權(quán)重:

這個(gè)方法的兩個(gè)主要功能是計(jì)算網(wǎng)絡(luò)和獲得獲勝者(突出顯示的項(xiàng)目)。

現(xiàn)在，簡(jiǎn)要介紹一下我們可以在屏幕上輸入的參數(shù)。

學(xué)習(xí)速率

學(xué)習(xí)速率是決定學(xué)習(xí)速度的一個(gè)參數(shù)。更正式地說(shuō)，它決定了我們根據(jù)損失梯度調(diào)整網(wǎng)絡(luò)權(quán)重的程度。如果太低，我們沿著斜坡向下的速度就會(huì)變慢。即使我們希望有一個(gè)較低的學(xué)習(xí)率，這可能意味著我們將需要很長(zhǎng)時(shí)間來(lái)達(dá)到趨同。學(xué)習(xí)速率也會(huì)影響我們的模型收斂到最小值的速度。

在處理神經(jīng)元時(shí)，它決定了有權(quán)重用于訓(xùn)練的神經(jīng)元的獲取時(shí)間(對(duì)新體驗(yàn)做出反應(yīng)所需的時(shí)間)。

學(xué)習(xí)半徑

學(xué)習(xí)半徑?jīng)Q定了獲勝神經(jīng)元周圍要更新的神經(jīng)元數(shù)量。在學(xué)習(xí)過(guò)程中，半徑圓內(nèi)的任何神經(jīng)元都會(huì)被更新。神經(jīng)元越靠近，發(fā)生的更新就越多。距離越遠(yuǎn)，數(shù)量越少。

總結(jié)

       在這一章中，我們學(xué)習(xí)了神經(jīng)元，還學(xué)習(xí)了著名的旅行推銷員問(wèn)題，它是什么，以及我們?nèi)绾斡秒娔X解決它。這個(gè)小例子在現(xiàn)實(shí)世界中有著廣泛的應(yīng)用。

       在下一章中，我們將回答我們所有開發(fā)人員都面臨的問(wèn)題:我應(yīng)該接受這份工作嗎?