八皇后算法python_八皇后问题遗传算法实现(python版)

八皇后问题的遗传算法实现过程详解

1、八皇后问题描述

19 世纪著名的数学家Gauss 在1850 年提出八皇后问题后, 该问题成为各类语言程序设计的经典题目。八皇后问题要求在8×8 格的国际象棋上摆放八个皇后,使横、竖、斜方向上都不能有两个及两个以上皇后在同一条直线上, 问题也可以推广到N 个皇后。穷举法在问题规模不大的情况下还可适用,回溯法是求解此问题的经典算法。但N 皇后问题是个NP 难问题, 随着皇后数目的增多, 求解复杂度激增, 就需利用非常规的技术求

解。遗传算法在求解一些NP 完全问题上得到了广泛地应用,本文用遗传算法求解八皇后问题,给出详细的实现过程。

2、基本遗传算法求解过程

基本遗传以初始种群为基点, 经过选择、交叉、变异操作生成新的种群,如此更新种群直到满足终止条件。其计算步骤如下:

(1) 将问题空间转换为遗传空间, 也就是编

码;

(2)随机生成P 个染色体作为初始种群;

(3)染色体评价,也就是按确定的适应度函数

计算各个染色体的适应度;

(4)根据染色体适应度,按选择算子进行染色

体的选择;

(5)按交叉概率进行交叉操作;

(6)按变异概率进行变异操作;

(7)返回(4)形成新的种群,继续迭代,直到满足终止条件。

基本遗传算法给出了基本框架, 针对求解的问题不同, 遗传算法在相应的计算步骤中有不同的设计。本文针对八皇后问题, 设计了相应的编码,适应度计算方法,交叉和变异操作。

3、用遗传算法求解八皇后问题实现过程详解

3.1 编码

遗传算法中传统的编码是二进制编码, 本文采用多值编码。染色体长度取决于皇后的个数。染色体中每个基因所处的位置表示其在棋谱中所在的行数, 基因值表示其所在的列数。如染色体40752613 表示:从0 开始数,第0 个4 表示在第零行的皇后在第4 列, 第1 个0 表示第一行的皇后在第0 列,以此类推。八皇后问题中皇后不能处于同行同列, 意味着染色体中0~7 的基因取值不能出现重复。

3.2 个体评价

染色体通常表示了问题的可行解, 对可行解进行遗传操作寻找最优解。但在八皇后问题中,染色体仅仅体现同行同列中未出现互攻, 在对角线上是否出现互攻还未做考虑。在对皇后的位置做比较的时候, 可以对两个棋子的行数差与列数差进行对比, 实现了互攻次数的统计。公式为:|绝对值((y2-y1)/(x2-x1)) |=1。公式中(x1,y1),(x2,y2)分别表示两个皇后所在的位置,即所在的行数和列数。当两个皇后的行数差与列数差比值的绝对值为1 的时候,两皇后在同一对角线上,即出现了互攻。每个染色体内的互攻次数为Value,初始值设为0;第0 行与1~7 行进行比较, 每出现一次互攻则Value 的值增加1;第1 行与2~7 行进行比较,以此类推来计算Value 值。当Value 为0 表示没有发生互攻,此染色体就是其中的一个可行解。当Value 不为0则进行适应度的计算。一般来说, 适应度越大越

好,而互攻次数为越小越好,所以可以将适应度的计算函数设置为:F=28-Value。

3.3 选择

选择使用的是经典的赌轮选择方法, 与基本遗传算法的实现无特别之处,此处不赘述。

3.4 交叉

经典的单点, 多点等交叉因染色体中不能出现重复的基因值,在该问题中不适用。本文使用部分匹配交叉,具体操作如下:

1)在染色体中随机选取两个点标记为y,

如:染色体a:01y24y3675;

染色体b:12y30y4576;

两个y 之间的基因段称为中间段, 记录其对应关系2-3,4-0;

2)对染色体a,b 的中间段进行交换,

形成染色体a':01y30y3675;染色体b': 12y24y4576;

3) 利用对应关系,对染色体a', b' 中间段外的基因进行交换,

形成 染色体a'': 41y30y2675;

染色体b'':   13y24y0576;

交叉完成。

3.5 变异

采用多值编码后, 变异操作并不能通过简单的0,1 反转实现。

本文采取随机地选取染色体内的两个基因进行交换来实现。

例如随机选取的是

6 和1 两个基因,那么

变异前染色体: 7 (6) 5 4 3 2 (1) 0

变异后染色体: 7 (1) 5 4 3 2 (6) 0

3.6 终止策略

本文采用的终止策略为: 当群体中出现染色体的适应值为0 时, 即表示算法搜索到了一个可行解,终止算法。若算法运行设置的代数还未找到可行解,同样终止程序运行。

4、总结本文详细介绍了用遗传算法求解八皇后问题的求解过程, 但要注意的是这只是其中的一种编码,交叉,变异等操作设计方法,还有许多其他的方法可以选择。对于各操作采取不同设计方案的遗传算法,其算法性能值得比较讨论。

1 #2 #遗传算法(八皇后问题)

