Python用戶寶典：了解并實(shí)現(xiàn)遺傳算法
譯文譯者 | 布加迪
審校 | 重樓
遺傳算法是一種基于自然選擇的技術(shù)，用于解決復(fù)雜問題。由于問題很復(fù)雜，遺傳算法（而不是其他方法）被用來得出解決問題的合理方案。本文介紹遺傳算法的基礎(chǔ)知識(shí)以及如何用Python來實(shí)現(xiàn)。
遺傳算法的要素
適應(yīng)度函數(shù)
適應(yīng)度函數(shù)衡量所考慮的解決方案與問題的最佳解決方案的接近程度。它為人群中的每個(gè)人提供了適應(yīng)度水平，描述了當(dāng)前一代人的質(zhì)量或效率。這個(gè)分值定義了選擇，而更高的適應(yīng)度值表明是經(jīng)過優(yōu)化的解決方案。
比如說，假設(shè)我們?cè)谔幚硪粋€(gè)實(shí)際的函數(shù)f(x)，其中x是一組參數(shù)。要找到的最優(yōu)值是x，這樣f(x)就取最大值。
選擇
這個(gè)過程決定了當(dāng)前一代人中哪些個(gè)體受到青睞，從而繁殖、為下一代做出貢獻(xiàn)。可以確定許多選擇方法，每種方法都有自己的特點(diǎn)和適合的上下文。
- 輪盤選擇：
根據(jù)個(gè)體的適應(yīng)度水平，選擇個(gè)體的概率也是最大的。
- 錦標(biāo)賽選擇：
隨機(jī)抽取一組，選擇其中最好的。
- 基于排序的選擇：
根據(jù)適合度對(duì)人進(jìn)行排序，選擇機(jī)會(huì)則根據(jù)適合度分?jǐn)?shù)按比例分配。
交叉
交叉是遺傳算法的一個(gè)基本概念，其目的是交換兩個(gè)親本的遺傳信息，形成一個(gè)或多個(gè)后代。這個(gè)過程非常類似自然界中發(fā)生的生物的交叉和重組。運(yùn)用遺傳的基本原理，交叉試圖產(chǎn)生具有雙親理想特征的后代，從而在下一代中有更好的適應(yīng)性。交叉是一個(gè)比較寬泛的概念，可以分為幾種類型，每種類型都有其特點(diǎn)和可以有效運(yùn)用的領(lǐng)域。
- 單點(diǎn)交叉：在親本染色體上選擇一個(gè)交叉點(diǎn)，實(shí)際上只發(fā)生一次交叉。這個(gè)位置之前的所有基因都取自第一個(gè)親本，而這個(gè)位置之后的所有基因都取自第二個(gè)親本。
- 兩點(diǎn)交叉：選擇兩個(gè)斷點(diǎn)，它們之間的部分在兩個(gè)親本染色體之間交換。它也有利于遺傳信息的交換，這與單點(diǎn)交叉不一樣。
突變
在遺傳算法中，突變之所以至關(guān)重要，是由于它提供了多樣性，多樣性是避免直接向最優(yōu)解區(qū)域收斂的關(guān)鍵因素。因此，獲得單個(gè)突變基因串的隨機(jī)變化，算法可以進(jìn)入僅通過交叉操作無法企及的最優(yōu)解空間的其他區(qū)域。這個(gè)隨機(jī)過程保證了無論怎樣，人群都會(huì)進(jìn)化，或者在遺傳算法確定的搜索空間區(qū)域內(nèi)移動(dòng)其位置。
實(shí)現(xiàn)遺傳算法的步驟
不妨用Python實(shí)現(xiàn)遺傳算法。
問題定義
問題：對(duì)具體函數(shù)進(jìn)行計(jì)算；f (x) = x^2f(x) = x^2，只對(duì)x值取整。
適應(yīng)度函數(shù)：對(duì)于染色體二進(jìn)制為x的情況，適應(yīng)度函數(shù)的一個(gè)例子可能是f(x)= x^2。
def fitness(chromosome):
x = int(''.join(map(str, chromosome)), 2)
return x ** 2人群初始化
生成一個(gè)給定長度的隨機(jī)染色體。
def generate_chromosome(length):
return [random.randint(0, 1) for _ in range(length)]
def generate_population(size, chromosome_length):
return [generate_chromosome(chromosome_length) for _ in range(size)]
population_size = 10
chromosome_length = 5
population = generate_population(population_size, chromosome_length)適應(yīng)度評(píng)估
評(píng)估人群中每個(gè)染色體的適應(yīng)度。
fitnesses = [fitness(chromosome) for chromosome in population]選擇
使用輪盤選擇法根據(jù)適合度選擇親本染色體。
def select_pair(population, fitnesses):
total_fitness = sum(fitnesses)
selection_probs = [f / total_fitness for f in fitnesses]
parent1 = population[random.choices(range(len(population)), selection_probs)[0]]
parent2 = population[random.choices(range(len(population)), selection_probs)[0]]
return parent1, parent2交叉
使用單點(diǎn)交叉，在父本基因串中選擇一個(gè)隨機(jī)的交叉位置，并在兩個(gè)基因串之間交換這個(gè)位置之后的所有基因值。
def crossover(parent1, parent2):
point = random.randint(1, len(parent1) - 1)
offspring1 = parent1[:point] + parent2[point:]
offspring2 = parent2[:point] + parent1[point:]
return offspring1, offspring2突變
通過以一定的概率翻轉(zhuǎn)比特來實(shí)現(xiàn)突變。
def mutate(chromosome, mutation_rate):
return [gene if random.random() > mutation_rate else 1 - gene for gene in chromosome]
mutation_rate = 0.01結(jié)語
總之，由于模擬物種進(jìn)化，遺傳算法對(duì)于解決無法直接解決的優(yōu)化問題具有一致性和有效性。因此，一旦您掌握了遺傳算法的基本要素，并了解了如何用Python實(shí)現(xiàn)遺傳算法，解決復(fù)雜任務(wù)就會(huì)容易得多。選擇、交叉和突變使您能夠?qū)鉀Q方案進(jìn)行修改，并不斷獲得最佳或接近最佳的答案。但愿您已準(zhǔn)備好將遺傳算法運(yùn)用到自己的任務(wù)中，從而在不同的任務(wù)和問題解決中得到改進(jìn)。
原文標(biāo)題：Understanding and Implementing Genetic Algorithms in Python，作者：Jayita Gulati
