Hello Researchers,
I am trying to improve the total distance reduction of travelling salesman problem using Simulated annealing. On this particular assignment, professor has given the freedom to modify any/all of the below parameters to improve the accuracy (reducing the travelling distance).
Parameters that could be modified:
1. Temperatures schedule.
2. Duration of thermal equilibrium loop.
3. Choosing of initial route.
4. Perturbation of route.
Any suggestions/references will be helpful. Thanks in advance.
Hi Anand,
first, let me say that, in my opinion, simulated annealing is not so suitable for addressing TSP as well as other combinatorial issues. There are too many control parameters to be set to find a goo balance between diversification and intensification phases. Evolutionary techniques should be more effective. Anyway, before modifying any control parameter on your SA, you should arrange a preliminary sensitivity analysis to test which parameter may have a significant impact on your target.
Good luck!
Hello,
We have done TSP using GA and SA as project in here. however, I agree with @Antonio Costa.
if u welling to use it. just hyper it using hill climbing algorithm so it would find the most optimum parameters vales for SA.
Good luck!
Thank you for your kind responses.
I too join my hands with both of your opinions. Rather dealing with a single path for finding the global optimum is always worse compared to multi-path algorithms like PSO and GA. As I mentioned in my question I am strictly obliged to do the investigation on Simulated annealing because of the instruction from my professor. Moreover it is just an assignment as the part of the ongoing course. Thank you..!!
I agree that simulated annealing might not be the best option to be used for solving the traveling salesman problem. Nevertheless, the question touches a general issue.
There is a good source on paramerterization of simulated annealing:
Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental
evaluation; part I, graph partitioning. Operations Research 37, 865–892 (1989)
We have used that parameterization within our Hotframe software (see Fink, A., Voß, S.: HotFrame: a heuristic optimization framework. In: Voß, S., Woodruff, D.L. (eds.) Optimization Software Class Libraries, pp. 81–154. Kluwer, Boston (2002)) and it turned out to be a good approach.
If simulated annealing is hybridized with other approaches (not only hill climbing as mentioned earlier), then a nice way to do so is by using it within the escape mechanism of reactive tabu search; see4, for instance, the following references:
Voß, S., Fink, A.: Hybridizing reactive tabu search with simulated annealing. Lect. Notes Comput. Sci. 7219, 509–512 (2012)
Voß, S., Fink, A.: A hybridized tabu search approach for the minimum
weight vertex cover problem. Journal of Heuristics 18 (2012) 869–876
DOI 10.1007/s10732-012-9211-9
I have analyzed in deep this question in several optimiation problems, including Graph Partitioning and Vehicle Routing Problems with Time Windows (VRPTW), and I can conclude that SA works well in these problems.
The performance of SA is often influenced by two parameters: (i) initial temperature; (ii) cooling rate. To adjust/calibrate these parameters I recommend to program a population-based version of SA (i.e. a set of solutions that evolve like an evolutionary algorithm), such that each individual/solution uses a different initial temperature and a cooling schedule. This strategy can be improved using parallel processing, as the following reference indicates, but it can be also applied in a serial way.
A clear description of this method for graph partitioning and vehicle routing problems in the single- and multi-objective cases is found in the following links (if you need the PDF of the papers, please send me a request and I will send you them privately).
http://link.springer.com/article/10.1023%2FB%3AHEUR.0000026898.11874.e7
http://www.sciencedirect.com/science/article/pii/S0957417412010664
Regardless of parameters (given a reasonable set), you might use 2-opt or 3-opt moves and search reversion (both alterations to the process, not the parameters) to improve your results. Here's a forestry paper - not traveling salesman, but perhaps of interest... http://www.silvafennica.fi/article/1232/author/3751
Perturbation of route plays a major role in the convergence of solution. Adoption different approaches in perturbation/ neighborhood generation would yield better accuracy in the results.
Dear Anand MP,
I have two papers that applied Simulated Annealing to train Neural Networks.
Hope this would help.
https://www.academia.edu/19921000/Simulated_Annealing_Algorithm_for_Deep_Learning
https://www.academia.edu/11315840/Multiple-view_shape_extraction_from_shading_as_local_regression_by_analytic_NN_scheme
- Badges
- Science topic
- Similar topics
- Social Science
- Media
- Social Media