Temporal Difference-Based Policy Iteration for Optimal Control of Stochastic Systems

In this paper, a unified policy iteration approach is presented for the optimal control problem of stochastic system with discounted average cost and continuous state space. The approach consists of temporal difference learning-based potential function approximation algorithms and performance difference formula-based policy improvement. The approximation algorithms are derived by solving the Poisson equation-based fixed-point equation, which can be viewed as continuous versions of least squares policy evaluation algorithm and least squares temporal difference algorithm. The simulations are provided to illustrate the effectiveness of the approach.     

求解M-张量方程的两种新型算法

多重线性系统在当今的工程计算和数据挖掘等领域有很多实际应用,许多问题可以转化为多重线性系统求解问题.在本文中,我们首先提出了一种新的迭代算法来求解系数张量为M-张量的多重线性系统,在此基础上又提出了一种新的改进算法,并对两种算法的收敛性进行了分析.数值算例的结果表明,本文提出的两种算法是有效的并且改进算法的迭代时间更少.     

A new path-based cutting plane approach for the discrete time-cost tradeoff problem

Determining discrete time-cost tradeoffs in project networks allows for the control of the processing time of an activity via the amount of non-renewable resources allocated to it. Larger resource allocations with associated higher costs reduce activities’ durations. Given a set of execution modes (time-cost pairs) for each activity, the discrete time-cost tradeoff problem (DTCTP) involves selecting a mode for each activity so that either: (i) the project completion time is minimized, given a budget, or (ii) the total project cost is minimized, given a deadline, or (iii) the complete and efficient project cost curve is constructed over all feasible project durations. The DTCTP is a problem with great applicability prospects but at the same time a strongly N P{\mathcal N}\,P-hard optimization problem; solving it exactly has been a real challenge. Known optimal solution methodologies are limited to networks with no more than 50 activities and only lower bounds can be computed for larger, realistically sized, project instances. In this paper, we study a path-based approach to the DTCTP, in which a new path-based formulation in activity-on-node project networks is presented. This formulation is subsequently solved using an exact cutting plane algorithm enhanced with speed-up techniques. Extensive computational results reported for almost 5,000 benchmark test problems demonstrate the effectiveness of the proposed algorithm in solving to optimality for the first time some of the hardest and largest instances in the literature. The promising results suggest that the algorithms may be embedded into project management software and, hence, become a useful tool for practitioners in the future.     

Parallelizing simulated annealing algorithms based on high-performance computer

We implemented five conversions of simulated annealing (SA) algorithm from sequential-to-parallel forms on high-performance computers and applied them to a set of standard function optimization problems in order to test their performances. According to the experimental results, we eventually found that the traditional approach to parallelizing simulated annealing, namely, parallelizing moves in sequential SA, difficultly handled very difficult problem instances. Divide-and-conquer decomposition strategy used in a search space sometimes might find the global optimum function value, but it frequently resulted in great time cost if the random search space was considerably expanded. The most effective way we found in identifying the global optimum solution is to introduce genetic algorithm (GA) and build a highly hybrid GA+SA algorithm. In this approach, GA has been applied to each cooling temperature stage. Additionally, the performance analyses of the best algorithm among the five implemented algorithms have been done on the IBM Beowulf PCs Cluster and some comparisons have been made with some recent global optimization algorithms in terms of the number of functional evaluations needed to obtain a global minimum, success rate and solution quality.     

Uniformization and performance sensitivity estimation in closed queueing networks

This paper proposes a single sample path-based sensitivity estimation method for discrete event systems. The method employs two major techniques: uniformization and importance sampling. By uniformization, steady-state performance measures can be estimated via the transition matrix of the embedded Markov chain in the uniformized process. The sensitivity of a transition matrix is obtained by applying importance sampling to an ensemble average of sample paths. The algorithm developed for this method is easy to be implemented; the method applies to more systems than infinitesimal perturbation analysis.     

Diophantine Quadratic Equation and Smith Normal Form Using Scaled Extended Integer Abaffy–Broyden–Spedicato Algorithms

