Модифікований генетичний алгоритм визначення хроматичного числа графа
Вантажиться...
Дата
2019-06
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Кваліфікаційна робота включає пояснювальну записку (73 сторінки, 15 рисунків., 21 псевдокод, 11 таблиць, 5 графіків, 4 додатки).
Метою даного дипломного проекту є створення модифікації генетичного алгоритму визначення хроматичного числа графа.
В роботі розглянуто та проаналізовано етапи роботи класичного генетичного алгоритму. Розібрано різні види селекції та схрещування, найбільш поширені методи кодування даних, існуючі умови завершення роботи алгоритму. З усіх можливих варіантів вибрано такі, що найбільш підходять до вирішення задачі знаходження хроматичного числа, вибір обґрунтовано.
В програмі передбачена можливість: задавати кількість вершин та ребер в графі; створювати випадкові графи; задавати кількість початкової популяції, кількість батьків, що мутують при кожній ітерації, кількість батьків для кросоверу; зміни штрафу за некоректний колір вершини та штрафу за кожен новий колір; вибирати функцію мутації та схрещування; вказати бажане хроматичне число та перевірити його на конфліктність. Розроблено такі тестові моделі, що найбільш підходять для демонстрації функцій алгоритму. Проаналізована швидкість та точність в залежності від параметрів. Підібрано оптимальний набір функцій мутації та кросоверу, їх послідовність та ознака початку дії кожної функції.
Для реалізації генетичного алгоритму було обрано мову програмування Python.
Даний алгоритм може бути використаний для складання розкладів, розподілу частот, регістрів у мікропроцесорах, обчислення похідних, розпаралелювання обчислень за числовими методами.
Опис
Ключові слова
алгоритм, генетичний алгоритм, хроматичне число, граф, мутація, кросовер, фітнес-функція, Python, algorithm, genetic algorithm, chromatic number, graph, mutation, crossover, fitness function
Бібліографічний опис
Товстенко, О. В. Модифікований генетичний алгоритм визначення хроматичного числа графа : дипломний проект ... бакалавра : 6.050102 Комп'ютерна інженерія / Товстенко Ольга Вячеславівна. – Київ, 2019. – 86 с.