nsga演算法的提出者

A. 多目標優化問題

形式化定義：

特點：

①包含多個可能有沖突的目標函數。

②希望找到能夠很好平衡全部優化目標的解集；

帕累托最優是指資源分配的一種理想狀態。給定固有的一群人和可分配的資源，如果從一種分配狀態到另一種分配狀態，在沒有使得任何人的境況變壞的前提下，使得至少有一個人變得更好，這就是帕累托改善的狀態；換言之，不可能在不是任何其他人受損的情況下再改善某些人的境況。

支配（Dominace） ：當x1和x2滿足如下條件時稱x1支配x2：①對於所有目標函數x1不比x2差；②至少在一個目標函數上，x1嚴格比x2要好。

對於點1和點2：對於目標函數f1是越大越好，在取相同f2時，點1比點2好；對於目標函數f2是越小越好，在取相同f1時，點1比點2好。所以點1支配點2。

對於點1和點4：目標函數f1上，取相同f2時，點4比點1好；目標函數f2上，取相同f1時，點1比點4好。所以點1和點4互不支配。

不可支配解集（Non-dominated solution set） ：當一個解集中任何一個解都不能被該集合中其他解支配，那麼就稱該解集為不可支配解集。

帕累托最優解集（Pareto-optimal set ）：所有可行中的不可支配解集被稱為帕累托最優解集。

帕累托最優前沿面（Pareto-optimal front） ：帕累托最優解集的邊界（boundary）被稱為帕累托最優前沿面。

多目標優化問題的目標 ：①尋找盡可能接近最優的解集；②盡可能增大找到解的多樣性。

優點：簡單

缺點：①很難設定一個權重向量能夠獲得帕累托最優解；②在一些非凸情況下不能夠保證獲得帕累托最優解。

優點：能夠應用到凸函數和非凸函數場景下。

缺點：函數需要精心選擇，需要在獨立函數的最小值或最大值之內。

優點：weighted Techebycheff metirc能夠保證獲得所有帕累托最優解。

缺點：①需要有每個函數最大值和最小值的先驗知識；②需要每個目標函數的z*能夠獨立被找到；③對於較小的p值，不一定保證所有能夠獲得所有的帕累托最優解；④隨著p增加，問題會變得不可求導。

①隨機產生初始種群；

②計算各點的目標函數值和約束函數值；

③根據目標函數值對種群分級；

④根據約束函數值和分級結果計算各點的約束罰項、劣解罰項及總罰項；

⑤根據各點的總罰項計算適應度；

⑥根據各點的適應度，進行選擇、交叉和變異操作，生成新種群；

⑦將總罰項為0的點放入非劣解集候選表，對候選表進行檢查，保留第1級非劣點，刪除其他點；

⑧檢查是否收斂，如沒有，轉到步驟②；

⑨刪除候選表中與其他店距離太近的點；

⑩輸出候選表中的帕累托最優解集及對應的目標函數值；

最後，決策人根據個人偏好從帕累托最優解集中挑選出最適合該問題的解。

遺傳演算法相比傳統的演算法的優點是能夠得到一個最優解集，而不是單單一個最優解，這樣會提供更多的選擇，但是計算的復雜度可能稍高，而且裡面涉及的一些函數需要精心設計。

1.權重系數轉換法

對每個目標函數fi(x)賦予權重wi，wi為目標函數的重要程度。μ=Σwi·fi(x)，這里就將多目標轉化為單目標函數，將μ作為評價函數。

2.並列選擇法

主要步驟：(1)將種群按照目標函數個數等分為子種群，為每個子種群分配一個目標函數。(2)將子種群中的個體按照各自的目標函數選擇出適應度高的個體，然後將其組成一個子種群。(3)再將子種群進行交配、變異、生成下一代父親種群。然後再重復第一步。

並列選擇法的缺點在於易於生成單個目標函數的極端最優解，而較難生成一種多個目標在某種程度上都比較滿意的折中解。

3.排序選擇法

基本思想就是基於「帕累托最優個體」的概念對群體中的個體進行排序，然後根據這個次序進行種群選擇。這樣的話，就能夠讓帕累托最優個體有更多的機會遺傳到下一代。這種方法的缺點是僅僅度量了各個個體之間的優越次序，而並未度量各個個體的分散程度，所以容易生成相似的解，而不是分布較廣的多個最優解。

4.共享函數法

針對排序選擇方法的缺點，即所求的幾個最優解通常都是集中於最優解集合的某一個小區域內，而不是分散在整個帕累托最優解集合。由此，引出了基於共享函數的 小生境技術 （小生境技術就是將每一代個體劃分為若干類，每個類中選出若干適應度較大的個體作為一個類的優秀代表組成一個群，再在種群中，以及不同種群中之間，雜交，變異產生新一代個體群。同時採用預選擇機制和排擠機制或分享機制完成任務。）。該演算法對相同個體或類似個體的數目加以限制，以便能夠產生出種類較多的不同的最優解。這就引出一個問題，怎麼衡量兩個個體之間的相似度？這就是小生境數。顧名思義，小生境就是在一個小環境中相似的個體種群。最常見的公式為：

