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

Аннотация

Предлагается метод решения задачи выделения максимальной клики в графе на осно-ве модифицированной модели адаптивного поведения роя частиц. Метод роя частиц явля-ется методом стохастической оптимизации в чем-то схожим с эволюционными алгорит-мами. Этот метод моделирует не эволюцию, а ройное и стайное поведение животных. В отличие от популяционных методов метод роя частиц работает с одной статической популяцией, члены которой постепенно улучшаются с появлением информации о про-странстве поиска. В качестве структуры данных, несущей информацию о решении, ис-пользуется последовательность, представляющую собой очередность формирования ре-шения, которая называется приоритетным списком. Приоритетный список – это кодиро-ванное решение, в терминах генетического алгоритма – «хромосома». Приоритетный список является косвенной схемой кодирования решения. Переход от приоритетного спи-ска к решению производится с помощью декодера. Декодер – оператор, позволяющий пе-рейти от косвенной (числовой) схемы кодирования решения задачи к фенотипу. Фактиче-ски приоритетный список является интерпретацией решения в конкретной предметной области. Описываются поисковые процедуры в пространстве решений, механизмы поведе-ния модернизированного роя частиц. Ключевая проблема, которая была решена в данной работе, связана с разработкой структуры аффинного пространства позиций, позволяю-щей отображать и осуществлять поиск интерпретаций решений с целочисленными значе-ниями параметров. В отличие от канонического метода роя частиц, для уменьшения веса аффинных связей, путем перемещения частицы в новую позицию аффинного пространства решений разработан оператор направленной мутации, суть которого заключается в изме-нении целочисленных значений генов в хромосоме. Временная сложность алгоритма, полученная экспериментальным путем, совпадает с теоретическими исследованиями и для рассмотренных тестовых задач составляет О(n2) – О(n3). Вероятность получения гло-бального оптимума составила 0,94. В среднем запуск программы обеспечивает нахождения решения, отличающегося от оптимального менее, чем на 1.5%. Результаты показыва-ют, что предлагаемый подход является приемлемой альтернативой для решения комбина-торных задач.