Целевая функция

Ключом к решению любой задачи оптимизации является целевая функция, и именно ее обычно труднее всего отыскать. Цель оптимизационного алгоритма состоит в том, чтобы найти такой набор входных переменных – в данном случае рейсов, – который минимизирует целевую функцию. Поэтому целевая функция должна возвращать значение, показывающее, насколько данное решение неудовлетворительно. Не существует никакого определенного масштаба неудовлетворительности; требуется лишь, чтобы возвращаемое значение было тем больше, чем хуже решение.

Часто, когда переменных много, бывает трудно сформулировать критерий, хорошее получилось решение или плохое. Рассмотрим несколько параметров, которые можно измерить в примере с групповым путешествием:

Цена

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

Суммарное время, проведенное всеми членами семьи в полете. Время ожидания

Время, проведенное в аэропорту в ожидании прибытия остальных членов группы. Время вылета

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

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

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

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

Определенная ниже функция getcost принимает во внимание полную стоимость поездки и общее время ожидания в аэропорту всеми членами семьи. Кроме того, она добавляет штраф $50, если машина возвращена в более поздний час, чем арендована. Добавьте эту функцию в файл optimization.py и, если хотите, включите в нее дополнительные факторы или измените соотношение между временем и деньгами. def schedulecost(sol): totalprice=0 latestarrival=0 earliestdep=24*60

for d in range(len(sol)/2): # Получить список прибывающих и убывающих рейсов origin=people[d][1]

outbound=flights[(origin,destination)][int(sol[d])] returnf=flights[(destination,origin)][int(sol[d+1])]

#       Полная цена равна сумме цен на билет туда и обратно totalprice+=outbound[2] totalprice+=returnf[2]

#       Находим самый поздний прилет и самый ранний вылет if latestarrival<getminutes(outbound[1]):

latestarrival=getminutes(outbound[1]) if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])

#       Все должны ждать в аэропорту прибытия последнего участника группы.

#       Обратно все прибывают одновременно и должны ждать свои рейсы.

totalwait=0

for d in range(len(sol)/2): origin=people[d][1]

outbound=flights[(origin,destination)][int(sol[d])] returnf=flights[(destination,origin)][int(sol[d+1])] totalwait+=latestarrival-getminutes(outbound[1]) totalwait+=getminutes(returnf[0])-earliestdep

#       Для этого решения требуется оплачивать дополнительный день аренды?

#       Если да, это обойдется в лишние $50!

if latestarrival>earliestdep: totalprice+=50

return totalprice+totalwait Логика этой функции очень проста, но суть вопроса она отражает. Улучшить ее можно несколькими способами. Так, в текущей версии предполагается, что все члены семьи уезжают из аэропорта вместе, когда прибывает самый последний, а возвращаются в аэропорт к моменту вылета самого раннего рейса. Можно поступить по-другому: если человеку приходится ждать два часа или дольше, то он арендует отдельную машину, а цены и время ожидания соответственно корректируются.

Протестируйте эту функцию в интерактивном сеансе:

>>> reload(optimization)

>>> optimization.schedulecost(s)

5285

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

Вы можете следить за любыми ответами на эту запись через 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