Cовременные информационные технологии/2. Вычислительная техника и программирование
Бендерук Юлия Андреевна, Граник Михаил Александрович, Месюра Владимир Иванович

Винницкий национальный технический университет

Динамический подбор коэффициентов социализации и персонализации метода роя частиц при решении задачи о распределении производственной нагрузки на основе генетического алгоритма

Введение

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

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

Формулировка задачи о распределении производственной нагрузки

Задача о распределении производственной нагрузки формулируется следующим образом: даны n заводов, каждый из которых выпускает некоторый металл. Стоимость выпуска p_i единиц металла на i-том заводе определяется по формуле (1):

(1)

Выпуск металла на каждом из заводов должен удовлетворять ограничениям, показанным в формуле (2):

(2)

Необходимо выпустить ровно s единиц металла, минимизировав при этом общие расходы.

В приведенных выше формулах a_i, b_i, c_i, pMin_i, pMax_i – некоторые константы, характеризующие i-ый завод.

Метод роя частиц и его применение к задаче о распределении производственной нагрузки

Метод роя частиц – имитационный метод, который был изобретен в 1995 году Эберхарта, Кеннеди и Ши. [1].

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

После начальной инициализации происходит итеративный процесс. На каждой итерации для каждой частицы пересчитывается ее скорость. Формула для пересчета скорости имеет следующий вид:

(3)

где v – вектор скорости, c₁ – важность персональной составляющей, rand () – случайная величина, равномерно распределенная на отрезке [0, 1], pbest – лучшая для данной частицы функция приспособленности, которая была достигнута в ходе итеративного процесса, current – ее текущая функция приспособленности, gbest – лучшая достигнута во время итеративного процесса функция приспособленности всех частиц популяции, c₂ – важность социальной составляющей. Константы c₁ и c₂ показывают, насколько частицы ориентируются на собственные и глобальные достигнутые результаты соответственно.

На основе измененной скорости частицы перечисляется также и ее позиция. Правило пересчета позиции является следующим:

(4)

После расчета новой позиции перечисляется функция приспособленности.

Есть несколько критериев остановки итерационного процесса. Первый из них – исчерпание заранее определенного количества итераций. Второй из них – достижение определенной точности вычислений.

Результат работы алгоритма – лучшая достигнута во время итерационного процесса функция приспособленности [2].

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

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

Изменение коэффициентов социализации и персонализации на основе генетического алгоритма

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

Самыми важными константами в методе роя частиц являются коэффициенты социализации и персонализации. Предлагается динамически подбирать их с помощью генетического алгоритма во время исполнения самого метода роя частиц, то есть при решении конкретной прикладной задачи. Для начала, для каждой частицы случайным образом сгенерируем значения коэффициентов из промежутка [0;4], используя равномерный закон распределения. Далее, на каждой итерации будем перебирать все пары частиц. Пускай сейчас рассматриваются i-ая и j-ая частицы. Не теряя общности, предположим, что функция приспособленности (в случае задачи о распределении производственной нагрузки – суммарная цена металла) i-ой частицы не меньше функции приспособленности j-ой частицы. Тогда с некоторой известной заранее вероятностью выполним такие действия:

с_1i=(c_1i+c_1j)/2.0 (5)

с_2i=(c_2i+c_2j)/2.0 (6)

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

Сравнение некоторых основных методов решения задачи о распределение производственной нагрузки

Было проведено сравнение генетического алгоритма, а также классического метода роя частиц и метода роя частиц с динамическим изменением коэффициентов социализации и персонализации на основе генетического алгоритма. Для сравнения были использованы корректные случайные наборы входных данных, каждый параметр которых – равномерно распределенная случайная величина. Количество заводов, выпускающих металл, принадлежало промежутку [0; 1000]. Параметры каждого завода принадлежали промежутку [0; 10000]. Общий объем металла также выбирался случайным образом, причем так, чтобы сохранить корректность входных данных. Алгоритмы сравнивались на трех выборках, которые состояли из 10, 50 и 100 тестовых наборов соответственно. При разработке программного обеспечения, реализующего метод роя частиц, использовались следующие константы: размер популяции – 70, количество итераций – 200, вероятность скрещивания – 0.3, вероятность мутации – 0.1. Для генетического алгоритма вероятность скрещивания была принята равной 0.6, остальные константы не изменились в сравнении с методом роя частиц. Критерий сравнения – среднее значение целевой функции (стоимости выпуска металла) для всех тестов выборки. Результат сравнения представлены в таблице 1.

Таблица 1 – Результат сравнения генетического алгоритма, классического метода роя частиц и метода роя частиц с изменением коэффициента социализации и персонализации на основе генетического алгоритма

Размер выборки	Результат генетического алгоритма	Результат классического метода роя частиц	Результат метода роя частиц с изменением коэффициента социализации и персонализации на основе генетического алгоритма
10	106992317864801.142	106798026507899.090	106596863347385.330
50	114285713148765.711	114191262738981.340	114152297875652.410
100	108320001363286.560	108320001363286.560	108303409725198.910

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

Выводы

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

Литература:

1. Девятков Владимир. Системы искусственного интеллекта. / Владимир Девятков. – М.: Издательство МГТУ им. Баумана, 2001. – 352 c. – ISBN 5-7038-1727-7.

2. Рассел Стюарт. Искусственный интеллект. Современный подход: пер. с англ. / Стюарт Рассел, Питер Норивг. – М.: «Вильямс», 2006. – 1408с. – ISBN 5-8459-0887-6.