SEARCH · PubMed Health

Results for “Algorithms”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 577 records · Page 32Linked to original sources

PubMed1999

A behavior-based inverse kinematics algorithm to predict arm prehension postures for computer-aided ergonomic evaluation.

In this paper, the computational problem of inverse kinematics of arm prehension movements was investigated. How motions of each joint involved in arm movements can be used to control the end-effector (hand) position and orientation was first examined. It is shown that the inverse kinematics problem due to the kinematic redundancy in joint space is ill-posed only at the control of hand orientation but not at the control of hand position. Based upon this analysis, a previously proposed inverse kinematics algorithm (Wang et Verriest, 1998a) to predict arm reach postures was extended to a seven-DOF arm model to predict arm prehension postures using a separate control of hand position and orientation. The algorithm can be either in rule-based form or by optimization through appropriate choice of weight coefficients. Compared to the algebraic inverse kinematics algorithm, the proposed algorithm can handle the non-linearity of joint limits in a straightforward way. In addition, no matrix inverse calculation is needed, thus avoiding the stability and convergence problems often occurring near a singularity of the Jacobian. Since an end-effector motion-oriented method is used to describe joint movements, observed behaviors of arm movements can be easily implemented in the algorithm. The proposed algorithm provides a general frame for arm postural control and can be used as an efficient postural manipulation tool for computer-aided ergonomic evaluation.

Adult↗

PubMed1997

Stochastic optimization algorithms of a Bayesian design criterion for Bayesian parameter estimation of nonlinear regression models: application in pharmacokinetics.

This article proposes three stochastic algorithms to optimize a Bayesian design criterion for Bayesian estimation of the parameters of nonlinear regression models; this criterion is the information expected from an experiment. The first algorithm is based on a stochastic version of the simplex with an adaptive sampling procedure. The others are stochastic approximation algorithms: the Kiefer-Wolfowitz and the pseudogradient algorithms. We first present the information criterion and the optimization algorithms. The efficiency of each algorithm for optimizing this Bayesian design criterion is then assessed by a simulation study for a nonlinear model assuming a discrete prior distribution. An application for designing an experiment to estimate the kinetics of radioiodine thyroid uptake is then proposed.

Algorithms↗

PubMed1994

Transient ischemic attack and minor ischemic stroke: an algorithm for evaluation and treatment. Mayo Clinic Division of Cerebrovascular Diseases.

OBJECTIVE: To report a cost-effective and scientifically based algorithm for the clinical assessment and treatment of patients with transient ischemic attack (TIA) or minor ischemic stroke. DESIGN: We comprehensively reviewed the literature on the epidemiologic features, assessment approaches, and treatment recommendations for ischemic cerebrovascular disease and developed an algorithm by using the available clinical and research data to support all decision-making steps. MATERIAL AND METHODS: For patients with TIA or minor ischemic stroke, the appropriate setting for investigation (inpatient or outpatient), suggested diagnostic tests, use of anticoagulants and antiplatelet agents, and indications for surgical treatment are reviewed. RESULTS: Although stroke is a common cause of death and lost productivity in the United States, the clinical assessment of patients with TIA or minor ischemic stroke has lacked consistency. The simplified algorithm clarifies patients who may be candidates for hospitalization and possible anticoagulation therapy. Initial diagnostic studies should include computed tomography of the head without use of a contrast agent, which quickly distinguishes nonhemorrhagic from hemorrhagic cerebrovascular disease. Evolving noninvasive studies of the cerebral vasculature are providing increasingly sensitive means of detecting stenoses, yet cerebral angiography remains the "gold standard." Treatment options depend on the pathophysiologic findings on diagnostic evaluation. CONCLUSION: The assessment of patients with ischemic cerebrovascular disease is complex. The simplified algorithmic approach reported herein necessitates entry of appropriate patients into the algorithm. Because of clinical heterogeneity, an algorithm may apply to a wide spectrum of patients but will not cover every situation; hence, evaluation must be guided by a patient's unique history and findings on examination and by the physician's clinical experience.

Algorithms↗

PubMed2002

Sensitivity and specificity of the Swedish interactive threshold algorithm for glaucomatous visual field defects.

