Подход к глобальной оптимизации, основанный на формировании мнений в сложных сетях

Краткое изложение

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

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

Вступление

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

Стандартные эволюционные алгоритмы представляют собой методы стохастического поиска, использующие популяцию решений, к которым применяются множественные стохастические операторы для генерации новой популяции с лучшими решениями в соответствии с выводом функции затрат, представляющей задачу оптимизации [2]. Алгоритмы оптимизации на основе роя - это методы, основанные на использовании популяции, использующие взаимодействующие искусственные агенты, способные получать обратную связь друг от друга и работать совместно, обычно имитируют естественные механизмы [3]. С совокупностью объектов, каждый из которых соответствует возможному решению, эти методы выполняют рандомизированный поиск в пространстве возможных решений по мере взаимодействия объектов друг с другом. Нахождение оптимального решения не гарантируется при рандомизированном поиске, однако это облегчает выход из локальных минимумов и помогает процессу сходиться вблизи глобального минимума, если не самого глобального минимума. Кроме того, эти методы могут быть использованы для сохранения нескольких хороших решений проблемы, вместо того, чтобы возвращать только лучшие [4]. Существует ряд методов оптимизации, основанных на использовании популяции, широко применяемых к задачам невыпуклой оптимизации из-за их доказанной эффективности. Генетический алгоритм (GA) [5], [6], Дифференциальная эволюция (DE) [7], [8], Метод муравьиной колонии/муравьиный алгоритм (ACO) [9], [10], Метод роя частиц (PSO) [11], [12], Эволюционная стратегия адаптации ковариационной матрицы (CMA-ES) [13] и Метод искусственной пчелиной колонии (ABC) [14] относятся к числу этих эффективных методов.

Хорошо известные методы оптимизации, основанных на использовании популяции, часто имеют другие варианты, предлагаемые с целью либо устранения существующих недостатков в исходной версии, либо улучшения ее производительности; примеры включают улучшенный метод ABC [15], в котором используется механизм обучения, или улучшенный DE [16], который устраняет состояние застоя в исходном DE. Другим распространенным подходом к созданию мощных алгоритмов оптимизации является внедрение эффективных схем и стратегий в различные существующие методы или даже в другие области исследований путем гибридизации, например, интеграции стратегии локального поиска в рамках PSO [17] или использования операторов DE для улучшения сочетания исследовательских и эксплуатационных характеристик в исходном CMA-ES [18].

Благодаря заметным достижениям в области популяционной оптимизации эти методы нашли свое место в различных дисциплинах, как в академических кругах, так и в промышленности, из-за их многочисленного практического применения. Например, инструменты, разработанные на основе популяционной оптимизации, используются в приложениях прогнозирования временных рядов [19], например, для прогнозирования финансовых рынков [20]. Эти методы также находят заметное применение в энергетическом секторе; например, прогнозирование потребления [21], оптимизация затрат, проектирование и управление энергетическими системами [22]. Другие области применения включают разработку систем управления [23], информатику [24] и биологию [25]. Проблема оптимизации, связанная с этими областями, может быть по своей сути непрерывной или дискретной проблемой. В то время как многие методы оптимизации, основанные на использовании популяции, предназначены для решения одного конкретного типа, непрерывные задачи всегда можно сопоставить с дискретной задачей путем квантования непрерывной области ее независимых переменных.

В данном исследовании заимствуются инструменты и идеи из сложных сетей и дисциплин социальной динамики для разработки эффективного метода бинарной оптимизации, основанном на использовании популяции. Наука о сетях активно изучалась в течение последних двух десятилетий, и инструменты теории графов нашли применение в нескольких областях знаний [26]. Это связано с тем фактом, что многие системы реального мира могут быть смоделированы как сетевые структуры, в которых ряд отдельных блоков взаимодействуют через набор соединений [27], [28]. При выполнении определенных условий динамические агенты, взаимодействующие через сеть соединений, могут демонстрировать коллективное поведение, такое как синхронизация [29] и консенсус [30]. Широкий спектр исследований в сообществе сетевых наук посвящен исследованию динамики социальных сетей [31]. Общий подход в этих исследованиях заключается в рассмотрении индивидов как взаимодействующих агентов, связанных в соответствии со сложной сетевой структурой, представляющей социальные связи.

