Библиотека тестовых задач Простейшая задача размещения 

Главная страница библиотеки Простейшая задача размещения

Тестовые  примеры  

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

В данном разделе библиотеки собраны тестовые примеры для простейшей задачи размещения, отличающиеся способом порождения матрицы транспортных расходов. Они разбиты на следующие классы:

1. Примеры на совершенных кодах   (PCodes)

2. Примеры на шахматной доске  (Chess)

3. Примеры на конечных проективных плоскостях (FPP)

4. Примеры с большим разрывом двойственности (Gap-A, Gap-B, Gap-C)

5. Примеры с равномерным распределением (Uniform)

6. Примеры на евклидовой плоскости (Eucl)

Для всех классов | I | = | J |, стоимость открытия любого предприятия равна 3000 и матрицы транспортных расходов составлены таким образом, чтобы число открываемых предприятий в оптимальном решении не сильно менялось при переходе от одного класса к другому. Классы PCodes и Chess характерны тем, что для них число строгих локальных минимумов относительно окрестности добавить – удалить – заменить (см. ниже) растет экспоненциально с ростом размерности задачи.  Класс FPP является полиномиально разрешимым. Классы Gap-A, Gap-B, Gap-C имеют большой разрыв двойственности, а классы Uniform и Eucl наиболее популярны при построении приближенных алгоритмов с гарантированными оценками точности. В следующей таблице приводятся усредненные характеристики поведения точного метода ветвей и границ на данных классах. 

Время счета приведено для PC Pentium-IV, 1800 MHz. 

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

N(S) = {S' Í I | $ i Î I такой, что S' = S È {i} }

    È {S' Í I | $ i Î I такой, что S' = S \{i} }

                 È {S' Í I | $ ij Î I такие, что S' = S È {i}\{j} }.  

В итоге получается представительное множество локальных оптимумов.Для него посчитано  число различных локальных оптимумов (N1) и  нижняя оценка на диаметр области, занимаемой локальными оптимумами (N2). Кроме того для каждого локального оптимума подсчитано число других локальных оптимумов, находящихся от данного на расстоянии не более r = 1, 2, 3,... Эта величина (Nr) усредняется по всем локальным оптимумам.В таблице приведены данные о средних значениях этих показателей для указанных классов исходных данных.

 На нижеследующей диаграмме приведены результаты эксперимента для  r = 1, ... ,100. Они свидетельствуют о том, что данные классы заметно отличаются друг от друга не только по числу локальных оптимумов но и по средней плотности, и следует ожидать, что клас Eucl  окажется наиболее простым для алгоритмов локального поиска, а классы PCodes, FPP и Gap-C — наиболее трудными.

  Главная страница библиотеки Простейшая задача размещения