錦標賽選擇演算法

『壹』 遺傳演算法中的錦標賽選擇演算法的思想是什麼

我理解的是，在50個人中，隨機選擇兩組人，每組10個人，對於每組的10個人按適應度進行排列，選擇兩組中適應度最好的兩個個體作為母代進行兩兩交叉；
然後再從剩下來的48個人中，隨機選擇兩組人，每組10個人，對於每組的10個人按適應度進行排列，選擇兩組中適應度最好的兩個個體作為母代進行兩兩交叉；
依此類推，知道你選出的母代個數滿足你的要求，這里母代個數肯定是少於50的。

『貳』 關於自適應遺傳演算法的交叉操作

不是隨機選擇的，是有規律的選，一般是等間隔選擇，例如兩個相鄰的個體。

如圖紅色是一種選擇方式：1&2, 3&4, 5&6, 7&8, 9&10

藍色也是一種選擇方式：1&6, 2&7, 3&8, 4&9, 5&10

當然，也要盡量避免相同個體交叉。

『叄』 計算機經典演算法——錦標賽排序演算法

關鍵詞 ：二叉樹
生活中的淘汰錦標賽 ：在單淘汰的錦標賽中，選手們兩兩比賽，勝者晉級，敗者被淘汰。比如世界乒乓球錦標賽或者大滿貫網球賽就是這么進行的。
這樣一來，就可以把比賽的賽程和結果對應成一個二叉樹。在樹中每一個選手是二叉樹中的一個葉子結點，每一場比賽就相當於兩個數字在比大小，數字大的選手獲勝進入下一輪，成為樹幹上的根。所以，進入到某一輪比賽的選手，其實都是某個子數乾的根結點。最後的冠軍就是整個二叉樹的根結點。這種賽制的合理性需要一個假設：A>B, B>C --> 必然有A>C（輸贏的傳遞性）

工程中，要比較兩個數字的大小
第一步：把所有的數字放到二叉樹的葉子節點，然後按照錦標賽單淘汰的方式，兩兩比較選出最大
第二步：對於第二大的，從所有被最大的數字淘汰的數字中選擇，以此類推選擇對於第三、第四大的數字

假定有25名短跑選手比賽競爭金銀銅牌，賽場上有5條賽道，因此一次可以有5個人同時比賽。比賽不及時，只看相應的名次。假如選手的發揮是穩定的，也就是說如果約翰比張三跑的快，張三比凱利跑的快，那麼約翰一定比凱利跑得快。最少需要幾組比賽才能決出前3名？

第一步，將25名選手分成5組，每組5人。讓每個組分別比賽，排出各組的名次來，假設他們的名字就是他們在小組中的編號。

第二步，讓各組的第一名，也就是A1、B1、C1、D1、E1再比一次。假設A1在這次比賽中獲勝，這樣我們就知道了第一名。

第四步，如上圖通過8次（5 +1 + 1 +1）選出的5人進行第三名的比賽，前3全部產生

更好的答案：
前6次比賽都是必須的，最佳答案的前2步和上述方案中的前2步是相同的。在第6組比賽（即5個第一名的比賽）結束之後，最後的2名已經沒有資格角逐前3名了。

不妨假設那一次比賽從最快到最慢的結果是A1、B1、C1、D1、E1，在D1和E1之前已經有3名選手了，他們肯定不是前3名。
誰還會是第二名的候選呢？根據錦標賽排序的原則，直接輸給第一名的人，也就是A2，以及最後附加賽輸給他的B1，僅此兩人而已。
誰會是第三名的候選呢？和A1在某一組比賽的第三名，他們是A3、C1，或者輸給第二名候選人B1的人，即B2。

因此，第二、第三名的候選人一共只有5個， A2、A3、B1、B2和C1，剛好湊一組。這樣加上前6次，只需要賽7組，這是最佳方法。

註：來自吳軍老師得到課程

『肆』 技能閃充--錦標賽排序法

第一步：把所有的數字放到二叉樹的葉子結點，然後按照錦標賽單淘汰的方式，兩兩比較選出最大的。
第二步：對於第二大的，從所有被最大的數字淘汰的數字中選擇。比如在某次比賽中被RNG淘汰的是FW，KT等戰隊，那麼這些戰隊在進行單淘汰，選亞軍。對於第三第四大的數字，可以以此類推。

按照這種方式將所有的數字排序，演算法的復雜度，或者說量級是N乘以LogN，和快排差不多。那麼為什麼不直接使用快速排序，而要發明出這么一種不太容易理解的演算法呢？因為在特定的場合下他更快速。比如說，如果我們只需要選出第一名，這種演算法的復雜度只有N，不是N乘以LogN，如果要選出第二名，則額外加上LogN次計算就可以了，對第三名也是如此。也就是說，這種方法在從N個選手中選出K個選手的事情特別快。

