Разработка подхода, оперирующего с треугольным представлением нечетких чисел, на основе PSO-алгоритма

Размещено на http://www.allbest.ru/

Разработка подхода, оперирующего с треугольным представлением нечетких чисел, на основе PSO-алгоритма

Чернышев Юрий Олегович

доктор технических наук профессор, Донской государственный технический университет 344000, Россия, Ростовская область, г. Ростов-на-Дону, площадь Гагарина, 1

Венцов Николай Николаевич

кандидат технических наук доцент, Донской государственный технический университет 344000, Россия, Ростовская область, г. Ростов-на-Дону, площадь Гагарина, 1

Долматов Андрей Анатольевич

старший помощник капитана, ООО "СКФ Менеджмент Сервисиз" 353900, Россия, Краснодарский край, г. Новороссийск, ул. Свободы, 1 

Аннотация

Предметом исследования являются интеллектуальные алгоритмы решения оптимизационных задач. Известно, что для одних и тех же проектных процедур в одних случаях необходимо получать точные решения, а в других достаточно получения приближенных решений. По этой причине актуальной является проблема управления точностью получаемых приближенных решений. Под приближенным решением можно понимать некоторую область точек, каждая из которых может быть в некоторой степени решением задачи. Предполагается, что на начальных этапах решения оптимизационной задачи допустимо оперировать нечеткими значениями, постепенно сужая область поиска. Предлагается подход который дополняет известный алгоритм «оптимизации с использованием роя частиц» возможностью обработки нечетких чисел с треугольным представлением. Современные многоагентные методы адаптивного поиска решений задач оптимизации, развиваются в направлении совершенствования способов взаимодействия между агентами. Например, известный метод «оптимизации с использованием роя частиц» (Particle Swarm Optimization, PSO) базируется на понятии популяции и моделирует поведение птиц в стае и косяков рыб. При этом классические биоинспирированные методы поиска решений оперируют, как правило, с четкими решениями. Разработана модификация PSO- алгоритма, за счет выполнения известных операций над нечеткими числами с треугольным представлением. Отличительной чертой предлагаемого подхода является организация интеллектуального процесса поиска в нечетком пространстве решений, оригинальность которого заключается в разработке способа движения интеллектуального агента (группы агентов) в пространстве образованном треугольным представлением нечетких чисел. Данный подход позволяет осуществлять поиск решений в нечетких пространствах, оперируя переменными вида «близко к X » не прибегая к лингвистическому анализу.

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

приближенный решение треугольный нечеткий

Chernyshev Yurii Olegovich

Doctor of Technical Science

Professor, Department of Automation of Production Processes, Don State Technical University

344000, Russia, Rostovskaya oblast', g. Rostov-na-Donu, ploshchad' Gagarina, 1

myvnn@list.ru

Ventsov Nikolai Nikolaevich

PhD in Technical Science

Associate Professor, Department of Information Technology, Don State Technical University

344000, Russia, Rostovskaya oblast', g. Rostov-na-Donu, ploshchad' Gagarina, 1

vencov@list.ru

Dolmatov Andrey Anatolevich

Senior Captain Assistant , LLC "SKF Management Services"

353900, Russia, Krasnodarskii krai, g. Novorossiisk, ul. Svobody, 1

daa50@mail.ru

Abstract

The object of studies involves intellectual algorithm for solving optimization problems. It is known that for the same type of project procedures some cases require exact solutions, while others allow for approximate solutions. For this reason the issue of managing the exactness of the approximate solutions is so topical. An approximate solution may be regarded as some sphere of dots, each of them being a possible problem solution. It is supposed that at the early stages of solving optimization problems, it is possible to operate fuzzy ranges, while gradually narrowing the search area. The authors offer an approach, which complements the well-known algorithm of particle swarm optimization with the possibility to process fuzzy numbers with the triangular expression. The current multi-agent methods for the adaptive search for the optimization solutions are developed towards improvement of the interaction among the agents. For example, the well-known particle swarm optimization methods (PSO) is based upon the idea of population and it models the behavior of the birds in a flock or fish in a shoal. At the same time classic bio-inspired methods for finding solutions usually operate with clear solutions. The authors have developed the modification of the PSO algorithm thanks to performance of a number of known operations with the fuzzy numbers involving triangular expressions. The special feature of this approach is organization of the intellectual searching process in a fuzzy solution space. Its originality is due to the development of the method for the movement of an agent (group of agents) within the area formed with the triangular expression of fuzzy numbers. This approach allows for searching for solutions in fuzzy spaces, operating with the variables of the "close to X" type, avoiding the linguistic analysis.

Keywords:

