Preview

Вестник Донского государственного технического университета

Расширенный поиск

Возможности использования элитных особей при решении задачи коммивояжера моделью Гольдберга

https://doi.org/10.12737/19695

Полный текст:

Аннотация

Целью данной работы является исследование актуальной задачи коммивояжера, которая является NP сложной задачей дискретной оптимизации. Показано, что для достижения поставленной цели пригодны лишь эвристические методы. Для решения задачи представлен результат совместного использования муравьиного (МА) и генетического (ГА) алгоритмов. Особенностью предложенного генетического алгоритма является то, что задача решается только с помощью различных мутаций (без кроссовера). Исследуемый ГА был улучшен введением элитарной стратегии. Испытания проводились на графах средней и большой размерности. Элитная особь, получаемая с помощью муравьиного алгоритма, в среднем улучшалась на 11 %. Показано, что эффективность генетического алгоритма напрямую зависит от количества особей в поколении и количества итераций алгоритма. Ввод элитарной стратегии улучшил получаемые значения целевой функции более чем в 2 раза. Увеличение числа запусков МА при выборе элиты позволило повысить эффективность алгоритма приблизительно на 2 %.

Об авторах

Валерий Григорьевич Кобак
Донской государственный технический университет
Россия


Ирма Шалвовна Рудова
Донской государственный технический университет
Россия


Список литературы

1. Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик - Москва : Физматлит, 2007. - 272 с.

2. Gambardella, L.-M. Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem [Электронный ресурс] / L.-M. Gambardella, M. Dorigo. - Режим доступа: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.4846 (дата обращения: 16.09.15).

3. Dorigo, M. The Ant System: Optimization by a colony of cooperating agents [Электронный ресурс] / M. Dorigo, V. Maniezzo, A. Colorni. - Режим доступа: ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf (дата обращения: 20.09.15).

4. Gambardella, L.-M. Solving symmetric and asymmetric TSPs by ant colonies [Электронный ресурс] / L.-M. Gambardella, M. Dorigo. - Режим доступа: http://ceit.aut.ac.ir/~meybodi/Learning%20Automata%20papers/LA-Papers-Ebdali/00542672.PDF (дата обращения: 27.09.15).

5. Чураков, М. Муравьиные алгоритмы. / М. Чураков, А. Якушев. - Режим доступа: http://rain.ifmo.ru/cat/ (дата обращения: 25.09.2015).

6. Штовба, С. Д. Муравьиные алгоритмы [Электронный ресурс] / С. Д. Штовба. - Режим доступа: http://www.serhiyshtovba.narod.ru/doc/Shtovba_Ant_Algorithms_Exponenta Pro_2003_3.pdf (дата обращения: 25.09.15).

7. Емельянов, В. В. Теория и практика эволюционного моделирования / В. В. Емельянов, В. М. Курейчик, В. В. Курейчик. - Москва : Физматлит, 2003. - 432 с.

8. Кобак, В. Г. Сравнительный анализ модифицированной модели Гольдберга и муравьиного алгоритма при решении задачи коммивояжера / В. Г. Кобак, И. Ш. Рудова, А. Г. Жуковский // Тр. Сев.-Кавк. филиала Моск. техн. ун-та связи и информатики. - Ростов-на-Дону, 2015. - T. 1. - С. 362-365.

9. Кобак, В. Г. Решение задачи коммивояжера модифицированной моделью Гольдберга с использованием различных сильных мутаций / В. Г. Кобак, И. Ш. Рудова // Сб. тр. юбилейной конф. студентов и молодых ученых, посвященной 85-летию ДГТУ. - Ростов-на-Дону, 2015. - С. 146-156.

10. Решение задачи коммивояжера модифицированной моделью Гольдберга с помощью различного вида мутаций / В. Г. Кобак [и др.] // Тр. Сев.-Кавк. филиала Моск. техн. ун-та связи и информатики. - Ростов-на-Дону, 2014. - T. 1. - С. 258-261.


Для цитирования:


Кобак В.Г., Рудова И.Ш. Возможности использования элитных особей при решении задачи коммивояжера моделью Гольдберга. Вестник Донского государственного технического университета. 2016;16(2):129-135. https://doi.org/10.12737/19695

For citation:


Kobak V.G., Rudova I.S. Applicability of elite samples in solving the traveling salesman problem by Goldberg model. Vestnik of Don State Technical University. 2016;16(2):129-135. (In Russ.) https://doi.org/10.12737/19695

Просмотров: 85


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1992-5980 (Print)
ISSN 1992-6006 (Online)