SA.py

def eval_constraints(sq, n):
    fitness = 0
    totalRowDiff = 0
    totalColDiff = 0
    rightDiagonal = 0
    leftDiagonal = 0
    for row in range(0, len(sq)):
        sum_row = 0
        sum_col = 0
        for col in range(0, len(sq)):
            sum_col += sq[col][row]
            sum_row += sq[row][col]
            if row == col:
               leftDiagonal += sq[row][col]
            if row+col == len(sq)-1:
               rightDiagonal += sq[row][col]
        totalRowDiff += abs(sum_row-n)
        totalColDiff += abs(sum_col-n)
    return abs(rightDiagonal-n)+abs(leftDiagonal-n)+totalColDiff+totalRowDiff

def swap_values(sq, times):
    temp = list(sq)
    for i in range(0, times):
        r1 = random.randint(0,len(sq)-1)
        c1 = random.randint(0,len(sq)-1)
        r2 = random.randint(0,len(sq)-1)
        c2 = random.randint(0,len(sq)-1)
        temp[r1][c1], temp[r2][c2] = temp[r2][c2],temp[r1][c1]
    return temp

def initial_square(l):
    return [[l[j] for j in range(i*int(np.sqrt(len(l))), (i+1)*int(np.sqrt(len(l))))] for i in range(0, int(np.sqrt(len(l))))]



def simulated_annealing(l, t):
    iter = 0
    initial_temp = 1.0
    steps = 500
    cooling = 0.97
    constant = 0.01
    sq = initial_square(l)
    n = sum(l)/int(np.sqrt(len(l)))
    cost = eval_constraints(sq, n)
    temp = initial_temp
    valid = False
    c_time = time.clock()
    while not valid:
      if cost is 0:
         valid = True
         break
      temp *= cooling
      ref_cost = cost
      for i in range(0, steps):
          temp_sq = swap_values(sq, 1)
          print temp_sq
          n_cost = eval_constraints(temp_sq, n)
          if n_cost < cost or np.exp(-(n_cost-cost)/(temp*constant)) > np.random.ranf():
             cost = n_cost
             sq = temp_sq
          if cost is 0:
             valid = True
             break
      if ref_cost != cost:
         temp /= cooling
      print 'Iteration: %d | Cost: %d' % (iter, cost)
      iter += 1
      if time.clock() - c_time > t:
         break
    return [sq, valid]