http://iet.metastore.ingenta.com
1887

Ant colony optimisation for coloured travelling salesman problem by multi-task learning

Ant colony optimisation for coloured travelling salesman problem by multi-task learning

For access to this article, please select a purchase option:

Buy eFirst article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
— Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Traditional algorithms, such as genetic algorithm and simulated annealing, have greatly attracted a lot of research studies due to their simplicity and flexibility to solve coloured travelling salesman problem (CTSP). However, their performance is limited in solution quality and convergence speed. To improve these limitations, this study presents a fast and effective ant colony optimisation (FEACO) algorithm. In the proposed FEACO, a new pheromone updating mechanism is incorporated into the traditional ant colony optimisation (ACO) to improve its performance. Furthermore, a multi-task cooperative learning approach is employed to solve CTSP. In it, multiple tasks in a shared city set are cooperatively carried out by all salesmen, but each task in exclusive city sets is independently performed by an appointed salesman. In ACO and FEACO, feasible solutions can be found for CTSP by cooperative learning, which is carried out by the cooperation of a set of ants. During the process, ants can cooperate to find good solutions by utilising the pheromone deposited on the paths while ants pass them. Compared with state-of-the-art algorithms, the experimental results on both small scale and larger scale show that the proposed method has potential to provide an improvement in solution quality and convergence speed.

