Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 2

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

Текст из файла (страница 2)

Мину. Математическое программирование.Теория и алгоритмы.- М.: Наука, 1990.]. Например, если функции f,gi – линейные и S Zn , тозадача (1.1) относится к классу задач целочисленного линейного программирования.В отдельный класс выделим задачи комбинаторной оптимизации. Они возникают,например, при проектировании информационно-управляющих систем реального времени.В постановке любой задачи комбинаторной оптимизации присутствуют некоторыеобъекты, которые требуется определенным образом разместить, упорядочить или разбитьна группы.

В этом случае множество S состоит из решений X, описывающихвсевозможные размещения/упорядочивания/разбиения на группы исходно заданныхобъектов. Математически множество S описывается набором ограничений, которыетребуют согласованного изменения значений элементов X: изменение значения одного изэлементов для сохранения корректности решения может требовать принятия конкретныхзначений ряда других элементов.

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

Для каждойработы задано время ее выполнения. Расписание определено, если для каждой работы3задан процессор, на котором она выполняется и порядковый номер выполнения работы напроцессоре (работа не может начать выполняться, пока не выполнены все работы сменьшими номерами). Требуется построить расписание выполнения работ на минимальнонеобходимом числе процессоров время выполнения которого не превосходит исходнозаданный директивный срок. Для этой задачи значением функции f является числопроцессоров, функция g задает ограничение: время выполнения расписания не должнопревышать директивный срок. Множество S определяется следующими ограничениями:1.

Каждая работа должна быть назначена на процессор для выполнения.2. Каждая работа должна быть назначена лишь на один процессор.3. Частичный порядок, заданный на множестве работ должен быть сохранен врасписании.4. Расписание должно быть беступиковым. Условием беступиковости расписанияявляется ацикличность отношения частичного порядка в расписании.Если эти условия не выполняются, то мы не можем вычислить время выполнениярасписания.Если мы изменяем расписание путем перемещения работы с процессора А напроцессор В, то номера работ на процессоре А больше перемещаемой должныуменьшиться на 1, а номера работ на процессоре В, которые должны выполняться послеперемещаемой работы должны увеличиться на 1.1.2. Понятие «сложных» задач условной оптимизации. Проблемыприменения оптимальных и эвристических алгоритмов, использующихаприорно известные свойства о целевой функции и функцияхограниченийПод сложными задачами условной оптимизации будем понимать задачи (1.1) длякоторых отсутствует априорная информация о функциях f,gi и множестве S, котораяможет быть использована для организации поиска оптимального решения, или сложностьполучения этой информации неприемлема.

Можно выделить следующие основныеособенности сложных задач условной оптимизации:1. Функций f,gi могут быть операторами, заданными правилами/алгоритмами ихвычисления, т.е. их аналитическая структура не может быть использована дляорганизации поиска оптимального решения задачи (1.1).2.

Негладкий характер функций f,gi.43. Отсутствие информации о производных функций f,gi или их производные неявляются непрерывными.4. Множество S может быть компонентно разнородным: S = SR  SZ  SF  SKS, т.е.различные компоненты вектора X могут принадлежать подмножествам множествадействительных чисел (R), целых чисел (Z), функций (F) и комбинаторных структур (KS).Указанные выше особенности делают проблематичным применение оптимальныхи эвристических методов, использующих некоторые априорно известные свойства задачидля организации поиска оптимального решения.

При больших размерности и/илиразмерах задачи (1.1) методы полного перебора допустимых решений также оказываютсянеприемлемыми по сложности.Идея о целесообразности случайного поведения, при наличии неопределенности,т.е. отсутствии достаточной информации, которая может быть использована дляорганизации поиска оптимального решения/поведения, впервые в четкой форме быласформулирована У.Р. Эшби в работе [У. Росс Эшби. Конструкция мозга.- М.:, ИЛ, 1962.] иреализована в известном гомеостате (гомеостат Эшби). Применительно к сложнымзадачам условной оптимизации, алгоритм поиска оптимального решения долженопираться на метод проб и ошибок.