有了上述演算法，我們講解下高盛和Google的面試題了，當然任何演算法用於實際的問題，都需要變通一下。

第一步：25名選手分成五組，為了便於說明我們把25人根據所在的組進行編號，A1-A5在A組，B1-B5在B組...最後E1-E5在E組。
然後讓各組分別比賽，排除名次。不是一般性，我們假設他們的名次就是他們在小組中的編號，即A組的名次是A1、A2、A3、A4、A5，B組和其它組的名次也是類似(如下圖)

第二步：讓各組的第一名，也就是A1、B1、C1、D1、E1再比一次，上圖中是第一排紅色的，這樣就能決出第一名。由於A1是第一名，A2可能也很厲害，只是運氣不好，小組賽遇到了A1，當A1已經獲得冠軍了，他就應該作為亞軍的候選。接下來就是第三步。
A2和另外四個組的第一名競爭亞軍。如果這一次A2贏了，他顯然是亞軍，就由A3遞進參加爭奪第三名的比賽。我在下圖中用紅色圈定了這種情況下參加第八次比賽的五位選手。如果A2沒有贏，另四組的某個第一名贏了，哪個贏的人是亞軍，就由那個組下一位選手遞進，角逐第三名。

第四步，如上圖選出五個人進行第三名比賽，致辭，前三名全部產生。但是這個答案並不完美。最好的答案是什麼呢？
其實前六次比賽是必須的，但是上述方案中有一個信息忽略了，就是第六組比賽之後（即五個第一名的比賽）結束之後，最後的兩名已經沒有資格角逐前三名了。我們假設那一次比賽從最快到最慢的結果是A1、B1、C1、D1、E1。在D1和E1之前已經有三名選手了，他們肯定不是前三名。

那麼誰會是第二名的候選人呢？根據錦標賽的排序原則，直接輸給第一名的人也就是A組的A2，以及最後附加賽輸給他的B1，僅此兩個人而已。接下來我們要問，除了A2和B1，誰還會是第三名的候選呢？和A1在某一組比賽的第三名，他們是A3、C1，或者輸給第二名候選人B1的人哪個人，即B2.
因此，第二、三名的候選人一共只有五個，即A2、A3、C1，或者輸給第二名候選人B1的那個即B2。
因此，第二、三名的候選人一共只有五個，即A2、A3、B1、B2、C1（下圖中紅色的選手），剛好湊一組。第七次，這五個人再跑一把即可，這樣只需要七次，最佳方法。

『伍』 遺傳演算法的專業術語誰給翻譯一下

這是遺傳演算法的各種選擇方法，按順序分別為：精英選擇法、適應度比例選擇法、輪盤賭選擇法、定標選擇法、錦標賽選擇法、排序選擇法、多世代選擇法、穩態選擇法、層次選擇法。其中精英選擇法、適應度比例選擇法、輪盤賭選擇法、錦標賽選擇法、排序選擇法是比較常見的選擇方法。

『陸』 遺傳演算法--GA

        遺傳演算法（GA）屬於 人工智慧啟發式演算法 ，啟發式演算法的目標就是 尋找原始問題的最優解 ，該演算法的定義為

         人類通過直觀常識和生活經驗，設計出一種以搜索最優解為目的，通過模擬大自然規律的演算法，該演算法在可以在接受的花銷（計算時間和存儲空間）范圍內找到問題實例的一個可行解，且該可行解和真實最優解的誤差一般不可以被估計

        當下主要有的啟發式演算法包括 遺傳演算法、退火法，蟻群演算法、人工神經網路等 ，這篇文章主要介紹遺傳演算法

        遺傳演算法的基本原理是模擬達爾文進化論 "物競天擇，適者生存" 的自然法則，其核心思想為

（1）將原始問題的參數，抽象為基因編碼

（2）將原始問題的可行解，抽象為基因排列的染色體組合

（3）將原始問題的解集規模，抽象為一定數量染色體組成的種群

（4）尋找可行解的過程，抽象為種群的進化過程（染色體選擇、交叉、變異等）

（5）比較可行解的優劣，抽象為量化比較不同種群對當前環境的適應程度

（6）逼近最優解的過程，抽象為淘汰適應度差的種群，保留適應度高的種群進行下一次進化

（7）問題的最優解，抽象為經過多次進化後，最終生存下來的精英種群

        理論上，通過有限次種群進化，生存下來的種群都是 精英染色體 ，是最適合當前環境條件的種群，也就可以無限逼近原始問題的最優解

相關生物學術語：

    為了大家更好了解遺傳演算法，在此之前先簡單介紹一下相關生物學術語，大家了解一下即可。

