演化式计算下篇

演化式計算下篇：基因演算法以及三種應用實例29

演化式計算下篇：

基因演算法以及三種應用實例

林豐澤*

文化大學應用數學系

摘 要

演化式計算是一個通用名詞，泛指以達爾文進化論”適者生存，不適者淘汰” 為基礎，來模擬自然界演化過程所建立的計算模式，這些計算模式又被稱為演化式演算法。經過將近三十餘年來的努力，演化式計算已經發展成為許多不同的研究領域與不同的研究團體，然而最早出現也是最主要的演化式演算法是演化式規劃、演化策略、與基因演算法。我們分成上下兩篇論文來介紹演化式演算法，做為演化式計算入門者的介紹文章。上篇不僅探討這三種主要模式的理論架構，並且分析與比較三者間的主要差異，下篇是介紹基因演算法的設計方法與步驟以及它的三種典型應用實例。我們針對基因演算法的設計方法分成下列四部份來討論：(1)基因編碼方式，(2)適應函數，(3)挑選機制，與 (4)交配與突變機制。三種典型的應用實例是：求函數最大化問題、破解維瓊內爾密碼、與求解最佳模糊利潤。對於每一個問題，我們分別就背景說明、設計方法、與結果討論來說明基因演算法是一種穩健、有效率的最佳化方法。

關鍵詞：演化式計算、基因演算法、函數最大化問題、維瓊內爾密碼、最佳模糊利潤

* E-mail: ftlin@https://www.wendangku.net/doc/3816764696.html,.tw

30智慧科技與應用統計學報

Evolutionary Computation Part 2:

Genetic Algorithms and Their Three

Applications

Feng-Tse Lin*

Department of Applied Mathematics

Chinese Culture University

Abstract

Evolutionary computation is a general term for a kind of computational model, which is based on Darwinian evolution’s “survival of the fittest” to simulate the natural evolution processes. These computational models are also called evolutionary algorithms. Over the past thirty years of endeavors, evolutionary computation has been developed into several different research fields and different research communities. Among of these, Evolutionary Programming, Evolution Strategy, and Genetic Algorithms, are the pioneers and the main streams of evolutionary algorithms. We would like to introduce evolutionary computation in two parts of papers as introductory articles for the beginners. The first part deals with not only the discussions of theoretical frameworks, but also the analysis and the comparison of these three major models. The second part introduces the design and the implementation of Genetic Algorithms as well as their three typical types of application. In this paper, we discuss the implementation of Genetic Algorithms in the following four parts: (1) gene coding, (2) fitness function, (3) selection mechanism, and (4) crossover and mutation mechanism. The three typical applications are the function maximization, breaking Vigenère cipher, and the optimal fuzzy profit problem. For each problem, we give its background, problem definition, detailed design method, and empirical results to support that Genetic Algorithms are a robust and an efficient optimization approach.

演化式計算下篇：基因演算法以及三種應用實例31

Keywords: Evolutionary computation, Genetic Algorithms, Function maximization problem, Vigenère cipher, Optimal fuzzy profit problem

* E-mail: ftlin@https://www.wendangku.net/doc/3816764696.html,.tw

This work was supported in part by the National Science Council, R.O.C. under Grant NSC 92-2213-E-034-003

32智慧科技與應用統計學報

1. 前言

演化式計算代表著模擬生物演化程序所建立的計算模式，根據達爾文進化論”適者生存，不適者淘汰” 的道理，做為在廣大空間的搜尋機制，藉此來求解各種困難的組合最佳化問題，找到問題的最佳解。演化式計算所建立的計算模式通稱為演化式演算法 (Evolutionary Algorithms，簡稱EA)。EA 有三種基本的理論模式，也被稱為是EA 的主流模式 (Back and Schwefel, 1993)，它們是演化式規劃 (Evolutionary Programming)、演化策略 (Evolution Strategy)、與基因演算法 (Genetic Algorithms，簡稱 GA)。我們針對這三種模式撰寫了上下兩篇文章，是希望對演化式計算從理論到應用做一個完整的介紹與說明，做為入門者的介紹教材。上篇文章是理論篇而下篇是應用篇。於上篇中我們除了介紹這三種基本模式的概念與運作方式外，並且比較與分析三者之間的差異。本文是下篇，我們要介紹基因演算法的設計方法與步驟，包括基因編碼方式、適應函數、挑選機制、以及交配與突變的設計，並且以三種典型的應用實例來驗証基因演算法具有穩健性與效率性。

GA 是所有 EA模式中最為著名也是使用最多的演化式演算法。Holland 認為自然界的演化是發生在生物染色體的基因中，每一種生物的特徵係來自於該物種上一代的基因排列，演化是指每一代基因所發生的變化情形。所謂適者生存是指這一代的基因排列優於上一代的基因排列，而產生比上一代更能適應環境生存的世代 (Holland, 1975)。因此，GA 是強調基因型的轉變，將欲求解問題的參數經過編碼成為基因格式，利用遺傳運算進行演化來找到問題的最佳解。這些遺傳運算是模擬自然界的演化程序，包括有複製 (reproduction)、交配 (crossover) 與突變 (mutation) 等等。因此 GA 具有下列幾點特性 (Goldberg, 1989)：

(1) G A是將參數編碼進行演化運算，而不是使用參數本身做搜尋。

(2) G A是高度的平行搜尋，會同時考慮空間的多個點而不是單一點，

因此可避免陷入區域的最佳解。

(3) G A只有使用適應函數做為本體的知識，沒有其他繁瑣的數學計

算。

(4) G A使用“機率規則” 而不是使用“明確規則” 來導引搜尋方

向，因此可適用於不同類型的問題上。

演化式計算下篇：基因演算法以及三種應用實例33

為了要證明 GA 是穩健的、有效率的演化式演算法，我們挑選三種典型的應用實例來說明。第一個應用是求函數的最大化問題，第二是破解密碼的問題，第三是求解最佳模糊利潤的問題。這三種應用代表三種不同類型的問題，需要使用不同的資料結構與不同的設計程序。本論文的結構如下所述。第二節說明 GA 的處理流程與設計步驟，我們分為基因編碼方式、適應函數、挑選機制、以及交配與突變機制等四部份來說明。第三、四、五節討論如何應用 GA 求解三種不同類型的問題，每一個問題我們都按照個體表示法、挑選機制、遺傳運算子、與執行結果的順序進行討論。第三節是求解複雜的函數最大化問題，第四節是破解維瓊內爾密碼，第五節是求解最佳模糊利潤。最後，第六節是本文的結論。

2. 基因演算法 (GA)

2.1 GA 的流程圖

GA 的處理流程圖如圖 1 所示，其做法簡單敘述如下。最初，隨機產生規模為N的群體稱為第 0 代，然後去評估每一個個體(染色體) 得到適應值。接著根據既定的挑選機制來複製個體進行遺傳演化。最典型的做法是根據個體的適應值，每一次挑選兩個個體當做雙親，適應值較高者被挑選的機率多於適應值較低者，因此高適應值的個體有多次的機會繁衍於後代。雙親根據機率r c決定是否要進行交配產生子代，產生後的子代再根據機率r m決定是否要做進一步的突變。交配是主要的遺傳運算，而突變只是次要的動作。產生後的子代或原來的雙親(沒有進行交配或突變者) 共同組成下一世代(仍然是N個)，如此繼續進行直到滿足終止條件為止。

34智慧科技與應用統計學報

圖 1 基因演算法的演化流程圖

2.2設計步驟

上述 GA 不斷重覆循環的演化程序可視為是在龐大的搜尋空間中，選擇可行的區域做有系統的多點搜尋。這種平行多點找尋方式，與其他技巧所使用的搜尋方法有極大的不同，這也是 GA 被視為是有效率搜尋方法的原因之一。應用 GA 求解組合最佳化問題的基本精神是：將欲搜尋問題的參數編碼成 0 與 1 的二進位碼型式，根據問題的條件或目標函數來設計適應函數。通常問題的目標函數可直接用來評估個體的優劣好壞，但是有些問題由於屬性的不同，它們的目標函數要經過適度的修正才能夠拿來當做適應函數，我們將在 2.4 節討論之。適應值較高的個體有較多的機會被挑選到交配池，這稱為複製。被複製的個體根據事先決定的機率，r c與r m，來做交配與突變，交配如同在搜尋空間中做大幅度的跳躍搜尋，而突變如同在鄰近區域做局部搜尋。設計 GA 求解問題可大致分成下列七個步驟進行之。

(1) 設計編碼方式(個體表示法)

(2) 決定群體規模

演化式計算下篇：基因演算法以及三種應用實例35

(3) 設計適應函數，決定個體適應度的評估標準

(4) 決定挑選與複製方法

(5) 定義交配與交配機率

(6) 定義突變與突變機率

(7) 決定終止條件

我們將上述的步驟歸納成四部份，稱為是 GA 的主要架構。這四部分是：(1) 基因編碼方式 (gene coding)， (2) 適應函數 (fitness function)，(3) 挑選機制 (selection mechanism)， (4) 交配與突變機制 (crossover and mutation mechanism)。以下就這四部份逐一來說明之。

2.3基因編碼方式

