Кривошей Наталия Сергеевна, аспирантка кафедры «Программное обеспечение вычислительной техники и автоматизированных систем»
344000, г. Ростов-на-Дону, пл. Гагарина, 1
Krivoshey, Natalia S., postgraduate student of the Computer and Automated Systems Software Department
344000, Rostov-on-Don, Gagarin sq., 1
Кобак Валерий Григорьевич, доктор технических наук, профессор кафедры «Программное обеспечение вычислительной техники и автоматизированных систем»
344000, г. Ростов-на-Дону, пл. Гагарина, 1
Kobak, Valery G., Dr.Sci. (Eng.), professor of the Computer and Automated Systems Software Department
344000, Rostov-on-Don, Gagarin sq., 1
Introduction. A comparative analysis of the modified Whitley model solutions through different methods of forming elite individuals is presented. The algorithms of Kron and Plotnikov-Zverev are used in the study for the formation of elite individuals. The work objectives are the development of the modified Whitley model involving the Kron’s and PlotnikovZverev’s algorithms to form elite individuals, as well as a software tool for solving the scheduling theory problem. It was necessary to obtain the best solution to this problem with various initial data followed by processing the results and identifying a modification of the Whitley model. The distribution problem which implies the search for the optimal distribution of work to the processors with the minimization of the maximum execution time is described.
Materials and Methods. All the algorithms implemented under the development of the software tool for solving the optimization scheduling problem are considered. The following algorithms are presented: the modified Whitley model, the application of the elitism strategy, the Kron’s algorithm, the Plotnikov-Zverev’s algorithm.
Research Results. A software tool is developed. It was applied to conduct a computational experiment with various initial data using one, two, three, and four elite individuals. The experiment was carried out for the most common data sets with a different number of elite individuals. Each Whitley model modification was launched a hundred times with each set of the source data. The comparative analysis of the results shows how the application of the considered elitism strategies in the developed modifications of the genetic algorithm (Whitley model) affects the accuracy of the solution to the homogeneous minimax problem with a different number of elite individuals.
Discussion and Conclusions. The best results of the algorithms are determined; the utilization of elitism in the modified Whitley model when solving a homogeneous minimax problem of scheduling theory is estimated. The algorithm results are compared for one, two, three and four elite individuals.
Введение. Представлен сравнительный анализ решений модифицированной модели Уитли при различных способах формирования элитных особей. В данном исследовании для формирования элитных особей используются алгоритмы Крона и Плотникова-Зверева. Целями работы являлись разработка модифицированной модели Уитли с применением алгоритмов Крона и Плотникова-Зверева для формирования элитных особей, а также программного средства для решения задачи теории расписаний. Необходимо было получить лучшее решение этой задачи при различных исходных данных с последующей обработкой результатов и выявлением модификации модели Уитли. Описана задача, которая подразумевает поиск оптимального распределения работ по процессорам с минимизацией максимального времени выполнения работ.
Материалы и методы. Приведено описание всех алгоритмов, которые были реализованы при разработке программного средства решения задачи оптимизации построения расписания. Разработаны следующие алгоритмы: модифицированная модель Уитли, применение стратегии элитизма, алгоритм Крона, алгоритм Плотникова-Зверева.
Результаты исследования. Разработано программное средство, с помощью которого проведён вычислительный эксперимент при различных исходных данных, с использованием одной, двух, трёх и четырёх элитных особей. Вычислительный эксперимент проведён для наиболее распространённых наборов данных при различном количестве элитных особей. Каждая модификация модели Уитли запускалась сто раз с каждым набором исходных данных. В результате сравнительного анализа было выявлено, какое влияние оказывает использование рассмотренных стратегий элитизма в разработанных модификациях генетического алгоритма (модели Уитли) на точность решения однородной минимаксной задачи при различном количестве элитных особей.
Обсуждение и заключения. Определены лучшие результаты работы алгоритмов, выявлена эффективность применения элитизма в модифицированной модели Уитли при решении однородной минимаксной задачи теории расписаний. Проведено сравнение результатов работы алгоритма при одной, двух, трёх и четырёх элитных особях.
The authors declare that there are no conflicts of interest present.