ANALYSIS OF LANDSCAPE OF OPTIMIZABLE FUNCTIONS WHEN MAKING DECISIONS RELATED TO DATA MANAGEMENT

АНАЛИЗ ЛАНДШАФТА ОПТИМИЗИРУЕМЫХ ФУНКЦИЙ ПРИ ПРИНЯТИИ ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ РЕШЕНИЙ

Научная статья

Родзина О.Н.^1, *, Родзина Л.С.²

¹ ORCID: 0000-0002-8032-2362;

² ORCID: 0000-0002-4968-1922;

^{1, 2} Южный федеральный университет, Таганрог, Россия

* Корреспондирующий автор (srodzin[at]yandex.ru)

Аннотация

В статье сформулирован принцип поиска оптимальных информационно-управляющих решений метаэвристическими алгоритмами. Метаэвристика представляет собой итерационную процедуру, использующую рандомизацию и элементы самообучения, интенсификацию и диверсификацию поиска, адаптивные механизмы управления, конструктивные эвристики и методы локального поиска. Это перспективный подход к решению многих оптимизационных проблем. Предложена программа на псевдокоде, иллюстрирующая поиск решений метаэвристическими алгоритмами. Рассматривается общая модель ландшафта оптимизируемой функции. Определяется расстояние между решениями. Для анализа ландшафта применяются различные меры: изменение среднего расстояния между множеством однородно распределенных решений и множеством локальных оптимальных решений; энтропия; амплитуда; корреляция.

Ключевые слова: метаэвристический алгоритм, принятие решений, оптимизация, ландшафт, энтропия.

ANALYSIS OF LANDSCAPE OF OPTIMIZABLE FUNCTIONS WHEN MAKING DECISIONS RELATED TO DATA MANAGEMENT

Research article

Rodzina O.N.^1, *, Rodzina L.S.²

¹ ORCID: 0000-0002-8032-2362;

² ORCID: 0000-0002-4968-1922;

^{1, 2} South Federal University, Taganrog, Russia

* Corresponding author (srodzin[at]yandex.ru)

Abstract

The article states the principle of searching for the most efficient data management solutions by metaheuristic algorithms. Metaheuristics is an iterative procedure that uses randomization and self-learning elements, intensification and diversification of searches, adaptive control mechanisms, constructive heuristics,, and local search methods. It is a very promising approach to solving many optimization problems. A pseudo-code program that illustrates the search for solutions by metaheuristic algorithms is proposed. General landscape model of the optimized function is considered. The distance between the solutions is determined. Various measures are used to analyze the landscape: Changing the average distance between the set of uniformly distributed solutions and the set of locally optimal solutions; entropy; amplitude; correlation.

Keywords: metaheuristic algorithm, decision making, optimization, landscape, entropy. 

Введение

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

В настоящее время, значительное число разработанных и применяемых на практике метаэвристик принадлежат к недетерминированным алгоритмам [2], [3]. Это обусловлено их более высокими показателями эффективности. К тому же, постановки оптимизационных задач зачастую содержат данные, которые имеют определенные погрешности, что окончательно делает значительные вычислительные затраты для нахождения точного решения неоправданными.

В статье с единых позиций представлен анализ ландшафта оптимизируемых функций при принятии информационно-управляющих решений.

Принцип поиска решений метаэвристическими алгоритмами

Метаэвристика представляет собой итерационную процедуру, использующую рандомизацию и элементы самообучения, интенсификацию и диверсификацию поиска, адаптивные механизмы управления, конструктивные эвристики и методы локального поиска. Идея метаэвристических алгоритмов основана на предположении, что целевая функция решаемой задачи имеет много локальных экстремумов, а просмотр всех допустимых решений невозможен, несмотря на конечность их числа. В такой ситуации нужно сосредоточить поиск в наиболее перспективных частях допустимой области. Таким образом, задача сводится к выявлению таких областей и быстрому их просмотру. Каждая из метаэвристик решает эту проблему по-своему [4].

Алгоритм состоит в многократном применении процедуры поиска альтернативных решений в некоторой окрестности и замены текущего решения на альтернативное решение. Для создания альтернативных решений используется текущее решение s. Множество альтернативных решений C(s), как правило, получают путем локальных преобразований решения s. На этапе замены текущего решения s новым решением s^ выбор осуществляется из множества альтернативных решений C(s). Этот итерационный процесс повторяется многократно до выполнения заданного критерия остановки.

Ниже приводится программа на псевдокоде, иллюстрирующая поиск решений метаэвристическими алгоритмами.

Input: Инициализация начального решения s₀.

t:=0;

Repeat

Создание альтернативных решений C(s_t) путем применения определенных операторов в некоторой окрестности решения s_t;