設計 GA 時首先要決定個體的編碼方式。在生物界基因是構成染色體的基本單元，基因中具有遺傳的物質是 DNA，而 DNA 是由 ATGC 四種核酸鹼基所構成的序列訊息，我們實作時則不用考慮那麼多。傳統上 GA 是強調基因型編碼，所以一個基因是代表一個實數或一個整數，或者甚至只是一個位元而已。但是無論如何，即使是實數或是整數，它們仍然是使用二進位編碼的。一個染色體上有多個基因，基因的數目就是欲求解問題的參數數目。圖 2(a) 是一個染色體有 6 個基因，每一個基因使用 3 個位元來編碼，這是典型的二進位編碼表示法。此外，還可以使用實數編碼或符號編碼等方式。圖 2(b) 是實數編碼的例子，這個染色體有 6 個基因，每一個基因對應一個實數變數。圖 2(c) 是符號編碼的例子，每一個基因對應一個符號變數，當我們欲求解推銷員旅行問題時，就可能需要使用符號編碼來表示城市名稱。

接著要決定每一代究竟有多少個體要進行演化，每一代的個體數目就是群體規模N。群體進行演化時就相當於同時做N組平行找尋，N太小則演化速度緩慢，也容易陷入區域最佳解；N太大則計算數量龐大，會耗費較長的計算時間。事實上，到目前為止N值的決定沒有明確的定論，典型的是從 30 到 300 都有，通常要看問題的本質以及執行效率或執行時間等因素，經過多次實驗後才決定之。

36 智慧科技與應用統計學報

圖 2 染色體的三種編碼方式，每一個染色體有6個基因。(a) 二進位編碼，

(b) 實數編碼，(c) 符號編碼。

2.4 適應函數

雖然問題的目標函數可用來評估個體的適應度 (fitness)，但是每一問題的屬性未必是相同的，有些問題的目標函數要修正後才能適用，有些問題甚至沒有目標函數可用。大部分屬於工程的問題是沒有簡單的目標函數可用，其解決方法就是另行設計一個模擬程式來做為適應函數。有些目標函數則是所產生的適應值範圍過於狹窄，會降低染色體的多樣性，容易發生群體過早收斂的現象，而過早收斂往往得不到全體最佳解。這種情況需要做適應函數的調整，根據過去的文獻資料，有兩種基本的調整類型：一是靜態比率調整 (static scaling)，二是動態比率調整 (dynamic scaling) (Goldberg, 1989; Michalewicz, 1992; Gen and Cheng, 1997)。最簡單的靜態比率調整是將目標函數做線性轉換，因此又稱為線性調整，此即 g = αf + β，其中 f 是原來的目標函數，g 是調整後的適應函數，α 與 β 是參數。而動態比率調整就是動態線性轉換，此即 g = αf + βt ，其中 βt 隨著每一世代而動態變化。我們就靜態比率調整來詳細說明這個做法。如上所述，f 是原來個體的適應值 (目標函數)，g 是調整後的適應值

g = αf + β

(1) (1) 式的參數 α 與 β 必需滿足下列式子，

g f = (2)

(a) 二進位編碼

(b) 實數編碼 (c) 符號編碼

演化式計算下篇：基因演算法以及三種應用實例 37

f k

g =max (3) 0min >g (4) f 是調整前群體的平均適應值，g 是調整後群體的平均適應值，max g 是調整後的最大適應值，而 min g 是調整後的最小適應值。第 (2) 式是保持調整前後群體的平均適應值不變，第 (3) 式是說明調整後的最大適應值是調整前平均適應值的 k 倍，第 (4) 式是保証調整後最小適應值不會是負值。圖 3 是適應函數調整前後兩者之間的關係示意圖，經過線性轉換後，max g 可被複製 k 個，而 g (或 f ) 可被複製一個。由於原來 Goldberg 所提出的線性轉換沒有 (4) 式，因此調整後的適應值可能會得到負數，對此一情況 Forrest 曾提出 sigma truncation 的改進做法 (Gen and Cheng, 1997)。Sigma truncation 是說要調整 f 之前先將群體的平均適應值減去某一常數值，此值是群體適應值的變異數 (σ) 的某一倍數 (c )，此式子如下： g = f ? (f ? c × σ) (5) 其他調整方法還有Gillies 提出的 power law scaling ，這是將適應值 f 調整為某一乘冪 k ，Gillies 建議 k = 1.005 (Gen and Cheng, 1997)。 g = f k

(6)

圖 3 適應函數的線性轉換觀念

2.5 挑選機制

挑選機制其實就是探討如何從群體 (樣本空間) 挑選出個體 (樣本)

0 適應值

38 智慧科技與應用統計學報

的取樣方式，被挑選的個體就是親代，可經由遺傳運算來產生子代。基本的取樣機制有三種：(1) 隨機取樣 (stochastic sampling)，(2) 明確取樣 (deterministic sampling)，與 (3) 混合取樣 (mixed sampling) (Gen and Cheng, 1997;Goldberg, 1989)。早期的 GA 大都使用隨機取樣，其觀念是每一個體根據它的存活機率來決定被複製的數目，做法是先計算出個體的期望值，再根據群體規模將期望值轉換成個體數目。最著名的隨機取樣就是 Holland 提出的輪盤式 (roulette wheel selection) 選擇。輪盤式選擇是將每一個體視為是輪盤上的一個區塊，區塊面積的大小與該個體的適應值成正比，適應值越大則區塊面積也越大，被挑選的機率也就越高。假如將輪盤看成是射飛鏢的遊戲，明顯的可看出面積越大就越容易射中，每次射中區塊 k 就等於挑選了個體 k ，總共射出 N 次飛鏢就會選出 N 個個體。每一次挑選，個體 k 被選中的機率是：

∑==N j j

k

k f f p 1 (7)

其中 f k 是個體 k 的適應值。輪盤式選擇又稱為比例挑選，它的缺點是：可能會造成抽樣誤差，此即染色體被複製的數目與它的期望值相差很大。此外，也可能發生適應度高的染色體被大量的複製而產生 “超級染色體”，造成群體過早收斂的現象。Baker 建議使用隨機普遍抽樣 (stochastic universal sampling) 的做法 (Baker, 1985)，這是計算每一個體 k 的期望值 e k = N × p k ，其中 N 是群體規模而 p k 是個體 k 的機率，再根據 e k 之值來實際分配個體 k 被複製的數目。

明確取樣是從樣本空間直接 (不用機率) 選出最佳的 N 個染色體，演化策略就是使用這種明確取樣方式。基本上，演化策略有 (μ, λ) 與 (μ+λ) 兩種挑選模式。(μ, λ) 模式是 μ 個雙親產生 λ 個子代後，再從 λ 中選出較優的 μ 個個體成為下一代群體。然而 (μ+λ) 模式是 μ 個雙親產生 λ 個子代後，再從 μ + λ 個子代與親代中挑選出最佳的 μ 個個體來組成下一代。此外還有區塊挑選 (block selection) 以及截取挑選 (truncation selection) 兩者也都是屬於明確取樣 (Thierens and Goldberg, 1994)。區塊挑選是先將所有染色體根據它們的適應值由大而小排序，然後從頭開始挑選最佳的 N 個。截取挑選是定義一個臨界值 T ，保證一定有 T % 個最佳

演化式計算下篇：基因演算法以及三種應用實例39

的染色體會被挑選，且每一個個體會有 100/T個數目。

混合取樣是同時含有隨機與明確兩種特性，最典型的例子是 Goldberg 提出的競賽挑選 (tournament selection)。此法是於群體中隨機挑選一些個體，由這些個體舉行一場比賽來相互競爭，最優者就是雙親 (Goldberg, 1989)。這個過程會重複進行，舉行不同的賽程直到選出足夠的親代為止。若每場賽事只有 2 個染色體參加，則稱為二元競賽。Wetzel 提出隨機競賽挑選(stochastic tournament selection)，做法是：每一染色體仍然根據適應值去計算它的機率，接著使用輪盤抽取兩個或數個個體，適應值最高者就直接做為下一代的個體 (Wetzel, 1983)。上述的輪盤式選擇或競賽挑選由於有隨機性質，有可能造成最佳適應值的個體沒被選上，因此有一種稱為精英挑選 (elitism) 的策略，此策略保證最佳的個體一定會被選上。

2.6 交配機制

交配是主要的遺傳運算子，將兩個染色體經過合併的程序來產生子代，讓子代各含有雙親的部分特性。交配的目的是希望子代能夠組合出含有更高適應度的染色體，然而有可能子代只遺傳雙親的缺點，所以交配不保證一定可以製造出更好的子代，不過有了天擇的機制，較差的子代會逐漸被淘汰，而優良的子代可以繼續繁衍下去。於上篇中我們已介紹了四種常用的交配方式：(1) 單點、(2) 兩點、(2) 多點、以及 (4) 均一交配(Syswerda, 1989)。許多研究顯示(Beasley, Bull, and Martin, 1993) 兩點交配較優於單點交配，只有當群體接近收斂時，兩點交配的效果才會遜色於單點交配(Spears and De Jong, 1993)。圖 4 是雙點交配，做法是隨機選取兩個不同的交配點，將雙親切割成前段、中段、與後段，雙親各自保留前段與後段而交換中段來產生子代，因此子代都含有雙親的部分資料。有的研究結果顯示：多點與均一交配有極差的效果，只有在一些特殊的情況下，才能有好的執行效率。

40 智慧科技與應用統計學報

圖 4 兩點交配是任意選取兩個交配點做交換而產生子代

圖 5 GA 對子代做突變

2.7 突變機制

突變會導致染色體突然間做隨意的變化，常見的變化是改變染色體上的一個基因。突變的作用會引導 GA 進入未曾尋找過的基因架構，將新基因導入群體中。但是突變次數過多將會導致 GA 變成隨機演算法，會任意破壞原來的結構，造成子代與親代喪失若干相似的特徵；而過少的突變則會造成有用的基因沒被發覺，可能會陷入區域的最佳解。因此 GA 將突變視為是次要的遺傳運算子，以較低的機率來反轉子代的某一個位元 (0 變 1 或 1 變 0)，典型的機率是r m = 0.001，此即每隔 1000 個位元 (或變數) 才反轉一個位元 (變數)。於圖 5 中，假設第 3 個基因 (實數) 是突變點，則突變會將 10.7 變為 13.2。

