Случайный поиск

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

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

Второй параметр, costf, – это целевая функция; в нашем примере в этом качестве используется schedulecost. Она передается в виде параметра, чтобы алгоритм можно было использовать повторно и для других задач оптимизации. Алгоритм случайным образом генерирует 1000 гипотез и для каждой вызывает функцию costf. Возвращается наилучшая гипотеза (с минимальной стоимостью). Добавьте в файл optimization.py следующую функцию:

def randomoptimize(domain,costf): best=999999999 bestr=None

for i in range(1000): # Выбрать случайное решение r=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]

#         Вычислить его стоимость cost=costf(r)

#        Сравнить со стоимостью наилучшего найденного к этому моменту решения if cost<best:

best=cost bestr=r return r

Разумеется, 1000 гипотез – очень малая доля от общего числа возможностей. Однако в этом примере хороших (если не оптимальных) решений много, поэтому, сделав тысячу попыток, есть шанс наткнуться на что-нибудь приемлемое. Запустите функцию в интерактивном сеансе: >>> reload(optimization)

>>> domain=[(0,8)]*(len(optimization.people)*2) >>> s=optimization.randomoptimize(domain,optimization.schedulecost) >>> optimization.schedulecost(s)

3328

>>> optimization.printschedule(s)

Seymour Boston 12:34-15:02 $109 12:08-14:05 $142 Franny Dallas 12:19-15:25 $342 9:49-13:51 $229

Zooey Akron 9:15-12:14 $247 15:50-18:45 $243 Walt Miami 15:34-18:11 $326 14:08-16:09 $232 Buddy Chicago 14:22-16:32 $126 15:04-17:23 $189 Les Omaha 15:03-16:42 $135 6:19-8:13 $239

Благодаря элементу случайности ваши результаты будут отличаться от представленных выше. Найденное решение не слишком хорошее, потому что Зуи (Zooey) придется ждать в аэропорту шесть часов, пока не прилетит Уолт (Walt), но могло быть гораздо хуже. Попробуйте выполнить эту функцию несколько раз и посмотрите, сильно ли будет меняться стоимость. А можете увеличить число итераций до 10 000 и полюбопытствовать, удастся ли улучшить результаты таким способом.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100