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

Question

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

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

Answer 1

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

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

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

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

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