PURPOSE: To determine the sensitivity and specificity of two new visual field algorithms in detecting glaucomatous visual field defects: (1) Swedish interactive threshold algorithm (SITA) standard and (2) SITA fast. DESIGN: Prospective observational case series. PARTICIPANTS: Ninety normal subjects and 82 glaucoma patients. TESTING: Central 30 degrees fields were performed with the Humphrey visual field analyzer 30-2 program (Humphrey Systems, Dublin, CA) using full threshold, SITA standard, and SITA fast algorithms on the same day for two or more sessions within a 1-month period. MAIN OUTCOME MEASURES: Sensitivity and specificity in detecting glaucomatous visual field defects with SITA standard and SITA fast using full threshold testing as the reference standard. RESULTS: The sensitivity of SITA standard and SITA fast in detecting glaucomatous defects overall was 98% and 95%, respectively. In the subset of mild glaucomatous field defects (26 patients), sensitivity of SITA standard was 92% versus 85% with SITA fast. Sensitivity was 100% for both algorithms in moderate to severe glaucomatous defects. Specificity for glaucoma defects using SITA standard and SITA fast was 96% for both algorithms. SITA standard reduced test-taking time from full threshold by 52% in normal subjects and 47% in glaucoma patients (P < 0.001). SITA fast reduced test-taking time by 72% in normal subjects and 65% in glaucoma patients (P < 0.001). Mean deviation values were 0.4 dB and 0.8 dB better in SITA standard and SITA fast fields, respectively, in normal subjects (P < 0.001), and 0.7 dB and 1.2 dB in SITA standard and SITA fast fields, respectively, in glaucoma patients (P < 0.001) compared with full threshold values. CONCLUSIONS: The new algorithms for measuring visual fields, SITA standard and SITA fast, have excellent sensitivity and specificity for glaucomatous visual field loss with considerable savings in time.

Adult↗

PubMed2003

Experimental validation tests of fast Fourier transform convolution and multigrid superposition algorithms for dose calculation in low-density media.

BACKGROUND AND PURPOSE: Modern conformal radiotherapy treatments require accurate dose calculation in any relevant clinical situation. One of these situations is the treatment of lung tumors, where irradiation has to be planned under challenging conditions for dose calculation. In this study we assess the errors in dose values predicted by fast Fourier transform convolution (FFTC) and multigrid superposition (MGS) algorithms implemented in a commercial treatment planning system (TPS). MATERIALS AND METHODS: FFTC and MGS algorithms were used in a FOCUS 3.0.0 (Computerized Medical Systems, USA) to calculate doses in treatment plans using photon beams of 6 and 25 MV nominal energy from a Saturne 43 linac (GE Medical Systems, USA). A 10x10-cm beam irradiating a mediastinum-lung and a thoracic wall-lung-thoracic wall modeled geometry was assessed. The calculated data were compared with measurements performed with radiographic films and ionization chamber. RESULTS: FFTC algorithm leads to an average deviation from ionometric dose measurements of over 10%. Discrepancies between measured and calculated beam fringe values (distance between 50 and 90% isodose lines) of up to 8 mm were observed. For MGS algorithm, all the points assessed in both geometries fulfilled the 3%-3 mm accuracy criteria and the average deviation of absolute dose was about 1%. A maximum of 3 mm deviation in the beam fringe for any depth was found and was within 2 mm beyond the buildup region. Deviations between ionometric and film measurements were within 3%. CONCLUSIONS: MGS algorithm assesses with reasonable accuracy dose distributions and absolute dose in inhomogeneous regions like the lung region. Therefore, and respecting the inhomogeneity dose calculation, the system could be used in routine clinical practice and in dose-escalation programs. This is not true in the case of FFTC algorithm which leads to errors greater than 10% in the absolute dose calculation and underestimates the beam fringe by up to 8 mm.

Algorithms↗

PubMed1999

Event-related dimensional reductions in the primary auditory cortex of the conscious cat are revealed by new techniques for enhancing the non-linear dimensional algorithms.

The analytic algorithms derived from non-linear deterministic models may be more sensitive to differences in physiological data than those based on linear stochastic models. Among the non-linear algorithms the time-dependent dimensional ones appear to be the most sensitive discriminators. In the present study dimensional responses were examined in both electronically and mathematically generated data and in high-resolution physiological data. The latter were event-related potentials (ERPs) recorded from the primary auditory cortex of cats during classical conditioning. Two techniques were found to lengthen and stabilize the linear scaling region in the correlation integral of the dimensional algorithms: (1) linking trials to increase data length; and (2) gain reduction to lower integer-values of noise, combined with algorithmic setting of slopes < 0.5 to zero. Of the three dimensional algorithms examined, only the time-dependent Point Correlation Dimension (PD2i) showed low error rates when tracking the dimensional shifts in non-stationary generated data. This algorithm also uniquely distinguished between the conditioned and unconditioned physiological responses. The ERPs had corresponding PD2i's that were significantly different from each other as well as from their own randomized-phase surrogates. The brief dimensional reduction that follows a conditioned stimulus is interpreted to be related to 'cooperativity' among the underlying cortical neurons that contribute to its electrogenesis.