以下我們挑選三種典型的應用實例來說明 GA 是穩健的、有效率的演化式演算法，對於每一個問題，我們除了說明問題的背景外，並且陳述求解該問題的設計方法，包括：個體表示法、挑選機制、與遺傳運算子，最後討論執行的結果。

雙親 子代 2

演化式計算下篇：基因演算法以及三種應用實例 41

3. 函數的最大化問題

3.1 說明

GA 的第一個應用是求解數學函數的最大化問題，對於簡單的數學函

數，GA 能夠輕易的解出函數的最佳解。我們先以 De

Jong 著名的函數測試平台編號第 2 號的函數 (Goldberg, 1989) 為例說明之，此函數是

(8)

函數的二維空間反向圖形如圖 8 所示，最佳解是 x 1 = x 2 = ?2.048, f (x i ) = 3905.9262。我們設計一個簡單的 GA 程式如下：群體規模為 100，交配率為 0.8，突變率為 0.003，採用單點交配，目標函數就是個體的適應函數，此程式於 3000 世代以前就可以得到最佳解。從圖 8 可看出這個函數的複雜度不高，GA 於演化過程只要朝向較高的適應值的方向，很容易可以找到最佳解。可是有些複雜的數學函數存在著許多局部最佳解，當在廣大的空間找尋時，稍微一不小心很容易陷入區域最佳解而到達不了整體最佳解。然而我們利用 GA 的交配與突變遺傳運算，還是能夠及時跳出區域最佳解而到達整體最佳解，接下來就來討論應用 GA 求解複雜的數學函數的設計方式與設計步驟。

圖 8 De Jong 第 2 號測試函數的二維空間的反向圖形，此函數的最佳解

是 x 1 = x 2 = ?2.048, f (x i ) = 3905.9262。

我們欲求解的數學函數是式子 (9) (Michalewicz, 1992)，此函數對應的三維空間圖形如圖 9 所示。圖 9 顯示的山峰與山谷正是代表這個函數所有可能的解，部分山峰是區域最佳解，山峰所對應的座標就是 x 1 與 x 2 的