Формирование общественного мнения в социальных сетях является одним из хорошо изученных предметов в сетевых и социальных науках; изучение индивидуальной и коллективной динамики популяции агентов, каждый из которых обладает ценностью мнения, поскольку они влияют друг на друга, в результате чего мнения эволюционируют [32], [33], [34]. Для отражения динамики процесса формирования общественного мнения в социальных сетях были предложены различные модели. Примером может служить модель избирателя, согласно которой агенты имеют дискретные значения мнений, и один за другим случайно выбранные агенты обновляют свои мнения под влиянием одного из своих соседей [35]. В другой модели, известной как модель ограниченного доверия, два соседа влияют на мнение друг друга и интерпретируются как агенты, подлежащие обсуждению, если их первоначальные мнения ближе определенного порога [36]. В данном исследовании используется манипулируемая версия этой модели, которая также учитывает социальную власть агентов в процессе формирования мнения, то есть агентов, имеющих разные уровни влияния [32], [37].

Далее в разделе 2 представляется новый метод бинарной оптимизации, основанный на формировании мнений в сложных системах. Предлагается модель взаимодействия для расчета изменений во мнениях агентов под влиянием других агентов. Для создания основы бинарной оптимизации предлагаемый метод использует данную модель взаимодействия и другие идеи, изученные в рамках социальной динамики. В разделе 3 подробно представлены эксперименты, которые проводятся для изучения характеристик предлагаемого метода, а также для оценки его эффективности посредством сравнений. Проблема методов оптимизации заключается в степени их обобщаемости и их способности обеспечивать разумную производительность в задачах с различными параметрами [38], [39]. Таким образом, наши эксперименты проводятся на разнообразных испытательных стендах для тщательной оценки предлагаемого метода с объективной оценкой его обобщаемости. Наконец, в разделе 4 статья завершается кратким изложением этого исследования и обсуждением полученных результатов и возможных будущих направлений.

Глобальная оптимизация, основанная на формировании мнении в сложной сети

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

В данном разделе подробно описывается предлагаемый алгоритм оптимизации. Предлагаемая методика основана на феномене консенсуса мнений в социальных сетях и использует модель формирования мнений. Некоторые недавно разработанные методы используют дискретные или непрерывные модели формирования мнений для решения однотипных задач оптимизации [33], [40], однако наш метод использует непрерывную модель мнений для решения задач бинарной оптимизации, чтобы сохранить дополнительную информацию к решениям [41], [42]. Предлагаемый метод манипулирует набором возможных решений проблемы, представленных векторами мнений, которыми владеет совокупность из N объектов, называемых агентами. В то время как сетевая структура с узлами (агентами) определяет связи между популяцией. Обозначим вектор мнений для агента i какгде D - количество элементов в векторе мнений, равное размеру задачи оптимизации. Каждый вектор мнений соответствует бинарному решению-кандидату{0, 1} которое получено с использованием функции преобразования T(.), определенной как показано ниже:

В пределах вектора мнений знак каждого элемента определяет двоичное значение для соответствующего измерения вектора решения, а абсолютное значение элемента указывает степень, в которой, в этом значении решения, агент уверен. Абсолютное значение элемента в векторе мнений названо определенностью. В данном исследовании решается задача минимизации для задачи неограниченной бинарной оптимизации. Функция затрат {0, 1}отображает вектор двоичного решения размера D на вещественное неотрицательное значение стоимости, которое измеряет пригодность решения-кандидата. Чем ниже стоимость решения, тем выше его пригодность.

Обозначим множество окрестностей агента i через которое определяется базовой сетевой структурой с узлами, представляющими агентов, и ребрами, представляющими связи между ними. На каждой итерации t алгоритма оптимизации каждый агент i выбирает, в качестве своего собеседника, агента, обладающего наиболее подходящим решением-кандидатом среди всех агентов в набореТакой подход к выбору собеседника приводит к тому, что агенты влияют друг на друга под воздействием взаимной социальной власти [32], [37]; чем выше пригодность решения агента, тем выше вероятность выбора этого агента в качестве собеседника влияющего на других агентов. Когда собеседник выбирается для взаимодействующего агента i, собеседник воздействует на агента i, и в результате генерируется вектор пробного мнения Вектор пробного мнения рассчитывается на основе как текущего мнения взаимодействующего агента (целевой вектор), так и мнения собеседника в соответствии со следующей моделью взаимодействия:

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

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

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

