Estimating the Efficient Parameter Values of Different Neighborhood Search Techniques of Simulated Annealing in Forest Spatial Planning Problems

Abstract

The performances of heuristic algorithms are highly dependent on the parameters used, and usually difficult to determine subjectively. Thus, how to balance the relations between the qualities of the solutions and the values of the parameters has been a hot and lasting topic in the field of optimization research. This article presented a statistical method to estimate the efficient parameter values of three alternative neighborhood search techniques of simulated annealing when applied to forest spatial harvest scheduling problems, as an example. The neighborhood search techniques included: the conventional version of simulated annealing (Method1), and the swapping version (Method2) and the changing version (Method3) of 2-element optimization (2-opt) moves. Results indicated that the performances of different neighborhood search strategies highly depended on the problem size, in which the superiorities of Method2 increased from about 10% for smaller cases (400 units) to approximately 80% of larger cases (>3600 units) when compared the objective function values with Method1 and Method3. The efficient parameter values of the cooling rate (CR), the number of iterations per temperature (Ntem), and the number of iterations used for generating initial solution (Nsol) could be estimated using polynomial functions with the number of units, while the initial temperature (IT) should be estimated using exponential function, where the determination coefficient ($R^{2}$ ) of the fitted functions were all larger than 0.60 [except for Nsol and CR of Mehod1 ($R^{2}=0.32$ and 0.42), CR of Method2 ($R^{2}=0.20$ )]. The number of satisfactory solutions all increased linearly ($R^{2} > 0.85$ ) with the number of units, while the solution efficiency decreased linearly ($R^{2} > 0.30$ ). The verifications of two extra grid datasets indicated that the parameter optimization methods were valid.

Keywords

• Simulated annealing
• neighborhood search
• parameter sensitivity
• heuristic algorithm
• tradeoff
• forestry