Клименко Анна Борисовна, кандидат технических наук, доцент кафедры Фундаментальной и прикладной математики
ул. Академика Янгела, д. 25, к. 2, г. Москва 117534
Anna B. Klimenko, Cand. of Sci. (Engineering), Associate Professor, Fundamental and Applied Mathematics department
25, building 2 Academician Yangel str., Moscow 117534
Алиева Эльвира Мурадовна, студент кафедры Фундаментальной и прикладной математики
ул. Академика Янгела, д. 25, к. 2, г. Москва 117534
Elvira M. Alieva, Student of Fundamental and Applied Mathematics department
25, building 2 Academician Yangel str., Moscow 117534
Сальников Андрей Евгеньевич, студент кафедры Фундаментальной и прикладной математики
ул. Академика Янгела, д. 25, к. 2, г. Москва 117534
Andrey Y. Salnikov, Student of Fundamental and Applied Mathematics department
25, building 2 Academician Yangel str., Moscow 117534
Цель исследования. Цель данного исследования – разработка структуры онтологии как основы базы данных/базы знаний для выбора эффективных метаэвристических алгоритмов решения задачи распределения нагрузки в гетерогенных распределенных динамичных вычислительных средах с учетом накладных расходов на передачу данных по сети.
Методы. Основными научными методами, применяемыми в рамках данного исследования, являются анализ предметной области, методы построения предметных онтологий, численные методы оптимизации и компьютерное моделирование. Поскольку в литературе не представлены модели планирования выделения ресурсов, которые бы учитывали географическую распределенность, наличие промежуточных маршрутов передачи данных, динамику топологий и нагрузки, а также гетерогенность системы в аспекте критериев оценивания качества распределения нагрузки, в данной статье предложена новая модель, учитывающая перечисленные особенности. Трудоемкость решения задачи планирования становится одним из варьируемых параметров, который при этом оказывает значительное влияние на результат планирования: с уменьшением трудоемкости вычислений, соответственно ухудшается результат. Поэтому в качестве метода решения предлагается жадная стратегия: из подлежащих рассмотрению методов оптимизации выбрать такой наименее трудоемкий, который бы позволял получить наилучший результат за выделенное время. Тестовые запуски алгоритмов имитации отжига демонстрируют различную эффективность на различных исходных условиях задачи, следовательно, целесообразно для выделенных классов задач выбрать эффективные в смысле качества решения и трудоемкости алгоритмы.
Результаты. Результатом исследования является структура онтологии эффективных алгоритмов. Также результатами являются вошедшие в состав онтологии экземпляры алгоритмов имитации отжига и задач, связанные отношением «эффективности».
Заключение. В данной статье предложены структура онтологии эффективных алгоритмов оптимизации и подход к решению задачи распределения вычислительной нагрузки с учетом трудоемкости процедуры распределения посредством «жадного» выбора наиболее эффективных алгоритмов оптимизации.
Purpose of research. The purpose of this research is to develop an ontology structure as the basis of a database/knowledge base for selecting effective metaheuristic algorithms for solving the problem of load distribution in heterogeneous distributed dynamic computing environments, taking into account the overhead of data transmission over the network.
Methods. The main scientific methods used in this study are domain analysis, methods for constructing subject ontologies, numerical optimization methods and computer modeling.
Since the literature does not present resource allocation planning models that would take into account geographic distribution, the presence of intermediate data transmission routes, the dynamics of topologies and load, as well as system heterogeneity in terms of criteria for assessing the quality of load distribution, this article proposes a new model that takes into account these features. The complexity of solving a planning problem becomes one of the variable parameters, which has a significant impact on the planning result: with a decrease in the complexity of calculations, the result deteriorates accordingly. Therefore, a greedy strategy is proposed as a solution method: from the optimization methods to be considered, select the least labor-intensive one that would allow obtaining the best result in the allotted time. Test runs of simulated annealing algorithms demonstrate different effectiveness under different initial conditions of the problem; therefore, it is advisable for selected classes of problems to choose algorithms that are effective in terms of solution quality and labor intensity.
Results. The result of the study is the structure of the ontology of effective algorithms. Also, the results are instances of simulated annealing algorithms and tasks included in the ontology, related by the “efficiency” relation.
Conclusion. This article proposes the structure of an ontology of effective optimization algorithms and an approach to solving the problem of distributing the computational load, taking into account the complexity of the distribution procedure through the “greedy” selection of the most effective optimization algorithms.
The authors declare that there are no conflicts of interest present.