Прежде чем новый вектор мнений будет готов для того, чтобы взаимодействующий агент мог использовать его для следующего поколения, процесс, называемый обновлением достоверности, изменяет значения определенности для некоторых элементов нового вектора мнений. Процесс обновления достоверности изменяет только абсолютные значения в векторе мнений и оставляет знаки неизменными, поэтому соответствующий вектор двоичного решения остается неизменным после этого процесса. Механизм обновления всегда увеличивает абсолютное значение измерения мнения и применяется только к подмножеству измерений (A), которое включает измерения, для которых знак переключается во время взаимодействия. На итерации t и для каждого агента i это подмножество измерений, обозначаемое как определяется:

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

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

На рис. 1 показан пример использования треугольного распределения вероятностей для процесса обновления достоверности; значение мнения в примере равно 0,6. После процесса обновления достоверности к этому значению мнения, новое значение мнения будет находиться в диапазоне [0.6, 1], с большей вероятностью будет меньше (ближе к старому значению).

Результатом процесса обновления достоверности является то, что изменение благоприятного значения в векторе решения будет сложнее на последующих итерациях, поскольку достоверность увеличивается в соответствующем измерении вектора мнений. Этот механизм интегрирует дополнительную информацию в значение мнения о том, как переключение знака (двоичное решение) влияет на стоимость. В предлагаемом методе запоминание предыдущих измерений моделируется путем изменения абсолютного значения (достоверности) элементов в векторе мнений. Не имея никаких предположений относительно оптимальных решений или процесса эволюции векторов мнений, поскольку исходные значения мнений получены из равномерного распределения в диапазоне [-1,1], следует ожидать, что взаимодействия снижают абсолютные значения в векторе мнений (значения мнений будут ближе к нулю). На каждой итерации t алгоритма, каждый агент i изменяет знаки различных элементов в своем векторе мнений. Для некоторых измерений вектора мнений, в котором определенный знак (двоичное значение) в решении считается выгодным в соответствии с функцией затрат, абсолютное значение мнения увеличивается. Это увеличит вероятность влияния полезного общего мнения. Предлагаемый метод оптимизации назван Бинарной оптимизацией на основе формирования общего мнения (GOFBO). Псевдокод метода GOFBO (см. рис. 2).

Наглядный пример

Чтобы проиллюстрировать, как работает предлагаемый алгоритм, приведен пример выполнения задачи оптимизации для 5-мерной двоичной задачи (см. рис. 3). В данном примере два агента обновляют свои векторы мнений посредством трех взаимодействий. Задача оптимизации определяется как минимизация непрерывной функции затрат при Каждый вектор двоичного решения, соответствующий мнению агента, является двоичным представлением непрерывного значения в диапазоне Для двоичного представления непрерывного диапазона значений с двоичным вектором длины равномерно распределенных точек в непрерывном диапазоне присваиваются последовательным значениям двоичного вектора. Здесь цель состоит в том, чтобы найти двоичное значение, максимально близкое к или для которого стоимость достигает оптимального значения при 0. В этом простом примере устанавливается частота мутаций равная нулю для более четкой демонстрации процесса обновления, однако на практике этот параметр принимает ненулевое значение.

Значения мнений показаны внутри кругов на рис. 3, причем белый (черный) круг указывает на значение равное единице (нулю) в соответствующем векторе решения. Стоимость каждого решения показана в правом нижнем углу прямоугольника, описывающего вектор мнений. Каждый подзаголовок на рис. 3 показывает одно взаимодействие, с начальным вектором мнений для обоих агентов, показанных слева. Агенты обновляют свои мнения на основе уравнения (2), и результатом взаимодействия является вектор пробного мнения, обозначенный сплошной черной стрелкой. На каждой итерации (рис. 3.a, 3.b и 3.c) только один из агентов меняет свое мнение под влиянием другого; нижний вектор мнения на левой панели соответствует взаимодействующему агенту, который обновляет свой вектор мнения, а верхний - собеседнику. Звездочки в результирующих векторах мнений (правая панель) указывают измерения, для которых знак изменился во время взаимодействия, таким образом, достоверность должна быть увеличена в соответствии с предлагаемым алгоритмом, в то время как знак этого элемента может быть сохранен из целевого вектора мнений или может быть взят из пробного вектора мнений.