s(d)為共享函數，是表示群體中兩個個體之間密切關系程度的一個函數。d(X,Y)為個體X,Y之間的hanmin距離，也是用於衡量個體間相似度的一個函數。在計算出小生境數後，可以是小生境數較小的個體能夠有更多的機會被選中，遺傳到下一代群體中，即相似程度較小的個體能夠有更多的機會被遺傳到下一代群體中。

缺點：每次選擇操作時都需要進行大量的個體之間的優越關系的評價和比較運算，使得演算法搜索效率較低。

5.Horn和Nafploitis印的基於小生境帕累托多目標遺傳演算法(NPGA)

類似於第2個的並列選擇法，將每一代個體劃分為若干類，每個類別選出若干適應度較大的個體作為一個類的優秀代表組成一個種群，然後交配變異產生新一代種群。基於這種小生境的遺傳演算法（Niched Genetic Algorithms，NGA），可以更好地保持解的多樣性，同時具有很高的全局尋優能力和收斂速度，特別適合於復雜多峰函數的優化問題。

6.Srinvivas和Deb的非支配排序遺傳演算法NSGA

1980年提出來的，在遺傳演算法的基礎上對選擇再生方法進行改進：將每個個體按照他們的支配和非支配關系進行再分層，再做選擇操作，從而達到目的。

其分層的含義就是取出種群中的非支配個體組成一個小種群（第一個非支配最優層），並賦予其中所有個體一個共享的虛擬適應度值。然後再取出個體後的種群中繼續取出非支配個體，再將它們組成一個小種群（第二個非支配最優層），並且賦予所有個體一個共享的虛擬適應度值。重復上述步驟，直到原始種群分配完畢，這就是分層，也叫非支配型排序。

非支配型排序遺傳演算法的缺點：①計算復雜度較高；②沒有精英策略；③需要制定共享半徑。

針對以上問題，k·Deb 於2002年提出了 7 的方法。

7.帶精英策略的非支配排序遺傳散發——NSGAII

1).採用快速非支配型排序，降低了演算法復雜度。其復雜度降為了O(MN**2)。

2).提出了擁擠度和擁擠度比較運算元，代替需要指定共享半徑的適應度共享策略。並在快速排序後的同級比較中作為勝出標准。使准pareto解中的個體能擴展到整個pareto域中，並均勻分布，保持了種群的多樣性。

3).引入精英策略，擴大采樣空間。將父代種群和子代種群合並，保證優良個體能夠留存下來。

其演算法步驟如下：1.首先隨機產生數量為n的初始種群，然後對其進行非支配型排序。接下來，就是常規的選擇，交叉，變異操作產生第一代子代種群。2.然後，從第二代開始，將父代和子代合並。然後對其進行快速非支配型排序，同時計算每個非支配層的個體進行擁擠度的計算。然後根據非支配關系和擁擠度來選擇合適的個體組成新的父代種群。最後通過再通過選擇，交叉，變異產生子代。3.接下來，重復第二步。

具體做法參考：https://blog.csdn.net/quinn1994/article/details/80679528/

B. 關鍵節點組成的線路為什麼不一定是關鍵線路

在雙代號，單代號網路圖中，有關鍵線路，位於關鍵線路上的工作為關鍵工作。關鍵工作兩端的節點為關鍵節點。但是關鍵節點之間的工作不一定就是關鍵工作。這是因為：

1、兩個關鍵節點間可以有多項工作。

2、開始節點和完成節點均為關鍵節點的工作，不一定是關鍵工作。

關鍵節(Critical Seciton)與mutex的功能類似，但它只能由同一進程中的線程使用。關鍵節可以防止共享資源被同時訪問。關鍵節實際上是一個CRITICAL_SECTION型的變數，它一次只能被一個線程擁有。在線程使用關鍵節之前，必須調用InitializeCriticalSection函數將其初始化。

關鍵線路又稱關鍵路徑，為線路上總的工作持續時間最長的路線，即工期最長的路線。一個項目的關鍵線路可能不止一條，關鍵線路在網路圖中可用雙箭線、粗實線來表示。關鍵線路主要用於各類項目的計劃制定和其進度的監控。

(2)nsga演算法的提出者擴展閱讀：

關鍵節演算法

關鍵節優化

