Asee peer logo

Scope Of Various Random Number Generators In Ant System Approach For Tsp

Download Paper |

Conference

2007 Annual Conference & Exposition

Location

Honolulu, Hawaii

Publication Date

June 24, 2007

Start Date

June 24, 2007

End Date

June 27, 2007

ISSN

2153-5965

Conference Session

Applied Mathematics

Tagged Division

Mathematics

Page Count

25

Page Numbers

12.1256.1 - 12.1256.25

Permanent URL

https://peer.asee.org/1727

Download Count

57

Request a correction

Paper Authors

author page

S.K. Sen Florida Institute of Technology

author page

Gholam Ali Shaykhian NASA

Download Paper |

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

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. https://peer.asee.org/1727

ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2007 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015