На рис. 3.а находится под влиянием и обновляет свой вектор мнений. Это взаимодействие приводит к получению вектора пробного мнения внутри которого есть одно измерение с измененным знаком во время взаимодействия. Поскольку означает, что взаимодействие улучшило решение, пробный вектор принимается агентом в качестве своего мнения для следующей итерации. В этом случае для измерений с измененным знаком процесс обновления достоверности выполняется с использованием уравнения (5), и для тех измерений, знак которых остался неизменным, значения мнений для следующего шага всегда берутся из пробного вектора (см. уравнение (6)). Действительно, поскольку изменение знака в определенном измерении улучшает стоимость, следовательно, его абсолютное значение (достоверность) увеличивается, что также расширяет его влияние на других агентов и в то же время снижает вероятность изменения соответствующего бинарного решения другими. Наконец, обновленный вектор мнений для получается в конце первого шага.

На следующем шаге (рис. 3.б) влияет на У нас есть поскольку агент 2 не меняет своего мнения на предыдущем шаге, при этом временной шаг увеличивается. Обратите внимание, что в реальной реализации алгоритма на каждой итерации все агенты обновляют свой вектор мнений. Вектор пробного мнения в этом взаимодействии показывает ухудшенную пригодность решения и знаки изменены для двух измерений. Согласно предложенному алгоритму, агент сохраняет текущий знак в каждом измерении своего вектора мнений неизменным. Однако для тех элементов, у которых один и тот же знак как в текущем мнении агента, так и в векторе пробного мнения, агент берет значения пробного вектора. Действительно, в таких случаях агент считает изменение знака недостатком и не принимает его. В результате в измерениях с измененными знаками взаимодействующий агент берет значения из своего вектора целевого мнения и повышает достоверность, что в конечном итоге снижает вероятность изменения знака в этих измерениях при последующих взаимодействиях. В конце этого шага для агента 2 получается обновленный вектор мнений.

На рис. 3.c поскольку агент 1 был собеседником и не изменил свой вектор мнения на предыдущем шаге. На третьем шаге снова подвергается влиянию что приводит к оптимальному решению проблемы.

Экспериментальные результаты

Мы применяем предложенный метод к ряду широко используемых контрольных функций. Производительность предлагаемого метода также сравнивается с рядом известных алгоритмов оптимизации.

Было показано, что топология (структура соединений) играет важную роль в определении поведения динамических процессов, например, синхронизации и консенсуса, в сетях [43]. Поэтому здесь сначала изучается влияние структуры сети соединений на производительность предлагаемого метода.

Контрольные функции

Чтобы проверить эффективность методов, они применяются к ряду контрольных функций, которые часто используются в литературе [44], [45]. Сначала используется ряд функций (таблица 1) для определения оптимальной топологии сети для предлагаемого алгоритма. В таблице 1 символ относится к входному вектору, для которого количество элементов равно количеству переменных, указанных для функции, а i-й элемент во входном векторе обозначается как Затем алгоритмы сравниваются по 30-ти контрольным функциям, показанным в таблице 2. Эти функции представлены как набор одноцелевых тестов IEEE CEC 2017, определенных в разделе [45], где также можно найти более подробную информацию о каждой функции. Набор тестов состоит из 30-ти базовых, гибридных и композиционных функций, построенных на 20-ти базовых функциях. Каждая базовая функция представляет собой сдвинутую и повернутую функцию в форме где вектор сдвига выбирается случайным образом из Матрица вращения генерируется из стандартных нормально распределенных записей с помощью процесса ортогонализации Грама-Шмидта [46] и присваивается уникальным значениям каждой функции. Для каждой функции выбрано количество переменных случайным образом из набора {2, 20, 10, 50, 100}, в то время как граница поиска для каждой переменной равна [-100, 100].

В экспериментах все методы применяются к двоичному представлению каждой функции для выполнения задачи бинарной оптимизации. Для того, чтобы оценить производительность методов для относительно крупномасштабной двоичной оптимизации, размер двоичных задач, связанных с функциями, имеет 1000 измерений; 1000 бит двоичного вектора решения. В векторе решения для представления каждой переменной функции выделено несколько двоичных битов (измерений в векторе решения). Например, 500 бит в векторе двоичного решения предназначены для каждой переменной которая имеет две переменные (1000/2), а для с 50 переменными каждая непрерывная переменная представлена 20-битной строкой в двоичном решении (1000/50). Чтобы представить непрерывную переменную с n-разрядной строкой, диапазон действительных значений, определенный как область переменной, разбивается на равные интервалы. Затем слева направо от домена каждой точке интервала присваиваются последующие значения битовой строки; нижняя и верхняя границы переменной области сопоставляются двоичным векторам "все нули" и "все единицы" соответственно.

Анализ влияния графа соединений

