Application of collaborative filtering methods in the problem of predicting the performance of population optimization algorithms

Full Text

Введение Актуальным и популярным подходом к решению многомерных задач непрерывной оптимизации является применение популяционных методов оптимизации [1], к которым относятся прежде всего эволюционные алгоритмы (генетические алгоритмы, метод дифференциальной эволюции), а также алгоритмы роевой оптимизации (например, метод роя частиц, алгоритм бактериального поиска) [2]. В настоящее время существуют десятки различных типов популяционных алгоритмов оптимизации и сотни их различных вариаций. Кроме того, эффективность применения алгоритмов рассматриваемого класса к различным прикладным задачам оптимизации зависит (иногда критическим образом) от достаточно большого числа параметров этих алгоритмов (так называемых метапараметров), значения которых обычно приходиться подбирать экспериментально. Перечисленные факты делают актуальной задачу подбора подходящих алгоритмов оптимизации, а также задачу настройки их мета-параметров, с целью наиболее эффективного решения заданного класса задач. В настоящей работе предлагается подход к решению этих двух проблем, основанный на применении методов коллаборативной фильтрации [3; 4], используемых традиционно при построении рекомендательных систем [5]. Описывается прототип программной системы, построенный на базе наиболее популярных популяционных алгоритмов оптимизации и системы тестовых целевых функций для задач непрерывной оптимизации, в том числе тех, которые традиционно используются при тестировании различных алгоритмов [6]. Рассматривается реализация нескольких методов предсказания эффективности работы заданного алгоритма на заданной задаче - методы на основе кластеризации набора задач, на основе вычисления близости между задачами, и на основе факторизации разреженной матрицы оценок. Приводятся результаты вычислительных экспериментов и сравнения рассматриваемых методов. Работа выполнена при финансовой поддержке РФФИ (грант № 20-07-01053 А). Исходные данные На первом этапе исследований была разработана программная система на языке программирования Python с целью автоматического тестирования заданного набора алгоритмов оптимизации на заданном наборе задач. В системе реализованы шесть семейств эволюционных и роевых алгоритмов непрерывной оптимизации (всего n = 36 алгоритмов): SA - метод имитации отжига [7]: 3 вариации на основе различных режимов отжига; GA - генетический алгоритм [8]: 12 вариаций, основанных на различных комбинациях трех генетических операторов - отбор, скрещивание и мутация; PS - метод роя частиц [9]: 3 вариации для различных схем управления величиной скорости частиц; BF - алгоритм бактериального поиска [10]: 5 вариаций для различных типов сигнальной функции, определяющей способ взаимодействия бактерий; BE - пчелиный алгоритм [11]: 8 вариаций для разных схем управления размером и плотностью областей локального поиска; DE - метод дифференциальной эволюции [12]: 5 вариаций для различных операторов скрещивания. Также в систему для исследования были включены восемь семейств задач непрерывной оптимизации (всего m = 67 задач), первые четыре являются стандартными целевыми функциями, традиционно используемые для тестирования алгоритмов непрерывной оптимизации [6], последние четыре - модельными практическими задачами непрерывной оптимизации: SPH - сферическая функция (рис. 1а), 8 вариаций: RAS - функция Растригина (рис. 1b), 8 вариаций: ROS - функция Розенброка (рис. 1c), 6 вариаций: GAU - линейная комбинация нескольких гауссианов (рис. 1d), 8 вариаций; APP - задача аппроксимации многочленами (рис. 2а), 8 вариаций; FIT - задача нелинейной аппроксимации (рис. 2b), 15 вариаций - линейная комбинация нескольких нелинейных функций, каждая из которых зависит от двух параметров (сдвиг и растяжение); NEU - задача обучения трехслойного перцептрона распознаванию различных двумерных областей (рис. 2c), 7 областей; FOL - задача укладки графа на плоскости - модельная задача предсказания трехмерной структуры белковых молекул (рис. 2d), 9 вариаций. Для проведения настоящего исследования использовались такие вариации задач оптимизации, чтобы их размерность была равна 10 (за исключением задачи обучения перцептрона, в которой минимально возможная размерность равна 15). Для оценки эффективности работы рассматриваемых алгоритмов при решении ими перечисленных задач использовалась следующая методика. Продолжительность работы каждого алгоритма определяется максимально допустимым числом вычислений целевой функции EFS = 10 000. При достижении этого значения алгоритм завершает свою работу, результатом его работы оказывается лучшее (т.е. минимальное) найденное им значение целевой функции. Так как все алгоритмы являются в той или иной степени стохастическими, то для усреднения результатов выполнялось по 100 запусков каждого алгоритма (для каждой из задач), из полученных данных выбиралось медианное значение: Fij - медианное значение результата работы i-го алгоритма на j-й задаче. Диапазоны изменения значений Fij существенно различаются для разных задач, для их выравнивания применялась процедура нормализации. Сначала значения Fij для фиксированного j линейно масштабируются в отрезок (δ, 1 - δ): где δ = 1/(n + 1), Fmin, j и Fmax, j - минимальное и максимальное значения в j-м столбце матрицы F. Найденные значения сортируются по возрастанию, порядковый номер (число от 1 до n) величины fij в упорядоченном списке, нормированный в тот же интервал (δ, 1 - δ), называется ее рангом rij. Окончательной оценкой эффективности работы i-го алгоритма при решении j-й задачи является величина равная среднему геометрическому целевой функции и ее ранга. Заметим, что все вычисленные таким образом значения Mij лежат в интервале (0, 1). Визуальное представления матрицы M показано на рис. 3. Кластерный анализ алгоритмов Согласно матрице M, каждый алгоритм может рассматриваться как точка в m-мерном пространстве, каждое измерение в котором отвечает одной из m задач. Соответственно, i-я строка этой матрицы оказывается вектором координат i-го алгоритма. Возникает естественный вопрос о распределении этих точек (т.е. алгоритмов) и об их взаимном расположении - объединяются ли они в кластеры, если да, то каким образом. Для выполнения кластерного анализа и визуализации его результатов применялись два классических метода - алгоритм K-средних (K-means) [13] и самоорганизующиеся карты Кохонена [14]. Алгоритм K-means (или метод K-средних) - это простой и быстрый метод кластеризации. Для заданного числа K этот метод строит распределение заданного набора точек (в соответствующем многомерном пространстве) по K кластерам. Данным методом минимизируется суммарное квадратичное отклонение точек в каждом кластере от центров соответствующих кластеров: где μk - центр (центроид) k-го кластера, Sk - множество точек, принадлежащих k-му кластеру (т.е. наиболее близкие к центру μk этого кластера). Выбор наиболее естественного параметра K осуществляется обычно на основе анализа изменения величины σ от параметра K - лучшие значения K соответствуют максимальным изменениям величины σ. Для рассматриваемой задачи график зависимости σ(K), приведенный на рис. 4, показывает, что оптимальным является разбиение нашего набора алгоритмов на 2-5 кластеров, т.к. последующие изменения K приводят уже к малым изменением целевой функции σ(K). Для визуализации результатов кластеризации необходимо каким-то образом отобразить точки из m-мерного пространства в двумерное пространство (т.е. на плоскость). Для этого и применяются самоорганизующиеся карты Кохонена, представляющие собой специальный вид нейронных сетей с обучением без учителя. Целью построения данных карт является нахождение такого нелинейного проецирования многомерного пространства в двумерное, при котором близкие точки в исходном многомерном пространстве оказываются близкими и в плоскости проекции. После того как карта Кохонена построена, ее клетки можно раскрасить в цвета, соответствующие, например, цветам наиболее близких к этим клеткам центров, найденных методом K-means), после чего разместить на этой же карте все точки анализируемого множества (в нашем случае - множества алгоритмов). На рис. 5 показаны результаты кластеризации рассматриваемого набора алгоритмов для случаев K = 2, 3, 4 и 5. Буквенный префикс каждой метки определяет семейство алгоритмов, а числовой суффикс - номер вариации соответствующего алгоритма. Маркерами отмечены проекции центров кластеров. Отметим, что построенное таким образом разбиение алгоритмов на кластеры оказывается очень близким к их разделению по семействам. Исключением является семейство алгоритмов дифференциальной эволюции, представители которого попадают в разные кластеры. Еще один интересный момент касается генетических алгоритмов - они образуют два независимых кластера, в первый попадают вариации, использующие турнирную схему отбора, во второй - ранговый метод отбора. Рис. 4. Зависимость целевой функции кластеризации σ и ее изменения Δσ от числа кластеров K при кластеризации алгоритмов Fig. 4. Dependence of the target function of clustering σ and its change Δσ on the number of clusters K when clustering algorithms Кластерный анализ задач По полностью аналогичной схеме была проведена и кластеризация используемого в работе набора из 67 задач, каждая из которых описывается вектором в n-мерном пространстве, координатным осям которого соответствуют различные алгоритмы. На рис. 6 приведены графики зависимости целевой функции кластеризации σ и ее изменения Δσ от числа кластеров K при кластеризации задач, которые показывают, что оптимальное число кластеров вновь находится на интервале от 2 до 5. Карты Кохонена и результаты кластеризации для K = 2, 3, 4, 5 показаны на рис. 7. Заметим, что для множества задач результаты кластеризации уже сильно отличаются от их «естественного» разделения на семейства - в большинстве кластеров присутствуют представители разных семейств задач. Возможным объяснением этого факта является сильная зависимость ландшафта целевой функции оптимизации от входных данных задачи, что наиболее актуально для последних четырех классов задач. Например, сложность обучения нейронной сети (в задаче бинарной классификации) существенно зависит от сложности распределения обучающей выборки. То же замечание справедливо и для двух классов задач аппроксимации. Аналогично, в задаче укладки графа сложность в значительной степени определяется структурой графа. Полученные результаты кластерного анализа могут быть использованы для предсказания эффективности работы различных алгоритмов при решении заданной задачи без непосредственного ее решения. Предсказание эффективности на основе средних значений Пусть в матрице M какая-то часть элементов не определена, будем называть такую матрицу разреженной. Обозначим долю в процентах неизвестных коэффициентов через α, а соответствующую разреженную матрицу через Mα. Требуется предсказать значения неопределенных элементов. Простейшим способом сделать это является использование средних значений имеющихся известных элементов матрицы. В первом случае мы можем оценить все неопределенные значения средним среди всех известных значений матрицы M. Назовем соответствующий способ предсказания методом P0. Обозначим предсказанную матрицу через M0. На рис. 8 показано распределение ошибки E0 = |M - M0| такого предсказания по результатам 200 расчетов для значения α = 25 (заметим, что данный метод слабо чувствителен к параметру α). Во втором случае значение неизвестного элемента оценивается средним значением стоящих в той же строке матрицы известных ее элементов. Этот способ назовем методом P1. Обозначим предсказанную данным методом матрицу через M1. Соответствующее распределение ошибки E1 = |M - M1| показано на рис. 9. Отметим, что средняя ошибка для второго способа предсказания примерно в два раза меньше ошибки для первого способа. Рис. 8. Матрица ошибок E0 Fig. 8. Error matrix E0 Рис. 9. Матрица ошибок E1 Fig. 9. Error matrix E1 Рис. 10. Распределение ошибки предсказания по задачам для двух методов предсказания на основе средних величин Fig. 10. Distribution of the prediction error by tasks for two prediction methods based on mean values Рис. 11. Распределение ранговой ошибки по задачам для двух методов предсказания на основе средних величин Fig. 11. Distribution of the ranking error by tasks for two prediction methods based on mean values Более важным для рассматриваемой задачи (предсказание эффективности работы различных алгоритмов при решении некоторой заданной задачи) является распределение ошибки предсказания по задачам, показанное на рис. 10 для двух рассмотренных выше методов. На рис. 11 показано распределение по задачам так называемой ранговой ошибки предсказания, которая вычисляется как расстояние между двумя перестановками, получающимся при сортировке соответствующих столбцов в полной матрице M и в предсказанной матрице M* (все расстояния на этом рисунке нормированы на среднее расстояние между двумя случайными перестановками, которое для случая n = 36 равно 12). Метод предсказания на основе средних по строкам мы будем использовать в дальнейшем для первоначального заполнения неопределенных элементов матрицы M там, где требуются величины всех ее элементов, например, для выполнения кластеризации задач или алгоритма K-Means. Кластеризация на разреженной матрице Для выполнения кластерного анализа алгоритмов или задач над разреженной матрицей Mα можно заполнить ее отсутствующие элементы средними значениями по строкам, т.е. фактически заменить эту разреженную матрицу на матрицу M1 (см. предыдущий параграф). Следует ожидать, что результат кластеризации будет некоторым образом зависеть от степени разреженности α. Для исследования степени деградации результатов кластеризации при использовании данного подхода была проведена серия вычислительных экспериментов. Для трех значений α = 25, 50 и 75 были проведены серии из 25 расчетов, в каждом из которых случайным образом строилась разреженная матрица Mα, по этой матрице методом P1 - матрица M1, для которой и применялся алгоритм кластеризации K-means для случая K = 2. Результат кластеризации сравнивался с аналогичным результатом для исходной матрицы (см. рис. 5 и 7) - для каждой пары алгоритмов (задач) вычислялось сколько раз их взаимное расположение (т.е. попадают ли они в один кластер или в разные кластеры) для разреженной матрицы отличается от их взаимного расположения для исходной матрицы. Затем для каждого алгоритма (задачи) вычислялась средняя ошибка его (ее) кластеризации относительно других алгоритмов (задач). На рис. 12 показано распределение такой ошибки при кластеризации алгоритмов, на рис. 13 - распределение этой же ошибки при кластеризации множества задач. Видно, что кластеризация алгоритмов слабо зависит от степени разреженности матрицы M. Исключения составляют 5 (из 36) алгоритмов, которые вносят свою ошибку и во все другие столбцы данной диаграммы. Средняя ошибка кластеризации для α = 75 составляет примерно 0,13. Это означает, что эти 5 алгоритмов неправильно кластеризуются примерно в половине случаев. Качество кластеризации задач более существенно зависит от степени разреженности α. Средняя ошибка для α = 75 составляет примерно 0,36, это соответствует ситуации, когда около четверти всех задач неправильно кластеризуются при каждой замене реальных значений элементов матрицы M на средние по строкам. Тем не менее, полученные показатели можно считать неплохим результатом для такой высокой степени разреженности. Рис. 12. Ошибка кластеризации алгоритмов для трех значений параметра α Fig. 12. Algorithms clustering error for three values of the parameter α Рис. 13. Ошибка кластеризации задач для трех значений параметра α Fig. 13. Tasks clustering error for three values of the parameter α Предсказание эффективности на основе кластеризации задач Для предсказания отсутствующих значений матрицы оценок M вместо глобальных средних величин представляется более целесообразным использовать средние величины в кластерах. Пусть имеется разреженная матрица Mα. Заполним пустые элементы данной матрицы средними значениями по строкам (т.е. получим матрицу M1) и выполним на основе этой матрицы кластеризацию задач с помощью метода K-Means. Пусть требуется оценить неизвестное значение Mij. Для этого найдем к какому кластеру в построенной системе кластеров принадлежит j-я задача, пусть центроид этот кластера задается вектором координат Cj. Оценим величину Mij соответствующей координатой Cij найденного центроида. В табл. 1 приведены результаты работы предложенного метода P2 для разных значений параметра K и их сравнение с методом P1 (т.е. с оценкой средними величинами по строкам). Таблица 1 Ошибка предсказания и ранговая ошибка (в скобках) методов P1 и P2 [Prediction error and ranking error (in brackets) of methods P1 and P2] α,% P1 P2, K = 2 P2, K = 3 P2, K = 4 25 0,119 (0,389) 0,103 (0,369) 0,097 (0,353) 0,093 (0,348) 50 0,119 (0,480) 0,107 (0,466) 0,105 (0,464) 0,103 (0,462) 75 0,121 (0,506) 0,117 (0,503) 0,115 (0,502) 0,115 (0,501) Для α = 25% выигрыш метода P2 (при числе кластеров K = 4) относительно метода P1 составил примерно 22% в ошибке предсказания и примерно 11% в ранговой ошибке. При больших значениях параметра α преимущество использования результатов кластерного анализа оказывается совсем незначительным. Была рассмотрена вариация описанного метода предсказания, основанная на использовании разреженного варианта метода K-Means, в котором расстояния между объектами измеряются только для координат, определенных у обоих объектах (если таких координат нет, то расстояние между этими объектами считается максимально возможным). Результаты работы такой вариации алгоритма P2, которую мы назовем методом P3, и ее сравнение с методом P1 приведены в табл. 2. Таблица 2 Ошибка предсказания и ранговая ошибка (в скобках) методов P1 и P3 [Prediction error and ranking error (in brackets) of methods P1 and P3] α, % P1 P3, K = 2 P3, K = 3 P3, K = 4 25 0,119 (0,389) 0,101 (0,367) 0,095 (0,340) 0,089 (0,337) 50 0,119 (0,480) 0,103 (0,463) 0,100 (0,453) 0,095 (0,447) 75 0,121 (0,506) 0,111 (0,508) 0,115 (0,513) 0,124 (0,532) Видно, что метод P3 показывает в большинстве случаев лучшие результаты по сравнению с методом P2 (красным цветом выделены случаи, где метод P3 оказался хуже метода P2). В частности, для случая α = 25% и K = 4 выигрыш метода P3 относительно метода P1 составил уже 25% в ошибке предсказания и примерно 15% в ранговой ошибке. Плохие результаты метода P3 при больших значениях α и K объясняется, скорее всего, нехваткой данных для кластеризации сильно разреженных векторов на большое число кластеров. Возможно, что при увеличении числа задач m эти результаты окажутся лучше. Предсказание эффективности с помощью метода k-NN Метод k-NN (k ближайших соседей, англ. k-nearest neighbors algorithm) - метрический алгоритм для автоматической классификации объектов или регрессии [15]. В случае использования метода для классификации объект присваивается тому классу, который является наиболее распространённым среди k соседей данного элемента, классы которых уже известны. В случае использования метода для регрессии, объекту присваивается среднее значение среди k ближайших к нему объектов, значения которых уже известны. Последний вариант и был применен к решению задачи предсказания отсутствующих значений матрицы оценок M. По аналогии с использованием кластеризации рассматривались две вариации метода k-NN. В первом случае (метод P4) отсутствующие элементы матрицы M заполняются средними значениями по строкам этой матрицы (т.е. с помощью метода P1). Далее к каждому столбцу m матрицы M1 применяется метод регрессии k-NN: для находятся k ближайших столбцов к столбцу m и вычисляется их среднее арифметическое mk. После этого отсутствующие элементы в текущем столбце матрицы M заменяются на соответствующие значения в векторе mk. Во втором случае (метод P5) вся работа выполняется с разреженной матрицей, для вычисления расстояния между заданными двумя ее столбцами используются только общие для этих столбцов координаты, вычисленное расстояние нормируется на корень квадратный из числа таких общих координат. Результаты применения методов P4 и P5 и их сравнение с методом P1 приведены в табл. 3 и табл. 4. Видно, что метод P4 показывает сопоставимые результаты с методами на основе кластеризации, но при этом выполняется примерно в 40 раз быстрее. А метод P5 при той же скорости работы оказывается и намного эффективнее. Его выигрыш по сравнению с методом P1 для случая α = 25% и k = 4 составляет уже примерно 40% (ошибка предсказания), а для случая α = 75% и k = 8 - примерно 17%. Кроме того, метод P5 показывает лучшие (среди рассмотренных методов) результаты и на сильно разреженных матрицах, например, при значении α = 75%. Таблица 3 Ошибка предсказания и ранговая ошибка (в скобках) методов P1 и P4 [Prediction error and ranking error (in brackets) of methods P1 and P4] α, % P1 P4, k = 2 P4, k = 4 P4, k = 8 25 0,119 (0,389) 0,092 (0,342) 0,090 (0,344) 0,094 (0,352) 50 0,119 (0,480) 0,109 (0,466) 0,108 (0,464) 0,108 (0,465) 75 0,121 (0,506) 0,119 (0,506) 0,119 (0,504) 0,118 (0,503) Таблица 4 Ошибка предсказания и ранговая ошибка (в скобках) методов P1 и P5 [Prediction error and ranking error (in brackets) of methods P1 and P5] α, % P1 P5, k = 2 P5, k = 4 P5, k = 8 25 0,119 (0,389) 0,075 (0,297) 0,073 (0,300) 0,076 (0,320) 50 0,119 (0,480) 0,087 (0,421) 0,082 (0,418) 0,082 (0,420) 75 0,121 (0,506) 0,114 (0,502) 0,104 (0,488) 0,100 (0,480) Метод предсказания на основе факторизации Еще одним классическим методом, применяемым в рекомендательных системах, является метод факторизации матрицы оценок [11]. Идея этого метода заключается в разложении матрицы M на произведение двух матриц: M = ABT. Размер матрицы A равен n на k, матрицы B - m на k, где k ∈ N - параметр. Целью разложения является минимизация ошибки, которая вычисляется как сумма квадратов отклонений соответствующих элементов матрицы ABT и исходной матрицы M. В случае разреженной матрицы Mα отклонения считаются только для имеющихся в ней элементов. В качестве оценки отсутствующих элементов берутся соответствующие значения из найденного произведения ABT. Собственно минимизация ошибки факторизации в данном методе выполняется с помощью градиентного спуска. Результаты применения метода факторизации (метод P6) и его сравнение с методов P1 приведены в табл. 5. Видно, что данный метод показывает чуть худшие результаты по сравнению с методом P5 на основе алгоритма k-NN, но лучшие, чем все остальные рассмотренные нами методы. Таблица 5 Ошибка предсказания и ранговая ошибка (в скобках) методов P1 и P6 [Prediction error and ranking error (in brackets) of methods P1 and P6] α, % P1 P6, k = 2 P6, k = 3 P6, k = 4 25 0,119 (0,389) 0,087 (0,331) 0,081 (0,325) 0,080 (0,321) 50 0,119 (0,480) 0,091 (0,438) 0,088 (0,435) 0,090 (0,442) 75 0,121 (0,506) 0,111 (0,503) 0,116 (0,522) 0,118 (0,523) Рис. 14. Визуализация факторизации матрицы M для случая k = 2 Fig. 14. Visualization of the matrix M factorization for the case k = 2 Факторизацию полной матрицы M при k = 2, можно использовать для взаимной визуализации многомерных наборов алгоритмов и задач на одной двумерной координатной плоскости, оси которой соответствуют некоторым обобщенным признакам. Пример такого отображения приведен на рис. 14. Для сравнения на этом же рисунке приведены разбиения множества алгоритмов на 4 кластера (цветные фигуры) и множества задач на 2 кластера (черный пунктир), полученные методом k-Means (см. рис. 5 и 7). Видно, что все три способа кластеризации (метод k-Means, карты Кохонена и факторизация) показывают согласованные результаты. Общее сравнение методов предсказания Сравнение трех лучших методов предсказания отсутствующих элементов матрицы M (P3 - на основе разреженной кластеризации, P5 - разреженная версия алгоритма k-NN, P6 - на основе факторизации матрицы) для степени разреженности α = 25% приведены на рис. 15 (ошибка предсказания) и на рис. 16 (ошибка ранжирования). Лучшие результаты в абсолютном большинстве случаев показал метод k-NN с числом соседей k = 4. На рис. 17 показаны результаты работы данного метода по ранжированию алгоритмов на отдельных задачах при разной степени разреженности матрицы M. Внешний круг каждой диаграммы соответствует упорядоченному списку алгоритмов согласно полной матрице M - лучший алгоритм находится вверху справа, худший - вверху слева, порядок убывания эффективности алгоритмов - по часовой стрелке. Внутренний круг соответствует упорядоченному списку этих же алгоритмов, построенному методом k-NN по разреженной матрице. Отрезками соединены одинаковые алгоритмы. Красным цветом выделены алгоритмы, оценки которых были получены методом k-NN (т.е. соответствующие пропущенным элементам матрицы M). Чем короче отрезки на диаграмме, тем лучше предсказанное методом k-NN ранжирования. Как следует из представленных диаграмм, наиболее плохим оказывается предсказание ранжирования для задачи RAS4, что соответствует и графикам на рис. 15 и 16. Рис. 15. Распределение ошибки предсказания по задачам для трех методов предсказания Fig. 15. Distribution of prediction error by tasks for three prediction methods Рис. 16. Распределение ошибки ранжирования по задачам для трех методов предсказания Fig. 16. Distribution of the ranking error by tasks for three prediction methods Рис. 17. Визуализация ошибки ранжирования для 8 задач из разных классов для трех степеней разреженности α = 25%, α = 50% и α = 75% (слева направо) Fig. 17. Visualization of the ranking error for 8 tasks from different classes for three degrees of sparsity α = 25%, α = 50% and α = 75% (from left to right) Заключение При выполнении настоящих исследований были получены следующие результаты: построена программная система для автоматического тестирования заданного набора алгоритмов непрерывной оптимизации при решении ими заданного множества задач, в том числе, модельных задач биоинформатики (задача об укладке графа) и задача обучения нейронной сети; на основе результатов выполненного тестирования с помощью метода k-Means проведен кластерный анализ включенных в систему алгоритмов и задач, предложена визуализация результатов кластерного анализа с помощью самоорганизующихся карт Кохонена; поставлена задача предсказания отсутствующих элементов в (разреженной) матрице оценок, предложено и реализовано несколько методов предсказания значений таких элементов, в том числе, метод на основе кластеризации, вариация метода k ближайших соседей (метод k-NN) и метод на основе факторизации разреженных матриц; проведена серия вычислительных экспериментов, показавшая, что для решения поставленной задачи наиболее эффективным из предложенных методов является метод k-NN. Проведенные исследования предполагается продолжить в следующих трех направлениях: расширение наборов алгоритмов и задач, в том числе за счет учета значений их мета-параметров; разработка методов предсказания эффективности рассматриваемых алгоритмов оптимизации для новых задач, т.е. задач, еще не включенных в систему; применение методов предсказания с использованием искусственных нейронных сетей.

About the authors

Nikolay M. Ershov

Lomonosov Moscow State University (MSU)

Email: ershov@gse.cs.msu.ru
Cand. Sci. (Phys.-Math.); senior research associate at the Faculty of Computational Mathematics and Cybernetics Moscow, Russian Federation

Olga P. Nikitina

Lomonosov Moscow State University (MSU)

Email: nikitinaolga_msu@mail.ru
Faculty of Computational Mathematics and Cybernetics Moscow, Russian Federation

References

Supplementary files