Замена решения s_t на лучшее решение s_t+1 из множества C(s_t);

t:=t+1;

Until Проверка условия останова;

Output: Найдено лучшее решение.

Анализ ландшафта оптимизируемых функций

Определим пространство поиска решений через ориентированный граф G = (S, E), где множество вершин S соответствует множеству кодируемых решений задачи, а множество ребер E соответствует множеству операторов перемещения, используемых для генерации новых решений. Вершины s_i и s_j являются соседними и связаны ребром, если решение s_j может быть получено из решения s_i с использованием оператора перемещения.

Ландшафт L функции оптимизации определяется как кортеж (G, f), где граф G представляет собой пространство поиска, а f – оптимизируемую функцию [5]. Двух или трехмерный ландшафт можно представить с использованием географических терминов (пики, овраги, плато и др.), а метаэвристический алгоритм – как траекторию поиска, например, пика [6].

Предлагается более общая NK-модель ландшафта. Она классифицирует функции пригодности ландшафтов в зависимости от двух параметров N и K. Параметр N определяет размерность задачи, а параметр K – степень влияния переменных на оптимизируемую функцию пригодности.

Для анализа ландшафта оптимизируемой функции введем понятие расстояния в графе G, представляющего пространство поиска [8]. Это позволит определять пространственную структуру ландшафта и может оказаться полезным для разработки поисковых механизмов, таких как диверсификация и интенсификации процедуры поиска оптимума. Определим расстояние d(s_i, s_j) между решениями s_i и s_j на графе G как длину самого короткого пути, т.е. минимальное количество применений оператора перемещения для перехода из s_i в s_j. Расстояние должно обладать следующими свойствами [9]:

• d(x, y) = 0, если и только если x = y;
• d(x, y) = d(y, x);
• d(x, y) + d(y, z) >= d(x, z).

Отметим, что для некоторых задач оптимизации вычисление расстояния между решениями может оказаться NP-полной проблемой или же иметь оценку сложности высокого полиномиального порядка [10], [11], [12]. Ландшафт характеризуется различными свойствами: числом локальных оптимумов, их распределением, неровностью, дисперсией и др. Большинство из этих свойств основаны на статистике и являются глобальными или локальными характеристиками ландшафта.

Глобальные характеристики дают информацию о структуре ландшафта в целом, используя все пространство поиска. Однако целью оптимизации является поиск «хороших» решений, которые, обычно, представляют собой малую часть пространства поиска. Поэтому глобальных характеристик для исследования ландшафта недостаточно.

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

Для множества полученных метаэвристических решений Р определим среднее расстояние dmm(Р) и нормированное среднее расстояние Dmm(Р):

Здесь diam (S) – диаметр множества решений S, равный максимальному расстоянию между решениями.

Нормированное среднее расстояние характеризует концентрацию множества решений Р в пространстве поиска. Небольшое расстояние указывает на то, что решения группируются в малой области пространства поиска. Величина D_Dmm = (Dmm(U) – Dmm(O))/Dmm(U) представляет собой изменение среднего расстояния между множеством однородно распределенных решений U и множеством локальных оптимальных решений. При этом мощность множества O в зависимости от сложности метаэвристического алгоритма выбирается на интервале 10³ £ O £ 10⁴ .

Энтропия позволяет измерять разнообразие множества решений в пространстве поиска [13]. Величина D_ent = ent(U) – ent(O)/ent(U) представляет изменение энтропии между начальными решениями U и конечным множеством локальных оптимумов O, полученных после выполнения метаэвристического алгоритма. Энтропия дает информацию о разбросе, а не о зернистости решений. Хотя решения, сконцентрированные в нескольких областях, и решения, сконцентрированные в одной области, могут иметь одинаковую небольшую энтропию [14].

Для анализа распределения решений в пространстве функции f может использоваться амплитуда. Амплитуда – это величина относительной разности между лучшим и худшим значением функции f в некотором множестве решений P:

Относительное изменение амплитуды D_Amp определяется соотношением между начальными решениями U и конечным множеством локальных оптимальных решений O по формуле:

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

где l(р) – длина пути до пика оптимизируемой функции, начиная с некоторого решения р ∈ P. Величина Lmm(P) дает некоторую информацию о гладкости ландшафта. При гладком ландшафте количество локальных оптимумов небольшое и длина пути по склону до оптимума больше, нежели при большом количестве пиков.

