TGINSIGHT SIMILAR POSTS
Изходен канал @clockstackwheels · Post #1084 · 9.04
В общем, была задача на оптимизацию плана работ: есть набор заказов, и в каждом N тасков. Таски могут зависеть друг от друга или нет, имеют длительность и тип. Ещё есть M работников, каждый из которых может выполнять таски только определённых типов, причём, у каждого своя скорость. Если все таски в заказе выполнены, фирма получает сколько-то денег. У заказа есть дедлайн, за просрочку штраф (за каждый день просрочки), который вычитается из цены заказа. И ещё фирма тратит деньги за каждый день своей работы независимо от того, как загружены её сотрудники (то есть просто платит зарплаты по сути). Ещё важен учёт праздников и выходных. Нужно заработать на определённом наборе заказов и работников как можно больше денег. Полный текст задачи и код программы проверки есть в репозитории. Эта задача является изменённым заказом, который мы с напарником решали в реальной жизни: оптимизация работы печатных станков для типографии. Правда, тогда и мы справились так себе, и заказчик в итоге сначала захотел всё вручную сам делать, а потом и вовсе похоронил проект при смене директора. !!! Не читайте дальше, если хотите сначала попробовать решить самостоятельно, потому что я сейчас опишу эффективные подходы и результаты. ________________________________________ Так вот. Мы с другим экспертом Андреем сразу сели и написали разные варианты, чтобы задать шкалу, по которой будем оценивать решения команд. За пару часов я собрал примитивный жадный алгоритм, который сортировал заказы по прибыльности и укладывал в сетку кое-как, это дало нам нижнюю оценку. Мой алгоритм заработал ~75 млн виртуальных рублей, мы решили для оценки поставить нижней границей 40 млн. То есть всё, что ещё ниже, оценивалось в ноль баллов за качество оптимизации. Затем Андрей закрылся дома на три дня и вышел на свет со сложным жадным алгоритмом, который очень хитро сортировал заказы и очень хитро укладывал их в сетку, попутно выбирая разные способы этой укладки в зависимости от конкретного заказа. Это позволило заработать ~275 млн рублей. Мы сделали верхней границей для оценки 280 млн. К сожалению, в итоге только две команды из десяти прошли нижнюю границу, заработав, соответственно, ~91 и ~105 млн. К верхней границе не приблизился никто. И у четырёх команд алгоритм вообще не смог уложить без нарушений задачи в сетку (то есть, например, произвольно менял длительности, накладывал задачи друг на друга, давал одному работнику две задачи в один момент и так далее). Важной ошибкой команд, на мой взгляд, являлся тот факт, что никто не воспользовался возможностью запустить алгоритм на несколько минут и дать ему поработать. По условиям задания, можно было тянуть до 5 минут на одну оптимизацию, но по факту решения команд отрабатывали за единицы и десятки секунд. На самом конкурсе, пока команды работали, я решил попробовать сделать быстрое (по времени написания) но эффективное решение. Сначала попробовал жадную сортировку + доведение до лучшего варианта методом имитации отжига. В качестве нового состояния я просто менял местами заказы целиком. Этот вариант работал пару минут и дал мне около ~200 млн дохода. К слову, команда-лидер использовала такой же подход, просто не докрутила число итераций и температуру. Ну и потом я взял готовую либу по реализации классической генетики с особями и скрещиванием. Особью был массив с приоритетами заказов (которые конечно же нужно было аккуратно уложить чистым алгоритмом). Тип скрещивания: scattered. Всего 15 поколений по 20 особей, и это за минуту-полторы давало ~230-240 млн. Считаю, что для конкурса это самый лучший выбор: пишется одним человеком за день и даёт почти максимум, при этом легко настраивается на нужную длительность работы, легко параллелится. Ну а потом уже дома я посидел и накодил свой вариант сложного жадного с плавающим окном перебора отсортированных заказов и плавающей же укладкой по работникам. Такая штука за две минуты зарабатывает ~281 млн. Но за три дня в условиях стресса я бы такое не сделал, скорее всего. #dev
Hashtags
Търсене: #part1fall2020
@deep_learning_school_news · Post #249 · 07.02.2021 г., 10:38
#part1fall2020 Решили продлить дедлайн по проектам первой и второй частей на неделю (раз мы все равно пока проверяем домашки) Деллайны скоро обновятся и на Степике. Если вы уже послали проект в форму, согласуйте с руководителем проекта формат досдачи.
Hashtags
@deep_learning_school_news · Post #246 · 04.02.2021 г., 14:40
#part1fall2020 Добрый вечер! Обращаемся к тем, кто сейчас заканчивает первую часть курса. Мы уже делали опрос о промежуточных итогах курса. Теперь, когда все занятия уже выложены, очень просим вас пройти финальный опрос. Напишите ваши самые важные мысли по занятиям в текстовые поля. Нам очень важен ваш фидбек, чтобы сделать курс лучше. Если по некоторым занятиям вам сказать нечего, это не страшно, далеко не все вопросы обязательные. Заранее спасибо!
Hashtags
@deep_learning_school_news · Post #245 · 27.01.2021 г., 12:42
#part1fall2020 Мы выложили на Степик ещё несколько дополнительных модулей для обоих потоков! Среди прочего там есть лекции от компании Яндекс, а также лекция от Kaggle-мастера Владислава Шахрая о том, как побеждать в конкурсах по анализу данных. Смотрим!
Hashtags
@deep_learning_school_news · Post #242 · 06.01.2021 г., 23:47
#part1fall2020 Всем привет! Как те, кто был на вебинаре, уже знают, мы решили перенести дедлайн по выбору итоговых проектов на 10 января. Срок выполнения проектов мы продлеваем до 7 февраля, 23:59. Срок выполнения последнего домашнего задания для продвинутого потока продлён до 17 января, 23:59 Кроме того, для тех, кто уже зарегистрировался, мы выкладываем список назначенных проектов. Заходите в соответствующий чат в Slack и начинайте работу! Почти во всех чатах уже появилась вступительная информация к выполнению. Тем, кто ещё не выбирал проекты, советуем поскорее определиться и заполнить форму. Предлагаем вам записываться на один проект и сразу начинать работу по нему, чтобы не ждать результатов распределения
Hashtags
@deep_learning_school_news · Post #241 · 04.01.2021 г., 16:42
#part1fall2020 Всем привет! Напоминаем, что через 20 минут состоится трансляция с ответами на вопросы о последних занятиях курса и итоговых проектах. Вопросы можно задать в комментариях к предыдущему посту в этом канале, а также во время трансляции в чате youtube. Ссылка на трансляцию
Hashtags
@deep_learning_school_news · Post #240 · 03.01.2021 г., 14:34
#part1fall2020 Всем привет! Завтра в 20:00 мы проведём вебинар по последним темам курса, а также про выполнение итогового проекта. Ссылка на вебинар появится здесь. Вы можете задать волнующие вас вопросы к вебинару в комментариях к этому посту или на самом мероприятии
Hashtags
@deep_learning_school_news · Post #238 · 02.01.2021 г., 01:45
#part1fall2020 Всем привет! На Stepik появилось много всего интересного: например, новые модули у базового и продвинутого потоков, которые помогут вам выполнить итоговые проекты, а также сама новость об итоговом проекте (в последнем модуле курса) Кроме того, мы создали в Slack чаты для выполнения проектов. После регистрации на проекты обязательно выбирайте чат с вашей тематикой и вступайте. Напоминаем, что дедлайн по регистрации на проекты — вечер 5 января
Hashtags
@deep_learning_school_news · Post #234 · 24.12.2020 г., 10:52
#part1fall2020 Всем привет! Вслед за проектами второй части, выкладываем долгожданную информацию о заключительных проектах курса на первой части! Все необходимые сведения есть в текстовом документе. Для записи на проект обязательно заполните форму регистрации.
Hashtags
@deep_learning_school_news · Post #230 · 13.12.2020 г., 02:14
#part1fall2020 Всем привет! Хотим рассказать о том, как будет устроено окончание семестра для базового и продвинутого потоков. — У базового потока появилось новое домашнее задание. Дедлайн по нему: 31 декабря 23:59:) — У продвинутого потока появился новый модуль по детекции. Впереди у базового и продвинутого потоков будет ещё по одному домашнему заданию, дедлайн у которого будет уже в январе. Также обоим потокам предстоит выполнение итогового проекта. Темы проектов будут известны в ближайшее время: мы надеемся, что успеем сфорировать полный список в середине следующей недели. После публикации списка тем у вас будет чуть больше недели, чттобы выбрать тему проекта. Выполнение проектов продлится до второй половины января. Всем хорошего окончания курса! Скоро мы напишем о предварительных порогах для получения дипломов.
Hashtags
@deep_learning_school_news · Post #223 · 30.11.2020 г., 22:34
#part1fall2020 Позади осталась большая часть курса! В связи с этим мы хотели бы спросить ваше мнение о пройденном материале: что вам понравилось, что не понравилось, какие темы были легкими, какие — сложными. Пожалуйста, заполните анкету по ссылке. Это очень поможет нам сделать курс лучше в следующие запуски. В том числе нам ценно мнение тех, кто по какой-то причине курс не закончил.
Hashtags
@deep_learning_school_news · Post #218 · 24.11.2020 г., 12:48
#part1fall2020 В связи с событиями во Владивостоке (полгорода без света), решили подвинуть дедлайн по домашнему заданию "Решение ML-задачи и Kaggle" на базовом потоке слегка вперёд. Теперь мягкий дедлайн — 28.11, жёсткий — 01.12.
Hashtags
@deep_learning_school_news · Post #212 · 18.11.2020 г., 09:53
#part1fall2020 Всем привет! Выложили новые модули для базового и продвинутого потока, а также домашнее задание для продвинутого потока. Дедлайн домашнего задания — 3 декабря. Задание снова представляет собой контест на Kaggle.com. Советуем приступать к выполнению заранее. Для базового потока на этой неделе домашнего задания не будет, зато будет на следующей неделе.
Hashtags