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

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

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

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

1, 2). На основепредложенной классификации алгоритмических систем удалось предложить иклассификацию методов их разработки. Такая классификация предложенавпервые и предоставляет разработчикам алгоритмического обеспечения новыевозможности по созданию алгоритмических комплексов и комбинированныхалгоритмов.8Рис. 1. Классификация алгоритмических систем.Рис. 2. Классификация методов построения алгоритмических систем.Предлагаетсявыделятьдвапринципиальноразныхтипаалгоритмических систем — алгоритмические комплексы и комбинированныеалгоритмы.Подтермином«алгоритмическийкомплекс»понимаетсясовокупность различных алгоритмов решения данной задачи, организованнаятаким образом, что только один из них выбирается как наиболеерациональный для текущего входа.

Такой выбор может быть основан нарезультатах:9—теоретическогоресурсногоанализакаждогоалгоритмаизрассматриваемой совокупности (классы входов определяются в ходепредварительногоисследованияалгоритмов).Выборрациональногоалгоритма осуществляется в результате решения задачи статическогораспознавания принадлежности текущего входа к одному из заранеевыделенных классов входов с априорно назначенными для этих классоврациональными алгоритмами;— динамического обучения алгоритмического комплекса, т.е.

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

Этотпорог является границей между классами, на которые в ходе кластеризациипопризнакурациональногоалгоритмаразбиваетсявсяобластьпромежуточных значений. Переключение с одного алгоритма на другойпроизводится при достижении некоторого порога переключения.Содержательно этот порог может быть, например, значением размерности10подзадачи,еслидекомпозиции.комбинированныйПорогпереключенияалгоритмможетиспользуетбытьтакжеметоднекоторымхарактерным параметром множества промежуточных результатов    Rt  ,на основе которого один из алгоритмов может быть выбран как болеепредпочтительный в текущей ситуации обработки входа в смысле выбраннойфункции качества A D .

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

Во-первых,принимая во внимание противоположный характер функций трудоемкостибазовых алгоритмов и тот факт, что метод динамического программированияпредполагает последовательное понижение размерности задачи (методдекомпозиции), можно сделать вывод, что алгоритмические системы типаалгоритмическийкомплексменееэффективны,чемсистемытипакомбинированный алгоритм. Во-вторых, в волновом алгоритме отсутствуетмодуль предвычисления порога переключения, в отличие от другихкомбинированных схем. И наконец, здесь сокращены объемы вычисленийблагодаря использованию новой структуры данных на этапе рекурсии,11позволяющей избавиться от повторных вычислений целевой функции одногоаргумента.В четвертой главе приводятся теоретический анализ волновогоалгоритма по трудоемкости, его программная реализация и результаты егоэкспериментального исследования в сравнении с базовыми точнымиалгоритмами решения задачи одномерной упаковки.В рамках теоретического анализа получены формулы полного иуникального числа обращений к строкам структуры на первом этапевыполнения алгоритма:n 1Vij  vj  k 'k k 'j 1C V , v1 , v2 ,..., vn    ...

    1 ,vni 0 i 0i 0   11n 12(1)n 12V  n1 i  v jjj 1где k n ' i1 ,..., in1   ;vnn 1Vij  vj  mn 1 'm1 m2 'j 1S V , v1 , v2 ,..., vn     ...     1  R ,vi1  0 i2 0in 1  0 n  (2)где mn1  min k 'n1 , vn  1 ; R – все k 'n i1 , i2 ,..., in1  для равных V i1 ,i2 , кромемаксимальных. В формулах (1) и (2):V  n1 i  v jjj 1i0,,i1  0, k1 1.vnТакже получена функция трудоемкости волнового алгоритма:f w n,V , k,  *   22  18  k  13  S 1;  *   2  ln S 1;  *   f n,V , k,  *  ,где вид функции f n,V , k, *  определяется порогом переключения.