Algorithms↗

PubMed2002

Unified algorithm for real-time detection of drug interaction and drug allergy.

This algorithm aims at unifying and generalizing the algorithm for detecting all types of documented drug interactions such as drug-drug interactions, drug-disease interactions, drug-patient interactions (drug allergy) from patient profile information and drug-laboratory test interactions in real-time prescribing system. Ideally, the system should conform to the following criteria: (1) data independence; (2) software interconnectability; (3) knowledge expandability; (4) flexibility; and (5) computation resource efficiency. We propose a robust Structured Query Language (SQL) algorithm to detect drug interactions and drug allergy according to such criteria. We believe that this is the first public domain algorithm in SQL that could be easily implemented into most open-system prescribing software which support SQL language. The algorithm comprises two major stages: 'expand' and 'extract'. The former expands all information in the prescription with their synonyms, groups, or components. The latter extracts the documented interactions by inner-joining knowledge-base with two independent copies of the expanded prescription list simultaneously. Simulation study for speed performance indicates that this algorithm is well behaved, for the speed of computation does not grow faster than the growth in prescription size.

Algorithms↗

PubMed1998

An algorithm for preoperative prediction of reoperation risk after internal fixation of femoral neck fractures.

An algorithm was designed for preoperative prediction of the risk for reoperation, and the mortality risk, after internal fixation of femoral neck fractures. Out of 51 reviewed studies of femoral neck fractures, eight met specified inclusion criteria such as low dropout rates, a minimum of ten surgeons performing the surgery, a minimum of 2 years follow-up, and a standard age, sex, and Garden class distribution. Five of these studies were used for the construction of the algorithm, and the remaining three for testing the specificity and sensitivity of the algorithm. A separate analysis of the influence of age on the reoperation rate was also performed. In the analysis of 399 reviewed cases of femoral neck fractures, the specificity for the algorithm in predicting the risk for reoperation was 96%, and the sensitivity was 51%. The positive predictive value for the algorithm in predicting the risk for reoperation was 77%, which was three times higher compared to the commonly used predictors age and Garden class (positive predictive value 25%). For prediction of the mortality risk the positive predictive value for-the algorithm was 57%.

Aged↗

PubMed1999

GLLS for optimally sampled continuous dynamic system modeling: theory and algorithm.

The original generalized linear least squares (GLLS) algorithm was developed for non-uniformly sampled biomedical system parameter estimation using finely sampled instantaneous measurements (D. Feng, S.C. Huang, Z. Wang, D. Ho, An unbiased parametric imaging algorithm for non-uniformly sampled biomedical system parameter estimation, IEEE Trans. Med. Imag. 15 (1996) 512-518). This algorithm is particularly useful for image-wide generation of parametric images with positron emission tomography (PET), as it is computationally efficient and statistically reliable (D. Feng, D. Ho, Chen, K., L.C. Wu, J.K. Wang, R.S. Liu, S.H. Yeh, An evaluation of the algorithms for determining local cerebral metabolic rates of glucose using positron emission tomography dynamic data, IEEE Trans. Med. Imag. 14 (1995) 697-710). However, when dynamic PET image data are sampled according to the optimal image sampling schedule (OISS) to reduce memory and storage space (X. Li, D. Feng, K. Chen, Optimal image sampling schedule: A new effective way to reduce dynamic image storage space and functional image processing time, IEEE Trans. Med. Imag. 15 (1996) 710-718), only a few temporal image frames are recorded (e.g. only four images are recorded for the four parameter fluoro-deoxy-glucose (FDG) model). These image frames are recorded in terms of accumulated radio-activity counts and as a result, the direct application of GLLS is not reliable as instantaneous measurement samples can no longer be approximated by averaging of accumulated measurements over the sampling intervals. In this paper, we extend GLLS to OISS-GLLS which deals with the fewer accumulated measurement samples obtained from OISS dynamic systems. The theory and algorithm of this new technique are formulated and studied extensively. To investigate statistical reliability and computational efficiency of OISS-GLLS, a simulation study using dynamic PET data was performed. OISS-GLLS using 4-measurement samples was compared to the non-linear least squares (NLS) method using 22-measurement samples, GLLS using 22-measurement samples and OISS-NLS using 4-measurement samples. Results demonstrated that OISS-GLLS was able to achieve parameter estimates of equivalent accuracy and reliability in comparison to NLS or GLLS using finely sampled measurements (22-measurement samples), or OISS-NLS using optimally sampled measurements (4-measurement samples). Further more, as fewer measurement samples are used in OISS-GLLS, this algorithm is computationally faster than NLS or GLLS. Therefore, OISS-GLLS is well-suited for image-wide parameter estimation when PET image data are recorded according to the optimal image sampling schedule.