2 ,1 ,048.2048.2 ,)1()(100)(212221=≤≤??+?=i x x x x x f i i Max

42 智慧科技與應用統計學報

值，我們所要找尋的最佳解就在最高的山峰。

)π20sin()π4sin(5.21),(Max 221121x x x x x x f ++= (9) 8.54.1 ,1.120.321≤≤≤≤?x x

-50

5-50

5

-10-5

5

10

圖 9 較複雜數學函數會有許多山峰與山谷，有些山峰是區域最佳解。

3.2 設計方法

3.2.1 個體表示法

由於此問題是求解 x 1 與 x 2 的值，因此個體表示法可使用二進位編碼來代表 x 1 與 x 2 的值，此即個體 = (x 1, x 2)。由於 x 1 的範圍是 [?3.0, 12.1]，因此變數 x 1 的長度是 15.1，假設我們希望每一變數的精確度到小數五位，那麼上述範圍應放大為 15.1 × 10,000 = 151,000，由於 18172000,1512≤<，因此需要 18 位元來表示 x 1。同理，x 2 的範圍是 [4.1,

5.8]，長度只有 1.7，由於 15142000,172≤<，需要有 15 位元來表示 x 2。因此，這個問題的個體長度一共是 33 位元。我們舉一例子說明之。假設隨機產生的個體是 (010001001011010000111110010100010)， 前 18 位元的十進位值是70352，而後 15 位元的十進位值是 31906，我們使用下列的公式計算出來所代表的 x 1 與 x 2 的值：

x 1 = ?3.0 + 70352 ×1

21

.1518?= ?3.0 + 4.052426 = 1.052426

x 2 = 4.1 + 31906 ×127.115?= 4.1 + 1.65533 = 5.75533

演化式計算下篇：基因演算法以及三種應用實例43

這個個體的適應值就是目標函數f(1.052426, 5.75533) = 20.25264。另一方面來說，假設已知x1 = ?0.330256，x2 = 4.694977，經上述的範圍放大後，個體會被編碼成

(001011010100001100010110011001100)

其中前 18 位元代表x1而後15 位元是x2。它的適應值是f(?0.330256, 4.694977) = 19.76319。若群體的規模是 100，則此群體共有 100 × 33 = 3,300 位元，最初程式隨機產 100 個個體，就稱為第 0 代。

3.2.2 挑選機制

我們採用的挑選機制是輪盤式選擇，其步驟如下：

第一步：計算每一個體p k的適應值，s k = evaluate(p k)，1 ≤k≤ 100。

第二步：計算群體的總適應值，T = s1 + s2 + … + s100。

第三步：計算每一個體p k 的機率αk= s k / T，1 ≤k≤ 100。

第四步：計算每一個體p k的累積機率βk= α1 + … + αk，1 ≤k≤ 100。

第五步：產生一個 [0, 1] 之間的亂數γ。

第六步：決定輪盤上的區域，挑選的規則是：當γ≤β1則挑選p1，否則若滿足

β k-1< γ≤β k應挑選p k，2 ≤k≤ 100。

3.2.3 遺傳運算子

上述的輪盤式選擇每一次會選出兩個染色體當做雙親，然後進行遺傳運算。由於這個問題的個體表示法是x1與x2兩個變數的二進位編碼，而且問題很單純，因此我們只使用簡單的單點交配，舉一例說明這個做法。例如：選出第 15 與第34 個個體來進行單點交配，而交配點隨機選在第 9 個位置

p15 = (100011000|101101001111000001110010)

p34 = (111011101|101110000100011111011110)

經過單點交配後，產生兩個新子代c1與c2：

c1 = (100011000|101110000100011111011110)

44 智慧科技與應用統計學報

c 2 = (111011101|101101001111000001110010)

此問題的交配率訂為 0.8，那麼有 80% 的個體，或 10 個位元中有 8 個會執行交配工作。當已經產生 100 個新子代 c 1, c 2, … , c 100 後，就開始進行突變。此問題的突變率訂為 0.001，那麼每一世代平均會有3,300 × 0.001 = 3.3個位元會執行突變。例如：第 46個體的第 18 個位元發生突變，將 1 變成 0，產生新個體：

c 46 = (100110110011101101110100000111100)

c 46 = (100110110011101100110100000111100)

程式執行到 800 世代後結束，但是大約在第 621 代，群體已經得到最佳個體 p *，

p * = (111110000000111000111101001010110)

此最佳個體代表 x 1 = 11.631407, x 2 = 5.724824，其適應值為 evaluate(p *) = f (11.631407, 5.724824) = 38.818208。圖 10 是顯示每隔 100 個世代群體所能得到最佳解的曲線，這個曲線呈遞增成長，大約在 621 代，群體已經得到最佳解 p *。

圖 10 求解函數的演化過程，大約 621 代已得到最佳解

4. 破解維瓊內爾密碼 (Breaking Vigen ère Cipher)

4.1 說明

維瓊內爾密碼 (Vigen ère cipher) 是根據法國外交官Blaise de Vigen ère

的名字而命名的，它是一種多套字母密碼法，此即同一個字母會使用不同

0 10

20

30

40

50

100 200 300400500600700800世代 函數最佳值

演化式計算下篇：基因演算法以及三種應用實例 45

套的字母移位加密而得到不同的密文。因此若維瓊內爾密碼的加密鑰匙長度為 d 時，代表會用到 d 套字母密碼，因此每隔 d 個字元會重複使用同一套字母密碼加密 (林豐澤，2001)。表格 1 說明當加密鑰匙為 ABCDE (d = 5) 時，明文 “attack at dawn” 加密後，其中的字母 a 分別被加密為 B 、E 、D 、與 C 四個不同的字母。(註：習慣上，明文使用小寫而密文使用大寫)

表格1 加密鑰匙是 ABCDE 時明文與密文的對照表 鑰匙

A B C D E A B C D E A B C D 明文

a t t a c k a t d a w n 密文 B V W E H L B D X E E C Z R

維瓊內爾密碼有下列幾點特性：

(1) 加密與解密使用相同的鑰匙參數。

(2) 使用多套字母密碼系統，當加密鑰匙的長度為 d 時，同一個字母會被

對應到 d 個其他字母。

(3) 加解密鑰匙的長度愈長，其組合數目會很龐大。例如，d = 5 時，所形

成的空間會超過 7101.1×。當鑰匙的長度和明文的長度幾乎相同時，這就是情報人員常用的一次活頁 (one time pad)。

(4)被猜中的機率低。以加密鑰匙長度為10來看，破解者猜中的機率是

1027

1。如果是一次活頁，以一篇 100 字的文章而言，破密者猜中的機率是 10027

1 = 1433689.11+e ≈ 0，因此即使被破解者猜到時，此明文也過了有效的時限。

4.2 設計方法

破解密碼的基本方式可分為：密文攻擊 (ciphertext-only attack)，已知明文攻擊 (known-plaintext attack) 與選擇文攻擊 (chosen-text attack) 等方法。密文攻擊法是指破解者只截收到密文，欲由密文直接破解得到明文。

46智慧科技與應用統計學報

已知明文攻擊法是破解者已擁有部分明文與部分密文，但對那些明文或密文沒有選擇或控制的能力，僅由現有的資訊來破解密文。至於選擇文攻擊是指破解者對明文或密文有選擇與控制的能力，他可以任意選擇自認為最容易破解的密文或明文而加以攻擊。在這三種方式中，以選擇文攻擊為最具攻擊火力，密文攻擊則是威力最弱的攻擊方式(林豐澤，2001)。理論上而言，威力較大的攻擊方式比較容易破解密碼，相對的，威力較弱者比較不容易破解。我們利用 GA 來破解密碼是屬於威力較弱的密文攻擊法，這代表著 GA 方法具有效力性與穩健性。

4.2.1 個體表示法

破解維瓊內爾密碼就是要找到所使用的加解密鑰匙，因此這個問題的染色體是對加解密鑰匙編碼，個體表示法要使用字串陣列結構。例如：加解密鑰匙是 “MCJOWEDUNP”，則字串陣列是儲存此鑰匙的 ASCII 碼：

[77, 67, 74, 79, 87, 69, 68, 85, 78, 80]

此外要設計一個常用字資料庫，事先建好一些常用的英文單字或是專業用語，這個資料庫是用來決定個體的品質(適應值)。這是因為 GA 利用個體來對密文解碼後，會去找尋此常用字資料庫查看解碼的正確性，資料庫的單字是根據字母次序做排列，所以可以使用二元搜尋法來找尋。

4.2.2 適應函數

適應函數的設計，不但影響到 GA 的執行績效，也關係著破解密碼的正確性，因此適應函數所定義的內涵，代表鑰匙的正確程度，也就是染色體的適應值。假設P = p1, p2, …, p n是明文的字元串，而C = c1, c2, …, c n 是所對應密文的字元串，K = k1, k2, … , k d是鑰匙參數，d是鑰匙的長度。當 GA 從某一代的群體取得一個鑰匙參數(染色體) K，會將C解密成P’，其計算程序是：P’ = D k(C) =p’1, p’2, … , p’n。我們定義一個陣列Match[1..d] 做為鑰匙參數比對成功的計數器，其中Match[i] 是鑰匙參數中第i K與第1+i K個字元成功比對的次數。每一個染色體的適應值的計算方法是：Fitness ＝Fitness + Match[i] × Match[i]，1 ≤i ≤ d。例如：我們先用染色體解出第一和第二字元，並把這兩個字元視為是一個“字彙”，將此字彙和常用資料庫裡面的單字做字串比對 (pattern matching)，找出子

演化式計算下篇：基因演算法以及三種應用實例 47

字串出現的頻率，並給予評分。表格 2 說明了 “PL” 這個字彙的比對過程以及所獲得的分數，此分數經過加總後就是染色體的適應值。

表格 2 子字串 PL 的比對過程 處理過的常用資料庫

A P P L E 分數 第1次比對

P L 0 第2次比對

P L 0 第3次比對

P L 0 第4次比對

P L 1 第5次比對

P L 0 第6次比對 P L 0

4.2.3 挑選機制

我們分別試用輪盤與賽程兩種選擇方式，但是發覺兩者效果的差異不大，因此我們決定使用輪盤式選擇。每個個體被挑選中的機率為 f i ，其中 i f 代表第 i 個染色體的適應值，而 ∑==N

1

N 1i i f f 是群體的平均適應值。

4.2.4 遺傳運算子

我們先設計一組實驗資料，專門測試單點、雙點、與多點交配的收斂情形，實驗的結果顯示：單點交配大約 13 代就會開始收斂，兩點交配大約 59 代，而多點交配大約要到400 代左右。過早的收斂執行速度最快，但是容易陷入區域最佳解，不容易得到真正的最佳解。經過多次實驗，我們發現多點交配的結果對於破解密碼是最好的，這個做法是將雙親染色體的奇數或偶數位元彼此互換，來使得其子代更具多樣性，這對於是否能夠破解維瓊內爾密碼有極關鍵性的影響。圖 11 說明多點交配的做法，為了方便說明，令雙親的染色體分別是 ABCDEFGHIJ 與 0123456789，經過多點交配後，子代分別得到 A1C3E5G6I9 與 0B2D4F6G8J 。而突變的做法是將染色體上的某一個字元做一任意改變，例如：將 ABCDEFGHIJ 變

48 智慧科技與應用統計學報

為 ABCXEFGHIJ ，通常這是一種局部搜尋的效果，但也可藉此來引進新的搜尋資訊。我們採用的交配率是 0.8 而突變率是0.003。

圖 11 多點交配，將雙親染色體的奇數或偶數位元彼此互換

4.3 討論

於演化初期可能會發生誤猜現象，例如：於表格 3 中，假設有 p 1 與 p 2 兩個染色體，p 1 的鑰匙正確度高過於 p 2。然而在初期時，p 2 碰巧將部分的密文解譯為 GOOD ，由於 “GOOD” 是收錄在常用資料庫中的單字，這會使得 p 2 獲得較高的適應值。而 p 1 於初期只有解譯不完整的字彙，只能得到低的適應值。幸虧大部分的誤猜現象到了演化中後期會逐漸消去，只剩下少數誤猜現象會一直存在直到收斂為止。

表格 3 適應函數的誤猜情形 染色體 正確的明文 解密後的片段 適應函數值

A EXAMPLE EMAADLT

25 B EXAMPLE GOODKTD

145

圖 12 是

GA 程式的執行績效與世代中所獲得最佳適應值的關係圖示，其中 X 軸為演化的世代，Y 軸代表獲得最高適應值的百分比。獲得適應值的高低代表得到加解密鑰匙的正確程度。通常在第500 代以後，就會得到

八、九成以上的正確機率。

雙親 子代

《计算工具的演变》教学反思.doc

《计算工具的演变》教学反思 学生拿到计算器都急于“玩一玩”，也急于告诉同伴自己对计算器的一些了解。教材在简单介绍计算器上的“显示器”和“键盘”之后，满足学生的需求，让他们通过玩，初步认识计算器上的一些常用的键。首先是找到开机和关机的键，试一试怎样开机、怎样关机。再摸摸、按按其他的键，并相互交流各人初步知道了哪些键，有什么作用。在这个教学环节里，着重认识0~9共十个数字键，+、-、×、÷四个运算键以及让计算器显示得数的等号键。学生了解这些键的功能后，就可以使用计算器进行计算了。通过“人机大比拼”的游戏，让学生客观的认识到在进行比较复杂的计算时，才使用计算器。 学生拿到计算器都急于“玩一玩”，也急于告诉同伴自己对计算器的一些了解。教材在简单介绍计算器上的“显示器”和“键盘”之后，满足学生的需求，让他们通过玩，初步认识计算器上的一些常用的键。首先是找到开机和关机的键，试一试怎样开机、怎样关机。再摸摸、按按其他的键，并相互交流各人初步知道了哪些键，有什么作用。在这个教学环节里，着重认识0~9共十个数字键，+、-、×、÷四个运算键以及让计算器显示得数的等号键。学生了解这些键的功能后，就可以使用计算器进行计算了。通过“人机大比拼”的游戏，让学生客观的认识到在进行比较复杂的计算时，才使用计算器。

学生拿到计算器都急于“玩一玩”，也急于告诉同伴自己对计算器的一些了解。教材在简单介绍计算器上的“显示器”和“键盘”之后，满足学生的需求，让他们通过玩，初步认识计算器上的一些常用的键。首先是找到开机和关机的键，试一试怎样开机、怎样关机。再摸摸、按按其他的键，并相互交流各人初步知道了哪些键，有什么作用。在这个教学环节里，着重认识0~9共十个数字键，+、-、×、÷四个运算键以及让计算器显示得数的等号键。学生了解这些键的功能后，就可以使用计算器进行计算了。通过“人机大比拼”的游戏，让学生客观的认识到在进行比较复杂的计算时，才使用计算器。 学生拿到计算器都急于“玩一玩”，也急于告诉同伴自己对计算器的一些了解。教材在简单介绍计算器上的“显示器”和“键盘”之后，满足学生的需求，让他们通过玩，初步认识计算器上的一些常用的键。首先是找到开机和关机的键，试一试怎样开机、怎样关机。再摸摸、按按其他的键，并相互交流各人初步知道了哪些键，有什么作用。在这个教学环节里，着重认识0~9共十个数字键，+、-、×、÷四个运算键以及让计算器显示得数的等号键。学生了解这些键的功能后，就可以使用计算器进行计算了。通过“人机大比拼”的游戏，让学生客观的认识到在进行比较复杂的计算时，才使用计算器。 学生拿到计算器都急于“玩一玩”，也急于告诉同伴自己对计算器的一些了解。教材在简单介绍计算器上的“显示器”和

大数据离线计算平台流式Shuffle服务

大数据离线计算平台流式Shuffle服务

?背景 ?架构 ?关键技术?收益与总结?下一步计划

?背景 ?架构 ?关键技术?收益与总结?下一步计划

背景-百度私有云 FPGA GPU 整机柜 Machine Management 环境初始化机器故障自动化 机器自动流转 Container 仲裁器 State Management 调度算法 队列/优先级资源位移 MetaServer NameSpace StateCenter Iterative RealTime Batch NFS Table Ojbect 搜索金融糯米AI 开放云ADU 服务托管研发效率相关工具 预算 交付管理 结算 高精硬件 集群/机器管理 集群操作系统-Matrix 统一资源调度-Normandy 分布式文件系统-AFS 分布式计算 分布式存储 产品生态

背景-百度大数据计算平台 C++ Python Java Simplified Unified API TM DStream DCE (MR/DAG)MPI/E LF Spark Normandy Matrix IDC 计算引擎 资源调度资源管理机器资源 API 层 ……

2014 2007 百度DAG 引擎上线 2006 2004 MapReduce 论文发表 Hadoop 开源 百度MR 上线 基于Hadoop 0.15.1 2011 百度MR 单集群规模超过5000台 2013 百度MR 单集群规模13000台 2015 内存流式Shuffle 上线 2014 百度统一计算表示层发布 背景-百度大数据离线计算平台发展历程

计算工具发展简史

计算工具发展简史 张郭男北大哲学系2010级---1192772452@https://www.wendangku.net/doc/3816764696.html, 从最早有实物见证的计算工具-----算筹，到现在以快速，高效，智能，大容量存储，多媒体再现，网络共享和自动化处理为特点的功能强大的现代计算机的出现，计算工具已由人类手的延伸发展到脑的延伸，人类的信息处理技术发生了质的飞跃，走过了一条不平凡的路。一个个激动人心的里程碑耸立在路旁，标记着当时人们的成就。 最早有实物见证的计算工具是诞生于中国的算筹，根据史书的记载和考古材料的发现，古代的算筹实际上是一根根同样长短和粗细的竹制小棍子，可以看做是它的硬件，而它的摆法便是其软件了。由于它在运算时使用十进位制，又使其成为当时世界上最先进的软件运算系统，这个传统在相当程度上使中国古代的数学水平长期领先于其他民族。后来算盘也被发明，成为西方计算工具传入前中国人计数的主要工具，两千余年的实践中算盘的计算口诀也发展到极成熟的地步，乃至一个熟练的使用算盘的会计有时可以在速度上击败使用计算器的工人，也就是说通过操纵者的熟练可以使运算速度达到惊人的水平。这样的优

势使中国的计算工具长期没有向西方的自动计算的，现代的方向发展，而是近于停滞不前。 而到了1642年，西方在计算工具方面取得了进展，第一台机械计算器-------加法器由19岁的帕斯卡制作成功。加分器是对中国算盘式的主要凭借操纵者素质提高来提高运算速度的计算机模式的一个突破，它第一次确立了计算机器的概念。后来，德国数学家莱布尼兹对加法器加以改良，发明了可以做乘除运算的计算器。人类的计算工具开始趋向于自动化，现代计算机的出现于是具有了可能。但加法器和乘法器的出现只是提供了一种不同于中国算盘的思路，创造出真正意义上的现代计算机还需时日。 下一个在人类计算工具发展历史上留下痕迹的，是巴贝奇设计的差分机。1822年差分机的模型出现，"这台机器不论在可能完成的计算范围、简便程度以及可靠性与精确度方面，或者是计算时完全不用人参与这方面，都超过了以前的机器。"这句话道出了差分机的先进性。它第一次引进了程序控制的思想，“它能够按照设计者的旨意，自动处理不同函数的计算过程”，这是个了不起的进步。1834年，野心勃勃的巴贝奇在1822年的基础上进行了大的改进，并取名为分析机。由于当时的技术水平限制，分析机仅仅停

TRIZ理论八大技术系统进化法则

机械创新设计课程论文(TIZE理论的八大技术系统进化法则) 专业机械设计制造及其自动化 班级10机自职1 学号1010113126 姓名姚巧珍 成绩 教师刘小鹏 2013年5月23日

TRIZ理论的八大技术系统进化法则 姚巧珍 （10机自职1班，学号：1010113126） [摘要] 技术系统的这八大进化法则可以应用于产生市场需求、定性技术预测、产生新技术、专利布局和选择企业战略制定的时机等。它可以用来解决难题，预测技术系统，产生并加强创造性问题的解决工具。本文讲述了TRIZ理论的八大技术系统进化法则，这些技术系统进化法则基本涵盖了各种产品核心技术的进化规律，每条法则又包含多种具体的进化路线和模式。它可以帮助设计者在方案设计阶段迅速地产生个具有创造性的新概念，实现产品的快速创新。 [关键词] 技术系统，进化法则，子系统，S曲线。 引言 一个产品或物体都可以看做是一个技术系统，技术系统可以简称为系统。系统是由多个子系统组成的，并通过子系统间的相互作用来实现一定的功能，子系统可以是零件或部件甚至于构成元素。系统是处于超系统之中的，超系统是系统所在的环境，环境中的其他相关的系统可以看做是超系统的构成部分。技术系统的进化是指实现系统功能的技术从低级向高级变化的过程，进化是客观进行着的，不管人们是认识了它还是没有认识它。如果认识和掌握了系统的进化规律，有利于设计者开发出更先进的产品，从而提升产品的竞争力。 1.八大技术系统进化法则 TRIZ的技术系统八大进化法则分别是：1）技术系统的S曲线进化法则； 2）提高理想度法则； 3）子系统的不均衡进化法则； 4）动态性和可控性进化法则；5）增加集成度再进行简化法则； 6）子系统协调性进化法则； 7）向微观级和场的应用进化法则； 8）减少人工进入的进化法则 1.1技术系统的S曲线进化法则 图1-1是一条典型的S曲线。S曲线描述了一个技术系统的完整生命周期，图中的横轴代表时间；纵轴代表技术系统的某个重要的性能参数，比如飞机这个技术系统，飞行速度、可靠性就是其重要性能参数，性能参数随时间的延续呈现S形曲线。 一个技术系统的进化一般经历4个阶段，分别是： 1）婴儿期 2）成长期 3）成熟期 4）衰退

01_TRIZ的技术系统八大进化法则

（一）TRIZ的技术系统八大进化法则 阿奇舒勒的技术系统进化论可以与自然科学中的达尔文生物进化论和斯宾塞的社会达尔文主义齐肩，被称为“三大进化论”。TRIZ的技术系统八大进化法则分别是：1、技术系统的S曲线进化法则；2、提高理想度法则；3、子系统的不均衡进化法则；4、动态性和可控性进化法则；5、增加集成度再进行简化法则；6、子系统协调性进化法则；7、向微观级和场的应用进化法则；8、减少人工进入的进化法则。技术系统的这八大进化法则可以应用于产生市场需求、定性技术预测、产生新技术、专利布局和选择企业战略制定的时机等。它可以用来解决难题，预测技术系统，产生并加强创造性问题的解决工具。 八大技术系统进化法则 1.技术系统的S曲线进化法则 1）婴儿期2）成长期3）成熟期4）衰退期

各阶段的特点。 S曲线族 2.提高理想度法则 1）一个系统在实现功能的同时，必然有2个方面的作用：有用功能和有害功能； 2）理想度是指有用作用和有害作用的比值 3）系统改进的一般方向是最大化理想度比值 4）在建立和选择发明解法的同时，需要努力提升理想度水平 提高理想度可以从以下4个方向予以考虑： 1）增加系统的功能2）传输尽可能多的功能到工作元件上3）将一些系统功能转移到超系统和外部环境中4）利用内部或外部已经存在的可利用资源。 3.子系统的不均衡进化法则

1）每个子系统都是沿着自己的S曲线进化的 2）不同的子系统将依据自己的时间进度进化 3）不同的子系统在不同的时间点到达自己的极限，这将导致子系统间矛盾的出现 4）系统中最先到达其极限的子系统将抑制整个系统的进化，系统的进化水平取决于此系统 5）需要考虑系统的持续改进来消除矛盾 4.动态性和可控性进化法则 1)增加系统的动态性,以更大的柔性和可移动性来获得功能的实现 2)增加系统的动态性要求增加可控性 5.增加集成度再进行简化法则 1.增加集成度的路径 2简化路径 3单--双---多--路径 4子系统分离路径 6.子系统协调性进化法则 1.匹配和不匹配元件的路径 2调节的匹配和不匹配的路径 3工具和工件匹配的路径 4匹配制造工程中加工动作节拍的路径 7.向微观级和场的应用进化法则 1.向微观级转化的路径 2转化到高效场的路径 3增加场效率的路径 4分割的路径 8.减少人工介入的进化法则 （1）减少人工介入的一般路径 本路径的技术进化阶段：包括人工动作的系统→替代人工但仍保留人工动作的方法→用机器动作完全代替人工。

