ПРИМЕНЕНИЕ БИОИНСПИРИРОВАННЫХ МЕТОДОВ ДЛЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

ПРИМЕНЕНИЕ БИОИНСПИРИРОВАННЫХ МЕТОДОВ ДЛЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

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

Родзин С.И. *

ORCID: 0000-0002-8998-2826,

Южный федеральный университет; Таганрог, Россия

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

Аннотация

В статье представлен общий подход к применению биоинспирированных методов для задач многокритериальной оптимизации с целью поддержки ЛПР при поиске Парето-оптимальных решений в соответствии с его предпочтениями. Предложен подход, предусматривающий определение «функции приспособленности» отдельных решений для аппроксимации множества Парето, сохранение разнообразия множества Парето решений, сохранение и использование элитных решений. Комбинируя биоэвристики с методами математического программирования, машинного обучения и интеллектуального анализа данных, получены решения для многокритериальных задач в таких областях как инженерное проектирование и биоинформатика, экономика и финансы, логистика, транспорт и телекоммуникации. Предложена грамматика для перспективных схем гибридизации, а также варианты гибридизации биоэвристик с методами машинного обучения, интеллектуального анализа данных.

Ключевые слова: биоинспирированные методы, многокритериальная оптимизация, множество Парето, грамматика.

APPLICATION OF BIOINSPIRED METHODS FOR THE TASKS OF MULTI-CRITERIA OPTIMIZATION

Research article

Rodzin S.I. *

ORCID: 0000-0002-8998-2826,

Southern Federal University; Taganrog, Russia

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

Abstract

The article presents general approach to the use of bio-inspired methods for problems of multi-criteria optimization with the aim of supporting the decision-maker when searching for Pareto-optimal solutions in accordance with the preferences. An approach involving the determination of the “fitness function” of individual solutions for approximating the Pareto set is proposed keeping the diversity of the Pareto set of solutions, while preserving and using elite solutions. Combining bio-heuristics with methods of mathematical programming, machine learning and data mining, solutions are obtained for multi-criteria problems in such areas as engineering design and bioinformatics, economics and finance, logistics, transport and telecommunications. Grammar for promising hybridization schemes is proposed, as well as bio-heuristic hybridization options with machine learning and data mining methods.

Keywords: bio-inspired methods, multi-criteria optimization, Pareto set, grammar.

Введение

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

Целью работы является проектирование и применение гибридных биоинспирированных методов для решения трудных задач многокритериальной оптимизации.

Постановка задачи многокритериальной оптимизации

Задачи оптимизации в таких областях как инженерное проектирование и биоинформатика, экономика и финансы, логистика, транспорт и телекоммуникации редко бывают однокритериальными [2], [3], [4]. Трудность в решении многокритериальных задач заключается в том, что окончательный выбор зависит от лица, принимающего решения; число Парето-решений увеличивается в зависимости от числа критериев едва ли не экспоненциально [5], [6], [7].

Задача многокритериальной оптимизации (МКО) заключается в минимизации вектора решений F(x) = (f₁(x), f₂(x),…, f_n(x)), где x = (x₁, ..., x_k) – вектор, представляющий переменные решения, связанные ограничениями, x∈S – пространство допустимых решений, n (n ≥ 2) – количество критериев. Множество Y = F(S) представляет точки y_i = f_i (x)  в пространстве критериев. Обычно не существует решения x* такого, что х* является оптимальным для всех критериев, т.е. ∀x ∈ S, f_i(x*) ≤f_i(x), i = 1..n [8].

Для задачи многокритериальной оптимизации (F, S) набор Парето оптимальных решений образует множество Парето: P* = {x ∈ S / ∄x'∈ S, F(x') ≺ F (x)} [9]. Множество Парето оптимальных решений образуют фронт Парето: PF* = {F(x), x ∈ P*} [10]. Построение фронта PF* или его аппроксимация является одной из основных целей МКО.

Гибридизация биоинспирированных методов для задач МКО

Комбинируя биоинспирированные методы (биоэвристики) с методами математического программирования, машинного обучения и интеллектуального анализа данных, могут быть получены лучшие решения для многих задач МКО.

Предлагается следующая грамматика для схем гибридизации:

<гибридная биоэвристика> → <проектирование> <реализация>

<проектирование> → <иерархическое> <прямое>

<иерархическое> → <МТМ> | <ММП> | <МПМ> | <ПММ>

<МТМ> → МТМ(<траекторная биоэвристика> (<биоэвристика>))

<МПМ> → МПМ(<популяционная биоэвристика> (<биоэвристика>))

