Adaption Model for Building Agile Pronunciation Dictionaries Using Phonemic Distance Measurements
Where human beings can easily learn and adopt pronunciation variations, machines need training before put into use. Also humans keep minimum vocabulary and their pronunciation variations are stored in front-end of their memory for ready reference, while machines keep the entire pronunciation dictionary for ready reference. Supervised methods are used for preparation of pronunciation dictionaries which take large amounts of manual effort, cost, time and are not suitable for real time use. This paper presents an unsupervised adaptation model for building agile and dynamic pronunciation dictionaries online. These methods mimic human approach in learning the new pronunciations in real time. A new algorithm for measuring sound distances called Dynamic Phone Warping is presented and tested. Performance of the system is measured using an adaptation model and the precision metrics is found to be better than 86 percent.
Dynamic Programming Based Algorithm for the Unit Commitment of the Transmission-Constrained Multi-Site Combined Heat and Power System
High penetration of intermittent renewable energy sources (RES) such as solar power and wind power into the energy system has caused temporal and spatial imbalance between electric power supply and demand for some countries and regions. This brings about the critical need for coordinating power production and power exchange for different regions. As compared with the power-only systems, the combined heat and power (CHP) systems can provide additional flexibility of utilizing RES by exploiting the interdependence of power and heat production in the CHP plant. In the CHP system, power production can be influenced by adjusting heat production level and electric power can be used to satisfy heat demand by electric boiler or heat pump in conjunction with heat storage, which is much cheaper than electric storage. This paper addresses multi-site CHP systems without considering RES, which lay foundation for handling penetration of RES. The problem under study is the unit commitment (UC) of the transmission-constrained multi-site CHP systems. We solve the problem by combining linear relaxation of ON/OFF states and sequential dynamic programming (DP) techniques, where relaxed states are used to reduce the dimension of the UC problem and DP for improving the solution quality. Numerical results for daily scheduling with realistic models and data show that DP-based algorithm is from a few to a few hundred times faster than CPLEX (standard commercial optimization software) with good solution accuracy (less than 1% relative gap from the optimal solution on the average).
Optimal Maintenance and Improvement Policies in Water Distribution System: Markov Decision Process Approach
The Markov decision process (MDP) based
methodology is implemented in order to establish the optimal
schedule which minimizes the cost. Formulation of MDP problem
is presented using the information about the current state of pipe,
improvement cost, failure cost and pipe deterioration model. The
objective function and detailed algorithm of dynamic programming
(DP) are modified due to the difficulty of implementing the
conventional DP approaches. The optimal schedule derived from
suggested model is compared to several policies via Monte
Carlo simulation. Validity of the solution and improvement in
computational time are proved.
Optimum Stratiﬁcation of a Skewed Population
The focus of this paper is to develop a technique
of solving a combined problem of determining Optimum Strata
Boundaries(OSB) and Optimum Sample Size (OSS) of each stratum,
when the population understudy isskewed and the study variable has
a Pareto frequency distribution. The problem of determining the OSB
isformulated as a Mathematical Programming Problem (MPP) which
is then solved by dynamic programming technique. A numerical
example is presented to illustrate the computational details of the
proposed method. The proposed technique is useful to obtain OSB
and OSS for a Pareto type skewed population, which minimizes the
variance of the estimate of population mean.
On Optimum Stratification
In this manuscript, we discuss the problem of determining the optimum stratification of a study (or main) variable based on the auxiliary variable that follows a uniform distribution. If the stratification of survey variable is made using the auxiliary variable it may lead to substantial gains in precision of the estimates. This problem is formulated as a Nonlinear Programming Problem (NLPP), which turn out to multistage decision problem and is solved using dynamic programming technique.
Adaptive Dynamic Time Warping for Variable Structure Pattern Recognition
Pattern discovery from time series is of fundamental importance. Particularly, when information about the structure of a pattern is not complete, an algorithm to discover specific patterns or shapes automatically from the time series data is necessary. The dynamic time warping is a technique that allows local flexibility in aligning time series. Because of this, it is widely used in many fields such as science, medicine, industry, finance and others. However, a major problem of the dynamic time warping is that it is not able to work with structural changes of a pattern. This problem arises when the structure is influenced by noise, which is a common thing in practice for almost every application. This paper addresses this problem by means of developing a novel technique called adaptive dynamic time warping.
Optimal Risk Reduction in the Railway Industry by Using Dynamic Programming
The paper suggests for the first time the use of dynamic programming techniques for optimal risk reduction in the railway industry. It is shown that by using the concept ‘amount of removed risk by a risk reduction option’, the problem related to optimal allocation of a fixed budget to achieve a maximum risk reduction in the railway industry can be reduced to an optimisation problem from dynamic programming. For n risk reduction options and size of the available risk reduction budget B (expressed as integer number), the worst-case running time of the proposed algorithm is O (n x (B+1)), which makes the proposed method a very efficient tool
for solving the optimal risk reduction problem in the railway industry.
A Deterministic Dynamic Programming Approach for Optimization Problem with Quadratic Objective Function and Linear Constraints
This paper presents the novel deterministic dynamic programming approach for solving optimization problem with quadratic objective function with linear equality and inequality constraints. The proposed method employs backward recursion in which computations proceeds from last stage to first stage in a multi-stage decision problem. A generalized recursive equation which gives the exact solution of an optimization problem is derived in this paper. The method is purely analytical and avoids the usage of initial solution. The feasibility of the proposed method is demonstrated with a practical example. The numerical results show that the proposed method provides global optimum solution with negligible computation time.
Dynamic Features Selection for Heart Disease Classification
The healthcare environment is generally perceived as
being information rich yet knowledge poor. However, there is a lack
of effective analysis tools to discover hidden relationships and trends
in data. In fact, valuable knowledge can be discovered from
application of data mining techniques in healthcare system. In this
study, a proficient methodology for the extraction of significant
patterns from the Coronary Heart Disease warehouses for heart
attack prediction, which unfortunately continues to be a leading cause
of mortality in the whole world, has been presented. For this purpose,
we propose to enumerate dynamically the optimal subsets of the
reduced features of high interest by using rough sets technique
associated to dynamic programming. Therefore, we propose to
validate the classification using Random Forest (RF) decision tree to
identify the risky heart disease cases. This work is based on a large
amount of data collected from several clinical institutions based on
the medical profile of patient. Moreover, the experts- knowledge in
this field has been taken into consideration in order to define the
disease, its risk factors, and to establish significant knowledge
relationships among the medical factors. A computer-aided system is
developed for this purpose based on a population of 525 adults. The
performance of the proposed model is analyzed and evaluated based
on set of benchmark techniques applied in this classification problem.
Optimum Replacement Policies for Kuwait Passenger Transport Company Busses: Case Study
Due to the excess of a vehicle operation through its life, some elements may face failure and deteriorate with time. This leads us to carry out maintenance, repair, tune up or full overhaul. After a certain period, the vehicle elements deteriorations increase with time which causes a very high increase of doing the maintenance operations and their costs. However, the logic decision at this point is to replace the current vehicle by a new one with minimum failure and maximum income. The importance of studying vehicle replacement problems come from the increase of stopping days due to many deteriorations in the vehicle parts. These deteriorations increase year after year causing an increase of operating costs and decrease the vehicle income. Vehicle replacement aims to determine the optimum time to keep, maintain, overhaul, renew and replace vehicles. This leads to an improvement in vehicle income, total operating costs, maintenance cost, fuel and oil costs, ton-kilometers, vehicle and engine performance, vehicle noise, vibration, and pollution. The aim of this paper is to find the optimum replacement policies of Kuwait Passenger Transport Company (KPTCP) fleet of busses. The objective of these policies is to maximize the busses pure profits. The dynamic programming (D.P.) technique is used to generate the busses optimal replacement policies
Joint Optimization of Pricing and Advertisement for Seasonal Branded Products
The goal of this paper is to develop a model to
integrate “pricing" and “advertisement" for short life cycle products,
such as branded fashion clothing products. To achieve this goal, we
apply the concept of “Dynamic Pricing". There are two classes of
advertisements, for the brand (regardless of product) and for a
particular product. Advertising the brand affects the demand and
price of all the products. Thus, the model considers all these products
in relation with each other. We develop two different methods to
integrate both types of advertisement and pricing. The first model is
developed within the framework of dynamic programming. However,
due to the complexity of the model, this method cannot be applicable
for large size problems. Therefore, we develop another method,
called hieratical approach, which is capable of handling the real
world problems. Finally, we show the accuracy of this method, both
theoretically and also by simulation.
Predicting the Minimum Free Energy RNA Secondary Structures using Harmony Search Algorithm
The physical methods for RNA secondary structure prediction are time consuming and expensive, thus methods for computational prediction will be a proper alternative. Various algorithms have been used for RNA structure prediction including dynamic programming and metaheuristic algorithms. Musician's behaviorinspired harmony search is a recently developed metaheuristic algorithm which has been successful in a wide variety of complex optimization problems. This paper proposes a harmony search algorithm (HSRNAFold) to find RNA secondary structure with minimum free energy and similar to the native structure. HSRNAFold is compared with dynamic programming benchmark mfold and metaheuristic algorithms (RnaPredict, SetPSO and HelixPSO). The results showed that HSRNAFold is comparable to mfold and better than metaheuristics in finding the minimum free energies and the number of correct base pairs.
A Dynamic Programming Model for Maintenance of Electric Distribution System
The paper presents dynamic programming based model as a planning tool for the maintenance of electric power systems. Every distribution component has an exponential age depending reliability function to model the fault risk. In the moment of time when the fault costs exceed the investment costs of the new component the reinvestment of the component should be made. However, in some cases the overhauling of the old component may be more economical than the reinvestment. The comparison between overhauling and reinvestment is made by optimisation process. The goal of the optimisation process is to find the cost minimising maintenance program for electric power distribution system.
All-Pairs Shortest-Paths Problem for Unweighted Graphs in O(n2 log n) Time
Given a simple connected unweighted undirected graph G = (V (G), E(G)) with |V (G)| = n and |E(G)| = m, we present a new algorithm for the all-pairs shortest-path (APSP) problem. The running time of our algorithm is in O(n2 log n). This bound is an improvement over previous best known O(n2.376) time bound of Raimund Seidel (1995) for general graphs. The algorithm presented does not rely on fast matrix multiplication. Our algorithm with slight modifications, enables us to compute the APSP problem for unweighted directed graph in time O(n2 log n), improving a previous best known O(n2.575) time bound of Uri Zwick (2002).
Optimal DG Placement in Distribution systems Using Cost/Worth Analysis
DG application has received increasing attention during
recent years. The impact of DG on various aspects of distribution system
operation, such as reliability and energy loss, depend highly on DG
location in distribution feeder. Optimal DG placement is an important
subject which has not been fully discussed yet.
This paper presents an optimization method to determine optimal DG
placement, based on a cost/worth analysis approach. This method
considers technical and economical factors such as energy loss, load point
reliability indices and DG costs, and particularly, portability of DG. The
proposed method is applied to a test system and the impacts of different
parameters such as load growth rate and load forecast uncertainty (LFU)
on optimum DG location are studied.
A New Hybrid Optimization Method for Optimum Distribution Capacitor Planning
This work presents a new algorithm based on a combination of fuzzy (FUZ), Dynamic Programming (DP), and Genetic Algorithm (GA) approach for capacitor allocation in distribution feeders. The problem formulation considers two distinct objectives related to total cost of power loss and total cost of capacitors including the purchase and installation costs. The novel formulation is a multi-objective and non-differentiable optimization problem. The proposed method of this article uses fuzzy reasoning for sitting of capacitors in radial distribution feeders, DP for sizing and finally GA for finding the optimum shape of membership functions which are used in fuzzy reasoning stage. The proposed method has been implemented in a software package and its effectiveness has been verified through a 9-bus radial distribution feeder for the sake of conclusions supports. A comparison has been done among the proposed method of this paper and similar methods in other research works that shows the effectiveness of the proposed method of this paper for solving optimum capacitor planning problem.
Optimal Policy for a Deteriorating Inventory Model with Finite Replenishment Rate and with Price Dependant Demand Rate and Cycle Length Dependant Price
In this paper, an inventory model with finite and
constant replenishment rate, price dependant demand rate, time
value of money and inflation, finite time horizon, lead time and
exponential deterioration rate and with the objective of maximizing
the present worth of the total system profit is developed. Using a
dynamic programming based solution algorithm, the optimal
sequence of the cycles can be found and also different optimal
selling prices, optimal order quantities and optimal maximum
inventories can be obtained for the cycles with unequal lengths,
which have never been done before for this model. Also, a
numerical example is used to show accuracy of the solution
Automated Segmentation of ECG Signals using Piecewise Derivative Dynamic Time Warping
Electrocardiogram (ECG) segmentation is necessary
to help reduce the time consuming task of manually annotating
ECG-s. Several algorithms have been developed to segment the ECG
automatically. We first review several of such methods, and then
present a new single lead segmentation method based on Adaptive
piecewise constant approximation (APCA) and Piecewise derivative
dynamic time warping (PDDTW). The results are tested on the QT
database. We compared our results to Laguna-s two lead method. Our
proposed approach has a comparable mean error, but yields a slightly
higher standard deviation than Laguna-s method.
Feature Based Dense Stereo Matching using Dynamic Programming and Color
This paper presents a new feature based dense stereo
matching algorithm to obtain the dense disparity map via dynamic
programming. After extraction of some proper features, we use some
matching constraints such as epipolar line, disparity limit, ordering
and limit of directional derivative of disparity as well. Also, a coarseto-
fine multiresolution strategy is used to decrease the search space
and therefore increase the accuracy and processing speed. The
proposed method links the detected feature points into the chains and
compares some of the feature points from different chains, to
increase the matching speed. We also employ color stereo matching
to increase the accuracy of the algorithm. Then after feature
matching, we use the dynamic programming to obtain the dense
disparity map. It differs from the classical DP methods in the stereo
vision, since it employs sparse disparity map obtained from the
feature based matching stage. The DP is also performed further on a
scan line, between any matched two feature points on that scan line.
Thus our algorithm is truly an optimization method. Our algorithm
offers a good trade off in terms of accuracy and computational
efficiency. Regarding the results of our experiments, the proposed
algorithm increases the accuracy from 20 to 70%, and reduces the
running time of the algorithm almost 70%.
A System of Automatic Speech Recognition based on the Technique of Temporal Retiming
We report in this paper the procedure of a system of
automatic speech recognition based on techniques of the dynamic
programming. The technique of temporal retiming is a technique
used to synchronize between two forms to compare. We will see how
this technique is adapted to the field of the automatic speech
recognition. We will expose, in a first place, the theory of the
function of retiming which is used to compare and to adjust an
unknown form with a whole of forms of reference constituting the
vocabulary of the application. Then we will give, in the second place,
the various algorithms necessary to their implementation on machine.
The algorithms which we will present were tested on part of the
corpus of words in Arab language Arabdic-10  and gave whole
satisfaction. These algorithms are effective insofar as we apply them
to the small ones or average vocabularies.
Application of Neuro-Fuzzy Dynamic Programming to Improve the Reactive Power and Voltage Profile of a Distribution Substation
Improving the reactive power and voltage profile of a
distribution substation is investigated in this paper. The purpose is to
properly determination of the shunt capacitors on/off status and
suitable tap changer (TC) position of a substation transformer. In
addition, the limitation of secondary bus voltage, the maximum
allowable number of switching operation in a day for on load tap
changer and on/off status of capacitors are taken into account. To
achieve these goals, an artificial neural network (ANN) is designed to
provide preliminary scheduling. Input of ANN is active and reactive
powers of transformer and its primary and secondary bus voltages.
The output of ANN is capacitors on/off status and TC position. The
preliminary schedule is further refined by fuzzy dynamic
programming in order to reach the final schedule. The operation of
proposed method in Q/V improving is compared with the results
obtained by operator operation in a distribution substation.
Optimal Path Planner for Autonomous Vehicles
In this paper a real-time trajectory generation algorithm for computing 2-D optimal paths for autonomous aerial vehicles has been discussed. A dynamic programming approach is adopted to compute k-best paths by minimizing a cost function. Collision detection is implemented to detect intersection of the paths with obstacles. Our contribution is a novel approach to the problem of trajectory generation that is computationally efficient and offers considerable gain over existing techniques.
Parallezation Protein Sequence Similarity Algorithms using Remote Method Interface
One of the major problems in genomic field is to perform sequence comparison on DNA and protein sequences. Executing sequence comparison on the DNA and protein data is a computationally intensive task. Sequence comparison is the basic step for all algorithms in protein sequences similarity. Parallel computing is an attractive solution to provide the computational power needed to speedup the lengthy process of the sequence comparison. Our main research is to enhance the protein sequence algorithm using dynamic programming method. In our approach, we parallelize the dynamic programming algorithm using multithreaded program to perform the sequence comparison and also developed a distributed protein database among many PCs using Remote Method Interface (RMI). As a result, we showed how different sizes of protein sequences data and computation of scoring matrix of these protein sequence on different number of processors affected the processing time and speed, as oppose to sequential processing.
Automated ECG Segmentation Using Piecewise Derivative Dynamic Time Warping
Electrocardiogram (ECG) segmentation is necessary to help reduce the time consuming task of manually annotating ECG's. Several algorithms have been developed to segment the ECG automatically. We first review several of such methods, and then present a new single lead segmentation method based on Adaptive piecewise constant approximation (APCA) and Piecewise derivative dynamic time warping (PDDTW). The results are tested on the QT database. We compared our results to Laguna's two lead method. Our proposed approach has a comparable mean error, but yields a slightly higher standard deviation than Laguna's method.