10.14489/vkit.2016.11.pp.003-007

DOI: 10.14489/vkit.2016.11.pp.003-007

Рудова И. Ш., Кобак В. Г.
ВОЗМОЖНОСТИ ИСПОЛЬЗОВАНИЯ ЭЛИТНЫХ ОСОБЕЙ ПРИ РЕШЕНИИ ЗАДАЧИ КОММИВОЯЖЕРА МОДЕЛЬЮ ГОЛЬДБЕРГА
(c. 3-7)

Аннотация. Представлено влияние числа итераций и различного числа элитных особей на результат работы одного из эффективных полиномиальных алгоритмов – муравьиного алгоритма (МА) при решении задачи коммивояжера – сложной задачи дискретной оптимизации класса NP (Non-Deterministic Polynomial). В данной версии МА использована модификация – «правило псевдослучайных пропорций», поддерживающая баланс между использованием накопленных знаний и исследованием новых решений. Испытания проведены на графах средней размерности. Показано, что эффективность МА возрастает при увеличении числа особей на итерации. Также представлена следующая модификация алгоритма: в качестве «элитной» особи используется результат работы генетического алгоритма (ГА). Особенностью предложенного ГА является то, что задача решается только с помощью различных мутаций (без кроссовера).

Ключевые слова: задача коммивояжера; генетический алгоритм; граф; модель Гольдберга; мутация; крос¬совер; муравьиный алгоритм; элитная особь; феромон; природные вычисления.

Rudova I. Sh., Kobak V. G.
SOLVING TRAVELING SALESMAN PROBLEM BY USING ELITE INDIVIDUALS IN GOLDBERG MODEL
(pp. 3-7)

Abstract. The present paper studies the influence of the iterations number and the elite individuals number on the result of the Ant Algorithm (AA) performance in solving the Traveling Salesman Problem (TSP). TSP is Non-Deterministic Polynomial a challenging discrete optimization problem, for which there is no algorithm found, and perhaps there is no algorithm which would allow to find the exact solution in polynomial time. AA is one of the effective olynomial algorithms for finding approximate TSP solutions. This version of the AA uses modification – “the rule of pseudorandom proportions,” which maintains balance between the use of the accumulated knowledge and the research of new solutions. The tests were carried out on average dimension graphs. It is shown that the AA effectiveness increases with the increase of individuals per iteration.The values of the objective function, using the elite strategies, improve by an average of 8.5 %. Enter of the elite strategy has not led to the increase in the algorithm execution time. The following modification of the algorithm is also presented: as an “elite” individual we use the result of a Genetic Algorithm (GA) performance. A specific feature of the suggested genetic algorithm is that the problem can be solved only by different mutations (no crossover). The mutation probability in the proposed algorithm is 100 %. As a Mutation Operator (MO) we selected a simple two-point unbalanced MO. As a selection policy we used the “comparison of a mutating individual with an ancestor, and then the best of them with a random individual in the generation”. The Objective Function (OF) values are obtained on average of 0.8 % closer to the known optimum. The increase of “elit” individuals number leads to the deterioration of OF values on average of 2 %. OF values derived from the works of classical ant algorithm, the optimum pace with an average of 124.5 %, using the “the pseudo proportions rule” and elitism strategy, has improved OF values about 11 times.

Keywords: Traveling salesman problem; Genetic algorithm; Graph; The Goldberg model; Mutation; Crossover; Ant algorithm; Elite individual; Pheromone; Natural computing.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