針對感測器網路多跳通信和多對一的流量特徵，提出負載均衡的約束條件，將關鍵節點集選取問題轉化為多目標優化問題，提出一種基於非支配遺傳演算法的關鍵節點集輪換演算法。通過節點密度控制機制，從投放的節點池中選取關鍵節點集，以滿足監測區域覆蓋連通。

在每輪網路工作的開始，激活不同的關鍵節點集，保證在每個時刻，有且僅有一個節點集完成對網路的充分覆蓋。模擬結果表明該演算法能夠快速收斂於最優解，極大化網路關鍵節點集數目，有效延長網路的生存時間。

無線感測器網路由大量集成了感測器、處理器、無線通信等模塊的低功耗節點以 Ad hoc 方式構成，節點協作完成監測區域環境信息的採集、處理和轉發，可以為環境監測、工業控制和災難現場緊急救援等諸多應用提供支持。

關鍵節排序

基於 NSGA-II 的多目標優化關鍵節點集輪換精 銳 非 支 配 遺 傳 算 法 NSGA-dominatedSorting Genetic Algorithm從非劣性排序、以擁擠距代替適值共享及基於精銳策略保留優異解等三個方面對原始 NSGA演算法進行改進，具有快速求解 Pareto 最優解的能力。

基於 NSGA-II 進行無線感測器網路關鍵節點集選取首先需要將問題空間轉化到編碼空間。為了避免重組操作中丟失優秀解，採用了一種循環重組的方法。同時，為了避免高適值個體快速繁殖而導致早熟，本文在非支配排序的過程中引入了刪除運算元，用來刪除種群中的相同個體。

C. 公鑰演算法原理

這是一種不對稱加密演算法。公鑰演算法包括快速公鑰演算法與傳統公鑰演算法。快速公鑰演算法與傳統公鑰演算法相比具有更廣泛地應用前景,對快速公鑰系統的研究是當前公鑰系統研究的一個熱點。

定義
不對稱加密演算法使用兩把完全不同但又是完全匹配的一對鑰匙—公鑰和私鑰。在使用不對稱加密演算法加密文件時，只有使用匹配的一對公鑰和私鑰，才能完成對明文的加密和解密過程。加密明文時採用公鑰加密，解密密文時使用私鑰才能完成，而且發信方（加密者）知道收信方的公鑰，只有收信方（解密者）才是唯一知道自己私鑰的人。不對稱加密演算法的基本原理是，如果發信方想發送只有收信方才能解讀的加密信息，發信者使用收信者的公鑰加密信件，收信者使用自己的私鑰鑰解密信件。顯然，採用不對稱加密演算法，收發信雙方在通信之前，收信方必須將自己早已隨機生成的公鑰送給發信方，而自己保留私鑰。由於不對稱演算法擁有兩個密鑰，因而特別適用於分布式系統中的數據加密。廣泛應用的不對稱加密演算法有RSA演算法和美國國家標准局提出的DSA。以不對稱加密演算法為基礎的加密技術應用非常廣泛。

工作原理
1976 年，Whitfield Diffe 和 Martin Hellman 創建了公鑰加密。公鑰加密是重大的創新，因為它從根本上改變了加密和解密的過程。

Diffe 和 Hellman 提議使用兩個密鑰，而不是使用一個共享的密鑰。一個密鑰（稱為「私鑰」）是保密的。它只能由一方保存，而不能各方共享。第二個密鑰（稱為「公鑰」）不是保密的，可以廣泛共享。這兩個密鑰（稱為「密鑰對」）在加密和解密操作中配合使用。密鑰對具有特殊的互補關系，從而使每個密鑰都只能與密鑰對中的另一個密鑰配合使用。這一關系將密鑰對中的密鑰彼此唯一地聯系在一起：公鑰與其對應的私鑰組成一對，並且與其他任何密鑰都不關聯。

由於公鑰和私鑰的演算法之間存在特殊的數學關系，從而使得這種配對成為可能。密鑰對在數學上彼此相關，例如，配合使用密鑰對可以實現兩次使用對稱密鑰的效果。密鑰必須配合使用：不能使用每個單獨的密鑰來撤消它自己的操作。這意味著每個單獨密鑰的操作都是單向操作：不能使用一個密鑰來撤消它的操作。此外，設計兩個密鑰使用的演算法時，特意設計無法使用一個密鑰確定密鑰對中的另一個密鑰。因此，不能根據公鑰確定出私鑰。但是，使得密鑰對成為可能的數學原理也使得密鑰對具有對稱密鑰所不具有的一個缺點。這就是，所使用的演算法必須足夠強大，才能使人們無法通過強行嘗試，使用已知的公鑰來解密通過它加密的信息。公鑰利用數學復雜性以及它的單向特性來彌補它是眾所周知的這樣一個事實，以防止人們成功地破解使用它編碼的信息。

如果將此概念應用於前面的示例，則發件人將使用公鑰將純文本加密成密碼。然後，收件人將使用私鑰將密碼重新解密成純文本。

