文檔

代碼及文檔：通過網盤分享的文件：code
鏈接: https://pan.baidu.com/s/1Rgo9ynnEqjZsSP2-6TyS8Q?pwd=n99p 提取碼: n99p

---

補充核心代碼

---

核心代碼內容：

genetic_algorithm,py

# -*- coding: utf-8 -*-
"""
Created on Sun Jul 25 10:01:26 2021@author: zyw
"""import numpy as np
import matplotlib.pyplot as pltfrom queen import Queendef select(C):'''This method is used to select two indices of individuals for crossoverParameters----------C : list of cost of indivduals.Returns-------two indices'''n = len(C)p = []for idx in range(2):i = np.random.randint(n)j = np.random.randint(n)if C[i] < C[j] and np.random.rand() < 0.9:p.append(i)else:p.append(j)return p[0], p[1]def crossover(p1, p2):n = len(p1)pos = np.random.randint(n)c1 = p1.copy()for i in range(pos, n):c1[i] = p2[i]c2 = p2.copy()for i in range(pos, n):c2[i] = p1[i]return c1, c2def mutation(x):'''find a new solution randomly'''y = x.copy()i = np.random.randint(y.size)y[i] = (y[i] + 1 + np.random.randint(y.size-1)) % y.sizereturn ydef replacement(P, C, OFF, NC):'''replacement for genetic algorithm, current P and offspring OFF compete for surviving Parameters----------P : list of current population.C : costs of current individualsOFF : list of offspringNC : cost of offspringReturns-------none'''for i in range(len(C)):if NC[i] < C[i] or (np.random.rand() < 0.1 and C[i] != 0):P[i] = OFF[i]C[i] = NC[i]def genetic_algorithm(f, n, N = 20, M = 1000, cxProb = 1.0, mtProb = 1.0):'''This is a toy genetic algorithm n is number of queenf is cost functionN is population sizeM is iteration timescxProb is crossover probabilitymtProb is mutation probability'''X = [Queen.init_solution(n) for i in range(N)]C = [f(x) for x in X]costs = np.zeros([M,2])## add your code here -------------------------------------------------for generation in range(M):# Select parentsp1, p2 = select(C)# Perform crossoverc1, c2 = crossover(X[p1], X[p2]) if np.random.rand() < cxProb else X[p1], X[p2]# Perform mutationc1 = mutation(c1) if np.random.rand() < mtProb else c1c2 = mutation(c2) if np.random.rand() < mtProb else c2# Evaluate offspringC1 = f(c1)C2 = f(c2)# Replace populationreplacement(X, C, [c1, c2], [C1, C2])# Track costscosts[generation, 0] = min(C)costs[generation, 1] = max(C)## end your code ------------------------------------------------------np.savetxt("convergence.csv", costs, fmt="%d", delimiter=",")y = np.array(range(M))plt.plot(y, costs, linewidth=2)plt.show()return X[C.index(min(C))], min(C)if __name__=="__main__":num = 16best, best_value = genetic_algorithm(Queen.eval, num)print(best, best_value)Queen.display(best)

local_search.py

# -*- coding: utf-8 -*-
"""
Created on Sun Jul 25 10:01:26 2021@author: zyw
"""import numpy as np
import matplotlib.pyplot as pltfrom queen import Queendef neighbor(x):'''find a new solution randomly'''y = x.copy()i = np.random.randint(y.size)y[i] = (y[i] + 1 + np.random.randint(y.size-1)) % y.sizereturn ydef random_search(f, x, iteration_times=1000):min_value = f(x)min_x = x.copy()value = min_valuecosts = np.zeros([iteration_times,2])for i in range(iteration_times):for j in range(len(x)):x = neighbor(x)value = f(x)if value < min_value:min_value = valuemin_x = x.copy()costs[i][0] = valuecosts[i][1] = min_valuenp.savetxt("convergence.csv", costs, fmt="%d", delimiter=",")y = np.array(range(iteration_times))plt.plot(y, costs, linewidth=2)plt.show()return min_x, min_valuedef greedy_search(f, x, iteration_times=1000):value = f(x)costs = np.zeros([iteration_times,1])for i in range(iteration_times):for j in range(len(x)):nx = neighbor(x)nvalue = f(nx)if nvalue < value:value = nvaluex = nxcosts[i][0] = valuenp.savetxt("convergence.csv", costs, fmt="%d", delimiter=",")y = np.array(range(iteration_times))plt.plot(y, costs, linewidth=2)plt.show()return x, valuedef hill_climbing(f, x):value = f(x)improved = True## add your code here -------------------------------------------------while improved:improved = Falsefor i in range(len(x)):nx = neighbor(x)nvalue = f(nx)if nvalue < value:value = nvaluex = nximproved = True## end your code ------------------------------------------------------return x, valuedef simulated_annealing(f, x, iteration_times=500, t0=100, alpha=0.9):'''This is a toy simulated annealing algorithm '''min_value = f(x)min_x = x.copy()value = min_valuet = t0costs = np.zeros([iteration_times,2])## add your code here -------------------------------------------------for i in range(iteration_times):for j in range(len(x)):nx = neighbor(x)nvalue = f(nx)delta = nvalue - valueif delta < 0 or np.random.rand() < np.exp(-delta / t):x = nxvalue = nvalueif value < min_value:min_value = valuemin_x = x.copy()t *= alpha  # Decrease temperature## end your code ------------------------------------------------------np.savetxt("convergence.csv", costs, fmt="%d", delimiter=",")y = np.array(range(iteration_times))plt.plot(y, costs, linewidth=2)plt.show()return min_x, min_valueif __name__=="__main__":num = 8x = Queen.init_solution(num)#best, best_value = random_search(Queen.eval, x)best, best_value = greedy_search(Queen.eval, x)#best, best_value = hill_climbing(Queen.eval, x)#best, best_value = simulated_annealing(Queen.eval, x)print(best_value, best)Queen.display(best)

---