Ant routing is a method for network routing in agent technology. Although its effectiveness and efficiency have been demonstrated and reported in the literature, its properties have not yet been well studied. This paper presents some preliminary analysis on an ant algorithm in regard to its population growing property and jumping behavior. Results conclude that as long as the value max, {i/spl Omega//sub j/|} is known, the practitioner is able to design the algorithm parameters, such as the number of agents being created for each request, k, and the maximum allowable number of jumps of an agent, in order to meet the network constraint.

Experimental results show that a word-based arithmetic coding scheme can achieve a higher compression performance for Chinese text. However, an arithmetic coding scheme is a fractional-bit compression algorithm which is known to be time consuming. In this article, we change the direction to study how to cascade the word segmentation model with a faster alternative, the integral-bit compression algorithm. It is shown that the cascaded algorithm is more suitable for practical usage. Among several word-based integral-bit compression algorithms, WLZSSHUF achieves the best compression results. Not only can it achieve a comparable compression ratio with a PPM compressor, COMP-2, it demonstrates a faster compression and decompression speed. In the last part of this article, the relation between the accuracy of the word segmentation model (match ratio) and the performance of the compression algorithm (compression ratio) are analyzed. By varying the match ratio, it was discovered that the growth rate of the compression ratio is content-dependent and close to linear. The results of our study will help the practitioners of information retrieval to design word-based compression algorithms for Chinese. This is particularly useful to multilingual digital libraries in which a massive volume of data is often involved.

Pruning a neural network to a reasonable smaller size, and if possible to give a better generalization, has long been investigated. Conventionally the common technique of pruning is based on considering error sensitivity measure, and the nature of the problem being solved is usually stationary. In this article, we present an adaptive pruning algorithm for use in a nonstationary environment. The idea relies on the use of the extended Kalman filter (EKF) training method. Since EKF is a recursive Bayesian algorithm, we define a weight-importance measure in term of the sensitivity of a posteriori probability. Making use of this new measure and the adaptive nature of EKF, we devise an adaptive pruning algorithm called adaptive Bayesian pruning. Simulation results indicate that in a noisy nonstationary environment, the proposed pruning algorithm is able to remove network redundancy adaptively and yet preserve the same generalization ability.

In this paper, the regularization of employing the forgetting recursive least square (FRLS) training technique on feedforward neural networks is studied. We derive our result from the corresponding equations for the expected prediction error and the expected training error. By comparing these error equations with other equations obtained previously from the weight decay method, we have found that the FRLS technique has an effect which is identical to that of using the simple weight decay method. This new finding suggests that the FRLS technique is another on-line approach for the realization of the weight decay effect. Besides, we have shown that, under certain conditions, both the model complexity and the expected prediction error of the model being trained by the FRLS technique are better than the one trained by the standard RLS method.

Recently we have proposed a simple circuit of winner-take-all (WTA) neural network. Assuming no external input, we have derived an analytic equation for its network response time. In this paper, we further analyze the network response time for a class of winner-take-all circuits involving self-decay and show that the network response time of such a class of WTA is the same as that of the simple WTA model.

In the use of extended Kalman filter approach in training and pruning a feedforward neural network, one usually encounters the problems on how to set the initial condition and how to use the result obtained to prune a neural network. In this paper, some cues on the setting of the initial condition will be presented with a simple example illustrated. Then based on three assumptions--1) the size of training set is large enough; 2) the training is able to converge; and 3) the trained network model is close to the actual one, an elegant equation linking the error sensitivity measure (the saliency) and the result obtained via extended Kalman filter is devised. The validity of the devised equation is then testified by a simulated example.

No abstract available.

Pruning is one of the effective techniques for improving the generalization error of neural networks. Existing pruning techniques are derived mainly from the viewpoint of energy minimization, which is commonly used in gradient-based learning methods. In recurrent networks, extended Kalman filter (EKF)-based training has been shown to be superior to gradient-based learning methods in terms of speed. This article explains a pruning procedure for recurrent neural networks using EKF training. The sensitivity of a posterior probability is used as a measure of the importance of a weight instead of error sensitivity since posterior probability density is readily obtained from this training method. The pruning procedure is tested using three problems: (1) the prediction of a simple linear time series, (2) the identification of a nonlinear system, and (3) the prediction of an exchange-rate time series. Simulation results demonstrate that the proposed pruning method is able to reduce the number of parameters and improve the generalization ability of a recurrent network.

Whether it is possible to have an optimal online algorithm for unidirectional ring, out-tree, in-tree, bidirectional tree, and bidirectional ring networks is discussed. The problem is considered under various restrictions of four parameters-origin node, destination node, release time and deadline. For unidirectional ring, it is shown that no such algorithm can exist unless one of the four parameters is fixed. For out-tree, it is shown that no such algorithm can exist unless one of three parameters-origin node, destination node and release time-is fixed. For in-tree, it is shown that no such algorithm can exist unless one of three parameters-origin node, destination node and deadline-is fixed. For bidirectional tree, it is shown that no such algorithm can exist unless the origin node or the destination node is fixed. For bidirectional ring, it is shown that no such algorithm can exist unless the origin node and either the destination node or the release time are fixed.>

The problem of minimizing the total tardiness for a set of unit-processing-time jobs on a single machine is considered. J. K. Lenstra and A. H. G. Rinnooy Kan have shown that the problem is NP-hard if the jobs have arbitrary precedence constraints. They asked whether the problem remains NP-hard for tree-structured precedence constraints. In this paper we show that the problem is NP-hard even for a set of chains. Our result gives a sharp boundary for the complexity of this problem, since there is a simple, polynomial-time algorithm for a set of independent jobs. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The problem of scheduling n independent tasks on $m \geqq 1$ identical processors, with the objective of minimizing the schedule length under the constraint that it must have minimum flow time, is considered. For nonpreemptive scheduling, it is known that the problem is NP-hard. This paper shows that the problem is a lot easier for preemptive scheduling. Specifically, an $O(n\log n)$ time algorithm to find an optimal preemptive schedule is given. This algorithm generates schedules with at most $m - 1$ preemptions. It is also shown that an optimal nonpreemptive schedule can be almost twice as long as an optimal preemptive schedule. The results suggest that preemption is extremely beneficial in simultaneously minimizing the flow time and the schedule length.