由於密鑰對中的私鑰和公鑰之間所存在的特殊關系，因此一個人可以在與許多人交往時使用相同的密鑰對，而不必與每個人分別使用不同的密鑰。只要私鑰是保密的，就可以隨意分發公鑰，並讓人們放心地使用它。使許多人使用同一個密鑰對代表著密碼學上的一個重大突破，因為它顯著降低了密鑰管理的需求，大大提高了密碼學的可用性。用戶可以與任意數目的人員共享一個密鑰對，而不必為每個人單獨設立一個密鑰。

公鑰加密是郵件安全中的一個基本要素。如果沒有公鑰加密，那麼是否存在實用的郵件安全解決方案是值得懷疑的，因為在公鑰加密出現之前，密鑰管理是一件很麻煩的事情。在了解了公鑰加密的基本概念之後，接下來便是了解如何藉助這些概念來實現郵件安全性。

D. Raft 演算法（詳細版）

在分布式系統中，一致性演算法至關重要。在所有一致性演算法中，Paxos 最負盛名，它由萊斯利·蘭伯特（Leslie Lamport）於 1990 年提出，是一種基於消息傳遞的一致性演算法，被認為是類似演算法中最有效的。

Paxos 演算法雖然很有效，但復雜的原理使它實現起來非常困難，截止目前，實現 Paxos 演算法的開源軟體很少，比較出名的有 Chubby、LibPaxos。此外，Zookeeper 採用的 ZAB（Zookeeper Atomic Broadcast）協議也是基於 Paxos 演算法實現的，不過 ZAB 對 Paxos 進行了很多改進與優化，兩者的設計目標也存在差異——ZAB 協議主要用於構建一個高可用的分布式數據主備系統，而 Paxos 演算法則是用於構建一個分布式的一致性狀態機系統。

由於 Paxos 演算法過於復雜、實現困難，極大地制約了其應用，而分布式系統領域又亟需一種高效而易於實現的分布式一致性演算法，在此背景下，Raft 演算法應運而生。

Raft 演算法在斯坦福 Diego Ongaro 和 John Ousterhout 於 2013 年發表的《In Search of an Understandable Consensus Algorithm》中提出。相較於 Paxos，Raft 通過邏輯分離使其更容易理解和實現，目前，已經有十多種語言的 Raft 演算法實現框架，較為出名的有 etcd、Consul 。

根據官方文檔解釋，一個 Raft 集群包含若干節點，Raft 把這些節點分為三種狀態：Leader、 Follower、Candidate，每種狀態負責的任務也是不一樣的。正常情況下，集群中的節點只存在 Leader 與 Follower 兩種狀態。

• Leader（領導者） ：負責日誌的同步管理，處理來自客戶端的請求，與Follower保持heartBeat的聯系；

• Follower（追隨者） ：響應 Leader 的日誌同步請求，響應Candidate的邀票請求，以及把客戶端請求到Follower的事務轉發（重定向）給Leader；

• Candidate（候選者） ：負責選舉投票，集群剛啟動或者Leader宕機時，狀態為Follower的節點將轉為Candidate並發起選舉，選舉勝出（獲得超過半數節點的投票）後，從Candidate轉為Leader狀態。

通常，Raft 集群中只有一個 Leader，其它節點都是 Follower。Follower 都是被動的，不會發送任何請求，只是簡單地響應來自 Leader 或者 Candidate 的請求。Leader 負責處理所有的客戶端請求（如果一個客戶端和 Follower 聯系，那麼 Follower 會把請求重定向給 Leader）。

為簡化邏輯和實現，Raft 將一致性問題分解成了三個相對獨立的子問題。

• 選舉（Leader Election） ：當 Leader 宕機或者集群初創時，一個新的 Leader 需要被選舉出來；

• 日誌復制（Log Replication） ：Leader 接收來自客戶端的請求並將其以日誌條目的形式復制到集群中的其它節點，並且強制要求其它節點的日誌和自己保持一致；

• 安全性（Safety） ：如果有任何的伺服器節點已經應用了一個確定的日誌條目到它的狀態機中，那麼其它伺服器節點不能在同一個日誌索引位置應用一個不同的指令。

根據 Raft 協議，一個應用 Raft 協議的集群在剛啟動時，所有節點的狀態都是 Follower。由於沒有 Leader，Followers 無法與 Leader 保持心跳（Heart Beat），因此，Followers 會認為 Leader 已經下線，進而轉為 Candidate 狀態。然後，Candidate 將向集群中其它節點請求投票，同意自己升級為 Leader。如果 Candidate 收到超過半數節點的投票（N/2 + 1），它將獲勝成為 Leader。

第一階段：所有節點都是 Follower。

