BOOSTING SIMULATED ANNEALING WITH FITNESS LANDSCAPE PARAMETERS FOR BETTER OPTIMALITY

Authors

  • Sunanda Gupta
  • Sakshi Arora

DOI:

https://doi.org/10.47839/ijc.14.2.807

Keywords:

Optimization, Multi Dimensional Knapsack Problem.

Abstract

Multi Dimensional Knapsack problem is a widely studied NP hard problem requiring extensive processing to achieve optimality. Simulated Annealing (SA) unlike other is capable of providing fast solutions but at the cost of solution quality. This paper focuses on making SA robust in terms of solution quality while assuring faster convergence by incorporating effective fitness landscape parameters. For this it proposes to modify the ‘Acceptance Probability’ function of SA. The fitness landscape evaluation strategies are embedded to Acceptance Probability Function to identify the exploitation and exploration of the search space and analyze the behavior on the performance of SA. The basis of doing so is that SA in the process of reaching optimality ignores the association between the search space and fitness space and focuses only on the comparison of current solution with optimal solution on the basis of temperature settings at that point. The idea is implemented in two different ways i.e. by making use of Fitness Distance Correlation and Auto Correlation functions. The experiments are conducted to evaluate the resulting SA on the range of MKP instances available in the OR library.

References

S. Martello and Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., 1990.

P.C. Chu, and John E. Beasley, A genetic algorithm for the multidimensional knapsack problem, Journal of Heuristics, (4) 1 (1998), pp. 63-86.

S. Gupta, and M.L. Garg, Binary trie coding scheme: an intelligent genetic algorithm avoiding premature convergence, International Journal of Computer Mathematics, (90) 5 (2013), pp. 881-902.

H. Pirkul, A heuristic solution procedure for the multiconstraint zero? one knapsack problem, Naval Research Logistics, (34) 2 (1987), pp. 161-172.

F. Hembecker, H.S. Lopes, and W. Godoy Jr., Particle swarm optimization for the multidimensional knapsack problem, Adaptive and Natural Computing Algorithms, Springer Berlin Heidelberg, 2007, pp. 358-365.

F. Qian, and R. Ding, Simulated annealing for the 0/1 multidimensional knapsack problem, Numerical Mathematics – English Series, (16) 4 (2007), pp. 320.

S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing, Science, (220) 4598 (1983), pp. 671-680.

W.L. Goffe, G.D. Ferrier and J. Rogers, Global optimization of statistical functions with simulated annealing, Journal of Econometrics, (60) 1 (1994), pp. 65-99.

J. Tavares, F. Baptista Pereira and E. Costa, Multidimensional knapsack problem: A fitness landscape analysis, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, (38) 3 (2008), pp. 604-616.

J.E. Beasley, OR-Library: distributing test problems by electronic mail, Journal of the Operational Research Society, (1990), pp. 1069-1072.

S. Uyar and G. Eryiğit, Improvements to penalty-based evolutionary algorithms for the multi-dimensional knapsack problem using a gene-based adaptive mutation approach, in Proceedings of the Conference on Genetic and Evolutionary Computation, (2005), pp. 1257-1264.

Downloads

Published

2015-06-30

How to Cite

Gupta, S., & Arora, S. (2015). BOOSTING SIMULATED ANNEALING WITH FITNESS LANDSCAPE PARAMETERS FOR BETTER OPTIMALITY. International Journal of Computing, 14(2), 107-112. https://doi.org/10.47839/ijc.14.2.807

Issue

Section

Articles