<ММП> → ММП(<биоэвристика> + <биоэвристика>)

<ПММ> → ПММ(<биоэвристика>)

<ПММ> → ПММ(<биоэвристика>, <биоэвристика>)

<биоэвристика> → <траекторная биоэвристика>| <популяционная биоэвристика>

<траекторная биоэвристика> → локальный поиск| модель отжига| табуированный поиск| поиск в переменной окрестности| жадный локальный поиск| алгоритм демона | ...

<популяционная биоэвристика> → эволюционный алгоритм| алгоритм муравьиных колоний| алгоритм роя частиц| бактериальный алгоритм| |иммунный алгоритм| ...

<биоэвристика> → <гибридная биоэвристика>.

Здесь используются следующие обозначения: МТМ(A1(A2)) – метод A2 встраивается в траекторную биоэвристику A1; ММП(А1 + А2) – автономные биоэвристики А1 и А2 выполняются в определенной последовательности; МПМ(A1(A2)) – метод А2 встраивается в популяционную биоэвристику А1; ПММ(A1, A2) – автономные биоэвристики А1 и А2 выполняются параллельно и во взаимодействии.

Например, с помощью биоэвристики находится «хорошее» приближенное решение, которое затем используется в качестве начального для работы метода математического программирования [2]. Или с помощью популяционной биоэвристики находится окрестность для аппроксимации решений из множества Парето. В этом случае схема подобного рода подхода к гибридизации имеет следующий вид:

Input: PO – аппроксимируемое множество Парето решений

Do S' = PO

Генерация популяционной биоэвристикой окрестности PN_x для каждого решения x∈ S';

Устанавливаем множество недоминируемых решений PO из объединения S' PN_x;

Until PO = S' (популяции достигли локальных оптимумов);

Output: Парето множество PO.

Предлагаются следующие схемы гибридизации биоэвристик и методов машинного обучения, интеллектуального анализа данных:

• использование знаний, полученных в процессе поиска решений для динамической и адаптивной настройки параметров траекторных и популяционных биоэвристик. Например, любой параметр популяционной биоэвристики (вероятность мутации, кроссинговера в эволюционных алгоритмах, обновления феромона в муравьиных алгоритмах, обновление скорости роя частиц и др.) может динамически изменяться, благодаря знаниям, извлеченным во время поиска, чем более эффективным с точки зрения качества и разнообразия получаемых решений является оператор, тем более существенным является вероятность его применения;
• использование интеллектуального анализа данных и знаний (ассоциативные правила, классификация, деревья решений), полученных в ходе поиска решений, в операторах рекомбинации популяционных биоэвристик, для генерации новых решений, активизации и диверсификации поиска;
• использование алгоритмов кластеризации и классификации для упрощения и аппроксимации целевых функций в процессе оценки решений;
• использование декомпозиции на подзадачи путем динамического разбиения области решения на подобласти, а самой задачи – на подзадачи, а также выбор подходящей биоэвристики для каждой из этих подзадач. Например, в биогеографическом алгоритме [10] поисковой оптимизации учитывается опыт, приобретаемый в ходе решения задачи;
• использование гибридной схемы, в которой динамически знания, полученные агентом интеллектуального анализа данных, применяются в процессе метаэвристического поиска в режиме онлайн обучения. Примером является меметический алгоритм [10], в котором мем (аналог гена, единица культурной информации) является реализацией какого-либо алгоритма локальной оптимизации, уточняющего текущие решения на каждой итерации, либо через некоторое число итераций. Основной задачей конструирования таких гибридных алгоритмов является задача выбора целесообразной стратегии использования того или иного мема из роя доступных мемов.

Заключение

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

Финансирование Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 19-07-00570-а.	Funding The reported study was funded by RFBR according to the research project №19-07-00570-а
Конфликт интересов Не указан.	Conflict of Interest None declared.

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