基因型(genotype)：性狀染色體的內部表現；

表現型(phenotype)：染色體決定的性狀的外部表現，或者說，根據基因型形成的個體的外部表現；

進化(evolution)：種群逐漸適應生存環境，品質不斷得到改良。生物的進化是以種群的形式進行的。

適應度(fitness)：度量某個物種對於生存環境的適應程度。

選擇(selection)：以一定的概率從種群中選擇若干個個體。一般，選擇過程是一種基於適應度的優勝劣汰的過程。

復制(reproction)：細胞分裂時，遺傳物質DNA通過復制而轉移到新產生的細胞中，新細胞就繼承了舊細胞的基因。

交叉(crossover)：兩個染色體的某一相同位置處DNA被切斷，前後兩串分別交叉組合形成兩個新的染色體。也稱基因重組或雜交；

變異(mutation)：復制時可能（很小的概率）產生某些復制差錯，變異產生新的染色體，表現出新的性狀。

編碼(coding)：DNA中遺傳信息在一個長鏈上按一定的模式排列。遺傳編碼可看作從表現型到基因型的映射。

解碼(decoding)：基因型到表現型的映射。

個體（indivial）：指染色體帶有特徵的實體；

種群（population）：個體的集合，該集合內個體數稱為種群

大體實現過程

遺傳演算法中每一條染色體，對應著遺傳演算法的一個解決方案，一般我們用適應性函數（fitness function）來衡量這個解決方案的優劣。所以從一個基因組到其解的適應度形成一個映射。 遺傳演算法的實現過程實際上就像自然界的進化過程那樣。

基本遺傳演算法概述

    1.[開始]生成n個染色體的隨機群體（適合該問題的解決方案）

    2.[適應度]評估群體中每個染色體x的適應度f（x）

    3.[新種群]通過重復以下來創建新種群直到新種群完成的步驟

        3.1 [選擇]根據種群的適合度選擇兩個親本染色體（更好的適應性，更大的選擇機會）

        3.2 [交叉]以交叉概率跨越父母形成新的後代（兒童） ）。如果沒有進行交叉，後代就是父母的確切副本。

        3.3 [突變]突變概率突變每個基因座（染色體中的位置）的新後代。

    4.[接受]在新種群中放置新後代[替換]使用新生成的種群進一步運行演算法

    5.[測試]如果滿足結束條件，則停止並返回當前種群中的最佳解

    6。[循環]轉到步驟2

影響GA的因素

    從遺傳演算法概述可以看出，交叉和變異是遺傳演算法中最重要的部分。性能主要受這兩個因素的影響。在我們解釋有關交叉和變異的更多信息之前，我們將給出一些有關染色體的信息。

染色體編碼

染色體應該以某種方式包含它所代表的解決方案的信息。最常用的編碼方式是二進制字元串。然後染色體看起來像這樣：

每個染色體由二進制字元串表示。字元串中的每個位都可以表示解決方案的一些特徵。另一種可能性是整個字元串可以表示一個數字 - 這已在基本的GA小程序中使用。當然，還有許多其他的編碼方式。編碼主要取決於解決的問題。例如，可以直接編碼整數或實數，有時對某些排列等進行編碼很有用。

染色體交叉

