Оптимизация с учетом предпочтений

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

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

Оптимизация распределения студентов по комнатам

В этом разделе мы решим задачу о распределении студентов по комнатам в общежитии с учетом их основного и альтернативного пожеланий. Хотя формулировка довольно специфична, ее можно легко обобщить на похожие задачи, – тот же самый код годится для распределения игроков по столам в онлайновой карточной игре, для распределения ошибок между разработчиками в большом программном проекте и даже для распределения работы по дому между прислугой. Как и раньше, наша цель – собрать информацию об отдельных людях и найти такое сочетание, которое приводит к оптимальному результату. В нашем примере будет пять двухместных комнат и десять претендующих на них студентов. У каждого студента есть основное и альтернативное пожелание. Создайте новый файл dorm.py и добавьте в него список комнат, список людей и два пожелания для каждого человека: import random import math

#  Двухместные комнаты

dorms=[‘Zeus’,’Athena’,’Hercules’,’Bacchus’,’Pluto’]

#  Люди и два пожелания у каждого prefs=[(‘Toby’, (‘Bacchus’, ‘Hercules’)),

(‘Steve’, (‘Zeus’, ‘Pluto’)), (‘Andrea’, (‘Athena’, ‘Zeus’)), (‘Sarah’, (‘Zeus’, ‘Pluto’)), (‘Dave’, (‘Athena’, ‘Bacchus’)), (‘Jeff’, (‘Hercules’, ‘Pluto’)), (‘Fred’, (‘Pluto’, ‘Athena’)), (‘Suzie’, (‘Bacchus’, ‘Hercules’)), (‘Laura’, (‘Bacchus’, ‘Hercules’)), (‘Neil’, (‘Hercules’, ‘Athena’))]

Сразу видно, что удовлетворить основное пожелание каждого человека не удастся, так как на два места в комнате Bacchus имеется три претендента. Поместить любого из этих трех в ту комнату, которую он указал в качестве альтернативы, тоже невозможно, так как в комнате Hercules всего два места.

Эта задача намеренно сделана небольшой, чтобы проследить логику было просто. Но в реальности может быть две-три сотни студентов, претендующих на множество комнат в общежитии. Так как в приведенном примере общее число вариантов порядка 100 000, то можно перебрать их все и найти оптимальный. Но если комнаты будут четырехместными, то количество вариантов будет исчислять триллионами.

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

что в таком представлении отсутствует ограничение, запрещающее помещать в одну комнату более двух студентов. Список, состоящий только из нулей, означает, что всех поместили в комнату Zeus, а это не соответствует никакому решению задачи.

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

Более правильный подход – отыскать такой способ представления решений, при котором любое представимое решение допустимо. Допустимое еще не означает хорошее, просто в каждой комнате должно оказаться ровно два студента. Можно, например, поступить следующим образом. Будем считать, что в каждой комнате есть два отсека, то есть всего их в нашем случае будет десять. Каждому студенту по очереди назначается один из незанятых отсеков; первого можно поместить в любой из десяти отсеков, второго – в любой из оставшихся девяти и т. д. Область определения для поиска должна быть построена с учетом этого ограничения. Добавьте такие строки в файл dorm.py: # [(0,9),(0,8),(0,7),(0,6),…,(0,0)]

domain=[(0,(len(dorms)*2)-i-1) for i in range(0,len(dorms)*2)] Следующая функция, печатающая решение, иллюстрирует принцип работы отсеков. Сначала она создает список отсеков, по два на каждую комнату. Затем она в цикле пробегает по всем числам, составляющим решение, и для каждого находит номер комнаты в данной позиции списка отсеков. Это та комната, в которую поместили студента. Функция печатает имя студента и название комнаты, а затем удаляет отсек из списка, чтобы в него нельзя было поместить другого студента. После завершающей итерации распределение студентов по комнатам распечатано, а список отсеков пуст. Добавьте эту функцию в файл dorm.py: def printsolution(vec): slots=[]

#       Создаем по два отсека на каждую комнату for i in range(len(dorms): slots+=[i,i]

#       Цикл по распределению студентов по комнатам for i in range(len(vec)):

x=int(vec[i])

#       Выбираем любой отсек из оставшихся dorm=dorms[slots[x]]

#       Печатаем имя студента и название комнаты, в которую он попал print prefs[i][0],dorm

#      Удаляем этот отсек del slots[x]

В интерактивном сеансе импортируйте файл и распечатайте решение: >>> import dorm

>>> dorm.printsolution([0,0,0,0,0,0,0,0,0,0])

Toby Zeus Steve Zeus Andrea Athena Sarah Athena Dave Hercules Jeff Hercules Fred Bacchus Suzie Bacchus Laura Pluto Neil Pluto

Если вы захотите изменить числа, чтобы посмотреть на другие решения, то не забывайте, что числа не должны выходить за пределы отведенных для них диапазонов. Первое число в списке должно находиться в диапазоне от 0 до 9, второе – от 0 до 8 и т. д. Если это ограничение будет нарушено, функция возбудит исключение. Поскольку функции оптимизации будут выбирать числа из диапазонов, заданных в параметре domain, то мы в реализации алгоритма с этой проблемой не столкнемся.

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

Целевая функция работает аналогично функции печати. Создается начальный список отсеков, и уже использованные отсеки из него удаляются. Стоимость вычисляется путем сравнения комнаты, в которую студент помещен, с двумя его пожеланиями. Стоимость не изменяется, если студенту досталась та комната, в которую он больше всего хотел поселиться; увеличивается на 1, если это второе из его пожеланий; и увеличивается на 3, если он вообще не хотел жить в этой комнате. def dormcost(vec): cost=0

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

#    Цикл по студентам

for i in range(len(vec)): x=int(vec[i]) dorm=dorms[slots[x]] pref=prefs[i][1]

#      Стоимость основного пожелания равна 0, альтернативного – 1 if pref[0]==dorm: cost+=0

elif pref[1]==dorm: cost+=1 else: cost+=3

#      Если комната не входит в список пожеланий, стоимость увеличивается на 3

# Удалить выбранный отсек del slots[x]

return cost

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

Выполнение оптимизации

Наличия представления решений, целевой функций и функции печати результатов достаточно для запуска написанных ранее функций оптимизации. Введите следующие команды: >>> reload(dorm)

>>> s=optimization.randomoptimize(dorm.domain,dorm.dormcost) >>> dorm.dormcost(s)

18

>>> optimization.geneticoptimize(dorm.domain,dorm.dormcost)

13 10

4

>>> dorm.printsolution(s)

Toby Athena Steve Pluto Andrea Zeus Sarah Pluto Dave Hercules Jeff Hercules Fred Bacchus Suzie Bacchus Laura Athena Neil Zeus

Можете и тут поиграть с параметрами – вдруг генетический алгоритм сможет найти решение быстрее.

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