# [9, 8, 7, 6,..., 1]
domain = [i for i in xrange(9, 0, -1)]

def dorm_cost(vec):
 cost=0

 # Создаем список отсеков, т.е. первые 2 места - 0 отсек и т.д.
 slots = [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]

 # Цикл по студентам, i - порядковый номер студента
 for i in xrange(len(vec)):
  x = int(vec[i])
  dorm = dorms[slots[x]]
  pref = prefs[i][1]
  print x, '->', slots[x],'->', prefs[i][0], pref, '->', dorm

  # Стоимость основного пожелания равна 0, альтернативного – 1
  # Если комната не входит в список пожеланий, стоимость увеличивается на 3
  if pref[0] == dorm: cost += 0
  elif pref[1] == dorm: cost += 1
  else: cost += 3

  # Удалить выбранны
й отсек
  # Это самое важное действие тут,
  # прошу особо обратить на него внимание и учесть, что элементы сдвигаются
  del slots[x]

 return cost

При конструировании целевой функции полезно стремиться к тому, чтобы стоимость идеального решения (в данном случае каждый студент заселился в комнату, которую поставил на первое место в своем списке предпочтений) была равна нулю. В рассматриваемом примере мы уже убедились, что идеальное решение недостижимо, но, зная о том, что его стоимость равна нулю, можно оценить, насколько мы к нему приблизились. У этого правила есть еще одно достоинство – алгоритм оптимизации может прекратить поиск, если уже найдено идеальное решение.

peoples = [('Seymour','BOS'),
    ('Franny','DAL'),
    ('Zooey','CAK'),
    ('Walt','MIA'),
    ('Buddy','ORD'),
    ('Les','OMA')]

# место назначения
destination = 'LGA'

# словарь рейсов

flights = {('LGA', 'CAK'): [('6:58', '9:01', 238), ('8:19', '11:16', 122), ('9:58', '12:56', 249), ('10:32', '13:16', 139), ('12:01', '13:41', 267), ('13:37', '15:33', 142), ('15:50', '18:45', 243), ('16:33', '18:15', 253), ('18:17', '21:04', 259), ('19:46', '21:45', 214)], ('DAL', 'LGA'): [('6:12', '10:22', 230), ('7:53', '11:37', 433), ('9:08', '12:12', 364), ('10:30', '14:57', 290), ('12:19', '15:25', 342), ('13:54', '18:02', 294), ('15:44', '18:55', 382), ('16:52', '20:48', 448), ('18:26', '21:29', 464), ('20:07', '23:27', 473)], ('LGA', 'BOS'): [('6:39', '8:09', 86), ('8:23', '10:28', 149), ('9:58', '11:18', 130), ('10:33', '12:03', 74), ('12:08', '14:05', 142), ('13:39', '15:30', 74), ('15:25', '16:58', 62), ('17:03', '18:03', 103), ('18:24', '20:49', 124), ('19:58', '21:23', 142)], ('LGA', 'MIA'): [('6:33', '9:14', 172), ('8:23', '11:07', 143), ('9:25', '12:46', 295), ('11:08', '14:38', 262), ('12:37', '15:05', 170), ('14:08', '16:09', 232), ('15:23', '18:49', 150), ('16:50', '19:26', 304), ('18:07', '21:30', 355), ('20:27', '23:42', 169)], ('LGA', 'OMA'): [('6:19', '8:13', 239), ('8:04', '10:59', 136), ('9:31', '11:43', 210), ('11:07', '13:24', 171), ('12:31', '14:02', 234), ('14:05', '15:47', 226), ('15:07', '17:21', 129), ('16:35', '18:56', 144), ('18:25', '20:34', 205), ('20:05', '21:44', 172)], ('OMA', 'LGA'): [('6:11', '8:31', 249), ('7:39', '10:24', 219), ('9:15', '12:03', 99), ('11:08', '13:07', 175), ('12:18', '14:56', 172), ('13:37', '15:08', 250), ('15:03', '16:42', 135), ('16:51', '19:09', 147), ('18:12', '20:17', 242), ('20:05', '22:06', 261)], ('CAK', 'LGA'): [('6:08', '8:06', 224), ('8:27', '10:45', 139), ('9:15', '12:14', 247), ('10:53', '13:36', 189), ('12:08', '14:59', 149), ('13:40', '15:38', 137), ('15:23', '17:25', 232), ('17:08', '19:08', 262), ('18:35', '20:28', 204), ('20:30', '23:11', 114)], ('LGA', 'DAL'): [('6:09', '9:49', 414), ('7:57', '11:15', 347), ('9:49', '13:51', 229), ('10:51', '14:16', 256), ('12:20', '16:34', 500), ('14:20', '17:32', 332), ('15:49', '20:10', 497), ('17:14', '20:59', 277), ('18:44', '22:42', 351), ('19:57', '23:15', 512)], ('LGA', 'ORD'): [('6:03', '8:43', 219), ('7:50', '10:08', 164), ('9:11', '10:42', 172), ('10:33', '13:11', 132), ('12:08', '14:47', 231), ('14:19', '17:09', 190), ('15:04', '17:23', 189), ('17:06', '20:00', 95), ('18:33', '20:22', 143), ('19:32', '21:25', 160)], ('ORD', 'LGA'): [('6:05', '8:32', 174), ('8:25', '10:34', 157), ('9:42', '11:32', 169), ('11:01', '12:39', 260), ('12:44', '14:17', 134), ('14:22', '16:32', 126), ('15:58', '18:40', 173), ('16:43', '19:00', 246), ('18:48', '21:45', 246), ('19:50', '22:24', 269)], ('MIA', 'LGA'): [('6:25', '9:30', 335), ('7:34', '9:40', 324), ('9:15', '12:29', 225), ('11:28', '14:40', 248), ('12:05', '15:30', 330), ('14:01', '17:24', 338), ('15:34', '18:11', 326), ('17:07', '20:04', 291), ('18:23', '21:35', 134), ('19:53', '22:21', 173)], ('BOS', 'LGA'): [('6:17', '8:26', 89), ('8:04', '10:11', 95), ('9:45', '11:50', 172), ('11:16', '13:29', 83), ('12:34', '15:02', 109), ('13:40', '15:37', 138), ('15:27', '17:18', 151), ('17:11', '18:30', 108), ('18:34', '19:36', 136), ('20:17', '22:22', 102)]}