3 # 最佳值284 importrandom5 importnumpy6

7

8 N=8 #皇后数

9 Cluster_size=12 #默认种群大小

10 LASTG=100 #/*终止后代*/

11 MRATE=0.8 #/*突变的概率*/

12 array=numpy.zeros((Cluster_size,N)).astype(int) #染色体集合

13 narray=numpy.zeros((Cluster_size * 2,N)).astype(int) #下一代染色体集合

14 _array=numpy.zeros((Cluster_size,N)).astype(int)#array数组的副本

15 values=numpy.zeros(Cluster_size).astype(int) #评估数组

16 max_array=numpy.zeros(N).astype(int) #保存最佳数组

17 generation = 0 #记录代数

18 signal = -1 #信号

19 max = -1 #记录当前最优值

20 max_generation = -1 #记录当前最优值代数

21

22

23

24 classStruct:25 key =numpy.zeros(N).astype(int)26 values =numpy.zeros(N).astype(int)27

28

29 rember=Struct()30

31

32 defrndn(l):33 rndno =random.randint(0,l-1)34 returnrndno35

36

37 defcopy_array():38 for i inrange(Cluster_size):39 for j inrange(N):40 _array[i][j]=array[i][j]41

42

43 defoutput_copy_array():44 for i inrange(Cluster_size):45 for j inrange(N):46 print(_array[i][j],end=" ")47 print()48

49

50 defthe_answer(values,size):51 for i inrange(size):52 if values[i]==28:53 returni54 return -1

55

56

57 defjudge(a,n):58 value = -1

59 for i inrange(n):60 value =a[i]61 j=i+1

62 while j<63 if return065 j>

66 return 1

67

68

69

70 defcount_collidecount():71 value=072 globalsignal73 for i inrange(Cluster_size):74 for j inrange(N):75 x1=j76 y1=array[i][j]77 m=j+1

78 while m<79 x2="m80" y2="array[i][m]81" if value>

83 m+=1

84 values[i]=28-value85 value=086 signal=the_answer(values,Cluster_size)87

88

89

90 defcount_generation_collidecount(values,cluster_size):91 value=092 for i inrange(cluster_size):93 for j inrange(N):94 x1=j95 y1=narray[i][j]96 m=j+1

97 while m<98 x2="m99" y2="narray[i][m]100" if y1 x1 value>

102 m+=1

103 values[i]=28-value104 value=0105

106

107 #/************************/

108 #/* selectp()函数 */

109 #/* 父代的选择 */

110 #/************************/

111 defselectp(roulette,totalfitness):112 acc=0113 ball=rndn(totalfitness)114 for i inrange(Cluster_size):115 acc+=roulette[i]116 if (acc>ball):117 break

118 returni119

120

121 deftakeoutrepeat( position):122 signal=True123 for i inrange(N):124 value = narray[position*2][i]125 j=i+1

126 while j<127 if have reapt number:>

129 signal=False130 j+=1

131 for i inrange(N):132 value=narray[position*2+1][i]133 j=i+1

134 while j<135 if have reapt number:>

137 signal=False138 j+=1

139 returnsignal140

141

142

143

