§ 2. Случайный поиск с локальной оптимизацией

2.1. В этом параграфе описывается подход к задачам дискретного программирования, основанный на сочетании случайного поиска с локальной оптимизацией. Идея этого подхода весьма проста. Производится случайный выбор исходного плана. Далее некоторым естественным образом определяется «окрестность» этого плана и находится «локальный» оптимум целевой функции на точках окрестности. Поиск этого оптимума чаще всего ведется прямым перебором, ибо окрестность по самому своему построению состоит из относительно небольшого числа точек. Затем производится случайный выбор нового плана и снова находится локальный оптимум в окрестности этого плана. Процесс этот повторяется многократно, и из полученных локальных оптимумов выбирается наилучший в смысле значения целевой функции. Он и принимается за приближенное решение задачи.

Подобный подход к дискретным задачам был предложен в статье Рейтера и Шермаиа [119]; наше изложение будет в основном следовать этой работе.

Перейдем теперь к формальному описанию этого подхода.

2.2. Рассматривается задача максимизации функции

на конечном множестве Предполагается, что при любых функция (2.1) принимает целочисленные значения, которые мы будем обозначать через

Пусть на определено отображение сопоставляющее каждому его окрестность Это отображение удовлетворяет двум требованиям:

1° . Для каждого имеется единственное

Тем самым на X определено семейство окрестностей

Предположим далее, что на задан оператор удовлетворяющий следующим условиям:

Очевидно, что оператор сопоставляет каждой точке из окрестности другую точку, в которой значение целевой функции не меньше.

Пару естественно назвать локально максимазационной структурой окрестностей на множестве

Введем еще несколько простых понятий. Точка называется локально оптимальной относительно структуры если Точка называется оптимальной, если при любом Через будем обозначать степень оператора т. е.

Из приведенных определений и из конечности множества вытекает следующая простая теорема.

Теорема 2.1. Для любой структуры на G:

1) в G существуют локально оптимальные точки; любая оптимальная точка является и локально оптимальной,

2) для любого существует такое что

Рассмотрим произвольную точку Точку X назовем доминантой точки X, если существует такое что для всех целых

Из утверждения 2) теоремы 2.1 сразу следует, что любая точка имеет единственную доминанту. Кроме того, легко убедиться в справедливости следующего факта.

Теорема 2.2. Пусть две максимизационные структуры окрестностей на и — соответствующие им множества локально оптимальных точек. Тогда из вытекает

Иначе говоря, множество локально оптимальных точек определяется независимо от

Для простоты изложения предположим, что различные локально оптимальные точки дадот различные значения целевой функции. Определим множества

То есть, состоит из всех точек, доминанты которых приводят к значению целевой функции, равному

2.3. Коротко упомянем и о вероятностной стороне вопроса. Выбор точек производится в соответствии с некоторым распределением вероятностей По поводу этого распределения ограничимся здесь самыми общими замечаниями, ибо его конкретизация должна проводиться с учетом особенностей рассматриваемой задачи. Отметим лишь, что обычно (особенно при полном отсутствии априорной информации о возможном местоположении искомого максимума) в качестве уместно брать равномерное распределение. В других случаях распределение можно делать условным, зависящим от исходов предыдущих испытаний.

Распределение дает возможность получить еще рдну вероятностную характеристику,

Именно, положим

Вспоминая определение (2.4), легко дать интерпретацию это есть вероятность того, что распределение даст нам такую точку из доминанта которой приведет к значению целевой функции

В частности, если в качестве взято равномерное распределение на то

Отметим, что для любого точного алгоритма структура определяет единственный локальный максимум, который и является искомым оптимумом. В этом случае распределение (2.5) припишет точке оптимума вес а все остальные будут равны нулю.

2.4. Описанная конструкция представляет собой абстрактное оформление высказанной в начале этого параграфа идеи. Разумеется, при доведении этой схемы до вычислительного алгоритма необходима детальная ее конкретизация, учитывающая особенности задачи.

Приведенное выше определение окрестности данной точки (данного плана) является весьма общим. На практике, разумеется, желательно, чтобы окрестности были легко обозримыми, т. е. содержали сравнительно небольшое число точек.

Приведем пример. Если X представляет собой перестановку чисел то в качестве окрестности можно взять, например,

(здесь последовательно занимает первое, второе, места) или же

