Владимир Анатольевич Судаков Д.т.н., Профессор
Anatolyevich Sudakov Vladimir Dr. Sci. (Engineering), Professor
Юрий Павлович Титов К.т.н
Yuri Pavlovich Titov Cand. Sci. (Engineering)
Цель исследования. Целью исследования является выработка рекомендаций по выбору параметров модификации метода муравьиных колоний при поиске рационального решения задачи назначения работников на работы при условии задания времени выполнения работы с применением нечетких множеств и учета времени взаимодействия между работниками, назначенными на одну задачу. Предложен алгоритм работы модификации метода муравьиных колоний. Рассмотрены различные алгоритмы остановки модифицированного метода муравьиных колоний.
Материалы и методы исследования. Применение, разработанного для поиска пути коммивояжера, метода муравьиных колоний для задачи назначения требует создания «графа решений» и некоторых модификаций алгоритма, связанных с занесением весов (феромона) на граф. В работе предлагается создать граф решений путем создания набора вершин, определяющих назначение работника на задачи, для каждого работника и вычисления пути в графе, определяющего решение задачи о назначении. Для остановки алгоритма метода муравьиных колоний рассматриваются два различных алгоритма: остановка при выполнении некоторого количества итераций и остановка при нахождения решения, удовлетворяющего ограничениям. Для оценки эффективности алгоритма рассматривались следующие критерии: оценка математического ожидания числа итераций алгоритма, оценка математического ожидания значения критерия, оценка математического ожидания числа рассмотренных решений и т.д. Для всех оценок математического ожидания вычисляется также доверительный интервал. По полученным оценкам в работе даются рекомендации по подбору параметров метода муравьиных колоний: количеству агентов, коэффициента испарения, параметров элитного и ранжированного метода муравьиных колоний и т.д. Оценивается и скорость и возможность поиска рациональных решений при различных значениях ограничений.
Результаты. В работе рассматривалась задача о назначении 35 работников по 15 задачам. В результате были выявлены следующие рекомендации по выбору параметров модифицированному методу муравьиных колоний. Чем больше агентов, тем лучше найденное решение, но количество рассмотренных решений увеличивается, что приводит к увеличению времени поиска. Для коэффициента испарения рекомендуется выбирать значение в пределах (0,8; 0,95). Использовать рекомендуется ранжированный алгоритм с параметром в 4 раза меньше количества агентов в группе. Определена проблема «зацикливания» метода муравьиных колоний, вызванная прохождением агентов по одним и тем же маршрутам.
Заключение. Выработанные рекомендации позволяют применять метод муравьиных колоний для решения задачи назначения работников на задачи. Предложенные рекомендации по параметрам обеспечивают высокую скорость и точность нахождения рационального решения задачи. Описана проблема «зацикливания» метода муравьиных колоний.
Purpose of the research. The aim of the study is to develop recommendations on the selection of parameters for modifying the ant colony method when searching for a rational solution to the task of appointing employees to work, subject to setting the time to complete the work using fuzzy sets and taking into account the interaction time between employees assigned to one task. The algorithm is proposed for modifying the ant colony method. Various stopping algorithms of the modified ant colony method are considered.
Materials and research methods. The use of the ant colony method developed for finding the traveling salesman’s path for the assignment problem requires the creation of a “decision graph” and some modifications of the algorithm associated with entering weights (pheromone) on the graph. The paper proposes to create a graph of solutions by creating a set of vertices that determine the appointment of an employee for tasks for each employee and calculating the path in the graph that determines the solution to the assignment problem. To stop the algorithm of the ant colony method, two different algorithms are considered: the stop when performing a certain number of iterations and the stop when finding a solution that satisfies the constraints. To evaluate the effectiveness of the algorithm, the following criteria were considered: the estimate of the mathematical expectation of the number of iterations of the algorithm, the estimate of the mathematical expectation of the criterion value, the estimate of the mathematical expectation of the number of considered solutions, etc. For all estimates of mathematical expectation, a confidence interval is also calculated. According to the estimates, the paper gives recommendations on the selection of parameters of the ant colony method: the number of agents, evaporation rate, parameters of the elite and ranked method of ant colonies, etc. Both the speed and the ability to find rational solutions for different values of constraints are evaluated.
Results. The work considered the task of appointing 35 employees for 15 tasks. As a result, the following recommendations were identified on the choice of parameters to the modified method of ant colonies. The more agents, the better solution found, but the number of the considered solutions increases, which leads to an increase in search time. For the evaporation coefficient, it is recommended to choose a value in the range (0.8; 0.95). It is recommended to use a ranked algorithm with a parameter 4 times less than the number of agents in the group. The problem of “cycling” of the ant colony method, caused by the passage of agents along the same routes, is determined.
Conclusion. The developed recommendations make it possible to use the ant colony method to solve the problem of assigning employees to tasks. The proposed recommendations on the parameters provide high speed and accuracy of finding a rational solution to the problem. The problem of “cycling” of the ant colony method is described.
The authors declare that there are no conflicts of interest present.