Модифікований генетичний алгоритм визначення хроматичного числа графа

Скорочена інформація про документ
dc.contributor.advisorМарченко, Олександр Іванович
dc.contributor.authorТовстенко, Ольга Вячеславівна
dc.date.accessioned2019-07-29T16:02:38Z
dc.date.available2019-07-29T16:02:38Z
dc.date.issued2019-06
dc.description.abstractenThe qualifying work includes an explanatory note (73 pages, 15 figures, 21 pseudocodes, 11 tables, 5 charts, 4 annexes). The purpose of this diploma project is to create a modification of the genetic algorithm for determining the chromatic number of a graph. The stages of the work of the classical genetic algorithm are considered and analyzed in this work. Different types of breeding and crossover are analyzed, the most common methods of encoding data, the existing conditions for the completion of the algorithm. Of all possible options, those that are most suited to the solution of the problem of finding a chromatic number are selected, the choice is justified. The program provides the ability to: set the number of vertices and edges in the graph; create random graphs; set the number of initial population, the number of parents, mutate each iteration, the number of parents for the crossover; change the fine for the wrong color of the summit and fine for each new color; select mutation and crossing function; specify the desired chromatic number and check it for conflicts. The following test models are developed that are most suitable for demonstrating the functions of the algorithm. The speed and accuracy are analyzed, depending on the parameters. The optimal set of mutation and crossover functions, their sequence and a sign of the beginning of each function's operation are selected. To implement the genetic algorithm was selected the Python programming language. This algorithm can be used for scheduling, frequency distribution, registers in microprocessors, derivative calculations, parallelization of computations by numerical methods.uk
dc.description.abstractukКваліфікаційна робота включає пояснювальну записку (73 сторінки, 15 рисунків., 21 псевдокод, 11 таблиць, 5 графіків, 4 додатки). Метою даного дипломного проекту є створення модифікації генетичного алгоритму визначення хроматичного числа графа. В роботі розглянуто та проаналізовано етапи роботи класичного генетичного алгоритму. Розібрано різні види селекції та схрещування, найбільш поширені методи кодування даних, існуючі умови завершення роботи алгоритму. З усіх можливих варіантів вибрано такі, що найбільш підходять до вирішення задачі знаходження хроматичного числа, вибір обґрунтовано. В програмі передбачена можливість: задавати кількість вершин та ребер в графі; створювати випадкові графи; задавати кількість початкової популяції, кількість батьків, що мутують при кожній ітерації, кількість батьків для кросоверу; зміни штрафу за некоректний колір вершини та штрафу за кожен новий колір; вибирати функцію мутації та схрещування; вказати бажане хроматичне число та перевірити його на конфліктність. Розроблено такі тестові моделі, що найбільш підходять для демонстрації функцій алгоритму. Проаналізована швидкість та точність в залежності від параметрів. Підібрано оптимальний набір функцій мутації та кросоверу, їх послідовність та ознака початку дії кожної функції. Для реалізації генетичного алгоритму було обрано мову програмування Python. Даний алгоритм може бути використаний для складання розкладів, розподілу частот, регістрів у мікропроцесорах, обчислення похідних, розпаралелювання обчислень за числовими методами.uk
dc.format.page86 с.uk
dc.identifier.citationТовстенко, О. В. Модифікований генетичний алгоритм визначення хроматичного числа графа : дипломний проект ... бакалавра : 6.050102 Комп'ютерна інженерія / Товстенко Ольга Вячеславівна. – Київ, 2019. – 86 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/28650
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.subjectалгоритмuk
dc.subjectгенетичний алгоритмuk
dc.subjectхроматичне числоuk
dc.subjectграфuk
dc.subjectмутаціяuk
dc.subjectкросоверuk
dc.subjectфітнес-функціяuk
dc.subjectPythonuk
dc.subjectalgorithmuk
dc.subjectgenetic algorithmuk
dc.subjectchromatic numberuk
dc.subjectgraphuk
dc.subjectmutationuk
dc.subjectcrossoveruk
dc.subjectfitness functionuk
dc.titleМодифікований генетичний алгоритм визначення хроматичного числа графаuk
dc.typeBachelor Thesisuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Tovstenko_bakalavr.pdf
Розмір:
3.1 MB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.06 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Бакалаврські роботи (СПСКС)
Бакалаврські роботи