И. Ш. Рудова, В. Г. Кобак (Донской государственный технический университет, Ростов-на-Дону, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

I. Sh. Rudova, V. G. Kobak (Don State Technical University, Rostov-on-Don, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Гладков, Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: ФИЗМАТЛИТ, 2006. 320 с.
2. Чураков М., Якушев А. Муравьиные алгоритмы [Электронный ресурс]. URL: http://rain.ifmo.ru/cat/view.php/ theory/unsorted/ant-algo-2006 (дата обращения: 17.01.2016).
3. Штовба С. Д. Муравьиные алгоритмы [Электронный ресурс]. URL: https://www.researchgate.net/publication/279535061_ Stovba_SD_Muravinye_algoritmy_Exponenta_Pro_Matematika_v_prilozeniah_-_2003_-_No4_-_S_70-75 (дата обращения: 25.12.2016).
4. Gambardella L. M., Dorigo M. Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem [Электронный ресурс]. URL: https://www.researchgate.net/publication/ 2322511_Ant-Q_A_Reinforcement_Learning_approach_to_the_traveling_salesman_problem (дата обращения: 16.12.2015).
5. Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a Colony of Cooperating Agents [Электронный ресурс]. URL: http://masters.donntu.org/2008/kita/khaustova/ library/6.htm (дата обращения: 15.12.2015).
6. Gambardella L. M., Dorigo M. Solving Symmetric and Asymmetric TSPs by Ant Colonies [Электронный ресурс]. URL: https://docviewer.yandex.ru/?url=http%3A%2F%2Fstaff. washington.edu%2Fpaymana%2Fswarm%2Fgambardella96-icec.pdf&name=gambardella96002Dicec.pdf&lang=en&c=56e017114bea (дата обращения: 27.12.2015).
7. Емельянов В. В., Курейчик В. М., Курейчик В. В. Теория и практика эволюционного моделирования. М.: ФИЗМАТЛИТ, 2003. 432 с.
8. Кобак В. Г., Рудова И. Ш., Жуковский А. Г. Сравнительный анализ модифицированной модели Гольдберга и муравьиного алгоритма при решении задачи коммивояжера // Тр. Сев.-Кавказ. фил. Моск. техн. ун-та связи и информатики: Междунар. молодеж. науч.-практ. конф. Ростов н/Д, 2015. T. 1. С. 362 – 365.
9. Кобак В. Г., Рудова И. Ш. Решение задачи коммивояжера модифицированной моделью Гольдберга с использованием различных сильных мутаций // Сб. тр. Юбилейной конф. студентов и молодых ученых, посвященной 85-летию ДГТУ. Ростов н/Д: ДГТУ, 2015. С. 146 – 156.
10. Кобак В. Г., Кавтарадзе И. Ш., Бормотов В. В., Швидченко С. А. Решение задачи коммивояжера модифицированной моделью Гольдберга с помощью различного вида мутаций // Тр. Сев.-Кавказ. фил. Моск. техн. ун-та связи и информатики: Междунар. молодеж. науч.-практ. конф. Ростов н/Д, 2014. T. 1. С. 258 – 261.

Eng

1. Gladkov L. A., Kureichik V. V., Kureichik V. M. (2006). Genetic algorithms. Moscow: FIZMATLIT. [in Russian language]
2. Churakov M., Iakushev A. (2006). Ant algorithms. Available at: http://rain.ifmo.ru/cat/view.php/ theory/unsorted/ant-algo-2006 (Accessed: 17.01.2016). [in Russian language]
3. Shtovba S. D. (2003). Ant algorithms. Available at: https://www.researchgate.net/publication/279535061_ Stovba_SD_Muravinye_algoritmy_Exponenta_Pro_Matematika_v_prilozeniah_-_2003_-_No4_-_S_70-75 (Accessed: 25.12.2016). [in Russian language]
4. Gambardella L. M., Dorigo M. Ant-Q: a reinforcement learning approach to the traveling salesman problem. Available at: https://www.researchgate.net/publication/ 2322511_Ant-Q_A_Reinforcement_Learning_approach_to_the_traveling_salesman_problem (Accessed: 16.12.2015).
5. Dorigo M., Maniezzo V., Colorni A. The ant system: optimization by a colony of cooperating agents. Available at: http://masters.donntu.org/2008/kita/khaustova/ library/6.htm (Accessed: 15.12.2015).
6. Gambardella L. M., Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies. Available at: https://docviewer.yandex.ru/?url=http%3A%2F%2Fstaff. washington.edu%2Fpaymana%2Fswarm%2Fgambardella96-icec.pdf&name=gambardella96002Dicec.pdf&lang=en&c=56e017114bea (Accessed: 27.12.2015).
7. Emel'ianov V. V., Kureichik V. M., Kureichik V. V. (2003). Theory and practice of evolutionary modeling. Moscow: FIZMATLIT. [in Russian language]
8. Kobak V. G., Rudova I. Sh., Zhukovskii A. G. (2015). Comparative analysis of modified Goldberg model and the ant algorithm for solving the traveling salesman problem. Proceedings of the North Caucasus branch of the Moscow Technical University of Communications and Informatics: International scientific and practical conference for young scientist. Vol. 1. (pp. 362-365). Rostov-on-Don. [in Russian language]
9. Kobak V. G., Rudova I. Sh. (2015). Solving the traveling salesman problem with Goldberg modified model using different forced mutations. Proceeding of the jubilee conference of the students and young scientist dedicated to 85th Anniversary of DGTU. (pp. 146-156). Rostov-on-Don: DGTU. [in Russian language]
10. Kobak V. G., Kavtaradze I. Sh., Bormotov V. V., Shvidchenko S. A. (2014). Solving the traveling salesman problem with Goldberg modified model using various types of mutations. Proceedings of the North Caucasus branch of the Moscow Technical University of Communications and Informatics: International scientific and practical conference for young scientist. Vol. 1. (pp. 258-261). Rostov-on-Don. [in Russian language]

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2016.11.pp.003-007}

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please fill out the form below:

{jform=2,doi=10.14489/vkit.2016.11.pp.003-007}