# coding: utf-8 import random # GA n = input() m = [] for i in range(n): m.append(input()) def generateGene(): tmp = [] table = m[:] for x in xrange(n): i = random.randint(0,len(table)-1) tmp.append(table[i]) del(table[i]) return tmp class Solution: def __init__(self, gene): self.gene = gene self.value = 0 if(len(gene)!=0): self.eval() def eval(self): discount = 0 for c in self.gene: self.value += max(c-discount,0) discount = (discount+c)%1000 NUM_POP = 10 # 少なくとも2以上かつ偶数にして GENERATION = 20 # 最初の個体群をランダム生成 pop = [Solution(generateGene()) for x in xrange(NUM_POP)] for gc in xrange(GENERATION): min_val = sum(m) max_val = -1 top_index = -1 top2_index = -1 # 評価補助テーブル生成 for i,s in enumerate(pop): if(s.value < min_val): min_val = s.value top2_index = top_index top_index = i if(s.value > max_val): max_val = s.value #print "max:", max_val, "min:", min_val pickup_table = [0]*n probability_sum = 0 for i in xrange(n): pickup_table[i] = max_val - pop[i].value probability_sum += pickup_table[i] # 評価の高さに基づいた確率により個体を交叉させ新個体を生成 left = NUM_POP - 2 #new_pop = [Solution(pop[top_index].gene[:]),Solution(pop[top2_index].gene[:])] top_s = Solution([]) top_s.gene = pop[top_index].gene[:] top_s.eval() top2_s = Solution([]) top2_s.gene = pop[top2_index].gene[:] top2_s.eval() new_pop = [top_s, top2_s] #print "top:", top_s.value, top_s.gene while(left>0): # 2個体pickする sum1 = 0 sum2 = 0 r1 = random.randint(0,probability_sum) r2 = random.randint(0,probability_sum) for s in pop: sum1 += s.value if(sum1>=r1): solution1 = s break for s in pop: sum2 += s.value if(sum2>=r2): solution2 = s break # 二点交叉 a,b = (random.randint(0,n),random.randint(0,n)) first, second = min(a,b), max(a,b) new1 = Solution([]) new1.gene = solution1.gene[:] new2 = Solution([]) new2.gene = solution2.gene[:] for i in range(first, second): new1.gene[i] = solution2.gene[i] new2.gene[i] = solution1.gene[i] new1.eval() new2.eval() # 生成した新個体をテーブルに追加 new_pop.append(new1) new_pop.append(new2) left -= 2 pop = new_pop top = pop[0] for s in pop: if(s.value < top.value): top = s print top.value