Когда группа субъектов взаимодействует и обменивается информацией, коллективный результат сильно зависит от сетевой структуры, управляющей коммуникацией. В данном разделе изучается как различные структуры сети взаимодействия влияют на эффективность GOFBO при применении к задачам оптимизации. Базовая сеть взаимодействия определяет связи между агентами и определяет набор соседних агентов для взаимодействующего агента, среди которых он выбирает своего собеседника. Каждый агент предоставляет информацию о решении своему набору соседей, и, таким образом, сеть взаимодействия играет важную роль в определении того, как информация распространяется через агентов и как векторы мнений развиваются с течением времени. Чтобы исследовать роль базовой сети, применяется предложенный алгоритм, используя различные структуры в качестве сети взаимодействия, а именно структуры случайной, малой, безразмерной, кольцевой и квадратной сетки.

Согласно модели Эрдёша-Реньи
(ER) [47], чтобы генерировать случайные сети, выбирается M случайных уникальных
пар узлов из всех возможных и устанавливаем для них связи. Чтобы построить сеть
малого мира, используется модель Уоттса-Строгаца (WS) [48]. Начиная с
кольцевого графа со средней степенью каждое звено перестраивается независимо с вероятностью Безмасштабные сети строятся с использованием модели преимущественного присоединения [49], известной как модель Барабаши-Альберт (BA). Модель BA начинается с клика, и узлы добавляются в сеть в несколько этапов. Новый узел устанавливает ссылок на старые узлы с вероятностью, пропорциональной степени старого узла. Обратите внимание, что упомянутые здесь параметры, а именно являются входными параметрами для моделей генератора графиков. Квадратная сетка или граф с 2D-решеткой имеет набор узлов, соответствующих целочисленным координатам на выбранной прямоугольной области декартовой плоскости, причем каждый узел связан со всеми узлами с расстоянием равным 1. Количество узлов задается а средняя степень фиксируется на уровне 4 для всех сетей путем настройки параметров связанных моделей. Также рассматривается сеть динамического взаимодействия, в соответствии с которой на каждой итерации алгоритма оптимизации агенты устанавливают 4 ссылки на случайно выбранных агентов; назовем это изменяющейся во времени случайной структурой.

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

С точки зрения теории графов, для согласованного алгоритма, работающего над графом взаимодействия, алгебраическая связность является мерой скорости сходимости [50]. Алгебраическая связность - это второе наименьшее собственное значение матрицы Лапласа, полученное из матрицы смежности сети соединений. Матрица Лапласа L вычисляется из матрицы смежности A, как показано ниже:

где выводит диагональную матрицу с градусами узлов в диагональных элементах. Вычисляется алгебраическая связность для графов, используемых в качестве сетей взаимодействия. Для стохастических сетевых моделей рассматривается средняя алгебраическая связность 10000 сгенерированных выборок. Обратите внимание, что изменяющаяся во времени модель случайной сети выбирает 4 случайных агента в качестве соседнего набора для взаимодействующего агента на каждой итерации. Поскольку в этом подходе структура сети не является постоянной в ходе оптимизации, вместо этого предполагается, что алгебраическая связность случайно сгенерированных сетей со всеми узлами, имеющими степень, равную 4, является достаточно репрезентативной для этой схемы сети взаимодействия. Столбцы в таблице 3 отсортированы в соответствии со средней алгебраической связностью, рассчитанной для каждой топологии сети; отсортированы в порядке возрастания слева направо.

Чтобы выполнить анализ результатов, представленных в таблице 3, вычисляется коэффициент корреляции Пирсона между результатами производительности и средней алгебраической связностью, связанной со структурами сети. Значения корреляции и получены между средними значениями алгебраической связности и результатами, достигнутыми для тестовых функций соответственно. Применение t-критерия позволяет сделать вывод о том, что результаты оптимизации для любой из 6 тестовых функций и алгебраическая связность сетей взаимодействия имеют линейную зависимость на уровне значимости Также вычисляется коэффициент множественных корреляций, указывающий на предсказуемость зависимой переменной (здесь алгебраическая связность) из набора независимых переменных (здесь результаты оптимизации для набора тестов). Квадрат коэффициента множественной корреляции вычисляется с помощью:

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

Динамические сети взаимодействия

