模式定理是具有低階、短定義距以及平均適應度高於種群平均適應度的模式在子代中呈指數增長。它保證了較優的模式（遺傳算法的較優解）的數目呈指數增長，為解釋遺傳算法機理提供了數學基礎。
基本介紹
- 中文名：模式定理
- 外文名：Schema Theory
基本概念,總結,
基本概念
模式(Schema)：編碼的字元串中具有類似特徵的子集。 例如上述五位二進制字元串中，模式“*111*”可代表4個個體。個體和模式的一個區別就是，個體是由{0，1}組成的編碼串，模式是由{0，1，*}組成，‘*’為通配符。
模式是指種群個體基因串中的相似樣板，它用來描述基因串中某些特徵位相同的結構。在二進制編碼中，模式是基於三個字元集(0,1,*)的字元串，符號*代表任意字元，即 0 或者 1。 模式示例：10**1
定義1：模式 H 中確定位置的個數稱為模式 H 的階，記作O(H)。例如O(10**1)=3 。
定義2：模式 H 中第一個確定位置和最後一個確定位置之間的距離稱為模式 H 的定義距，記作δ(H)。例如δ(10**1)=4 。
模式階(Schema Order)：表示模式中已有明確含義的字元個數，記為o(s)，s代表模式。例如o(*111*)=3; 階數越低，說明模式的概括性越強，所代表的編碼串個體數也越多。其中階數為零的模式概括性最強。模式階用來反映不同模式間確定性的差異，模式階數越高，模式的確定性就越高，所匹配的樣本數就越少。在遺傳操作中，即使階數相同的模式，也會有不同的性質，而模式的定義距就反映了這種性質的差異。
模式定義長度(Schema Defining Length)：指第一個和最後一個具有含義的字元之間的距離，其可表示該模式在今後遺傳操作中被破壞的可能性，越短則越小，長度為0最難被破壞。
模式數目：在二進制字元串中，假設字元長度為 λ，字元串中每一個字元可取(0,1,*)三個符號中任意一個，則可能組成的模式數目最多是 3^λ，擴展為一般情況，單個字元的取值有 k 種，則字元串組成的模式數目 n 為 (k+1)^λ。
編碼字元串（一個個體編碼串）所含模式總數：在二進制字元串中，假設字元長度為 λ，則可能組成的模式數目最多是 2^λ。因為每個個體編碼串均已有數字，只能在既定值和‘*’之間選擇。擴展為一般情況，單個字元的取值有 k 種，則字元串組成的模式數目 n 為 k^λ。
群體所含模式數：在長度為 λ 規模為 M 的二進制編碼字元串群體中，一般含有 2^λ ~ M*2^λ 個模式。
總結
模式定理是適應度高於群體平均適應度的，長度較短，低階的模式在遺傳算法的疊代過程中將按指數規律增長。該定理深刻地闡明了遺傳算法中發生“優勝劣汰”的原因。在遺傳過程中能存活的模式都是定義長度短、階次低、平均適應度高於群體平均適應度的優良模式。遺傳算法正是利用這些優良模式逐步進化到最優解。
模式能夠劃分搜尋空間，而且模式的階越高，對搜尋空間的劃分越細緻。模式定理告訴我們：GA 根據模式的適應度、長度和階次為模式分配搜尋次數。為那些適應度較高，長度較短，階次較低的模式分配的搜尋次數按指數率增長；為那些適應度較低，長度較長，階次較高的模式分配的搜尋次數按指數率衰減。