上面提到，一個應用 Raft 協議的集群在剛啟動（或 Leader 宕機）時，所有節點的狀態都是 Follower，初始 Term（任期）為 0。同時啟動選舉定時器，每個節點的選舉定時器超時時間都在 100~500 毫秒之間且並不一致（避免同時發起選舉）。

第二階段：Follower 轉為 Candidate 並發起投票。

沒有 Leader，Followers 無法與 Leader 保持心跳（Heart Beat），節點啟動後在一個選舉定時器周期內未收到心跳和投票請求，則狀態轉為候選者 Candidate 狀態，且 Term 自增，並向集群中所有節點發送投票請求並且重置選舉定時器。

注意，由於每個節點的選舉定時器超時時間都在 100-500 毫秒之間，且彼此不一樣，以避免所有 Follower 同時轉為 Candidate 並同時發起投票請求。換言之，最先轉為 Candidate 並發起投票請求的節點將具有成為 Leader 的「先發優勢」。

第三階段：投票策略。

節點收到投票請求後會根據以下情況決定是否接受投票請求（每個 follower 剛成為 Candidate 的時候會將票投給自己）：

請求節點的 Term 大於自己的 Term，且自己尚未投票給其它節點，則接受請求，把票投給它；

請求節點的 Term 小於自己的 Term，且自己尚未投票，則拒絕請求，將票投給自己。

第四階段：Candidate 轉為 Leader。

一輪選舉過後，正常情況下，會有一個 Candidate 收到超過半數節點（N/2 + 1）的投票，它將勝出並升級為 Leader。然後定時發送心跳給其它的節點，其它節點會轉為 Follower 並與 Leader 保持同步，到此，本輪選舉結束。

注意：有可能一輪選舉中，沒有 Candidate 收到超過半數節點投票，那麼將進行下一輪選舉。

在一個 Raft 集群中，只有 Leader 節點能夠處理客戶端的請求（如果客戶端的請求發到了 Follower，Follower 將會把請求重定向到 Leader） ，客戶端的每一個請求都包含一條被復制狀態機執行的指令。Leader 把這條指令作為一條新的日誌條目（Entry）附加到日誌中去，然後並行得將附加條目發送給 Followers，讓它們復制這條日誌條目。

當這條日誌條目被 Followers 安全復制，Leader 會將這條日誌條目應用到它的狀態機中，然後把執行的結果返回給客戶端。如果 Follower 崩潰或者運行緩慢，再或者網路丟包，Leader 會不斷得重復嘗試附加日誌條目（盡管已經回復了客戶端）直到所有的 Follower 都最終存儲了所有的日誌條目，確保強一致性。

第一階段：客戶端請求提交到 Leader。

如下圖所示，Leader 收到客戶端的請求，比如存儲數據 5。Leader 在收到請求後，會將它作為日誌條目（Entry）寫入本地日誌中。需要注意的是，此時該 Entry 的狀態是未提交（Uncommitted），Leader 並不會更新本地數據，因此它是不可讀的。

第二階段：Leader 將 Entry 發送到其它 Follower

Leader 與 Followers 之間保持著心跳聯系，隨心跳 Leader 將追加的 Entry（AppendEntries）並行地發送給其它的 Follower，並讓它們復制這條日誌條目，這一過程稱為復制（Replicate）。

有幾點需要注意：

1. 為什麼 Leader 向 Follower 發送的 Entry 是 AppendEntries 呢？

因為 Leader 與 Follower 的心跳是周期性的，而一個周期間 Leader 可能接收到多條客戶端的請求，因此，隨心跳向 Followers 發送的大概率是多個 Entry，即 AppendEntries。當然，在本例中，我們假設只有一條請求，自然也就是一個Entry了。

2. Leader 向 Followers 發送的不僅僅是追加的 Entry（AppendEntries）。

在發送追加日誌條目的時候，Leader 會把新的日誌條目緊接著之前條目的索引位置（prevLogIndex）， Leader 任期號（Term）也包含在其中。如果 Follower 在它的日誌中找不到包含相同索引位置和任期號的條目，那麼它就會拒絕接收新的日誌條目，因為出現這種情況說明 Follower 和 Leader 不一致。

3. 如何解決 Leader 與 Follower 不一致的問題？

在正常情況下，Leader 和 Follower 的日誌保持一致，所以追加日誌的一致性檢查從來不會失敗。然而，Leader 和 Follower 一系列崩潰的情況會使它們的日誌處於不一致狀態。Follower可能會丟失一些在新的 Leader 中有的日誌條目，它也可能擁有一些 Leader 沒有的日誌條目，或者兩者都發生。丟失或者多出日誌條目可能會持續多個任期。

