qweqweqe123123

Комбинаторная оптимизация

В 50-х и 60-х гг. основные прорывы в исследованиях по оптимизации были связаны с новыми алгоритмами поиска оптимумов функций непрерывно изменяющихся переменных. Во многих важных теоретических и практических задачах приходится выбирать «лучшее» решение из большого набора возможных решений. Если переменные оптимизации могут принимать только некоторые дискретные значения, задача оптимизации будет заключаться в том, чтобы найти лучшую комбинацию этих значений. Такие задачи называются задачами комбинаторной оптимизации (combinatorial optimization problems). Основные результаты в исследованиях по комбинаторной оптимизации были получены в 70-х гг. Для многих таких задач решение может рассматриваться как размещение набора дискретных объектов в соответствии с заданными ограничениями. Поэтому решение называется также конфигурацией (configuration). Набор всех решений называется пространством решений. Наша задача — разработать эффективные алгоритмы определения конфигурации, минимизирующей значение функции стоимости или целевой функции. Примером комбинаторной задачи оптимизации является хорошо известная задача коммивояжера (traveling salesman  problemTSP), которая состоит в определении обладающего минимальной стоимостью маршрута коммивояжера, проходящего через каждый город только один раз и возвращающегося в точку отправления. В этом случае размещаемыми объектами являются города, а то, что каждый город нужно посетить ровно один раз, является ограничением [158]. Эту проблему можно интерпретировать в терминах обычной оптимизации. Посещаемые города — это переменные оптимизации, причем дискретное значение переменной означает номер, под которым данный город войдет в список посещенных. Упомянутое выше условие может быть выполнено, если на дискретные значения, принимаемые переменными, наложить некоторое ограничение.

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

Один из методов решения NP-полных задач состоит в использовании алгоритма аппроксимации, позволяющего найти приближенное решение за разумное время. Общая стратегия разработки алгоритмов аппроксимации состоит в последовательном улучшении, основанном на методе проб и ошибок. Поиск начинается с некоторой произвольной конфигурации и продолжается проверкой соседних с ней конфигураций до тех пор, пока не будет найдена конфигурация с меньшей стоимостью. Алгоритм завершает работу, если он больше не может найти соседней конфигурации более низкой стоимости. Эта стратегия кажется разумной, но она имеет один серьезный недостаток: поиск решения оканчивается в ближайшем локальном минимуме (рис. 9.6). Решения, которые кажутся удачными по сравнению с их близкими соседями, не обязательно являются наилучшими в глобальном смысле. Стандартное итеративное улучшение позволяет лишь спускаться с холма, но не подниматься обратно, и потому не гарантирует хорошего результата [158, 134].

Комбинаторная оптимизация

Метод модельной закалки основан на аналогичной стратегии, но существенно отличается от метода итеративного улучшения тем, что разрешает ограниченный подъем «вверх» по поверхности функции стоимости. Благодаря этому оказывается возможным «выбраться» из локального минимума и спуститься в другой, более глубокий [134].

Смотрите также