5226759
Genetic Parallel Programming: Design and Implementation
This paper presents a novel Genetic Parallel Programming (GPP) paradigm for evolving parallel programs running on a Multi-Arithmetic-Logic-Unit (Multi-ALU) Processor (MAP). The MAP is a Multiple Instruction-streams, Multiple Data-streams (MIMD), general-purpose register machine that can be implemented on modern Very Large-Scale Integrated Circuits (VLSIs) in order to evaluate genetic programs at high speed. For human programmers, writing parallel programs is more difficult than writing sequential programs. However, experimental results show that GPP evolves parallel programs with less computational effort than that of their sequential counterparts. It creates a new approach to evolving a feasible problem solution in parallel program form and then serializes it into a sequential programif required. The effectiveness and efficiency of GPP are investigated using a suite of 14 well-studied benchmark problems. Experimental results show that GPP speeds up evolution substantially.
6017611
Balancing Samples' Contributions on GA Learning
A main branch in Evolutionary Computation is learning a system directly from input/output samples without investigating thternal behaviors of the system. Input/output samples captured from a real system are usually incomplete, biased and noisy. In order to evolve a precise system, the sample set should include a complete set of samples. Thus, a large number of samples should be used. Fitness functions being used in Evohitionary Algorithms usually based on the matched ratio of samples. Unfortunately, some of these samples may be exactly or semantically duplicated. These duplicated samples cannot be identified simply because we do not know the internal behavior of the system being evolved. This paper proposes a method to overcome this problem by using a dynamic fitness function that incorporates the contribution of each sample in the evolutionary process. Experiments on evolving Finite State Machines with Genetic Algorithms are presented to demonstrate the effect on improving the successful rate and convergent speed of the proposed method.
11001415
Automatic refinement of knowledge bases with fuzzy rules
Abstract The knowledge-acquisition bottleneck obstructs the development of expert systems. Refinement of existing knowledge bases is a subproblem of the knowledge-acquisition problem. The paper presents a HEuristic REfinement System (HERES), which refines rules with mixed fuzzy and nonfuzzy concepts represented in a variant of the rule representation language Z-II automatically. HERES employs heuristics and analytical methods to guide its generation of plausible refinements. The functionality and effectiveness of HERES are verified through various case studies. It has been verified that HERES can successfully refine knowledge bases. The refinement methods can handle imprecise and uncertain examples and generate approximate rules. In this aspect, they are better than other famous learning algorithms such as ID3 15–18 , AQ11, and INDUCE 14, 19, 20 because HERES' methods are currently unique in processing inexact examples and creating approximate rules.
17795196
Scalable model-based clustering by working on data summaries
The scalability problem in data mining involves the development of methods for handling large databases with limited computational resources. We present a two-phase scalable model-based clustering framework: first, a large data set is summed up into subclusters; Then, clusters are directly generated from the summary statistics of subclusters by a specifically designed expectation-maximization (EM) algorithm. Taking example for Gaussian mixture models, we establish a provably convergent EM algorithm, EMADS, which embodies cardinality, mean, and covariance information of each subcluster explicitly. Combining with different data summarization procedures, EMADS is used to construct two clustering systems: gEMADS and bEMADS. The experimental results demonstrate that they run several orders of magnitude faster than the classic EM algorithm with little loss of accuracy. They generate significantly better results than other model-based clustering systems using similar computational resources.
18141920
Learning functional dependency networks based on genetic programming
Bayesian Network (BN) is a powerful network model, which represents a set of variables in the domain and provides the probabilistic relationships among them. But BN can handle discrete values only; it cannot handle continuous, interval and ordinal ones, which must be converted to discrete values and the order information is lost. Thus, BN tends to have higher network complexity and lower understandability. In this paper, we present a novel dependency network which can handle discrete, continuous, interval and ordinal values through functions; it has lower network complexity and stronger expressive power; it can represent any kind of relationships; and it can incorporate a-priori knowledge though user-defined functions. We also propose a novel Genetic Programming (GP) to learn dependency networks. The novel GP does not use any knowledge-guided nor application-oriented operator, thus it is robust and easy to replicate. The experimental results demonstrate that the novel GP can successfully discover the target novel dependency networks, which have the highest accuracy and the lowest network complexity.
18293423
Using Evolutionary Programming and Minimum Description Length Principle for Data Mining of Bayesian Networks
We have developed a new approach to learning Bayesian network structures based on the minimum description length (MDL) principle and evolutionary programming. It employs a MDL metric, which is founded on information theory, and integrates a knowledge-guided genetic operator for the optimization in the search process.
588086
Calculating normalization constants of closed queueing networks by numerically inverting their generating functions
A new algorithm is developed for calculating normalization constants (partition functions) and moments of product-form steady-state distributions of closed queuing networks and related models. The essential idea is to numerically invert the generating function of the normalization constant and related generating functions appearing in expressions for the moments. It is known that the generating function of the normalization constant often has a remarkably simple form, but numerical inversion evidently has not been considered before. For p-dimensional transforms, as occur with queuing networks having p closed chains, the algorithm recursively performs p one-dimensional inversions. The required computation grows exponentially in the dimension, but the dimension can often be reduced by exploiting conditional decomposition based on special structure. For large populations, the inversion algorithm is made more efficient by computing large sums using Euler summation. The inversion algorithm also has a very low storage requirement. A key ingredient in the inversion algorithm is scaling. An effective static scaling is developed for multichain closed queuing networks with only single-server and (optionally) infinite-server queues. An important feature of the inversion algorithm is a self-contained accuracy check, which allows the results to be verified in the absence of alternative algorithms.
34460188
Incorporating proxy services into wide area cellular IP networks
Performance enhancing proxies have drawn considerable interests from the network community as an effective approach to improve user experience in cellular networks. Previous research on this subject has been focusing on the design of proxy servers as well as the functions that these servers provide. In this paper, we study the placement of proxy servers, especially the approach of incorporating proxies into cellular networks, which allows better, faster, and more secure proxy services. We discuss various factors that must be considered when placing proxies inside cellular networks, including the information requirements of the proxies, the network requirements for supporting the proxy functions, and mobility management. Using GPRS as an example, we lay out a procedure for adding proxies into data transmission paths in cellular networks. Copyright © 2001 John Wiley & Sons, Ltd.
2298581
Global Mobility Management by Replicated Databases in Personal Communication Networks
This paper explores the use of replicated databases for management of customer data (e.g., mobility data, call routing logic) in global, intelligent, and wireless networks. We propose and analyze two, full and partial, data replication schemes-which are compatible with industry protocol standards-and compare them with the traditional, centralized database scheme. By identifying a set of key teletraffic and mobility parameters, we develop a modeling framework based on queueing models and apply it to assess the relative performance and merits of these schemes. The paper also addresses some implementation issues. Numerical results reveal that the full replication scheme outperforms the centralized one over a wide range of the parameters considered in this study. Furthermore, if some customer data-such as location data for highly mobile customers in wireless networks-change frequently, and if each call launches multiple queries into the databases, the partial replication scheme offers further performance improvement. In general, however, the choice of the database design would depend on the specific characteristics of the service and user behavior under consideration.
15996223
A low-voltage CMOS low-dropout regulator with enhanced loop response
A 1.5-V 100-mA CMOS low-dropout regulator with a double pole-zero cancellation scheme and a linearly operated power PMOS transistor at dropout to enhance the loop-gain response, is presented. The circuit realization is well-studied and developed with respect to the loop-gain response, the transient response, the output noise and the output accuracy, as well as the standby power consumption. Implemented in a 0.6 /spl mu/m CMOS process, experimental results show that the regulator provides a full load transient response of less than 1-/spl mu/s settling time and less than 50-mV overshoots and undershoots. Moreover, it provides a ripple rejection of better than -26 dB and an output noise of 0.07 /spl mu/V/sqrt Hz at 100 kHz.
39521573
An inversion algorithm for loss networks with state-dependent rates
We extend our recently developed algorithm for computing (exact) steady-state blocking probabilities for each class in product-form loss networks to cover general state-dependent arrival and service rates. This generalization allows us to consider, for the first time, a wide variety of buffered and unbuffered resource-sharing models with non-Poisson traffic as may arise with overflows in the context of alternative routing. As before, we consider non-complete-sharing policies involving upper-limit and guaranteed-minimum bounds for the different classes, but here we consider both bounds simultaneously. Major features of the algorithm are: dimension reduction by conditional decomposition based on special structure, an effective scaling algorithm to control errors in the inversion, the efficient treatments of multiple classes with identical parameters and the truncation of large sums.