A modified ant colony system for solving the travelling salesman problem with time windows
Chi-Bin Cheng, Chun-Pin Mao
Mathematical and Computer Modelling, accepted 29 November 2006
Table 1Applications of ant colonyoptimization (ACO)
Problem domain / Literature / Algorithm / year
Traveling salesman problem / Colorni et al. [1] / AS / 1991
Dorigo et al. [14] / AS / 1996
Gambardella and Dorigo [15] / Ant-Q / 1995
Dorigo and Gambardella [16] / ACS / 1997
Bullnheimer et al. [17] / ASrank / 1999
St¨utzle and Hoos [18] / MMAS / 2000
Quadratic assignment problem / Gambardella et al. [3] / AS-QAP / 1999
Maniezzo [4] / ANTS-QAP / 1999
St¨utzle and Hoos [18] / MMAS-QAP / 2000
Talbi et al. [19] / Parallel Ant Colonies / 2001
Solimanpur et al. [20] / ACO / 2004
Scheduling / Colorni et al. [9] / AS-JSP / 1994
St¨utzle [21] / AS-FSP / 1998
McMullen [10] / ACO / 2001
T’kindt et al. [11] / ACO / 2002
Gravel et al. [12] / ACO / 2002
Ying and Liao [13] / ACS / 2004
Shyu et al. [22] / ACO / 2004
Blum [23] / Beam-ACO / 2005
Vehicle routing problem / Bullnheimer et al. [5] / AS-VRP / 1999
Gambardella et al. [24] / MACS-VRPTW / 1999
Bell and McMullen [25] / ACO / 2004
Network routing / Schoonderwoerd et al. [7] / ABC / 1996
Di Caro and Dorigo [8] / AntNet / 1998
Sequential ordering / Gambardella and Dorigo [26] / HAS-SOP / 2000
Graph colouring / Costa and Hertz [6] / ANTCOL / 1997
Constraint satisfaction / Solnon [27] / Ant-P-solver / 2000
Classification / Shelokar et al. [28] / ACO classifier system / 2004
Clustering / Shelokar et al. [29] / ACO / 2004
Kuo et al. [30] / Ant k-means / 2005
Yang and Kamel [31] / Multi-ant colonies / 2006
References
[1] A. Colorni, M. Dorigo, V. Maniezzo, Distributed optimization by ant colonies, in: Proceedings of ECAL91 — European Conference on Artificial Life, Paris, France, 1991, pp. 134–142.
[2] W. Gutjahr, A graph-based ant system and its convergence, Future Generation Computer Systems 16 (2000) 873–888.
[3] L.M. Gambardella, E. Taillard, M. Dorigo, Ant colonies for the quadratic assignment problem, Journal of Operational Research Society 50 (1999) 167–176.
[4] V. Maniezzo, A. Colorni, The ant system applied to the quadratic assignment problem, IEEE Transactions on Knowledge and Data Engineering 11 (1999) 769–784.
[5] B. Bullnheimer, R.F. Hartl, C. Strauss, An improved ant system algorithm for the vehicle routing problem, Annals of Operations Research 89 (1999) 319–334.
[6] D. Costa, A. Hertz, Ants can colour graphs, Journal of Operational Research Society 48 (1997) 295–305.
[7] R. Schoonderwoerd, O. Holland, J. Bruten, L. Rothkrantz, Ant-based load balancing in telecommunications networks, Adaptive Behavior (1997) 169–207.
[8] G. Di Caro, M. Dorigo, AntNet: Distributed stigmergetic control for communications networks, Journal of Artificial Intelligence Research 9
(1998) 317–365.
[9] A. Colorni, M. Dorigo, V. Maniezzo, M. Trubian, Ant system for job-shop scheduling, Belgian Journal of Operations Research 34 (1994)
39–53.
[10] P.R. McMullen, An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives, Artificial Intelligence
in Engineering 15 (2001) 309–317.
[11] V. T’kindt, N. Monmarche, F. Tercinet, D. Laugt, An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling
problem, European Journal of Operational Research 142 (2002) 250–257.
[12] M. Gravel, W.L. Price, C. Gagne, Scheduling continuous casting of aluminum using a multiple objective ant colony optimization
metaheuristic, European Journal of Operational Research 143 (2002) 218–229.
[13] K.-C. Ying, C.-J. Liao, An ant colony system for permutation flow-shop sequencing, Computers and Operations Research 31 (2004) 791–801.
[14] M. Dorigo, V. Maniezzo, A. Colorni, The ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man
and Cybernetics 26 (1996) 29–41.
[15] L.M. Gambardella, M. Dorigo, Ant-Q: A reinforcement learning approach to the traveling salesman problem, in: Proceedings of the 12th
International Conference on Machine Learning, ML-95, Tahoe City, CA, 9–12 July 1995, pp. 252–260.
[16] M. Dorigo, L.M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on
Evolutionary Computation 1 (1) (1997) 53–66.
[17] B. Bullnheimer, R.F. Hartl, C. Strauss, A new rank-based version of the ant system: A computational study, Central European Journal for
Operations Research and Economics 7 (1) (1999) 25–38.
[18] T. St¨utzle, H.H. Hoos, MAX–MIN ant system, Future Generation Computer Systems 16 (8) (2000) 889–914.
[19] E.-G. Talbi, O. Roux, C. Fonlupt, D. Robillard, Parallel ant colonies for the quadratic assignment problem, Future Generation Computer
Systems 17 (2001) 441–449.
[20] M. Solimanpur, P. Vrat, R. Shankar, Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing, European
Journal of Operational Research 157 (2004) 592–606.
[21] T. St¨utzle, An ant approach to the flow shop problem, in: Proceedings of the 6th European Congress on Intelligent Techniques & Soft
Computing, EUFIT’98, Aachen, Germany, 7–10 September 1998, pp. 1560–1564.
[22] S.J. Shyu, B.M.T. Lin, P.Y. Lin, Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total
completion time, Computers and Industrial Engineering 47 (2004) 181–193.
[23] C. Blum, Beam-ACO — Hybridizing ant colony optimization with beam search: An application to open shop scheduling, Computers and
Operations Research 32 (6) (2005) 1565–1591.
[24] L.M. Gambardella, ´ E.D. Taillard, G. Agazzi, MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows,
in: D. Corne, M. Dorigo, F. Glover (Eds.), New Ideas in Optimization, McGraw Hill, London, UK, 1999, pp. 63–76.
[25] J.E. Bell, P.R. McMullen, Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics 18 (2004)
41–48.
[26] L.M. Gambardella, M. Dorigo, Ant colony system hybridized with a new local search for the sequential ordering problem, INFORMS Journal
on Computing 13 (3) (2000) 237–255.
[27] C. Solnon, Solving permutation constraint satisfaction problems with artificial ants, in: Proceedings of the 14th European Conference on
Artificial Intelligence, Berlin, Germany, 20–25 August 2000, pp. 118–122.
[28] P.S. Shelokar, V.K. Jayaraman, B.D. Kulkarni, An ant colony classifier system: Application to some process engineering problems, Computer
and Chemical Engineering 28 (2004) 1577–1584.
[29] P.S. Shelokar, V.K. Jayaraman, B.D. Kulkarni, An ant colony approach for clustering, Analytica Chimica ACTA 509 (2004) 187–195.
[30] R.J. Kuo, H.S.Wang, T.-L. Hu, S.H. Chou, Application of ant k-means on clustering analysis, Computers and Mathematics with Applications
50 (2005) 1709–1724.
[31] Y. Yang, M.S. Kamel, An aggregated clustering approach using multi-ant colonies algorithms, Pattern Recognition 39 (2006) 1278–1289.
[32] M. Dorigo, G. Di Caro, L.M. Gambardella, Ant algorithms for discrete optimization, Artificial Life 5 (1999) 137–172.
[33] M. Gendreau, A. Hertz, G. Laporte, M. Stan, A generalized insertion heuristic for the traveling salesman problem with time windows,
Operations Research 43 (3) (1998) 330–335.
[34] M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time windows constraints, Operations Research 35 (2)
(1987) 254–265.
[35] D.J. Rosenkrantz, R.E. Stearns, P.M. Lewis, An analysis of several heuristics for the traveling salesman problem, SIAM Journal on Computing
6 (1977) 563–581.
[36] J.-Y. Potvin, S. Bengio, The vehicle routing problem with time windows—Part II: Genetic search, INFORMS Journal on Computing 8 (1996)
165–172.
A hybrid approach for feature subset selection using neural networks and ant colony optimization
Rahul Karthik Sivagaminathan, Sreeram Ramakrishnan
Expert Systems with Applications 33 (2007) 49–60
يافتن زيرمجموعه بهينه اي ازويژگيها يك مساله NP-hard است. براي تعداد زيادي ويژگي، ارزيابي همه وضعيتها از لحاظ محاسباتي ممكن نيست بنابراين به روشهاي جستجوي اكتشافي مثل روشهاي نمايي، ترتيبي و تصادفي نياز است. روش نمايي شامل روشهايي مثل شاخه و قيد است كه از يك مجموعه كامل شروع كرده و با استفاده از استراتژي اول عمق،ويژگيها را حذف مي كند. روش ديگر در اين مقوله، جستجوي پرتوي است كه در آن ويژگيها براساس كيفيت به طور نزولي در صف قرار مي گيرند. جستجوي پرتوي در هر مرحله تمام وضعيتهاي ممكن حاصل از افزودن يك زيرمجموعه از ويژگيها را ارزيابي مي كند.
الگوريتم هاي جستجوي ترتيبي[1] (SSA) كه روشهاي مرحله اي هم ناميده مي شوند، پيچيدگي نسبتا كمتري دارند و از استراتژي تپه نوردي براي يافتن راه حل بهينه بهره مي برند. به دليل نقاط شروع مختلف، SSA به دو دسته انتخاب پيشروي ترتيبي[2] با شروع از يك مجموعه تهي و انتخاب پسروي ترتيبي[3] با شروع از مجموعه كامل ويژگيها تقسيم مي شود. به طور كلي روشهاي فرااكتشافي به عنوان روشهاي جستجوي تصادفي شناخته مي شوند.
ACO اولين بار براي مسايل TSP و QAP مطرح شد. بعدها محققين آن را براي مسايل بهينه سازي گسسته زيادي به كار بردند. اين فرااكتشاف براي مسايل NP-hard مختلف مانند بهينه سازي تركيبي ايستا/پويا به كار برده شد. مسايل بهينه سازي تركيبي گسسته شامل
Job shop scheduling (Blum & Sampels, 2002; Colorine, Dorigo, & Maniezzo, 1994)
flow shop scheduling (Stu¨ tzle, 1998)
open shop scheduling (Blum, 2003)
group shop scheduling (Sampels, Blum, Mastrolilli, & Rossi-Doria, 2002)
vehicle routing problem (Bullnheimer, Hartl, & Strauss, 1998)
sequential ordering (Gambardilla & Dorigo,1997)
graph coloring (Costa & Hentz, 1997)
shortest common super sequences (Micheal & Middendorf,1999)
مسايل بهينه سازي تركيبي پويا شامل مسيريابي در شبكه هاي اتصال گرا (Schoonderwoerd, Holland, Bruten, & Rothkrantz ,1996) و بدون اتصال (Sim & Sun, 2001) است.
ReferencesAlmuallim, H., & Dietterich, T. G. (1991). Learning with many irrelevant features. In Proceedings of the ninth national conference on artificial intelligence (AAAI-91) (Vol. 2, pp. 547–552). Anaheim, CA: AAAI Press.
Ani, A. Al. (in press). An ant algorithm based approach for feature subset selection. In International Conference on Artificial Intelligence and Machine Learning.
Ani, A. Al. (2005). Feature subset selection using ant colony optimization. International Journal of Computational Intelligence, 2(1), 53–58.
Blum, C. (2003). An ant-colony optimization algorithm to tackle shop scheduling problems. Tech. report, TR/IRDIA/ 2003-01, IRDIA, Universite’ Libre de Bruxelles, Belgium.
Blum, A. L., & Langley, P. (1997). Selection of relevant features and examples in machine learning. Artificial Intelligence, 245–271.
Blum, C., & Sampels, M. (2002). Ant colony optimization for fop shop scheduling: A case study on different pheromone representations. In Proceedings of the 2002 congress on evolutionary computing (CEC’02) (pp. 1558). New York: IEEE Press.
Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). From nature to artificial swarm intelligence. New York: Oxford University Press.
Boz, O. (2002). Feature subset selection using sorted feature relevance. In The proceedings of ICMLA, international conference of machine learning and applications, Los Angeles, USA (pp. 147–153).
Bullnheimer, B., Hartl, R. F., & Strauss, G. (1998). Applying the ant system for the vehicle routing problem. In Meta-heuristics: Advances and trends in local search paradigms for optimizations(pp. 109–120).
Cardie, C. (1993). Using decision trees to improve case-based learning. In Proceedings of the tenth international conference on machine learning (pp. 25–32). Los Altos, CA: Morgan Kaufmann Publishers.
Caruana, R., & Freitag, D. (1994). Greedy attribute selection. In Proceedings of the eleventh international conference on machine learning (pp. 180–189). Los Altos, CA: Morgan Kaufmann Publishers.
Colorine, A., Dorigo, M., &Maniezzo, V. (1994). Ant system for job shop scheduling. Belgium Journal of Operations Research, Statistics and Computer Science (JORBEL), 34, 39–53.
Corne, D., Dorigo, M., & Glover, F. (1999). New ideas in optimization. Maidenhead: McGraw Hill.
Costa, D., & Hentz, A. (1997). Ants can color graph. Journal of the Operational Research Society, 48, 295–305.
Debuse, J. C. W., &Smith, V. J. R. (1997). Feature subset selection within a simulated annealing data mining algorithm. Journal of Intelligent Information Systems, 9, 57–81.
Desai, R., Lin, F. C., & Desai, G. R. (2001). Medical diagnosis with a Kohonen LVQ2 neural network. In Proceedings of the 8th interna- tional conference on neural information processing, Cd-ROM, Shanghai.
Devijver, P. A., & Kittler, J. (1982). Pattern recognition: A statistical approach. Englewood Cliffs, NJ: Prentice Hall International.
Doak, J. (1992). Intrusion detection: The application offeature selection – A comparison of algorithms, and the application of a wide area network analyzer. Master’s thesis, Department of Computer Science, University of California, Davis.
Dorigo, M., Caro, G. D., &Gambardella, L. M. (1999). Ant algorithm for discrete optimization. Artificial Life, 5(2), 137–172.
Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transaction on Evolutionary Computation, 1(1), 53–66.
Gambardilla, L. M., & Dorigo, M. (1997). HAS-SOP: An hybrid ant system for the sequential ordering problem. Tech. report 11-97, Lugano, Switzerland: IDSIA.
Gorunescu, F., Gorunescu, M., Darzi, E. El., & Gorunescu, S. (2005). An evolutionary computational approach to probabilistic neural network with application to hepatic cancer diagnosis. In 18th IEEE symposium on computer-based medical systems (CBMS-05) (pp. 461–466).
Jensen, R., & Shen, Q. (2003). Finding rough set reducts with ant colony
optimization. In Proceedings of the 2003 UK workshop on computa-
tional intelligence (pp. 15–22).
John, G., Kohavi, R., & Pfleger, K. (1994). Irrelevant features and the
subset selection problem. In Machine learning: Proceedings of the
eleventh international conference (pp. 121–129). Los Altos, CA:
Morgan Kaufmann Publishers.
Kira, K., & Rendell, L. A. (1992). The feature selection problem:
Traditional methods and a new algorithm. In Proceedings of the 10th
national conference on artificial intelligence (pp. 129–134). San Jose,
CA: MIT Press.
Kulkarni, R. S., Lugosi, G., & Santosh, V. S. (1998). Learning pattern
classification – A survey. IEEE Transaction on Information Theory,
44(6), 2178–2206.
Kulkarni, R. S., & Vidyasagar, M. (1997). Learning decision rules for
pattern classification under a family of probability measures. IEEE
Transactions on Information Theory, 43(1), 154–166.
Lanzarini, L., & Giusti, D. A. (2000). Pattern recognition in medical
images using neural networks. IEEE Transaction on Image and Signal
Processing Analysis.
Leardi, R., Boggia, R., & Terrile, M. (1992). Genetic algorithms as a
strategy for feature selection. Journal of Chemo-metrics, 6, 267–281.
Merz, C. J., &Murphy, P. M. (1996). UCI Repository of machine learning
databases. Irvine, CA: Department of Information and Computer
Science, University of California. Available from http://www.ics.u-
ci.edu/~mlearn/MLRepository.html.
Micheal, R., & Middendorf, M. (1999). An ACO algorithm for the
shortest common super sequence problem. New ideas in optimization.
Maidenhead: McGraw Hill.
Narendra, P., & Fukunaga, K. (1977). A branch and bound algorithm for
feature subset se lection. IEEE Transactions on Computing, 77(26),
917–922.
Pudil, P., Novovicova, J., & Kittler, J. (1994). Floating search methods in
feature selection. Pattern Recognition Letters Archive, 15(11),
1119–1125.
Punch, W. F., Goodman, E. D., Pei, M., Chia-shun, L., Hovland, P., &
Enbody, R. (1993). Further research on feature selection and classi-
fication using genetic algorithms. In The proceedings of 5th interna-
tional conference on genetic algorithm (pp. 557–564).
Ripley, B. D., & Hjort, N. L. (1996). Pattern recognition and neural
networks. New York: Cambridge University Press.
Sampels, M., Blum, C., Mastrolilli, M., & Rossi-Doria, O. (2002).
Metaheuristics for group shop scheduling. In The proceedings of
seventh international conference on parallel problem solving from nature,
PPSN-VII. Lecture notes in computer science, Berlin, Germany (Vol.
2439, pp. 631–640).
Schoonderwoerd, R., Holland, O., Bruten, J., & Rothkrantz, L. (1996).
Ant-based load balancing in telecommunications networks. Adaptive
Behavior, 5(2), 169–207.
Schreyer, M., & Raidl, G. R. (2002). Letting ants labeling point features.
In Proceedings of the 2002 IEEE congress on evolutionary computation
at the IEEE world congress on computational intelligence (pp. 1564–
1569).
(2002-11) State of the Ant - Overview of ANTS2002 (SIT Seminar 20-11-2002):