Файл: Голенко Д.И. Статистические модели в управлении производством.pdf

={АГ.Р(А,А{)^Щ.

При таком определении окрестности алгоритм локаль­ ного случайного поиска можно сформулировать следую­

=тіп/С(Л*) .

4.Если К (Ап ) ^К(Ап), то Ап принимаем за локаль­ ный оптимум.

Если К (Ап )<К(Ап), то в качестве исходного рас­

писания принимаем А * и продолжаем процесс.

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

мум найден достоверно. Эффективность описанной про­ цедуры поиска определяется в основном характером введенной метрики.

При построении той или иной метрики на множестве перестановок (вектор-перестановок) исходят из чисто интуитивных соображений; в настоящее время не сущест­ вует методов, с помощью которых можно было бы срав­ нивать между собой две различные метрики в смысле их эффективности для локального поиска. По этой причине направленный случайный поиск для задач календарного планирования является по сути дела комбинацией эври­ стических методов и метода Монте-Карло.

При разработке статистических методов поиска экст­ ремума существенно используется понятие непрерывное- _ ти. По аналогии, в комбинаторном пространстве переста-

новок введем понятие о некотором статистическом экви­ валенте свойства непрерывности для функций дискрет­ ного аргумента. Назовем новое свойство, дающее важную информацию о поведении функции дискретного аргумен­

непрерывности существенно связано с выбором метрики, определяющей соответствующие окрестности. Метрики, обеспечивающие больший процент точек со статистичес­ кой непрерывностью, будем называть метриками с луч­ шей статистической непрерывностью.

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

парного расположения элементов в одной из них относи­

говоря, расстояние между яі и я 2 определяется как мини­ мальное количество разрезов, которые необходимо сде­ лать в одной из перестановок, чтобы из нее составить вто­

1.Моделируем R раз случайную величину, равномер­ но распределенную в интервале (0, я + 1 ) , где п — число элементов перестановки я.

2.Полученные реализации упорядочим по возраста­ нию, т. е.

3.Элемент перестановки я, находящийся на г-ж мес­ те, попадает в множество Si, если Ui-i<r^Ui. Тогда мно­

1, 2, ...,/? + 1 , в соответствии с которой размещают мно­ жество Si. Ясно, что полученная таким образом переста­ новка я находится от исходной я на расстоянии, не пре­ вышающем R.

Другими словами, мы вначале случайным образом вы­ брали R мест разрезов и разрезанные участки случайным образом переставили между собой.

Например, я = ( 2 , 5, 6, 8, 1, 7, 3, 4), п = 8; # = 3. В ре­ зультате моделирования случайной величины, равномер­ но распределенной на (0,9), получены реализации щ =

1, 7), 5 4 = (3, 4,). Пусть_далее я ' = (2, 3, 4, 1), тогда я=!(6, 8, 1,7,3, 4,2, 5) и р ( я , я) = 1.

Метод поиска локальных экстремумов на основе вве­ денной метрики называют цепным методом Монте-Карло. При разумном задании Rn и Nn цепной метод более эф­ фективен, чем обычный метод Монте-Карло. Так, в зада­ че 20X10 (20 деталей обрабатываются на 10 станках) [2.6] время обработки детали на станке задавалось двумя способами: путем моделирования случайной величины.

для ценного метода примерно в 5—6 раз меньше, чем для метода Монте-Карло.

численная функция, определенная на множестве всех пе­

ка следующим образом: я.і<яг, если существует такое і (Is^is^n), что Рі = а ь р 2 = « 2 рг-і = ш-і, но Рг>аг. Легко видеть, что указанное отношение обладает свойст­ вом транзитивности (если Яі<Яг и яг<яз, то яі<Яз) и, таким образом, все множество перестановок может быть однозначным образом упорядочено. Использованный принцип упорядочения обычно называют лексикографи­ ческим. Каждой перестановке поставим в соответствие число N(n), которое определим как номер места, зани­ маемого перестановкой я при лексикографическом упоря­

но, что множество П всех перестановок состоит из п клас­

собой разбиение на непересекающиеся классы, т. е. клас­ сы k-vo порядка представляют собой непересекающиеся множества, объединение которых содержит все переста­ новки из П.