要使 Follower 的日誌與 Leader 恢復一致，Leader 必須找到最後兩者達成一致的地方（說白了就是回溯，找到兩者最近的一致點），然後刪除從那個點之後的所有日誌條目，發送自己的日誌給 Follower。所有的這些操作都在進行附加日誌的一致性檢查時完成。

Leader 為每一個 Follower 維護一個 nextIndex，它表示下一個需要發送給 Follower 的日誌條目的索引地址。當一個 Leader 剛獲得權力的時候，它初始化所有的 nextIndex 值，為自己的最後一條日誌的 index 加 1。如果一個 Follower 的日誌和 Leader 不一致，那麼在下一次附加日誌時一致性檢查就會失敗。在被 Follower 拒絕之後，Leader 就會減小該 Follower 對應的 nextIndex 值並進行重試。最終 nextIndex 會在某個位置使得 Leader 和 Follower 的日誌達成一致。當這種情況發生，附加日誌就會成功，這時就會把 Follower 沖突的日誌條目全部刪除並且加上 Leader 的日誌。一旦附加日誌成功，那麼 Follower 的日誌就會和 Leader 保持一致，並且在接下來的任期繼續保持一致。

第三階段：Leader 等待 Followers 回應。

Followers 接收到 Leader 發來的復制請求後，有兩種可能的回應：

寫入本地日誌中，返回 Success；

一致性檢查失敗，拒絕寫入，返回 False，原因和解決辦法上面已做了詳細說明。

需要注意的是，此時該 Entry 的狀態也是未提交（Uncommitted）。完成上述步驟後，Followers 會向 Leader 發出 Success 的回應，當 Leader 收到大多數 Followers 的回應後，會將第一階段寫入的 Entry 標記為提交狀態（Committed），並把這條日誌條目應用到它的狀態機中。

第四階段：Leader 回應客戶端。

完成前三個階段後，Leader會向客戶端回應 OK，表示寫操作成功。

第五階段，Leader 通知 Followers Entry 已提交

Leader 回應客戶端後，將隨著下一個心跳通知 Followers，Followers 收到通知後也會將 Entry 標記為提交狀態。至此，Raft 集群超過半數節點已經達到一致狀態，可以確保強一致性。

需要注意的是，由於網路、性能、故障等各種原因導致「反應慢」、「不一致」等問題的節點，最終也會與 Leader 達成一致。

前面描述了 Raft 演算法是如何選舉 Leader 和復制日誌的。然而，到目前為止描述的機制並不能充分地保證每一個狀態機會按照相同的順序執行相同的指令。例如，一個 Follower 可能處於不可用狀態，同時 Leader 已經提交了若乾的日誌條目；然後這個 Follower 恢復（尚未與 Leader 達成一致）而 Leader 故障；如果該 Follower 被選舉為 Leader 並且覆蓋這些日誌條目，就會出現問題，即不同的狀態機執行不同的指令序列。

鑒於此，在 Leader 選舉的時候需增加一些限制來完善 Raft 演算法。這些限制可保證任何的 Leader 對於給定的任期號（Term），都擁有之前任期的所有被提交的日誌條目（所謂 Leader 的完整特性）。關於這一選舉時的限制，下文將詳細說明。

在所有基於 Leader 機制的一致性演算法中，Leader 都必須存儲所有已經提交的日誌條目。為了保障這一點，Raft 使用了一種簡單而有效的方法，以保證所有之前的任期號中已經提交的日誌條目在選舉的時候都會出現在新的 Leader 中。換言之，日誌條目的傳送是單向的，只從 Leader 傳給 Follower，並且 Leader 從不會覆蓋自身本地日誌中已經存在的條目。

Raft 使用投票的方式來阻止一個 Candidate 贏得選舉，除非這個 Candidate 包含了所有已經提交的日誌條目。Candidate 為了贏得選舉必須聯系集群中的大部分節點。這意味著每一個已經提交的日誌條目肯定存在於至少一個伺服器節點上。如果 Candidate 的日誌至少和大多數的伺服器節點一樣新（這個新的定義會在下面討論），那麼它一定持有了所有已經提交的日誌條目（多數派的思想）。投票請求的限制中請求中包含了 Candidate 的日誌信息，然後投票人會拒絕那些日誌沒有自己新的投票請求。

Raft 通過比較兩份日誌中最後一條日誌條目的索引值和任期號，確定誰的日誌比較新。如果兩份日誌最後條目的任期號不同，那麼任期號大的日誌更加新。如果兩份日誌最後的條目任期號相同，那麼日誌比較長的那個就更加新。

如同 4.1 節介紹的那樣，Leader 知道一條當前任期內的日誌記錄是可以被提交的，只要它被復制到了大多數的 Follower 上（多數派的思想）。如果一個 Leader 在提交日誌條目之前崩潰了，繼任的 Leader 會繼續嘗試復制這條日誌記錄。然而，一個 Leader 並不能斷定被保存到大多數 Follower 上的一個之前任期里的日誌條目 就一定已經提交了。這很明顯，從日誌復制的過程可以看出。

鑒於上述情況，Raft 演算法不會通過計算副本數目的方式去提交一個之前任期內的日誌條目。只有 Leader 當前任期里的日誌條目通過計算副本數目可以被提交；一旦當前任期的日誌條目以這種方式被提交，那麼由於日誌匹配特性，之前的日誌條目也都會被間接的提交。在某些情況下，Leader 可以安全地知道一個老的日誌條目是否已經被提交（只需判斷該條目是否存儲到所有節點上），但是 Raft 為了簡化問題使用了一種更加保守的方法。

當 Leader 復制之前任期里的日誌時，Raft 會為所有日誌保留原始的任期號，這在提交規則上產生了額外的復雜性。但是，這種策略更加容易辨別出日誌，即使隨著時間和日誌的變化，日誌仍維護著同一個任期編號。此外，該策略使得新 Leader 只需要發送較少日誌條目。

raft 的讀寫都在 leader 節點中進行，它保證了讀的都是最新的值，它是符合強一致性的（線性一致性），raft 除了這個還在【客戶端交互】那塊也做了一些保證，詳情可以參考論文。但是 zookeeper 不同，zookeeper 寫在 leader，讀可以在 follower 進行，可能會讀到了舊值，它不符合強一致性（只考慮寫一致性，不考慮讀一致性），但是 zookeeper 去 follower 讀可以有效提升讀取的效率。

對比於 zab、raft，我們發現他們選舉、setData 都是需要過半機制才行，所以他們針對網路分區的處理方法都是一樣的。

一個集群的節點經過網路分區後，如一共有 A、B、C、D、E 5個節點，如果 A 是 leader，網路分區為 A、B、C 和 D、E，在A、B、C分區還是能正常提供服務的，而在 D、E 分區因為不能得到大多數成員確認（雖然分區了，但是因為配置的原因他們還是能知道所有的成員數量，比如 zk 集群啟動前需要配置所有成員地址，raft 也一樣），是不能進行選舉的，所以保證只會有一個 leader。

如果分區為 A、B 和 C、D、E ，A、B 分區雖然 A 還是 leader，但是卻不能提供事務服務（setData），C、D、E 分區能重新選出 leader，還是能正常向外提供服務。

1）我們所說的日誌（log）與狀態機（state machine）不是一回事，日誌指還沒有提交到狀態機中的數據。
2）新 leader 永遠不會通過計算副本數量提交舊日誌，他只能復制舊日誌都其他 follower 上，對於舊日誌的提交，只能是新 leader 接收新的寫請求寫新日誌，順帶著把舊日誌提交了。

E. 關鍵節點組成的線路為什麼不一定是關鍵線路

關鍵節點之間的工作不一定就是關鍵工作。這是因為：

1、兩個關鍵節點間可以有多項工作

2、開始節點和完成節點均為關鍵節點的工作，不一定是關鍵工作

F. NSGA-Ⅱ的介紹

NSGA-Ⅱ是目前最流行的多目標進化演算法之一，它降低了非劣排序遺傳演算法的復雜性，具有運行速度快，解集的收斂性好的優點，成為其他多目標優化演算法性能的基準。

G. 誰能通俗的講解一下NSGA-II多目標遺傳演算法

NSGA-II特別的地方就在它的選擇過程上，其他的和其他演算法也沒什麼區別。

選擇過程分兩個部分：
1. 把種群分成一組Pareto非支配集。一個非支配集里的個體不被當前或之後非支配集里的任何個體支配。方法就是每次選出所有不被任何其他個體支配的非支配個體，從種群里刪除當一個非支配集，然後剩下的再不停重復這個過程，直到取完。
2. 按crowd distance排序。就是在各個維度左右相鄰個體的距離之和。

選擇的時候，先從前往後一個個取非支配集。取到手裡的個體數量大於等於需要的數量了，最後一個非支配集里再怎麼選？選crowd distance大的。

H. pso的多目標優化

