аспирант
заведующий кафедрой «Вычислительные системы и информационная безопасность», доктор технических наук, профессор
доцент кафедры «Программное обеспечение вычислительной техники и автоматизированных систем», доктор технических наук, профессор
Introduction. Practical tasks (location of service points, creation of microcircuits, scheduling, etc.) often require an exact or approximate to exact solution at a large dimension. In this case, achieving an acceptable result requires solving a set cover problem, fundamental for combinatorics and the set theory. An exact solution can be obtained using exhaustive methods; but in this case, when the dimension of the problem is increased, the time taken by an exact algorithm rises exponentially. For this reason, the precision of approximate methods should be increased: they give a solution that is only approximate to the exact one, but they take much less time to search for an answer at a large dimension.
Materials and Methods. One of the ways to solve the covering problem is described, it is a genetic algorithm. The authors use a modification of the Goldberg model and try to increase its efficiency through various types of mutation and crossover operators. We are talking about gene mutations, two-point mutations, addition and deletion mutations, insertion and deletion mutations, saltation, mutations based on inversion. The following types of crossover operator are noted: single-point, two-point, three-point and their versions with restrictions, uniform, triad. The effect of the stopping condition and the probability values of genetic operators on the accuracy of the solutions is investigated. It is shown how an increase in the number of individuals in a generation affects the efficiency of a solution.
Research Results. The experiment results allow us to draw three conclusions. 1) It is recommended to use a combination of gene mutation and single-point crossing. 2) With an increase in the number of individuals, the accuracy of the result and the time to obtain it increases. The average deviation from the exact result at a task size of 25 × 25 was 0%, at 50 × 50 – 0%, at 75 × 75 – 0.013%, at 100 × 100 – 0%, at 110 × 110 – 0% (the number of individuals was 500).3) It is advisable to use the probabilities of the mutation and crossover operator 100% and 100%, respectively. Discussion and Conclusions. Recommendations are given to improve the efficiency of covering problem solution. To this end, a preferred combination of the genetic algorithm parameters, of types of crossover and mutation operators is indicated.
Введение. Практические задачи (размещение пунктов обслуживания, создание микросхем, составление расписаний и пр.) зачастую требуют точного или приближенного к точному решения при большой размерности. Достижение приемлемого результата в данном случае требует решения задачи покрытия множеств — фундаментальной для комбинаторики и теории множеств. Точное решение можно получить с помощью переборных методов, однако в этом случае при повышении размерности задачи во много раз возрастает время работы точного алгоритма. По этой причине следует увеличивать точность приближенных методов: они дают решение, лишь приближенное к точному, однако затрачивают на поиск ответа намного меньше времени при большой размерности.
Материалы и методы. Описывается один из способов решения задачи покрытия — генетический алгоритм. Авторы используют модификацию модели Голдберга и пытаются повысить ее эффективность с помощью различных видов оператора мутации и скрещивания. Речь идет о генной мутации, двухточечной мутации, мутации добавления и удаления, мутации вставки и удаления, сальтации, мутациях на основе инверсии. Отмечены следующие виды оператора скрещивания: одноточечный, двухточечный, трехточечный и их версии с ограничениями, равномерный, триадный. Исследуется влияние условия останова и значений вероятностей генетических операторов на точность получаемых решений. Показано, каким образом увеличение числа особей в поколении влияет на эффективность решения.
Результаты исследования. Итоги экспериментов позволяют сделать три вывода. 1) Рекомендуется использовать сочетание генной мутации и одноточечного скрещивания. 2) При повышении количества особей растет точность результата и время его получения. Среднее отклонение от точного результата при размере задачи 25×25 составило 0 %, при 50×50 — 0%, при 75×75 — 0,013 %, при 100×100 — 0 %, при 110×110 — 0 % (количество особей — 500). 3) Целесообразно использовать вероятности оператора мутации и скрещивания 100 % и 100 % соответственно.
Обсуждение и заключения. Даны рекомендации, позволяющие повысить эффективность решения задачи покрытия. С этой целью указано предпочтительное сочетание параметров генетического алгоритма, типов операторов скрещивания и мутации.
The authors declare that there are no conflicts of interest present.