在我們確定了將使用的編碼之後，我們可以繼續進行交叉操作。 Crossover對來自親本染色體的選定基因進行操作並產生新的後代。最簡單的方法是隨機選擇一些交叉點，並在此點之前從第一個父項復制所有內容，然後在交叉點之後復制另一個父交叉點之後的所有內容。交叉可以說明如下:( |是交叉點）：

還有其他方法可以進行交叉，例如我們可以選擇更多的交叉點。交叉可能非常復雜，主要取決於染色體的編碼。針對特定問題進行的特定交叉可以改善遺傳演算法的性能。

4.染色體突變

在執行交叉之後，發生突變。突變旨在防止群體中的所有解決方案落入解決問題的局部最優中。突變操作隨機改變由交叉引起的後代。在二進制編碼的情況下，我們可以將一些隨機選擇的位從1切換到0或從0切換到1.突變可以如下所示：

突變（以及交叉）技術主要取決於染色體的編碼。例如，當我們編碼排列時，可以將突變作為兩個基因的交換來進行。

GA的參數

    1.交叉和突變概率

    GA有兩個基本參數 - 交叉概率和變異概率。

     交叉概率 ：交叉的頻率。如果沒有交叉，後代就是父母的精確副本。如果存在交叉，則後代由父母染色體的部分組成。如果交叉概率為100％，那麼所有後代都是由交叉產生的。如果它是0％，那麼全新一代都是從舊種群的染色體的精確拷貝製成的（但這並不意味著新一代是相同的！）。交叉是希望新染色體將包含舊染色體的良好部分，因此新染色體將更好。但是，將舊人口的一部分留給下一代是好的。

     突變概率 ：染色體部分突變的頻率。如果沒有突變，則在交叉（或直接復制）後立即生成後代而不進行任何更改。如果進行突變，則改變染色體的一個或多個部分。如果突變概率為100％，則整個染色體發生變化，如果是0％，則沒有變化。突變通常會阻止GA陷入局部極端。突變不應該經常發生，因為GA實際上會改變為隨機搜索。

    2.其他參數

     種群規模 ：種群中有多少染色體（一代）。如果染色體太少，GA幾乎沒有可能進行交叉，只探索了一小部分搜索空間。另一方面，如果染色體太多，GA會減慢。研究表明，經過一定的限制（主要取決於編碼和問題），使用非常大的種群是沒有用的，因為它不能比中等規模的種群更快地解決問題。

     3      選擇

正如您從GA概述中已經知道的那樣，從群體中選擇染色體作為交叉的父母。問題是如何選擇這些染色體。根據達爾文的進化論，最好的進化能夠創造出新的後代。選擇最佳染色體的方法有很多種。例如輪盤賭選擇，Boltzman選擇，錦標賽選擇，等級選擇，穩態選擇和其他一些選擇。

1.輪盤賭選擇

父母根據他們的健康狀況選擇。染色體越好，它們被選擇的機會就越多。想像一下輪盤賭輪，人口中的所有染色體都放在那裡。輪盤中截面的大小與每條染色體的適應度函數的值成比例 - 值越大，截面越大。有關示例，請參見下圖。

輪盤賭中放入一塊大理石，並選擇停止的染色體。顯然，具有較大適應值的染色體將被選擇更多次。

該過程可以通過以下演算法來描述。

[Sum]計算總體中所有染色體擬合度的總和 - 總和S.

[Select]從區間（0，S）-r生成隨機數。

[循環]遍歷總體並從0 - 總和中求和。當總和s大於r時，停止並返回您所在的染色體。當然，對於每個群體，步驟1僅執行一次。

2.排名選擇

當健身值之間存在很大差異時，先前的選擇類型會出現問題。例如，如果最佳染色體適應度是所有擬合度總和的90％，那麼其他染色體將很少被選擇的機會。等級選擇首先對群體進行排序，然後每個染色體接收由該等級確定的適合度值。最差的將是健身1，第二個最差的2等等，最好的將具有適應度N（人口中的染色體數量）。您可以在下面的圖片中看到，在更改適應性與排名確定的數字後情況如何變化。

排名前的情況（適合度圖）

排名後的情況（訂單號圖）

現在所有染色體都有機會被選中。然而，這種方法會導致收斂速度變慢，因為最好的染色體與其他染色體的差別不大。

3.穩態選擇

這不是選擇父母的特定方法。這種選擇新種群的主要思想是染色體的很大一部分可以存活到下一代。穩態選擇GA以下列方式工作。在每一代中，選擇一些好的（具有更高適應性）染色體來創建新的後代。然後去除一些不好的（具有較低適合度）染色體並將新的後代放置在它們的位置。其餘人口倖存下來。

4.精英

精英主義的想法已經被引入。當通過交叉和變異創建新的種群時，我們有很大的機會，我們將失去最好的染色體。精英主義是首先將最佳染色體（或少數最佳染色體）復制到新種群的方法的名稱。其餘人口以上述方式構建。精英主義可以迅速提高GA的性能，因為它可以防止丟失最佳找到的解決方案。

交叉(Crossover)和突變 (Mutation)

交叉和變異是GA的兩個基本運算符。 GA的表現非常依賴於它們。運算符的類型和實現取決於編碼以及問題。有多種方法可以執行交叉和變異。在本章中，我們將簡要介紹一些如何執行多個編碼的示例和建議。

1.二進制編碼

交叉

單點交叉 - 選擇一個交叉點，從第一個父項復制從染色體開始到交叉點的二進制字元串，其餘從另一個父項復制

選擇兩點交叉 - 兩個交叉點，從第一個父節點復制從染色體開始到第一個交叉點的二進制字元串，從第一個父節點復制從第一個交叉點到第二個交叉點的部分，其餘的是再次從第一個父級復制

均勻交叉 - 從第一個父項或第二個父項中隨機復制位

算術交叉 - 執行一些算術運算以產生新的後代

突變

位反轉 - 選擇的位被反轉

2.置換編碼

交叉

單點交叉 - 選擇一個交叉點，將排列從第一個父項復制到交叉點，然後掃描另一個父項，如果該數字還沒有在後代中，則添加它注意：還有更多方法如何在交叉點之後產生休息

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

變異

順序更改 - 選擇並交換兩個數字

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

3.值編碼

交叉

可以使用來自二進制編碼的所有交叉

變異

添加一個小數字（用於實數值編碼） - 將一個小數字添加到（或減去）所選值

（1.29 5.68 2.86 4.11 5.55）=>（1.29 5.68 2.73 4.22 5.55）

4.樹編碼

交叉

樹交叉 - 在父母雙方中選擇一個交叉點，父母在該點被分割，交換點下面的部分被交換以產生新的後代

變異

更改運算符，數字 - 選定節點已更改

補充:

疑惑點：

初始種群是啥：

利用二進制（一般）表示最終解

例如：需要求解z=x^2+y^2的最大值，x={1，5，3，8}，y={5，4，0，6}

用六位二進制數表示由x，y組成的解，例如：001100 表示x=1，y=4

001100 稱為一條基因序列，表示的是該問題的一種解決 方案

種群是包含多個基因序列（解決方案/個體）的集合

適應度函數是啥，有什麼作用：

適應度函數可以理解成「 游戲 規則」，如果問題較為復雜，需要自定義適應度函數，說明如何區分優秀與不優秀的個體; 如果問題比較簡單，例如上述求最大值的問題，則直接用此函數式作為適應度函數即可。作用：評定個體的優劣程度，從而決定其遺傳機會的大小。

怎麼選擇：

定義「適者生存不適者淘汰」的規則，例如：定義適應度高的被選擇的概率更大

怎麼交叉：

利用循環，遍歷種群中的每個個體，挑選另一個體進行交叉。例如，通過遍歷為基因序列A挑選出B配對，則取A的前半部分，B的後半部分，組合成新的個體（基因序列）C

如何變異：

隨機挑選基因序列上的某一位置，進行0-1互換

建議 GA的參數

如果您決定實施遺傳演算法，本章應該為您提供一些基本建議。這些建議非常籠統。您可能希望嘗試使用自己的GA來解決特定問題，因為沒有一般理論可以幫助您針對任何問題調整GA參數。

建議通常是對GA的經驗研究的結果，這些研究通常僅在二進制編碼上進行。

交叉率

交叉率一般應高，約為80％-95％。 （但是有些結果表明，對於某些問題，交叉率約為60％是最好的。）

突變率

另一方面，突變率應該非常低。最佳利率似乎約為0.5％-1％。

人口規模

可能令人驚訝的是，非常大的人口規模通常不會改善GA的性能（從找到解決方案的速度的意義上說）。良好的人口規模約為20-30，但有時大小為50-100是最好的。一些研究還表明，最佳種群規模取決於編碼字元串（染色體）的大小。這意味著如果你有32位染色體，那麼人口應該高於16位染色體。

選擇

可以使用基本的輪盤賭選擇，但有時排名選擇可以更好。查看有關選擇優缺點的章節。還有一些更復雜的方法可以在GA運行期間更改選擇參數。基本上，這些表現類似於模擬退火。如果您不使用其他方法來保存最佳找到的解決方案，則應確保使用精英主義。您也可以嘗試穩態選擇。

編碼

編碼取決於問題以及問題實例的大小。查看有關編碼的章節以獲取一些建議或查看其他資源。

交叉和變異

運算符取決於所選的編碼和問題。查看有關操作員的章節以獲取一些建議。您還可以查看其他網站。

搜索空間

    如果我們正在解決問題，我們通常會尋找一些最好的解決方案。所有可行解決方案的空間（所需解決方案所在的解決方案集）稱為搜索空間（也稱為狀態空間）。搜索空間中的每個點代表一種可能的解決方案。每個可能的解決方案可以通過其對問題的值（或適應度）進行「標記」。通過GA，我們在眾多可能的解決方案中尋找最佳解決方案 - 以搜索空間中的一個點為代表。然後尋找解決方案等於在搜索空間中尋找一些極值（最小值或最大值）。有時可以很好地定義搜索空間，但通常我們只知道搜索空間中的幾個點。在使用遺傳演算法的過程中，隨著進化的進行，尋找解決方案的過程會產生其他點（可能的解決方案）。

    問題是搜索可能非常復雜。人們可能不知道在哪裡尋找解決方案或從哪裡開始。有許多方法可用於尋找合適的解決方案，但這些方法不一定能提供最佳解決方案。這些方法中的一些是爬山，禁忌搜索，模擬退火和遺傳演算法。通過這些方法找到的解決方案通常被認為是很好的解決方案，因為通常不可能證明最佳方案。

NP-hard Problems

NP問題是一類無法用「傳統」方式解決的問題。我們可以快速應用許多任務（多項式）演算法。還存在一些無法通過演算法解決的問題。有很多重要問題很難找到解決方案，但是一旦有了解決方案，就很容易檢查解決方案。這一事實導致了NP完全問題。 NP代表非確定性多項式，它意味著可以「猜測」解決方案（通過一些非確定性演算法），然後檢查它。如果我們有一台猜測機器，我們或許可以在合理的時間內找到解決方案。為簡單起見，研究NP完全問題僅限於答案可以是或否的問題。由於存在輸出復雜的任務，因此引入了一類稱為NP難問題的問題。這個類並不像NP完全問題那樣受限。 NP問題的一個特徵是，可以使用一個簡單的演算法，可能是第一眼看到的，可用於找到可用的解決方案。但是這種方法通常提供了許多可能的解決方案 - 只是嘗試所有可能的解決方案是非常緩慢的過程（例如O（2 ^ n））。對於這些類型問題的更大的實例，這種方法根本不可用。今天沒有人知道是否存在一些更快的演算法來提供NP問題的確切答案。對於研究人員來說，發現這樣的演算法仍然是一項重大任務（也許你！:-)）。今天許多人認為這種演算法不存在，因此他們正在尋找替代方法。替代方法的一個例子是遺傳演算法。 NP問題的例子是可滿足性問題，旅行商問題或背包問題。可以獲得NP問題匯編。