Две топологии с наивысшими показателями в предыдущем наборе экспериментов, а именно кольцевая и изменяющаяся во времени случайная, находятся на двух крайних точках диапазона алгебраической связности, рассчитанного для сетевых структур взаимодействия; кольцевая сеть имеет наименьшую алгебраическую связность, а изменяющаяся во времени случайная сеть имеет наибольшую. Этот факт наряду с тем фактом, что алгебраическая связность сети взаимодействия имеет значительную корреляцию с производительностью оптимизации, предполагает, что результат задачи оптимизации может быть улучшен путем увеличения или уменьшения алгебраической связности сети взаимодействия, в зависимости от характеристик присущих проблеме. Алгебраическая связность графа растет в результате увеличения плотности. Например, кольцевой граф со 100 узлами и имеет алгебраическую связность то время как при алгебраическая связность возрастает до Верхняя граница алгебраической связности (N-клика), которая является алгебраической связностью полного графа с N узлами, равна N. Здесь для выполнения задачи оптимизации предлагаются две динамические сети взаимодействия, для которых размер окрестности изменяется по мере прохождения алгоритмом оптимизации временных шагов последовательности. Проверим, произойдет ли изменение алгебраической связности сети взаимодействия при выполнении оптимизации эффективным для более широкого круга задач оптимизации с различными характеристиками. Чтобы проверить эффективность динамических сетевых структур, GOFBO инициализируется сетью взаимодействия, кольцевой или изменяющейся во времени случайной, имеющей начальный размер окрестности а  размер окрестности постепенно уменьшается до 2 по мере выполнения алгоритма. По истечении итераций размер набора окрестностей на итерации t вычисляется как:

где - максимальное количество итераций. В уравнении (9) умножение второго члена на 2 позволяет оставаться четным числом, так как в кольцевом графе наличие четного числа соседей необходимо для всех узлов. В экспериментах размер набора окрестностей для каждого взаимодействующего агента будет одинаковым между обеими сетями динамического взаимодействия на каждой конкретной итерации. На рис. 4 показан пример топологий сети динамического взаимодействия, для которых средняя степень уменьшается с течением итераций, в то время как обе топологии имеют одинаковую среднюю степень в одних и тех же точках (равные числа итераций) процесса. Настройка на простую контрольную задачу, известную как ONEMAX, для которой стоимость равна числу 0 в векторе решения, устанавливается равным 30. Результаты, достигнутые с помощью применения динамических сетевых структур, приведены в таблице 4 вместе с результатами двух лучших результатов в предыдущей серии экспериментов.

Согласно таблице 4, использование кольцевой топологии с динамическим размером окрестности приводит к лучшим результатам в 5 из 6 тестовых функций. Кольцевая топология с уменьшающейся средней степенью помогает методу обеспечить баланс между процессами изучения и эксплуатации, что, как хорошо известно, оказывает существенное влияние на производительность алгоритмов оптимизации, основанных на использовании популяции. Начиная с большего количества подключений, агенты имеют возможность взаимодействовать с большим количеством агентов, что означает, что у них есть доступ к более широкому спектру информации. Это приводит к большей способности к исследованию в пространстве поиска. Поскольку ссылки постепенно удаляются в ходе последующих итераций, каждый агент взаимодействует с меньшим количеством агентов, с которыми имеет длительные связи, и, следовательно, с большей вероятностью будет иметь с ними более близкие мнения. Таким образом, общие решения будут ближе, а поиск в пространстве решений будет более локализованным, следовательно, эксплуатация выполняется хорошо. Следовательно, будет использована эта оптимальная топология в качестве сети взаимодействия для GOFBO в экспериментальных сравнениях для анализа производительности алгоритмов оптимизации.

Динамика конвергенции

Предлагаемый алгоритм ищет оптимальную точку, поскольку он имитирует процесс формирования мнения среди искусственных агентов, приводящий к консенсусу среди популяции. В литературе по эволюционным вычислениям и роевому интеллекту это явление интерпретируется как конвергенция популяции. Здесь представляются эмпирические результаты сходимости предлагаемого алгоритма при условии изменения основных параметров процесса оптимизации. Используется задача ONEMAX и выполняется 20 запусков с независимыми случайными инициализациями для каждого случая. Среднее число итераций, необходимых для достижения сходимости, указывается в зависимости от основных параметров (см. рис. 5). По мере увеличения N время сходимости (среднее количество требуемых итераций до сходимости) вначале быстро растет, а затем рост замедляется (рис. 5.а). Больший размер окрестности делает время конвергенции менее чувствительным к увеличению численности популяции, поскольку каждый агент имеет больше связей с другими, и, следовательно, информация распространяется быстрее. С увеличением размера задачи время сходимости сначала резко возрастает, но постепенно стабилизируется при более высоких значениях размера задачи (рис. 5.б).

