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

Abstract

RU: Решена актуальная задача получения последовательности опытов при проведении полного факторного эксперимента, обеспечивающей его минимальную стоимость. Цель работы – создание метода для оптимизации многофакторных планов эксперимента с помощью алгоритма оптимизации роем частиц. Метод. Предложен метод построения оптимальной матрицы планирования эксперимента по стоимости реализации с использованием алгоритма роя частиц. Метод роя частиц базируется на моделировании поведения популяции частиц в пространстве параметров задачи оптимизации. Вначале вводится количество факторов и стоимость перехода для каждого уровня факторов. Затем с учетом введенных данных формируется сводная матрица планирования эксперимента. Частицы разбросаны случайным образом по всей сводной матрице планирования эксперимента, и каждая частица имеет случайный вектор скорости. После этого частицы начинают перемещаться по строкам и столбцам матрицы. В каждой точке, где побывала частица, рассчитывается значение стоимости проведения эксперимента. При этом каждая частица запоминает, какое (и где) лучшее значение стоимости эксперимента она лично нашла и где расположена точка, являющаяся лучшей среди всех точек, которые разведали частицы. На каждой итерации частицы корректируют свою скорость (модуль и направление), чтобы с одной стороны быть поближе к лучшей точке, которую она нашла сама и, в то же время, приблизиться к точке, которая в данный момент является глобально лучшей. Через некоторое количество итераций частицы собираются вблизи наиболее хорошей точки. Затем корректируется текущая координата каждой частицы. После этого рассчитывается значение стоимости проведения эксперимента в каждой новой точке, каждая частица проверяет, не стала ли новая координата лучшей среди всех точек, где она побывала. Затем среди всех новых точек осуществляется проверка, не нашли ли мы новую глобально лучшую точку, и, если нашли, запоминаем ее координаты и значение стоимости проведения эксперимента в ней. Затем рассчитывается выигрыш по сравнению с исходной стоимостью проведения эксперимента. Результаты. Разработано программное обеспечение, реализующее предложенный метод, которое использовано при проведении вычислительных экспериментов по исследованию свойств метода. Выводы. Проведенные эксперименты подтвердили работоспособность предложенного метода и реализующего его программного обеспечения, а также позволяют рекомендовать их для применения на практике при построении оптимальных матриц планирования экспериментов. UK: Вирішено актуальну завдачу отримання послідовності дослідів при проведенні повного факторного експерименту, що забезпечує його мінімальну вартість. Мета роботи – створення методу для оптимізації багатофакторних планів експерименту за допомогою алгоритму оптимізації роєм часток. Метод. Запропоновано метод побудови оптимальної матриці планування експерименту за вартістю реалізації з використанням алгоритму рою часток. Метод рою часток базується на моделюванні поведінки популяції частинок в просторі параметрів задачі оптимізації. На початку вводиться кількість чинників і вартість переходу для кожного рівня факторів. Потім з урахуванням введених даних формується зведена матриця планування експерименту. Частинки розкидані випадковим чином по всій зведеної матриці планування експерименту і кожна частинка має випадковий вектор швидкості. Після цього частинки починають переміщатися по рядках і стовпцях матриці. У кожній точці, де побувала частинка, розраховується значення вартості проведення експерименту. При цьому кожна частка запам’ятовує, яке (і де) краще значення вартості експерименту вона особисто знайшла і де розташована точка, яка є кращою серед усіх точок, які розвідали частки. На кожній ітерації частки коректують свою швидкість (модуль і напрямок), щоб з одного боку бути ближче до кращої точці, яку вона знайшла сама і, в той же час, наблизитися до точки, яка в даний момент є глобально кращої. Через деякий кількість ітерацій частки збираються поблизу найбільш хорошою точки. Потім коригується поточна координата кожної частки. Після цього розраховується значення вартості проведення експерименту в кожній новій точці, кожна частка перевіряє, чи не стала нова координата кращою серед усіх точок, де вона побувала. Потім серед усіх нових точок здійснюється перевірка, чи не знайшли ми нову глобально кращу точку, і, якщо знайшли, запам’ятовуємо її координати і значення вартості проведення експерименту в ній. Потім розраховується виграш в порівнянні з вихідною вартістю проведення експерименту. Результати. Розроблено програмне забезпечення, що реалізує запропонований метод, який використано при проведенні обчислювальних експериментів з дослідження властивостей методу. Висновки. Проведені експерименти підтвердили працездатність запропонованого методу і реалізує його програмного забезпечення, а також дозволяють рекомендувати їх для застосування на практиці при побудові оптимальних матриць планування експериментів. EN: The actual problem of obtaining a sequence of experiments in the conduct of a full factor experiment ensuring its minimum cost has been solved. Objective – is to create a method for optimizing multifactor experimental plans using an optimization algorithm for the particle swarm. Method. A method is proposed for constructing an optimal experiment design matrix for the cost of implementation using the particle swarm algorithm. The particle swarm method is based on modeling the behavior of the particle population in the parameter space of the optimization problem. In the beginning, the number of factors and the cost of the transition for each level of factors are introduced. Then, taking into account the input data, a composite matrix of experiment planning is formed. The particles are scattered randomly across the entire composite experiment design matrix and each particle has a random velocity vector. After that, the particles begin to move along the rows and columns of the matrix. At each point where the particle visited, the value of the experiment is calculated. In this case, each particle remembers which (and where) the best value of the cost of the experiment, she personally found and where the point is located, which is the best among all the points that explored the particles. At each iteration, the particles correct their velocity (module and direction) in order to be closer to the best point on the one hand, which she found herself and, at the same time, to approach the point that is currently globally better. After a certain number of iterations, the particles are collected near the best point. Then the current coordinate of each particle is corrected. After this, the cost of the experiment is calculated at each new point, each particle checks whether the new coordinate has become the best among all the points where it visited. Then, among all the new points, we check whether we have found a new globally better point, and if found, remember its coordinates and the value of the cost of conducting the experiment in it. Then the gain is calculated in comparison with the initial cost of the experiment. Results. The software that implements the proposed method is developed, which was used in carrying out computational experiments to study the properties of the method. Conclusions. The conducted experiments confirmed the efficiency of the proposed method and the software that implements it, and also allow them to be recommended for application in practice when constructing optimal experimental design matrices.