參考：

         https://www.jianshu.com/p/ae5157c26af9

        https://www.jianshu.com/p/b36b520bd187

『柒』 asp.net常用的而且比較經典的演算法都有哪些

文件結構：
插入排序
1.直接插入排序
2.二叉插入排序
3.2路插入排序
4.表插入排序
5.希爾排序
選擇排序
1.簡單選擇排序
2.錦標賽排序（樹選擇排序）
3.堆排序
交換排序
1.冒泡排序
2.雞尾酒排序（雙向冒泡排序）
3.快速排序

歸並排序

1.歸並排序

分配排序
1.箱排序（桶排序）
2.基數排序

注意：

1.箱排序沒有太大實用價值，主要是被基數排序所調用。該排序對不同的數據類型有不同的比較方法，本函數中針對整形數據進行比較。

2.快速排序和堆排序具有較高的效率，但是為了兼具高效保持排序的穩定性，建議使用歸並排序。

『捌』 堆排序過程

1，實用的排序演算法：選擇排序
（1）選擇排序的基本思想是：每一趟（例如第i趟，i=0，1，2，3，……n-2）在後面n-i個待排序元素中選擇排序碼最小的元素，作為有序元素序列的第i個元素。待到第n-2趟做完，待排序元素只剩下一個，就不用再選了。
（2）三種常用的選擇排序方法
1>直接選擇排序
2>錦標賽排序
3>堆排序
其中，直接排序的思路和實現都比較簡單，並且相比其他排序演算法，直接選擇排序有一個突出的優勢——數據的移動次數少。
（3）直接選擇排序簡介
1>直接選擇排序（select sort）是一種簡單的排序方法，它的基本步驟是：
1）在一組元素V[i]~V[n-1]中選擇具有最小排序碼的元素；
2）若它不是這組元素中的第一個元素，則將它與這組元素中的第一個元素對調；
3）在這組元素中剔除這個具有最小排序碼的元素，在剩下的元素V[i+1]~V[n-1]中重復執行1、2步驟，直到剩餘元素只有一個為止。
2>直接選擇排序使用注意
它對一類重要的元素序列具有較好的效率，這就是元素規模很大，而排序碼卻比較小的序列。因為對這種序列進行排序，移動操作所花費的時間要比比較操作的時間大的多，而其他演算法移動操作的次數都要比直接選擇排序來的多，直接選擇排序是一種不穩定的 排序方法。
3>直接選擇排序C++函數代碼