Algorithms↗

PubMed1993

An experimental algorithm versus standard advanced cardiac life support in a swine model of out-of-hospital cardiac arrest.

STUDY OBJECTIVE: To compare an experimental algorithm with standard advanced cardiac life support in a swine model of out-of-hospital cardiac arrest. DESIGN: Randomized, controlled experimental trial. SETTING/TYPE OF PARTICIPANT: Animal laboratory using swine. INTERVENTIONS: Eighteen swine (17.8 to 23.7 kg) were sedated, intubated, anesthetized, and instrumented for monitoring of arterial and central venous pressures and ECG. Ventricular fibrillation was induced using a bipolar pacing catheter. Animals were randomized to treatment with the experimental algorithm or standard advanced cardiac life support therapy after eight minutes of untreated ventricular fibrillation. The experimental algorithm consisted of starting CPR; giving high-dose epinephrine (0.20 mg/kg), lidocaine (1.0 mg/kg), bretylium (5.0 mg/kg), and propranolol (0.5 to 1.0 mg) by peripheral IV; hyperventilating (20 to 25 breaths per minute); and delaying countershock (5 J/kg) 60 seconds after completion of drug delivery. Data were analyzed with the Student's t-test and Fisher's exact test. MEASUREMENTS AND MAIN RESULTS: Outcome variables were arterial and central venous pressures, return of spontaneous circulation, and one-hour survival. Hemodynamics were not different between groups during CPR. Return of spontaneous circulation occurred in seven of nine swine (77%) in the experimental algorithm group versus two of nine swine (22%) in the advanced cardiac life support group (P = .057). Four of nine swine (44%) in the experimental algorithm group survived to one hour versus none of the animals in the advanced cardiac life support group (P = .041). CONCLUSION: In this swine model of out-of-hospital cardiac arrest, animals treated with an experimental algorithm had a significant improvement in one-hour survival compared with those treated with advanced cardiac life support.

Algorithms↗

PubMed2000

Specific and general HLA-DR binding motifs: comparison of algorithms.

Using panels of peptides well characterized for their ability to bind to HLA DR1, DRB1*1101, or DRB1*0401 molecules, algorithms were deduced to predict binding to these molecules. These algorithms consist of blocks of 8 amino acids containing an amino acid anchor (Tyr, Phe, Trp, Leu, Ile, or Val) at position i and different amino acid combinations at positions i+2 to i+7 depending on the class II molecule. The sensitivity (% of correctly predicted binder peptides) and specificity (% of correctly predicted non-binder peptides) of these algorithms, were tested against different independent panels of peptides and compared to other algorithms reported in the literature. Similarly, using a panel of 232 peptides able to bind to one or more HLA molecules as well as 43 non-binder peptides, we deduced a general motif for the prediction of binding to HLA-DR molecules. The sensitivity and specificity of this general motif was dependent on the threshold score used for the predictions. For a score of 0.1, the sensitivity and specificity were 84.7% and 69.8%, respectively. This motif was validated against several panels of binder and non-binder peptides reported in the literature, as well as against 35, 15-mer peptides from hepatitis C virus core protein, that were synthesized and tested in a binding assay against a panel of 19 HLA-DR molecules. The sensitivities and specificities against these panels of peptides were similar to those attained against the panels used to deduce the algorithm. These results show that comparison of binder and non-binder peptides, as well as correcting for the relative abundance of amino acids in proteins, is a useful approach to deduce performing algorithms to predict binding to HLA molecules.

Algorithms↗

PubMed2001

Treatment planning using a dose-volume feasibility search algorithm.