Функциятрудоемкости может быть использована для прогнозирования временнойэффективности волнового алгоритма.12Численные эксперименты подтвердили ожидаемое превосходствоволнового алгоритма над базовыми. Результаты приведены на рисунках 3–8.На рисунках ниже по оси ординат указано значение трудоемкостиисследуемых алгоритмов или время выполнения программной реализации вмиллисекундах. Значение V =1000 — объем упаковки, n — число типовгрузов, а k — параметр, показывающий соразмерность общего объема исреднего объема по типам грузов.Рис.

3. Зависимости трудоемкостей от параметра k .Рис. 4. Зависимости трудоемкостей от числа типов грузов, n  3,7 .13Рис. 5. Сравнение трудоемкостей табличного и волнового алгоритмов дляn  7, 100 .Рис. 6. Зависимости временных эффективностей от параметра k .Рис.

7. Зависимости временных эффективностей алгоритмовот числа типов грузов, n  3, 7 .14Рис. 8. Сравнение временной эффективности табличного и волновогоалгоритмов для n  7, 100 .Сокращение трудоемкости волнового алгоритма относительно лучшегоиз базовых в среднем составило 73,72%. Сокращение времени работыволнового алгоритма относительно лучшего из базовых в среднем составило44,62%.

Другими словами, волновой алгоритм в среднем выполняет в 4,3раза меньше базовых операций и в среднем работает в 2 раза быстрее, чемнаиболее эффективный из пары табличный — рекурсивный для текущеговхода.ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИПубликации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ1.ГиряеваА.Н.,КомбинированныйИсаеваалгоритмА.С.,решенияНаумовазадачиО.А.,УльяноводномернойМ.В.упаковки:статически-адаптивный подход // Проблемы полиграфии и издательскогодела. 2008.

№2. С. 67–82.2. Наумова О.А., Ульянов М.В. Теоретическое определение числауникальных обращений волнового алгоритма решения задачи одномернойупаковки к строкам структуры данных // Автоматизация и современныетехнологии. 2009. №4. С. 14–21.3. Наумова О.А., Ульянов М.В.

Классификация методов построенияалгоритмических систем // Вычислительные технологии. 2011. Т. 16, № 1. С.105–118.15Публикации в других изданиях4. Гиряева А.Н., Наумова О.А. Детальный анализ трудоемкости табличногоалгоритма упаковки // Материалы международной научно-техническойконференции «Информационные технологии и системы ИСТ-2008» —Нижний Новгород: НГТУ, 2008, С. 218–219.5. Наумова О.А., Ульянов М.В., Яковлев И.А. Прогнозирование временныхоценок для табличного алгоритма решения задачи оптимальной упаковки наоснове функции трудоемкости // Бизнес-Информатика 2008. №3(5). С. 37–46.6. Наумова О.А., Ульянов М.В.

Комбинированный и волновой алгоритмырешения задачи упаковки: принципы построения и особенности // БизнесИнформатика. 2009. №2(8). С. 27–33.7. Наумова О.А. Теоретическое определение числа уникальных обращенийволнового алгоритма решения задачи одномерной упаковки к строкамструктуры данных (тезисы доклада) // Материалы XV международнойнаучно-технической конференции «Информационные технологии и системыИСТ-2009» — Нижний Новгород: НГТУ, 2009, С. 290–291.8.НаумоваО.А.Классификациякомбинированныхкомпьютерныхалгоритмов по типу определения алгоритмов по типу определения порогапереключения (тезисы доклада) // Труды 52-й Всероссийской научнойконференцииМФТИ«Современныепроблемыфундаментальныхиприкладных наук». Часть IX.

Инновации и высокие технологии — М.:МФТИ, 2009. — 166 с. С. 25-27.9. Наумова О.А., Ульянов М.В. Алгоритмические системы: классификация иметодыпостроения//Программныеинформационныесистемы:Межвузовский сборник научных трудов. Рязань: РГРТУ, 2010. 152 с. С. 74–79.10. Наумова О.А., Ульянов М.В. Классификация алгоритмических систем наоснове результатов кластеризации и классификации данных (тезисы доклада)// МатериалыXVI международной научно-технической конференции16«Информационные технологии и системы ИСТ-2010» — Нижний Новгород:НГТУ, 2010.

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

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