Метод рішення «задачі комівояжера» на основі алгоритму «великих і малих мурашок»

Рейтинг користувача:  / 0
ГіршийКращий 

Автори:

Іхуа Лань, Наньянський педагогічний університет, м. Наньян, провінція Хенань, КНР

Яньвей Тянь, Аньянський педагогічний університет, м. Аньян, провінція Хенань, КНР

Янь Тянь, Наньянський педагогічний університет, м. Наньян, провінція Хенань, КНР

Цзіньцзян Лю, Наньянський педагогічний університет, м. Наньян, провінція Хенань, КНР

Сяо Цзя, Південний медичний университет, м. Гуанчжоу, провінція Гуандун, КНР

Реферат:

Мета. Класичний „мурашиний“ алгоритм оптимізації використовувався для вирішення завдання недетермі-нованої поліноміальної складності – „завдання комівояжера“, грунтуючись на тому, що мурашки, як правило, обирають дорогу, марковану великою кількістю феромону. Алгоритм Мах-min „мурашиної системи“ (MMAS), переважно, приводить до найближчого сусіднього міста та завжди формулює локально оптимальне рішення.

Методика. Сформульовано алгоритм „колонії великих і малих мурашок“ зі, свого роду, стратегією „стрибок через яму“. При цьому великі мурашки можуть переносити більшу кількість феромону та більш схильні до помилок.

Результат. Уперше використаний алгоритм колонії великих і малих мурашок для збільшення швидкості сходження. Потім, за використання концепції стрибок через яму, був реалізований пошук шляхів у більш широкому діапазоні, де стратегія малого стрибка дозволяє більш ніж одній мурашці вибрати альтернативний шлях, а стратегія великого стрибка дозволяє ставити перешкоди на дорозі, відміченій феромоном, та примушувати мурашок обирати іншу дорогу. Результати експериментів показали, що модифікований алгоритм завжди досягає оптимального результату на відміну від MMAS-алгоритму.

Наукова новизна. Вивчено новий „мурашиний алгоритм“ і розглянута ефективність ідеї, що раніше не об-говорювалася.

Практична значимість. Запропонований алгоритм може використовуватися для вирішення багатьох завдань, особливо у поєднанні з яким-небудь детермінованим алгоритмом для реалізації швидкої загальної оптимізації.

Список літератури / References:

  1. Pang, S., Ma, T., and Liu, T. (2015), “An improved ant colony optimization with optimal search library for solving the traveling salesman problem“. Journal of Computational & Theoretical Nanoscience, vol.12, no.5, pp. 440−1444.

  2. Bu, Y., Li, T. Q., and Zhang, Q. (2015), “A weighted max-min ant colony algorithm for tsp instances“. Ieice Trans Fundamentals, vol.98, no.3, pp. 894−897.

  3. Basheerjasser, M., Sarmini, M., and Yaseen, R. (2014), “Ant colony optimization (ACO) and a variation of bee colony optimization (BCO) in solving tsp problem, a comparative study“. International Journal of Computer Applications, vol.96, no.1, pp. 1−8.

  4. Camp, C. V., and Bichon, B. J. (2014), “Design of space trusses using ant colony optimization“. Journal of Structural Engineering, vol.130, no.5, pp. 741−751.

  5. Shuang, B., Chen, J., and Li, Z. (2011), “Study on hybrid ps-aco algorithm“. Applied Intelligence, vol.34, no.1, pp. 64−73.

  6. Mavrovouniotis, M., and Yang, S. (2011), “A memetic ant colony optimization algorithm for the dynamic travelling salesman problem“. Soft Computing, vol.15, no.7, pp. 1405−1425.

  7. Dorigo, M., and Blum, C. (2005), “Ant colony optimization theory: a survey“. Theoretical Computer Science. Vol.344, no.1, pp. 243−278

  8. Dorigo, M. (1997), “Ant colonies for the traveling salesman problem“. Biosystems, vol.12, no.2, pp. 667−670.

  9. Dorigo, M., and Stützle, T. (1999), “The ant colony optimization meta-heuristic“. New Ideas in Optimization, vol.28, no.3, pp. 11−32.

 

Files:
2015_06_lan
Date 2016-02-08 Filesize 560.88 KB Download 412

Відвідувачі

3230789
Сьогодні
За місяць
Всього
188
17392
3230789

Гостьова книга

Якщо у вас є питання, побажання або пропозиції, ви можете написати їх у нашій «Гостьовій книзі»

Реєстраційні дані

ISSN (print) 2071-2227,
ISSN (online) 2223-2362.
Журнал зареєстровано у Міністерстві юстиції України.
Реєстраційний номер КВ № 17742-6592ПР від 27.04.2011.

Контакти

49005, м. Дніпро, пр. Д. Яворницького, 19, корп. 3, к. 24 а
Тел.: +38 (056) 746 32 79.
e-mail: Ця електронна адреса захищена від спам-ботів. вам потрібно увімкнути JavaScript, щоб побачити її.
Ви тут: Головна Про журнал редакційна колегія UkrCat Архів журналу 2015 Зміст №6 2015 Інформаційні технології, системний аналіз та керування Метод рішення «задачі комівояжера» на основі алгоритму «великих і малих мурашок»