Например, в решении, представленном списком [1,4,3,2,7,3,6,3,2,4,5,3]
Сеймур (Seymour) летит первым рейсом из Бостона в Нью-Йорк и четвертым рейсом из Нью-Йорка в Бостон, а Фрэнни (Franny) – третьим рейсом из Далласа в Нью-Йорк и вторым обратно.

def hill_climb(domain, costf):

 # Выбрать случаиное решение
 sol = [random.randint(0, domain[i]) for i in xrange(len(domain))]
 best = costf(sol)

 # Главныи цикл
 is_stop = False
 while not is_stop:
  # Создать список соседних решении
  neighbors = []
  for j in xrange(len(domain)):

   # Отходим на один шаг в каждом направлении
   if 0 < sol[j] < 9:
    neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])
    neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])

   if 0 == sol[j]:
    neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])

   if sol[j] == domain[j]:
    neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])

  # Ищем наилучшее из соседних решении

  is_stop = True
  for j in xrange(len(neighbors)):
   cost = costf(neighbors[j])
   if cost < best:
    is_stop = False
    best = cost
    sol = neighbors[j]

 return sol, best

result, score = hill_climb(domain, schedule_cost)
print result, score

Для выбора начального решения эта функция генерирует случайный список чисел из заданного диапазона. Соседи текущего решения ищутся путем посещения каждого элемента списка и создания двух новых списков, в одном из которых этот элемент увеличен на единицу, а в другом уменьшен на единицу. Лучшее из соседних решений становится новым решением. 

Из рисунка видно, что, спускаясь по склону, мы необязательно отыщем наилучшее возможное решение. Найденное решение будет локальным минимумом, то есть лучшим из всех в ближайшей окрестности, но это не означает, что оно вообще лучшее. Решение, лучшее среди всех возможных, называется глобальным минимумом, и именно его хотят найти все алгоритмы оптимизации. Один из возможных подходов к решению проблемы называется спуском с горы со случайным перезапуском. В этом случае алгоритм спуска выполняется несколько раз со случайными начальными точками в надежде, что какое-нибудь из найденных решений будет близко к глобальному минимуму. Так же, все усугубляется тем, что у такой ф-ии как наша, большая импульсивность (много локальных минимумов и максимумов), очень не линейная скорость роста в разных точках, в общем очень много факторов, с учетом того, что мы рассматриваем ф-ию в 12 мерном пространстве и в каждом из них она ведет себя по-разному…

Алгоритм имитации отжига

Алгоритм имитации отжига навеян физическими аналогиями. Отжигом называется процесс нагрева образца с последующим медленным охлаждением. Поскольку сначала атомы заставляют попрыгать, а затем постепенно «отпускают вожжи», то они переходят в новую низко-энергетичную конфигурацию.

Иногда необходимо перейти к худшему решению, чтобы найти лучшее. Алгоритм имитации отжига работает, потому что всегда готов перейти к лучшему решению, но ближе к началу процесса соглашается принять и худшее. По мере того как процесс развивается, алгоритм соглашается на худшее решение все с меньшей охотой, а в конце работы принимает только лучшее. Вероятность того, что будет принято решение с более высокой стоимостью, рассчитывается по формуле:

Поскольку температура (готовность принять худшее решение) вначале очень высока, то показатель степени близок к 0, поэтому вероятность равна почти 1. По мере уменьшения температуры разность между высокой стоимостью и низкой стоимостью становится более значимой, а чем больше разность, тем ниже вероятность, поэтому алгоритм из всех худших решений будет выбирать те, что лишь немногим хуже текущего.

def annealing_optimize(domain, costf, T=10000.0, cool=0.99, step=1):
 
 # Выбрать случаиное решение
 vec = [random.randint(0, domain[i]) for i in xrange(len(domain))]

 while T > 0.1:
  # Выбрать один из индексов
  i = random.randint(0, len(domain)-1)

  # Выбрать направление изменения
  dir = random.randint(-step, step)

  # Создать новыи список, в котором одно значение изменено
  vecb = vec[:]
  vecb[i] += dir
  if vecb[i] < 0: vecb[i] = 0
  elif vecb[i] > domain[i]: vecb[i] = domain[i]

  # Вычислить текущую и новую стоимость
  ea = costf(vec)
  eb = costf(vecb)
  p = pow(math.e, (-eb-ea)/T)

  # Новое решение лучше? Если нет, метнем кости
  if (eb < ea or random.random() < p):
   vec = vecb      

  # Уменьшить температуру
  T = T * cool
 return vec, eb

result, score = annealing_optimize(domain, schedule_cost)
print result, score

На каждой итерации в качестве i случайно выбирается одна из переменных решения, а dir случайно выбирается межд