1. Родзин С.И. Состояние, проблемы и перспективы развития биоэвристик / С.И. Родзин, В.В. Курейчик // Программные системы и вычислительные методы. – 2016. – № 2. – С. 158–172.
2. Deb K. Multi-objective test problems, linkages and evolutionary methodologies / K. Deb, A. Sinha, S.Kukkonen // Proc. of the ACM Conf. Genetic and Evolutionary Computation (GECCO’2006). – 2006. – P. 1141–1148.
3. Jourdan L. Hybridizing exact methods and metaheuristics: A taxonomy / L. Jourdan, M. Basseur, E.-G. Talbi // European Journal of Operational Research. – 2009. – N. 4. – P. 35–67.
4. Liefooghe A. Combinatorial optimization of stochastic multi-objective problems: An application to the flow-shop scheduling problem / A. Liefooghe, M. Basseur, L. Jourdan, E.-G. Talbi // Proc. Evolutionary Multi-Criterion Optimization (EMO’2007). – vol. 4403. – P. 457–471.
5. Farina M. Dynamic multi-objective optimization problems: Test cases, approximations, and applications / M. Farina, K. Deb, P. Amato // IEEE Transactions on Evolutionary Computation. – 2004. – N. 8(5). – Р. 425–442.
6. Wang R. Preference-inspired Co-evolutionary Algorithms for Many-objective Optimisation / R. Wang, R.C. Purshouse, P.J. Fleming // IEEE Trans. on Evolutionary Computation. – 2012. DOI: 10.1109/TEVC.2012.2204264.
7. Rodzin S. Smart Dispatching and Metaheuristic Swarm Flow Algorithm / S. Rodzin // Computer and Systems Sciences Intern. – 2014. – N. 1. – P. 109–115.
8. Pham D. T. Multi-objective optimization using the bees algorithm / D.T. Pham, A.Ghanbarzadeh // Proc. of the Conf. Innovative Production Machines and Systems (IPROMS’07). – 2007. – P. 217-229.
9. Xue F. Multi-objective differential evolution algorithm, convergence analysis, and applications / F. Xue, A.C. Sanderson, R.J. Graves // IEEE Congress on Evolutionary Computation (CEC’2007). – 2007. – P. 743–750.
10. Rodzin, S.I. Metaheuristics memes and biogeography for trans computational combinatorial optimization problems / S.I. Rodzin, O.N. Rodzina // Proc. of the 6th IEEE Int. Conf. on Cloud System and Big Data Engineering (Confluence'2016). AI and Soft Computing. – 2016. – P. 1–5.

Список литературы на английском языке / References in English

1. Rodzin S.I. Sostojanie, problemy i perspektivy razvitija biojevristik [Status, problems and prospects of bio heuristics development] / S.I. Rodzin, V.V. Kureychik // Programmnye sistemy i vychislitel'nye metody [Software systems and computational methods]. – 2016. – N. 2. – P. 158–172. [in Russian]
2. Deb K. Multi-objective test problems, linkages and evolutionary methodologies / K. Deb, A. Sinha, S.Kukkonen // Proc. of the ACM Conf. Genetic and Evolutionary Computation (GECCO’2006). – 2006. – P. 1141–1148.
3. Jourdan L. Hybridizing exact methods and metaheuristics: A taxonomy / L. Jourdan, M. Basseur, E.-G. Talbi // European Journal of Operational Research. – 2009. – N. 4. – P. 35–67.
4. Liefooghe A. Combinatorial optimization of stochastic multi-objective problems: An application to the flow-shop scheduling problem / A. Liefooghe, M. Basseur, L. Jourdan, E.-G. Talbi // Proc. Evolutionary Multi-Criterion Optimization (EMO’2007). – vol. 4403. – P. 457–471.
5. Farina M. Dynamic multi-objective optimization problems: Test cases, approximations, and applications / M. Farina, K. Deb, P. Amato // IEEE Transactions on Evolutionary Computation. – 2004. – N. 8(5). – Р. 425–442.
6. Wang R. Preference-inspired Co-evolutionary Algorithms for Many-objective Optimisation / R. Wang, R.C. Purshouse, P.J. Fleming // IEEE Trans. on Evolutionary Computation. – 2012. DOI: 10.1109/TEVC.2012.2204264.
7. Rodzin, S.I. Metaheuristics memes and biogeography for trans computational combinatorial optimization problems / S.I. Rodzin, O.N. Rodzina // Proc. of the 6th IEEE Int. Conf. on Cloud System and Big Data Engineering (Confluence'2016). AI and Soft Computing. – 2016. – P. 1–5.
8. Rodzin S. Smart Dispatching and Metaheuristic Swarm Flow Algorithm / S. Rodzin // Computer and Systems Sciences Intern. – 2014. – N. 1. – P. 109–115.
9. Xue F. Multi-objective differential evolution algorithm, convergence analysis, and applications / F. Xue, A.C. Sanderson, R.J. Graves // IEEE Congress on Evolutionary Computation (CEC’2007). – 2007. – P. 743–750.
10. Pham D. T. Multi-objective optimization using the bees algorithm / D.T. Pham, A.Ghanbarzadeh // Proc. of the Conf. Innovative Production Machines and Systems (IPROMS’07). – 2007. – P. 217-229.