Сравнение GOFBO с другими методами оптимизации, основанных на использовании популяции

GOFBO выполняет оптимизацию на основе процесса консенсуса мнений во взаимодействующих многоагентных системах. Чтобы оценить эффективность GOFBO для задач бинарной оптимизации, сравнивается его производительность с рядом известных методов, основанных на популяции, а именно: Генетическими алгоритмами (GA), Бинарной гибридной топологией оптимизация роя частиц (BHTPSO), Оптимизацией роя частиц с выборочной информацией (SIPSO), Бинарным обучением с дифференциальной эволюцией (BLDE) и Дискретной искусственной пчелиной колонией (DisABC). Все эти методы широко использовались для различных задач бинарной оптимизации. Далее эти методы кратко объясняются, а затем подробно описываются экспериментальные сравнения.

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

PSO - это вдохновленный природой алгоритм оптимизации, который ищет допустимое пространство решений путем изменения траекторий для популяции объектов, называемых частицами [52]. На каждой итерации алгоритма все частицы обновляют свои позиции (решения, которых они придерживаются для решения проблемы) в соответствии с вектором скорости, который вычисляется путем корректировки текущей скорости частицы, на которую влияют как лучшие решения, найденные до сих пор в рое, так и лучшее решение, найденное до сих пор индивидуально самой частицей. В двоичных версиях PSO каждая вновь вычисленная скорость обычно ограничена определенным диапазоном а функция отображает скорость на действительное значение в диапазоне [0, 1],

которое затем используется в качестве вероятности переключения бита в векторе решения. Используется современный вариант бинарной PSO, называемый бинарной гибридной топологией PSO (BHTPSO) [53], который направлен на улучшение исследования и возможности перехода от локальных оптимумов путем объединения локальной и глобальной информации в рое частиц. BHTPSO обновляет скорость частицы i, как показано ниже:

где и - векторы скорости и положения, соответственно, для частицы i на итерации t. и являются наилучшими решениями, найденными до текущей итерации t отдельной частицей, среди всей популяции роя и среди соседей частицы соответственно. и - случайные вещественные числа, выбранные из равномерного распределения в интервале [0, 1]. Факторы обучения и определяют степень, в которой частицы получают помощь от своей индивидуальной и социально разделяемой информации. Инерция частицы на итерации t определяется которая фактически управляет влиянием текущей скорости на новую скорость Коэффициенты обучения и инерции рассчитываются следующим образом:

Используя обновленную скорость, BHTPSO обновляет положения частиц в каждом измерении в соответствии со следующим правилом:

где - действительное число, полученное из равномерного распределения в диапазоне а - функция преобразования, рассчитанная следующим образом:

и E вычисляется с использованием функции ошибок Гаусса:

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

SIPSO - это вариант PSO, который использует безмасштабные сети для представления структуры соединений для роя [54]. Подобно предлагаемому методу (GOFBO), SIPSO использует сетевую структуру для определения связей между частицами, которая генерируется с помощью модели BA. Каждая частица инициируется со случайной позицией {0, 1}и в процессе оптимизации они приобретают две разные стратегии в зависимости от их степеней, описываемых следующим правилом обновления скорости для каждого измерения

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

BLDE [55] - это недавно предложенный высокопроизводительный метод бинарной оптимизации, основанный на использовании популяции, разработанный на основе оригинального алгоритма DE. Этот метод включает в себя классические стратегии поиска DE [56] и механизм обучения PSO. BLDE архивирует решения, найденные предыдущим поколением, чтобы следующее поколение могло извлечь уроки из этого опыта. Этот современный вариант бинарного DE имеет только один параметр - способность к мутации

ABC - это популяционная метаэвристика, основанная на интеллектуальном поведении пчелиного роя в поисках пищи [14] и имеющая ряд эффективных вариантов [57], [58]. ABC масштабирует вектор разности, вычисленный между двумя решениями-кандидатами, используя параметр называемый коэффициентом масштабирования. В DisABC используется динамический коэффициент масштабирования, который вычисляется для каждой итерации алгоритма в соответствии с приведенной ниже формулой:

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