PURPOSE: An approach to treatment plan optimization is presented that inputs dose--volume constraints and utilizes a feasibility search algorithm that seeks a set of beam weights so that the calculated dose distributions satisfy the dose--volume constraints. In contrast to a search for the "best" plan, this approach can quickly determine feasibility and point out the most restrictive of the predetermined constraints. METHODS AND MATERIALS: The cyclic subgradient projection (CSP) algorithm was modified to incorporate dose--volume constraints in a treatment plan optimization schema. The algorithm was applied to determine beam weights for several representative three-dimensional treatment plans. RESULTS: Using the modified CSP algorithm, we found that either a feasible solution to the dose--volume constraint problem was found or the program determined, after a predetermined set of iterations was performed, that no feasible solution existed for the particular set of dose--volume constraints. If no feasible solution existed, we relaxed several of the dose--volume constraints and were able to achieve a feasible solution. CONCLUSION: Feasibility search algorithms can be used in radiation treatment planning to generate a treatment plan that meets the dose--volume constraints established by the radiation oncologist. In the absence of a feasible solution, these algorithms can provide information to the radiation oncologist as to how the dose--volume constraints may be modified to achieve a feasible solution.

Algorithms↗

PubMed1999

Development and clinical implementation of an enhanced display algorithm for use in networked electronic portal imaging.

PURPOSE: To introduce and clinically validate a preprocessing algorithm that allows clinical images from an electronic portal imaging device (EPID) to be displayed on any computer monitor, without loss of clinical usability. The introduction of such a system frees EPI systems from the constraints of fixed viewing workstations and increases mobility of the images in a department. METHODS AND MATERIALS: The preprocessing algorithm, together with its variable parameters is introduced. Clinically, the algorithm is tested using an observer study of 316 EPID images of the pelvic region in the framework of treatment of carcinoma of the cervix and endometrium. Both anterior-posterior (AP/PA) and latero-lateral (LAT) images were used. The images scored were taken from six different patients, five of whom were obese, female, and postmenopausal. The result is tentatively compared with results from other groups. The scoring system, based on the number of visible landmarks in the port, is proposed and validated. Validation was performed by having the observer panel score images with artificially induced noise levels. A comparative study was undertaken with a standard automatic window and leveling display technique. Finally, some case studies using different image sites and EPI detectors are presented. RESULTS: The image quality for all images in this study was deemed to be clinically useful (mean score >1). Most of the images received a score which was second highest (AP/PA landmarks > or =6 and LAT landmarks > or =5). Obesity, which has been an important factor determining the image quality, was not seen to be a factor here. Compared to standard techniques a highly significant improvement was determined with regard to clinical usefulness. The algorithm performs fast (less than 9 seconds) and needs no additional user interaction in most of the cases. The algorithm works well on both direct detection portal imagers and camera-based imagers whether analog or digital cameras. CONCLUSIONS: We have demonstrated that it is possible to preprocess EPIs in such a way that the clinically relevant landmarks are easily detected on a generic computer screen. The algorithm is system-independent and fast. This allows for the encoding of EPIs in more generalized commercial formats so that distribution of images is facilitated.

Algorithms↗

PubMed2000

3D image registration using a fast noniterative algorithm.

This note describes the implementation of a three-dimensional (3D) registration algorithm, generalizing a previous 2D version [Alexander, Int J Imaging Systems and Technology 1999;10:242-57]. The algorithm solves an integrated form of linearized image matching equation over a set of 3D rectangular sub-volumes ('patches') in the image domain. This integrated form avoids numerical instabilities due to differentiation of a noisy image over a lattice, and in addition renders the algorithm robustness to noise. Registration is implemented by first convolving the unregistered images with a set of computationally fast [O(N)] filters, providing four bandpass images for each input image, and integrating the image matching equation over the given patch. Each filter and each patch together provide an independent set of constraints on the displacement field derived by solving a set of linear regression equations. Furthermore, the filters are implemented at a variety of spatial scales, enabling registration parameters at one scale to be used as an input approximation for deriving refined values of those parameters at a finer scale of resolution. This hierarchical procedure is necessary to avoid false matches occurring. Both downsampled and oversampled (undecimating) filtering is implemented. Although the former is computationally fast, it lacks the translation invariance of the latter. Oversampling is required for accurate interpolation that is used in intermediate stages of the algorithm to reconstruct the partially registered from the unregistered image. However, downsampling is useful, and computationally efficient, for preliminary stages of registration when large mismatches are present. The 3D registration algorithm was implemented using a 12-parameter affine model for the displacement: u(x) = Ax + b. Linear interpolation was used throughout. Accuracy and timing results for registering various multislice images, obtained by scanning a melon and human volunteers in various stationary positions, is described. The algorithm may be generalized to more general models of the displacement field, and is also well suited to parallel processing.

