簡述
在一個種群繁衍的過程中，存在著自然選擇剑辫，交配繁衍摘昌，基因突變等生物進(jìn)化過程，遺傳算法便是模擬這樣的一個過程虱颗。與上面進(jìn)化過程相對應(yīng)的一個數(shù)據(jù)集在每一次迭代過程中都要經(jīng)過選擇操作沥匈，交換操作，突變操作忘渔。通過模式定理和積木塊假設(shè)可以證明算法有獲得最優(yōu)解的可能性高帖，以及有能力獲得最優(yōu)解。
基礎(chǔ)理論
選擇操作
在生物進(jìn)化的過程中辨萍，一個種群中會受到自然選擇的作用從而達(dá)到優(yōu)勝略汰棋恼。在遺傳算法中，選擇操作便是一個淘汰過程锈玉。它可很直接的選擇適應(yīng)度前50%的個體爪飘，也可以按照個體適應(yīng)值的占比有概率的選擇，書中介紹的選擇算法是輪盤賭算法
即如圖所示拉背，一個個體數(shù)為10的種群师崎，上面是隨機(jī)生成的分塊，下面是種群中個體適應(yīng)值占總適應(yīng)值的比重椅棺，且總和均為1犁罩。
輪盤賭的算法如下（類python的一種偽代碼）：
gen_index, p_index, a_index = 0
p_sum = p[p_index]
a_sum = a[a_index]
while gen_index < length:
if p_sum <= a_sum:
new_gen[gen_index++] = old_gen[a_index]
p_sum += p[++p_index]
else:
a_sum += a[++a_index]
依照算法一輪下來，新的一代個體分別是{a2两疚，a3床估，a5，a6诱渤，a6丐巫，a7，a8勺美，a9递胧，a10，a10}赡茸，其中a1和a4因為個體適應(yīng)度太小被淘汰掉了缎脾。
交叉操作
基于概率的兩個個體的基因交換
舉個例子兩個個體為a1 = [2, 3, 5, 6, 7], a2=[1, 4, 5, 6, 8]
a1_index, a2_index = 0
pc = 0.2 ##交叉概率
for i in len(a1):
for j in len(a2):
if rand < pc:
swap(a1[i], a2[j])
選擇操作需要注意特定問題的個體特性，如旅行商問題就是一個不能重復(fù)的數(shù)組占卧，那么交叉操作就需要成對進(jìn)行遗菠。交叉不一定是兩個相鄰的個體進(jìn)行的联喘，也可以指定特定個體（如當(dāng)前適應(yīng)度最優(yōu)個體），與其他個體交換辙纬。
變異操作
基于概率的個體的基因隨機(jī)變化
舉例個體為a=[1, 2, 3, 4, 5]
pm = 0.1
for i in len(a):
if rand < pm:
a[i] = randint(lower_bound, upper_bound)
模式定理
模式定義：模式是描述種群在位串的某些確定位置上具有相似性質(zhì)的位串子集的相似性模板
模式階定義：模式H中確定位置的個數(shù)稱作該模式的模式階耸袜，記作O(H)
定義距定義：模式H第一個確定位置和最后一個確定位置的距離為定義距，記作D(H)
模式定理：在遺傳算法選擇牲平、交叉和變異算子的作用下，具有低階域滥、短定義距纵柿、并且其平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中將呈指數(shù)級增長。
舉例說明：一個種群中的個體是由{0启绰，1昂儒，*}構(gòu)成,0和1是具體的數(shù)值，*表示為通配符委可，那么0100渊跋，01**，00**等都可以表示為模式着倾，0100的模式階就為4拾酝，01**的模式階就為2，0100的定義距為4卡者，01**的定義距為2蒿囤。
現(xiàn)在假如一個初始種群的有兩個個體{00000000，11111111} 崇决，在經(jīng)過遺傳計算（淘汰先不管）后材诽，種群改為{00001111，11110000恒傻，00000000脸侥，11111111}這時候就會明顯發(fā)現(xiàn)，00000000這種長定義距的模式只有一個盈厘，0000****這種較低階的睁枕，且定義距短的模式有兩個，在經(jīng)過n次遺傳計算后扑庞，種群中形如這樣的0*******一階定義距為1模式將會是數(shù)量最多的譬重，那么基于這些模式就有可能組成最優(yōu)解，這也是最優(yōu)解產(chǎn)生的必要條件罐氨。（ps:肯定有具體的證明過程了臀规，這只是一個初步的理解xp）
積木塊假設(shè)
積木塊：具有低階、短定義距的模式以及高水平的模式
積木塊假設(shè)：個體的積木塊通過選擇栅隐、交叉塔嬉、變異等遺傳算子的作用玩徊，能夠結(jié)合在一起形成高階，長距谨究、高適應(yīng)度的個體代碼串
這也不難理解恩袱，多種模式的個體，可以相互結(jié)合形成胶哲，特定的個體畔塔，這也就說明了，遺傳算法是有能力形成最優(yōu)解的
遺傳算法流程
- 初始化：隨機(jī)生成種群NP鸯屿，迭代計數(shù)器g = 0
- 個體評價：計算種群中個體的適應(yīng)度
- 遺傳運算：選擇運算 交叉運算 變異運算
- 終止條件判斷：g > G 停止計算澈吨，輸出結(jié)果；g < G寄摆，g++
遺傳算法的缺點
具體的收斂速度什么的沒找到具體數(shù)據(jù)谅辣，我水平又一般，復(fù)雜算法就不太會分析了婶恼，只知道他是可以收斂的桑阶。但是做了幾道題之后發(fā)現(xiàn)，遺傳算法容易提前收斂勾邦，遺傳運算過程中種群多樣性變低蚣录，再想進(jìn)化的話，完全靠變異眷篇，也就是被困在局部最優(yōu)解包归。
