Анализ и разработка современных интеллектуальных методов моделирования в системах принятия решений


Сравнительный анализ работы различных алгоритмов решения задачи о назначении тяговых ресурсов на поезда



страница19/24
Дата09.08.2018
Размер2.94 Mb.
#43463
ТипЗадача
1   ...   16   17   18   19   20   21   22   23   24

1.19Сравнительный анализ работы различных алгоритмов решения задачи о назначении тяговых ресурсов на поезда


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

Следующим шагом исследования было сравнение возможностей метода аукционов и методов многомерной оптимизации. Ниже приводится результаты сравнения венгерского алгоритма и метода аукционов и метода аукционов с методом имитации отжига, проведенного в рамках проекта интеллектуальных систем управления на железнодорожном транспорте (ИСУЖТ).


1.19.1.1Сравнительное моделирование применения венгерского алгоритма и метода аукционов для решения задачи о назначениях


Сравнив предложенный подход решения задачи о назначениях методом аукционов с применением венгерского алгоритма, можно отметить, что алгоритм аукционов показывает существенный прирост в скорости сходимости по сравнению с венгерским алгоритмом: 20 секунд вместо 3–4 минут (данные временные показатели не стоит оценивать в абсолютном значении, поскольку указанное исследование проводилось на языке AgentSpeak, который сам по себе довольно «медленный» язык) [111, 79].

Данная оценка времени показывает, что алгоритм аукциона сходится в Nlog(N) времени, что является значительным улучшением по сравнению с O(n4) венгерского метода.

Таблица 5.. Сравнение венгерского метода и метода аукциона


Показатели качества

Венгерский алгоритм

Метод аукциона

Время работы (имитация задачи о назначениях на AgentSpeak)

3-4 мин.

20 сек.

Вычислительная сложность

O(n3)

Nlog N

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

1.19.1.2Сравнение работы метода аукциона и метода имитации отжига


Для оценки характеристик указанных алгоритмов была проведена серия экспериментов, в которой рассматривались следующие критерии их работы: время работы, возврат нескольких решений, работа с разряженными матрицами, настройка точности, возможность увеличения размерности задачи, работа с «вытянутыми» матрицами [110]. Сравнительный анализ этих характеристик показан в Таблице 5.17.

Таблица 5.. Сравнительный анализ метода аукционов и метода имитации отжига



Критерий

Метод аукционов

Метод имитации отжига

Возврат нескольких решений

Нет

Да

Работа с «вытянутыми» матрицами

Хорошо

Большие временные затраты

Работа с разряженными матрицами

Особые случаи требуют отдельной проверки

Большие временные затраты

Время работы

36 сек.

3 мин.

Возможность увеличения размерности задачи

Нет

Да, но с большим увеличением временных затрат

Настройка точности

Нет

Да

Данные испытаний, которые использовались для анализа, приближены к реальному трафику и распределению ресурсов перевозки на участке Восточного полигона от станции Тайшет до станции Таксимо (Байкало-Амурская магистраль). Привязка тяговых ресурсов к поездам велась на горизонте в 24 часа от начала планирования.

На этом наборе данных, программа планирования грузоперевозок выполнялась дважды: в первом запуске назначение тяговых ресурсов выполнялось алгоритмом аукциона, во втором - алгоритмом имитации отжига. Основное преимущество аукциона заключается в его времени работы. Как видно из таблицы, по данным проведенных испытаний планирование заканчивается почти в четыре раза быстрее с аукционами, чем с методом имитации отжига. Аукцион также показывает лучшую производительность на наборах данных, где количество «сотрудников» значительно превышает количество «рабочих мест». Например, когда много локомотивов и локомотивных бригад доступных для некоторой операции планирования, но количество поездов относительно невелико, матрица полезности получается «растянутой»(одно из ее измерений намного больше, чем другое). С другой стороны, метод имитации отжига позволяет получить высокую гибкость при корректировке точности окончательного решения. Если набор приемлемых решений включает ряд решений с очень сходной суммарной полезностью, метод имитации отжига может быть запущен со скорректированными параметрами, с целью уменьшения количества итераций, что приводит к значительно меньшему времени выполнения без потери оптимальности решения. Это возможно, например, когда имеется несколько назначаемых бригад, которые выходят на явку в депо приписки примерно в одно и то же время.

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

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



Каталог: upload -> medialibrary
medialibrary -> Авиакомпания свяжет Хабаровск с приморским поселком Кавалерово Это направление включено в список субсидируемых государством маршрутов
medialibrary -> Число пассажиров региональной авиации Приморья приближается к 25 тысячам
medialibrary -> Россия выиграла разбирательство в международном арбитражном суде по иску немецкой компании Sana Consulting
medialibrary -> Перечень вопросов для подготовки к зачету по дисциплине «Операционные системы»
medialibrary -> 1. Рабочая программа Цели освоения дисциплины


Поделитесь с Вашими друзьями:
1   ...   16   17   18   19   20   21   22   23   24




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница