0. 前言

進化算法 (Evolutionary Algorithm, EA) 和遺傳算法 (Genetic Algorithms, GA) 已成功解決了許多復雜的設計和布局問題，部分原因是它們采用了受控隨機元素的搜索。這通常使得使用 EA 或 GA 設計的系統(tǒng)能夠超越我們的理解進行創(chuàng)新。在本節(jié)中，我們將解決一個經(jīng)典的設計和布局問題：N 皇后問題，這個問題使用大小為 N 的典型棋盤，經(jīng)典的國際象棋棋盤大小為 8 (即 8×8 )。我們的目標是在棋盤上放置 N 個皇后棋子，使得沒有一個棋子可以在不移動的情況下俘獲另一個棋子。

1. N 皇后問題

在國際象棋中，皇后棋子是最強大的，可以沿著任何方向和距離移動。通常，每個玩家只有一個皇后棋子，但有一條特殊規(guī)則，允許玩家在將兵移動到對手的底線時加冕更多的皇后，皇后游戲的前提是玩家已經(jīng)加冕了多個皇后(雖然這種情況在真實的比賽中可能永遠不會發(fā)生，因為當玩家的國王棋子被俘獲時，比賽就將結束)。
經(jīng)典的 N 皇后問題最初被稱為八皇后拼圖，起源于國際象棋。任務是將八名皇后放置在棋盤上，而且他們中的任何兩個都不互相構成威脅。換句話說，沒有兩個皇后可以在同一行、同一列或同一對角線。概括而言，N 皇后問題使用 N × N 的棋盤和 N (其中 N>3 )個皇后。對于原始的八皇后情形，有 92 個解，消除對稱解，則有 12 個唯一解。
使用排列組合，將 8 個皇后放置在 8 × 8 棋盤上的所有可能方式有 4,426,165,368 種。但是，如果通過確保不會在同一行或同一列上放置兩個皇后的方式創(chuàng)建候選解決方案，則可能的組合數(shù)量將減少到 $8!=40320$ 個。

2. 解的表示

在解決 N 皇后問題時，利用以下前提條件：每行恰好容納一個皇后，同時沒有兩個皇后共享同一列。這意味著可以將候選解表示為有序的整數(shù)列表或索引列表，每個索引表示皇后之一占據(jù)當前行的列數(shù)。例如，在 4×4 棋盤上的四皇后問題中，具有以下索引列表：

(3, 2, 0, 1)

表示(索引從 0 開始計數(shù))：

1. 在第一行中，皇后放置在第四列中
2. 在第二行中，皇后放置在第三列中
3. 在第三行中，皇后放置在第一列中
4. 在第四行中，皇后放置在第二列中

3. 遺傳算法解決 N 皇后問題

(1) 首先，導入所需庫：

import random
import numpy as npfrom deap import algorithms
from deap import base
from deap import creator
from deap import toolsimport matplotlib.pyplot as plt
from matplotlib.pyplot import figure

(2) 查看國際象棋棋盤上的皇后的初始位置。由于皇后棋子可以沿著任何方向和距離移動，因此這個游戲被限制在皇后的最大數(shù)量等于棋盤大小的情況下。在本節(jié)中，我們使用 8 個棋子，接下來，繪制皇后的初始位置：

board_size = number_of_queens = 8chessboard = np.zeros((board_size,board_size))
chessboard[1::2,0::2] = 1
chessboard[0::2,1::2] = 1figure(figsize=(6, 6), dpi=80)
plt.imshow(chessboard, cmap='binary')for _ in range(number_of_queens):i, j = np.random.randint(0, board_size, 2)plt.text(i, j, '?', fontsize=30, ha='center', va='center', color='black' if (i - j) % 2 == 0 else 'white')
plt.show()

下圖顯示了渲染后的棋盤和皇后棋子的移動方式?？梢钥吹?#xff0c;選定的棋子可以立即俘獲其他幾個棋子，我們的目標是將所有皇后放置在沒有一個棋子可以俘獲另一個棋子的位置。

(3) 皇后游戲的適應度評估函數(shù) evalNQueens 通過采用一種簡便方法來評估個體的適應度，而不是迭代運行每一種放置方式。該函數(shù)假設只能在一行或一列上放置一個皇后。因此，我們只需要評估皇后是否位于同一對角線，簡化了適應度函數(shù)代碼：

creator.create("FitnessMax", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)def evalNQueens(individual):size = len(individual)#Count the number of conflicts with other queens.#The conflicts can only be diagonal, count on each diagonal lineleft_diagonal = [0] * (2*size-1)right_diagonal = [0] * (2*size-1)#Sum the number of queens on each diagonal:for i in range(size):left_diagonal[i+individual[i]] += 1right_diagonal[size-1-i+individual[i]] += 1#Count the number of non-conflicts on each diagonalsum_ = 0for i in range(2*size-1):if left_diagonal[i] > 1:sum_ += left_diagonal[i] - 1if right_diagonal[i] > 1:sum_ += right_diagonal[i] - 1    return sum_,

