Науковий вісник НГУ

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

• 
• 

Рейтинг користувача:  / 0

ГіршийКращий 

Деталі

Категорія: Інформаційні технології, системний аналіз та керування

Останнє оновлення: 09 лютого 2016

Опубліковано: 09 лютого 2016

Перегляди: 3818

Автори:

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

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

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

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

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

Реферат:

Мета. Класичний „мурашиний“ алгоритм оптимізації використовувався для вирішення завдання недетермі-нованої поліноміальної складності – „завдання комівояжера“, грунтуючись на тому, що мурашки, як правило, обирають дорогу, марковану великою кількістю феромону. Алгоритм Мах-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.

2015_06_lan
2016-02-08  560.88 KB  964

• < Попередня
• Наступна >