Talk:Ant colony optimization
From Scholarpedia
Contents |
Comments of Reviewer A
Article topics and descriptions are fine but I strongly suggest at least three modifications:
1) Introduce the real ant behavior at the beginning of the document. The natural inspiration at the end is presented with Deneubourg double bridge experiment and the presentation is too mathematical. A simpler explanation is needed at the beginning.
2) In the Main ACO Algorithms chapter I strongly suggest to change the order algorithms are presented. Historically the first is AS, the second Ant-Q and ACS and later on MAX-MIN. Please present first ACS (that is more known than Ant-Q) as an extension of AS showing the difference in the way pheromone is updated, in the way node are selected, and showing that the pheromone level is bounded (at least it never decreases below tau0). It is interesting here to cite Ant-Q, 1995 by the same authors Gambardella, Dorigo. In Ant-Q the pseudo-random-proportional rule and iteration best and global best updating rule where already introduced. Last present MAX-MIN.
3) Say something about convergence proof.
Author's Answers to Reviewer A
1) I do prefer the current presentation structure. The choice of putting the natural inspiration as an appendix was done on purpose. In fact, on one side I want to avoid to over-emphasize the natural inspiration as it is no longer functional to the ACO metaheuristic. On the other hand, I think the natural inspiration is an important aspect that needs to be mentioned. Therefore, the decision to put it as an appendix. I start the entry with the TSP example which is in fact used as a didactic tool. I do not see how moving the natural inspiration to the beginning would make the article simpler.
2) I disagree with this point. The ordering I use is the logical one, which I also use in my book and all the review papers I have published. I am not writing an historical paper, and history can be be found somewhere else (e.g., in my ACO book). I do not mention Ant-Q because, although it was developed before ACS, it is based on wrong assumptions (the connection with reinforcement learning that is at the basis of Ant-Q is in fact wrong). I agree with the referee that iteration best and global best updating rule were introduced in Ant-Q before than in MAX-MIN ant system ad that the idea of a lower bound on the pheromone was present in Ant-Q before than in MAX-MIN ant system. I have added a couple of sentences at the beginning of the Ant Colony System section to clarify this point.
3) Done.
Comments of Reviewer B
This is a standard introduction for ACO novices. I only have very few comments/suggestions:
1) The following sentence might confuse a reader not being familiar with ACO algorithms: "To apply ACO, the optimization problem is transformed into the problem of finding a shortest path on a weighted graph." Specify better what "short" means. In my opinion, this sentence is also a bit misleading (in the sense that it gives the impression that the application of ACO is quite restricted). In fact, the author should point out that ACO can be applied to any problem for which exists a solution construction mechanism.
2) The following sentence is, in my opinion, not completely correct: "Then the construction graph GC(V,E) is defined by associating the components C either with the set of vertices V or with the set of edges E." There are examples of ACO algorithms in the literature that do not fit this description. For example, Blum and Sampels (JMMA, 2004), introduced an ACO algorithm for a general shop scheduling problem in which the pheromone values are neither associated with the nodes nor with the edges of the construction graph.
3) In the 3rd sentence of section "Current trends..." you could make a reference to the work on search bias, and reference the following paper:
C. Blum and M. Dorigo. Search bias in ant colony optimization: On the role of competition-balanced systems. IEEE Transactions on Evolutionary Computation, 9(2):159-174, 2005.
4) In the "current trends" section you also might want to say something about hybridization with other techniques for optimization. An example is Beam-ACO.
C. Blum. Beam-ACO---Hybridizing ant colony optimization with beam search: An application to open shop scheduling. Computers & Operations Research, 32(6):1565-1591, 2005.
Author's Answers to Reviewer B
1) I agree with this comment, which was raised also by Reviewer C. I have substituted, as suggested by Reviewer C, the term "best path" to "shortest path".
2) I have changed "is defined" into "can be defined". Taking into account the way Blum and Sampels define their construction graph would require a much more complicate description, which does not fit the style of this encyclopedic entry.
3 & 4) The section "Applications of ACO and Current Trends" could indeed be much longer and more detailed. However, I have decided to keep it as short as possible and to redirect the reader to the ACO book and to the TCS paper. Citing the two suggested appers would call for additional citation, and there is no clear way to avoid the growth of the encyclopedia entry into a full length overview. Therefore, I think it is better not to add additional references.
Comments of Reviewer C
This is a very nice, informative and easily readable survey. I did not find any errors and have only a few minor comments/suggestions.
1) Second paragraph, "shortest path": I think the restriction to "shortest path" limits the applicability of ACO unnecessarily by presupposing that the objective function value in a construction graph is additive in the "length" values assigned to the edges. I would replace "shortest path" by "best path".
2) Paragraph "The Schedule_Activities": It is a little bit confusing that "solution improvement" (which is a Daemon action) comes here before the update of the pheromones, contrary to the order in the pseudocode. Is it possible to give also a short hint to an example where the Daemon action comes last?
3) Formula for transition probability in AS: The reader may wonder why the reference to component c_ij is not made in an analogous way for tau and for rho, e.g., by writing tau_ij^alpha eta_ij^beta.
4) Sentence "Pheromone evaporation is needed to avoid an overly rapid convergence of the algorithm": I'm not quite sure whether evaporation always slows convergence down (although this may be the more typical case), since there are examples where a large evaporation rate can effect an aggressive hill-climbing. The following sentence "It implements a useful form of forgetting...") is true anyway and gives a good intuition for the effect of evaporation.
5) Subsection on ACS, last paragraph: Perhaps it might be mentioned that it is the more "greedy" pseudorandom proportional rule favoring exploitation as opposed to exploration that makes a counter effect by the (diversifying) local update advisable.
6) To the comments of reviewer A: Personally, I prefer the order chosen by the author where the behavior of real ants is given in an appendix instead of at the beginning, since ACO is an optimization technique and not a biological theory.
Author's Answers to Reviewer C
1) I agree with this comment and implemented the change.
2) I say clearly in the text that the the Schedule_Activities construct does not specify how the three algorithmic components are scheduled and synchronized. However, as an example as requested by the reviewer would have complictaed the explanation, I have decided to invert the order in which the three algorithmic components are listed in the metaheuristic.
3) I agree with this comment and have changed the text accordingly.
4) I agree with this comment and have changed the text accordingly.
5) I agree with this comment and have changed the text accordingly. This required some extensive rearrangements in the subsection dedicated to ACS.
6) I fully agree with the reviewer on this point.
Additional Comments of Reviewer A
You have introduced some changes and now the document gives also an ACO historical overview. However, again in the current version the reader has the feeling that MMAS came before ACS, and that some modifications were first introduced in MAX-MIN and later on in ACS (as for the best trail updating). You also wrote the following sentence:
"Also, although some of the changes to ant system proposed by MMAS and ACS are very similar, the two developments were indipendent".
To better understand this sentence I checked the original MAX-MIN paper available on the Thomas Stützle webpage :
Thomas Stützle and Holger Hoos: Improvements on the Ant System: A detailed Report on MAX-MIN Ant System. Technical Report AIDA-96-12 - Revised version , Darmstadt University of Technology, Computer Science Department, Intellectics Group (gzipped postscript file, 194k).
And I have seen that both Ant-Q and ACS are cited in the references list. So I think your interpretation that the two developments were independent is questionable, since it seems, from the literature, that ACS came before MAX-MIN.
Author's Answers to Additional Comments of Reviewer A
OK, you are right (simply, I was not giving much importance to the chronological aspects). I have checked with Thomas Stützle and he also agrees with your comments. Therefore, I have reorganized a little the Main ACO Algorithms section which now follows the chronolgical order in which algorithms were introduced in the literature. Also, contributions are made more explicit.