(4) 在適應度評估函數(shù)之后，編寫 eaSimple 函數(shù)，它是標準的 DEAP 中 algorithms.eaSimple 函數(shù)的副本。該函數(shù)與 OneMax 一節(jié)中使用的函數(shù)幾乎完全相同，可以自定義輸出表現(xiàn)最佳的個體，并測試是否可以提前停止。在以下代碼中，比較了個體適應度與最大適應度，如果達到了最大適應度，進化過程將會提前停止：

toolbox = base.Toolbox()
toolbox.register("permutation", random.sample, range(number_of_queens), number_of_queens)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.permutation)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)toolbox.register("evaluate", evalNQueens)
toolbox.register("mate", tools.cxPartialyMatched)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=2.0/number_of_queens)
toolbox.register("select", tools.selTournament, tournsize=3)def plot_board(individual):  plt.imshow(chessboard, cmap='binary')for i in range(number_of_queens):               plt.text(i, individual[i], '?', fontsize=20, ha='center', va='center', color='black' if (i - individual[i]) % 2 == 0 else 'white')
plt.show()def eaSimple(population, toolbox, cxpb, mutpb, ngen, max, stats=None, halloffame=None, ):  logbook = tools.Logbook()logbook.header = ['gen', 'nevals'] + (stats.fields if stats else [])# Evaluate the individuals with an invalid fitnessinvalid_ind = [ind for ind in population if not ind.fitness.valid]fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)for ind, fit in zip(invalid_ind, fitnesses):ind.fitness.values = fitif halloffame is not None:halloffame.update(population)record = stats.compile(population) if stats else {}logbook.record(gen=0, nevals=len(invalid_ind), **record)    print(logbook.stream)done = False# Begin the generational processfor gen in range(1, ngen + 1):if done: return# Select the next generation individualsoffspring = toolbox.select(population, len(population))offspring = [toolbox.clone(ind) for ind in offspring]# Apply crossover and mutation on the offspringfor i in range(1, len(offspring), 2):if random.random() < cxpb:offspring[i - 1], offspring[i] = toolbox.mate(offspring[i - 1],offspring[i])del offspring[i - 1].fitness.values, offspring[i].fitness.valuesfor i in range(len(offspring)):if random.random() < mutpb:offspring[i], = toolbox.mutate(offspring[i])del offspring[i].fitness.values# Evaluate the individuals with an invalid fitnessinvalid_ind = [ind for ind in offspring if not ind.fitness.valid]fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)for ind, fit in zip(invalid_ind, fitnesses):ind.fitness.values = fit            if fit[0] >= max:print("Solved")done = True# Update the hall of fame with the generated individualsif halloffame is not None:halloffame.update(offspring)            plot_board(halloffame[0])            # Replace the current population by the offspringpopulation[:] = offspring# Append the current generation statistics to the logbookrecord = stats.compile(population) if stats else {}logbook.record(gen=gen, nevals=len(invalid_ind), **record)print(logbook.stream)

(5) 最后，執(zhí)行種群的演化。首先創(chuàng)建種群和一個用于存儲最佳個體的 HallOfFame 容器。然后，注冊各種統(tǒng)計數(shù)據(jù)，最后調(diào)用 eaSimple 函數(shù)演化種群。在以下代碼中，將 max = number_of_queens 作為輸入來控制個體達到最大適應度時提前停止種群的進化：

pop = toolbox.population(n=100)
hof = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("Avg", np.mean)
stats.register("Std", np.std)
stats.register("Min", np.min)
stats.register("Max", np.max)eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=100, max = number_of_queens,stats=stats ,halloffame=hof)

最后，查看進化過程的輸出，并查看算法演化解決方案的效果如何。從輸出中可以看出，演化過程能夠提前停止(在第 5 代生成一個可行的解決方案)。重新查看解決方案，確認每個皇后無法互相攻擊?？梢栽黾悠灞P大小和皇后數(shù)量(如增加到 16 或更大的值)，這可能需要同時增加種群大小和演化代數(shù)的數(shù)量。

可以通過完成以下問題進一步理解使用 DEAP 庫實現(xiàn)遺傳算法的流程：

• 將要演化的種群大小更改為其他值，然后重新運行，觀察較大的種群對演化的影響
• 更改交叉和突變率，然后重新運行，觀察能否在更少的代數(shù)中解決問題
• 增加或減少錦標賽的大小，然后重新運行，觀察錦標賽大小對演化的影響

小結

N 皇后問題是一個經(jīng)典的組合問題，要求在一個( N x N )的棋盤上放置 N 個皇后，使得它們互相不能攻擊到對方。遺傳算法是解決 N 皇后問題的一種有效方法，本節(jié)中，我們使用 DEAP 庫實現(xiàn)遺傳算法解決了 N 皇后問題。

系列鏈接

遺傳算法與深度學習實戰(zhàn)（1）——進化深度學習
遺傳算法與深度學習實戰(zhàn)（2）——生命模擬及其應用
遺傳算法與深度學習實戰(zhàn)（3）——生命模擬與進化論
遺傳算法與深度學習實戰(zhàn)（4）——遺傳算法詳解與實現(xiàn)
遺傳算法與深度學習實戰(zhàn)（5）——遺傳算法框架DEAP
遺傳算法與深度學習實戰(zhàn)（6）——DEAP框架初體驗