数学竞赛专题讲座七年级第讲计算工具与算法的变迁含答案

第五讲 计算——工具与算法的变迁 研究数学、学习数学总离不开计算，随着时代的变迁，计算工具在不断地改变，从中国古老的算盘、 纸笔运算发展到利用计算器、计算机运算． 初中代数中运算贯穿于始终，运算能力是运算技能与逻辑能力的结合，它体现在对算理算律的理解与使用，综合运算的能力及选择简捷合理的运算路径上，这要求我们要善于观察问题的结构特点，灵活选用算法和技巧，有理数的计算常用的方法与技巧有： 1．巧用运算律； 2．用字母代数； 3．分解相约； 4．裂项相消； 5．利用公式； 6．加强估算等． “当今科学活动可以分成理论、实验和计算三大类，科学计算已经与理论研究、科学实验一起，成为第三种科学方法．——威尔逊 注：威尔逊，著名计算物理学家，20世纪80年代诺贝尔奖获得者． 【例1】 现有四个有理数3，4，6-，l0，将这4个数(每个数用且只用一次)进行加、减、乘、除四则运算，使其结果等于24，其三种本质不同的运算式有： (1) ；(2) ；(3) ． (浙江省杭州市中考题) 思路点拨 从24最简单的不同表达式人手，逆推，拼凑． 链接： 今天，计算机泛应用于社会生活各个方面，计算机技术在数学上的应用，不但使许多繁难计算 变得简单程序化，而且还日益改变着我们的观念与思维． 著名的计算机专家沃斯说过：“程序=算法十数据结构”． 有理数的计算与算术的计算有很大的不同，主要体现在： (1)有理数的计算每一步要确定符号； （2）有理数计算常常是符号演算； (3)运算的观念得以改变，如两个有理数相加，其和不一定大于任一加数；两个有理数相减，其差不一定小于被减数． 程序框图是一种用规定、指向线及文字说明来准确、直观地表示算法的图形，能清晰地展现算法的逻辑结构，常见的逻辑结构有：顺序结构、条件结构和循环结构． 【例2】 如果4个不同的正整数q p n m 、、、满足4)7)(7)(7)(7(=----q p n m ，那么，q p n m +++等于( )． A ．10 B ．2l C ．24 D ．26 E ．28 (新加坡数学竞赛题) 思路点拨 解题的关键是把4表示成4个不同整数的形式． 【例3】 计算： (1)100 321132112111+++++++++++ ； (“祖冲之杯”邀请赛试题) (2)19492 —19502 +19512 —19522 +…+19972 —19982 +19992 (北京市竞赛题) (3)5+52+53+…十52002 ． 思路点拨 对于(1)，首先计算每个分母值，则易掩盖问题的实质，不妨先从考察一般情形人手；(2)式使人易联想到平方差公式，对于(3)，由于相邻的后一项与前一项的比都是5，可从用字母表示和式着手．

进化计算综述

进化计算综述 1.什么是进化计算 在计算机科学领域，进化计算（Evolutionary Computation）是人工智能（Artificial Intelligence），进一步说是智能计算（Computational Intelligence）中涉及到组合优化问题的一个子域。其算法是受生物进化过程中“优胜劣汰”的自然选择机制和遗传信息的传递规律的影响，通过程序迭代模拟这一过程，把要解决的问题看作环境，在一些可能的解组成的种群中，通过自然演化寻求最优解。 2.进化计算的起源 运用达尔文理论解决问题的思想起源于20世纪50年代。 20世纪60年代，这一想法在三个地方分别被发展起来。美国的Lawrence J. Fogel提出了进化编程（Evolutionary programming），而来自美国Michigan 大学的John Henry Holland则借鉴了达尔文的生物进化论和孟德尔的遗传定律的基本思想，并将其进行提取、简化与抽象提出了遗传算法（Genetic algorithms）。在德国，Ingo Rechenberg 和Hans-Paul Schwefel提出了进化策略（Evolution strategies）。 这些理论大约独自发展了15年。在80年代之前，并没有引起人们太大的关注，因为它本身还不够成熟，而且受到了当时计算机容量小、运算速度慢的限制，并没有发展出实际的应用成果。

到了20世纪90年代初，遗传编程（Genetic programming）这一分支也被提出，进化计算作为一个学科开始正式出现。四个分支交流频繁，取长补短，并融合出了新的进化算法，促进了进化计算的巨大发展。 Nils Aall Barricelli在20世纪六十年代开始进行用进化算法和人工生命模拟进化的工作。Alex Fraser发表的一系列关于模拟人工选择的论文大大发展了这一工作。 [1]Ingo Rechenberg在上世纪60 年代和70 年代初用进化策略来解决复杂的工程问题的工作使人工进化成为广泛认可的优化方法。[2]特别是John Holland的作品让遗传算法变得流行起来。[3]随着学术研究兴趣的增长，计算机能力的急剧增加使包括自动演化的计算机程序等实际的应用程序成为现实。[4]比起人类设计的软件，进化算法可以更有效地解决多维的问题，优化系统的设计。[5] 3.进化计算的分支 进化计算的主要分支有：遗传算法GA ，遗传编程GP、进化策略ES、进化编程EP。下面将对这4个分支依次做简要的介绍。 1遗传算法（Genetic Algorithms）： 遗传算法是一类通过模拟生物界自然选择和自然遗传机制的随机化搜索算法，由美国John HenryHoland教授于1975年在他的专著《Adaptation in Natural and Artificial Systems》中首次提出。[6]它是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的种群的进化过程，通过有组织地然而是随机地信息交换来重新组合那些适应性好的串。遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染

TRIZ技术进化理论的应用研究

TRIZ技术进化理论的应用研究 TRIZ理论认为发明创造是有规律可循的，在大量发明创造背后隐藏着客观的基本规律。产品技术成熟与否、技术发展未来走势和进化路线是可以根据TRIZ理论提出的方法进行预测分析的。TRIZ技术进化理论就是专门研究技术系统进化预测的重要分支。 技术系统进化理论 在技术系统向新的技术系统进化过程中，必然遵循一定的规律，这些规律就是技术系统进化理论。TRIZ理论核心内容之一就是技术系统进化理论。它可以根据技术系统进化规律预测其未来发展趋势，帮助企业开发有竞争力的产品。技术系统进化理论基本涵盖了各种产品核心技术进化规律，每条规律又包含了不同数目的具体进化模式和路线。目前，已经发现的产品进化路线已有300多条，典型进化路线有20余条。这些进化路线对于研究产品创新设计具有重要意义。 在经典TRIZ中，有八大类的技术系统进化法则：1.技术系统完备性法则；2.技术系统能量传递法则；3.技术系统动态性进化法则；4.技术系统提高理想度法则；5.技术系统子系统不均衡进化法则；6.技术系统向超系统进化法则；7.技术系统向微观级进化法则；8.系统协调性进化法则。

运用这些法则，我们能够判断当前研发的产品处于技术系统进化模式中的哪个位置，然后根据法则的提示能够预测技术系统未来发展的方向。系统进化模式可以在过去的专利发明中发现，所有系统都是向理想化最终结果方向进化的，并且用来指导新产品开发，避免盲目尝试和浪费时间。当然，与TRIZ中的其他内容相比，技术系统进化理论不算是非常成熟的理论，还有许多值得进一步研究和发展的地方。 进化模式与进化路线 技术系统的进化路线是指一个系统从结构进化的特点 描述产品核心技术所处的状态序列，每一种进化模式都包括多种进化路线。进化路线的实质是从产品一种核心技术转移到另一种核心技术，产品沿进化路线进化的过程是新旧核心技术交替的过程。产品进化过程实质上是产品结构的进化过程，因此，TRIZ理论中进化理论是预测产品结构的进化理论。技术进化的一般趋势由理想化进化模式，即增加系统的理想化水平决定的；而增加系统的理想化水平通常是通过增加系统的动态性（柔性化）、维数变化（多维化）和向超系统进化（集成化）等进化模式来完成，进化模式层次如图1所示。 应用案例 目前，在公共场所、景区及社区，车挤绿地、停车难等问题已越来越突出。为了解决停车车位占地面积与住户商用

大数据计算技术-U5_汤羽

05分布式存储架构 5.1 HDFS分布式文件系统 5.2HBase存储架构 5.3 二次索引表机制

数据存储系统 包括数据采集层（系统日志、网络爬虫、无线传感器网络、物联网、以及各种数据源）；数据清洗、抽取与建模（将各种类型的结构化、非结构化、异构数据转化为标准存储格式数据，并定义数据属性及值域）；数据存储架构（集中式/分布式文件系统、关系型数据库/分布式数据库、行存储数据结构/列存储数据结构，键值对结构，哈希表（Hash Table ）检索）；数据统一接口等。 数据采集与建模 分布式文件系统数据存储系统 分布式数据库/数据仓库

数据存储架构 在存储结构中：数据库提供了数据的逻辑存储结构；分布式文件系统提供了数据的物理存储结构。 Data Acquisition / Extraction / Transforming / Modeling Distributed File Systems (HDFS / GFS / Colossus) NoSQL Database (HBase / BigTable / MongoDB / Neo4j) Unified Data Access Interface

逻辑存储结构Logic Storage Structure 也称为数据的逻辑结构。数据存储的逻辑模型（抽象模型），即纸面上人们设计的存储模式或数据结构，比如矩阵（matrix）、树（tree）、数据库表单（form）等。主要用于表达数据属性及数据元素相互间的关联关系。

物理存储结构Physical Storage Structure 也称为数据的存储结构。数据存储的物理模型，即在物理存储介质（如磁盘）上数据实际的排列方式。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。 1)顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，元素之间的关系由存储单元的邻接关系来体现。 2)链接存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系。 3)索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址）。 4)散列存储：根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。

