Введение в линейное программирование на Python |
||
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Разработка ИИГородские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Авторизация |
2022-05-07 21:25 Представьте, что вы играете в стратегию. У вас есть:
Наездники сильнее лучников, которые, в свою очередь, сильнее мечников. В следующей таблице приведена информация о силе и стоимости каждого юнита: Итак, у вас есть 1200 еды, 800 дерева и 600 золота. Как с помощью этих ресурсов максимизировать силу армии? Можно просто найти юнит с наилучшим соотношением силы/стоимости, приобрести их как можно больше, а затем повторить процесс с оставшимися двумя. Но подход “угадай и проверь” может даже не быть оптимальным. Теперь представьте, что у вас миллионы юнитов и ресурсов. Предыдущая стратегия, скорее всего, не приведет к наилучшему варианту. Для решения этой задачи возможно применение алгоритма машинного обучения (например, генетический алгоритм), но, как и в первом случае, нет гарантии на оптимальный результат. К счастью, существует метод, который решит эту задачу наилучшим образом, — линейное программирование (или линейная оптимизация), входящее в область исследования операций. Сегодня мы будем использовать этот метод для определения лучшего количества мечников, лучников и наездников с целью создания армии с максимально возможной силой. 1. Решатели (солверы) Для линейного программирования в Python существуют разные библиотеки — многоцелевая SciPY, удобная для новичков PuLP, всеохватывающая Pyomo и многие другие. Сегодня мы воспользуемся инструментом Google OR-Tools, который поставляется c несколькими готовыми решателями и имеет наибольшее количество звезд на GitHub. Вы можете запустить код из этого руководства, используя блокнот Google Colab. Если установка не прошла, перезапустите ядро и попробуйте снова: иногда случаются неполадки. !python -m pip install --upgrade --user -q ortools Все эти библиотеки имеют скрытое преимущество: они выступают в роли интерфейсов, чтобы использовать одну модель с разными решателями. Такие солверы, как Gurobi, Cplex и SCIP, имеют собственные API, но модели, которые они создают, привязаны к конкретному решателю. OR-Tools позволяет использовать абстрактный путь моделирования задачи. Затем мы можем выбрать один или несколько решателей для поиска оптимального варианта. Таким образом, созданную модель можно использовать многократно! Google OR-Tools имеет собственный решатель линейного программирования под названием GLOP (Google Linear Optimization Package). Это проект с открытым исходным кодом, созданный командой Google по исследованию операций и написанный на С++. Также доступен SCIP — некоммерческий решатель, созданный в 2005 году и получающий обновления и поддержку по сей день. Как вариант, можно использовать коммерческие версии типа Gurobi и Cplex. Однако вам придется установить их поверх OR-Tools и получить соответствующую лицензию (что может стоить дорого). Для начала попробуем GLOP. # Импортируем оболочку OR-Tools для линейного программирования # Создаем решатель с помощью бэкенда GLOP 2. Переменные Мы создали копию решателя OR-Tools с помощью GLOP. Как же использовать линейное программирование? Первым делом необходимо определить переменные, которые нужно оптимизировать. В данном примере имеется три значения: количество мечников, лучников и наездников в армии. OR-Tools принимает три типа переменных:
Нам нужно круглое число юнитов в армии, поэтому выбираем Переведите это в код. Бесконечность заменяем на # Создаем переменные для оптимизации 3. Ограничения Переменные определены, но ограничения не менее важны. Как бы парадоксально это не звучало, но добавление большего количества ограничений помогает решателю быстрее находить оптимальное решение. В чем же дело? Солвер можно сравнить с деревом: ограничения помогают ему обрезать ветки и уменьшать область поиска. В данном случае имеется ограниченное количество ресурсов для производства юнитов. Иначе говоря, мы не можем потратить больше, чем у нас есть. Например, количество еды для найма юнитов не может превышать 1200. То же самое относится к лесу (800) и золоту (600). Согласно таблице, у юнитов следующая стоимость:
Можно написать одно ограничение на каждый ресурс, как показано ниже: В OR-Tools просто добавляем ограничения в копию решателя с 4. Цель Теперь, имея переменные и ограничения, необходимо определить цель (или целевую функцию). В линейном программировании эта функция должна быть линейной (как и ограничения), то есть иметь вид
Максимизация силы армии равна максимизации суммы силы каждого юнита. Целевая функция может выглядеть так: В целом, у целевой функции есть только два типа: максимизация или минимизация. В OR-Tools мы указываем это с помощью solver.Maximize(swordsmen*70 + bowmen*95 + horsemen*230 Готово! Чтобы смоделировать любую задачу линейной оптимизации, нужно выполнить три шага.
С этим разобрались, теперь можно попросить солвер найти оптимальное решение. 5. Оптимизация! Расчет наилучшего варианта закончен с помощью Выведем наибольшую суммарную силу, которую можно получить с наилучшим составом армии: status = solver.Solve() # Если оптимальное решение найдено, вывести результаты ================= Solution ================= Optimal power = 1800.0 ?power Отлично! Решатель нашел наилучший вариант: общая сила армии равняется 1800 и состоит из 6 мечников и 6 наездников. Разберем этот результат.
Однако в этом результате есть нечто странное: числа некруглые, хотя мы определили, что хотим целочисленные переменные (IntVar). Так что же произошло? К сожалению, для ответа на данный вопрос нужно глубоко погрузиться в линейное программирование. Чтобы не усложнять, предположим, что причина в GLOP. У решателей имеются характеристики, с которыми нужно считаться, а GLOP не справляется с целочисленными переменными. Вот еще одно доказательство, что создание моделей для многоразового применения — не просто удобство. Заключение Мы рассмотрели пять основных шагов любой задачи линейной оптимизации на примере.
Основное преимущество линейного программирования — алгоритм дает гарантию, что найденное решение оптимально (с определенной погрешностью). Это надежная гарантия, но у нее есть цена: модель может быть такой сложной, что солверу потребуются годы (или больше) для нахождения наилучшего решения. В таком случае есть два варианта.
Источник: m.vk.com Комментарии: |
|