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.  
  383. #Adding head to head comparisons
  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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top