N皇後問題
經典的 N 皇後問題最初被稱為八皇後拼圖，起源于國際象棋。任務是将八名皇後放置在棋盤上，而且他們中的任何兩個都不互相構成威脅。換句話說，沒有兩個皇後可以在同一行、同一列或同一對角線。概括而言，N 皇後問題使用 N×N 的棋盤和 N (其中 N>3) 個皇後。對于原始的八皇後情形，有 92 個解，消除對稱解，則有 12 個唯一解。
使用排列組合，将 8 個皇後放置在 8×8 棋盤上的所有可能方式有 4,426,165,368 種。但是，如果通過確定不會在同一行或同一列上放置兩個皇後的方式建立候選解決方案，則可能的組合數量将減少到 8!=40320 個。
解的表示
在解決 N 皇後問題時，利用以下前提條件：每行恰好容納一個皇後，同時沒有兩個皇後共享同一列。這意味着可以将候選解表示為有序的整數清單或索引清單，每個索引表示皇後之一占據目前行的列數。
例如，在4×4棋盤上的四皇後問題中，具有以下索引清單：
(3, 2, 0, 1)
表示（索引從 0 開始計數）：
- 在第一行中，皇後放置在第四列中。
- 在第二行中，皇後放置在第三列中。
- 在第三行中，皇後放置在第一列中。
- 在第四行中，皇後放置在第二列中。
下圖描述了上述索引：
而索引 (1, 3, 0, 2) 則可以用來表示下圖：
(1, 3, 0, 2)
以這種方式表示的候選解中唯一可能的違反限制的是一對皇後之間共享對角線。
如，在第一個候選解中：
這意味着，在評估以這種方式表示的解時，隻需要查找并計算它們代表的位置之間的共享對角線。
問題的表示
為了封裝N-Queens問題，建立名為NQueensProblem的Python類。用所需的問題大小初始化該類，并提供以下公共方法：
- getViolationsCount(positions)：計算給定解違反限制的次數
- plotBoard(positions)：根據給定的解在棋盤上繪制皇後
棋子圖檔如下所示：
# 導入必要庫
import numpy as np
import matplotlib as mpl
from matplotlib import pyplot as plt
class NQueensProblem:
"""N皇後問題定義
"""
def __init__(self,numOfQueens):
self.numOfQueens = numOfQueens
def __len__(self):
"""
:return: the number of queens
"""
return self.numOfQueens
def getViolationsCount(self,positions):
"""
計算給定解中的違規次數
由于輸入的每一行都包含唯一的列索引，是以行或列不可能違反限制，僅對角線需要計算違反限制數。
"""
if len(positions) != self.numOfQueens:
raise ValueError("size of positions list should be equal to ", self.numOfQueens)
violations = 0
# 周遊每對皇後，計算它們是否在同一對角線上:
for i in range(len(positions)):
for j in range(i + 1, len(positions)):
#first queen in pair
column1 = i
row1 = positions[i]
#second queen in pair
column2 = j
row2 = positions[j]
if abs(column1 - column2) == abs(row1 - row2):
violations += 1
return violations
def plotBoard(self,positions):
"""
根據給定的解在棋盤上繪制皇後的位置
"""
if len(positions) != self.numOfQueens:
raise ValueError("size of positions list must be equal to ",self.numOfQueens)
fig,ax = plt.subplots()
#棋盤定義:
board = np.zeros((self.numOfQueens,self.numOfQueens))
#棋盤顔色交替
board[::2,1::2] = 1
board[1::2,::2] = 1
#繪制棋盤
ax.imshow(board,interpolation='none',cmap=mpl.colors.ListedColormap(['#ffc794','#4c2f27']))
#讀取棋子圖檔，并進行縮放
queenThumbnail = plt.imread("queen-thumbnail.png")
thumbnailSpread = 0.70 * np.array([-1,1,-1,1]) / 2
# 棋子繪制
for i,j in enumerate(positions):
#将棋子放在棋盤上
ax.imshow(queenThumbnail,extent=[j,j,i,i]+thumbnailSpread)
#坐标軸設定
ax.set(xticks=list(range(self.numOfQueens)),yticks=list(range(self.numOfQueens)))
ax.axis('image')
return plt 遺傳算法解決N皇後問題
常量及遺傳算子定義
1. 導入所需庫
from deap import base
from deap import creator
from deap import tools
from deap import algorithms
import random
import array
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns 2. 常量定義
# 16皇後
NUM_OF_QUEENS = 16
# 種群中個體數量
POPULATION_SIZE = 300
# 最大代際數
MAX_GENERATIONS = 100
# 交叉機率
P_CROSSOVER = 0.9
# 突變機率
P_MUTATION = 0.1 3. 首先使用要解決的問題的大小建立NQueensProblem類的執行個體：
nQueens = NQueensProblem(NUM_OF_QUEENS) 4. 由于目标是最大程度地減少違規次數（期望值為0），是以定義最小化适用度政策：
creator.create("FitnessMin",base.Fitness,weights=(-1.0,)) 5. 定義個體類
creator.create("Individual",array.array,typecode='i',fitness=creator.FitnessMin) 6. 由于解由有序的整數清單表示，每個整數表示皇後的列位置，是以使用以下定義來建立初始種群：
toolbox = base.Toolbox()
toolbox.register("randomOrder",random.sample,range(len(nQueens)),len(nQueens))
toolbox.register("individualCreator",tools.initIterate,creator.Individual,toolbox.randomOrder)
toolbox.register("populationCreator",tools.initRepeat,list,toolbox.individualCreator) 7. 設定适應度函數以計算皇後在棋盤上的放置所引起的違規次數：
def getViolationCount(individual):
return nQueens.getViolationsCount(individual),
toolbox.register("evaluate",getViolationCount)
8. 定義遺傳算子
toolbox.register("select",tools.selTournament,tournsize=2)
toolbox.register("mate",tools.cxUniformPartialyMatched,indpb=2.0/len(nQueens))
toolbox.register("mutate",tools.mutShuffleIndexes,indpb=1.0/len(nQueens)) 使用精英主義政策
使用名人堂可以用來保留進化過程中種群中曾經存在的最佳個體，并不會由于選擇，交叉或變異而失去了它們，HallOfFame類在tools子產品中實作。
将Halloffame對象用于實作精英主義。 Halloffame對象中包含的個體被直接注入下一代，并且不受選擇，交叉和突變的遺傳算子的影響
# 名人堂成員數量
HALL_OF_FAME_SIZE = 30
def eaSimpleWithElitism(population,
toolbox,
cxpb,
mutpb,
ngen,
stats=None,
halloffame=None,
verbose=__debug__):
"""
使用halloffame來實作精英機制。 包含在名人堂麥中的個體被直接注入下一代，并且不受選擇，交叉和突變的遺傳算子的影響。
"""
logbook = tools.Logbook()#用于監控算法運作，和統計資料
logbook.header = ['gen','nevals'] + (stats.fields if stats else [])
# 計算個體适應度
invalid_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 = fit
if halloffame is None:
raise ValueError("halloffame parameter must not be empty!")
#更新名人堂成員
halloffame.update(population)
hof_size = len(halloffame.items) if halloffame.items else 0
record = stats.compile(population) if stats else {}
logbook.record(gen=0,nevals=len(invalid_ind),**record)
if verbose:
print(logbook.stream)
#開始遺傳流程
for gen in range(1,ngen + 1):
#選擇個體數目=種群個體數-名人堂成員數
offspring = toolbox.select(population,len(population) - hof_size)
#種群更新到下一代
offspring = algorithms.varAnd(offspring,toolbox,cxpb,mutpb)
#計算個體适應度
invalid_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
#将名人堂成員添加到目前代
offspring.extend(halloffame.items)
#更新名人堂
halloffame.update(offspring)
#使用目前代替換種群
population[:] = offspring
#将目前統計資訊附加到日志
record = stats.compile(population) if stats else {}
logbook.record(gen=gen,nevals=len(invalid_ind),**record)
if verbose:
print(logbook.stream)
return population,logbook 遺傳流程
使用main函數完成遺傳流程
def main():
#建立初始種群
population = toolbox.populationCreator(n=POPULATION_SIZE)
#注冊要監聽的統計對象
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min",np.min)
stats.register("avg",np.mean)
#執行個體化名人堂對象
hof = tools.HallOfFame(HALL_OF_FAME_SIZE)
#運作遺傳算法
population,logbook = eaSimpleWithElitism(population,
toolbox,
cxpb=P_CROSSOVER,
mutpb=P_MUTATION,
ngen=MAX_GENERATIONS,
stats=stats,
halloffame=hof,
verbose=True)
#列印名人堂成員
print("- Best solutions are:")
for i in range(HALL_OF_FAME_SIZE):
print(i,": ",hof.items[i].fitness.values[0]," -> ",hof.items[i])
#繪制統計結果
minFitnessValues,meanFitnessValues = logbook.select("min","avg")
plt.figure(1)
sns.set_style("whitegrid")
plt.plot(minFitnessValues,color='red')
plt.plot(meanFitnessValues,color='green')
plt.xlabel('Generation')
plt.ylabel('Min / Average Fitness')
plt.title('Min and Average fitness over Generations')
# 繪制最佳解
sns.set_style("whitegrid", {'axes.grid' : False})
nQueens.plotBoard(hof.items[0])
# 繪制結果顯示
plt.show() 代碼運作及結果
代碼運作：
if __name__ == "__main__":
main() 可以看到列印的名人堂成員：
- Best solutions are:
0 : 0.0 -> Individual('i', [12, 9, 3, 1, 13, 11, 5, 14, 0, 6, 10, 7, 2, 15, 8, 4])
1 : 0.0 -> Individual('i', [10, 12, 1, 9, 2, 6, 8, 15, 11, 0, 14, 7, 4, 13, 3, 5])
2 : 0.0 -> Individual('i', [10, 12, 1, 9, 2, 6, 8, 14, 11, 0, 15, 7, 4, 13, 3, 5])
3 : 0.0 -> Individual('i', [1, 12, 10, 7, 2, 0, 5, 14, 11, 6, 15, 13, 4, 9, 3, 8])
...
29 : 1.0 -> Individual('i', [9, 14, 4, 10, 12, 0, 5, 1, 11, 15, 2, 7, 8, 13, 3, 6]) 繪制最佳解：
最小适應度和平均适應度變化情況：