Nested Markov chain hyper-heuristic (NMHH): a hybrid hyper-heuristic framework for single-objective continuous problems.
Ontology highlight
ABSTRACT:
SUBMITTER: Bandi N
PROVIDER: S-EPMC10909227 | biostudies-literature | 2024
REPOSITORIES: biostudies-literature
Publications
Nested Markov chain hyper-heuristic (NMHH): a hybrid hyper-heuristic framework for single-objective continuous problems.
PeerJ. Computer science 20240202
This article introduces a new hybrid hyper-heuristic framework that deals with single-objective continuous optimization problems. This approach employs a nested Markov chain on the base level in the search for the best-performing operators and their sequences and simulated annealing on the hyperlevel, which evolves the chain and the operator parameters. The novelty of the approach consists of the upper level of the Markov chain expressing the hybridization of global and local search operators an ...[more]
Similar Datasets
Project description:Metabolic flux analysis (MFA), a key technology in bioinformatics, is an effective way of analyzing the entire metabolic system by measuring fluxes. Many existing MFA approaches are based on differential equations, which are complicated to be solved mathematically. So MFA requires some simple approaches to investigate metabolism further. In this article, we applied continuous-time Markov chain to MFA, called MMFA approach, and transformed the MFA problem into a set of quadratic equations by analyzing the transition probability of each carbon atom in the entire metabolic system. Unlike the other methods, MMFA analyzes the metabolic model only through the transition probability. This approach is very generic and it could be applied to any metabolic system if all the reaction mechanisms in the system are known. The results of the MMFA approach were compared with several chemical reaction equilibrium constants from early experiments by taking pentose phosphate pathway as an example.
| S-EPMC4148055 | biostudies-literature
Project description:This work considers the Bi-objective Traveling Salesman Problem (BTSP), where two conflicting objectives, the travel time and monetary cost between cities, are minimized. Our purpose is to compute the trade-off solutions that fulfill the problem requirements. We introduce a novel three-Phase Hybrid Evolutionary Algorithm (3PHEA) based on the Lin-Kernighan Heuristic, an improved version of the Non-Dominated Sorting Genetic Algorithm, and Pareto Variable Neighborhood Search, a multi-objective version of VNS. We conduct a comparative study with three existing approaches dedicated to solving BTSP. To assess the performance of algorithms, we consider 20 BTSP instances from the literature of varying degrees of difficulty (e.g., euclidean, random, mixed, etc.) and different sizes ranging from 100 to 1000 cities. We also compute several multi-objective performance indicators, including running time, coverage, hypervolume, epsilon, generational distance, inverted generational distance, spread, and generalized spread. Experimental results and comparative analysis indicate that the proposed three-phase method 3PHEA is significantly superior to existing approaches covering up to 80% of the true Pareto fronts.
| S-EPMC10017715 | biostudies-literature
Project description:To address the urgent need to accurately predict the spreading trend of the COVID-19 epidemic, a continuous Markov-chain model was, for the first time, developed in this work to predict the spread of COVID-19 infection. A probability matrix of infection was first developed in this model based upon the contact frequency of individuals within the population, the individual's characteristics, and other factors that can effectively reflect the epidemic's temporal and spatial variation characteristics. The Markov-chain model was then extended to incorporate both the mutation effect of COVID-19 and the decaying effect of antibodies. The developed comprehensive Markov-chain model that integrates the aforementioned factors was finally tested by real data to predict the trend of the COVID-19 epidemic. The result shows that our model can effectively avoid the prediction dilemma that may exist with traditional ordinary differential equations model, such as the susceptible-infectious-recovered (SIR) model. Meanwhile, it can forecast the epidemic distribution and predict the epidemic hotspots geographically at different times. It is also demonstrated in our result that the influence of the population's spatial and geographic distribution in a herd infection event is needed in the model for a better prediction of the epidemic trend. At the same time, our result indicates that no simple derivative relationship exists between the threshold of herd immunity and the virus basic reproduction number R0. The threshold of herd immunity achieved through natural immunity is significantly higher than 1 - 1/R0. These not only explain the theoretical misconceptions of herd immunity thresholds in herd immunity theory but also provide a guidance for predicting the optimal vaccination coverage. In addition, our model can predict the temporal and spatial distribution of infections in different epidemic waves. It is implied from our model that it is challenging to eradicate COVID-19 in the short term for a large population size and a wide spatial distribution. It is predicted that COVID-19 is likely to coexist with humans for a long time and that it will exhibit multipoint epidemic effects at a later stage. The statistical evidence is consistent with our prediction and strongly supports our modeling results.
| S-EPMC8869237 | biostudies-literature
Project description:Online detection of fatigued wear debris in the lubricants of aero-engines can provide warning of engine failure during flight, thus having great economic and social benefits. In this paper, we propose a capacitance array sensor and a hyper-heuristic partial differential equation (PDE) inversion method for detecting multiple micro-scale metal debris, combined with self-adaptive cellular genetic (SA-CGA) and morphological algorithms. Firstly, different from the traditional methods, which are limited in multi-induction-Dirac-boundary-inversion, a mathematical model with non-local boundary conditions is established. Furthermore, a hyper-heuristic method based on prior knowledge is also proposed to extract the wear character. Moreover, a 12-plate array circulating sensor and corresponding detection system are designed. The experimental results were compared with the optical microscopy. The results show that under the conditions of 1~3 wear debris with diameters of between 250⁻900 μm, the accuracy of the proposed method is 10⁻38% higher than those of the traditional methods. The recognition error of the wear debris counts decreases to 0.
| S-EPMC6387040 | biostudies-literature
Project description:The conditional independence structure induced on the observed marginal distribution by a hidden variable directed acyclic graph (DAG) may be represented by a graphical model represented by mixed graphs called maximal ancestral graphs (MAGs). This model has a number of desirable properties, in particular the set of Gaussian distributions can be parameterized by viewing the graph as a path diagram. Models represented by MAGs have been used for causal discovery [22], and identification theory for causal effects [28]. In addition to ordinary conditional independence constraints, hidden variable DAGs also induce generalized independence constraints. These constraints form the nested Markov property [20]. We first show that acyclic linear SEMs obey this property. Further we show that a natural parameterization for all Gaussian distributions obeying the nested Markov property arises from a generalization of maximal ancestral graphs that we call maximal arid graphs (MArG). We show that every nested Markov model can be associated with a MArG; viewed as a path diagram this MArG parametrizes the Gaussian nested Markov model. This leads directly to methods for ML fitting and computing BIC scores for Gaussian nested models.
| S-EPMC6461354 | biostudies-literature
Project description:BackgroundBiomedical ontologies have become an increasingly critical lens through which researchers analyze the genomic, clinical and bibliographic data that fuels scientific research. Of particular relevance are methods, such as enrichment analysis, that quantify the importance of ontology classes relative to a collection of domain data. Current analytical techniques, however, remain limited in their ability to handle many important types of structural complexity encountered in real biological systems including class overlaps, continuously valued data, inter-instance relationships, non-hierarchical relationships between classes, semantic distance and sparse data.ResultsIn this paper, we describe a methodology called Markov Chain Ontology Analysis (MCOA) and illustrate its use through a MCOA-based enrichment analysis application based on a generative model of gene activation. MCOA models the classes in an ontology, the instances from an associated dataset and all directional inter-class, class-to-instance and inter-instance relationships as a single finite ergodic Markov chain. The adjusted transition probability matrix for this Markov chain enables the calculation of eigenvector values that quantify the importance of each ontology class relative to other classes and the associated data set members. On both controlled Gene Ontology (GO) data sets created with Escherichia coli, Drosophila melanogaster and Homo sapiens annotations and real gene expression data extracted from the Gene Expression Omnibus (GEO), the MCOA enrichment analysis approach provides the best performance of comparable state-of-the-art methods.ConclusionA methodology based on Markov chain models and network analytic metrics can help detect the relevant signal within large, highly interdependent and noisy data sets and, for applications such as enrichment analysis, has been shown to generate superior performance on both real and simulated data relative to existing state-of-the-art approaches.
| S-EPMC3329418 | biostudies-literature
Project description:BackgroundOver the last decade genetic marker-based plant breeding strategies have gained increasing attention because genotyping technologies are no longer limiting. Now the challenge is to optimally use genetic markers in practical breeding schemes. For simple traits such as some disease resistances it is possible to target a fixed multi-locus allele configuration at a small number of causal or linked loci. Efficiently obtaining this genetic ideotype from a given set of parental genotypes is known as the marker-assisted gene pyramiding problem. Previous methods either imposed strong restrictions or used black box integer programming solutions, while this paper explores the power of an explicit heuristic approach that exploits the underlying genetic structure to prune the search space.ResultsGene Stacker is introduced as a novel approach to marker-assisted gene pyramiding, combining an explicit directed acyclic graph model with a pruned generation algorithm inspired by a simple exhaustive search. Both exact and heuristic pruning criteria are applied to reduce the number of generated schedules. It is shown that this approach can effectively be used to obtain good solutions for stacking problems of varying complexity. For more complex problems, the heuristics allow to obtain valuable approximations. For smaller problems, fewer heuristics can be applied, resulting in an interesting quality-runtime tradeoff. Gene Stacker is competitive with previous methods and often finds better and/or additional solutions within reasonable time, because of the powerful heuristics.ConclusionsThe proposed approach was confirmed to be feasible in combination with heuristics to cope with realistic, complex stacking problems. The inherent flexibility of this approach allows to easily address important breeding constraints so that the obtained schedules can be widely used in practice without major modifications. In addition, the ideas applied for Gene Stacker can be incorporated in and extended for a plant breeding context that e.g. also addresses complex quantitative traits or conservation of genetic background. Gene Stacker is freely available as open source software at http://genestacker.ugent.be . The website also provides documentation and examples of how to use Gene Stacker.
| S-EPMC4332449 | biostudies-literature
Project description:Heuristics and the application of fast-and-frugal trees may play a role in establishing a clinical decision-making framework for value-based oncology. We determined whether clinical decision-making in oncology can be structured heuristically based on the timeline of the patient's treatment, clinical intuition, and evidence-based medicine. A group of 20 patients with advanced non-small cell lung cancer (NSCLC) were enrolled into the study for extensive treatment analysis and sequential decision-making. The extensive clinical and genomic data allowed us to evaluate the methodology and efficacy of fast-and-frugal trees as a way to quantify clinical decision-making. The results of the small cohort will be used to further advance the heuristic framework as a way of evaluating a large number of patients within registries. Among the cohort whose data was analyzed, substitution and amplification mutations occurred most frequently. The top five most prevalent genomic alterations were TP53 (45%), ALK (40%), LRP1B (30%), CDKN2A (25%), and MYC (25%). These 20 cases were analyzed by this clinical decision-making process and separated into two distinctions: 10 straightforward cases that represented a clearer decision-making path and 10 complex cases that represented a more intricate treatment pathway. The myriad of information from each case and their distinct pathways was applied to create the foundation of a framework for lung cancer decision-making as an aid for oncologists. In late-stage lung cancer patients, the fast-and-frugal heuristics can be utilized as a strategy of quantifying proper decision-making with limited information.
| S-EPMC6057456 | biostudies-literature
Project description:Forced-choice questionnaires have been proposed as a way to control some response biases associated with traditional questionnaire formats (e.g., Likert-type scales). Whereas classical scoring methods have issues of ipsativity, item response theory (IRT) methods have been claimed to accurately account for the latent trait structure of these instruments. In this article, the authors propose the multi-unidimensional pairwise preference two-parameter logistic (MUPP-2PL) model, a variant within Stark, Chernyshenko, and Drasgow's MUPP framework for items that are assumed to fit a dominance model. They also introduce a Markov Chain Monte Carlo (MCMC) procedure for estimating the model's parameters. The authors present the results of a simulation study, which shows appropriate goodness of recovery in all studied conditions. A comparison of the newly proposed model with a Brown and Maydeu's Thurstonian IRT model led us to the conclusion that both models are theoretically very similar and that the Bayesian estimation procedure of the MUPP-2PL may provide a slightly better recovery of the latent space correlations and a more reliable assessment of the latent trait estimation errors. An application of the model to a real data set shows convergence between the two estimation procedures. However, there is also evidence that the MCMC may be advantageous regarding the item parameters and the latent trait correlations.
| S-EPMC5978637 | biostudies-literature
Project description:We present new methodology based on Multi-Objective Markov Decision Processes for developing sequential decision support systems from data. Our approach uses sequential decision-making data to provide support that is useful to many different decision-makers, each with different, potentially time-varying preference. To accomplish this, we develop an extension of fitted-Q iteration for multiple objectives that computes policies for all scalarization functions, i.e. preference functions, simultaneously from continuous-state, finite-horizon data. We identify and address several conceptual and computational challenges along the way, and we introduce a new solution concept that is appropriate when different actions have similar expected outcomes. Finally, we demonstrate an application of our method using data from the Clinical Antipsychotic Trials of Intervention Effectiveness and show that our approach offers decision-makers increased choice by a larger class of optimal policies.
| S-EPMC5179144 | biostudies-literature