进化计算 复习题及部分参考答案

进化计算复习总结 一、选择填空 1.生命的共同特性是_D_____；__C____保证正熵世界中任何生命能延续；有限区域不断膨胀的种群中__B____和_A_____是不可避免的。 A.选择 B.竞争 C.变异 D.繁殖 D,C,B和A教材p4 2.__D____使复杂生命系统更为复杂。 A.非线性 B.多变量 C.环境多变 D.进化 D 3.生物独立进化中某些明显相同的功能对应的__A____结构却是_D_____的，如从软体、节肢到脊椎动物的视觉凝视机制。 A.底层基因 B.表现型 C.多变 D.各种各样 A、D https://www.wendangku.net/doc/3816764696.html,marck认为环境引起有神经系统动物变异的过程是___D___。 A.机能→需要→习性→环境→形态构造 B.需要→习性→环境→形态构造→机能 C.习性→需要→环境→机能→形态构造 D.环境→需要→习性→机能→形态构造 D教材p2 5.Medel定律表明：有深层次的__遗传因子____控制着遗传过程。 [遗传因子/基因] 教材p3 6.Weismann用连续切割鼠尾的实验明确否定了__D____的观点。 A.演变和进化是缓慢而连续的 B.演变和进化是连续有突变 C.用进废退 D.获得性遗传 D教材p3 7.Morgen果蝇实验研究了遗传性状的变化与_B_____之间的关系。 A.基因 B.染色体 C.细胞 D.核糖核酸 B教材p3 8.生物体外在表现特征是__D____构成的体现。生物进化本质体现在_A_____的改进上。 A.基因 B.细胞 C.核糖核酸 D.染色体 D教材p3 9.____C__的特异性决定生物多样性，____B__的稳定性保证物种稳定性，____D__的改变决定生物体的变异。 A.基因的杂交和变异 B.基因结构 C.基因组合 D.遗传信息 C,B,D教材p3 10.现代进化论中进化机制本质上是鲁棒的___C___和___B___过程 A.选择 B.优化 C.搜索 D.繁殖 C,B教材p3

