Смешанное целочисленное линейное программирование, используемое для реализации алгоритмов оптимизации (например, генетический или частичный рой)

Question

Я изучаю алгоритмы оптимизации для автоматической группировки пользователей. Тем не менее, я совершенно не знаком с этими алгоритмами, и я слышал о них, когда я просмотрел соответствующую литературу. И, иначе, в одной из статей авторы реализовали собственный алгоритм (основанный на собственной логике) с использованием Integer Programming (так я слышал об IP).

Мне интересно, нужно ли реализовать алгоритм генетического/частичного роя (или любой другой оптимизации) с использованием смешанного целочисленного линейного программирования или это только один из вариантов. В конце концов, мне нужно будет создать веб-систему, которая автоматически группирует пользователей. Я ценю любую помощь.

Answer 1

Я думаю, вы немного сбиваете с толку термины. Это разные методы оптимизации. Вы можете с уверенностью представить проблему с использованием нотации Mixed Integer Programming (MIP), но вы можете решить ее с помощью MIP-решения или генетических алгоритмов (GA) или оптимизации роя частиц (PSO).

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

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

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

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