Paper Authors

Abstract

NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract

Scope of various random number generators in ant system approach for TSP

Abstract

Random numbers are essential ingredients to all stochastic methods including probabilistic heuristic ones. There are several random number generators. Given a method to solve a traveling salesman problem (TSP), which generator should one use to obtain the best result in terms of quality/accuracy and cost/computational complexity? The article attempts to seek an answer to this question when the specified method is the ant algorithm. Nature and characteristics of random numbers, their generators, and TSPs are specially stressed for a better appreciation.

1. Introduction

A given number cannot be just termed random unless we check/test the sequence which it belongs to. This is unlike the transcendental number 3.14159265358 or the algebraic number (1 5) / 2 1.61803398874989 (golden ratio) or the Hilbert number 2 2 2.66514414269023. The word random implies that the predictability (probability of correct prediction) is low and never 100%. As long as there is a finite number of outcomes, the predictability is never zero. In the case of tossing a fair coin, the predictability is 50% while that 2 of rolling a six-faced fair die, it is 16 %. However, an approximate global prediction with high 3 predictability is possible so far as the character of the sequence is concerned. After a large number, say 500, of tosses of a coin, we may say that approximately 250 heads will be obtained. 2 This number could be 245 or 256. By a statistical test, say -test, we may conclude that the coin is fair (unbiased) statistically/probabilistically. These heads and tails or, equivalently, 1s and 0s constitute a uniformly distributed random sequence. If we consider a class of 60 students and note their heights or weights one after the other, it is not possible to predict what the height/weight of the next student would be. These 60 heights or 60 weights are statistically random. But these random heights/weights are not uniformly distributed. We have invariably discovered that such heights/weights are normally distributed. Thus we have random sequences which are exponentially distributed or log normally distributed or distributed in any of the infinite possible ways. Thus the uniform distribution of random numbers is one of infinite possible distribution. Once we have a procedure to produce a uniformly distributed random sequence, we can easily produce a random sequence having any other distribution from this sequence. One may distinguish between global randomness and local randomness although most randomness concepts are global. In a near-infinite random sequence, there could be long sequences (stretches) of the same digit(s), say, 1, the overall sequence might be random though. Long sequences of the same digits, even though generated by a random process would reduce the

• Citation

• Format
  • APA
  • APA - LaTeX bibitem
  • MLA
  • MLA - LaTeX bibitem
  • Bibtex
  • EndNote - RIS

Sen, S., & Shaykhian, G. A. (2007, June), Scope Of Various Random Number Generators In Ant System Approach For Tsp Paper presented at 2007 Annual Conference & Exposition, Honolulu, Hawaii. 10.18260/1-2--1727