Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 11 of 11
Full-Text Articles in Physical Sciences and Mathematics
Unsupervised Algorithms For Learning Emergent Spatio-Temporal Correlations, Chaitanya Tumuluri
Unsupervised Algorithms For Learning Emergent Spatio-Temporal Correlations, Chaitanya Tumuluri
Electrical Engineering and Computer Science - Technical Reports
Many applications require the extraction of spatiotemporal correlations among dynamically emergent features of non-stationary distributions. In such applications it is not possible to obtain an a priori analytical characterization of the emergent distribution. This paper extends the Growing Cell Structures (GCS) network and presents two novel (GIST and GEST) networks, which combine unsupervised feature-extraction and Hebbian learning, for tracking such emergent correlations. The networks were successfully tested on the challenging Data Mapping problem, using an execution driven simulation of their implementation in hardware. The results of the simulations show the successful use of the GIST and GEST networks for extracting …
Knowledge-Based Nonuniform Crossover, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Knowledge-Based Nonuniform Crossover, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
Electrical Engineering and Computer Science - Technical Reports
We present a new "knowledge-based non-uniform crossover" (KNUX) operator for genetic algorithms (GA's) that generalizes uniform crossover. We extend this to "Dynamic KNUX" (DKNUX), which constantly updates the knowledge extracted so far from the environment's feedback on previously generated chromosomes. KNUX can improve on good solutions previously obtained by using other algorithms. The modifications made by KNUX are orthogonal to other changes in parameters of GA's, and can be pursued together with any other proposed improvements. Whereas most genetic search methods focus on improving the move-selection procedures, after having chosen a fixed move-generation mechanism, KNUX and DKNUX make the move-generation …
Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira
Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira
Electrical Engineering and Computer Science - Technical Reports
ln this paper we present Genetic Algorithms - evolutionary algorithms based on an analogy with natural selection and survival of the fittest - applied to an NP Complete combinatorial optimization problem: minimizing the makespan of a Stochastic Flow Shop No Wait (FSNW) schedule. This is an important optimization criteria in real-world situations and the problem itself is of practical significance. We restrict our applications to the three machine flow shop no wait problem which is known to be NP complete. The stochastic hypothesis is that the processing times of jobs are described by normally distributed random variables. We discuss how …
Numerical Solution Of Laplace's Equation, Per Brinch Hansen
Numerical Solution Of Laplace's Equation, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial discusses Laplace's equation for steady state heat flow in a two-dimensional region with fixed temperatures on the boundaries. The equilibrium temperatures are computed for a square grid using successive overrelaxation with parity ordering of the grid elements. The numerical method is illustrated by a Pascal algorithm. We assume that the reader is familiar with elementary calculus.
Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen
Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.
Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen
Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.
Simulated Annealing, Per Brinch Hansen
Simulated Annealing, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial describes simulated annealing, an optimization method based on the principles of statistical mechanics. Simulated annealing finds near-optimal solutions to optimization problems that cannot be solved exactly because they are NP-complete. The method is illustrated by a Pascal algorithm for the traveling salesperson problem. The performance of the algorithm was measured on a Computing Surface.
Primality Testing, Per Brinch Hansen
Primality Testing, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial describes the Miller-Rabin method for testing the primality of large integers. The method is illustrated by a Pascal algorithm. The performance of the algorithm was measured on a Computing Surface.
Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann
Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann
Electrical Engineering and Computer Science - Technical Reports
In this report we present a class of efficient maximum-likelihood soft-decision decoding algorithms for linear block codes. The approach used here is to convert the decoding problem into a search problem through a graph which is a trellis for an equivalent code of the transmitted code. Algorithm A*, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to drastically reduce the search …
A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang
A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang
Electrical Engineering and Computer Science - Technical Reports
This paper presents a simple load balancing algorithm and its probabilistic analysis. Unlike most of the previous load balancing algorithms, this algorithm maintains locality. We show that the cost of this load balancing algorithm is small for practical situations and discuss some interesting applications for data remapping.
The Fast Fourier Transform, Per Brinch Hansen
The Fast Fourier Transform, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial discusses the fast Fourier transform, which has numerous applications in signal and image processing. The FFT computes the frequency components of a signal that has been sampled at n points in O( n log n) time. We explain the FFT and illustrate it by examples and Pascal algorithms. We assume that you are familiar with elementary calculus.