//函數功能，直接選擇排序演算法對數列排序
//函數參數，數列起點，數列終點
void dselect_sort(const int start, const int end) {
for (int i = start; i < end; ++i) {
int min_position = i;
for (int j = i + 1; j <= end; ++j) { //此循環用來尋找最小關鍵碼
if (numbers[j] < numbers[min_position]) {
min_position = j;
}
}
if (min_position != i) { //避免自己與自己交換
swap(numbers[min_position], numbers[i]);

（4）關於錦標賽排序
直接選擇排序中，當n比較大時，排序碼的比較次數相當多，這是因為在後一趟比較選擇時，往往把前一趟已經做過的比較又重復了一遍，沒有把前一趟的比較結果保留下來。
錦標賽排序（tournament sort）克服了這一缺點。它的思想與體育比賽類似，就是把待排序元素兩兩進行競賽，選出其中的勝利者，之後勝利者之間繼續競賽，再選出其中的勝利者，然後重復這一過程，最終構造出勝者樹，從而實現排序的目的。

2，堆排序的排序過程
（1）個人理解：堆排序是選擇排序的一種，所以它也符合選擇排序的整體思想。直接選擇排序是在還未成序的元素中逐個比較選擇，而堆排序是首先建立一個堆（最大堆或最小堆），這使得數列已經「大致」成序，之後只需要局部調整來重建堆即可。建立堆及重建堆這一過程映射到數組中，其實就是一個選擇的過程，只不過不是逐個比較選擇，而是藉助完全二叉樹來做到有目的的比較選擇。這也是堆排序性能優於直接選擇排序的一個體現。
（2）堆排序分為兩個步驟：
1>根據初始輸入數據，利用堆的調整演算法形成初始堆；
2>通過一系列的元素交換和重新調整堆進行排序。
（3）堆排序的排序思路
1>前提，我們是要對n個數據進行遞增排序，也就是說擁有最大排序碼的元素應該在數組的末端。
2>首先建立一個最大堆，則堆的第一個元素heap[0]具有最大的排序碼，將heap[0]與heap[n-1]對調，把具有最大排序碼的元素交換到最後，再對前面n-1個元素，使用堆的調整演算法siftDown(0,n-2)，重新建立最大堆。結果具有次最大排序碼的元素又浮到堆頂，即heap[0]的位置，再對調heap[0]與heap[n-2]，並調用siftDown(0，n-3)，對前n-2個元素重新調整，……如此反復，最後得到一個數列的排序碼遞增序列。
（4）堆排序的排序過程：
下面給出局部調整成最大堆的函數實現siftDown()，這個函數在前面最小堆實現博文中的實現思路已經給出，只需做微小的調整即可用在這里建立最大堆。

『玖』 遺傳演算法

優化的演算法有很多種，從最基本的梯度下降法到現在的一些啟發式演算法，如遺傳演算法(GA)，差分演化演算法(DE)，粒子群演算法(PSO)和人工蜂群演算法(ABC)。

舉一個例子，遺傳演算法和梯度下降：

梯度下降和遺傳演算法都是優化演算法，而梯度下降只是其中最基礎的那一個，它依靠梯度與方向導數的關系計算出最優值。遺傳演算法則是優化演算法中的啟發式演算法中的一種，啟發式演算法的意思就是先需要提供至少一個初始可行解，然後在預定義的搜索空間高效搜索用以迭代地改進解，最後得到一個次優解或者滿意解。遺傳演算法則是基於群體的啟發式演算法。

遺傳演算法和梯度下降的區別是：

1.梯度下降使用誤差函數決定梯度下降的方向，遺傳演算法使用目標函數評估個體的適應度
2.梯度下降是有每一步都是基於學習率下降的並且大部分情況下都是朝著優化方向迭代更新，容易達到局部最優解出不來；而遺傳演算法是使用選擇、交叉和變異因子迭代更新的，可以有效跳出局部最優解
3.遺傳演算法的值可以用二進制編碼表示，也可以直接實數表示

遺傳演算法如何使用它的內在構造來算出 α 和 β ：

主要講一下選擇、交叉和變異這一部分：
1.選擇運算:將選擇運算元作用於群體。選擇的目的是把優秀（適應值高）的個體直接遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。

2.交叉運算：將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。交叉運算元是將種群中的個體兩兩分組，按一定概率和方式交換部分基因的操作。將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。例如：（根據概率選取50個個體，兩兩配對，交換x,y，比如之前兩個是(x1,y1),(x2,y2)，之後變成了（x1,y2）,(x2,y1)）

3.變異運算：將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。（x2可能變為x2+δ，y1變為y1+δ）
種群P(t)經過選擇、交叉、變異運算之後得到下一代種群P(t+1)。

遺傳演算法就是通過對大量的數據個體使用選擇、交叉和變異方式來進化，尋找適合問題的最優解或者滿意解。

遺傳演算法參數的用處和設置：

1.編碼選擇：通常使用二進制編碼和浮點數編碼，二進制適合精度要求不高、特徵較少的情況。浮點數適合精度高、特徵多的情況
2.種群：種群由個體組成，個體中的每個數字都代表一個特徵，種群個體數量通常設置在40-60之間；迭代次數通常看情況定若計算時間較長可以在100內，否則1000以內都可以。
3.選擇因子：通常有輪盤賭選擇和錦標賽選擇，輪盤賭博的特點是收斂速度較快，但優勢個體會迅速繁殖，導致種群缺乏多樣性。錦標賽選擇的特點是群多樣性較為豐富，同時保證了被選個體較優。
4.交叉因子：交叉方法有單點交叉和兩點交叉等等，通常用兩點交叉。交叉概率則選擇在0.7-0.9。概率越低收斂越慢時間越長。交叉操作能夠組合出新的個體，在串空間進行有效搜索，同時降低對種群有效模式的破壞概率。
5.變異因子：變異也有變異的方法和概率。方法有均勻變異和高斯變異等等；概率也可以設置成0.1。變異操作可以改善遺傳演算法的局部搜索能力，豐富種群多樣性。
6.終止條件：1、完成了預先給定的進化代數；2、種群中的最優個體在連續若干代沒有改進或平均適應度在連續若干代基本沒有改進；3、所求問題最優值小於給定的閾值.

『拾』 遺傳演算法理解

遺傳演算法是一種進化演算法，進化是什麼哪？就是種群逐漸適應生存環境，種群中個體不斷得到改良的過程。

遺傳演算法是一種對生物遺傳的模擬、在演算法中，初始化一個種群，種群中的每個染色體個體都是一種解決方案，我們通過適應性fitness來衡量這個解決方案的好壞。並對它們進行選擇、變異、交叉的操作，找到最優的解決方案。

總結一下遺傳演算法的基本的步驟：

1.初始化一個種群，並評估每條染色體所對應個體的適應度。

2.選擇、交叉、變異，產生新的種群

3.再評估每個個體的適應值，如果適應值達到要求或者達到最大循環次數，否則重復2，不斷產生新種群。

知道了GA的大致流程之後、來具體分析一下細節，怎麼實現吧

我們知道遺傳演算法起源於生物遺傳，因此在種群中每個個體就是一個染色體，那如何對染色體進行編碼，讓它表示我們的解決方案那（就是把現實要優化的參數用編碼表示成一個染色體）。這里就遇到了一個編碼、解碼的問題，我們將需要優化的目標編碼成染色體，然後再解碼為我們可以用來計算fitness的解；

一般在進行參數優化時，一般有兩種方式：實數編碼、二進制編碼

實數編碼：基因直接用實數進行表示，這樣的表示方法比較簡單，不用特意解碼了，但是在交叉和變異時，容易過早收斂，陷入局部最優。

二進制編碼：將基因用二進制的形式表示，將參數的值轉化為二進制形式，這樣交叉、變異時更好操作，多樣性好，但是佔用的存儲空間大，需要解碼。

染色體就稱為個體。對於一次實驗，個體就是需要優化參數的一種解、許多這樣的個體就構成了種群。

在面對群體中那麼多個體時，如何判斷個體的好壞呢，就是通過適應值函數了，將解帶入適應值函數，適應值越大、解越好。

在遺傳演算法中，我們怎麼使得裡面的個體變得越來越優秀呢？

核心思想就是：選擇優秀的、淘汰不好的，並且為了生成更好的解，我們要嘗試交叉、變異，帶來新的解。

選擇就是從當前的種群中選擇出比較好的個體、淘汰不好的個體

常見的選擇方法有：輪盤賭選擇、錦標賽選擇、最佳保留選擇等等

輪盤賭選擇就是根據每個個體fitness和種群所有fitness之和比較，確定每個個體被選中的概率，然後進行n次選擇，選擇n個個體構成新種群，是一種放回抽樣的方式。

錦標賽就是每次從種群中選擇m個個體，選擇最優的，放入新種群，重復選擇，直到新種群中個體數目達到n。

最佳保留選擇就是在輪盤賭的基礎上，將fitness個體先加進新種群，因為輪盤賭是一種概率模型，可能存在最優個體沒有進入新種群的情況。

在選擇之後，就要考慮產生新的、更優秀的解，為種群帶來新的血液。遺傳演算法的思路是交叉兩個優秀的解，往往get好的解。

交叉通過在經過選擇的種群中，隨機選擇一對父母，將它們的染色體進行交叉，生成新的個體，替代原來的解。

常用的交叉方法有：單點交叉、多點交叉等等。

交叉就像生物裡面，染色體交換基因一樣的～但是並不是種群中所有個體都進行交叉的，實現時可以，設置一個交叉率和交叉概率，隨機選擇種群中兩個體、隨機一個數，小於交叉率就進行交叉操作，並根據交叉概率判斷交叉的程度，從而生成新個體，反之就保留這兩個體。

變異也是一種產生新個體的方式，通過改變個體上基因，期望產生更好的解。比如在以二進制編碼的個體上，將裡面的0、1進行等位變化啥的，就是0變1、1變0這樣。同樣也要考慮變異率、變異產生的新解是不可控的，可能很好，也可能很壞，不能像交叉一樣，確保一定的效果，所以往往變異率設置的比較小。