Classes of integer Abaffy–Broyden–Spedicato (ABS) methods have recently been introduced for solving linear systems of Diophantine equations. Each method provides the general integer solution of the system by computing an integer solution and an integer matrix, named Abaffian, with rows generating the integer null space of the coefficient matrix. The Smith normal form of a general rectangular integer matrix is a diagonal matrix, obtained by elementary nonsingular (unimodular) operations. Here, we present a class of algorithms for computing the Smith normal form of an integer matrix. In doing this, we propose new ideas to develop a new class of extended integer ABS algorithms generating an integer basis for the integer null space of the matrix. For the Smith normal form, having the need to solve the quadratic Diophantine equation, we present two algorithms for solving such equations. The first algorithm makes use of a special integer basis for the row space of the matrix, and the second one, with the intention of controlling the growth of intermediate results and making use of our given conjecture, is based on a recently proposed integer ABS algorithm. Finally, we report some numerical results on randomly generated test problems showing a better performance of the second algorithm in controlling the size of the solution. We also report the results obtained by our proposed algorithm on the Smith normal form and compare them with the ones obtained using Maple, observing a more balanced distribution of the intermediate components obtained by our algorithm.     

Non-uniform data distribution for communication-efficient parallel clustering

Global communication requirements and load imbalance of some parallel data mining algorithms are the major obstacles to exploit the computational power of large-scale systems. This work investigates how non-uniform data distributions can be exploited to remove the global communication requirement and to reduce the communication cost in parallel data mining algorithms and, in particular, in the k-means algorithm for cluster analysis. In the straightforward parallel formulation of the k-means algorithm, data and computation loads are uniformly distributed over the processing nodes. This approach has excellent load balancing characteristics that may suggest it could scale up to large and extreme-scale parallel computing systems. However, at each iteration step the algorithm requires a global reduction operation which hinders the scalability of the approach. This work studies a different parallel formulation of the algorithm where the requirement of global communication is removed, while maintaining the same deterministic nature of the centralised algorithm. The proposed approach exploits a non-uniform data distribution which can be either found in real-world distributed applications or can be induced by means of multi-dimensional binary search trees. The approach can also be extended to accommodate an approximation error which allows a further reduction of the communication costs. The effectiveness of the exact and approximate methods has been tested in a parallel computing system with 64 processors and in simulations with 1024 processing elements.     

Solving the sum-of-ratios problem by a stochastic search algorithm

In spite of the recent progress in fractional programming, the sum-of-ratios problem remains untoward. Freund and Jarre proved that this is an NP-complete problem. Most methods overcome the difficulty using the deterministic type of algorithms, particularly, the branch-and-bound method. In this paper, we propose a new approach by applying the stochastic search algorithm introduced by Birbil, Fang and Sheu to a transformed image space. The algorithm then computes and moves sample particles in the q − 1 dimensional image space according to randomly controlled interacting electromagnetic forces. Numerical experiments on problems up to sum of eight linear ratios with a thousand variables are reported. The results also show that solving the sum-of-ratios problem in the image space as proposed is, in general, preferable to solving it directly in the primal domain.     

Solving the response time variability problem by means of a psychoclonal approach

The response time variability problem (RTVP) is a combinatorial scheduling problem that has recently appeared in the literature. This problem has a wide range of real life applications in fields such as manufacturing, hard real-time systems, operating systems and network environments. Originally, the RTVP occurs whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the instants at which they receive the necessary resources is minimized. Since the RTVP is hard to solve, heuristic techniques are needed for solving it. Three metaheuristic—multi-start, GRASP and PSO—algorithms proposed for solving the RTVP in two previous studies have been the most efficient to date in solving non-small instances of the RTVP. We propose solving the RTVP by means of a psychoclonal algorithm based approach. The psychoclonal algorithm inherits its attributes from Maslow’s hierarchy of needs theory and the artificial immune system (AIS) approach, specifically the clonal selection principle. In this paper, we compare the proposed psychoclonal algorithm with the three aforementioned metaheuristic algorithms and show that, on average, the psychoclonal algorithm strongly improves on the results obtained.