• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Castle assignment algorithm explanation. a guest May 28th, 2017 110 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. Run 1, no rr(round-robin): [ 1  3  8  5 12 22  2 33  6  8]
2. Run 1, rr: [ 4  0  6 13 13 25  1  3 26  9]
3. Run 2, no rr: [ 5  1  8 13 12 23  3  2 25  8]
4. Run 2, rr: [ 0  1  8 14 16  1 22  3 25 10]
5.
6. These assignments have been generated by a genetic algorithm, described below.
7.
8. Genotype of individuals
9. -----------------------
10.
11. Each genotype is a sorted list of nine integers between 0 and 100 inclusive.
12.
13. [k(1) k(2) k(3) k(4) k(5) k(6) k(7) k(8) k(9)]
14.
15. Let k(0) = 0 and k(10) = 100. Each genotype expresses thus expresses their phenotype as follows:
16.
17. -Castle n(n=1 to 10) attack strength = k(n) - k(n-1)
18.
19. This implementation has a few advantages:
20.
21. -You do not have to check the total # of soldiers assigned, and only have to sort genotypes to ensure non-negative attack strengths.
22. -There is a 1-1 correspondence between genotypes and valid assignments with 100 soldiers.
23. -Small changes in genotype correspond to small changes in phenotype.
24.
25.
26. Crossover & mutation
27. --------------------
28. Crossover is single point, with sorting afterwards to ensure valid assignments.
29.
30. Mutation on single list entry k(n) are done by using binomial trials:
31.
32. new k(n) = ( # of successes in 302 trials with p = ((3*k(n) + 1) / 302) )//3
33.
34. Repeated iterations to force mutation can be done. This ensures most mutations will be small and that only a sort is needed to ensure a valid genotype.
35.
36.
37. Selection
38. ---------
39. Given a ranking of each individual within a population, here is how I prepared the next generation, assuming a pop. size of 200:
40.
41. -Bottom 20 are replaced by copies of top 20. Entries ranked 11-20 undergo a single forced mutation in this copy.
42. -Next-to-bottom 20 undergo hypermutation: forced mutations on each entry.
43. -A few non-forced mutations occur in the middle 120 of the population.
44. -All of the top 180, (Including the originals, but not the copies of the top 20), undergo randomly paired crossover.
45.
46. This procedure is rather ad-hoc, but it was effective nevertheless.
47.
48. Evaluation and general approach
49. -------------------------------
50. To take account of the fact that the data from the previous contest was available and likely to be exploited, I adopted a two-stage approach.
51.
52. In the first stage, I generated an 'optimized' population. For each run, 200 random submitted assignments were used, which remained the same generation over generation. At the the end of each run, the best at the end is chosen. This is repeated several times to obtain an 'optimized' population.
53.
54. The second stage is largely the same, but in addition to the 200 submitted assignments, 100 'optimized' assignments are used in evaluation. At the end of these runs, the best of each is evaluated under the full submitted and optimized populations, and the best under that criteria is chosed. Alternatively, we can perform a round robin with the best-of-runs, add the scores to the previous, and use that criteria.
55.
56. 'Optimized' pop. code (Python 2.7, Numpy 1.7)
57. ---------------------------------------------
58. import numpy as np
59. import csv
60.
61. #Returns the phenotype of the given genome.
62. def expPheno(c1):
63.     temp = np.zeros(11, dtype=np.int)
64.     temp[-1] = 100
65.     temp[1:-1] = c1
66.     pheno = temp[1:] - temp[:-1]
67.     return pheno
68.
69. #Emulates the battles, written so no floats are necessary.
70. def canEval(c1, c2):
71.     p1 = expPheno(c1)
72.     p2 = expPheno(c2)
73.     bwins = np.sign(p1 - p2)
74.     #print bwins
75.     cval = (bwins + 1 )*np.array(range(1,11))
76.     #print cval
77.     tval = np.sum(cval)
78.     #print tval
79.     return np.sign(tval - 55) + 1
80.
81. def trueEval(c1, c2):
82.     bwins = np.sign(c1 - c2)
83.     #print bwins
84.     cval = (bwins + 1 )*np.array(range(1,11))
85.     #print cval
86.     tval = np.sum(cval)
87.     #print tval
88.     return np.sign(tval - 55) + 1
89.
90. #Implements single point crossover on two genotypes
91. def crossover(c1,c2):
92.     cut = np.random.randint(1, high = 9)
93.     out = np.array([c1, c2])
94.     out[:,cut:] = out[::-1,cut:]
95.     out = np.sort(out)
96.     return out
97.
98. #Implements a point mutation on the genotype using the binomial distribution
99. def mutate(c1, pos = None, force = False):
100.     vals = 101
101.     w = 1
102.     n = ((2*w +1)*vals) - 1
103.     if (pos == None):
104.         pos = np.random.randint(9)
105.     pn = (2*w + 1)*c1[pos] + w
106.     p = pn / float(n)
107.
108.     while True:
109.         r = np.random.binomial(n, p)
110.         new = r//(2*w + 1)
111.         if (not force):
112.             break
113.         if (new != c1[pos]):
114.             break
115.
116.     c1[pos] = new
117.     out = np.sort(c1)
118.     return out
119.
120. #The submitted strategies in the first round
121. subPop = np.genfromtxt('castle-solutions_fix.csv', dtype=np.int, delimiter=',',skip_header=1,usecols = (0,1,2,3,4,5,6,7,8,9))
122. sp = 1387
123.
124. rSize = 700
125. gNum = 50
126.
127. refPop = np.zeros((rSize, 9), dtype=np.int)
128.
129. for iter in range(rSize):
130.     pSize = 200
131.     evoPop = np.random.randint(101, size = (pSize, 9))
132.     evoPop = np.sort(evoPop)
133.
134.     sSize = 200
135.     sPop = np.random.permutation(subPop)
136.     sPop = sPop[:sSize,:]
137.     best = np.zeros(9, dtype=np.int)
138.     bSc = 0
139.
140.     for gen in range(gNum):
141.         scores = np.zeros(pSize, dtype=np.int)
142.
143.         #Evaluating genotypes
144.         for i in range(pSize):
145.             pheno = expPheno(evoPop[i,:])
146.             for j in range(sSize):
147.                 out = trueEval(pheno, sPop[j,:])
148.                 scores[i] += out
149.
150.         #argsort outputs the original indices of the items a hypothetical sorted list
151.         #The last entry is the index of the best scoring strategy
152.         rank = np.argsort(scores)
153.         best = evoPop[rank[pSize-1],:]
154.         bSc = scores[ rank[ pSize - 1 ] ]
155.
156.         #Replace last 20 with first 20 and mutates ranks 11-20
157.         for i in range(20):
158.             evoPop[rank[i],:] = evoPop[rank[i + pSize - 20],:]
159.
160.         for i in range(10):
161.             evoPop[rank[i],:] = mutate(evoPop[rank[i],:], force = True)
162.
163.         #Hypermutates next to last 20
164.         for i in range(20):
165.             for j in range(9):
166.                 evoPop[rank[i+20],:] = mutate(evoPop[rank[i + pSize - 20],:], pos = j , force = True)
167.
168.         #Random mutations for middle 120
169.         rk = np.random.permutation(rank[40:-40])
170.         for i in range(12):
171.             evoPop[rk[i],:] = mutate(evoPop[rk[i],:])
172.
173.         #Crossover with all but last 20
174.         cross = np.random.permutation(rank[20:])
175.         for i in range(90):
176.             out = crossover(evoPop[cross[2*i],:], evoPop[cross[2*i+1],:])
177.             evoPop[cross[2*i],:] = out[0,:]
178.             evoPop[cross[2*i + 1],:] = out[1,:]
179.
180.         #if (gen%5 == 4):
181.         #   print ""
182.         #   print gen
183.         #   print best
184.         #   print scores[ rank[ pSize - 1 ] ]
185.
186.     refPop[iter] = best
187.     print ""
188.     print iter
189.     print refPop[iter]
190.     print bSc
191.
192. with open('optGen.csv', 'wb') as wtag:
193.     write = csv.writer(wtag, delimiter=',')
194.     write.writerows(refPop)
195.
196.
197. Blended evaluation code (Python 2.7, Numpy 1.7)
198. -----------------------------------------------
199. import numpy as np
200. import csv
201.
202. #Returns the phenotype of the given genome.
203. def expPheno(c1):
204.     temp = np.zeros(11, dtype=np.int)
205.     temp[-1] = 100
206.     temp[1:-1] = c1
207.     pheno = temp[1:] - temp[:-1]
208.     return pheno
209.
210. #Emulates the battles, written so no floats are necessary.
211. def canEval(c1, c2):
212.     p1 = expPheno(c1)
213.     p2 = expPheno(c2)
214.     bwins = np.sign(p1 - p2)
215.     #print bwins
216.     cval = (bwins + 1 )*np.array(range(1,11))
217.     #print cval
218.     tval = np.sum(cval)
219.     #print tval
220.     return np.sign(tval - 55) + 1
221.
222. def trueEval(c1, c2):
223.     bwins = np.sign(c1 - c2)
224.     #print bwins
225.     cval = (bwins + 1 )*np.array(range(1,11))
226.     #print cval
227.     tval = np.sum(cval)
228.     #print tval
229.     return np.sign(tval - 55) + 1
230.
231. #Implements single point crossover on two genotypes
232. def crossover(c1,c2):
233.     cut = np.random.randint(1, high = 9)
234.     out = np.array([c1, c2])
235.     out[:,cut:] = out[::-1,cut:]
236.     out = np.sort(out)
237.     return out
238.
239. #Implements a point mutation on the genotype using the binomial distribution
240. def mutate(c1, pos = None, force = False):
241.     vals = 101
242.     w = 1
243.     n = ((2*w +1)*vals) - 1
244.     if (pos == None):
245.         pos = np.random.randint(9)
246.     pn = (2*w + 1)*c1[pos] + w
247.     p = pn / float(n)
248.
249.     while True:
250.         r = np.random.binomial(n, p)
251.         new = r//(2*w + 1)
252.         if (not force):
253.             break
254.         if (new != c1[pos]):
255.             break
256.
257.     c1[pos] = new
258.     out = np.sort(c1)
259.     return out
260.
261. #The submitted strategies in the first round
262. subPop = np.genfromtxt('castle-solutions_fix.csv', dtype=np.int, delimiter=',',skip_header=1,usecols = (0,1,2,3,4,5,6,7,8,9))
263. sp = 1387
264.
265. optPop = np.genfromtxt('optGen.csv', dtype=np.int, delimiter=',')
266. op = 700
267.
268. rSize = 400
269. gNum = 50
270.
271. pSize = 200
272. sSize = 200
273. oSize = 100
274.
275. refPop = np.zeros((rSize, 9), dtype=np.int)
276.
277. for iter in range(rSize):
278.     evoPop = np.random.randint(101, size = (pSize, 9))
279.     evoPop = np.sort(evoPop)
280.
281.     sPop = np.random.permutation(subPop)
282.     sPop = sPop[:sSize,:]
283.
284.     oPop = np.random.permutation(optPop)
285.     oPop = oPop[:oSize,:]
286.
287.     best = np.zeros(9, dtype=np.int)
288.     bSc = 0
289.
290.     for gen in range(gNum):
291.
292.         scores = np.zeros(pSize, dtype=np.int)
293.
294.         #Evaluating genotypes against submitted phenotypes
295.         for i in range(pSize):
296.             pheno = expPheno(evoPop[i,:])
297.             for j in range(sSize):
298.                 out = trueEval(pheno, sPop[j,:])
299.                 scores[i] += out
300.
301.
302.         #Evaluating genotypes against optimized phenotypes
303.         for i in range(pSize):
304.             for j in range(oSize):
305.                 out = canEval(evoPop[i,:], oPop[j,:])
306.                 scores[i] += out
307.
308.
309.         #argsort outputs the original indices of the items a hypothetical sorted list
310.         #The last entry is the index of the best scoring strategy
311.         rank = np.argsort(scores)
312.         best = evoPop[rank[pSize-1],:]
313.         bSc = scores[ rank[ pSize - 1 ] ]
314.
315.         #Replace last 20 with first 20 and mutates ranks 11-20
316.         for i in range(20):
317.             evoPop[rank[i],:] = evoPop[rank[i + pSize - 20],:]
318.
319.         for i in range(10):
320.             evoPop[rank[i],:] = mutate(evoPop[rank[i],:], force = True)
321.
322.         #Hypermutates next to last 20
323.         for i in range(20):
324.             for j in range(9):
325.                 evoPop[rank[i+20],:] = mutate(evoPop[rank[i + pSize - 20],:], pos = j , force = True)
326.
327.         #Random mutations for middle 120
328.         rk = np.random.permutation(rank[40:-40])
329.         for i in range(12):
330.             evoPop[rk[i],:] = mutate(evoPop[rk[i],:])
331.
332.         #Crossover with all but last 20
333.         cross = np.random.permutation(rank[20:])
334.         for i in range(90):
335.             out = crossover(evoPop[cross[2*i],:], evoPop[cross[2*i+1],:])
336.             evoPop[cross[2*i],:] = out[0,:]
337.             evoPop[cross[2*i + 1],:] = out[1,:]
338.
339.         #if (gen%5 == 4):
340.         #   print ""
341.         #   print gen
342.         #   print best
343.         #   print scores[ rank[ pSize - 1 ] ]
344.
345.     refPop[iter] = best
346.
347.     print ""
348.     print iter
349.     print refPop[iter]
350.     print bSc
351.
352.
353. #Comparing best of the runs above
354. hScores = np.zeros(rSize, dtype=np.int)
355.
356. for iter in range(rSize):
357.
358.     #Evaluating genotypes against submitted phenotypes
359.     pheno = expPheno(refPop[iter,:])
360.     for j in range(sp):
361.         out = trueEval(pheno, subPop[j,:])
362.         hScores[iter] += out
363.
364.
365.     #Evaluating genotypes against optimized phenotypes
366.     geno = refPop[iter,:]
367.     for j in range(op):
368.         out = canEval(geno, optPop[j,:])
369.         hScores[iter] += out
370.
371. hRank = np.argsort(hScores)
372. hBest = refPop[hRank[rSize-1],:]
373.
374. hPheno = expPheno(hBest)
375.
376. print ""
377. print hBest
378. print hPheno
379. print hScores[hRank[rSize-1]]
380. print hScores[hRank[rSize-1]] / float((op + sp)*2)
381. print ""
382.
384. tScores = np.copy(hScores)
385.
386. for i in range(rSize - 1):
387.     for j in range(i + 1, rSize):
388.         out = canEval(refPop[i,:], refPop[j,:])
389.         tScores[i] += out
390.         tScores[j] += 2 - out
391.
392. tRank = np.argsort(tScores)
393. tBest = refPop[tRank[rSize-1],:]
394.
395. tPheno = expPheno(tBest)
396.
397. print tBest
398. print tPheno
399. print tScores[tRank[rSize-1]]
400. print tScores[tRank[rSize-1]] / float((op + sp + rSize - 1)*2)
401.
402. #Saving best for examination
403. refStat = np.zeros((rSize, 11), dtype=np.int)
404.
405. refStat[:,:9] = refPop
406. refStat[:,9] = hScores
407. refStat[:,10] = tScores
408.
409. with open('blendEvo.csv', 'wb') as wtag:
410.     write = csv.writer(wtag, delimiter=',')
411.     write.writerows(refStat)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top