optimization, vague estimates, swarm optimization method, search area, fuzzy operations, evolutionary method, swarm optimization methods, fuzzy multitudes, adaptation, evolution method

Современные многоагентные методы адаптивного поиска решений задач оптимизации развиваются в направлении совершенствования способов взаимодействия между агентами [1-3]. Например, в [3] предложена модификация алгоритма искусственной пчелиной колонии (Artificial Bee Colony) для решения задач оптимизации. В ней усилены составляющие, отвечающие за анализ области поиска и выход из локальных оптимумов. Одной из составляющих алгоритма явлется использование поиска на основе золотого сечения (Golden Section Search strategy). Критерием завершения работы алгоритма является получение решения, удовлетворяющего заданным условиям, или выполнение заданного числа итераций.

Известно, что для одних и тех же проектных процедур в одних случаях необходимо получать точные решения, а в других достаточно получения приближенных решений [4]. Под приближенным решением можно понимать некоторую область точек, каждая из которых может быть решением задачи. Например, условие «масса проектируемого изделия должна быть около 320 грамм» подразумевает, что нечеткими могут быть требования, связанные с массой составляющих изделие деталей. В подобных ситуациях актуальной становится проблема поиска решений в нечетких пространствах. Классические биоинспирированные методы поиска решений оперируют, как правило, с четкими решениями. Например, известный метод «оптимизации с использованием роя частиц» (Particle Swarm Optimization, PSO) базируется на понятии популяции и моделирует поведение птиц в стае и косяков рыб [5-8]. Стратегия поведения особей (частиц) в популяции (рое) состоит в стремлении превзойти достижения соседних частиц и улучшить собственные. Перемещения частиц внутри области поиска, обуславливаются их природным стремлением конкурировать между собой. Выбор траектории движения осуществляются частицей на основе личного опыта, а также опыта её соседей.

Классический метод роя базируется на представлении процесса поиска решения N-мерной оптимизационной задачи, как движения частицы (группы частиц) в N-мерном пространстве, координаты которой можно описать вектором (кортежем) X=<x1, x2,…, x,j,…, xN> [8]. Значение каждого элемента кортежа определяет четкое решение в соответствующей размерности пространства. С помощью кортежа Xi(t)=<xi,1(t), xi,2(t), …, xi,j(t), …, xi,N(t)> можно обозначить позицию i-ой частицы в пространстве поиска решений в момент времени t. Целью алгоритма является определение кортежа Xi(t), для которого:

(1)

Процесс поиска решений данным подходом начинается с генерации частиц. Начальное состояние частицы i в нулевой момент времени описывается кортежем Xi(0)=<xi,1(0), xi,2(0),…, xi,j(0),…, xi,N(0)>.

Позиция i-ой частицы в пространстве поиска решений изменяется добавлением скорости Vi(t)=<vi,1(t), vi,2(t),…, vi,N(t)> к текущей позиции:

Xi(t + 1) = Xi(t) + Vi(t + 1). (2)

В разновидности gbest PSO-метода каждая частица тяготеет к лучшему решению целого роя, поэтому скорость i-ой частицы в j-ом измерении определяется по формуле:

vi,j(t+1) = vi,j(t)+c1r1,j(t)[yi,j(t)-xi,j(t)] +c2r2,j(t)[y*j(t)-xi,j(t)], (3)

где: vi,j(t)- скорость i-ой частицы в j-ом измерении в момент времени t; xij(t) - координаты частицы i в измерении j; c1 и c2 - положительные константы ускорения, варьирующие когнитивную и социальную компоненты скорости частицы; r1j и r2j - случайные переменные, принимающие значения 0 или 1; yi,j(t)- координата наилучшей достигнутой позиции частицы i в j-ом измерении; y*j(t)- координата наилучшей достигнутой позиции роя в j-ом измерении.

Предлагаемый подход

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

В случае, если область определения носит нечеткий характер, процедура функционирования алгоритма должна быть модифицирована, например, за счет выполнения известных операций над нечеткими числами с треугольным представлением. При использовании треугольного представления каждое исходное нечеткое число, а также результат операции над ними описываются тремя скалярными значениями, что существенно упрощает вычислительный процесс [9].

Нечеткое число (близко к А) может быть выражено как [9]:

(4)

где - степень принадлежности множеству ; - объединение по всем ; означает, что степень принадлежности x множеству равна .

Функция принадлежности к нечеткому числу имеет две границы: верхнюю и нижнюю, поэтому нормальное выпуклое нечеткое число можно записать в виде [9]:

(5)

где a, b -нижняя и верхняя границы функции принадлежности, функция принадлежности на участке [a;A], - функция принадлежности на участке [A;b].

