Приближенные и эвристические методы решения задач комбинаторной оптимизации
Методы перебора и все их усовершенствования имеют один, но очень серьезный недостаток: время работы, экспоненциально растущее при увеличении размерности задачи. Для решения практических задач это часто бывает неприемлемо. За редкими исключениями, эффективными можно считать только алгоритмы, имеющие не более чем полиномиальные оценки трудоемкости. Ясно, что такие алгоритмы не могут сводиться к полному перебору планов (ввиду того, что количество планов растет экспоненциально). Других же подходов, пригодных сразу для всех задач комбинаторного поиска, не имеется. Значит, можно надеяться только на алгоритмы, учитывающие специфику конкретных задач.
Исследования в области методов дискретной оптимизации позволили найти некоторое количество задач, для которых действительно существуют эффективные (т.е. полиномиальные с невысокой степенью полинома) алгоритмы решения. К ним относятся, например, такие задачи, как отыскание кратчайшего пути между вершинами графа, максимизация потока в сети при заданной пропускной способности ребер и др. Однако для большей части задач, возникающих на практике, неизвестны эффективные алгоритмы точного решения. Поскольку решать задачи все равно надо, а на перебор надежда плохая, очень часто приходится жертвовать точностью определения экстремума ради сокращения времени его определения. Вместо строгого доказательства того, что полученный план будет давать точный минимум или максимум целевой функции, приходится опираться на соображения здравого смысла, которые позволяют считать, что полученный план с достаточно большой вероятностью либо оптимален, либо хотя бы близок к оптимальному. Конечно, это неприятно, ибо противоречит неуемной тяге человеческого духа к совершенству. Но с другой стороны, много ли вещей мы в жизни делаем оптимальным образом? И ничего, живем.
Относительно более приятна ситуация, когда точно известна хотя бы степень возможной неоптимальности. Алгоритмы оптимизации, для которых имеются нетривиальные оценки возможного отклонения решения от оптимума, называются приближенными или субоптимальными.
Хороший пример приближенного алгоритма известен для задачи о многопроцессорном расписании (см. п.1.3.5). Алгоритм прост донельзя: нужно лишь упорядочить задачи по убыванию их длительности, а затем каждую следующую задачу назначать на наименее загруженный процессор. Оказывается, что отношение времени выполнения набора задач, получаемого по этому алгоритму (T), к минимально возможному времени выполнения, которое можно найти в результате перебора (T0), всегда удовлетворяет неравенству: T/T0 £ 4/3 – 1/3n. Например, при n=3 из этого получается оценка: T0 ³ 9/11×T. Если, к примеру, по данному алгоритму получилось время выполнения 220с, то нет гарантии, что это наилучшее возможное распределение, однако можно быть уверенным, что минимальное возможное время не может быть меньше 180с.
К сожалению, далеко не во всех случаях можно подобным образом оценить погрешность. Вполне типична ситуация, когда используемый алгоритм дает достаточно приличные решения, однако нет никаких гарантий, что эти решения всегда близки к оптимальным. Алгоритмы, основанные на нестрогих соображениях «здравого смысла» и не имеющие никаких гарантий близости к оптимальным, называются эвристическими алгоритмами. Некоторые авторы, правда, вообще отказывают им в праве называться алгоритмами (поскольку под сомнением такое важное свойство любого алгоритма, как результативность) и используют вместо этого термин «эвристики».
Не существует универсальных рецептов построения эвристических алгоритмов для любых задач. В то же время имеется несколько хорошо зарекомендовавших себя подходов, которые оказываются полезными для разных типов задач.
Алгоритмы локальной пошаговой оптимизации основываются на следующих соображениях. В большинстве комбинаторных задач построение плана можно организовать как пошаговый процесс. Например, на каждом шаге решения может определяться значение очередной переменной. К сожалению, в большинстве случаев трудно сказать, какое решение нужно принять на очередном шаге, чтобы в конце концов придти к оптимальному плану задачи. Зато очень часто бывает легко выбрать решение, которое выглядит наилучшим для данного шага, без учета отдаленных последствий.
Простейшим видом алгоритмов локальной пошаговой оптимизации являются алгоритмы последовательного выбора.
Рассмотрим в качестве примера задачу о коммивояжере. Произвольно выберем начальный город и зададимся вопросом, в какой город следует ехать в первую очередь. Очевидный ответ – в ближайший. На втором шаге и на последующих шагах по той же логике следует выбирать ближайший из еще не посещенных городов. Конечно, такой алгоритм не гарантирует оптимальность построенного плана, ибо не исключено, что выигрыш на первых шагах приведет к большим потерям на последующих (можно и вообще заехать в тупик, откуда нет дороги). Однако можно аккуратными вероятностными рассуждениями подтвердить и без того очевидный факт: при выборе на каждом шаге ближайшего города ожидаемая длина всего маршрута будет меньше, чем при любом другом выборе.
Для задачи о рюкзаке можно предложить такой алгоритм последовательного выбора: отсортировать товары по убыванию отношения стоимости единицы товара к ее объему, а затем на каждом шаге брать максимальное количество очередного товара, умещающееся в оставшемся объеме.
Можно улучшить качество работы алгоритмов последовательного выбора, если разрешить ограниченный перебор, т.е. выбирать решение на данном шаге, учитывая результаты двух, трех или более шагов. Например, перебрать все варианты двух первых поездок коммивояжера, выбрать из них тот вариант, который имеет минимальную длину, и на основании этого выбора сделать первый шаг. Затем так же перебрать варианты второго и третьего шагов, сделать второй шаг и т.д. Если число перебираемых шагов ограничено, то алгоритм, хотя и будет работать значительно медленнее, все же сохранит полиномиальную сложность. Конечно, в силу ограниченности глубины перебора получение оптимального плана не гарантируется. Не гарантируется даже, что при увеличении глубины перебора качество полученных планов будет всегда возрастать, можно только надеяться на это.
Другим типом алгоритмов локальной пошаговой оптимизации являются алгоритмы последовательного улучшения плана. Предположим, некоторый (не оптимальный) план задачи уже построен тем или иным способом (например, при помощи алгоритма последовательного выбора). Иногда бывает возможно предложить процедуру несложной модификации плана, при которой он остается допустимым планом задачи. Если для модифицированного плана значение целевой функции лучше, чем для исходного, то новый, улучшенный план следует взять вместо исходного и попытаться еще раз применить к нему улучшающую модификацию. Процесс прекратится, когда все возможные модификации будут только ухудшать план.
Рассмотрим, например, некоторый маршрут коммивояжера, проходящий последовательно через города A, B, C, D. В качестве модификации рассмотрим маршрут, в котором те же города посещаются в порядке A, C, B, D. Очевидно, такая перестановка сохраняет допустимость маршрута, а длина нового маршрута может оказаться меньше, чем у исходного.
Основным недостатком алгоритмов локальной оптимизации является то, что они совсем не обязательно приводят к глобально оптимальному плану задачи. В частности, для алгоритмов последовательного улучшения очень важен удачный выбор исходного плана. (Представьте себе альпиниста, который «локально оптимально» выбирает всегда путь, ведущий вверх. В конце концов он доберется до какой-нибудь вершины, но это может быть вершина маленького холмика, а не вершина самой высокой горы). Полезную роль может сыграть использование случайного выбора для построения исходного плана. Случайно выбранный план будет, скорее всего, сам по себе хуже, чем план, построенный по алгоритму последовательного выбора (хотя и не обязательно), но при многократном повторении комбинации «случайный выбор + последовательное улучшение» возрастает вероятность хотя бы раз оказаться «на склоне нужной горы» и придти к глобальному оптимуму.
Интересной разновидностью эвристических алгоритмов являются популярные в последнее время генетические алгоритмы. Они основаны на использовании биологических аналогий, использующих такие понятия, как популяция, ген, мутация, кроссинговер, отбор.
При разработке генетического алгоритма важную роль играет удачный выбор способа кодирования допустимых планов задачи. Каждый план представляется в виде линейной цепочки («хромосомы»), состоящей из некоторых символов или чисел, играющих роль генов. Для хромосом определяются операции мутации (изменения одного или сразу нескольких генов) и кроссинговера (получения новой хромосомы как комбинации двух имеющихся). Важно суметь так определить эти операции, чтобы хромосомы, получающиеся в результате, также кодировали допустимые планы задачи. Дальнейшее понятно: случайным или иным образом выбирается «начальная популяция» хромосом, новые хромосомы образуются с помощью случайных мутаций и кроссинговера, по правилам отбора формируется новое поколение популяции и т.д., смотри учебник биологии.
По сути дела, генетические алгоритмы являются оригинальной разновидностью алгоритмов случайного выбора с последовательным улучшением. Тот факт, что аналогичная схема дала неплохие результаты при эволюции живой природы, дает надежду на достаточную эффективность этих алгоритмов при решении задач комбинаторной оптимизации.
В некоторых случаях эвристический алгоритм производит впечатление настолько естественного для данной задачи, настолько самоочевидного, что неопытному человеку кажется, будто этот алгоритм должен всегда давать оптимальный план задачи. Проверка на двух-трех простых примерах укрепляет уверенность. Однако если нет строгого доказательства оптимальности, алгоритм приходится считать эвристическим. Интуиция в таких случаях не аргумент, она очень часто обманывает.
В качестве иллюстрации сказанного рассмотрим следующий пример. Задача о минимальном доминирующем множестве графа формулируется следующим образом. В данном неориентированном графе G=(V,E) найти минимальное по мощности подмножество вершин V0такое, что каждая из остальных вершин G смежна хотя бы с одной вершиной из V0.
После небольших размышлений в голову обычно приходит следующий алгоритм решения этой задачи. Упорядочим вершины графа по убыванию их степени (т.е. количества ребер, инцидентных вершине). Будем на каждом шаге включать в множество V0вершину максимальной степени из тех, которые не смежны ни с одной вершиной из V0. В случае равенства степеней будем брать вершину с меньшим номером.
Другой напрашивающийся алгоритм выглядит чуть похитрее. После включения вершины с максимальной степенью в множество V0удалим эту вершину из графа G вместе с инцидентными ей ребрами, уменьшим на 1 степени смежных ей вершин, найдем максимум степени среди оставшихся вершин и т.д.
Оба алгоритма являются полиномиальными. Но дают ли они точное решение?
Для большинства простых примеров оба алгоритма действительно находят минимальное доминирующее множество. Рассмотрим, однако, простой контрпример, показанный на рис.1.5.
Рис.1.5
В данном случае оба алгоритма включат в доминирующее множество вершину 1, после чего придется включить туда еще как минимум три вершины. В то же время три вершины 2, 3 и 4 образуют минимальное доминирующее множество.
Таким образом, для данной задачи очевидные алгоритмы, как оказалось, не всегда находят оптимальный план. Это не случайная неудача. В следующем разделе курса будут рассмотрены теоретические результаты, из которых следует, что для рассмотренной выше задачи построение точного полиномиального алгоритма явилось бы открытием мирового класса.