On application of machine-learning for designing adaptive sorting programs in algebra of algorithms

The experiment on development of adaptive sorting program on the basis of usage of algorithm selection method, machine learning system and algebra-algorithmic approach is conducted. Machine learning facilities allow to automatize constructing of adaptive algorithm on the basis of analysis of experim...

Full description

Saved in:

Bibliographic Details
Date:	2025
Main Author:	Yatsenko, O.A.
Format:	Article
Language:	Russian
Published:	PROBLEMS IN PROGRAMMING 2025
Subjects:	UDC 681.3
Online Access:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/805
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Problems in programming
Download file:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-805
record_format	ojs
resource_txt_mv	ppisoftskievua/45/b6b63d214a7ab57015f7494249eee245.pdf
spelling	pp_isofts_kiev_ua-article-8052025-08-28T20:52:26Z On application of machine-learning for designing adaptive sorting programs in algebra of algorithms О применении машинного обучения для проектирования адаптивних программ сортировки в алгебре алгоритмов Про застосування машинного навчання для проектування адаптивних програм сортування в алгебрі алгоритмів Yatsenko, O.A. UDC 681.3 УДК 681.3 УДК 681.3 The experiment on development of adaptive sorting program on the basis of usage of algorithm selection method, machine learning system and algebra-algorithmic approach is conducted. Machine learning facilities allow to automatize constructing of adaptive algorithm on the basis of analysis of experimental data, related to execution of initial algorithms. Designing of algorithms is based on usage of systems of algorithmic algebras.Prombles in programming 2011; 2: 23-33 Проведен эксперимент по разработке адаптивной программы сортировки на основе использования метода выбора алгоритмов, системы машинного обучения и алгеброалгоритмического подхода. Средства машинного обучения позволяют автоматизировать построение адаптивного алгоритма на основе анализа экспериментальных данных, связанных с выполнением исходных алгоритмов, имеющихся в распоряжении разработчика. Для проектирования алгоритмов использован язык, основывающийся на системах алгоритмических алгебр.Prombles in programming 2011; 2: 23-33 Проведено експеримент з розробки адаптивної програми сортування на основі використання методу вибору алгоритмів, системи машинного навчання і алгеброалгоритмічного підходу. Засоби машинного навчання дозволяють автоматизувати побудову адаптивного алгоритму на основі аналізу експериментальних даних, пов'язаних з виконанням початкових алгоритмів, які є у розпорядженні розробника. Для проектування алгоритмів використана мова, що ґрунтується на системах алгоритмічних алгебр.Prombles in programming 2011; 2: 23-33 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-28 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/805 PROBLEMS IN PROGRAMMING; No 2 (2011); 23-33 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2 (2011); 23-33 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2 (2011); 23-33 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/805/857 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-08-28T20:52:26Z
collection	OJS
language	Russian
topic	UDC 681.3
spellingShingle	UDC 681.3 Yatsenko, O.A. On application of machine-learning for designing adaptive sorting programs in algebra of algorithms
topic_facet	UDC 681.3 УДК 681.3 УДК 681.3
format	Article
author	Yatsenko, O.A.
author_facet	Yatsenko, O.A.
author_sort	Yatsenko, O.A.
title	On application of machine-learning for designing adaptive sorting programs in algebra of algorithms
title_short	On application of machine-learning for designing adaptive sorting programs in algebra of algorithms
title_full	On application of machine-learning for designing adaptive sorting programs in algebra of algorithms
title_fullStr	On application of machine-learning for designing adaptive sorting programs in algebra of algorithms
title_full_unstemmed	On application of machine-learning for designing adaptive sorting programs in algebra of algorithms
title_sort	on application of machine-learning for designing adaptive sorting programs in algebra of algorithms
title_alt	О применении машинного обучения для проектирования адаптивних программ сортировки в алгебре алгоритмов Про застосування машинного навчання для проектування адаптивних програм сортування в алгебрі алгоритмів
description	The experiment on development of adaptive sorting program on the basis of usage of algorithm selection method, machine learning system and algebra-algorithmic approach is conducted. Machine learning facilities allow to automatize constructing of adaptive algorithm on the basis of analysis of experimental data, related to execution of initial algorithms. Designing of algorithms is based on usage of systems of algorithmic algebras.Prombles in programming 2011; 2: 23-33
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/805
work_keys_str_mv	AT yatsenkooa onapplicationofmachinelearningfordesigningadaptivesortingprogramsinalgebraofalgorithms AT yatsenkooa oprimeneniimašinnogoobučeniâdlâproektirovaniâadaptivnihprogrammsortirovkivalgebrealgoritmov AT yatsenkooa prozastosuvannâmašinnogonavčannâdlâproektuvannâadaptivnihprogramsortuvannâvalgebríalgoritmív
first_indexed	2025-09-17T09:23:29Z
last_indexed	2025-09-17T09:23:29Z
_version_	1850410452494843904
fulltext	Інструментальні засоби і середовища програмування © Яценко Е.А., 2011 23 УДК 681.3 Е.А. Яценко О ПРИМЕНЕНИИ МАШИННОГО ОБУЧЕНИЯ ДЛЯ ПРОЕКТИРОВАНИЯ АДАПТИВНЫХ ПРОГРАММ СОРТИРОВКИ В АЛГЕБРЕ АЛГОРИТМОВ Проведен эксперимент по разработке адаптивной программы сортировки на основе использования ме- тода выбора алгоритмов, системы машинного обучения и алгеброалгоритмического подхода. Средства машинного обучения позволяют автоматизировать построение адаптивного алгоритма на основе анали- за экспериментальных данных, связанных с выполнением исходных алгоритмов, имеющихся в распо- ряжении разработчика. Для проектирования алгоритмов использован язык, основывающийся на систе- мах алгоритмических алгебр. Введение В работах [1–3] создана инструмен- тальная система программирования, на- званная Интегрированным инструмента- рием Проектирования и Синтеза программ (ИПС), основывающаяся на системах ал- горитмических алгебр (САА) В.М. Глуш- кова [1]. В системе совместно используют- ся три формы представления знаний: ана- литическая (формула в алгебре алгорит- мов), естественно-лингвистическая (тек- стовая) и графовая (граф-схемы). Особен- ность инструментария состоит также в ис- пользовании метода диалогового конст- руирования синтаксически правильных программ, ориентированном на исключе- ние возникновения синтаксических оши- бок в процессе проектирования. В упомя- нутых работах система была применена для синтеза многопоточных, кластерных, Грид-программ по схемам асинхронных алгоритмов. При этом исследовалось так- же совместное использование ИПС и сис- темы переписывания правил TermWare [4] для автоматизации трансформации про- грамм. В последнее время все больше воз- растает необходимость в разработке про- граммных приложений, которые способ- ны не только выполнять однажды задан- ную в алгоритме последовательность дей- ствий над предварительно определенными данными, но и способны сами анализиро- вать поступающую информацию, находить в ней закономерности, выполнять про- гнозирование и т. д. Создание подобных программ связано с необходимостью на- копления и анализа большого количества экспериментальных данных (входных, промежуточных и результирующих). При этом возникает проблема автоматизации извлечения полезной информации из большого объема данных. Решение данной задачи осуществляется в рамках техноло- гии интеллектуального анализа данных (ИАД) (Data Mining) [5] – одной из актив- но развивающихся областей информаци- онных технологий, предназначенной для выявления полезных знаний из баз данных различной природы. Учитывая вышесказанное в данной работе проведен эксперимент по разработ- ке адаптивной программы сортировки, со- вмещающий проектирование в алгебре ал- горитмов и интеллектуальный анализ дан- ных. Под адаптивным понимается алго- ритм, учитывающий характеристики вход- ных данных и выбирающий наилучшую стратегию их обработки. При этом исполь- зована концепция задачи выбора алгорит- ма [6]. Цель упомянутой задачи – это от- вет на вопрос “Какой из имеющихся алго- ритмов выполнится наилучшим образом при решении заданной вычислительной проблемы?”. Исследованию данной задачи посвящены работы в различных предмет- ных областях: прогнозирование времен- ных рядов [7]; задачи удовлетворения ог- раничений (constraint satisfaction prob- lem) [8]; оптимизация [9]; сортировка [10, 11]. В упомянутых работах автоматизация выбора алгоритмов выполняется с использо- ванием ИАД и методов машинного обучения. ISSN 1727-4907. Проблеми програмування. 2011. № 2 Інструментальні засоби і середовища програмування Суть предложенного в данной рабо- те подхода к разработке адаптивной про- граммы сортировки состоит в следующем. Исходные алгоритмы сортировки проекти- руются с использованием алгебраических средств в системе ИПС и затем выполня- ются на тестовой совокупности числовых массивов. Далее полученные эксперимен- тальные данные анализируются в системе интеллектуального анализа данных We- ka [12] с применением машинного обуче- ния. Полученная в результате анализа обу- чающая модель (дерево решений) преобра- зуется в алгебраическую спецификацию (САА-схему) адаптивного алгоритма, со- держащую информацию о выборе наи- лучшей стратегии сортировки в зависимо- сти от характеристик входных данных. За- тем схема преобразуется в код на целевом языке программирования (С++). В работе проведено сравнение производительности исходных алгоритмов и разработанной адаптивной программы. Материал работы состоит из разде- лов. В разделе 1 рассматривается концеп- ция задачи выбора алгоритма и методы машинного обучения, связанные с ее ре- шением. Раздел 2 посвящен результатам проведенного эксперимента по разработке программы выбора алгоритма сортировки. 1. Проблема выбора алгоритма и машинное обучение Цель задачи выбора алгоритма – это выбор наилучшего алгоритма для заданной вычислительной проблемы в соответствии с некоторыми ее характеристиками. Фор- мальная модель проблемы выбора алго- ритма была разработана Д. Райсом [6]. Упомянутая модель может быть использо- вана для ответа на вопрос: “Какой из имеющихся у разработчика алгоритмов наилучшим образом подходит для реше- ния задачи и определенных входных дан- ных?”. Основными компонентами модели являются следующие: • пространство задач P представля- ет множество экземпляров класса задач; • пространство свойств F содержит измеримые характеристики (метрики) за- дач P; • пространство алгоритмов A является множеством всех рассматриваемых алгоритмов, предназначенных для решения задачи; • пространство производительности Y представляет отображение каждого ал- горитма во множество показателей произ- водительности. Далее проблема выбора алгоритма может быть сформулирована следующим образом. Для заданного экземпляра задачи Px∈ , со свойствами , необходи- мо найти отображение S(f(x)) в простран- ство алгоритмов A, такое, что выбранный алгоритм Fxf ∈)( A∈α максимизирует отображе- ние производительности y(α(x))∈Y. Выбор свойств F в значительной степени зависит от предметной области и выбранных алгоритмов. Например, при рассмотрении алгоритмов сортировки по- следовательностей чисел, свойством явля- ется степень отсортированности входной последовательности. Показателем произ- водительности может служить время вы- полнения алгоритма в секундах. С использованием правил “если-то” решение задачи выбора алгоритма может быть, например, сформулировано так: если входящие данные имеют ха- рактеристики C1, C2, ..., Cn, то использо- вать алгоритм A1 вместо алгоритма A2. Выбор алгоритма может осуществ- ляться статически или динамически. Ста- тическая программа выбора алгоритма де- лает выбор до начала выполнения алго- ритма и затем передает управление вы- бранному алгоритму. В отличие от стати- ческой, динамическая система выбора ал- горитма может изменять его выбор дина- мически, контролируя выполнение алго- ритма. В реальных ситуациях, выбор алго- ритма выполняется вручную экспертами, которые имеют хорошее теоретическое понимание вычислительной сложности различных алгоритмов и хорошо знакомы с их свойствами во время выполнения. Одним из способов автоматизации выбора 24 Інструментальні засоби і середовища програмування 25 алгоритма является применение машинно- го обучения [6]. Проблеме автоматизации выбора алгоритмов для задач сортировки посвя- щены работы [10, 11]. В работе [10] при выборе алгоритма сортировки в качестве единственного свойства задачи рассматри- вается длина последовательности, подле- жащей обработке. В процессе выбора ал- горитма использовано динамическое про- граммирование. Более подробное исследо- вание проведено в [11] с использованием машинного обучения. В упомянутой рабо- те помимо размера массива учитывается степень его отсортированности. Исследо- ваны три метрики отсортированности: ко- личество перестановок (inversions, INV); количество возрастающих подпоследова- тельностей (RUN); длина наибольшего подмассива (LAS). Показано, что наиболее эффективным является использование единственной метрики – RUN. Данная работа также посвящена решению задачи выбора алгоритмов сор- тировки; при этом использован подход, разработанный в [11]. Основным отличием данной работы является использование ал- геброалгоритмического подхода при раз- работке алгоритмов, позволяющего ис- пользовать высокоуровневые специфика- ции, не зависящие от реализации на кон- кретном языке программирования. В работе [11] проблема выбора ал- горитма сформулирована как задача клас- сификации, являющаяся одним из методов машинного обучения. Определение. Пусть имеется набор объектов, каждый из которых принадле- жит одному из m классов. Задачей класси- фикации является составление правила, по которому для любого объекта можно с большой степенью достоверности опреде- лить класс, которому данный объект при- надлежит [5]. Пусть X = {x1, ..., xk} – множество атрибутов объекта, Y = {1, …, m} – мно- жество номеров (или наименований) клас- сов. В результате классификации должна быть получена целевая функция f: X → Y. Целевая функция f(x1, ..., xk) сопоставляет объекту с атрибутами x1, ..., xk соответст- вующий номер (метку) класса, к которому этот объект принадлежит. Например, в случае задачи выбора алгоритма сортировки объектами задачи классификации являются обрабатываемые массивы [11]. Атрибутами объектов явля- ются: • x1 – длина массива; • x2 – степень отсортированности. Метками классов являются назва- ния различных алгоритмов сортировки (сортировка вставками, быстрая и т. д.). Функция f(x1, x2) сопоставляет каждому входному массиву название наилучшего (по времени выполнения) алгоритма, кото- рым его необходимо сортировать. Более подробно пример описания данных для данной задачи рассматривается в разде- ле 2. В распоряжении у исследователя обычно имеется некоторый набор объек- тов, у которых метка класса уже известна. Эти объекты могут быть использованы для обучения модели, т. е. подбора параметров модели классификации и для тестирования построенной модели классификации. Классификация с обучением подра- зумевает следующие действия: 1) подготовка данных. Имеющийся набор объектов с известными метками классов разбивается на две части: обу- чающую выборку и тестовую выборку. Желательно, чтобы это разбиение было произведено случайным образом. Чаще всего обучающая выборка имеет размер больше, чем тестовая; 2) обучение модели. Параметры мо- дели классификации подбираются на ос- нове обучающей выборки таким образом, чтобы добиться наилучшего соответствия между предсказанными и фактическими метками классов; 3) тестирование модели. Получен- ная в результате обучения модель прове- ряется на достоверность. Для этого вычис- ляется процент неверных результатов классификации объектов из тестовой вы- борки. Классификация с обучением имеет множество приложений, например, в таких областях, как кредитование, медицинская Інструментальні засоби і середовища програмування диагностика, предсказание доходов, мар- кетинг. К известным методам классифика- ции с обучением относятся деревья реше- ний, нейронные сети, сети Байеса [5]. В работе [11] показано, что наилучшим в случае задачи выбора алгоритмов сорти- ровки является использование деревьев решений. Дерево решений – это дерево, в ко- тором каждой внутренней вершине по- ставлен в соответствие некоторый атрибут, каждая ветвь, выходящая из данной вер- шины, соответствует одному из возмож- ных значений атрибута, а каждому листу дерева сопоставлен конкретный класс или набор вероятностей классов [5, 13]. На рис. 1 в качестве примера представлено упрощенное дерево решений для выбора одного из алгоритмов сортировки в зави- симости от размера массива. Дерево по- строено на основе экспериментальных данных, приведенных в работе [10]. В раз- деле 2 рассматривается построенное дере- во решений, дополнительно учитывающее степень отсортированности обрабатывае- мых массивов. Для того чтобы классифицировать новый объект, необходимо двигаться по дереву сверху вниз, начиная с корня. При этом на каждом внутреннем узле дерева выбирается та ветвь, которая соответству- ет фактическому значению соответствую- щего атрибута. Добравшись до листа дере- ва, получаем тот класс, которому принад- лежит объект согласно классифицирую- щему правилу. Существуют различные ал- горитмы построения деревьев решений: ID3, C4.5, NewId, ITrule, CN2 и др. [5]. В данной работе, как и в [11], для проведения экспериментов была выбрана система машинного обучения Weka (Waikato Environment for Knowledge Analysis) [12]. Weka представляет собой набор средств визуализации и библиотеку алгоритмов машинного обучения для ре- шения задач интеллектуального анализа данных и прогнозирования, с графической пользовательской оболочкой для доступа к ним. Система является свободным про- граммным обеспечением, разработанным на языке Java в университете Вайкато (Но- вая Зеландия). На сегодняшний день она является лучшей библиотекой с открытым кодом для анализа данных. Weka позволя- ет непосредственно применять алгоритмы к выборкам данных, а также вызывать ал- горитмы из программ на Java. Для исполь- зования Weka из систем, реализованных на других платформах, возможен вызов алго- ритмов через интерфейс командной стро- ки. Система позволяет выполнять такие задачи анализа данных, как: • подготовка данных – предвари- тельная обработка (preprocessing); • отбор признаков (feature selection); • кластеризация; Сортировка слиянием Размер массива > 32 Быстрая сортировка ≤ 32 Сортировка вставками Размер массива ≤ 21 > 21 Рис. 1. Пример дерева решений 26 Інструментальні засоби і середовища програмування 27 • классификация, в частности, де- ревья решений; • поиск ассоциативных правил; • регрессионный анализ; • визуализация результатов. Система Weka также подходит для разработки новых подходов в машинном обучении. Пользователями Weka являются исследователи в области машинного обу- чения и прикладных наук, она также ши- роко используется в учебных целях. Исходные данные в упомянутой системе представлены в виде матрицы признаковых описаний объектов, пример такой таблицы рассматривается в подраз- деле 2.2. 2. Применение метода выбора алгоритма для сортировок Цель проведенного в данной работе эксперимента состояла в построении адап- тивного алгоритма сортировки массивов на основе имеющихся, с использованием метода выбора алгоритма и машинного обучения, рассмотренных в разделе 1. Бы- ли использованы 5 алгоритмов: сортировка вставками (insertion sort), сортировка Шел- ла (shell sort), пирамидальная сортировка (heap sort), сортировка слиянием (merge sort), быстрая сортировка (quick sort) [14]. В адаптивной сортировке учитываются свойства обрабатываемого массива – дли- на и степень неотсортированности. Для проектирования алгоритмов использованы средства САА (см. подраздел 2.1); затем алгоритмы реализованы на языке С++. Эксперимент состоял из следующих этапов: 1) подготовка обучающих данных (обучающей выборки). Произведена гене- рация входных массивов с различными ха- рактеристиками и затем каждый из алго- ритмов сортировки по очереди был вы- полнен на этих данных. Алгоритм, выпол- нившийся за наименьшее время, был обо- значен как наилучший. Собственно обу- чающие данные являются таблицей с ин- формацией о размере массива, степени его неотсортированности и наилучшем алго- ритме; 2) выполнение обучающего алго- ритма, а именно, обучения с использова- нием дерева решений (см. раздел 1) на обучающей выборке в системе Weka; 3) преобразование дерева решений в САА-схему; 4) генерация по САА-схеме кода на целевом языке программирования; 5) сравнение времени выполнения адаптивного алгоритма и исходных алго- ритмов на тестовом наборе массивов. Перечисленные этапы более под- робно рассматриваются в подразделе 2.2. 2.1. Формализованное проектиро- вание программ в системах алгорит- мических алгебр. В основу проектирова- ния программ сортировки в рамках данной работы положен аппарат САА (системы алгоритмических алгебр) В.М. Глуш- кова [1]. САА являются двухосновной ал- геброй < U, B; Ω >, где U – множество операторов, B – множество логических ус- ловий. Сигнатура операций Ω = Ω1 ∪ Ω2 состоит из системы Ω1 логических опера- ций и операторных Ω2 операций. На САА базируется алгоритмический язык САА/1, используемый для проектирования про- грамм в ИПС. Данный язык предназначен для многоуровневого структурного проек- тирования и документирования последова- тельных и параллельных алгоритмов и программ. Преимуществом его использо- вания является возможность описания ал- горитмов в естественно-лингвистической форме (САА-схемы), удобной для челове- ка, что облегчает достижение требуемого качества программ. Перечислим основные операции, используемые для разработки схем алгоритмов. Составные условия строятся из ба- зисных с помощью логических операций САА: • дизъюнкция: ‘условие1’ ИЛИ ‘ус- ловие2’; • конъюнкция: ‘условие1’ И ‘усло- вие2’; • отрицание: НЕ ‘условие’. Составные операторы строятся из элементарных посредством операций: • “оператор1” ЗАТЕМ “оператор2” – последовательное выполнение операто- ров; • ЕСЛИ ‘условие’ ТО “оператор1” Інструментальні засоби і середовища програмування ИНАЧЕ “оператор2” КОНЕЦ ЕСЛИ – опе- ратор ветвления; • ПОКА НЕ ‘условие_окончания_ цикла’ ЦИКЛ “оператор” КОНЕЦ ЦИКЛА – оператор цикла. В работах [1, 3] аппарат САА-М применен при решении задач символьной мультиобработки: последовательных и па- раллельных сортировок, поиска, языкового процессирования и др. В качестве примера приведем САА- схему сортировки вставками входного массива A длины n: СХЕМА insertionSort(A, n) ==== ДЛЯ '(i) от (1) до (n)' ЦИКЛ "(temp := a[i])" ЗАТЕМ "(j := i – 1)" ПОКА НЕ 'temp < a[j]' И 'j >= 0' ЦИКЛ "(a[j + 1] := a[j])" ЗАТЕМ "(j := j – 1)" КОНЕЦ ЦИКЛА "(a[j + 1] := temp)" КОНЕЦ ЦИКЛА КОНЕЦ СХЕМЫ insertionSort(A, n) 2.2. Результаты эксперимента. Для проведения эксперимента были подготов- лены 5 алгоритмов сортировки, перечис- ленные в начале раздела 2, а также разра- ботана программа (С++), позволяющая вы- зывать данные алгоритмы и сравнивать время их выполнения на различных вход- ных массивах. Впоследствии данная про- грамма также была дополнена адаптивным алгоритмом, выбирающим наилучший ал- горитм сортировки в зависимости от дли- ны и степени неотсортированности вход- ного массива. В данной работе степень неотсор- тированности массива A длины n вычисля- ется по формуле [11] n runs(A) runs'(A) = , где runs(A) – количество возрастающих (отсортированных) подмассивов (англ. “runs up”) в сортируемом массиве. Метри- ка runs'(A) принимает значения в диапазо- не (0 … 1]. Например, для массива A = < \|10\| 4 5 7\| 1 3\| 2 6 9\| 8\| >, runs(A) = 5; runs' = 0.5. Для отсортированного массива длины n степень неотсортированности runs'(A) = 1 / n; для массива чисел, распо- ложенных в обратном порядке runs'(A) = = n / n = 1. В работе [11] показано, что для рас- сматриваемой задачи использование при- веденной метрики является наиболее эф- фективным. Для сравнения производительности алгоритмов сортировки на различных входных массивах была разработана про- грамма генерации числовых массивов с различной степенью неотсортированности. С помощью данной программы подготов- лен набор из 800 числовых массивов раз- мером от 10 до 100 элементов. Упомяну- тый набор включал следующие типы мас- сивов: • 500 массивов со случайно пере- мешанными элементами, для генерации которых использован алгоритм “Algorithm 235” (Random Permutation) [15]; • 150 почти отсортированных мас- сивов (nearly-sorted arrays [11, 16]). Такие массивы сгенерированы путем занесения в каждый массив последовательности чисел 1, 2, ..., n. Затем выполнена перестановка случайных пар элементов, количество ко- торых составляет от 0 до 10 % от длины массива; • 150 массивов с элементами, рас- положенными в обратном порядке, с не- значительным количеством перестановок. Генерация упомянутых массивов произво- дится аналогично предыдущим, но в этом случае в массив вначале заносится обрат- ная последовательность чисел: n, n–1, ..., ..., 2, 1. В разработанной программе сорти- ровки для каждого массива из упомянуто- го набора вначале вычисляется степень не- отсортированности и затем по очереди за- 28 Інструментальні засоби і середовища програмування 29 пускаются 5 различных алгоритмов сорти- ровки. Длина входного массива, величина runs', а также название наилучшего алго- ритма (который выполнился за наимень- шее количество времени), записывается в файл в виде таблицы (см. табл. 1). Данный файл представляет собой набор обучаю- щих данных, передаваемых в систему We- ka. Поле “Наилучший алгоритм”, указан- ное в таблице, является целевым атрибу- том, значение которого будет прогнозиро- ваться на основе значений других атрибу- тов обрабатываемого массива. В результа- те эксперимента наилучшими в различных случаях оказались два из пяти рассматри- ваемых алгоритмов – сортировка вставка- ми и быстрая сортировка. На рис. 2 и рис. 3 показаны графики распределения величин “размер массива” и “степень неотсортированности” для рас- сматриваемого набора обучающих данных. В системе Weka к полученным экс- периментальным данным был применен алгоритм построения дерева решений J4.8 (реализация алгоритма C4.5 на языке Java [12]), результирующее дерево показа- но на рис. 4. Листья дерева соответствуют выбору одного из алгоритмов. Из рисунка видно, в частности, что при небольших значениях степени неотсортированности, runs' ≤ 0.4, наилучшим является алгоритм сортировки вставками не зависимо от раз- мера массива. В остальных случаях выбор алгоритма зависит от размера и значения runs'. Точность классификации с помощью данной модели при проверке на рассмат- риваемых обучающих данных составила 93.625 %. Далее на основе построенного дере- ва система Weka может использоваться для прогнозирования наилучшего алго- ритма для произвольного входного масси- ва. Для этого в систему необходимо пере- дать файл с таблицей, аналогичной табли- це 1, в которой приведена строка (или не- сколько строк) со значением размера мас- сива, степени неотсортированности, а в поле “Наилучший алгоритм” указать сим- вол “?”. Однако, при вызове данной систе- мы из программы сортировки возникают дополнительные накладные расходы по времени. Поэтому в данной работе дерево решений преобразуется сначала в САА- схему, а затем в подпрограмму на целевом языке программирования (С++), которая включается в программу сортировки. По полученному дереву была по- строена САА-схема выбора алгоритма сортировки adaptiveSort(A, n), приве- денная далее. В приведенной схеме для входяще- го массива, подлежащего сортировке, вна- чале вычисляется степень неотсортиро- ванности. Затем в зависимости от длины массива и величины runs' вызывается со- ответствующий алгоритм. Полученный ал- горитм был назван адаптивным алгорит- мом сортировки. Таблица 1. Пример обучающих данных, поступающих на вход системы Weka Номер массива Размер массива (n) Степень неотсортирован- ности (runs') Наилучший алгоритм 1 10.0 0.1 insertion 2 10.0 0.3 insertion 3 10.0 0.4 insertion 4 10.0 0.5 insertion 5 10.0 0.6 insertion 6 10.0 0.7 insertion 7 10.0 0.9 quick 8 10.0 1.0 quick Інструментальні засоби і середовища програмування Рис. 2. Распределение величины “размер массива” для обучающих данных со значениями “insertion” и “quick” Рис. 3. Распределение величины “степень неотсортированности” для обучающих данных со значениями “insertion” и “quick” 30 Інструментальні засоби і середовища програмування 31 Рис. 4. Дерево решений для сортировки СХЕМА adaptiveSort(A, n) ==== "(runs := "Вычислить степень неотсортированности массива (A) длины (n)")" ЕСЛИ ‘runs <= 0.4’ ТО "insertionSort(A, n)" ИНАЧЕ ЕСЛИ ‘runs > 0.4’ ТО ЕСЛИ ‘size <= 50’ ТО ЕСЛИ ‘runs <= 0.8125’ ТО ЕСЛИ ‘size <= 30’ ТО ЕСЛИ ‘runs <= 0.7’ ТО "insertionSort(A, n)" ИНАЧЕ ЕСЛИ ‘runs > 0.7’ ТО ЕСЛИ ‘size <= 10’ ТО "insertionSort(A, n)" ИНАЧЕ ЕСЛИ ‘size > 10’ ТО "quickSort(A, 0, n-1)" КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ ИНАЧЕ ЕСЛИ ‘size > 30’ ТО ЕСЛИ ‘size <= 40’ ТО "insertionSort(A, n)" ИНАЧЕ ЕСЛИ ‘size > 40’ ТО "quickSort(A, 0, n-1)" КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ Інструментальні засоби і середовища програмування ИНАЧЕ ЕСЛИ ‘runs > 0.8125’ ТО "quickSort(A, 0, n-1)" КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ ИНАЧЕ ЕСЛИ ‘size > 50’ ТО "quickSort(A, 0, n-1)" КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ КОНЕЦ СХЕМЫ adaptiveSort(A, n) Для проверки эффективности полу- ченного адаптивного алгоритма был под- готовлен тестовый набор из 140 массивов трех вышеупомянутых видов. Экспери- мент производился на Intel Core 2 Quad CPU, 2.51 ГГц; ОС Windows XP. На рис. 5 показано суммарное время выполнения на всех массивах каждого из 5 алгоритмов сортировки и адаптивного алгоритма в микросекундах. Время выполнения adaptiveSort(A, n) является наимень- шим, что свидетельствует об эффективно- сти предлагаемого подхода. Заключение Проведен эксперимент по разработ- ке адаптивной программы сортировки на основе использования метода выбора ал- горитмов, системы машинного обучения и алгеброалгоритмического подхода. Сред- ства машинного обучения позволяют ав- томатизировать построение адаптивного алгоритма на основе анализа эксперимен- тальных данных, связанных с выполнени- ем исходных алгоритмов, имеющихся в распоряжении разработчика. Для проекти- рования алгоритмов использован язык САА-схем, преимуществом которого яв- ляются простота в обучении и использова- нии, а также независимость от языка про- граммирования и возможность переведе- ния в произвольный целевой язык. Прове- денный вычислительный эксперимент по- казал большую производительность разра- ботанного адаптивного алгоритма в срав- нении с исходными, что свидетельствует об эффективности разработанного подхода. 32 Рис. 5. Суммарное время выполнения алгоритмов сортировки на тестовом наборе из 140 массивов (длина каждого массива – 100 элементов) Інструментальні засоби і середовища програмування 33 Перспективами дальнейших иссле- дований в данном направлении являются интеграция системы ИПС и системы Weka, а также использование предложенного подхода для других предметных областей. 1. Андон Ф.И., Дорошенко А.Е., Цейт- лин Г.Е., Яценко Е.А. Алгеброалгоритмиче- ские модели и методы параллельного про- граммирования. – Киев: Академпериодика, 2007. – 631 с. 2. Дорошенко А.Е., Жереб К.А., Яценко Е.А. Об оценке сложности и координации вы- числений в многопоточных программах // Проблеми програмування. – 2007. – № 2. – С. 41–55. 3. Дорошенко А.Е., Яценко Е.А. Средства сер- висно-ориентированного программирова- ния параллельных программ // Проблеми програмування. – 2009. – № 2. – С. 12–21. 4. Дорошенко А.Е., Шевченко Р.С. Система символьных вычислений для программи- рования динамических приложений // Про- блемы программирования. – 2005. – № 4. – С. 718–727. 5. Степанов Р.Г. Технология Data Mining: Интеллектуальный анализ данных. – 2008. – http://m8.ksu.ru/EOS/dm.pdf 6. Smith-Miles K.A. Cross-Disciplinary perspec- tives on meta-learning for algorithm selection. ACM Comput. Surv., 41, 1, Article 6 (De- cember 2008). – 2008. – 25 p. 7. Wang X., Smith K.A., Hyndman R. Character- istic-Based clustering for time series data. Data Mining Knowl. Discov. 13. – 2006. – P. 335–364. 8. Samulowitz H., Memisevic R. Learning to solve QBF. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence. – 2007. – P. 255–260. 9. Smith-Miles K.A. Towards insightful algo- rithm selection for optimisation using meta- learning concepts. In Proceedings of the IEEE Joint Conference on Neural Networks. – 2008. – P. 4118–4124. 10. Lagoudakis M., Littman M., Parr R. Selecting the right algorithm. In Proceedings of the AAAI Fall Symposium Series: Using Uncer- tainty within Computation. – 2001. 11. Guo H. Algorithm selection for sorting and probabilistic inference: A machine learning- based approach. Ph.D. dissertation, Kansas State University. – 2003. 12. Weka Project home page. – http://www.cs. waikato.ac.nz/ml/weka/ 13. Деревья решений – общие принципы рабо- ты. – http://www.basegroup.ru/library/analy- sis/tree/description/ 14. Кнут Д. Искусство программирования для ЭВМ. – М.: Мир, 1978. – Т. 3. – 843 с. 15. Durstenfeld R. Algorithm 235: Random per- mutation. Communications of the Association for Computing Machinery, 7:420. – 1964. 16. Slightly Skeptical View on Sorting Algo- rithms. – http://www.softpanorama.org/Algo- rithms/sorting.shtml Получено 16.03.2011 Об авторе: Яценко Елена Анатольевна, кандидат физико-математических наук, старший научный сотрудник. Место работы автора: Институт программных систем НАН Украины. Тел.: (044) 424 4972, e-mail: oayat@ukr.net http://m8.ksu.ru/EOS/dm.pdf http://www.basegroup.ru/library/analysis/tree/description/ http://www.basegroup.ru/library/analysis/tree/description/ http://www.softpanorama.org/Algorithms/sorting.shtml http://www.softpanorama.org/Algorithms/sorting.shtml Введение 1. Проблема выбора алгоритма и машинное обучение 2. Применение метода выбора алгоритма для сортировок Заключение

On application of machine-learning for designing adaptive sorting programs in algebra of algorithms

Institution

Similar Items