С другой стороны, целевые функции некоторых задач оптимизации характеризуются наличием обширного плато, преодолеть которое метаэвристический алгоритм подчас не в состоянии. Пусть имеется решение s в пространстве поиска S, v - некоторое значение критерия f. Обозначим через N(s), подмножество точек s' в окрестности решения s. Пусть X является подмножеством N(s), которое состоит из решений s''∈X таких, что f (s'') = v. X представляет собой плато, тогда и только тогда, когда |X| ≥ 2. Если ландшафт функции включает несколько плато, то целевой функции оптимизации f недостаточно, чтобы различить подмножества N(s) окрестностей текущей точки s. Чтобы отделить одно плато от другого необходимо использовать дополнительную информацию. Либо изменить целевую функцию.

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

Заключение

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

Финансирование Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 19-01-00412-а.	Funding The study was carried out with the financial support of the Russian Federal Property Fund in the framework of scientific project No. 19-01-00412-a.
Конфликт интересов Не указан.	Conflict of Interest None declared.

Список литературы / References

1. Bischl B. Algorithm Selection Based on Exploratory Landscape Analysis and Cost-Sensitive Learning / B. Bischl, O. Mersmann, H. Trautmann, M. Preuss // Proc. of the 14^th Annual Conf. on Genetic and Evolutionary Computation (GECCO). – 2012. – P. 313 –
2. Rodzin S.I. Effectiveness evaluation of memetic and biogeography algorithms using benchmark and trans computational tasks of combinatorial optimization / S.I. Rodzin, O.N. Rodzina // Proc. of the First Int. Scientific Conf. “Intelligent Information Technologies for Industry” (IITI'16). – 2016. vol. 1. Advances in Intelligent Systems and Computing 450. – P. 463–475.
3. Rodzin S. Smart Dispatching and Metaheuristic Swarm Flow Algorithm / Rodzin // Computer and Systems Sciences Intern. – 2014. – N. 1. – P. 109–115.
4. Hanster C. Exploratory Landscape Analysis for Everyone / C. Hanster, P. Kerschke // Proc. of the 19^th Annual Conf. on Genetic and Evolutionary Computation (GECCO). – 2017. – Companion. ACM. doi:10.1145/3067695.3082477.
5. Kerschke P. Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems [Electronic resource] / P. Kerschke // R-package version 1.7. – 2017. URL https://github.com/kerschke/ flacco. (accessed: 23.07.2019)
6. Kerschke P. Cell Mapping Techniques for Exploratory Landscape Analysis / P. Kerschke, M. Preuss, C. Hern´andez, O. Schutze, J.Q. Sun, C. Grimme, G. Rudolph, B. Bischl, H. Trautmann // EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation. – 2014. – P. 115 –
7. Malan K.M. Quantifying Ruggedness of Continuous Landscapes using Entropy / K.M. Malan, A.P. Engelbrecht // Proc. of the IEEE Congress on Evolutionary Computation (CEC). – 2009. – P. 1440 –
8. Rodzin S. New computational models for big data and optimization / S. Rodzin, O. Rodzina // Proc. of the 9^th Conf. on Application of Information and Communication Technologies (AICT’2015). – 2015. – P. 3–7.
9. Bozhenyuk A. Hybrid Ant Fuzzy Algorithm for MRI Images Segmentation / A. Bozhenyuk, El-Khatib, Ja. Kacprzyk, M. Knyazeva, S. Rodzin // Lecture Notes in Computer Science. – 2019. – vol. 11509. P. 127–137.
10. Mersmann O. Exploratory Landscape Analysis / O. Mersmann, B. Bischl, H. Trautmann, M. Preuss, C. Weihs, G. Rudolph // Proc. of the 13^th Annual Conf. on Genetic and Evolutionary Computation (GECCO). – 2011. – P. 829 – 836.
11. Muller C.L. Global Characterization of the CEC 2005 Fitness Landscapes using Fitness-Distance Analysis / C.L. Muller, I.F. Sbalzarini // Applications of Evolutionary Computation. – – P. 294 – 303. doi:10.1007/978-3-642-20525-5_ 30.
12. Munoz M.A. Exploratory Landscape Analysis of Continuous Space Optimization Problems using Information Content / M.A. Munoz, M. Kirley, S.K. Halgamuge // IEEE Trans. on Evolutionary Computation. – – P. 74 – 87. doi:10.1109/TEVC.2014. 2302006.
13. Rodzin S.I. Metaheuristics memes and biogeography for trans computational combinatorial optimization problems / S.I. Rodzin, O.N. Rodzina // Proc. of the 6^th IEEE Int. Conf. on Cloud System and Big Data Engineering (Confluence'2016). AI and Soft Computing. – 2016. – P. 1–5.
14. Shirakawa S. Bag of Local Landscape Features for Fitness Landscape Analysis / S. Shirakawa, T. Nagao // Soft Computing. – 2016. – N. 20(10). – 3787 – 3802.