144 defjudge_reapt(c, cluster):145 value =0146 arraysEqual =True147 i=0148 for j inrange(cluster):149 while (arraysEqual and i

153 if(arraysEqual):154 value+=1

155 else:156 arraysEqual=True157 i=0158

159 if(value>0):160 returnFalse161 else:162 returnTrue163

164

165

166

167 #/************************/

168 #/* selection()函数 */

169 #/* 选择下一代 */

170 #/************************

171

172 defselection():173 globalsignal174 globalmax_generation175 globalmax176 totalfitness=0177 roulette=numpy.zeros(Cluster_size*2).astype(int)178 acc=0179 for i inrange(Cluster_size):180 totalfitness=0181 count_generation_collidecount(roulette,Cluster_size*2)182 c=0183 while c

186 signal=the_answer(roulette,Cluster_size*2)187

188 whileTrue:189 ball =rndn(totalfitness)190 acc=0191 c=0192 while cball:195 break

196 c+=1

197 judge=judge_reapt(c,Cluster_size)198 if judge==True:199 break

200 #/ *染色体的复制 * /

201 for j inrange(N):202 array[i][j]=narray[c][j]203

204 for q in range(Cluster_size*2):205 if roulette[q]>max:206 max =roulette[q]207 max_generation =generation208 for i inrange(N):209 max_array[i]=narray[q][i]210 print(roulette[q], end=" ")211 print()212

213

214

215

216

217

218 defjudgein(m,location1,location2):219 i=location1220 while i<=location2:221 if ((m == rember.key[i]) | (m ==rember.values[i])):222 returni223 i+=1

224 return -1

225

226

227

228

229

230

231 #/************************/

232 #/* crossing()函数 */

233 #/* 特定2染色体的交叉 */

234 #/************************/

235 defcrossing(mama, papa,position):236 whileTrue:237 whileTrue:238 cp1 =rndn(N)239 cp2 =rndn(N)240 if cp1 !=cp2:241 break

242 #print("cp1="+str(cp1)+"cp2="+str(cp2))

243 if cp1<244 location1="cp1245" location2="cp2246" else:247>

250 i =location1251 while i<=location2:252 rember.key[i] =array[mama][i]253 rember.values[i] =array[papa][i]254 #交换中间段

255 narray[position*2][i] =array[papa][i]256 narray[position*2+1][i] =array[mama][i]257 i+=1

258 #利用对应关系,对染色体mama和papa, 中间段外的基因进行交换

259 #/ * 交换前半部分 * /

260 for j inrange(location1):261 weizhi =judgein(array[mama][j],location1,location2)262 #print("weizhi= "+str(weizhi))

263 if (weizhi == -1):264 narray[position*2][j] =array[mama][j]265 else:266 if (array[mama][j] ==rember.key[weizhi]):267 narray[position*2][j] =rember.values[weizhi]268 else:269 narray[position*2][j] =rember.key[weizhi]270 weizhi =judgein(array[papa][j], location1, location2)271 if (weizhi == -1):272 narray[position*2+1][j] =array[papa][j]273 else:274 if (array[papa][j] ==rember.key[weizhi]):275 narray[position*2+1][j] =rember.values[weizhi]276 else:277 narray[position*2+1][j] =rember.key[weizhi]278

279

280 #/ *交换后半部分 * /

281 j = location2+1

282 while j<283 weizhi="judgein(array[mama][j]," location1 location2 if narray else:287 else:290 else:295 else:298 j>

300

301 signal =takeoutrepeat(position)302 #print("--------------signal= "+str(signal))

303 if (signal !=False):304 break

305

306

307

308

309

310

311 #/************************/

312 #/* notval()函数 */

313 #/* */

314 #/************************/

315 defnotval(i):316 whileTrue:317 position1 =rndn(N)318 position2 =rndn(N)319 if position1 !=position2:320 break

321 temp=narray[i][position2]322 narray[i][position2] =narray[i][position1]323 narray[i][position1] =temp324

325

326

327

328 #/***********************/

329 #/* mutation()函数 */

330 #/* 突变 */

331 #/***********************/

332 defmutation():333 for i in range(Cluster_size*2):334 if (rndn(100) / 100 <=MRATE):335 #/ *染色体突变 * /

336 notval(i)337 print("mutation is complete")338

339

340

341

342

343 defmating():344 totalfitness =0345 roulette=numpy.zeros(Cluster_size).astype(int)346 print(len(roulette))347 #生成轮盘

348 for i inrange(Cluster_size):349 roulette[i] =values[i]350 totalfitness +=roulette[i]351 #选择和交叉的循环

352 for i inrange(Cluster_size):353 whileTrue:354 mama=selectp(roulette,totalfitness)355 papa=selectp(roulette,totalfitness)356 if mama !=papa:357 break

358 #特定2染色体的交叉

359 crossing(mama,papa,i)360

361

362

363 defoutputrember():364 for i inrange(N):365 print("key="+rember.key[i]+"values="+rember.values[i])366

367

368

369

370 defoutputnarray():371 for i in range(Cluster_size*2):372 if (i % 2 ==0):373 print("------------------------------")374 for j inrange(N):375 print(narray[i][j],end=" ")376 print()377

378

379

380

381 defoutput():382 globalmax383 globalmax_generation384 for i inrange(Cluster_size):385 if values[i]>max:386 max =values[i]387 max_generation=max_generation388 print(values[i],end=" ")389 print()390

391

392

393

394 defoutputarray():395 for i inrange(Cluster_size):396 for j in range(8):397 print(array[i][j], end =" ")398 print()399

400

401

402

403

404 definit_Cluster():405 print('fsadsgagasgs')406 a=[0 for n in range(8)]407 count=0408 while count <409 for y in range x="random.randint(0,7)">

411 a[y]=x412 if(judge(a,8)):413 for i in range(8):414 array[count][i]=a[i]415 else:416 count=count-1

417 count+=1

418

419

420

421

422

423 defmain():424 globalgeneration425 init_Cluster()426 while generation<427 if signal break>

429 else:430 print("代数="+str(generation))431 count_collidecount()432 print("-------------output------------values--------------------------")433 output()434 print("------------- outputarray--------------------------------------")435 outputarray()436 mating()437 print("------------- outputarray--------------------------------------")438 outputarray()439 print("-----------------mating选择交叉---------outputnarray---------------")440 outputnarray()441 mutation()442 print("-----------------mutation变异---------outputnarray---------------")443 outputnarray()444 print("------------- outputarray--------------------------------------")445 outputarray()446 copy_array()447 #print("---------------------------------------------------------------")

448 #output_copy_array()

449 selection()450 print("-----------------selection选择下一代--------outputarray---------------")451 outputarray()452 generation+=1

453 print("signal ="+str(signal)+"max ="+str(max)+"max_generation ="+str(max_generation)) #max为最佳值, max_generation为产生最佳值的代数

454 print(max_array,end=" ")455

456

457 if __name__ == "__main__":458 main()

427>409>283>244>135>127>98>79>63>

你可能感兴趣的