Балаханов Вадим / Владимир Кокарев, 5 курс, opt-sem

На этом форуме публикуются и уточняются постановки задач студентам, а также отслеживается ход их выполнения

Модератор: staff

Закрыто
Бычков Иван
Аспирант
Сообщения: 179
Зарегистрирован: 23 сен 2008 01:19 pm

Балаханов Вадим / Владимир Кокарев, 5 курс, opt-sem

Сообщение Бычков Иван »

Тема работы: Алгоритмы планирования в ВС РВ, основанные на методе муравьиных колоний.

Расшифровка темы: Работа является продолжением работы, выполненной на 3-м и 4-м курсах. В диплом войдут описание и исследование алгоритма построения статико-динамических расписаний (стандарт ARINC-653) и алгоритма построения расписания обмена по шине с централизованным доступом (MIL-STD 1553В). Первый из алгоритмов был реализован и исследован на 3-м и 4-м курсах, разработка второго из алгоритмов была начата в прошлом году, и основная часть работы на 5-м курсе будет заключаться в его доработке и исследовании.
В различных системах, работающих по стандарту MIL-STD 1553В, кроме ограничений стандарта, на расписание могут накладываться дополнительные технологические ограничения (сообщения с фазовыми сдвигами, цепочки сообщений и т.д.). Существующие алгоритмы (жадные) зачастую требуют значительной доработки при появлении необходимости учитывать эти дополнительные требования. Предполагается, что метод муравьиных колоний, который можно рассматривать как расширение жадных алгоритмов, позволит избегать таких сложностей за счет более широкого исследования пространства решений. Разработанный алгоритм планирования обмена должен позволять учитывать дополнительные технологические ограничения на расписание обмена без необходимости существенной доработки базового алгоритма. Также в этом году планируется разработка "контейнерной" версии муравьиного алгоритма для построения расписаний обмена, основанной на идее, описанной в дипломной работе С.Лущикова в прошлом году.

Цели дипломной работы:
1)Разработка алгоритма построения статико-динамических расписаний и алгоритма построения расписания обмена по шине с централизованным доступом, основанных на методе муравьиных колоний.
2)Реализация разработанных алгоритмов с использованием библиотеки комбинаторной оптимизации.
3)Исследование эффективности разработанных алгоритмов.

Ожидаемые результаты (с учетом результатов, полученных за два предыдущих года):
1)Доработка алгоритма планирования обмена (разработка «контейнерной» версии алгоритма, адаптация к реальным технологическим ограничениям на расписание).
2)Исследование эффективности разработанного алгоритма на реальных данных.
3)Сравнение разработанного алгоритма с существующими.
4)Написание текста дипломной работы.
Владимир Кокарев
Аспирант
Сообщения: 1
Зарегистрирован: 24 апр 2008 11:56 pm
Откуда: Москва
Контактная информация:

Отчет о проделанной работе за 9-й семестр

Сообщение Владимир Кокарев »

Отчет по научной работе за 9-й семестр

Выполнил: студент 522 группы Кокарев Владимир Александрович
Научные руководители: Костенко В.А., Балаханов В.А.

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

Цели работы:
1. Разработка алгоритма построения статико-динамических расписаний и алгоритма построения расписания обмена по шине с централизованным доступом, основанных на методе муравьиных колоний;
2. Реализация разработанных алгоритмов с использованием библиотеки комбинаторной оптимизации;
3. Исследование эффективности разработанных алгоритмов по критерию «качество получаемых решений».

Проделанная работа:
1. Предложены модификации алгоритмов, разработанных в рамках курсовых работ третьего и четвертого курсов:
a. динамическое изменение параметров алгоритма и локальной эвристики на итерациях;
b. «запуск муравьев с двух концов интервала планирования»;
2. Изучен алгоритм построения расписания обменов по шине с централизованным управлением, основанный на решении задачи об упаковке в контейнеры;
3. Проведено исследование эффективности разработанного алгоритма для построения статико-динамических расписаний по критерию «качество получаемых решений» в зависимости от характеристик исходных данных:
a. загрузки канала;
b. количества разделов;
c. количества работ;
d. среднего отношения длины директивного интервала к времени выполнения работы.

План дальнейшей работы:
1. Разработка нового гибридного алгоритма для решения задачи построения расписания обменов по шине с централизованным управлением, основанного на методе муравьиных колоний и алгоритме для решения задачи об упаковке в контейнеры;
2. Реализация разработанного алгоритма с использованием библиотеки комбинаторной оптимизации;
3. Исследование эффективности разработанных муравьиных алгоритмов для построения расписания обменов по шине с централизованным управлением на реальных данных, сравнение её с эффективностью существующих алгоритмов.

Литература:
1. Теория расписаний и вычислительные машины / Под ред. Э.Г.Коффмана. М.: Наука, 1984.
2. Штовба С.Д. Муравьиные алгоритмы: теория и применение // Программирование. 2005. №4.
3. Dorigo M., Gambardella L.M. Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem // IEEE Trans. On Evolutionary Computation. 1997. V.1. №1.
4. Stuzle T., Hoos H.H. MAX-MIN Ant System // Future Generation Computer Systems. 2000. V.16 №8. P.889-914.
5. Arinc Specification 653. Airlines Electronic Engineering Committee. [PDF] (http://www.arinc.com).
6. Dorigo M., Maniezzo V., Colorni A. Optimization by a Colony of Cooperative Agents // IEEE Trans. On Systems, Man and Cybernetics. Art B. 1996. V.26. №1. P. 29-42.
7. Гурьянов Г.С. Алгоритмы синтеза коммутационных сред с коммутацией каналов и построения статических расписаний обменов для вычислительных систем реального времени // Дипломная работа, 2005.
8. Костенко В.А., Гурьянов Е.С. Алгоритм построения расписаний обменов по шине с централизованным управлением и исследование его эффективности // 2005.
9. Костенко В.А., Кудасов А.В. Алгоритмы построения циклограмм обмена по каналу с централизованным управлением в САПР комплексирования бортовых устройств // 2006.
10. Лущиков С.Е. Дипломная работа «Алгоритмы планирования обменов по шине с централизованным управлением в вычислительных системах реального времени» // 2008.
Закрыто