大数据计算

李建中：大数据计算基本概念研究问题及部分解 作者：机房360出处：论坛2012-11-30 22:14 2012.11.30Hadoop与大数据技术大会(下午) 2012.11.30Hadoop与大数据技术大会(下午) 主持人：各位领导各位来宾下午好!欢迎大家参加Hadoop与大数据技术大会。我是本次大会的程序委员会主席之一，CSDN程序员杂志的主编刘江。首先我介绍一下这次大会是由中国计算机学会主办的、CCF专业委员会承办的大会。除了今天的全体会议之外，明天还有四个分论坛，希望大家不要错过。我们还有官方微博，如果有相关大方的发布信息可以从这里获取。另外微博评论注意加HBTC四个字母。 今天下午有来自各机构、公司的专家来分享技术。首先有请中国计算机学会大数据专家委员会副主席哈尔滨工业大学教授李建中老师为我们演讲，《大数据计算基本概念研究问题和部分解》。 李建中：非常高兴有机会和大家交流一下对大数据的理解。HIT是哈尔滨工业大学的缩写，所以我的理解可能和工业界有一点点的不同，请看一下我们学院式的对大数据的研究有什么样的看法。我讲三个问题： 第一，大数据的基本概念。 第二，大数据计算机其挑战。 第三，研究问题与部分解。 第一，大数据的基本概念。什么是大数据，实际上我的报告讲了很多了，为什么叫做描述?因为大数据实际上是结合了不可定义的概念，大是相对的，是相对目前的及拴系统计算能力来说的，今天的大数据明天就不是大数据，大数据有的人说三个V，有的人说四个V，V我也不详细说了。所以说，大数据存在已久。有一个会议叫SSDB是1983年创建的一个会议，这里面的论文就是在研究大数据，这个会议到现在已经有29年的历史了，现在为什么谈起来大数据呢?因为个时候大数据还没有那么普遍，涉及的领域很少，参加这方面研究的人也很有限，所以跟现在不同。现在的大数据和当时研究的不同主要有两点。

计算工具的发展史

计算工具的发展史 现在人们常用计算器来计算，既快捷，又精准，给人们的生活、工作带来了方便。但是计算机的发展经历了漫长的过程，凝聚着劳动人民的智慧。 我国春秋时期出现的算筹是世界上最古老的计算工具。计算的时候摆成纵式和横式两种数字，按照纵式相间的原则表示任何自然数，从而进行加、减、乘、除、开放以及其它的代数计算。负数出现后，算筹分为红和两种，红筹表示正数，黑筹表示负数。这种运算工具和运算方法是当时世界上独一无二的。后来我国劳动人民创造了算盘作为运算工具。早在公元15世纪，算盘已经在我国广泛使用，后来流传到日本、朝鲜等国。它的特点是结构简单，使用方便，特别实用，它计算数目较大的和数目较多的加减法，更为简便。算盘已经基本具备了现代计算器的主要结构特征。例如，拨动算珠，也就是向算盘输入数据，这时算盘起着“储存器”的作用；运算时，珠算口诀起着“运算指令”的作用，而算盘则起着“运算器”的作用。当然，算珠毕竟要靠人的手来拨动，而且也根本谈不上“自动运算”。 除中国外，其它中古的国家亦有各式各样的计算工具发明，例如罗马人的「算盘」，古希腊人的「算板」，印度人的「沙盘」，及英国人的「刻齿本片」等。这些计算工具的原理基本上是相同的，同样是透过某种具体的物体来代表数，并利用对物件的机械操作来进行运算。 比例规：伽利略发明了「比例规」，它的外形像圆规，两脚上各有刻度，可任意开合，是利用比例的原理进行乘除比例等计算的工具。 纳皮尔筹：15世纪后，「格子算法」通行于中亚细亚及欧洲，纳皮尔筹便是根据了「格子算法」的原理，但与格子算法不同的是它把格子和数字刻在「筹」﹝长条竹片或木片﹞上，这便可根据需要拼凑起来计算。 计算尺：在1614年，对数被发明以后，乘除运算可以化为加减运算，对数计算尺便是依据这一特点来设计。1620年，E?冈特最先利用对数计算尺来计算乘除。1632年，奥特雷德发明了有滑尺的计算尺，并制成了圆形计算尺。1652年，R?比萨克制成了有固定尺身和滑尺的计算尺。1850年，V?曼南在计算尺上装上游标，因此而受到当时科学工作者，特别是工程技术人员所广泛采用。 机械计算机：机械式计算机是与计算尺同时出现的，是计算工具上的一大发明。席卡德﹝1623﹞是最早构思出机械式计算机，他在给天文学家J?开普勒的信﹝1623，1624﹞上描述了他发明的四则计算机，但并没有成功制成。而能成功创制第一部能计算加减法的计算机是B?帕斯卡﹝1642﹞，在1671年，G?W?莱布尼茨发明了一种能作四则运算的手摇计算机，是长1米的大盒子。自此以后，经过人们在这方面多年的研究，特别是经过L?H?托马斯，W?奥德内尔等人的改良后，出现了多种多样的手摇计算机，并风行全世界。于17世纪末，这种计算机传入了中国，并由中国人制造了12位数的手摇计算机，独创出一种算筹式手摇计算机。 电子计算机：一种能依照一定的「程序」自动控制的计算机。19世纪初，法国的J?M?雅卡尔发明了用穿孔卡片来控制的纺织机，1822年，英国的C?巴贝奇便根据同一原理制成了一部能执行计算程序的差分机，并于1834年，设计了一部完全程序控制的分析机，可惜碍于当时的机械技术所限制而没有制成，但已包含了现代计算的基本思想和主要的组成部分了。 此后，由于电力技术有了很大的发展，电动式计算机便慢慢取代以人工为动

进化计算

进化优化研究领域 由于优化在工程应用问题的广泛存在，数学家和计算领域的专家已经投入了巨大的精力并取得了一系列有意义的研究成果。 ★广义上来说，这些优化算法可以分为两类：精确和随机算法。精确算法包括分支限界算法和动态规划算法等等。但是，当出现问题的规模上升到一定的程度、先验知识较少或者问题的复杂性较高的情况时，这些算法的性能会急剧下降，甚至出现失效的情况。特别地，对于NP完全或者NP难问题的解决上，精确算法的应用非常有限。 ★随机算法中的进化算法（Evolutionary Algorithm）是一类算法框架灵感来源于自然的算法。相比于精确算法，进化算法具有以下特性：（1）无需先验过多问题先验知识；（2）对于问题是否线性可微、可导和连续没有要求；（2）自动采取设定机制对抗各种约束条件；（3）优化性能优秀。因此进化优化领域研究已经成为了国内外研究的热点。 ★实验室工作主要包括：（1）面向大规模优化应用的进化计算研究；（2）进化算法应用于电力系统经济负载调配应用；（3）应用于数字IIR滤波器涉及的进化计算研究；（4）最优化软硬件协同设计研究。 进化算法能够做什么？ 图 设计一个有鲁棒性的算法可以在未知高维空间中寻找出最小值。

应用领域： 面向大规模优化的进化计算研究 在生产实践与科学研究中，存在许多大规模优化问题。例如，大规模电网配置与调度[1]、移动通信网络设计、生物医学信息处理、以及数据挖掘等等。这些问题的共同特点是决策空间维数很高，一般在102～104量级。维数的增高在导致决策空间急剧增大的同时，也会造成问题求解难度的迅速增大。例如，有些优化问题的局部最优的个数会随着维数增加呈指数

TRIZ理论——八大进化法则

阿奇舒勒于1946年开始创立TRIZ理论，其中重要的之一是系统进化论。阿奇舒勒技术系统进化论的主要观点是技术系统的进化并非随机的，而是遵循着一定的客观的进化模式，所有的系统都是向“最终理想化”进化的，系统进化的模式可以在过去的专利发明中发现，并可以应用于新系统的开发，从而避免盲目的尝试和浪费时间。 阿奇舒勒的技术系统进化论主要有八大进化法则，这些法则可以用来解决难题，预测技术系统，产生并加强创造性问题的解决工具。这八大法则是： 1）技术系统的S曲线进化法则； 2）提高理想度法则； 3）子系统的不均衡进化法则； 4）动态性和可控性进化法则； 5）增强集成度再进行简化的法则； 6）子系统协调性计划法则； 7）向微观级和增加场应用的进化法则； 8）减少人工介入的进化法则。 下面，就详细解释阿奇舒勒的技术系统这八大进化法则。 2.2八大技术系统进化法则 2.2.1 技术系统的S曲线进化法则 阿奇舒勒通过对大量的发明专利的分析，发现产品的进化规律满足一条S形的曲线。产品的进化过程是依靠设计者来推进的，如果没有引进新的技术，它将停留在当前的技术水平上，而新技术的引入将推动产品的进化。 S曲线也可以认为是一条产品技术成熟度预测曲线。 图2-1是一条典型的S曲线。S曲线描述了一个技术系统的完整生命周期，图中的横轴代表时间；纵轴代表技术系统的某个重要的性能参数（39个工程参数），比如飞机这个技术系统，飞行速度、可靠性就是其中重要性能参数，性能参数随时间的延续呈现S形曲线。 一个技术系统的进化一般经历4个阶段，分别是： 1）婴儿期 2）成长期 3）成熟期 4）衰退期 每个阶段都会呈现不同的特点。

服务计算与大数据

