基本介紹
- 中文名：桶隊算法
- 外文名：bucket brigade algorithm
- 提出者：Holland
定義,人工智慧,遺傳算法,套用實例,
定義
桶隊算法（bucket brigade algorithm是由Holland（1986）提出的，主要是為了解決訊息傳遞，基於規則的分類器系統問題。以人工 智慧型和遺傳算法為基礎，從規則與環境關係的角度體現了複雜系統的脆性問題。主要套用於複雜自適應系統（complex adaptive systems）。
人工智慧
人工智慧（Artificial Intelligence），英文縮寫為AI。它是研究、開發用於模擬、延伸和擴展人的智慧型的理論、方法、技術及套用系統的一門新的技術科學。 人工智慧是計算機科學的一個分支，它企圖了解智慧型的實質，並生產出一種新的能以人類智慧型相似的方式做出反應的智慧型機器，該領域的研究包括機器人、語言識別、圖像識別、自然語言處理和專家系統等。人工智慧從誕生以來，理論和技術日益成熟，套用領域也不斷擴大，可以構想，未來人工智慧帶來的科技產品，將會是人類智慧的“容器”。
人工智慧是對人的意識、思維的信息過程的模擬。人工智慧不是人的智慧型，但能像人那樣思考、也可能超過人的智慧型。
人工智慧是一門極富挑戰性的科學，從事這項工作的人必須懂得計算機知識，心理學和哲學。人工智慧是包括十分廣泛的科學，它由不同的領域組成，如機器學習，計算機視覺等等，總的說來，人工智慧研究的一個主要目標是使機器能夠勝任一些通常需要人類智慧型才能完成的複雜工作。但不同的時代、不同的人對這種“複雜工作”的理解是不同的。
人工智慧在計算機上實現時有2種不同的方式。一種是採用傳統的編程技術，使系統呈現智慧型的效果，而不考慮所用方法是否與人或動物機體所用的方法相同。這種方法叫工程學方法（ENGINEERING APPROACH），它已在一些領域內作出了成果，如文字識別、電腦下棋等。另一種是模擬法（MODELING APPROACH），它不僅要看效果，還要求實現方法也和人類或生物機體所用的方法相同或相類似。遺傳算法（GENERIC ALGORITHM，簡稱GA）和人工神經網路（ARTIFICIAL NEURAL NETWORK，簡稱ANN）均屬後一類型。遺傳算法模擬人類或生物的遺傳-進化機制，人工神經網路則是模擬人類或動物大腦中神經細胞的活動方式。為了得到相同智慧型效果，兩種方式通常都可使用。採用前一種方法，需要人工詳細規定程式邏輯，如果遊戲簡單，還是方便的。如果遊戲複雜，角色數量和活動空間增加，相應的邏輯就會很複雜（按指數式增長），人工編程就非常繁瑣，容易出錯。而一旦出錯，就必須修改原程式，重新編譯、調試，最後為用戶提供一個新的版本或提供一個新補丁，非常麻煩。採用後一種方法時，編程者要為每一角色設計一個智慧型系統（一個模組）來進行控制，這個智慧型系統（模組）開始什麼也不懂，就像初生嬰兒那樣，但它能夠學習，能漸漸地適應環境，應付各種複雜情況。這種系統開始也常犯錯誤，但它能吸取教訓，下一次運行時就可能改正，至少不會永遠錯下去，用不到發布新版本或打補丁。利用這種方法來實現人工智慧，要求編程者具有生物學的思考方法，入門難度大一點。但一旦入了門，就可得到廣泛套用。由於這種方法編程時無須對角色的活動規律做詳細規定，套用於複雜問題，通常會比前一種方法更省力。
遺傳算法
遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜尋最優解的方法。遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特徵的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭髮的特徵是由染色體中控制這一特徵的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由於仿照基因編碼的工作很複雜，我們往往進行簡化，如二進制編碼，初代種群產生之後，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，並藉助於自然遺傳學的遺傳運算元（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的後生代種群比前代更加適應於環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。
遺傳算法是解決搜尋問題的一種通用算法，對於各種通用問題都可以使用。搜尋算法的共同特徵為：
① 首先組成一組候選解
② 依據某些適應性條件測算這些候選解的適應度
③ 根據適應度保留某些候選解，放棄其他候選解
④ 對保留的候選解進行某些操作，生成新的候選解。
在遺傳算法中，上述幾個特徵以一種特殊的方式組合在一起：基於染色體群的並行搜尋，帶有猜測性質的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜尋算法區別開來。
遺傳算法
遺傳算法還具有以下幾方面的特點：
(1)遺傳算法從問題解的串集開始搜尋，而不是從單個解開始。這是遺傳算法與傳統最佳化算法的極大區別。傳統最佳化算法是從單個初始值疊代求最優解的；容易誤入局部最優解。遺傳算法從串集開始搜尋，覆蓋面大，利於全局擇優。
(2)遺傳算法同時處理群體中的多個個體，即對搜尋空間中的多個解進行評估，減少了陷入局部最優解的風險，同時算法本身易於實現並行化。
(3)遺傳算法基本上不用搜尋空間的知識或其它輔助信息，而僅用適應度函式值來評估個體，在此基礎上進行遺傳操作。適應度函式不僅不受連續可微的約束，而且其定義域可以任意設定。這一特點使得遺傳算法的套用範圍大大擴展。
(4)遺傳算法不是採用確定性規則，而是採用機率的變遷規則來指導他的搜尋方向。
(6)此外，算法本身也可以採用動態自適應技術，在進化過程中自動調整算法控制參數和編碼精度，比如使用模糊自適應法。
套用實例
信貸分配
由Holland基於於服務經濟模型開發的信貸分配，由兩個主要部分組成：拍賣和票據交換所。
每個分類器都有一個賬戶用來衡量它的實力，分類器匹配按照它們的實力來競價。通常出價最高的分類器來發布訊息，拍賣允許合適的分類器來發布訊息，一旦選擇一個分類器進行激活，它必須結算它的付款，通過結算機構支付其出價給其他分類。一個匹配的和激活的分類器傳送其投標的分類負責傳送訊息匹配的投標分類條件，競標-交易分布在這些分類之中。
與分類器合作的規則通過接收分類器出價得到獎勵，在一個鏈中的最後一個分類器收到環境獎勵，所有其他分類器收到來自他們的前任的獎勵。分類器的強度可能受到徵稅的影響。計畫是稅收懲罰無效的分類：
Ti(t):=ctax*Si(t)
使用以下方程更新分類器的實力：
Si(t+1)=Si(t) -Pi(t) - Ti(t) + Ri(t)
分類器報價與其實力成正比：
Bi=cbid*S
遺傳算法用於進化分類器。分類器的實力定義其適應性，過濾分類器以較高的機率（如旋轉輪可能被採用）再次出現和二進制字元串突變和交叉運算元被用來生成新的分類器。新生成的分類器替換弱，低強度分類器（其他機制，如擁擠也可以採用）。
