A Comparison of Multiple Objective Algorithms in the Context of a Dial a Ride Problem
Ontology highlight
ABSTRACT:
SUBMITTER: Krzhizhanovskaya V
PROVIDER: S-EPMC7304764 | biostudies-literature | 2020 May
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:Dial a ride problem (DARP) is a complex version of the pick-up and delivery problem with many practical applications in the field of transportation. This study proposes an enhanced deterministic annealing algorithm for the solution of large-scale multi-vehicle DARPs. The proposed method always explores the feasible search space; therefore, a feasible solution is guaranteed at any point of termination. This method utilises advanced local search operators to accelerate the search for optimal solutions and it relies on a linearly decreasing deterministic annealing schedule to limit poor jumps during the course of search. This study puts forward a systematic series of experiments to compare the performance of solution methods from various angles. The proposed method is compared with the most efficient methods reported in the literature i.e., the Adaptive Large Neighbourhood Search (ALNS), Evolutionary Local Search (ELS), and Deterministic Annealing (DA) using standard benchmarks. The results suggest that the proposed algorithm is on average faster than the state-of-the-art algorithms in reaching competitive objective values across the range of benchmarks.
| S-EPMC10852268 | biostudies-literature
Project description:We present a combined report on the results of three editions of the Cell Tracking Challenge, an ongoing initiative aimed at promoting the development and objective evaluation of cell segmentation and tracking algorithms. With 21 participating algorithms and a data repository consisting of 13 data sets from various microscopy modalities, the challenge displays today's state-of-the-art methodology in the field. We analyzed the challenge results using performance measures for segmentation and tracking that rank all participating methods. We also analyzed the performance of all of the algorithms in terms of biological measures and practical usability. Although some methods scored high in all technical aspects, none obtained fully correct solutions. We found that methods that either take prior information into account using learning strategies or analyze cells in a global spatiotemporal video context performed better than other methods under the segmentation and tracking scenarios included in the challenge.
| S-EPMC5777536 | biostudies-literature
Project description:Coordinating the charging scheduling of electric vehicles for dynamic dial-a-ride services is challenging considering charging queuing delays and stochastic customer demand. We propose a new two-stage solution approach to handle dynamic vehicle charging scheduling to minimize the costs of daily charging operations of the fleet. The approach comprises two components: daily vehicle charging scheduling and online vehicle-charger assignment. A new battery replenishment model is proposed to obtain the vehicle charging schedules by minimizing the costs of vehicle daily charging operations while satisfying vehicle driving needs to serve customers. In the second stage, an online vehicle-charger assignment model is developed to minimize the total vehicle idle time for charges by considering queuing delays at the level of chargers. An efficient Lagrangian relaxation algorithm is proposed to solve the large-scale vehicle-charger assignment problem with small optimality gaps. The approach is applied to a realistic dynamic dial-a-ride service case study in Luxembourg and compared with the nearest charging station charging policy and first-come-first-served minimum charging delay policy under different charging infrastructure scenarios. Our computational results show that the approach can achieve significant savings for the operator in terms of charging waiting times (-74.9%), charging times (-38.6%), and charged energy costs (-27.4%). A sensitivity analysis is conducted to evaluate the impact of the different model parameters, showing the scalability and robustness of the approach in a stochastic environment.
| S-EPMC8136635 | biostudies-literature
Project description:We present a comprehensive analysis of the submissions to the first edition of the Endoscopy Artefact Detection challenge (EAD). Using crowd-sourcing, this initiative is a step towards understanding the limitations of existing state-of-the-art computer vision methods applied to endoscopy and promoting the development of new approaches suitable for clinical translation. Endoscopy is a routine imaging technique for the detection, diagnosis and treatment of diseases in hollow-organs; the esophagus, stomach, colon, uterus and the bladder. However the nature of these organs prevent imaged tissues to be free of imaging artefacts such as bubbles, pixel saturation, organ specularity and debris, all of which pose substantial challenges for any quantitative analysis. Consequently, the potential for improved clinical outcomes through quantitative assessment of abnormal mucosal surface observed in endoscopy videos is presently not realized accurately. The EAD challenge promotes awareness of and addresses this key bottleneck problem by investigating methods that can accurately classify, localize and segment artefacts in endoscopy frames as critical prerequisite tasks. Using a diverse curated multi-institutional, multi-modality, multi-organ dataset of video frames, the accuracy and performance of 23 algorithms were objectively ranked for artefact detection and segmentation. The ability of methods to generalize to unseen datasets was also evaluated. The best performing methods (top 15%) propose deep learning strategies to reconcile variabilities in artefact appearance with respect to size, modality, occurrence and organ type. However, no single method outperformed across all tasks. Detailed analyses reveal the shortcomings of current training strategies and highlight the need for developing new optimal metrics to accurately quantify the clinical applicability of methods.
| S-EPMC7026422 | biostudies-literature
Project description:The importance of the time-cost-quality trade-off problem in construction projects has been widely recognized. Its goal is to minimize time and cost and maximize quality. In this paper, the bonus-penalty mechanism is introduced to improve the traditional time-cost model, and considering the nonlinear relationship between quality and time, a nonlinear time-cost quality model is established. Meanwhile, in order to better solve the time-cost-quality trade-off problem, a multi-objective immune wolf colony optimization algorithm has been proposed. The hybrid method combines the fast convergence of the wolf colony algorithm and the excellent diversity of the immune algorithm to improve the accuracy of the wolf colony search process. Finally, a railway construction project is taken as an example to prove the effectiveness of the method.
| S-EPMC9910742 | biostudies-literature
Project description:BACKGROUND:Structural variations (SVs) have been reported to play an important role in genetic diversity and trait regulation. Many computer algorithms detecting SVs have recently been developed, but the use of multiple algorithms to detect high-confidence SVs has not been studied. The most suitable sequencing depth for detecting SVs in pear is also not known. RESULTS:In this study, a pipeline to detect SVs using next-generation and long-read sequencing data was constructed. The performances of seven types of SV detection software using next-generation sequencing (NGS) data and two types of software using long-read sequencing data (SVIM and Sniffles), which are based on different algorithms, were compared. Of the nine software packages evaluated, SVIM identified the most SVs, and Sniffles detected SVs with the highest accuracy (> 90%). When the results from multiple SV detection tools were combined, the SVs identified by both MetaSV and IMR/DENOM, which use NGS data, were more accurate than those identified by both SVIM and Sniffles, with mean accuracies of 98.7 and 96.5%, respectively. The software packages using long-read sequencing data required fewer CPU cores and less memory and ran faster than those using NGS data. In addition, according to the performances of assembly-based algorithms using NGS data, we found that a sequencing depth of 50× is appropriate for detecting SVs in the pear genome. CONCLUSION:This study provides strong evidence that more than one SV detection software package, each based on a different algorithm, should be used to detect SVs with higher confidence, and that long-read sequencing data are better than NGS data for SV detection. The SV detection pipeline that we have established will facilitate the study of diversity in other crops.
| S-EPMC6972009 | biostudies-literature
Project description:In recent years, researchers have taken the many-objective optimization algorithm, which can optimize 5, 8, 10, 15, 20 objective functions simultaneously, as a new research topic. However, the current research on many-objective optimization technology also encounters some challenges. For example: Pareto resistance phenomenon, difficult diversity maintenance. Based on the above problems, this paper proposes a many-objective evolutionary algorithm based on three states (MOEA/TS). Firstly, a feature extraction operator is proposed. It can extract the features of the high-quality solution set, and then assist the evolution of the current individual. Secondly, based on Pareto front layer, the concept of "individual importance degree" is proposed. The importance degree of an individual can reflect the importance of the individual in the same Pareto front layer, so as to further distinguish the advantages and disadvantages of different individuals in the same front layer. Then, a repulsion field method is proposed. The diversity of the population in the objective space is maintained by the repulsion field, so that the population can be evenly distributed on the real Pareto front. Finally, a new concurrent algorithm framework is designed. In the algorithm framework, the algorithm is divided into three states, and each state focuses on a specific task. The population can switch freely among these three states according to its own evolution. The MOEA/TS algorithm is compared with 7 advanced many-objective optimization algorithms. The experimental results show that the MOEA/TS algorithm is more competitive in many-objective optimization problems.
| S-EPMC11333576 | biostudies-literature
Project description:BackgroundThe maximum clique enumeration (MCE) problem asks that we identify all maximum cliques in a finite, simple graph. MCE is closely related to two other well-known and widely-studied problems: the maximum clique optimization problem, which asks us to determine the size of a largest clique, and the maximal clique enumeration problem, which asks that we compile a listing of all maximal cliques. Naturally, these three problems are NP-hard, given that they subsume the classic version of the NP-complete clique decision problem. MCE can be solved in principle with standard enumeration methods due to Bron, Kerbosch, Kose and others. Unfortunately, these techniques are ill-suited to graphs encountered in our applications. We must solve MCE on instances deeply seeded in data mining and computational biology, where high-throughput data capture often creates graphs of extreme size and density. MCE can also be solved in principle using more modern algorithms based in part on vertex cover and the theory of fixed-parameter tractability (FPT). While FPT is an improvement, these algorithms too can fail to scale sufficiently well as the sizes and densities of our datasets grow.ResultsAn extensive testbed of benchmark graphs are created using publicly available transcriptomic datasets from the Gene Expression Omnibus (GEO). Empirical testing reveals crucial but latent features of such high-throughput biological data. In turn, it is shown that these features distinguish real data from random data intended to reproduce salient topological features. In particular, with real data there tends to be an unusually high degree of maximum clique overlap. Armed with this knowledge, novel decomposition strategies are tuned to the data and coupled with the best FPT MCE implementations.ConclusionsSeveral algorithmic improvements to MCE are made which progressively decrease the run time on graphs in the testbed. Frequently the final runtime improvement is several orders of magnitude. As a result, instances which were once prohibitively time-consuming to solve are brought into the domain of realistic feasibility.
| S-EPMC3382443 | biostudies-literature
Project description:Machine learning methods are attracting considerable attention from the pharmaceutical industry for use in drug discovery and applications beyond. In recent studies, we and others have applied multiple machine learning algorithms and modeling metrics and, in some cases, compared molecular descriptors to build models for individual targets or properties on a relatively small scale. Several research groups have used large numbers of datasets from public databases such as ChEMBL in order to evaluate machine learning methods of interest to them. The largest of these types of studies used on the order of 1400 datasets. We have now extracted well over 5000 datasets from CHEMBL for use with the ECFP6 fingerprint and in comparison of our proprietary software Assay Central with random forest, k-nearest neighbors, support vector classification, naïve Bayesian, AdaBoosted decision trees, and deep neural networks (three layers). Model performance was assessed using an array of fivefold cross-validation metrics including area-under-the-curve, F1 score, Cohen's kappa, and Matthews correlation coefficient. Based on ranked normalized scores for the metrics or datasets, all methods appeared comparable, while the distance from the top indicated that Assay Central and support vector classification were comparable. Unlike prior studies which have placed considerable emphasis on deep neural networks (deep learning), no advantage was seen in this case. If anything, Assay Central may have been at a slight advantage as the activity cutoff for each of the over 5000 datasets representing over 570,000 unique compounds was based on Assay Central performance, although support vector classification seems to be a strong competitor. We also applied Assay Central to perform prospective predictions for the toxicity targets PXR and hERG to further validate these models. This work appears to be the largest scale comparison of these machine learning algorithms to date. Future studies will likely evaluate additional databases, descriptors, and machine learning algorithms and further refine the methods for evaluating and comparing such models.
| S-EPMC8237624 | biostudies-literature
Project description:Colonies of the arboreal turtle ant create networks of trails that link nests and food sources on the graph formed by branches and vines in the canopy of the tropical forest. Ants put down a volatile pheromone on the edges as they traverse them. At each vertex, the next edge to traverse is chosen using a decision rule based on the current pheromone level. There is a bidirectional flow of ants around the network. In a previous field study, it was observed that the trail networks approximately minimize the number of vertices, thus solving a variant of the popular shortest path problem without any central control and with minimal computational resources. We propose a biologically plausible model, based on a variant of the reinforced random walk on a graph, which explains this observation and suggests surprising algorithms for the shortest path problem and its variants. Through simulations and analysis, we show that when the rate of flow of ants does not change, the dynamics converges to the path with the minimum number of vertices, as observed in the field. The dynamics converges to the shortest path when the rate of flow increases with time, so the colony can solve the shortest path problem merely by increasing the flow rate. We also show that to guarantee convergence to the shortest path, bidirectional flow and a decision rule dividing the flow in proportion to the pheromone level are necessary, but convergence to approximately short paths is possible with other decision rules.
| S-EPMC9963535 | biostudies-literature