Algorithms↗

PubMedDate not supplied

Algorithm for determining equivalent A-constants and surgeon factors.

PURPOSE: To describe statistical algorithms for determining surgeon factors and corresponding A-constants and compare them to empirical data. METHODS: The Holladay and SRK/T equations are rearranged to develop a series of equations expressing the surgeon factor as a function of the A-constant or, alternatively, the A-constant as a function of the surgeon factor. These expressions are statistically manipulated using keratometric and axial length distributions to determined clinically equivalent A-constant-surgeon factor pairs. Predictions made by this algorithm are fit to a linear equation that accurately relates surgeon factors to equivalent A-constants and are compared to a set of corresponding A-constants and surgeons factors used by the Food and Drug Administration for labeling purposes. Algorithm performance is assessed by calculating the difference between the Holladay and SRK/T intraocular lens power equations, establishing equivalence criteria. These calculations are performed using clinically equivalent A-constant-surgeon factor pairs with an axial length and average corneal curvature corresponding to the population mean. RESULTS: The difference calculation is less than or equal to 0.02 diopter (D) for A-constants ranging between 110.0 and 120.0. A comparison of the algorithm with empirically derived corresponding A-constant-surgeon factor pairs shows that the two methods are identical for A-constants ranging between 117.0 and 119.0; however, differences in equivalent surgeon factors predicted by these methods increase with decreasing A-constants. The magnitude of this difference is 0.44 mm at an A-constant of 110.0, resulting in a difference of 0.45 D in equivalence criteria. CONCLUSIONS: These data demonstrate that the statistical algorithm provides an improvement in A-constant-surgeon factor equivalent for A-constants less than 117.0. The structure of this algorithm can easily be adapted to interrelate other pairs of personal constants and serves as a theoretical method to standardize personal constants.

Algorithms↗

PubMed2001

A globally convergent Lagrange and barrier function iterative algorithm for the traveling salesman problem.

In this paper a globally convergent Lagrange and barrier function iterative algorithm is proposed for approximating a solution of the traveling salesman problem. The algorithm employs an entropy-type barrier function to deal with nonnegativity constraints and Lagrange multipliers to handle linear equality constraints, and attempts to produce a solution of high quality by generating a minimum point of a barrier problem for a sequence of descending values of the barrier parameter. For any given value of the barrier parameter, the algorithm searches for a minimum point of the barrier problem in a feasible descent direction, which has a desired property that the nonnegativity constraints are always satisfied automatically if the step length is a number between zero and one. At each iteration the feasible descent direction is found by updating Lagrange multipliers with a globally convergent iterative procedure. For any given value of the barrier parameter, the algorithm converges to a stationary point of the barrier problem without any condition on the objective function. Theoretical and numerical results show that the algorithm seems more effective and efficient than the softassign algorithm.

Algorithms↗

PubMed2001

Estimates of average complexity of neurocontrol algorithms.

Neurocontrol algorithms can be operated in a batch mode or an incremental mode. Furthermore, some of them have variants with and without an explicit plant model. These variants exhibit fundamentally different behavior with regard to the volume of data necessary for convergence. To assess this difference, simplified algorithms in a discrete state space using the dynamic programming framework are analyzed: a batch algorithm, and two incremental algorithms with and without a plant model. Analysis shows that the batch algorithm is the fastest, while the two incremental algorithms (in particular the model-free variant) are considerably slower, measured in expected number of samples to convergence.

Algorithms↗

PubMed2002

A deterministic annealing algorithm for approximating a solution of the max-bisection problem.

The max-bisection problem is an NP-hard combinatorial optimization problem. In this paper an equivalent linearly constrained continuous optimization problem is formulated and a deterministic annealing algorithm is proposed for approximating its solution. The algorithm is derived from the introduction of a square-root barrier function, where the barrier parameter behaves as temperature in an annealing procedure and decreases from a sufficiently large positive number to 0. The algorithm searches for a better solution in a feasible descent direction, which has a desired property that lower and upper bounds on variables are always satisfied automatically if the step length is a number between 0 and 1. We prove that the algorithm converges to at least an integral local minimum point of the continuous problem if a local minimum point of the barrier problem is generated for a sequence of descending values of the barrier parameter with zero limit. Numerical results show that the algorithm is much faster than one of the best existing approximation algorithms while they produce more or less the same quality solution.

Algorithms↗