С учетом формулы (5) позицию i-ой частицы в нечетком пространстве поиска решений в момент времени t обозначим как кортеж нечетких чисел, представленных в треугольной форме:

(6)

где -часть нечеткого решения , соответствующая положению i-ой частицы на j-ой оси пространства поиска в момент времени t.

В свою очередь:

где - нижняя граница нечеткого числа, описывающего положение i-ой частицы на j-ой оси пространства поиска; - точка в которой значение функции принадлежности нечеткого числа, описывающего положение i-ой частицы на j-ой оси пространства поиска равно единице; - верхняя граница нечеткого числа, описывающего положение i-ой частицы на j-ой оси пространства поиска.

По аналогии с формулой (6) позиция i-ой частицы в пространстве поиска решений будет изменяться добавлением к текущей позиции скорости:

(7)

где - скорость которая должна быть добавлена к частице ; - скорость описывающая изменение направления в котором должна двигаться i-ая частица вдоль j-ой оси области поиска.

Нечеткое число также можно описать кортежем:

где - нижняя граница нечеткого числа, описывающего изменение положения i-ой частицы на j-ой оси пространства поиска; - точка в которой значение функции принадлежности нечеткого числа, описывающего изменение положения i-ой частицы на j-ой оси пространства поиска равно единице; - верхняя граница нечеткого числа, описывающего изменение положения i-ой частицы на j-ой оси пространства поиска.

В соответствии с формулами (6) и (7) формула (2) примет вид:

Сложение двух нечетких чисел определяется как [9]:

где a,b,a?,b? - границы слагаемых нечетких чисел.

Значения C, a??,b??, характеризующие нечеткое число , определяются равенствами С=A+B, a??= a+ a?; b??=b+ b?. Тогда [9]:

Так как С определяется суммой A и B, нечеткое число, полученное в результате арифметической операции, можно определить не проводя лингвистического анализа в силу того, что известно при каком значении x функция принадлежности равна единице.

Если декодер определен как нечеткое число с треугольным представлением, а da и db соответственно нижняя и верхняя границы функции принадлежности, а D точка, в которой значение функции принадлежности равно единице, тогда реализацией метода отрицательного отбора (одной из «граней» иммунного метода) [10-11] является сопоставление чисел и . В качестве степени близости можно использовать удаленность C, a??,b?? от D, da и db.

Заключение

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

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

Библиография

1. J. Jordan, S. Helwig, R. Wanka. Social interaction in particle swarm optimization, the ranked FIPS, and adaptive multi-swarms. // Proceedings of the 10th annual conference on Genetic and evolutionary computation.-Atlanta, USA, ACM, 2008, pp. 49-56.

2. W. Elshamy, H. M. Emara, A. Bahgat. Clubs-based Particle Swarm Optimization // Swarm Intelligence Symposium.-2007, pp. 289 - 296.

3. Sandeep Kumar, Pawan Bhambu, Vivek Kumar Sharma Sandeep. New Local Search Strategy in Artificial Bee Colony Algorithm // International Journal of Computer Science and Information Technologies, Vol. 5 (2), 2014, pp. 2559-2565.

4. Литвиненко В.А. Адаптивные алгоритмы проектных операций САПР ЭВА // IS-IT14: тр. Междунар. конгр. по интеллект. системам и информ. технологиям, п. Дивноморское, 2-9 сент./ ЮФУ. М.: Физматлит, 2014. Т.1, С. 113-119.

5. Eberhart R., Kennedy J. A New Optimizer using Particle Swarm Theory // In Proceedings of the Sixth International Symposium on Micro machine and Human Science 1995 - P. 39-43

6. Engelbrecht A. Computational intelligence: an introduction - John Wiley and Sons Ltd., 2007 - 597p.

7. Abraham A., Grosan G. Swarm Intelligence in Data Mining -Springer, 2006 - 267p.

8. Венцов Н.Н. Эволюционный подход к моделированию распределительных процессов. Инженерный вестник Дона [Электронный ресурс]: электрон. науч.-инновац. журн. -2013.-Режим доступа: http://www.ivdon.ru/magazine/archive/n4y2013/1886. -Загл. с экрана.

9. Борисов А.Н., Крумберг О.А., Федоров И.П. Принятие решений на основе нечетких моделей: Примеры использования. - Рига: Зинатне, 1990.- 184 с.

10. Искусственные иммунные системы и их применение/Под ред. Д. Дасгупты: Пер. с англ. Под ред. А.А. Романюхи.-М.: Физматлит, 2006.-344 с.

11. Чернышев Ю.О., Григорьев Г.В., Венцов Н.Н. Искусственные иммунные системы: обзор и современное состояние//Программные продукты и системы. 2014. № 108. С. 136-142.

Размещено на Allbest.ru