Только такой процесс позволяет извлечь информацию,необходимую для организации поиска решения. Метод проб и ошибок основан напонятии случайного эксперимента: случайного выбора значений компонентов вектора X,что дает возможность получить информацию о функциях f,gi и множестве S, котораяможет быть использована для организации поиска решения сложной задачи условнойоптимизации.Наиболееширокоприменяемымиподходамикпостроениюалгоритмовоптимизации опирающихся на метод проб и ошибок являются следующие:алгоритмы случайного поиска (ненаправленного, направленного,направленного с самообучением) [ Л.А.

Растригин. Статистические методы поиска.- М.:Наука, 1968.],алгоритмы имитации отжига [Уоссермен Ф. Нейрокомпьютерная техника. Теория ипрактика.- М.: Мир, 1992. – 240с.],генетические и эволюционные алгоритмы [Holland J.N. Adaptation in Natural andArtificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.],муравьиные алгоритмы [Dorigo M.

Optimization, Learning and Natural Algorithms. // PhDThesis. Dipartimento di Elettronica, Politechnico Di Milano, Milano. 1992.], [Штовба С.Д.Муравьиные алгоритмы: теория и применение// Программирование. 2005. №4.].51.3. Классические задачи комбинаторной оптимизации1.3.1. Задача коммивояжераЗадачу коммивояжёра можно представить в виде нахождения пути на графе.Вершины графа соответствуют городам, а ребра между вершинами являются путямисообщения между этими городами.

Граф является полносвязным, т.е. между любымидвумя вершинами есть ребро. Каждому ребру можно сопоставить вес, который можнопонимать, например, как расстояние между городами, время или стоимость поездки.Маршрутом (гамильтоновым циклом) называется маршрут на таком графе, в которыйвходит по одному разу каждая вершина графа. Задача заключается в отысканиикратчайшего маршрута. Длина маршрута определяется как сумма весов входящих внего ребер. Маршрут может быть описан циклической перестановкой номеров городовJ  ( j1 , j2 , jn , jn1 ) , где ji - номер города находящийся в i –ой позиции перестановки.Пространством поиска решений является множество перестановок n городов, таких,что все j1 , j2 , jn разные и j1  jn1 .Существует несколько частных случаев общей постановки задачи, в частности:симметричная задача коммивояжера,асимметричная задача коммивояжера,метрическая задача коммивояжера.В симметричной задаче коммивояжера задается неориентированный граф и всепары ребер между одними и теми же вершинами имеют одинаковый вес, т.е.

длялюбого ребра (i,j) wij  w ji .В асимметричной задаче коммивояжера задается ориентированный граф и дугимежду одними вершинами могут иметь разный вес, т.е. wij  w ji .Симметричная задача коммивояжера является метрической, если для весов ребервыполняется правило треугольника: wij  wik  wkj . То есть прямой путь междулюбыми двумя вершинами не длиннее любого обходного пути.В практических задачах, если между некоторыми вершинами не существует ребер,то они искусственно добавляются в граф и им присваиваются большие веса. Из-забольшого веса такое ребро никогда не попадает в оптимальный маршрут и маршруты,близкие по длине к оптимальному маршруту.6Данная задача принадлежит к классу NP-трудных задач и часто используется кактестовая задача для сравнения качества работы различных алгоритмов опирающихсяна метод проб и ошибок.Математическиематематическойформулировкиформулировкизадачиопределяетсямогутбытьклассомразными.алгоритма,Выборкоторыйпредполагается использовать для решения задачи.1.3.2.

Задача о рюкзакеИмеется рюкзак объемом b и набор n различных товаров. Для каждого товара iзаданы: объем ai и стоимость ci. Требуется упаковать рюкзак так, чтобы суммарнаястоимость упакованных товаров была максимальной и их суммарный объем непревышал объем рюкзака b.Математически эту задачу можно записать следующим образом:nmax( ci  xi )Xi 1na  xi 1iibi  1,, n : xi  0 или 1Если товар упакован в рюкзак, то xi=1, если нет xi=0.Если все коэффициенты ai целые числа и b целое число, то задача является NPтрудной. Если все коэффициенты ai вещественные, то задача может быть решенажадным алгоритмом сложности O(n·log n). Обе задачи о рюкзаке обладают свойствомоптимальности для подзадач. Вынув товар i из оптимально загруженного рюкзака,получим решение задачи о рюкзаке с максимальным объемом b-ai и набором из n-1товара.

То есть, жадный алгоритм может быть построен как для непрерывной, так идискретной задачи. Вычислим относительную стоимость всех товаров в расчете наединицу объема ci ai . Оптимальный жадный алгоритм для непрерывной задачизаключается в следующем: сначала в рюкзак укладывается по максимуму товар ссамой дорогой относительной стоимостью. Если товар закончился, а рюкзак незаполнен, то укладывается следующий по относительной стоимости товар, затемследующий, и так далее, пока не набран вес b .

В [Кормен Т., Лейзерсон Ч., Ривест Р.Алгоритмы: построение и анализ. М.: МЦНМО, 2000.] показано, что аналогичный жадныйалгоритм может не получать оптимум в дискретной задаче о рюкзаке.71.3.3. Задачи построения расписаний и их классификацияОпишем общую задачу построения расписания согласно [Теория расписаний ивычислительные машины.

Под ред. Э.Г. Коффмана. М.: Наука, 1984. 334 с.]. Модель в рамках котороймогутбытьсформулированымногиезадачипостроениярасписанийзадаетсясовокупностью моделей ресурсов, системы заданий (работ) и меры оценки расписаний.Ресурсы. В большинстве моделей ресурсы состоят просто из набора процессоров P.В наиболее общей модели еще имеется набор дополнительных типов ресурсов R,некоторое подмножество которых используется на протяжении всего времени выполнениязадания на некотором процессоре. Общее количество ресурса типа Ri задается целымположительным числом.Система работ может быть определена через T,  , [τji], {Rj}, где:T={T1,T2,…,Tn} - набор работ подлежащих планированию; - заданное на T отношение частичного порядка, которое определяетограничение на последовательность выполнения работ.

Характеристики

Список файлов лекций