在多目標優化問題中，每個目標函數可以分別獨立進行優化，然後為每個目標找到最優值。但是，很少能找到對所有目標都是最優的完美解，因為目標之間經常是互相沖突的，只能找到Pareto最優解。
PSO演算法中的信息共享機制與其他基於種群的優化工具有很大的不同。在遺傳演算法（GA）中，染色體通過交叉互相交換信息，是一種雙向信息共享機制。但是在PSO演算法中，只有gBest（或nBest）給其他微粒提供信息，是一種單向信息共享機制。由於點吸引特性，傳統的PSO演算法不能同時定位構成Pareto前鋒的多個最優點。雖然通過對所有目標函數賦予不同的權重將其組合起來並進行多次運行，可以獲得多個最優解，但是還是希望有方法能夠一次同時找到一組Pareto最優解。
在PSO演算法中，一個微粒是一個獨立的智能體，基於其自身和同伴的經驗來搜索問題空間。前者為微粒更新公式中的認知部分，後者為社會部分，這二者在引導微粒的搜索方面都有關鍵的作用。因此，選擇適當的社會和認知引導者（gBest和pBest）就是MO-PSO演算法的關鍵點。認知引導者的選擇和傳統PSO演算法應遵循相同的規則，唯一的區別在於引導者應按照Pareto支配性來確定。社會引導者的選擇包括兩個步驟。第一步是建立一個從中選取引導者的候選池。在傳統PSO演算法中，引導者從鄰居的pBest之中選取。而在MO-PSO演算法中更常用的方法是使用一個外部池來存儲更多的Pareto最優解。第二步就是選擇引導者。gBest的選擇應滿足如下兩個標准：首先，它應該能為微粒提供有效的引導來獲得更好的收斂速度；第二，它還需要沿Pareo前鋒來提供平衡的搜索，以維持種群的多樣性。文獻中通常使用兩種典型的方法：（1）輪盤選擇模式，該方式按照某種標准進行隨機選擇，其目的是維持種群的多樣性；（2）數量標准：按照某種不涉及隨機選擇的過程來確定社會引導者。
Moore最早研究了PSO演算法在多目標優化中的應用，強調了個體和群體搜索二者的重要性，但是沒有採用任何維持多樣性的方法。Coello在非劣最優概念的基礎上應用了一個外部「容器」來記錄已找到的非支配向量，並用這些解來指導其它微粒的飛行。Fieldsend採用一種稱為支配樹的數據結構來對最優微粒進行排序。Parsopoulos應用了權重聚合的方法。Hu應用了動態鄰域，並在此基礎上利用擴展記憶，按詞典順序依次優化各個目標。Ray使用聚集機制來維持多樣性，並用一個多水平篩來處理約束。Lu使用了動態種群策略。Bartz-Beielstein採用歸檔技術來提高演算法性能。Li在PSO演算法中採用NSGA-II演算法中的主要機制，在局部最優微粒及其後代微粒之間確定局部最優微粒；並此基礎上又提出一種新的演算法，在適應值函數中使用最大最小策略來確定Pareto支配性。張利彪使用多個目標函數下各最優位置的均值來指導微粒飛行。Pulido使用多個子種群並採用聚類技術來求解多目標規劃問題。Mahfouf採用加權聚合方法來計算微粒的適應值，並據此確定引導微粒的搜索。Salazar-Lechuga使用適應值共享技術來引導微粒的搜索。Gong提出微粒角度的概念，並使用最小微粒角度和微粒密度來確定局部最優和全局最優微粒。基於AER模型，Zhang提出一種新的智能PSO模型，來將種群驅向Pareto最優解集。Ho提出一種新的適應值分配機制，並使用壽命（Age）變數來保存和選擇最優歷史記錄。Huang將CLPSO演算法應用到多目標規劃中。Ho提出另一種基於Pareto的與尺度無關的適應值函數，並使用一種基於正交試驗設計的智能運動機制（IMM）來確定微粒的下一步運動。Branke系統研究了多種個體最優微粒的選擇方法對MOPSO演算法性能的影響。張勇考慮儲備集更新策略在多目標PSO演算法中的關鍵作用，提出一種兩階段儲備集更新策略。
原萍提出一種分布式PSO演算法—分割域多目標PSO演算法（DRMPSO），並將其應用到基站優化問題。向量評價PSO演算法（VEPSO）是一種受向量評價遺傳演算法（VEGA）的啟發提出的一種演算法，在VEPSO演算法中，每個種群僅使用多個目標函數之一來進行評價，同時各種群之間互相交互經驗。將每個種群分配到一台網路PC上，即可直接使VEPSO演算法並行化，以加速收斂。Vlachogiannis應用並行VEPSO演算法來確定發電機對輸電系統的貢獻。熊盛武利用PSO演算法的信息傳遞機制，在PSO演算法中引入多目標演化演算法常用的歸檔技術，並採用環境選擇和配對選擇策略，使得整個群體在保持適當的選擇壓力的情況下收斂於Pareto最優解集。
由於適應值的計算非常消耗計算資源，為了減少計算量，需要減少適應值評價的次數。Reyes-Sierra採用適應值繼承和估計技術來實現該目標，並比較了十五種適應值繼承技術和四種估計技術應用於多目標PSO演算法時的效果。
保持MOPSO中的多樣性的方法主要有兩種：sigma方法和ε-支配方法。Villalobos-Arias在目標函數空間中引入條塊劃分來形成聚類，從而保持多樣性。