Чтобы обеспечить справедливое сравнение между методами, размер популяции для всех методов установлен равным Максимальное количество в 1000 итераций рассматривается как условие завершения для всех методов, в то время как генерация 100 потомков рассматривается как одна итерация для GA. Используется кольцевая структура с динамическим размером окрестности в качестве сети взаимодействия для предлагаемого метода. Другие настройки для GA, BHTPSO, BSIPSO, BLDE и DisABC взяты из предложений в соответствующих исследованиях [53], [54], [55], [57], [59], для которых сообщается о наилучшей производительности для каждого метода. В частности, выбор колеса рулетки, 2-точечное пересечение и линейно уменьшающаяся частота мутаций от до 0, которая вычисляется по уравнению (3), являются настройками, используемыми для GA. Инициализируется BHTPSO со случайными положениями и скоростями для частиц в рое, а оптимальный выбор параметров адаптирован из соответствующего исследования [53]. Значения параметров BHTPSO: и Для BSIPSO параметры задаются как и в соответствии со сделанными предложениями [54]. BLDE применяется к задачам с наиболее эффективным значением способности к мутации, представленным как { { }}. Чтобы применить DisABC, минимальное и максимальное значения коэффициента масштабирования устанавливаются как и соответственно. Краткое описание настроек параметров для методов, используемых в экспериментах, приведено в таблице 5.

Контрольные функции используются для тестирования производительности GOFBO, а также для сравнения ее с другими методами. Для проведения сравнений методы применяются к контрольным функциям в 50-ти запусках каждый с независимой случайной инициализацией популяции. Среднее значение наилучших, т.е. наименьших значений затрат, найденных во всех независимых запусках метода, рассматривается как показатель его эффективности для каждой конкретной функции. В таблице 6 средняя производительность каждого метода приведена со стандартным отклонением результатов. Результаты показывают, что GOFBO достигает наилучших результатов в 23 из 30 тестов. GA, BLDE и DisABC находят наилучшие решения для остальных функций. Тем не менее, GA имеет лучшую общую производительность по сравнению как с BLDE, так и с DisABC в соответствии с их ранжированием на основе средних значений. Средний ранг алгоритмов, основанный на средних наилучших найденных значениях затрат, равен 1.3, 2.5, 2.8, 3.5, 5.1, и 5.9 отсортированы от лучших к худшим общим показателям, соответствующим GOFBO, GA, BLDE, DisABC, BHTPSO и BSIPSO соответственно.

Результаты (таблица 6) показывают, что GOFBO достигает наименьшего стандартного отклонения в 11 из 30 тестов, для всех из которых он находит наилучшие решения. GOFBO также имеет самый высокий средний рейтинг по сравнению с другими в соответствии со стандартным отклонением результатов. Это говорит о большей надежности предлагаемого метода по сравнению с другими методами. В таблице 7 показаны минимальные и максимальные значения затрат, найденные в 50 запусках каждого метода для тестовых функций. Предложенный метод обнаружил минимальные значения затрат в 19 из 30 функций. Также для 16 из 30 тестовых функций наихудшее решение, найденное GOFBO, имеет наименьшую стоимость по сравнению с наихудшими решениями, найденными другими методами, что повышает уверенность в производительности предлагаемого метода.

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

Далее проводится непараметрическая статистическая проверка результатов, чтобы дополнить сравнения. Двусторонний тест ранговой суммы Уилкоксона [60] может отклонить нулевую гипотезу о том, что два набора данных (выборочных наборов) получены из непрерывных распределений с равными медианами; нулевая гипотеза также может быть сформулирована как одинаково вероятная, что значение, взятое из выборочного набора, будет меньше или больше значения, взятого из другого набора образцов. Отклонение нулевой гипотезы с высокой значимостью в случаях, когда предлагаемый алгоритм показывает более высокую среднюю производительность, означает, что результаты получены из смещенного распределения, что подтверждает превосходство результатов, достигнутых предлагаемым алгоритмом. Представляются результаты двустороннего теста ранговой суммы Уилкоксона для тестов, в которых предложенный метод показал наилучшие результаты (таблица 8). Как видно, предлагаемый метод предоставляет более низкие значения p, что указывает на то, что предлагаемый метод дает показательные результаты.

Вывод

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

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

Производительность предлагаемого оптимизатора также сравнивалась с рядом широко используемых классических и современных методов оптимизации, основанные на использовании популяции, включая GA, BHTPSO, BSIPSO, BLDE и DisABC. Эксперименты показали, что предлагаемый оптимизатор обладает наилучшей производительностью в 23 из 30 тестовых функций. GOFBO также превзошел другие с точки зрения минимальных и максимальных наилучших значений затрат, найденных при нескольких запусках каждой контрольной функции. Эффективность предложенного метода статистически проверяется с помощью критерия Уилкоксона.

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