Василий Балашов / Александр Барковский, 4 курс, opt-sem

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

Модератор: staff

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

Василий Балашов / Александр Барковский, 4 курс, opt-sem

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

= Постановка задачи для А. Барковского, 4 курс =

== Тема работы ==

Разработка и исследование алгоритмов формирования рекомендаций по обеспечению совместимости требований к информационному обмену на основе схемы имитации отжига.

== Контекст ==

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

С момента защиты автором курсовой на 3-м курсе, собрана значительная статистика по работе существующих алгоритмов формирования рекомендаций, что позволяет более адресно применять наработки 3-го курса по алгоритмам на основе ИО в случаях, когда существующие алгоритмы недостаточно эффективны (в 1-ю очередь по точности и стабильности результата).

== Цель работы ==

Целью работы является разработка алгоритмов формирования рекомендаций на основе схемы ИО и исследование их работы на различных классах исходных данных.

== Задачи ==

Для достижения поставленной цели необходимо решить следующие задачи:
* выполнить обзор алгоритмов, применяемых для решения дискретных задач математического программирования с линейной целевой функцией и алгоритмически (не аналитически) заданным множеством допустимых решений - подмножеством многомерного числового пространства с целочисленными значениями координат
* // обзор нужен для получения множества алгоритмов, с которыми можно пытаться сочетать алгоритмы на основе ИО для улучшения их характристик
* определить на основе экспериментальных данных классы исходных данных для формирования рекомендаций, на которых существующие алгоритмы формирования рекомендаций недостаточно эффективны
* разработать на основе схемы имитации отжига, с использованием наработок с 3-го курса, алгоритмы, ориентированные на применение к выявленным классам исходных данных
* // новые алгоритмы должны применяться в сочетании с существующими
* выполнить исследование разработанных алгоритмов по критериям точности и вычислительной сложности (чило итераций для получения решения, сложность отдельной итерации, стабильность значений этих критериев)
* // исследование должно проводиться с применением метода проверки статистических гипотез, т.к. алгоритмы на основе схемы ИО являются рандомизированными

== Ожидаемые результаты ==

* обзор алгоритмов, применяемых для решения дискретных задач математического программирования с линейной целевой функцией и алгоритмически (не аналитически) заданным множеством допустимых решений - подмножеством многомерного числового пространства с целочисленными значениями координат
* новые алгоритмы формирования рекомендаций
* экспериментальная реализация алгоритмов
* результаты экспериментального исследования
Барковский Александр

Сообщение Барковский Александр »

Разработка алгоритмов формирования рекомендаций на основе схемы имитации отжига.

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

Выполнил: студент 421 группы Барковский А.В.
Научный руководитель: м.н.с. Балашов В.В.


Введение.

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

Цель формирования рекомендаций - найти в заданных границах такие значения требований, при которых указанный алгоритм планирования способен построить расписание, при этом необходимо минимизировать затраты на переход к новому набору требований от исходного набора. Задача формирования рекомендаций сводится к задаче оптимизации с ограничениями, не заданными аналитически [1,2].

Цель работы.

Необходимо разработать и исследовать алгоритмы формирования рекомендаций на основе комбинации схемы имитации отжига и других алгоритмов оптимизации.

Результаты, полученные в данном семестре.

1. Определены классы исходных данных, на которых существующие алгоритмы формирования рекомендаций недостаточно эффективны:

- алгоритм на основе последовательного ослабления требований [2]: множество совместимости представляет собой набор несвязных областей;

- градиентный алгоритм: множество совместимости имеет сложную границу или не связно;

- алгоритм на основе последовательного усиления требований [2]: множество совместимости не связно;

2. Выполнен обзор методов оптимизации [3 - 8], в результате которого определены алгоритмы [4, 8], которые можно сочетать со схемой имитации отжига для улучшения их характеристик.

Задачи, которые планируется решить в следующем семестре.

1. Разработать алгоритмы на основе схемы имитации отжига алгоритмы, ориентированные на применение к выявленным классам исходных данных.
2. Выполнить реализацию и исследование разработанных алгоритмов по критериям точности и вычислительной сложности.

Литература.

1. Балашов В.В. Алгоритмы формирования рекомендаций при планировании информационного обмена по каналу с централизованным управлением. // Известия РАН. Теория и системы управления. 2007. № 6. С. 76-84.
2. Балашов В.В. Формирование рекомендаций по изменению требований к информационному обмену при невозможности построения циклограммы обменов по мультиплексному каналу // Труды Третьей международной конференции "Параллельные вычисления и задачи управления" (РАСО'2006). 2006. С. 422-437.
3. Nelder J.A., Mead R. A Simplex Method for Function Minimization // The Computer Journal. 1965. [7.] № 4.
4. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические Алгоритмы. Москва: ФИЗМАТЛИТ, 2006. 320 с.
5. Khachiyan L.G. A Polynomial Algorithm in Linear Programming // Soviet Math. Dokl. 1979. [20.] № 1.
6. Коган Д.И. Динамическое программирование и дискретная многокритериальная оптимизация: учебное пособие. Нижний Новгород: Изд-во Нижегородского ун-та, 2004. 150 с.
7. Simplex algorithm [HTML] (http://en.wikipedia.org/wiki/Simplex_method).
8. Branch and bound [HTML] (http://en.wikipedia.org/wiki/Branch_and_bound).
Бычков Иван
Аспирант
Сообщения: 179
Зарегистрирован: 23 сен 2008 01:19 pm

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

У вас есть какой-нибудь отчуждаемый результат?
Барковский Александр

Сообщение Барковский Александр »

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