(здесь аналогично перемещается пара

Различие между описанным подходом и методом случайного поиска в его чистом виде удобно пояснить также в терминах окрестностей: в методе случайного поиска окрестность каждой испытываемой точки состоит только из самой этой точки (тем самым каждая точка является локально оптимальной).

Оператор определяемый своими свойствами представляет собой абстрактное описание алгоритма локальной оптимизации функции (2.1) на окрестности Мы уже отмечали, что чаще всего этот алгоритм сводится попросту к рационально организованному полному перебору точек окрестности.

Общность описанной конструкции предоставляет также широкие возможности для разнообразных ее модификаций. Так, можно ввести в рассмотрение «стоимость» (или иную аналогичную характеристику) объема вычислений с тем, чтобы не добиваться малозаметных улучшений плана слишком дорогой «ценой». Наряду с детерминированными алгоритмами локальной оптимизации в ряде случаев может оказаться целесообразным рассмотрение некоторых рандомизированных процессов поиска максимума и т. п.

В качестве исходной здесь рассматривалась задача максимизации; перенесение схемы на случай задачи минимизации является совершенно очевидным.

2.5. В качестве иллюстрации опишем некоторые предложенные Рейтером и Шерманом [119] алгоритмы для решения задачи о коммивояжере. Задача эта неоднократно упоминалась выше (см., например, § 3 гл. 10, § 2 гл. 12); поэтому математическая формулировка здесь не воспроизводится. Отметим лишь, что в качестве здесь будет фигурировать множество всех перестановок чисел функция представляет собой суммарную длину пути, проходимого при перестановке и задача заключается в ее минимизации.

Алгоритм Случайным образом выбирается план План X получается из него переменой мест Вычисляются если то X заменяется на на . В полученном плане меняются местами второй и третий

элементы, после чего производится сравнение значений целевой функции для X и для новой перестановки Найденный в результате последовательных транспозиций путь и его длина запоминаются. Производится случайный выбор нового исходного плана, и весь процесс повторяется.

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

Алгоритм III. Случайным образом выбирается план Путем перестановки из него получается план Из плана путем перестановки получается план Из плана путем перестановки получается план Вычисляются и сравниваются План, на котором минимальна, служит отправной точкой для новой серии сравнений; при этом начинают уже со второго члена соответствующей перестановки. Всего сравнивается наборов по плану в каждом.

Алгоритм представляет собой по существу серию алгоритмов, зависящих от натурального параметра Алгоритм IV (1) совпадает с алгоритмом III. Когда с его помощью найден локально минимальный план X, берутся два смежных элемента этого плана и перемещаются вдоль него. При этом ищется их положение в плане и их ориентация или дающие минимум Эта процедура и составляет алгоритм IV (2). В локально минимальном плане, полученном с его помощью, производятся всевозможные перемещения троек индексов и т. д. Алгоритм начинает работу над локально минимальным планом, полученным с помощью алгоритма

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

алгоритмы работают с довольно большими окрестностями (так, в алгоритме IV (1) количество точек в окрестности составляет а в алгоритме оно равно

Эксперименты велись с сериями задач различных размеров; большинство этих задач было взято из имеющейся литературы, и для них уже были известны оптимальные (или «подозревавшиеся» на оптимальность) планы. Далее будет приведена некоторая выборка из результатов экспериментов.

Для серии задач с 9 городами были получены планы не худшие, чем известные до сих пор. В одной из этих задач оптимальный план при помощи алгоритма III был получен в 48% всех просчетов; для той же задачи алгоритм IV (2) привел к оптимуму в 91% всех просчетов, а алгоритмы обнаружили оптимальный план в 100% всех просчетов. Для наиболее «трудной» задачи этой серии алгоритм III дал оптимум лишь в 1,3% всех просчетов, алгоритм в 25%, алгоритм в 44% и алгоритм IV (4) — в 59% всех просчетов. Число просчетов по каждой из 10 решавшихся задач колебалось от 65 до 285.

В задаче с 15 городами был найден лучший план, чем известный до сих пор. При помощи алгоритма III он был получен в 11% всех просчетов. Наилучшие результаты здесь дал алгоритм он выявил лучший план в 35,4% всех просчетов и следующий за ним — в 59,6% всех просчетов. Максимальное среднее время одного просчета (для алгоритма составило 20 сек.

Для задачи с 25 городами найденный Хелдом и Карпом [94] оптимальный план был получен при помощи алгоритма III в 1,7% всех просчетов, при помощи алгоритма в 28% всех просчетов и при помощи алгоритма всех просчетов. Среднее время одного просчета для последнего алгоритма равнялось 1 мин. 45 сек.

В задаче с 33 городами наилучшее решение было найдено алгоритмом в 23% просчетов, алгоритмом IV (15) — в 33% просчетов.

К рассматривавшейся ранее многими авторами задаче с 42 городами применялись все четыре алгоритма.

Алгоритм I дал лучший результат 1204, алгоритм II — 605, алгоритм III — 204; точное значение оптимума 167,5 было найдено только алгоритмами серии IV (алгоритмом IV(3) - в 3,5% просчетов, алгоритмом в 22% и алгоритмом в 28,6% просчетов).

Задача с 57 городами находилась уже почти на пределе возможностей имевшейся машины. Наилучший из найденных здесь результатов был найден посредством алгоритма IV (22) в 4% всех просчетов (среднее время одного просчета было около 21 мин.). Алгоритм оказался для этой задачи заметно хуже.

Изложенные здесь результаты численных экспериментов говорят о том, что описанный подход является вполне приемлемым.