References

    1. 1)
      • J. Li , M.C. Zhou , Q.R. Sun .
        1. Li, J., Zhou, M.C., Sun, Q.R., et al: ‘Coloured travelling salesman problem’, IEEE Trans. Cybern., 2015, 45, (11), pp. 23902401.
        . IEEE Trans. Cybern. , 11 , 2390 - 2401
    2. 2)
      • J. Li , Q. Sun , M.C. Zhou .
        2. Li, J., Sun, Q., Zhou, M.C., et al: ‘A new multiple travelling salesman problem and its genetic algorithm-based solution’. Proc. 2013 IEEE Int. Conf. on Systems Man and Cybernetics, Manchester, UK, 2013, pp. 16.
        . Proc. 2013 IEEE Int. Conf. on Systems Man and Cybernetics , 1 - 6
    3. 3)
      • P. Wang , C. Sanin , E. Szczerbicki .
        3. Wang, P., Sanin, C., Szczerbicki, E.: ‘Evolutionary algorithm and decisional DNA for multiple travelling salesman problem’, Neurocomputing, 2015, 150, pp. 5057.
        . Neurocomputing , 50 - 57
    4. 4)
      • L. Kota , K. Jarmai .
        4. Kota, L., Jarmai, K.: ‘Mathematical modelling of multiple tour multiple travelling salesman problem using evolutionary programming’, Appl. Math. Model., 2015, 39, (12), pp. 34103433.
        . Appl. Math. Model. , 12 , 3410 - 3433
    5. 5)
      • M. Dorigo , V. Maniezzo , A. Colorni .
        5. Dorigo, M., Maniezzo, V., Colorni, A.: ‘Ant system: optimization by a colony of cooperating agents’, IEEE Trans. Syst. Man Cybern. B, Cybern., 1996, 26, (1), pp. 2941.
        . IEEE Trans. Syst. Man Cybern. B, Cybern. , 1 , 29 - 41
    6. 6)
      • M. Dorigo , L.M. Gambardella .
        6. Dorigo, M., Gambardella, L.M.: ‘Ant colony system: a cooperative learning approach to the travelling salesman problem’, IEEE Trans. Evol. Comput., 1997, 1, (1), pp. 5366.
        . IEEE Trans. Evol. Comput. , 1 , 53 - 66
    7. 7)
      • W.Y. Dong , X.S. Dong .
        7. Dong, W.Y., Dong, X.S.: ‘Parameters selection for genetic algorithms and ant colony algorithms by uniform design’, Lect. Notes Comput. Sci., 2014, 8588, pp. 184195.
        . Lect. Notes Comput. Sci. , 184 - 195
    8. 8)
      • T.J. Liao , K. Socha , M.A. Oca .
        8. Liao, T.J., Socha, K., Oca, M.A., et al: ‘Ant colony optimization for mixed-variable optimization problems’, IEEE Trans. Evol. Comput., 2013, 18, (4), pp. 503518.
        . IEEE Trans. Evol. Comput. , 4 , 503 - 518
    9. 9)
      • C. Pereira , L. Gonçalves , M. Ferreira .
        9. Pereira, C., Gonçalves, L., Ferreira, M.: ‘Exudate segmentation in fundus images using an ant colony optimization approach’, Inf. Sci., 2015, 296, pp. 1424.
        . Inf. Sci. , 14 - 24
    10. 10)
      • W.Y. Dong , W.S. Zhang , R.G. Yu .
        10. Dong, W.Y., Zhang, W.S., Yu, R.G.: ‘Convergence and runtime analysis of ITÖ algorithm for one class of combinatorial optimization’, Chin. J. Comput., 2011, 34, (4), pp. 636646.
        . Chin. J. Comput. , 4 , 636 - 646
    11. 11)
      • Y.F. Yi , Y.L. Cai , W.Y. Dong .
        11. Yi, Y.F., Cai, Y.L., Dong, W.Y., et al: ‘Improved ITÖ for multi-objective real-time vehicle routing problem with customers satisfaction’, Acta Electron. Sin., 2015, 43, (10), pp. 20532061.
        . Acta Electron. Sin. , 10 , 2053 - 2061
    12. 12)
      • W.Y. Dong , Y.L Cai , Y.F Wang .
        12. Dong, W.Y., Cai, Y.L, Wang, Y.F, et al: ‘Discrete ITÔ algorithm to the coloured travelling salesman problem’, Int. J. Wireless Mob. Comput., 2016, 11, (2), pp. 157165.
        . Int. J. Wireless Mob. Comput. , 2 , 157 - 165
    13. 13)
      • Z.L. Kang , K. Grauman , F. Sha .
        13. Kang, Z.L., Grauman, K., Sha, F.: ‘Learning with whom to share in multi-task feature learning’. Proc. 28th Int. Conf. on Machine Learning (ICML), Bellevue, WA, USA, 2011, pp. 18.
        . Proc. 28th Int. Conf. on Machine Learning (ICML) , 1 - 8
    14. 14)
      • J. Gao , W. Fan , J. Jiang .
        14. Gao, J., Fan, W., Jiang, J., et al: ‘Knowledge transfer via multiple model local structure mapping’. Proc. 14th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (SIGKDD), Las Vegas, NV, USA, 2008, pp. 283291.
        . Proc. 14th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (SIGKDD) , 283 - 291
    15. 15)
      • J.L. Pan , Q. Yang .
        15. Pan, J.L., Yang, Q.: ‘A survey on transfer learning’, IEEE Trans. Knowl. Data Eng., 2010, 22, (10), pp. 13451359.
        . IEEE Trans. Knowl. Data Eng. , 10 , 1345 - 1359
    16. 16)
      • Y. Zhang .
        16. Zhang, Y.: ‘Multi-task learning and algorithmic stability’. Proc. 29th AAAI Conf. on Artificial Intelligence (AAAI), Austin, TX, USA, 2015, pp. 31813187.
        . Proc. 29th AAAI Conf. on Artificial Intelligence (AAAI) , 3181 - 3187
    17. 17)
      • L. Chen , Q. Zhang , B.X. Li .
        17. Chen, L., Zhang, Q., Li, B.X.: ‘Predicting multiple attributes via relative multi-task learning’. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), Columbus, OH, USA, 2014, pp. 10271034.
        . IEEE Conf. on Computer Vision and Pattern Recognition (CVPR) , 1027 - 1034
    18. 18)
      • C. Su , F. Yang , S. Zhang .
        18. Su, C., Yang, F., Zhang, S., et al: ‘Multi-task learning with low rank attribute embedding for person re-identification’. IEEE Int. Conf. on Computer Vision (ICCV), Santiago, Chile, 2015, pp. 37393747.
        . IEEE Int. Conf. on Computer Vision (ICCV) , 3739 - 3747
    19. 19)
      • L. Zhao , Q. Sun , J.P. Ye .
        19. Zhao, L., Sun, Q., Ye, J.P.: ‘Multi-task learning for spatio-temporal event forecasting’. ACM SIGKDD Conf. on Knowledge Discovery & Data Mining (SIGKDD), Sydney, Australia, 2015, pp. 15031512.
        . ACM SIGKDD Conf. on Knowledge Discovery & Data Mining (SIGKDD) , 1503 - 1512
    20. 20)
      • A.A. Liu , Y.T. Su , W.Z. Nie .
        20. Liu, A.A., Su, Y.T., Nie, W.Z., et al: ‘Hierarchical clustering multi-task learning for joint human action grouping and recognition’, IEEE Trans. Pattern Anal. Mach. Intell., 2017, 39, (1), pp. 102113.
        . IEEE Trans. Pattern Anal. Mach. Intell. , 1 , 102 - 113
    21. 21)
      • C.S. Li , J.C. Yan , F. Wei .
        21. Li, C.S., Yan, J.C., Wei, F., et al: ‘Self-paced multi-task learning’. Proc. 31st AAAI Conf. on Artificial Intelligence (AAAI), San Fransisco, CA, USA, 2017, pp. 21752181.
        . Proc. 31st AAAI Conf. on Artificial Intelligence (AAAI) , 2175 - 2181
    22. 22)
      • H.G. Zhang , J. Zhou .
        22. Zhang, H.G., Zhou, J.: ‘Dynamic multiscale region search algorithm using vitality selection for travelling salesman problem’, Expert Syst. Appl., 2016, 60, pp. 8195.
        . Expert Syst. Appl. , 81 - 95
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-its.2016.0282
Loading

Related content

content/journals/10.1049/iet-its.2016.0282
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address