Полная версия

Главная arrow Информатика arrow Интегрированные автоматизированные системы управления химическими производствами и предприятиями

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Метод поиска в локальной окрестности

Рассмотрим понятие «окрестная структура» LNS(7i).

Для любой перестановки п = {i1} i2, in}, окрестная структура LNS(tt) считается заданной, если задана мера близости (метрика) для любых перестановок пг и п2: ср(л1} л2). Определим метрику ф(те1} п2) как число нарушений попарного расположения элементов в одной относительно другой перестановки. Например, для:

Заметим, что метрика (p(7il5 п2) для любых пг, п2е{il;i2,...,in} удовлетворяет известным аксиомам:

Более того, метрика ф инвариантна относительно любой перестановки из группы перестановок

т. е. ф(л12) = ф(а-л],а-712) VoeSn.

Итак, для некоторой л определим структуру к-«окрестности». LNS(7T, /с) — совокупность перестановок л', для которых ф(л, л') <к.

Общее число перестановок R(n,k), находящихся в к-«окрестности» перестановки л определяется по следующей формуле:

или

В этом случае общий алгоритм включает в себя следующие шаги.

Шаг 1. Выбираем начальное решение л° и начальную максимальную окрестную структуру LNS(7r°, к0).

Шаг 2. В окрестной структуре LNS(n°, к0) проведем N(k0) раз случайный поиск в ^-«окрестности» с получением N подмножеств выпуска продуктов и отберем среди них лучшее решение л1.

Шаг 3. Если существует улучшенное решение л1, то примем л° = л1 и возвратимся к шагу 2. Если же улучшенного решения л1 не существует, то сужаем окрестность поиска 0 = к0- 1) и возвращаемся к шагу 2. Процесс продолжается до тех пор, пока окрестность не сузится до нуля (к0 = 0).

Случайный поиск в /с-«окрестности» LNS(k, к) можно проводить следующим образом.

Случайно генерируем к - 1 случайных целочисленных чисел и Ub затем ранжируем их в порядке возрастания:

Все продукты в л группируются в к подмножеств (ДГ, (; = 1 ,к), так что ц е Nj, если < 1 < Uj (; = 1, к).

Любая перестановка между этими к подмножествами образует новую последовательность п’, которая принадлежит к -окрестности LNS(n, к) исходной последовательности л.

Например: л = {7, 8, 9, 10, 1, 2, 3, 4, 5, 6 }, п = 10, к = 4.

Случайно сгенерируем Up где j = l,k-l: Ul = 2, U2 - 5, U3= 8, где О = U0 < t/j = 2 < U2 = 5 < U3 = 8 < U4 = 10.

Получим следующие подмножества выпуска продуктов:

если л = {N4 kj N2u iV3 u JV1} = {4,5,6,8,9,10,1,2,3,7}, то ф(тг, я) = = 2 < к = 4.

Пример 7.11

Для решения задачи Джонсона (п=6, т=6) с данными (табл. 7.10) на компьютере реализован алгоритм поиска в локальной окрестности.

Для л° = {1, 2, 3, 4, 5, 6,},/(тг°) = 355 применим LNS с параметрами 0 = 4, п0 - 7). Результаты десятикратного решения задачи представлены в табл. 7.11. Напомним, что глобальным решением задачи методом полного перебора является Gmin = 248; п* = {6, 5,1, 4, 2, 3}.

Таблица 7.10

Продолжительность обработки продуктов в аппаратах (л = 6, т = 6)

i

j

1

2

3

4

5

6

1

10

20

5

30

2

13

2

54

15

8

12

10

5

3

45

1

20

7

9

5

4

6

34

21

13

7

17

5

10

35

40

45

55

3

6

6

12

47

39

24

7

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>