1.(1)什么是SOA？SOA有什么特点?请例举几种SOA的实例； (2)什么是Web Service？简要说明Web Services中Service的含义。 答：（1）SOA的定义:SOA(service-oriented architecture)被设计为提供这样的灵活性：将业务过程以及下层的IT基础设施作为一个安全的、标准化的组件（即服务）,这些组件可以通过被重用的方式来适应不断变化的业务优先级。 SOA的特点有： 1)服务是自包含和模块化的 2)服务支持互操作 3)服务是松耦合的 4)服务是位置透明的 5)服务是由构件组成的合成模块 SOA的实例： CORBA（Common Object Request Broker Architecture,公共对象请求代理体系结构） DCOM（Distributed Component Object Model分布式组件对象模型）J2EE WWW (2）Web Service是一种用URI标识的软件应用，它的接口和绑定可以通过XML 文档定义、描述和发现。Web Service支持通过基于Internet的协议、并利用基于XML的信息与其他软件进行直接的交互。 Service的含义：应用程序或者业务的不同功能单元，这些功能单元作为一个独立的实例存在，并且通过松耦合、基于消息的通信模式和其他应用程序或者服务进行交互。 2.(1)请给出Web Services的体系结构图（包含角色和行为的三角图），并简述各角色和行为的含义。 (2)下图是Web Services的协议栈，将其补充完整；并简述栈中每一层的作用。 （1）

角色： 服务需求者（service requester）：一个应用程序、软件模块或者需要服务的另一个服务。 服务提供者（service provider）：接受和执行服务使用者的请求的可寻址的网络实体。 服务中介（service broker）：包含一个可用服务库并且为感兴趣的服务使用者提供服务提供者接口的查找。 Publish发布:一个服务的描述只有被发布，该服务才可以被服务请求者发现和调用。使用的协议是WSDL。 Search查找:服务请求者通过向服务注册中心查询来定位符合自己要求的服务。使用的协议是UDDI。 Bind Invoke绑定和调用:服务请求者根据服务注册中心提供的服务描述信息来调用服务。使用的协议是SOAP。 (2) Web Service协议栈中各层的作用： Discovery：服务发现层:服务请求者查询可以调用的服务。 Composition：服务组合层:组合Web服务，从而可以形成新的Web服务。Service Description：服务描述层:为调用服务提供了具体的方法。包含服务的接口和实现细节。 XML Messaging：XML信息层:用于调用服务时传送信息。 Network：网络传输层:采用广泛使用的协议传输消息，并且能够顺利通过代理防火墙。 3.(1)什么是WSDL？WSDL定义了service的哪些个方面？分别对应于WSDL中的哪些元素？WSDL文档被分为哪两种类型？ (2)请说明binding元素与portType之间的关系，为什么说 “Binding element is generic”？ （1）WSDL一种用来定义网络服务的XML格式，该XML格式将网络服务定义为一组在信息的层次上操作的终端节点，这些信息包含基于文档的信息和基于过程的信息。 WSDL定义了Service的以下三个方面： a.服务是什么（服务接口）。对应着portType与message和type元素。 b.访问规格（怎样使用服务）。对应着binding元素。

TRIZ理论技术系统进化法则

3.5 基于技术系统进化法则的方案设计 技术系统进化论的主要观点是技术系统的进化并非随机的，而是遵循着一定的客观的进化模式，所有的系统都是向“最终理想化”进化的，系统进化的模式可以在过去的专利发明中发现，并可以应用于新系统的开发。 3.5.1汽车车架的进化路线描述 TRIZ中子系统协调性进化法则指出：在技术系统的进化中，子系统的匹配和不匹配交替出现，以改善性能或补偿不理想的作用。也就是说技术系统的进化是沿着各个子系统相互之间更协调的方向发展。即系统的各个部件在保持协调的前提下，充分发挥各自的功能。如图3.19所示。对车架增加保险杠，提高汽车的防撞性能，提高安全性。 图3.19 车架进化路线 这次进化的地方是将原来的最容易发生碰撞的前端增加了保险杠，从而使得汽车的防撞性能得到改善。 3.5.2汽车控制系统的进化路线描述 TRIZ指出技术系统的动态性进化应沿着增加结构柔性、可移动性、可控性的方向发展，以适应环境状况或执行方式的变化。 本文选择动态性的增加可控性进化路线：无控制→直接控制→反馈控制→自我调节，即引入某种部件，即增加防抱死系统，具体方案如图3.20所示。

图3.20 控制系统进化路线 防抱死制动系统ABS全称是Anti-lock Braking System，即ABS，可安装在任何带液压刹车的汽车上。它是利用阀体内的一个橡胶气囊，在踩下刹车时，给予刹车油压力，充斥到ABS的阀体中，此时气囊利用中间的空气隔层将压力返回，使车轮避过锁死点。 ABS（Anti-lock Braking System）防抱死制动系统，通过安装在车轮上的传感器发出车轮将被抱死的信号，控制器指令调节器降低该车轮制动缸的油压，减小制动力矩，经一定时间后，再恢复原有的油压，不断的这样循环（每秒可达5~10次），始终使车轮处于转动状态而又有最大的制动力矩。、 在制动时，ABS根据每个车轮速度传感器传来的速度信号，可迅速判断处车轮的抱死状态，关闭开始抱死车轮上面的常开输入电磁阀，让制动力不变，如果车轮继续抱死，则打开常闭输出电磁阀，这个车轮上的制动压力由于出现直通制动液贮油箱的管路而迅速下移，防止了因制动力过大而将车轮完全抱死。在此同时，主控制阀通电开启，动态压力的制动液可进入制动阀，动态压力的制动液从动态助力管路通过主控制阀、制动总泵密封垫外缘到达前轮输入管路如此反复地工作（工作频率3－12次/秒），让制动状态始终处于最佳点（滑移率S为20%），制动效果达到最好，行车最安全。 在制动总泵前面腔内地制动液是动态压力制动液，它推动反应套筒向右移动，反应套筒又推动助力活塞从而使制动踏板推杆向右移。因此，在ABS工作地时候，驾驶员可以感觉到脚上踏板地颤动，听到一些噪音。 汽车减速后，一旦ABS电脑检测到车轮抱死状态消失，它就会让主控制阀关闭，从而使系统转入普通地制动状态下进行工作。如果蓄压器地压力下降到安全极限以下，红色制动故障指示灯和琥珀色ABS故障指示灯亮。在这种情况下，驾驶员要用较大地力进行深踩踏板地制动地方式才能对前后轮进行有效地制动。

云计算与大数据技术课后习题

第一章云计算与大数据基础 1.在信息产业的发展历程中。硬件驱动力，网络驱动力，作为两个重要的内在动力在不同的时期起着重要的作用 6．MapReduce思想来源LISP语言 7.按照资源封装层次，云计算分为 Iaas paas saas三种 8. 教材P2 1.1.2 10. 教材P8 1.2.2 11. 教材P10 1.2.3 第二章云计算与大数据相关技术 1.一致性hash算法原理： 哈希算法是一种从稀疏值到紧密值范围的映射方法，在存储和计算定位时可以被看做是一种路由算法。通过这种路与哦算法文件块能被唯一的定位到一个节点的位置。传统的hash 算法容错性和扩展性都不好，无法有效的适应面向数据系统节点的动态变化。意思就是当集群需要增加节点，传统的hash算法不容易检测到新增加的节点，此为扩展性不好，而一致性hash算法增加一个节点只会影响增加的这个节点到前一个节点之间的数据。容错性就是如果不幸一个机器C宕机了,那么机器B和C之间的数据都会被D执行，那么受影响的数据只是机器B和C之间的数据。当然，容错性和扩展性对于节点数较多的集群是比较有意义的，对于节点较少的集群似乎这两个特性并没有什么诱惑力。 一致性hash的实际目的就是解决节点频繁变化时的任务分配问题，一致性hash将整个hash值空间组织成一个虚拟圆环，我们这里假设某hash函数H值空间为0~(2^32-1),即32位无符号整形。下面简述一下一致性hash的原理： 这是一致性hash的整个值空间0~(2^32-1)

下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，假设使用四台机器进行hash： 将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。 例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下： 根据一致性哈希算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上 下面我们看看当集群机器比较少的情况 例如系统中只有两台服务器，其环分布如下，

技术系统进化法则培训讲义

TRIZ培训讲义
技术系统进化法则
技术系统进化法则
DAOV路线图—优化阶段
定义 Define 分析 Analyze 优化 Optimize 验证 Verify
1.概念列表
2.方案选择
S曲线 进化法则 进化树 列出概念方案 风险分析
决策分析 Pro/Innovator 评价模块
A Pera Global Company ? 2011 IWINT,INC
进化法则的作用和意义
对于新产品的预测分析给予建议 对于现有产品的改进方向给予建议 作为产品专利规避的有效工具
A Pera Global Company ? 2011 IWINT,INC
第 1 页
IWINT

TRIZ培训讲义
技术系统进化法则
主题大纲
进化规律简介 技术系统进化法则 Pro/E软件简介 产品预测的步骤和案例 小结
A Pera Global Company ? 2011 IWINT,INC
TRIZ的核心思想之一
技术系统的进化和发展并不是随机的，而是遵循 着一定的客观规律
A Pera Global Company ? 2011 IWINT,INC
TRIZ体系——创新的规律
算法
S曲线
完备性法则 能量传递法则 协调性法则 动态性法则 子系统不均衡进化 向超系统进化
创新的思维 创新的方法
工具 工具
创新的规律
向微观级进化 提高理想度法则
……
正确预测 产品未来！
术语
A Pera Global Company ? 2011 IWINT,INC
第 2 页
IWINT