Similar Journals
|
Algorithms
Number of Followers: 13  Open Access journalISSN (Print) 1999-4893 This journal is no longer being updated because: RSS is returning 403 Forbidden |
- Algorithms, Vol. 15, Pages 1: Towards Bio-Inspired Anomaly Detection Using
the Cursory Dendritic Cell Algorithm
Authors: Carlos Pinto, Rui Pinto, Gil Gonçalves
First page: 1
Abstract: The autonomous and adaptable identification of anomalies in industrial contexts, particularly in the physical processes of Cyber-Physical Production Systems (CPPS), requires using critical technologies to identify failures correctly. Most of the existing solutions in the anomaly detection research area do not consider such systems’ dynamics. Due to the complexity and multidimensionality of CPPS, a scalable, adaptable, and rapid anomaly detection system is needed, considering the new design specifications of Industry 4.0 solutions. Immune-based models, such as the Dendritic Cell Algorithm (DCA), may provide a rich source of inspiration for detecting anomalies, since the anomaly detection problem in CPPS greatly resembles the functionality of the biological dendritic cells in defending the human body from hazardous pathogens. This paper tackles DCA limitations that may compromise its usage in anomaly detection applications, such as the manual characterization of safe and danger signals, data analysis not suitable for online classification, and the lack of an object-oriented implementation of the algorithm. The proposed approach, the Cursory Dendritic Cell Algorithm (CDCA), is a novel variation of the DCA, developed to be flexible and monitor physical industrial processes continually while detecting anomalies in an online fashion. This work’s contribution is threefold. First, it provides a comprehensive review of Artificial Immune Systems (AIS), focusing on AIS applied to the anomaly detection problem. Then, a new object-oriented architecture for the DCA implementation is described, enabling the modularity and abstraction of the algorithm stages into different classes (modules). Finally, the CDCA for the anomaly detection problem is proposed. The CDCA was successfully validated in two industrial-oriented dataset benchmarks for physical anomaly and network intrusion detection, the Skoltech Anomaly Benchmark (SKAB) and M2M using OPC UA. When compared to other algorithms, the proposed approach exhibits promising classification results. It was placed fourth on the SKAB scoreboard and presented a competitive performance with the incremental Dendritic Cell Algorithm (iDCA).
Citation: Algorithms
PubDate: 2021-12-21
DOI: 10.3390/a15010001
Issue No: Vol. 15, No. 1 (2021)
- Algorithms, Vol. 15, Pages 2: Preconditioning the Quad Dominant Mesh
Generator for Ship Structural Analysis
Authors: Luka Grubišić, Domagoj Lacmanović, Josip Tambača
First page: 2
Abstract: This paper presents an algorithm for the fully automatic mesh generation for the finite element analysis of ships and offshore structures. The quality requirements on the mesh generator are imposed by the acceptance criteria of the classification societies as well as the need to avoid shear locking when using low degree shell elements. The meshing algorithm will be generating quadrilateral dominated meshes (consisting of quads and triangles) and the mesh quality requirements mandate that quadrilaterals with internal angles close to 90° are to be preferred. The geometry is described by a dictionary containing points, rods, surfaces, and openings. The first part of the proposed method consists of an algorithm to automatically clean the geometry. The corrected geometry is then meshed by the frontal Delaunay mesh generator as implemented in the gmsh package. We present a heuristic method to precondition the cross field of the fronatal quadrilateral mesher. In addition, the influence of the order in which the plates are meshed will be explored as a preconditioning step.
Citation: Algorithms
PubDate: 2021-12-24
DOI: 10.3390/a15010002
Issue No: Vol. 15, No. 1 (2021)
- Algorithms, Vol. 15, Pages 3: An Efficient Kriging Modeling Method Based
on Multidimensional Scaling for High-Dimensional Problems
Authors: Yu Ge, Junjun Shi, Yaohui Li, Jingfang Shen
First page: 3
Abstract: Kriging-based modeling has been widely used in computationally intensive simulations. However, the Kriging modeling of high-dimensional problems not only takes more time, but also leads to the failure of model construction. To this end, a Kriging modeling method based on multidimensional scaling (KMDS) is presented to avoid the “dimensional disaster”. Under the condition of keeping the distance between the sample points before and after the dimensionality reduction unchanged, the KMDS method, which mainly calculates each element in the inner product matrix due to the mapping relationship between the distance matrix and the inner product matrix, completes the conversion of design data from high dimensional to low dimensional. For three benchmark functions with different dimensions and the aviation field problem of aircraft longitudinal flight control, the proposed method is compared with other dimensionality reduction methods. The KMDS method has better modeling efficiency while meeting certain accuracy requirements.
Citation: Algorithms
PubDate: 2021-12-23
DOI: 10.3390/a15010003
Issue No: Vol. 15, No. 1 (2021)
- Algorithms, Vol. 15, Pages 4: A New Algorithm for Simultaneous Retrieval
of Aerosols and Marine Parameters
Authors: Taddeo Ssenyonga, Øyvind Frette, Børge Hamre, Knut Stamnes, Dennis Muyimbwa, Nicolausi Ssebiyonga, Jakob J. Stamnes
First page: 4
Abstract: We present an algorithm for simultaneous retrieval of aerosol and marine parameters in coastal waters. The algorithm is based on a radiative transfer forward model for a coupled atmosphere-ocean system, which is used to train a radial basis function neural network (RBF-NN) to obtain a fast and accurate method to compute radiances at the top of the atmosphere (TOA) for given aerosol and marine input parameters. The inverse modelling algorithm employs multidimensional unconstrained non-linear optimization to retrieve three marine parameters (concentrations of chlorophyll and mineral particles, as well as absorption by coloured dissolved organic matter (CDOM)), and two aerosol parameters (aerosol fine-mode fraction and aerosol volume fraction). We validated the retrieval algorithm using synthetic data and found it, for both low and high sun, to predict each of the five parameters accurately, both with and without white noise added to the top of the atmosphere (TOA) radiances. When varying the solar zenith angle (SZA) and retraining the RBF-NN without noise added to the TOA radiance, we found the algorithm to predict the CDOM absorption, chlorophyll concentration, mineral concentration, aerosol fine-mode fraction, and aerosol volume fraction with correlation coefficients greater than 0.72, 0.73, 0.93, 0.67, and 0.87, respectively, for 45∘≤ SZA ≤ 75∘. By adding white Gaussian noise to the TOA radiances with varying values of the signal-to-noise-ratio (SNR), we found the retrieval algorithm to predict CDOM absorption, chlorophyll concentration, mineral concentration, aerosol fine-mode fraction, and aerosol volume fraction well with correlation coefficients greater than 0.77, 0.75, 0.91, 0.81, and 0.86, respectively, for high sun and SNR ≥ 95.
Citation: Algorithms
PubDate: 2021-12-24
DOI: 10.3390/a15010004
Issue No: Vol. 15, No. 1 (2021)
- Algorithms, Vol. 15, Pages 5: Deep Transfer Learning for Parkinson’s
Disease Monitoring by Image-Based Representation of Resting-State EEG
Using Directional Connectivity
Authors: Emad Arasteh Emamzadeh-Hashemi, Ailar Mahdizadeh, Maryam S. Mirian, Soojin Lee, Martin J. McKeown
First page: 5
Abstract: Parkinson’s disease (PD) is characterized by abnormal brain oscillations that can change rapidly. Tracking neural alternations with high temporal resolution electrophysiological monitoring methods such as EEG can lead to valuable information about alterations observed in PD. Concomitantly, there have been advances in the high-accuracy performance of deep neural networks (DNNs) using few-patient data. In this study, we propose a method to transform resting-state EEG data into a deep latent space to classify PD subjects from healthy cases. We first used a general orthogonalized directed coherence (gOPDC) method to compute directional connectivity (DC) between all pairwise EEG channels in four frequency bands (Theta, Alpha, Beta, and Gamma) and then converted the DC maps into 2D images. We then used the VGG-16 architecture (trained on the ImageNet dataset) as our pre-trained model, enlisted weights of convolutional layers as initial weights, and fine-tuned all layer weights with our data. After training, the classification achieved 99.62% accuracy, 100% precision, 99.17% recall, 0.9958 F1 score, and 0.9958 AUC averaged for 10 random repetitions of training/evaluating on the proposed deep transfer learning (DTL) network. Using the latent features learned by the network and employing LASSO regression, we found that latent features (as opposed to the raw DC values) were significantly correlated with five clinical indices routinely measured: left and right finger tapping, left and right tremor, and body bradykinesia. Our results demonstrate the power of transfer learning and latent space derivation for the development of oscillatory biomarkers in PD.
Citation: Algorithms
PubDate: 2021-12-24
DOI: 10.3390/a15010005
Issue No: Vol. 15, No. 1 (2021)
- Algorithms, Vol. 15, Pages 6: Accelerating Symmetric Rank-1 Quasi-Newton
Method with Nesterov’s Gradient for Training Neural Networks
Authors: S. Indrapriyadarsini, Shahrzad Mahboubi, Hiroshi Ninomiya, Takeshi Kamio, Hideki Asai
First page: 6
Abstract: Gradient-based methods are popularly used in training neural networks and can be broadly categorized into first and second order methods. Second order methods have shown to have better convergence compared to first order methods, especially in solving highly nonlinear problems. The BFGS quasi-Newton method is the most commonly studied second order method for neural network training. Recent methods have been shown to speed up the convergence of the BFGS method using the Nesterov’s acclerated gradient and momentum terms. The SR1 quasi-Newton method, though less commonly used in training neural networks, is known to have interesting properties and provide good Hessian approximations when used with a trust-region approach. Thus, this paper aims to investigate accelerating the Symmetric Rank-1 (SR1) quasi-Newton method with the Nesterov’s gradient for training neural networks, and to briefly discuss its convergence. The performance of the proposed method is evaluated on a function approximation and image classification problem.
Citation: Algorithms
PubDate: 2021-12-24
DOI: 10.3390/a15010006
Issue No: Vol. 15, No. 1 (2021)
- Algorithms, Vol. 15, Pages 7: Modeling of the 5G-Band Patch Antennas Using
ANNs under the Uncertainty of the Geometrical Design Parameters Associated
with the Manufacturing Process
Authors: Piotr Górniak
First page: 7
Abstract: In the paper, the author deals with modeling the stochastic behavior of ordinary patch antennas in terms of the mean and standard deviation of their reflection coefficient S11 under the geometrical uncertainty associated with their manufacturing process. The Artificial Neural Network is used to model the stochastic reflection coefficient of the antennas. The Polynomial Chaos Expansion and FDTD computations are used to obtain the training and testing data for the Artificial Neural Network. For the first time, the author uses his analytical transformations to reduce the required number of highly time-consuming FDTD simulations for a given set of nominal values of the design parameters of the ordinary patch antenna. An analysis is performed for n257 and n258 frequency bands (24.5–28.7 GHz). The probability distributions of the design parameters are extracted from the measurement results obtained for a series of manufactured patch antenna arrays for three different frequencies in the C, X, and Ka bands. Patch antennas are chosen as the subject of the scientific analysis in this paper because of the popularity of the patch antennas in the scientific literature concerning antennas, as well as because of a simple form of these antennas that is reflected in the time required for computation of training and testing data for the Artificial Neural Network.
Citation: Algorithms
PubDate: 2021-12-24
DOI: 10.3390/a15010007
Issue No: Vol. 15, No. 1 (2021)
- Algorithms, Vol. 15, Pages 8: Finite-Time Control of Singular Linear
Semi-Markov Jump Systems
Authors: Xiaofu Ji, Xuehua Liu
First page: 8
Abstract: The problem of finite-time control for singular linear semi-Markov jump systems (SMJSs) with unknown transition rates is considered in this paper. By designing a new semi-positive definite Lyapunov-like function, state feedback controller design methods are given that allow closed-loop singular linear SMJSs to be regular, impulse-free and stochastically finite-time-stable without external disturbance, and stochastically finite-time bounded with external disturbance. The obtained conditions are expressed by a set of strict matrix inequalities, which can be simplified to a set of linear matrix inequalities by a one dimensional search for a scalar. Two numerical examples are given to illustrate the effectiveness of proposed method.
Citation: Algorithms
PubDate: 2021-12-24
DOI: 10.3390/a15010008
Issue No: Vol. 15, No. 1 (2021)
- Algorithms, Vol. 15, Pages 9: Hyper-Heuristic Based on ACO and Local
Search for Dynamic Optimization Problems
Authors: Felipe Martins Müller, Iaê Santos Bonilha
First page: 9
Abstract: Hyper-heuristics comprise a set of approaches that are motivated (at least in part) by the objective of intelligently combining heuristic methods to solve hard optimization problems. Ant colony optimization (ACO) algorithms have been proven to deal with Dynamic Optimization Problems (DOPs) properly. Despite the good results obtained by the integration of local search operators with ACO, little has been done to tackle DOPs. In this research, one of the most reliable ACO schemes, the MAX-MIN Ant System (MMAS), has been integrated with advanced and effective local search operators, resulting in an innovative hyper-heuristic. The local search operators are the Lin–Kernighan (LK) and the Unstringing and Stringing (US) heuristics, and they were intelligently chosen to improve the solution obtained by ACO. The proposed method aims to combine the adaptation capabilities of ACO for DOPs and the good performance of the local search operators chosen in an adaptive way and based on their performance, creating in this way a hyper-heuristic. The travelling salesman problem (TSP) was the base problem to generate both symmetric and asymmetric dynamic test cases. Experiments have shown that the MMAS provides good initial solutions to the local search operators and the hyper-heuristic creates a robust and effective method for the vast majority of test cases.
Citation: Algorithms
PubDate: 2021-12-24
DOI: 10.3390/a15010009
Issue No: Vol. 15, No. 1 (2021)
- Algorithms, Vol. 14, Pages 339: A Rule Extraction Technique Applied to
Ensembles of Neural Networks, Random Forests, and Gradient-Boosted Trees
Authors: Guido Bologna
First page: 339
Abstract: In machine learning, ensembles of models based on Multi-Layer Perceptrons (MLPs) or decision trees are considered successful models. However, explaining their responses is a complex problem that requires the creation of new methods of interpretation. A natural way to explain the classifications of the models is to transform them into propositional rules. In this work, we focus on random forests and gradient-boosted trees. Specifically, these models are converted into an ensemble of interpretable MLPs from which propositional rules are produced. The rule extraction method presented here allows one to precisely locate the discriminating hyperplanes that constitute the antecedents of the rules. In experiments based on eight classification problems, we compared our rule extraction technique to “Skope-Rules” and other state-of-the-art techniques. Experiments were performed with ten-fold cross-validation trials, with propositional rules that were also generated from ensembles of interpretable MLPs. By evaluating the characteristics of the extracted rules in terms of complexity, fidelity, and accuracy, the results obtained showed that our rule extraction technique is competitive. To the best of our knowledge, this is one of the few works showing a rule extraction technique that has been applied to both ensembles of decision trees and neural networks.
Citation: Algorithms
PubDate: 2021-11-23
DOI: 10.3390/a14120339
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 340: Overview of Algorithms for Using Particle
Morphology in Pre-Detonation Nuclear Forensics
Authors: Tom Burr, Ian Schwerdt, Kari Sentz, Luther McDonald, Marianne Wilkerson
First page: 340
Abstract: A major goal in pre-detonation nuclear forensics is to infer the processing conditions and/or facility type that produced radiological material. This review paper focuses on analyses of particle size, shape, texture (“morphology”) signatures that could provide information on the provenance of interdicted materials. For example, uranium ore concentrates (UOC or yellowcake) include ammonium diuranate (ADU), ammonium uranyl carbonate (AUC), sodium diuranate (SDU), magnesium diuranate (MDU), and others, each prepared using different salts to precipitate U from solution. Once precipitated, UOCs are often dried and calcined to remove adsorbed water. The products can be allowed to react further, forming uranium oxides UO3, U3O8, or UO2 powders, whose surface morphology can be indicative of precipitation and/or calcination conditions used in their production. This review paper describes statistical issues and approaches in using quantitative analyses of measurements such as particle size and shape to infer production conditions. Statistical topics include multivariate t tests (Hotelling’s T2), design of experiments, and several machine learning (ML) options including decision trees, learning vector quantization neural networks, mixture discriminant analysis, and approximate Bayesian computation (ABC). ABC is emphasized as an attractive option to include the effects of model uncertainty in the selected and fitted forward model used for inferring processing conditions.
Citation: Algorithms
PubDate: 2021-11-24
DOI: 10.3390/a14120340
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 341: A Blockchain-Based Audit Trail Mechanism:
Design and Implementation
Authors: Cristina Regueiro, Iñaki Seco, Iván Gutiérrez-Agüero, Borja Urquizu, Jason Mansell
First page: 341
Abstract: Audit logs are a critical component in today’s enterprise business systems as they provide several benefits such as records transparency and integrity and security of sensitive information by creating a layer of evidential support. However, current implementations are vulnerable to attacks on data integrity or availability. This paper presents a Blockchain-based audit trail mechanism that leverages the security features of Blockchain to enable secure and reliable audit trails and to address the aforementioned vulnerabilities. The architecture design and specific implementation are described in detail, resulting in a real prototype of a reliable, secure, and user-friendly audit trail mechanism.
Citation: Algorithms
PubDate: 2021-11-26
DOI: 10.3390/a14120341
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 342: An O(log2N) Fully-Balanced Resampling
Algorithm for Particle Filters on Distributed Memory Architectures
Authors: Alessandro Varsi, Simon Maskell, Paul G. Spirakis
First page: 342
Abstract: Resampling is a well-known statistical algorithm that is commonly applied in the context of Particle Filters (PFs) in order to perform state estimation for non-linear non-Gaussian dynamic models. As the models become more complex and accurate, the run-time of PF applications becomes increasingly slow. Parallel computing can help to address this. However, resampling (and, hence, PFs as well) necessarily involves a bottleneck, the redistribution step, which is notoriously challenging to parallelize if using textbook parallel computing techniques. A state-of-the-art redistribution takes O((log2N)2) computations on Distributed Memory (DM) architectures, which most supercomputers adopt, whereas redistribution can be performed in O(log2N) on Shared Memory (SM) architectures, such as GPU or mainstream CPUs. In this paper, we propose a novel parallel redistribution for DM that achieves an O(log2N) time complexity. We also present empirical results that indicate that our novel approach outperforms the O((log2N)2) approach.
Citation: Algorithms
PubDate: 2021-11-26
DOI: 10.3390/a14120342
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 343: Algorithmic Design of an FPGA-Based
Calculator for Fast Evaluation of Tsunami Wave Danger
Authors: Mikhail Lavrentiev, Konstantin Lysakov, Andrey Marchuk, Konstantin Oblaukhov, Mikhail Shadrin
First page: 343
Abstract: Events of a seismic nature followed by catastrophic floods caused by tsunami waves (the incidence of which has increased in recent decades) have an important impact on the populations of littoral regions. On the coast of Japan and Kamchatka, it takes nearly 20 min for tsunami waves to approach the nearest dry land after an offshore seismic event. This paper addresses an important question of fast simulation of tsunami wave propagation by mapping the algorithms in use in field-programmable gate arrays (FPGAs) with the help of high-level synthesis (HLS). Wave propagation is described by the shallow water system, and for numerical treatment the MacCormack scheme is used. The MacCormack algorithm is a direct difference scheme at a three-point stencil of a “cross” type; it happens to be appropriate for FPGA-based parallel implementation. A specialized calculator was designed. The developed software was tested for precision and performance. Numerical tests computing wave fronts show very good agreement with the available exact solutions (for two particular cases of the sea bed topography) and with the reference code. As the result, it takes just 17.06 s to simulate 1600 s (3200 time steps) of the wave propagation using a 3000 × 3200 computation grid with a VC709 board. The step length of the computational grid was chosen to display the simulation results in sufficient detail along the coastline. At the same time, the size of data arrays should provide their free placement in the memory of FPGA chips. The rather high performance achieved shows that tsunami danger could be correctly evaluated in a few minutes after seismic events.
Citation: Algorithms
PubDate: 2021-11-26
DOI: 10.3390/a14120343
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 344: A Visual Mining Approach to Improved
Multiple-Instance Learning
Authors: Sonia Castelo, Moacir Ponti, Rosane Minghim
First page: 344
Abstract: Multiple-instance learning (MIL) is a paradigm of machine learning that aims to classify a set (bag) of objects (instances), assigning labels only to the bags. This problem is often addressed by selecting an instance to represent each bag, transforming an MIL problem into standard supervised learning. Visualization can be a useful tool to assess learning scenarios by incorporating the users’ knowledge into the classification process. Considering that multiple-instance learning is a paradigm that cannot be handled by current visualization techniques, we propose a multiscale tree-based visualization called MILTree to support MIL problems. The first level of the tree represents the bags, and the second level represents the instances belonging to each bag, allowing users to understand the MIL datasets in an intuitive way. In addition, we propose two new instance selection methods for MIL, which help users improve the model even further. Our methods can handle both binary and multiclass scenarios. In our experiments, SVM was used to build the classifiers. With support of the MILTree layout, the initial classification model was updated by changing the training set, which is composed of the prototype instances. Experimental results validate the effectiveness of our approach, showing that visual mining by MILTree can support exploring and improving models in MIL scenarios and that our instance selection methods outperform the currently available alternatives in most cases.
Citation: Algorithms
PubDate: 2021-11-27
DOI: 10.3390/a14120344
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 345: Compensating Data Shortages in
Manufacturing with Monotonicity Knowledge
Authors: Martin von Kurnatowski, Jochen Schmid, Patrick Link, Rebekka Zache, Lukas Morand, Torsten Kraft, Ingo Schmidt, Jan Schwientek, Anke Stoll
First page: 345
Abstract: Systematic decision making in engineering requires appropriate models. In this article, we introduce a regression method for enhancing the predictive power of a model by exploiting expert knowledge in the form of shape constraints, or more specifically, monotonicity constraints. Incorporating such information is particularly useful when the available datasets are small or do not cover the entire input space, as is often the case in manufacturing applications. We set up the regression subject to the considered monotonicity constraints as a semi-infinite optimization problem, and propose an adaptive solution algorithm. The method is applicable in multiple dimensions and can be extended to more general shape constraints. It was tested and validated on two real-world manufacturing processes, namely, laser glass bending and press hardening of sheet metal. It was found that the resulting models both complied well with the expert’s monotonicity knowledge and predicted the training data accurately. The suggested approach led to lower root-mean-squared errors than comparative methods from the literature for the sparse datasets considered in this work.
Citation: Algorithms
PubDate: 2021-11-27
DOI: 10.3390/a14120345
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 346: A Procedure for Factoring and Solving
Nonlocal Boundary Value Problems for a Type of Linear Integro-Differential
Equations
Authors: Efthimios Providas, Ioannis Nestorios Parasidis
First page: 346
Abstract: The aim of this article is to present a procedure for the factorization and exact solution of boundary value problems for a class of n-th order linear Fredholm integro-differential equations with multipoint and integral boundary conditions. We use the theory of the extensions of linear operators in Banach spaces and establish conditions for the decomposition of the integro-differential operator into two lower-order integro-differential operators. We also create solvability criteria and derive the unique solution in closed form. Two example problems for an ordinary and a partial intergro-differential equation respectively are solved.
Citation: Algorithms
PubDate: 2021-11-28
DOI: 10.3390/a14120346
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 347: Computing the Atom Graph of a Graph and
the Union Join Graph of a Hypergraph
Authors: Anne Berry, Geneviève Simonet
First page: 347
Abstract: The atom graph of a graph is a graph whose vertices are the atoms obtained by clique minimal separator decomposition of this graph, and whose edges are the edges of all possible atom trees of this graph. We provide two efficient algorithms for computing this atom graph, with a complexity in O(min(nωlogn,nm,n(n+m¯)) time, where n is the number of vertices of G, m is the number of its edges, m¯ is the number of edges of the complement of G, and ω, also denoted by α in the literature, is a real number, such that O(nω) is the best known time complexity for matrix multiplication, whose current value is 2,3728596. This time complexity is no more than the time complexity of computing the atoms in the general case. We extend our results to α-acyclic hypergraphs, which are hypergraphs having at least one join tree, a join tree of an hypergraph being defined by its hyperedges in the same way as an atom tree of a graph is defined by its atoms. We introduce the notion of union join graph, which is the union of all possible join trees; we apply our algorithms for atom graphs to efficiently compute union join graphs.
Citation: Algorithms
PubDate: 2021-11-28
DOI: 10.3390/a14120347
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 348: Robust Representation and Efficient
Feature Selection Allows for Effective Clustering of SARS-CoV-2 Variants
Authors: Zahra Tayebi, Sarwan Ali, Murray Patterson
First page: 348
Abstract: The widespread availability of large amounts of genomic data on the SARS-CoV-2 virus, as a result of the COVID-19 pandemic, has created an opportunity for researchers to analyze the disease at a level of detail, unlike any virus before it. On the one hand, this will help biologists, policymakers, and other authorities to make timely and appropriate decisions to control the spread of the coronavirus. On the other hand, such studies will help to more effectively deal with any possible future pandemic. Since the SARS-CoV-2 virus contains different variants, each of them having different mutations, performing any analysis on such data becomes a difficult task, given the size of the data. It is well known that much of the variation in the SARS-CoV-2 genome happens disproportionately in the spike region of the genome sequence—the relatively short region which codes for the spike protein(s). In this paper, we propose a robust feature-vector representation of biological sequences that, when combined with the appropriate feature selection method, allows different downstream clustering approaches to perform well on a variety of different measures. We use such proposed approach with an array of clustering techniques to cluster spike protein sequences in order to study the behavior of different known variants that are increasing at a very high rate throughout the world. We use a k-mers based approach first to generate a fixed-length feature vector representation of the spike sequences. We then show that we can efficiently and effectively cluster the spike sequences based on the different variants with the appropriate feature selection. Using a publicly available set of SARS-CoV-2 spike sequences, we perform clustering of these sequences using both hard and soft clustering methods and show that, with our feature selection methods, we can achieve higher F1 scores for the clusters and also better clustering quality metrics compared to baselines.
Citation: Algorithms
PubDate: 2021-11-29
DOI: 10.3390/a14120348
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 349: GW-DC: A Deep Clustering Model Leveraging
Two-Dimensional Image Transformation and Enhancement
Authors: Xutong Li, Taoying Li, Yan Wang
First page: 349
Abstract: Traditional time-series clustering methods usually perform poorly on high-dimensional data. However, image clustering using deep learning methods can complete image annotation and searches in large image databases well. Therefore, this study aimed to propose a deep clustering model named GW_DC to convert one-dimensional time-series into two-dimensional images and improve cluster performance for algorithm users. The proposed GW_DC consisted of three processing stages: the image conversion stage, image enhancement stage, and image clustering stage. In the image conversion stage, the time series were converted into four kinds of two-dimensional images by different algorithms, including grayscale images, recurrence plot images, Markov transition field images, and Gramian Angular Difference Field images; this last one was considered to be the best by comparison. In the image enhancement stage, the signal components of two-dimensional images were extracted and processed by wavelet transform to denoise and enhance texture features. Meanwhile, a deep clustering network, combining convolutional neural networks with K-Means, was designed for well-learning characteristics and clustering according to the aforementioned enhanced images. Finally, six UCR datasets were adopted to assess the performance of models. The results showed that the proposed GW_DC model provided better results.
Citation: Algorithms
PubDate: 2021-11-29
DOI: 10.3390/a14120349
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 350: The Buy-Online-Pick-Up-in-Store Retailing
Model: Optimization Strategies for In-Store Picking and Packing
Authors: Nicola Ognibene Pietri, Xiaochen Chou, Dominic Loske, Matthias Klumpp, Roberto Montemanni
First page: 350
Abstract: Online shopping is growing fast due to the increasingly widespread use of digital services. During the COVID-19 pandemic, the desire for contactless shopping has further changed consumer behavior and accelerated the acceptance of online grocery purchases. Consequently, traditional brick-and-mortar retailers are developing omnichannel solutions such as click-and-collect services to fulfill the increasing demand. In this work, we consider the Buy-Online-Pick-up-in-Store concept, in which online orders are collected by employees of the conventional stores. As labor is a major cost driver, we apply and discuss different optimizing strategies in the picking and packing process based on real-world data from a German retailer. With comparison of different methods, we estimate the improvements in efficiency in terms of time spent during the picking process. Additionally, the time spent on the packing process can be further decreased by applying a mathematical model that guides the employees on how to organize the articles in different shopping bags during the picking process. In general, we put forward effective strategies for the Buy-Online-Pick-up-in-Store paradigm that can be easily implemented by stores with different topologies.
Citation: Algorithms
PubDate: 2021-11-30
DOI: 10.3390/a14120350
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 351: Locally Scaled and Stochastic Volatility
Metropolis– Hastings Algorithms
Authors: Wilson Tsakane Mongwe, Rendani Mbuvha, Tshilidzi Marwala
First page: 351
Abstract: Markov chain Monte Carlo (MCMC) techniques are usually used to infer model parameters when closed-form inference is not feasible, with one of the simplest MCMC methods being the random walk Metropolis–Hastings (MH) algorithm. The MH algorithm suffers from random walk behaviour, which results in inefficient exploration of the target posterior distribution. This method has been improved upon, with algorithms such as Metropolis Adjusted Langevin Monte Carlo (MALA) and Hamiltonian Monte Carlo being examples of popular modifications to MH. In this work, we revisit the MH algorithm to reduce the autocorrelations in the generated samples without adding significant computational time. We present the: (1) Stochastic Volatility Metropolis–Hastings (SVMH) algorithm, which is based on using a random scaling matrix in the MH algorithm, and (2) Locally Scaled Metropolis–Hastings (LSMH) algorithm, in which the scaled matrix depends on the local geometry of the target distribution. For both these algorithms, the proposal distribution is still Gaussian centred at the current state. The empirical results show that these minor additions to the MH algorithm significantly improve the effective sample rates and predictive performance over the vanilla MH method. The SVMH algorithm produces similar effective sample sizes to the LSMH method, with SVMH outperforming LSMH on an execution time normalised effective sample size basis. The performance of the proposed methods is also compared to the MALA and the current state-of-art method being the No-U-Turn sampler (NUTS). The analysis is performed using a simulation study based on Neal’s funnel and multivariate Gaussian distributions and using real world data modeled using jump diffusion processes and Bayesian logistic regression. Although both MALA and NUTS outperform the proposed algorithms on an effective sample size basis, the SVMH algorithm has similar or better predictive performance when compared to MALA and NUTS across the various targets. In addition, the SVMH algorithm outperforms the other MCMC algorithms on a normalised effective sample size basis on the jump diffusion processes datasets. These results indicate the overall usefulness of the proposed algorithms.
Citation: Algorithms
PubDate: 2021-11-30
DOI: 10.3390/a14120351
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 352: A Sequential Graph Neural Network for
Short Text Classification
Authors: Ke Zhao, Lan Huang, Rui Song, Qiang Shen, Hao Xu
First page: 352
Abstract: Short text classification is an important problem of natural language processing (NLP), and graph neural networks (GNNs) have been successfully used to solve different NLP problems. However, few studies employ GNN for short text classification, and most of the existing graph-based models ignore sequential information (e.g., word orders) in each document. In this work, we propose an improved sequence-based feature propagation scheme, which fully uses word representation and document-level word interaction and overcomes the limitations of textual features in short texts. On this basis, we utilize this propagation scheme to construct a lightweight model, sequential GNN (SGNN), and its extended model, ESGNN. Specifically, we build individual graphs for each document in the short text corpus based on word co-occurrence and use a bidirectional long short-term memory network (Bi-LSTM) to extract the sequential features of each document; therefore, word nodes in the document graph retain contextual information. Furthermore, two different simplified graph convolutional networks (GCNs) are used to learn word representations based on their local structures. Finally, word nodes combined with sequential information and local information are incorporated as the document representation. Extensive experiments on seven benchmark datasets demonstrate the effectiveness of our method.
Citation: Algorithms
PubDate: 2021-12-01
DOI: 10.3390/a14120352
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 353: Hexadecimal Aggregate Approximation
Representation and Classification of Time Series Data
Authors: Zhenwen He, Chunfeng Zhang, Xiaogang Ma, Gang Liu
First page: 353
Abstract: Time series data are widely found in finance, health, environmental, social, mobile and other fields. A large amount of time series data has been produced due to the general use of smartphones, various sensors, RFID and other internet devices. How a time series is represented is key to the efficient and effective storage and management of time series data, as well as being very important to time series classification. Two new time series representation methods, Hexadecimal Aggregate approXimation (HAX) and Point Aggregate approXimation (PAX), are proposed in this paper. The two methods represent each segment of a time series as a transformable interval object (TIO). Then, each TIO is mapped to a spatial point located on a two-dimensional plane. Finally, the HAX maps each point to a hexadecimal digit so that a time series is converted into a hex string. The experimental results show that HAX has higher classification accuracy than Symbolic Aggregate approXimation (SAX) but a lower one than some SAX variants (SAX-TD, SAX-BD). The HAX has the same space cost as SAX but is lower than these variants. The PAX has higher classification accuracy than HAX and is extremely close to the Euclidean distance (ED) measurement; however, the space cost of PAX is generally much lower than the space cost of ED. HAX and PAX are general representation methods that can also support geoscience time series clustering, indexing and query except for classification.
Citation: Algorithms
PubDate: 2021-12-02
DOI: 10.3390/a14120353
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 354: A Model-Driven Approach for Solving the
Software Component Allocation Problem
Authors: Issam Al-Azzoni, Julian Blank, Nenad Petrović
First page: 354
Abstract: The underlying infrastructure paradigms behind the novel usage scenarios and services are becoming increasingly complex—from everyday life in smart cities to industrial environments. Both the number of devices involved and their heterogeneity make the allocation of software components quite challenging. Despite the enormous flexibility enabled by component-based software engineering, finding the optimal allocation of software artifacts to the pool of available devices and computation units could bring many benefits, such as improved quality of service (QoS), reduced energy consumption, reduction of costs, and many others. Therefore, in this paper, we introduce a model-based framework that aims to solve the software component allocation problem (CAP). We formulate it as an optimization problem with either single or multiple objective functions and cover both cases in the proposed framework. Additionally, our framework also provides visualization and comparison of the optimal solutions in the case of multi-objective component allocation. The main contributions introduced in this paper are: (1) a novel methodology for tackling CAP-alike problems based on the usage of model-driven engineering (MDE) for both problem definition and solution representation; (2) a set of Python tools that enable the workflow starting from the CAP model interpretation, after that the generation of optimal allocations and, finally, result visualization. The proposed framework is compared to other similar works using either linear optimization, genetic algorithm (GA), and ant colony optimization (ACO) algorithm within the experiments based on notable papers on this topic, covering various usage scenarios—from Cloud and Fog computing infrastructure management to embedded systems, robotics, and telecommunications. According to the achieved results, our framework performs much faster than GA and ACO-based solutions. Apart from various benefits of adopting a multi-objective approach in many cases, it also shows significant speedup compared to frameworks leveraging single-objective linear optimization, especially in the case of larger problem models.
Citation: Algorithms
PubDate: 2021-12-06
DOI: 10.3390/a14120354
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 355: A Meeting Point of Probability, Graphs,
and Algorithms: The Lovász Local Lemma and Related Results—A
Survey
Authors: András Faragó
First page: 355
Abstract: A classic and fundamental result, known as the Lovász Local Lemma, is a gem in the probabilistic method of combinatorics. At a high level, its core message can be described by the claim that weakly dependent events behave similarly to independent ones. A fascinating feature of this result is that even though it is a purely probabilistic statement, it provides a valuable and versatile tool for proving completely deterministic theorems. The Lovász Local Lemma has found many applications; despite being originally published in 1973, it still attracts active novel research. In this survey paper, we review various forms of the Lemma, as well as some related results and applications.
Citation: Algorithms
PubDate: 2021-12-08
DOI: 10.3390/a14120355
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 356: Optimized Weighted Nearest Neighbours
Matching Algorithm for Control Group Selection
Authors: Szabolcs Szekér, Ágnes Vathy-Fogarassy
First page: 356
Abstract: An essential criterion for the proper implementation of case-control studies is selecting appropriate case and control groups. In this article, a new simulated annealing-based control group selection method is proposed, which solves the problem of selecting individuals in the control group as a distance optimization task. The proposed algorithm pairs the individuals in the n-dimensional feature space by minimizing the weighted distances between them. The weights of the dimensions are based on the odds ratios calculated from the logistic regression model fitted on the variables describing the probability of membership of the treated group. For finding the optimal pairing of the individuals, simulated annealing is utilized. The effectiveness of the newly proposed Weighted Nearest Neighbours Control Group Selection with Simulated Annealing (WNNSA) algorithm is presented by two Monte Carlo studies. Results show that the WNNSA method can outperform the widely applied greedy propensity score matching method in feature spaces where only a few covariates characterize individuals and the covariates can only take a few values.
Citation: Algorithms
PubDate: 2021-12-08
DOI: 10.3390/a14120356
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 357: Special Issue “2021 Selected Papers
from Algorithms’ Editorial Board Members”
Authors: Frank Werner
First page: 357
Abstract: This is the second edition of a special issue of Algorithms that is of a rather different nature compared to other Special Issues in the journal, which are usually dedicated to a particular subject in the area of algorithms [...]
Citation: Algorithms
PubDate: 2021-12-09
DOI: 10.3390/a14120357
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 358: Agent State Flipping Based Hybridization
of Heuristic Optimization Algorithms: A Case of Bat Algorithm and Krill
Herd Hybrid Algorithm
Authors: Robertas Damaševičius, Rytis Maskeliūnas
First page: 358
Abstract: This paper describes a unique meta-heuristic technique for hybridizing bio-inspired heuristic algorithms. The technique is based on altering the state of agents using a logistic probability function that is dependent on an agent’s fitness rank. An evaluation using two bio-inspired algorithms (bat algorithm (BA) and krill herd (KH)) and 12 optimization problems (cross-in-tray, rotated hyper-ellipsoid (RHE), sphere, sum of squares, sum of different powers, McCormick, Zakharov, Rosenbrock, De Jong No. 5, Easom, Branin, and Styblinski–Tang) is presented. Furthermore, an experimental evaluation of the proposed scheme using the industrial three-bar truss design problem is presented. The experimental results demonstrate that the hybrid scheme outperformed the baseline algorithms (mean rank for the hybrid BA-KH algorithm is 1.279 vs. 1.958 for KH and 2.763 for BA).
Citation: Algorithms
PubDate: 2021-12-10
DOI: 10.3390/a14120358
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 359: Lempel-Ziv Parsing for Sequences of Blocks
Authors: Dmitry Kosolobov, Daniel Valenzuela
First page: 359
Abstract: The Lempel-Ziv parsing (LZ77) is a widely popular construction lying at the heart of many compression algorithms. These algorithms usually treat the data as a sequence of bytes, i.e., blocks of fixed length 8. Another common option is to view the data as a sequence of bits. We investigate the following natural question: what is the relationship between the LZ77 parsings of the same data interpreted as a sequence of fixed-length blocks and as a sequence of bits (or other “elementary” letters)' In this paper, we prove that, for any integer b>1, the number z of phrases in the LZ77 parsing of a string of length n and the number zb of phrases in the LZ77 parsing of the same string in which blocks of length b are interpreted as separate letters (e.g., b=8 in case of bytes) are related as zb=O(bzlognz). The bound holds for both “overlapping” and “non-overlapping” versions of LZ77. Further, we establish a tight bound zb=O(bz) for the special case when each phrase in the LZ77 parsing of the string has a “phrase-aligned” earlier occurrence (an occurrence equal to the concatenation of consecutive phrases). The latter is an important particular case of parsing produced, for instance, by grammar-based compression methods.
Citation: Algorithms
PubDate: 2021-12-10
DOI: 10.3390/a14120359
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 360: Merging Discrete Morse Vector Fields: A
Case of Stubborn Geometric Parallelization
Authors: Douglas Lenseth, Boris Goldfarb
First page: 360
Abstract: We address the basic question in discrete Morse theory of combining discrete gradient fields that are partially defined on subsets of the given complex. This is a well-posed question when the discrete gradient field V is generated using a fixed algorithm which has a local nature. One example is ProcessLowerStars, a widely used algorithm for computing persistent homology associated to a grey-scale image in 2D or 3D. While the algorithm for V may be inherently local, being computed within stars of vertices and so embarrassingly parallelizable, in practical use, it is natural to want to distribute the computation over patches Pi, apply the chosen algorithm to compute the fields Vi associated to each patch, and then assemble the ambient field V from these. Simply merging the fields from the patches, even when that makes sense, gives a wrong answer. We develop both very general merging procedures and leaner versions designed for specific, easy-to-arrange covering patterns.
Citation: Algorithms
PubDate: 2021-12-11
DOI: 10.3390/a14120360
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 361: A Domain Adaptive Person Re-Identification
Based on Dual Attention Mechanism and Camstyle Transfer
Authors: Chengyan Zhong, Guanqiu Qi, Neal Mazur, Sarbani Banerjee, Devanshi Malaviya, Gang Hu
First page: 361
Abstract: Due to the variation in the image capturing process, the difference between source and target sets causes a challenge in unsupervised domain adaptation (UDA) on person re-identification (re-ID). Given a labeled source training set and an unlabeled target training set, this paper focuses on improving the generalization ability of the re-ID model on the target testing set. The proposed method enforces two properties at the same time: (1) camera invariance is achieved through the positive learning formed by unlabeled target images and their camera style transfer counterparts; and (2) the robustness of the backbone network feature extraction is improved, and the accuracy of feature extraction is enhanced by adding a position-channel dual attention mechanism. The proposed network model uses a classic dual-stream network. Comparative experimental results on three public benchmarks prove the superiority of the proposed method.
Citation: Algorithms
PubDate: 2021-12-13
DOI: 10.3390/a14120361
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 362: Faster Provable Sieving Algorithms for the
Shortest Vector Problem and the Closest Vector Problem on Lattices in
ℓp Norm
Authors: Priyanka Mukhopadhyay
First page: 362
Abstract: In this work, we give provable sieving algorithms for the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices in ℓp norm (1≤p≤∞). The running time we obtain is better than existing provable sieving algorithms. We give a new linear sieving procedure that works for all ℓp norm (1≤p≤∞). The main idea is to divide the space into hypercubes such that each vector can be mapped efficiently to a sub-region. We achieve a time complexity of 22.751n+o(n), which is much less than the 23.849n+o(n) complexity of the previous best algorithm. We also introduce a mixed sieving procedure, where a point is mapped to a hypercube within a ball and then a quadratic sieve is performed within each hypercube. This improves the running time, especially in the ℓ2 norm, where we achieve a time complexity of 22.25n+o(n), while the List Sieve Birthday algorithm has a running time of 22.465n+o(n). We adopt our sieving techniques to approximation algorithms for SVP and CVP in ℓp norm (1≤p≤∞) and show that our algorithm has a running time of 22.001n+o(n), while previous algorithms have a time complexity of 23.169n+o(n).
Citation: Algorithms
PubDate: 2021-12-13
DOI: 10.3390/a14120362
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 363: Resource Allocation for Intelligent
Authors: Wei Huang, Zhiren Han, Li Zhao, Hongbo Xu, Zhongnian Li, Ze Wang
First page: 363
Abstract: Due to its ability to significantly improve the wireless communication efficiency, the intelligent reflective surface (IRS) has aroused widespread research interest. However, it is a challenge to obtain perfect channel state information (CSI) for IRS-related channels due to the lack of the ability to send, receive, and process signals at IRS. Since most of the existing channel estimation methods are developed to obtain cascaded base station (BS)-IRS-user devices (UDs) channel, this paper studies the problem of computation and communication resource allocation of the IRS-assisted federated learning (FL) system based on the imperfect CSI. Specifically, we take the statistical CSI error model into consideration and formulate the training time minimization problem subject to the rate outage probability constraints. In order to solve this issue, the semi-definite relaxation (SDR) and the constrained concave convex procedure (CCCP) are invoked to transform it into a convex problem. Subsequently, a low-complexity algorithm is proposed to minimize the delay of the FL system. Numerical results show that the proposed algorithm effectively reduces the training time of the FL system base on imperfect CSI.
Citation: Algorithms
PubDate: 2021-12-14
DOI: 10.3390/a14120363
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 364: Metaheuristics in the Humanitarian Supply
Chain
Authors: Francisca Santana Robles, Eva Selene Hernández-Gress, Neil Hernández-Gress, Rafael Granillo Macias
First page: 364
Abstract: Everyday there are more disasters that require Humanitarian Supply Chain (HSC) attention; generally these problems are difficult to solve in reasonable computational time and metaheuristics (MHs) are the indicated solution algorithms. To our knowledge, there has not been a review article on MHs applied to HSC. In this work, 78 articles were extracted from 2016 publications using systematic literature review methodology and were analyzed to answer two research questions: (1) How are the HSC problems that have been solved from Metaheuristics classified' (2) What is the gap found to accomplish future research in Metaheuristics in HSC' After classifying them into deterministic (52.56%) and non-deterministic (47.44%) problems; post-disaster (51.28%), pre-disaster (14.10%) and integrated (34.62%); facility location (41.03%), distribution (71.79%), inventory (11.54%) and mass evacuation (10.26%); single (46.15%) and multiple objective functions (53.85%), single (76.92%) and multiple (23.07%) period; and the type of Metaheuristic: Metaphor (71.79%) with genetic algorithms and particle swarm optimization as the most used; and non-metaphor based (28.20%), in which search algorithms are mostly used; it is concluded that, to consider the uncertainty of the real context, future research should be done in non-deterministic and multi-period problems that integrate pre- and post-disaster stages, that increasingly include problems such as inventory and mass evacuation and in which new multi-objective MHs are tested.
Citation: Algorithms
PubDate: 2021-12-15
DOI: 10.3390/a14120364
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 365: A Branch-and-Bound Algorithm for
Polymatrix Games ϵ-Proper Nash Equilibria Computation
Authors: Slim Belhaiza
First page: 365
Abstract: When several Nash equilibria exist in the game, decision-makers need to refine their choices based on some refinement concepts. To this aim, the notion of a ϵ-proper equilibria set for polymatrix games is used to develop 0–1 mixed linear programs and compute ϵ-proper Nash equilibria. A Branch-and-Bound exact arithmetics algorithm is proposed. Experimental results are provided on polymatrix games randomly generated with different sizes and densities.
Citation: Algorithms
PubDate: 2021-12-16
DOI: 10.3390/a14120365
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 366: Subspace Detours Meet
Gromov–Wasserstein
Authors: Clément Bonet, Titouan Vayer, Nicolas Courty, François Septier, Lucas Drumetz
First page: 366
Abstract: In the context of optimal transport (OT) methods, the subspace detour approach was recently proposed by Muzellec and Cuturi. It consists of first finding an optimal plan between the measures projected on a wisely chosen subspace and then completing it in a nearly optimal transport plan on the whole space. The contribution of this paper is to extend this category of methods to the Gromov–Wasserstein problem, which is a particular type of OT distance involving the specific geometry of each distribution. After deriving the associated formalism and properties, we give an experimental illustration on a shape matching problem. We also discuss a specific cost for which we can show connections with the Knothe–Rosenblatt rearrangement.
Citation: Algorithms
PubDate: 2021-12-17
DOI: 10.3390/a14120366
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 367: A Pathfinding Problem for Fork-Join
Directed Acyclic Graphs with Unknown Edge Length
Authors: Kunihiko Hiraishi
First page: 367
Abstract: In a previous paper by the author, a pathfinding problem for directed trees is studied under the following situation: each edge has a nonnegative integer length, but the length is unknown in advance and should be found by a procedure whose computational cost becomes exponentially larger as the length increases. In this paper, the same problem is studied for a more general class of graphs called fork-join directed acyclic graphs. The problem for the new class of graphs contains the previous one. In addition, the optimality criterion used in this paper is stronger than that in the previous paper and is more appropriate for real applications.
Citation: Algorithms
PubDate: 2021-12-17
DOI: 10.3390/a14120367
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 368: Adaptive and Lightweight Abnormal Node
Detection via Biological Immune Game in Mobile Multimedia Networks
Authors: Yajing Zhang, Kai Wang, Jinghui Zhang
First page: 368
Abstract: Considering the contradiction between limited node resources and high detection costs in mobile multimedia networks, an adaptive and lightweight abnormal node detection algorithm based on artificial immunity and game theory is proposed in order to balance the trade-off between network security and detection overhead. The algorithm can adapt to the highly dynamic mobile multimedia networking environment with a large number of heterogeneous nodes and multi-source big data. Specifically, the heterogeneous problem of nodes is solved based on the non-specificity of an immune algorithm. A niche strategy is used to identify dangerous areas, and antibody division generates an antibody library that can be updated online, so as to realize the dynamic detection of the abnormal behavior of nodes. Moreover, the priority of node recovery for abnormal nodes is decided through a game between nodes without causing excessive resource consumption for security detection. The results of comparative experiments show that the proposed algorithm has a relatively high detection rate and a low false-positive rate, can effectively reduce consumption time, and has good level of adaptability under the condition of dynamic nodes.
Citation: Algorithms
PubDate: 2021-12-20
DOI: 10.3390/a14120368
Issue No: Vol. 14, No. 12 (2021)
- Algorithms, Vol. 14, Pages 301: A Model-Agnostic Algorithm for Bayes Error
Determination in Binary Classification
Authors: Umberto Michelucci, Michela Sperti, Dario Piga, Francesca Venturini, Marco A. Deriu
First page: 301
Abstract: This paper presents the intrinsic limit determination algorithm (ILD Algorithm), a novel technique to determine the best possible performance, measured in terms of the AUC (area under the ROC curve) and accuracy, that can be obtained from a specific dataset in a binary classification problem with categorical features regardless of the model used. This limit, namely, the Bayes error, is completely independent of any model used and describes an intrinsic property of the dataset. The ILD algorithm thus provides important information regarding the prediction limits of any binary classification algorithm when applied to the considered dataset. In this paper, the algorithm is described in detail, its entire mathematical framework is presented and the pseudocode is given to facilitate its implementation. Finally, an example with a real dataset is given.
Citation: Algorithms
PubDate: 2021-10-20
DOI: 10.3390/a14110301
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 302: Multi-Objective UAV Positioning Mechanism
for Sustainable Wireless Connectivity in Environments with Forbidden
Flying Zones
Authors: İbrahim Atli, Metin Ozturk, Gianluca C. Valastro, Muhammad Zeeshan Asghar
First page: 302
Abstract: A communication system based on unmanned aerial vehicles (UAVs) is a viable alternative for meeting the coverage and capacity needs of future wireless networks. However, because of the limitations of UAV-enabled communications in terms of coverage, energy consumption, and flying laws, the number of studies focused on the sustainability element of UAV-assisted networking in the literature was limited thus far. We present a solution to this problem in this study; specifically, we design a Q-learning-based UAV placement strategy for long-term wireless connectivity while taking into account major constraints such as altitude regulations, nonflight zones, and transmit power. The goal is to determine the best location for the UAV base station (BS) while reducing energy consumption and increasing the number of users covered. Furthermore, a weighting method is devised, allowing energy usage and the number of users served to be prioritized based on network/battery circumstances. The suggested Q-learning-based solution is contrasted to the standard k-means clustering method, in which the UAV BS is positioned at the centroid location with the shortest cumulative distance between it and the users. The results demonstrate that the proposed solution outperforms the baseline k-means clustering-based method in terms of the number of users covered while achieving the desired minimization of the energy consumption.
Citation: Algorithms
PubDate: 2021-10-21
DOI: 10.3390/a14110302
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 303: Selection of Key Frames for 3D
Reconstruction in Real Time
Authors: Koschel, Müller, Reiterer
First page: 303
Abstract: Cameras play a prominent role in the context of 3D data, as they can be designed to be very cheap and small and can therefore be used in many 3D reconstruction systems. Typical cameras capture video at 20 to 60 frames per second, resulting in a high number of frames to select from for 3D reconstruction. Many frames are unsuited for reconstruction as they suffer from motion blur or show too little variation compared to other frames. The camera used within this work has built-in inertial sensors. What if one could use the built-in inertial sensors to select a set of key frames well-suited for 3D reconstruction, free from motion blur and redundancy, in real time' A random forest classifier (RF) is trained by inertial data to determine frames without motion blur and to reduce redundancy. Frames are analyzed by the fast Fourier transformation and Lucas–Kanade method to detect motion blur and moving features in frames to label those correctly to train the RF. We achieve a classifier that omits successfully redundant frames and preserves frames with the required quality but exhibits an unsatisfied performance with respect to ideal frames. A 3D reconstruction by Meshroom shows a better result with selected key frames by the classifier. By extracting frames from video, one can comfortably scan objects and scenes without taking single pictures. Our proposed method automatically extracts the best frames in real time without using complex image-processing algorithms.
Citation: Algorithms
PubDate: 2021-10-21
DOI: 10.3390/a14110303
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 304: Analytic Form Fitting in Poor Triangular
Meshes
Authors: Cristian Rendon-Cardona, Jorge Correa, Diego A. Acosta, Oscar Ruiz-Salguero
First page: 304
Abstract: Fitting of analytic forms to point or triangle sets is central to computer-aided design, manufacturing, reverse engineering, dimensional control, etc. The existing approaches for this fitting assume an input of statistically strong point or triangle sets. In contrast, this manuscript reports the design (and industrial application) of fitting algorithms whose inputs are specifically poor triangular meshes. The analytic forms currently addressed are planes, cones, cylinders and spheres. Our algorithm also extracts the support submesh responsible for the analytic primitive. We implement spatial hashing and boundary representation for a preprocessing sequence. When the submesh supporting the analytic form holds strict C0-continuity at its border, submesh extraction is independent of fitting, and our algorithm is a real-time one. Otherwise, segmentation and fitting are codependent and our algorithm, albeit correct in the analytic form identification, cannot perform in real-time.
Citation: Algorithms
PubDate: 2021-10-22
DOI: 10.3390/a14110304
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 305: Metaheuristics for the Minimum Time Cut
Path Problem with Different Cutting and Sliding Speeds
Authors: Bonfim Amaro Amaro Junior, Marcio Costa Santos, Guilherme Nepomuceno de Carvalho, Luiz Jonatã Pires de Araújo, Placido Rogerio Pinheiro
First page: 305
Abstract: The problem of efficiently cutting smaller two-dimensional pieces from a larger surface is recurrent in several manufacturing settings. This problem belongs to the domain of cutting and packing (C&P) problems. This study approached a category of C&P problems called the minimum time cut path (MTCP) problem, which aims to identify a sequence of cutting and sliding movements for the head device to minimize manufacturing time. Both cutting and slide speeds (just moving the head) vary according to equipment, despite their relevance in real-world scenarios. This study applied the MTCP problem on the practical scope and presents two metaheuristics for tackling more significant instances that resemble real-world requirements. The experiments presented in this study utilized parameter values from typical laser cutting machines to assess the feasibility of the proposed methods compared to existing commercial software. The results show that metaheuristic-based solutions are competitive when addressing practical problems, achieving increased performance regarding the processing time for 94% of the instances.
Citation: Algorithms
PubDate: 2021-10-23
DOI: 10.3390/a14110305
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 306: An Application of an Unequal-Area
Facilities Layout Problem with Fixed-Shape Facilities
Authors: Alan McKendall, Artak Hakobyan
First page: 306
Abstract: The unequal-area facility layout problem (UA-FLP) is the problem of locating rectangular facilities on a rectangular floor space such that facilities do not overlap while optimizing some objective. The objective considered in this paper is minimizing the total distance materials travel between facilities. The UA-FLP considered in this paper considers facilities with fixed dimension and was motivated by the investigation of layout options for a production area at the Toyota Motor Manufacturing West Virginia (TMMWV) plant in Buffalo, WV, USA. This paper presents a mathematical model and a genetic algorithm for locating facilities on a continuous plant floor. More specifically, a genetic algorithm, which consists of a boundary search heuristic (BSH), a linear program, and a dual simplex method, is developed for an UA-FLP. To test the performance of the proposed technique, several test problems taken from the literature are used in the analysis. The results show that the proposed heuristic performs well with respect to solution quality and computational time.
Citation: Algorithms
PubDate: 2021-10-23
DOI: 10.3390/a14110306
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 307: Outdoor Node Localization Using Random
Neural Networks for Large-Scale Urban IoT LoRa Networks
Authors: Winfred Ingabire, Hadi Larijani, Ryan M. Gibson, Ayyaz-UI-Haq Qureshi
First page: 307
Abstract: Accurate localization for wireless sensor end devices is critical, particularly for Internet of Things (IoT) location-based applications such as remote healthcare, where there is a need for quick response to emergency or maintenance services. Global Positioning Systems (GPS) are widely known for outdoor localization services; however, high-power consumption and hardware cost become a significant hindrance to dense wireless sensor networks in large-scale urban areas. Therefore, wireless technologies such as Long-Range Wide-Area Networks (LoRaWAN) are being investigated in different location-aware IoT applications due to having more advantages with low-cost, long-range, and low-power characteristics. Furthermore, various localization methods, including fingerprint localization techniques, are present in the literature but with different limitations. This study uses LoRaWAN Received Signal Strength Indicator (RSSI) values to predict the unknown X and Y position coordinates on a publicly available LoRaWAN dataset for Antwerp in Belgium using Random Neural Networks (RNN). The proposed localization system achieves an improved high-level accuracy for outdoor dense urban areas and outperforms the present conventional LoRa-based localization systems in other work, with a minimum mean localization error of 0.29 m.
Citation: Algorithms
PubDate: 2021-10-23
DOI: 10.3390/a14110307
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 308: The GM-BP Neural Network Prediction Model
for International Competitiveness of Computer Information Service Industry
Authors: Xianhang Xu, Mohd Anuar Arshad, Ubaid Ali, Arshad Mahmood
First page: 308
Abstract: The computer information service industry is closely related to the fourth industrial revolution and stands at the core of the global value chain. It has become an essential engine for developing industries in various countries, and its scale is constantly expanding. In the critical period of global economic transformation and development, the use of mathematical models to predict its international competitiveness will help scientifically evaluate the development level of the industry and accelerate the adaptation to the needs of the fourth industrial revolution. In this article, a prediction model is proposed for the international competitiveness of the computer information service industry. First, we used the Revealed Comparative Advantage (RCA) index to measure the international competitiveness of the computer information service industry. Furthermore, based on the characteristics of the industry and high-quality development theory, we constructed the evaluation indicator system of influencing factors and used the grey relational analysis method to screen key indicators. Then, we combined the Grey model and BP neural network algorithm to construct the GM-BP prediction model. Finally, China is used as an example to predict the international competitiveness of its computer information service industry, and suggestions are made for industrial development. The results show that the grey relational analysis method can genuinely reflect the impact of different aspects on the international competitiveness of China’s computer information service industry and better determine the key indicators of influencing factors. The GM-BP model has minor errors and excellent simulation results and can accurately predict the future status of international competitiveness. The applicability and reliability of the model are reasonable.
Citation: Algorithms
PubDate: 2021-10-23
DOI: 10.3390/a14110308
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 309: A Parallel Algorithm for Dividing
Octonions
Authors: Aleksandr Cariow, Janusz P. Paplinski
First page: 309
Abstract: The article presents a parallel hardware-oriented algorithm designed to speed up the division of two octonions. The advantage of the proposed algorithm is that the number of real multiplications is halved as compared to the naive method for implementing this operation. In the synthesis of the discussed algorithm, the matrix representation of this operation was used, which allows us to present the division of octonions by means of a vector–matrix product. Taking into account a specific structure of the matrix multiplicand allows for reducing the number of real multiplications necessary for the execution of the octonion division procedure.
Citation: Algorithms
PubDate: 2021-10-24
DOI: 10.3390/a14110309
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 310: A Non-Dominated Genetic Algorithm Based on
Decoding Rule of Heat Treatment Equipment Volume and Job Delivery Date
Authors: Yan Liang, Qingdong Zhang
First page: 310
Abstract: This paper investigated the flexible job-shop scheduling problem with the heat treatment process. To solve this problem, we built an unified mathematical model of the heat treatment process and machining process. Up to now, this problem has not been investigated much. Based on the features of this problem, we are intended to minimize Cmax, maximize the space utilization rate of heat treatment equipment, and minimize the total delay penalty to optimize the scheduling. By taking the dynamic process arrival under consideration, this paper proposed a set of decoding rules based on the heat treatment equipment volume and job delivery date to achieve a hybrid dynamic scheduling solution during one scheduling procedure. When the utilization rate of heat treatment equipment volume is maximized, and the job delivery date is taken under consideration, it is preferred to minimize the number of workpiece batches in the same job, and reduce the waiting time of the pending job. In combination with the improved adaptive non-dominated genetic algorithm, we worked out the solution. Furthermore, we verified the effectiveness of the proposed decoding rules and improved algorithm through algorithm comparison and calculation results. Finally, a software system for algorithm verification and algorithm comparison was developed to verify the validity of our proposed algorithm.
Citation: Algorithms
PubDate: 2021-10-25
DOI: 10.3390/a14110310
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 311: Evaluation of Features Generated by a
High-End Low-Cost Electrical Smart Meter
Authors: Christina Koutroumpina, Spyros Sioutas, Stelios Koutroubinas, Kostas Tsichlas
First page: 311
Abstract: The problem of energy disaggregation is the separation of an aggregate energy signal into the consumption of individual appliances in a household. This is useful, since the goal of energy efficiency at the household level can be achieved through energy-saving policies towards changing the behavior of the consumers. This requires as a prerequisite to be able to measure the energy consumption at the appliance level. The purpose of this study is to present some initial results towards this goal by making heavy use of the characteristics of a particular din-rail meter, which is provided by Meazon S.A. Our thinking is that meter-specific energy disaggregation solutions may yield better results than general-purpose methods, especially for sophisticated meters. This meter has a 50 Hz sampling rate over 3 different lines and provides a rather rich set of measurements with respect to the extracted features. In this paper we aim at evaluating the set of features generated by the smart meter. To this end, we use well-known supervised machine learning models and test their effectiveness on certain appliances when selecting specific subsets of features. Three algorithms are used for this purpose: the Decision Tree Classifier, the Random Forest Classifier, and the Multilayer Perceptron Classifier. Our experimental study shows that by using a specific set of features one can enhance the classification performance of these algorithms.
Citation: Algorithms
PubDate: 2021-10-25
DOI: 10.3390/a14110311
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 312: A Linearly Involved Generalized Moreau
Enhancement of ℓ2,1-Norm with Application to Weighted Group Sparse
Classification
Authors: Yang Chen, Masao Yamagishi, Isao Yamada
First page: 312
Abstract: This paper proposes a new group-sparsity-inducing regularizer to approximate ℓ2,0 pseudo-norm. The regularizer is nonconvex, which can be seen as a linearly involved generalized Moreau enhancement of ℓ2,1-norm. Moreover, the overall convexity of the corresponding group-sparsity-regularized least squares problem can be achieved. The model can handle general group configurations such as weighted group sparse problems, and can be solved through a proximal splitting algorithm. Among the applications, considering that the bias of convex regularizer may lead to incorrect classification results especially for unbalanced training sets, we apply the proposed model to the (weighted) group sparse classification problem. The proposed classifier can use the label, similarity and locality information of samples. It also suppresses the bias of convex regularizer-based classifiers. Experimental results demonstrate that the proposed classifier improves the performance of convex ℓ2,1 regularizer-based methods, especially when the training data set is unbalanced. This paper enhances the potential applicability and effectiveness of using nonconvex regularizers in the frame of convex optimization.
Citation: Algorithms
PubDate: 2021-10-27
DOI: 10.3390/a14110312
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 313: Matheuristics and Column Generation for a
Basic Technician Routing Problem
Authors: Nicolas Dupin, Rémi Parize, El-Ghazali Talbi
First page: 313
Abstract: This paper considers a variant of the Vehicle Routing Problem with Time Windows, with site dependencies, multiple depots and outsourcing costs. This problem is the basis for many technician routing problems. Having both site-dependency and time window constraints lresults in difficulties in finding feasible solutions and induces highly constrained instances. Matheuristics based on Mixed Integer Linear Programming compact formulations are firstly designed. Column Generation matheuristics are then described by using previous matheuristics and machine learning techniques to stabilize and speed up the convergence of the Column Generation algorithm. The computational experiments are analyzed on public instances with graduated difficulties in order to analyze the accuracy of algorithms for ensuring feasibility and the quality of solutions for weakly to highly constrained instances. The results emphasize the interest of the multiple types of hybridization between mathematical programming, machine learning and heuristics inside the Column Generation framework. This work offers perspectives for many extensions of technician routing problems.
Citation: Algorithms
PubDate: 2021-10-27
DOI: 10.3390/a14110313
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 314: DMFO-CD: A Discrete Moth-Flame
Optimization Algorithm for Community Detection
Authors: Mohammad H. Nadimi-Shahraki, Ebrahim Moeini, Shokooh Taghian, Seyedali Mirjalili
First page: 314
Abstract: In this paper, a discrete moth–flame optimization algorithm for community detection (DMFO-CD) is proposed. The representation of solution vectors, initialization, and movement strategy of the continuous moth–flame optimization are purposely adapted in DMFO-CD such that it can solve the discrete community detection. In this adaptation, locus-based adjacency representation is used to represent the position of moths and flames, and the initialization process is performed by considering the community structure and the relation between nodes without the need of any knowledge about the number of communities. Solution vectors are updated by the adapted movement strategy using a single-point crossover to distance imitating, a two-point crossover to calculate the movement, and a single-point neighbor-based mutation that can enhance the exploration and balance exploration and exploitation. The fitness function is also defined based on modularity. The performance of DMFO-CD was evaluated on eleven real-world networks, and the obtained results were compared with five well-known algorithms in community detection, including GA-Net, DPSO-PDM, GACD, EGACD, and DECS in terms of modularity, NMI, and the number of detected communities. Additionally, the obtained results were statistically analyzed by the Wilcoxon signed-rank and Friedman tests. In the comparison with other comparative algorithms, the results show that the proposed DMFO-CD is competitive to detect the correct number of communities with high modularity.
Citation: Algorithms
PubDate: 2021-10-28
DOI: 10.3390/a14110314
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 315: Nonsingular Terminal Sliding Mode Based
Finite-Time Dynamic Surface Control for a Quadrotor UAV
Authors: Yuxiao Niu, Hanyu Ban, Haichao Zhang, Wenquan Gong, Fang Yu
First page: 315
Abstract: In this work, a tracking control strategy is developed to achieve finite-time stability of quadrotor Unmanned Aerial Vehicles (UAVs) subject to external disturbances and parameter uncertainties. Firstly, a finite-time extended state observer (ESO) is proposed based on the nonsingular terminal sliding mode variable to estimate external disturbances to the position subsystem. Then, utilizing the information provided by the ESO and the nonsingular terminal sliding mode control (NTSMC) technique, a dynamic surface controller is proposed to achieve finite-time stability of the position subsystem. By conducting a similar step for the attitude subsystem, a finite-time ESO-based dynamic surface controller is proposed to carry out attitude tracking control of the quadrotor UAV. Finally, the performance of the control algorithm is demonstrated via a numerical simulation.
Citation: Algorithms
PubDate: 2021-10-29
DOI: 10.3390/a14110315
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 316: Variation Trends of Fractal Dimension in
Epileptic EEG Signals
Authors: Zhiwei Li, Jun Li, Yousheng Xia, Pingfa Feng, Feng Feng
First page: 316
Abstract: Epileptic diseases take EEG as an important basis for clinical judgment, and fractal algorithms were often used to analyze electroencephalography (EEG) signals. However, the variation trends of fractal dimension (D) were opposite in the literature, i.e., both D decreasing and increasing were reported in previous studies during seizure status relative to the normal status, undermining the feasibility of fractal algorithms for EEG analysis to detect epileptic seizures. In this study, two algorithms with high accuracy in the D calculation, Higuchi and roughness scaling extraction (RSE), were used to study D variation of EEG signals with seizures. It was found that the denoising operation had an important influence on D variation trend. Moreover, the D variation obtained by RSE algorithm was larger than that by Higuchi algorithm, because the non-fractal nature of EEG signals during normal status could be detected and quantified by RSE algorithm. The above findings in this study could be promising to make more understandings of the nonlinear nature and scaling behaviors of EEG signals.
Citation: Algorithms
PubDate: 2021-10-29
DOI: 10.3390/a14110316
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 317: A Real-Time Car Towing Management System
Using ML-Powered Automatic Number Plate Recognition
Authors: Ahmed Abdelmoamen Ahmed, Sheikh Ahmed
First page: 317
Abstract: Automatic Number Plate Recognition (ANPR) has been widely used in different domains, such as car park management, traffic management, tolling, and intelligent transport systems. Despite this technology’s importance, the existing ANPR approaches suffer from the accurate identification of number plats due to its different size, orientation, and shapes across different regions worldwide. In this paper, we are studying these challenges by implementing a case study for smart car towing management using Machine Learning (ML) models. The developed mobile-based system uses different approaches and techniques to enhance the accuracy of recognizing number plates in real-time. First, we developed an algorithm to accurately detect the number plate’s location on the car body. Then, the bounding box of the plat is extracted and converted into a grayscale image. Second, we applied a series of filters to detect the alphanumeric characters’ contours within the grayscale image. Third, the detected the alphanumeric characters’ contours are fed into a K-Nearest Neighbors (KNN) model to detect the actual number plat. Our model achieves an overall classification accuracy of 95% in recognizing number plates across different regions worldwide. The user interface is developed as an Android mobile app, allowing law-enforcement personnel to capture a photo of the towed car, which is then recorded in the car towing management system automatically in real-time. The app also allows owners to search for their cars, check the case status, and pay fines. Finally, we evaluated our system using various performance metrics such as classification accuracy, processing time, etc. We found that our model outperforms some state-of-the-art ANPR approaches in terms of the overall processing time.
Citation: Algorithms
PubDate: 2021-10-30
DOI: 10.3390/a14110317
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 318: Using Decision Trees and Random Forest
Algorithms to Predict and Determine Factors Contributing to First-Year
University Students’ Learning Performance
Authors: Thao-Trang Huynh-Cam, Long-Sheng Chen, Huynh Le
First page: 318
Abstract: First-year students’ learning performance has received much attention in educational practice and theory. Previous works used some variables, which should be obtained during the course or in the progress of the semester through questionnaire surveys and interviews, to build prediction models. These models cannot provide enough timely support for the poor performance students, caused by economic factors. Therefore, other variables are needed that allow us to reach prediction results earlier. This study attempts to use family background variables that can be obtained prior to the start of the semester to build learning performance prediction models of freshmen using random forest (RF), C5.0, CART, and multilayer perceptron (MLP) algorithms. The real sample of 2407 freshmen who enrolled in 12 departments of a Taiwan vocational university will be employed. The experimental results showed that CART outperforms C5.0, RF, and MLP algorithms. The most important features were mother’s occupations, department, father’s occupations, main source of living expenses, and admission status. The extracted knowledge rules are expected to be indicators for students’ early performance prediction so that strategic intervention can be planned before students begin the semester.
Citation: Algorithms
PubDate: 2021-10-30
DOI: 10.3390/a14110318
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 319: Risk Assessment Algorithm for Power
Transformer Fleets Based on Condition and Strategic Importance
Authors: Diego A. Zaldivar, Andres A. Romero, Sergio R. Rivera
First page: 319
Abstract: In every electric power system, power transformers (PT) play a critical role. Under ideal circumstances, PT should receive the utmost care to maintain the highest operative condition during their lifetime. Through the years, different approaches have been developed to assess the condition and the inherent risk during the operation of PT. However, most proposed methodologies tend to analyze PT as individuals and not as a fleet. A fleet assessment helps the asset manager make sound decisions regarding the maintenance scheduling for groups of PT with similar conditions. This paper proposes a new methodology to assess the risk of PT fleets, considering the technical condition and the strategic importance of the units. First, the state of the units was evaluated using a health index (HI) with a fuzzy logic algorithm. Then, the strategic importance of each unit was assessed using a weighting technique to obtain the importance index (II). Finally, the analyzed units with similar HI and II were arranged into a set of clusters using the k-means clustering technique. A fleet of 19 PTs was used to validate the proposed method. The obtained results are also provided to demonstrate the viability and feasibility of the assessment model.
Citation: Algorithms
PubDate: 2021-10-31
DOI: 10.3390/a14110319
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 320: Load Balancing Strategies for Slice-Based
Parallel Versions of JEM Video Encoder
Authors: Héctor Migallón, Otoniel López-Granado, Miguel O. Martínez-Rach, Vicente Galiano, Manuel P. Malumbres
First page: 320
Abstract: The proportion of video traffic on the internet is expected to reach 82% by 2022, mainly due to the increasing number of consumers and the emergence of new video formats with more demanding features (depth, resolution, multiview, 360, etc.). Efforts are therefore being made to constantly improve video compression standards to minimize the necessary bandwidth while retaining high video quality levels. In this context, the Joint Collaborative Team on Video Coding has been analyzing new video coding technologies to improve the compression efficiency with respect to the HEVC video coding standard. A software package known as the Joint Exploration Test Model has been proposed to implement and evaluate new video coding tools. In this work, we present parallel versions of the JEM encoder that are particularly suited for shared memory platforms, and can significantly reduce its huge computational complexity. The proposed parallel algorithms are shown to achieve high levels of parallel efficiency. In particular, in the All Intra coding mode, the best of our proposed parallel versions achieves an average efficiency value of 93.4%. They also had high levels of scalability, as shown by the inclusion of an automatic load balancing mechanism.
Citation: Algorithms
PubDate: 2021-11-01
DOI: 10.3390/a14110320
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 321: Path Planning of a Mechanical Arm Based on
an Improved Artificial Potential Field and a Rapid Expansion Random Tree
Hybrid Algorithm
Authors: Qingni Yuan, Junhui Yi, Ruitong Sun, Huan Bai
First page: 321
Abstract: To improve the path planning efficiency of a robotic arm in three-dimensional space and improve the obstacle avoidance ability, this paper proposes an improved artificial potential field and rapid expansion random tree (APF-RRT) hybrid algorithm for the mechanical arm path planning method. The improved APF algorithm (I-APF) introduces a heuristic method based on the number of adjacent obstacles to escape from local minima, which solves the local minimum problem of the APF method and improves the search speed. The improved RRT algorithm (I-RRT) changes the selection method of the nearest neighbor node by introducing a triangular nearest neighbor node selection method, adopts an adaptive step and generates a virtual new node strategy to explore the path, and removes redundant path nodes generated by the RRT algorithm, which effectively improves the obstacle avoidance ability and efficiency of the algorithm. Bezier curves are used to fit the final generated path. Finally, an experimental analysis based on Python shows that the search time of the hybrid algorithm in a multi-obstacle environment is reduced to 2.8 s from 37.8 s (classic RRT algorithm), 10.1 s (RRT* algorithm), and 7.4 s (P_RRT* algorithm), and the success rate and efficiency of the search are both significantly improved. Furthermore, the hybrid algorithm is simulated in a robot operating system (ROS) using the UR5 mechanical arm, and the results prove the effectiveness and reliability of the hybrid algorithm.
Citation: Algorithms
PubDate: 2021-11-01
DOI: 10.3390/a14110321
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 322: Robust Bilinear Probabilistic Principal
Component Analysis
Authors: Yaohang Lu, Zhongming Teng
First page: 322
Abstract: Principal component analysis (PCA) is one of the most popular tools in multivariate exploratory data analysis. Its probabilistic version (PPCA) based on the maximum likelihood procedure provides a probabilistic manner to implement dimension reduction. Recently, the bilinear PPCA (BPPCA) model, which assumes that the noise terms follow matrix variate Gaussian distributions, has been introduced to directly deal with two-dimensional (2-D) data for preserving the matrix structure of 2-D data, such as images, and avoiding the curse of dimensionality. However, Gaussian distributions are not always available in real-life applications which may contain outliers within data sets. In order to make BPPCA robust for outliers, in this paper, we propose a robust BPPCA model under the assumption of matrix variate t distributions for the noise terms. The alternating expectation conditional maximization (AECM) algorithm is used to estimate the model parameters. Numerical examples on several synthetic and publicly available data sets are presented to demonstrate the superiority of our proposed model in feature extraction, classification and outlier detection.
Citation: Algorithms
PubDate: 2021-11-01
DOI: 10.3390/a14110322
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 323: Metaheuristics for a Flow Shop Scheduling
Problem with Urgent Jobs and Limited Waiting Times
Authors: BongJoo Jeong, Jun-Hee Han, Ju-Yong Lee
First page: 323
Abstract: This study considers a scheduling problem for a flow shop with urgent jobs and limited waiting times. The urgent jobs and limited waiting times are major considerations for scheduling in semiconductor manufacturing systems. The objective function is to minimize a weighted sum of total tardiness of urgent jobs and the makespan of normal jobs. This problem is formulated in mixed integer programming (MIP). By using a commercial optimization solver, the MIP can be used to find an optimal solution. However, because this problem is proved to be NP-hard, solving to optimality requires a significantly long computation time for a practical size problem. Therefore, this study adopts metaheuristic algorithms to obtain a good solution quickly. To complete this, two metaheuristic algorithms (an iterated greedy algorithm and a simulated annealing algorithm) are proposed, and a series of computational experiments were performed to examine the effectiveness and efficiency of the proposed algorithms.
Citation: Algorithms
PubDate: 2021-11-03
DOI: 10.3390/a14110323
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 324: Feature Selection for High-Dimensional
Datasets through a Novel Artificial Bee Colony Framework
Authors: Yuanzi Zhang, Jing Wang, Xiaolin Li, Shiguo Huang, Xiuli Wang
First page: 324
Abstract: There are generally many redundant and irrelevant features in high-dimensional datasets, which leads to the decline of classification performance and the extension of execution time. To tackle this problem, feature selection techniques are used to screen out redundant and irrelevant features. The artificial bee colony (ABC) algorithm is a popular meta-heuristic algorithm with high exploration and low exploitation capacities. To balance between both capacities of the ABC algorithm, a novel ABC framework is proposed in this paper. Specifically, the solutions are first updated by the process of employing bees to retain the original exploration ability, so that the algorithm can explore the solution space extensively. Then, the solutions are modified by the updating mechanism of an algorithm with strong exploitation ability in the onlooker bee phase. Finally, we remove the scout bee phase from the framework, which can not only reduce the exploration ability but also speed up the algorithm. In order to verify our idea, the operators of the grey wolf optimization (GWO) algorithm and whale optimization algorithm (WOA) are introduced into the framework to enhance the exploitation capability of onlooker bees, named BABCGWO and BABCWOA, respectively. It has been found that these two algorithms are superior to four state-of-the-art feature selection algorithms using 12 high-dimensional datasets, in terms of the classification error rate, size of feature subset and execution speed.
Citation: Algorithms
PubDate: 2021-11-04
DOI: 10.3390/a14110324
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 325: Travel Time Reliability-Based Rescue
Resource Scheduling for Accidents Concerning Transport of Dangerous Goods
by Rail
Authors: Lanfen Liu, Xinfeng Yang
First page: 325
Abstract: The characteristics of railway dangerous goods accidents are very complex. The rescue of railway dangerous goods accidents should consider the timeliness of rescue, the uncertainty of traffic environment and the diversity of rescue resources. Thus, the purpose of this paper is to confront the rescue resources scheduling problem of railway dangerous goods accident by considering factors such as rescue capacity, rescue demand and response time. Based on the analysis of travel time and reliability for rescue route, a multi-objective scheduling model of rescue resources based on travel time reliability is constructed in order to minimize the total arrival time of rescue resources and to maximize total reliability. The proposed model is more reliable than the traditional model due to the consideration of travel time reliability of rescue routes. Moreover, a two-stage algorithm is designed to solve this problem. A multi-path algorithm with bound constraints is used to obtain the set of feasible rescue routes in the first stage, and the NSGA-II algorithm is used to determine the scheduling of rescue resources for each rescue center. Finally, the two-stage algorithm is tested on a regional road network, and the results show that the designed two-stage algorithm is valid for solving the rescue resource scheduling problem of dangerous goods accidents and is able to obtain the rescue resource scheduling scheme in a short period of time.
Citation: Algorithms
PubDate: 2021-11-05
DOI: 10.3390/a14110325
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 326: Optimized Dissolved Oxygen Fuzzy Control
for Recombinant Escherichia coli Cultivations
Authors: Rafael Akira Akisue, Matheus Lopes Harth, Antonio Carlos Luperni Horta, Ruy de Sousa Junior
First page: 326
Abstract: Due to low oxygen solubility and mechanical stirring limitations of a bioreactor, ensuring an adequate oxygen supply during a recombinant Escherichia coli cultivation is a major challenge in process control. Under the light of this fact, a fuzzy dissolved oxygen controller was developed, taking into account a decision tree algorithm presented in the literature, and implemented in the supervision software SUPERSYS_HCDC. The algorithm was coded in MATLAB with its membership function parameters determined using an Adaptive Network-Based Fuzzy Inference System tool. The controller was composed of three independent fuzzy inference systems: Princ1 and Princ2 assessed whether there would be an increment or a reduction in air and oxygen flow rates (respectively), whilst Delta estimated the size of these variations. To test the controller, simulations with a neural network model and E. coli cultivations were conducted. The fuzzification of the decision tree was successful, resulting in smoothing of air and oxygen flow rates and, hence, in an attenuation of dissolved oxygen oscillations. Statistically, the average standard deviation of the fuzzy controller was 2.45 times lower than the decision tree (9.48%). Results point toward an increase in the flow meter lifespan and a possible reduction of the metabolic stress suffered by E. coli during the cultivation.
Citation: Algorithms
PubDate: 2021-11-05
DOI: 10.3390/a14110326
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 327: Hybrid Multiagent Collaboration for
Time-Critical Tasks: A Mathematical Model and Heuristic Approach
Authors: Yifeng Zhou, Kai Di, Haokun Xing
First page: 327
Abstract: Principal–assistant agent teams are often employed to solve tasks in multiagent collaboration systems. Assistant agents attached to the principal agents are more flexible for task execution and can assist them to complete tasks with complex constraints. However, how to employ principal–assistant agent teams to execute time-critical tasks considering the dependency between agents and the constraints among tasks is still a challenge so far. In this paper, we investigate the principal–assistant collaboration problem with deadlines, which is to allocate tasks to suitable principal–assistant teams and construct routes satisfying the temporal constraints. Two cases are considered in this paper, including single principal–assistant teams and multiple principal–assistant teams. The former is formally formulated in an arc-based integer linear programming model. We develop a hybrid combination algorithm for adapting larger scales, the idea of which is to find an optimal combination of partial routes generated by heuristic methods. The latter is defined in a path-based integer linear programming model, and a branch-and-price-based (BP-based) algorithm is proposed that introduces the number of assistant-accessible tasks surrounding a task to guide the route construction. Experimental results validate that the hybrid combination algorithm and the BP-based algorithm are superior to the benchmarks in terms of the number of served tasks and the running time.
Citation: Algorithms
PubDate: 2021-11-05
DOI: 10.3390/a14110327
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 328: Adaptive Refinement in
Advection–Diffusion Problems by Anomaly Detection: A Numerical Study
Authors: Antonella Falini, Maria Lucia Sampoli
First page: 328
Abstract: We consider advection–diffusion–reaction problems, where the advective or the reactive term is dominating with respect to the diffusive term. The solutions of these problems are characterized by the so-called layers, which represent localized regions where the gradients of the solutions are rather large or are subjected to abrupt changes. In order to improve the accuracy of the computed solution, it is fundamental to locally increase the number of degrees of freedom by limiting the computational costs. Thus, adaptive refinement, by a posteriori error estimators, is employed. The error estimators are then processed by an anomaly detection algorithm in order to identify those regions of the computational domain that should be marked and, hence, refined. The anomaly detection task is performed in an unsupervised fashion and the proposed strategy is tested on typical benchmarks. The present work shows a numerical study that highlights promising results obtained by bridging together standard techniques, i.e., the error estimators, and approaches typical of machine learning and artificial intelligence, such as the anomaly detection task.
Citation: Algorithms
PubDate: 2021-11-07
DOI: 10.3390/a14110328
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 329: Zero-Crossing Point Detection of
Sinusoidal Signal in Presence of Noise and Harmonics Using Deep Neural
Networks
Authors: Venkataramana Veeramsetty, Bhavana Reddy Edudodla, Surender Reddy Salkuti
First page: 329
Abstract: Zero-crossing point detection is necessary to establish a consistent performance in various power system applications, such as grid synchronization, power conversion and switch-gear protection. In this paper, zero-crossing points of a sinusoidal signal are detected using deep neural networks. In order to train and evaluate the deep neural network model, new datasets for sinusoidal signals having noise levels from 5% to 50% and harmonic distortion from 10% to 50% are developed. This complete study is implemented in Google Colab using deep learning framework Keras. Results shows that the proposed deep learning model is able to detect zero-crossing points in a distorted sinusoidal signal with good accuracy.
Citation: Algorithms
PubDate: 2021-11-08
DOI: 10.3390/a14110329
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 330: Autoencoder-Based Reduced Order Observer
Design for a Class of Diffusion-Convection-Reaction Systems
Authors: Alexander Schaum
First page: 330
Abstract: The application of autoencoders in combination with Dynamic Mode Decomposition for control (DMDc) and reduced order observer design as well as Kalman Filter design is discussed for low order state reconstruction of a class of scalar linear diffusion-convection-reaction systems. The general idea and conceptual approaches are developed following recent results on machine-learning based identification of the Koopman operator using autoencoders and DMDc for finite-dimensional discrete-time system identification. The resulting linear reduced order model is combined with a classical Kalman Filter for state reconstruction with minimum error covariance as well as a reduced order observer with very low computational and memory demands. The performance of the two schemes is evaluated and compared in terms of the approximated L2 error norm in a numerical simulation study. It turns out, that for the evaluated case study the reduced-order scheme achieves comparable performance with significantly less computational load.
Citation: Algorithms
PubDate: 2021-11-11
DOI: 10.3390/a14110330
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 331: A Mathematical Model of Universal Basic
Income and Its Numerical Simulations
Authors: Maria Letizia Bertotti
First page: 331
Abstract: In this paper, an elementary mathematical model describing the introduction of a universal basic income in a closed market society is constructed. The model is formulated in terms of a system of nonlinear ordinary differential equations, each of which gives account of how the number of individuals in a certain income class changes in time. Societies ruled by different fiscal systems (with no taxes, with taxation and redistribution, with a welfare system) are considered and the effect of the presence of a basic income in the various cases is analysed by means of numerical simulations. The main findings are that basic income effectively acts as a tool of poverty alleviation: indeed, in its presence the portion of individuals in the poorest classes and economic inequality diminish. Of course, the issue of a universal basic income in the real world is more complex and involves a variety of aspects. The goal here is simply to show how mathematical models can help in forecasting scenarios resulting from one or the other policy.
Citation: Algorithms
PubDate: 2021-11-11
DOI: 10.3390/a14110331
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 332: Application of Mini-Batch Metaheuristic
Algorithms in Problems of Optimization of Deterministic Systems with
Incomplete Information about the State Vector
Authors: Andrei V. Panteleev, Aleksandr V. Lobanov
First page: 332
Abstract: In this paper, we consider the application of the zero-order mini-batch optimization method in the problem of finding optimal control of a pencil of trajectories of nonlinear deterministic systems in the case of incomplete information about the state vector. The pencil of trajectories originates from a given set of initial states. To solve the problem, the structure of a feedback system is proposed, which contains models of the plant, measuring system, nonlinear state observer and control law of the fixed structure with unknown coefficients. The objective function proposed considers the quality of pencil of trajectories control, which is estimated by the average value of the Bolz functional over the given set of initial states. Unknown control laws of a plant and an observer are found in the form of expansions in terms of orthonormal systems of basis functions, which are specified on the set of possible states of a dynamical system. The original pencil of trajectories control problem is reduced to a global optimization problem, which is solved using the well-proven zero-order method, which uses a modified mini-batch approach in a random search procedure with adaptation. An algorithm for solving the problem is proposed. The satellite stabilization problem with incomplete information is solved.
Citation: Algorithms
PubDate: 2021-11-14
DOI: 10.3390/a14110332
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 333: Parallel Implementation of the Algorithm
to Compute Forest Fire Impact on Infrastructure Facilities of JSC Russian
Railways
Authors: Nikolay Viktorovich Baranovskiy, Aleksey Podorovskiy, Aleksey Malinin
First page: 333
Abstract: Forest fires have a negative impact on the economy in a number of regions, especially in Wildland Urban Interface (WUI) areas. An important link in the fight against fires in WUI areas is the development of information and computer systems for predicting the fire safety of infrastructural facilities of Russian Railways. In this work, a numerical study of heat transfer processes in the enclosing structure of a wooden building near the forest fire front was carried out using the technology of parallel computing. The novelty of the development is explained by the creation of its own program code, which is planned to be put into operation either in the Information System for Remote Monitoring of Forest Fires ISDM-Rosleskhoz, or in the information and computing system of JSC Russian Railways. In the Russian Federation, it is forbidden to use foreign systems in the security services of industrial facilities. The implementation of the deterministic model of heat transfer in the enclosing structure with the complexity of the algorithm O (2N2 + 2K) is presented. The program is implemented in Python 3.x using the NumPy and Concurrent libraries. Calculations were carried out on a multiprocessor cluster in the Sirius University of Science and Technology. The results of calculations and the acceleration coefficient for operating modes for 1, 2, 4, 8, 16, 32, 48 and 64 processes are presented. The developed algorithm can be applied to assess the fire safety of infrastructure facilities of Russian Railways. The main merit of the new development should be noted, which is explained by the ability to use large computational domains with a large number of computational grid nodes in space and time. The use of caching intermediate data in files made it possible to distribute a large number of computational nodes among the processors of a computing multiprocessor system. However, one should also note a drawback; namely, a decrease in the acceleration of computational operations with a large number of involved nodes of a multiprocessor computing system, which is explained by the write and read cycles in cache files.
Citation: Algorithms
PubDate: 2021-11-15
DOI: 10.3390/a14110333
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 334: Is One Teacher Model Enough to Transfer
Knowledge to a Student Model'
Authors: Nicola Landro, Ignazio Gallo, Riccardo La Grassa
First page: 334
Abstract: Nowadays, the transfer learning technique can be successfully applied in the deep learning field through techniques that fine-tune the CNN’s starting point so it may learn over a huge dataset such as ImageNet and continue to learn on a fixed dataset to achieve better performance. In this paper, we designed a transfer learning methodology that combines the learned features of different teachers to a student network in an end-to-end model, improving the performance of the student network in classification tasks over different datasets. In addition to this, we tried to answer the following questions which are in any case directly related to the transfer learning problem addressed here. Is it possible to improve the performance of a small neural network by using the knowledge gained from a more powerful neural network' Can a deep neural network outperform the teacher using transfer learning' Experimental results suggest that neural networks can transfer their learning to student networks using our proposed architecture, designed to bring to light a new interesting approach for transfer learning techniques. Finally, we provide details of the code and the experimental settings.
Citation: Algorithms
PubDate: 2021-11-15
DOI: 10.3390/a14110334
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 335: A Context-Aware Neural Embedding for
Function-Level Vulnerability Detection
Authors: Hongwei Wei, Guanjun Lin, Lin Li, Heming Jia
First page: 335
Abstract: Exploitable vulnerabilities in software systems are major security concerns. To date, machine learning (ML) based solutions have been proposed to automate and accelerate the detection of vulnerabilities. Most ML techniques aim to isolate a unit of source code, be it a line or a function, as being vulnerable. We argue that a code segment is vulnerable if it exists in certain semantic contexts, such as the control flow and data flow; therefore, it is important for the detection to be context aware. In this paper, we evaluate the performance of mainstream word embedding techniques in the scenario of software vulnerability detection. Based on the evaluation, we propose a supervised framework leveraging pre-trained context-aware embeddings from language models (ELMo) to capture deep contextual representations, further summarized by a bidirectional long short-term memory (Bi-LSTM) layer for learning long-range code dependency. The framework takes directly a source code function as an input and produces corresponding function embeddings, which can be treated as feature sets for conventional ML classifiers. Experimental results showed that the proposed framework yielded the best performance in its downstream detection tasks. Using the feature representations generated by our framework, random forest and support vector machine outperformed four baseline systems on our data sets, demonstrating that the framework incorporated with ELMo can effectively capture the vulnerable data flow patterns and facilitate the vulnerability detection task.
Citation: Algorithms
PubDate: 2021-11-17
DOI: 10.3390/a14110335
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 336: Decomposition of Random Sequences into
Mixtures of Simpler Ones and Its Application in Network Analysis
Authors: András Faragó
First page: 336
Abstract: A classic and fundamental result about the decomposition of random sequences into a mixture of simpler ones is de Finetti’s Theorem. In its original form, it applies to infinite 0–1 valued sequences with the special property that the distribution is invariant to permutations (called an exchangeable sequence). Later it was extended and generalized in numerous directions. After reviewing this line of development, we present our new decomposition theorem, covering cases that have not been previously considered. We also introduce a novel way of applying these types of results in the analysis of random networks. For self-containment, we provide the introductory exposition in more detail than usual, with the intent of making it also accessible to readers who may not be closely familiar with the subject.
Citation: Algorithms
PubDate: 2021-11-19
DOI: 10.3390/a14110336
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 337: An Interaction-Based Convolutional Neural
Network (ICNN) Toward a Better Understanding of COVID-19 X-ray Images
Authors: Shaw-Hwa Lo, Yiqiao Yin
First page: 337
Abstract: The field of explainable artificial intelligence (XAI) aims to build explainable and interpretable machine learning (or deep learning) methods without sacrificing prediction performance. Convolutional neural networks (CNNs) have been successful in making predictions, especially in image classification. These popular and well-documented successes use extremely deep CNNs such as VGG16, DenseNet121, and Xception. However, these well-known deep learning models use tens of millions of parameters based on a large number of pretrained filters that have been repurposed from previous data sets. Among these identified filters, a large portion contain no information yet remain as input features. Thus far, there is no effective method to omit these noisy features from a data set, and their existence negatively impacts prediction performance. In this paper, a novel interaction-based convolutional neural network (ICNN) is introduced that does not make assumptions about the relevance of local information. Instead, a model-free influence score (I-score) is proposed to directly extract the influential information from images to form important variable modules. This innovative technique replaces all pretrained filters found by trial-and-error with explainable, influential, and predictive variable sets (modules) determined by the I-score. In other words, future researchers need not rely on pretrained filters; the suggested algorithm identifies only the variables or pixels with high I-score values that are extremely predictive and important. The proposed method and algorithm were tested on real-world data set and a state-of-the-art prediction performance of 99.8% was achieved without sacrificing the explanatory power of the model. This proposed design can efficiently screen patients infected by COVID-19 before human diagnosis and can be a benchmark for addressing future XAI problems in large-scale data sets.
Citation: Algorithms
PubDate: 2021-11-19
DOI: 10.3390/a14110337
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 338: An Empirical Study of Cluster-Based MOEA/D
Bare Bones PSO for Data Clustering
Authors: Daphne Teck Ching Lai, Yuji Sato
First page: 338
Abstract: Previously, cluster-based multi or many objective function techniques were proposed to reduce the Pareto set. Recently, researchers proposed such techniques to find better solutions in the objective space to solve engineering problems. In this work, we applied a cluster-based approach for solution selection in a multiobjective evolutionary algorithm based on decomposition with bare bones particle swarm optimization for data clustering and investigated its clustering performance. In our previous work, we found that MOEA/D with BBPSO performed the best on 10 datasets. Here, we extend this work applying a cluster-based approach tested on 13 UCI datasets. We compared with six multiobjective evolutionary clustering algorithms from the existing literature and ten from our previous work. The proposed technique was found to perform well on datasets highly overlapping clusters, such as CMC and Sonar. So far, we found only one work that used cluster-based MOEA for clustering data, the hierarchical topology multiobjective clustering algorithm. All other cluster-based MOEA found were used to solve other problems that are not data clustering problems. By clustering Pareto solutions and evaluating new candidates against the found cluster representatives, local search is introduced in the solution selection process within the objective space, which can be effective on datasets with highly overlapping clusters. This is an added layer of search control in the objective space. The results are found to be promising, prompting different areas of future research which are discussed, including the study of its effects with an increasing number of clusters as well as with other objective functions.
Citation: Algorithms
PubDate: 2021-11-22
DOI: 10.3390/a14110338
Issue No: Vol. 14, No. 11 (2021)
- Algorithms, Vol. 14, Pages 278: Ensembling EfficientNets for the
Classification and Interpretation of Histopathology Images
Authors: Athanasios Kallipolitis, Kyriakos Revelos, Ilias Maglogiannis
First page: 278
Abstract: The extended utilization of digitized Whole Slide Images is transforming the workflow of traditional clinical histopathology to the digital era. The ongoing transformation has demonstrated major potentials towards the exploitation of Machine Learning and Deep Learning techniques as assistive tools for specialized medical personnel. While the performance of the implemented algorithms is continually boosted by the mass production of generated Whole Slide Images and the development of state-of the-art deep convolutional architectures, ensemble models provide an additional methodology towards the improvement of the prediction accuracy. Despite the earlier belief related to deep convolutional networks being treated as black boxes, important steps for the interpretation of such predictive models have also been proposed recently. However, this trend is not fully unveiled for the ensemble models. The paper investigates the application of an explanation scheme for ensemble classifiers, while providing satisfactory classification results of histopathology breast and colon cancer images in terms of accuracy. The results can be interpreted by the hidden layers’ activation of the included subnetworks and provide more accurate results than single network implementations.
Citation: Algorithms
PubDate: 2021-09-26
DOI: 10.3390/a14100278
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 279: Short Communication: Optimally Solving the
Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in
Cubic Time
Authors: Marcos M. Salvatierra, Mario Salvatierra, Juan G. Colonna
First page: 279
Abstract: In general, the unit-demand envy-free pricing problem has proven to be APX-hard, but some special cases can be optimally solved in polynomial time. When substitution costs that form a metric space are included, the problem can be solved in O(n4) time, and when the number of consumers is equal to the number of items—all with a single copy so that each consumer buys an item—a O(n3) time method is presented to solve it. This work shows that the first case has similarities with the second, and, by exploiting the structural properties of the costs set, it presents a O(n2) time algorithm for solving it when a competitive equilibrium is considered or a O(n3) time algorithm for more general scenarios. The methods are based on a dynamic programming strategy, which simplifies the calculations of the shortest paths in a network; this simplification is usually adopted in the second case. The theoretical results obtained provide efficiency in the search for optimal solutions to specific revenue management problems.
Citation: Algorithms
PubDate: 2021-09-26
DOI: 10.3390/a14100279
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 280: A Brief Roadmap into Uncertain Knowledge
Representation via Probabilistic Description Logics
Authors: Rafael Peñaloza
First page: 280
Abstract: Logic-based knowledge representation is one of the main building blocks of (logic-based) artificial intelligence. While most successful knowledge representation languages are based on classical logic, realistic intelligent applications need to handle uncertainty in an adequate manner. Over the years, many different languages for representing uncertain knowledge—often extensions of classical knowledge representation languages—have been proposed. We briefly present some of the defining properties of these languages as they pertain to the family of probabilistic description logics. This limited view is intended to help pave the way for the interested researcher to find the most adequate language for their needs, and potentially identify the remaining gaps.
Citation: Algorithms
PubDate: 2021-09-28
DOI: 10.3390/a14100280
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 281: Information Fusion-Based Deep Neural
Attentive Matrix Factorization Recommendation
Authors: Zhen Tian, Lamei Pan, Pu Yin, Rui Wang
First page: 281
Abstract: The emergence of the recommendation system has effectively alleviated the information overload problem. However, traditional recommendation systems either ignore the rich attribute information of users and items, such as the user’s social-demographic features, the item’s content features, etc., facing the sparsity problem, or adopt the fully connected network to concatenate the attribute information, ignoring the interaction between the attribute information. In this paper, we propose the information fusion-based deep neural attentive matrix factorization (IFDNAMF) recommendation model, which introduces the attribute information and adopts the element-wise product between the different information domains to learn the cross-features when conducting information fusion. In addition, the attention mechanism is utilized to distinguish the importance of different cross-features on prediction results. In addition, the IFDNAMF adopts the deep neural network to learn the high-order interaction between users and items. Meanwhile, we conduct extensive experiments on two datasets: MovieLens and Book-crossing, and demonstrate the feasibility and effectiveness of the model.
Citation: Algorithms
PubDate: 2021-09-28
DOI: 10.3390/a14100281
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 282: Simultaneous Feature Selection and Support
Vector Machine Optimization Using an Enhanced Chimp Optimization Algorithm
Authors: Wu, Zhang, Jia, Leng
First page: 282
Abstract: Chimp Optimization Algorithm (ChOA), a novel meta-heuristic algorithm, has been proposed in recent years. It divides the population into four different levels for the purpose of hunting. However, there are still some defects that lead to the algorithm falling into the local optimum. To overcome these defects, an Enhanced Chimp Optimization Algorithm (EChOA) is developed in this paper. Highly Disruptive Polynomial Mutation (HDPM) is introduced to further explore the population space and increase the population diversity. Then, the Spearman’s rank correlation coefficient between the chimps with the highest fitness and the lowest fitness is calculated. In order to avoid the local optimization, the chimps with low fitness values are introduced with Beetle Antenna Search Algorithm (BAS) to obtain visual ability. Through the introduction of the above three strategies, the ability of population exploration and exploitation is enhanced. On this basis, this paper proposes an EChOA-SVM model, which can optimize parameters while selecting the features. Thus, the maximum classification accuracy can be achieved with as few features as possible. To verify the effectiveness of the proposed method, the proposed method is compared with seven common methods, including the original algorithm. Seventeen benchmark datasets from the UCI machine learning library are used to evaluate the accuracy, number of features, and fitness of these methods. Experimental results show that the classification accuracy of the proposed method is better than the other methods on most data sets, and the number of features required by the proposed method is also less than the other algorithms.
Citation: Algorithms
PubDate: 2021-09-28
DOI: 10.3390/a14100282
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 283: XGB4mcPred: Identification of DNA
N4-Methylcytosine Sites in Multiple Species Based on an eXtreme Gradient
Boosting Algorithm and DNA Sequence Information
Authors: Xiao Wang, Xi Lin, Rong Wang, Kai-Qi Fan, Li-Jun Han, Zhao-Yuan Ding
First page: 283
Abstract: DNA N4-methylcytosine(4mC) plays an important role in numerous biological functions and is a mechanism of particular epigenetic importance. Therefore, accurate identification of the 4mC sites in DNA sequences is necessary to understand the functional mechanism. Although some effective calculation tools have been proposed to identifying DNA 4mC sites, it is still challenging to improve identification accuracy and generalization ability. Therefore, there is a great need to build a computational tool to accurately identify the position of DNA 4mC sites. Hence, this study proposed a novel predictor XGB4mcPred, a predictor for the identification of 4mC sites trained using an extreme gradient boosting algorithm (XGBoost) and DNA sequence information. Firstly, we used the One-Hot encoding on adjacent and spaced nucleotides, dinucleotides, and trinucleotides of the original 4mC site sequences as feature vectors. Then, the importance values of the feature vectors pre-trained by the XGBoost algorithm were used as a threshold to filter redundant features, resulting in a significant improvement in the identification accuracy of the constructed XGB4mcPred predictor to identify 4mC sites. The analysis shows that there is a clear preference for nucleotide sequences between 4mC sites and non-4mC site sequences in six datasets from multiple species, and the optimized features can better distinguish 4mC sites from non-4mC sites. The experimental results of cross-validation and independent tests from six different species show that our proposed predictor XGB4mcPred significantly outperformed other state-of-the-art predictors and was improved to varying degrees compared with other state-of-the-art predictors. Additionally, the user-friendly webserver we used to developed the XGB4mcPred predictor was made freely accessible.
Citation: Algorithms
PubDate: 2021-09-29
DOI: 10.3390/a14100283
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 284: FPGA-Based Linear Detection Algorithm of
an Underground Inspection Robot
Authors: Chuanwei Zhang, Shirui Chen, Lu Zhao, Xianghe Li, Xiaowen Ma
First page: 284
Abstract: Conveyor belts are key pieces of equipment for bulk material transport, and they are of great significance to ensure safe operation. With the development of belt conveyors in the direction of long distances, large volumes, high speeds, and high reliability, the use of inspection robots to perform full inspections of belt conveyors has not only improved the efficiency and scope of the inspections but has also eliminated the dependence of the traditional method on the density of sensor arrangement. In this paper, relying on the wireless-power-supply orbital inspection robot independently developed by the laboratory, aimed at the problem of the deviation of the belt conveyor, the methods for the diagnosis of the deviation of the conveyor belt and FPGA (field-programmable gate array) parallel computing technology are studied. Based on the traditional LSD (line segment detection) algorithm, a straight-line extraction IP core, suitable for an FPGA computing platform, was constructed. This new hardware linear detection algorithm improves the real-time performance and flexibility of the belt conveyor diagnosis mechanism.
Citation: Algorithms
PubDate: 2021-09-29
DOI: 10.3390/a14100284
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 285: Efficient and Portable Distribution
Modeling for Large-Scale Scientific Data Processing with Data-Parallel
Primitives
Authors: Hao-Yi Yang, Zhi-Rong Lin, Ko-Chih Wang
First page: 285
Abstract: The use of distribution-based data representation to handle large-scale scientific datasets is a promising approach. Distribution-based approaches often transform a scientific dataset into many distributions, each of which is calculated from a small number of samples. Most of the proposed parallel algorithms focus on modeling single distributions from many input samples efficiently, but these may not fit the large-scale scientific data processing scenario because they cannot utilize computing resources effectively. Histograms and the Gaussian Mixture Model (GMM) are the most popular distribution representations used to model scientific datasets. Therefore, we propose the use of multi-set histogram and GMM modeling algorithms for the scenario of large-scale scientific data processing. Our algorithms are developed by data-parallel primitives to achieve portability across different hardware architectures. We evaluate the performance of the proposed algorithms in detail and demonstrate use cases for scientific data processing.
Citation: Algorithms
PubDate: 2021-09-29
DOI: 10.3390/a14100285
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 286: Enhanced Hyper-Cube Framework Ant Colony
Optimization for Combinatorial Optimization Problems
Authors: Ali Ahmid, Thien-My Dao, Ngan Van Le
First page: 286
Abstract: Solving of combinatorial optimization problems is a common practice in real-life engineering applications. Trusses, cranes, and composite laminated structures are some good examples that fall under this category of optimization problems. Those examples have a common feature of discrete design domain that turn them into a set of NP-hard optimization problems. Determining the right optimization algorithm for such problems is a precious point that tends to impact the overall cost of the design process. Furthermore, reinforcing the performance of a prospective optimization algorithm reduces the design cost. In the current study, a comprehensive assessment criterion has been developed to assess the performance of meta-heuristic (MH) solutions in the domain of structural design. Thereafter, the proposed criterion was employed to compare five different variants of Ant Colony Optimization (ACO). It was done by using a well-known structural optimization problem of laminate Stacking Sequence Design (SSD). The initial results of the comparison study reveal that the Hyper-Cube Framework (HCF) ACO variant outperforms the others. Consequently, an investigation of further improvement led to introducing an enhanced version of HCFACO (or EHCFACO). Eventually, the performance assessment of the EHCFACO variant showed that the average practical reliability became more than twice that of the standard ACO, and the normalized price decreased more to hold at 28.92 instead of 51.17.
Citation: Algorithms
PubDate: 2021-09-29
DOI: 10.3390/a14100286
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 287: Closed-Loop Cognitive-Driven Gain Control
of Competing Sounds Using Auditory Attention Decoding
Authors: Ali Aroudi, Eghart Fischer, Maja Serman, Henning Puder, Simon Doclo
First page: 287
Abstract: Recent advances have shown that it is possible to identify the target speaker which a listener is attending to using single-trial EEG-based auditory attention decoding (AAD). Most AAD methods have been investigated for an open-loop scenario, where AAD is performed in an offline fashion without presenting online feedback to the listener. In this work, we aim at developing a closed-loop AAD system that allows to enhance a target speaker, suppress an interfering speaker and switch attention between both speakers. To this end, we propose a cognitive-driven adaptive gain controller (AGC) based on real-time AAD. Using the EEG responses of the listener and the speech signals of both speakers, the real-time AAD generates probabilistic attention measures, based on which the attended and the unattended speaker are identified. The AGC then amplifies the identified attended speaker and attenuates the identified unattended speaker, which are presented to the listener via loudspeakers. We investigate the performance of the proposed system in terms of the decoding performance and the signal-to-interference ratio (SIR) improvement. The experimental results show that, although there is a significant delay to detect attention switches, the proposed system is able to improve the SIR between the attended and the unattended speaker. In addition, no significant difference in decoding performance is observed between closed-loop AAD and open-loop AAD. The subjective evaluation results show that the proposed closed-loop cognitive-driven system demands a similar level of cognitive effort to follow the attended speaker, to ignore the unattended speaker and to switch attention between both speakers compared to using open-loop AAD. Closed-loop AAD in an online fashion is feasible and enables the listener to interact with the AGC.
Citation: Algorithms
PubDate: 2021-09-30
DOI: 10.3390/a14100287
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 288: Machine Learning-Based Prediction of the
Seismic Bearing Capacity of a Shallow Strip Footing over a Void in
Heterogeneous Soils
Authors: Mohammad Sadegh Es-haghi, Mohsen Abbaspour, Hamidreza Abbasianjahromi, Stefano Mariani
First page: 288
Abstract: The seismic bearing capacity of a shallow strip footing above a void displays a complex dependence on several characteristics, linked to geometric problems and to the soil properties. Hence, setting analytical models to estimate such bearing capacity is extremely challenging. In this work, machine learning (ML) techniques have been employed to predict the seismic bearing capacity of a shallow strip footing located over a single unsupported rectangular void in heterogeneous soil. A dataset consisting of 38,000 finite element limit analysis simulations has been created, and the mean value between the upper and lower bounds of the bearing capacity has been computed at the varying undrained shear strength and internal friction angle of the soil, horizontal earthquake accelerations, and position, shape, and size of the void. Three machine learning techniques have been adopted to learn the link between the aforementioned parameters and the bearing capacity: multilayer perceptron neural networks; a group method of data handling; and a combined adaptive-network-based fuzzy inference system and particle swarm optimization. The performances of these ML techniques have been compared with each other, in terms of the following statistical performance indices: coefficient of determination (); root mean square error (); mean absolute percentage error; scatter index; and standard bias. Results have shown that all the ML techniques perform well, though the multilayer perceptron has a slightly superior accuracy featuring noteworthy results (0.9955 and 0.0158).
Citation: Algorithms
PubDate: 2021-09-30
DOI: 10.3390/a14100288
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 289: Comparing Commit Messages and Source Code
Metrics for the Prediction Refactoring Activities
Authors: Priyadarshni Suresh Sagar, Eman Abdulah AlOmar, Mohamed Wiem Mkaouer, Ali Ouni, Christian D. Newman
First page: 289
Abstract: Understanding how developers refactor their code is critical to support the design improvement process of software. This paper investigates to what extent code metrics are good indicators for predicting refactoring activity in the source code. In order to perform this, we formulated the prediction of refactoring operation types as a multi-class classification problem. Our solution relies on measuring metrics extracted from committed code changes in order to extract the corresponding features (i.e., metric variations) that better represent each class (i.e., refactoring type) in order to automatically predict, for a given commit, the method-level type of refactoring being applied, namely Move Method, Rename Method, Extract Method, Inline Method, Pull-up Method, and Push-down Method. We compared various classifiers, in terms of their prediction performance, using a dataset of 5004 commits and extracted 800 Java projects. Our main findings show that the random forest model trained with code metrics resulted in the best average accuracy of 75%. However, we detected a variation in the results per class, which means that some refactoring types are harder to detect than others.
Citation: Algorithms
PubDate: 2021-09-30
DOI: 10.3390/a14100289
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 290: Fine-Grained Pests Recognition Based on
Truncated Probability Fusion Network via Internet of Things in Forestry
and Agricultural Scenes
Authors: Kai Ma, Ming-Jun Nie, Sen Lin, Jianlei Kong, Cheng-Cai Yang, Jinhao Liu
First page: 290
Abstract: Accurate identification of insect pests is the key to improve crop yield and ensure quality and safety. However, under the influence of environmental conditions, the same kind of pests show obvious differences in intraclass representation, while the different kinds of pests show slight similarities. The traditional methods have been difficult to deal with fine-grained identification of pests, and their practical deployment is low. In order to solve this problem, this paper uses a variety of equipment terminals in the agricultural Internet of Things to obtain a large number of pest images and proposes a fine-grained identification model of pests based on probability fusion network FPNT. This model designs a fine-grained feature extractor based on an optimized CSPNet backbone network, mining different levels of local feature expression that can distinguish subtle differences. After the integration of the NetVLAD aggregation layer, the gated probability fusion layer gives full play to the advantages of information complementarity and confidence coupling of multi-model fusion. The comparison test shows that the PFNT model has an average recognition accuracy of 93.18% for all kinds of pests, and its performance is better than other deep-learning methods, with the average processing time drop to 61 ms, which can meet the needs of fine-grained image recognition of pests in the Internet of Things in agricultural and forestry practice, and provide technical application reference for intelligent early warning and prevention of pests.
Citation: Algorithms
PubDate: 2021-09-30
DOI: 10.3390/a14100290
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 291: An Algorithm for Making Regime-Changing
Markov Decisions
Authors: Juri Hinz
First page: 291
Abstract: In industrial applications, the processes of optimal sequential decision making are naturally formulated and optimized within a standard setting of Markov decision theory. In practice, however, decisions must be made under incomplete and uncertain information about parameters and transition probabilities. This situation occurs when a system may suffer a regime switch changing not only the transition probabilities but also the control costs. After such an event, the effect of the actions may turn to the opposite, meaning that all strategies must be revised. Due to practical importance of this problem, a variety of methods has been suggested, ranging from incorporating regime switches into Markov dynamics to numerous concepts addressing model uncertainty. In this work, we suggest a pragmatic and practical approach using a natural re-formulation of this problem as a so-called convex switching system, we make efficient numerical algorithms applicable.
Citation: Algorithms
PubDate: 2021-10-04
DOI: 10.3390/a14100291
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 292: Utilizing the Particle Swarm Optimization
Algorithm for Determining Control Parameters for Civil Structures Subject
to Seismic Excitation
Authors: Courtney A. Peckens, Andrea Alsgaard, Camille Fogg, Mary C. Ngoma, Clara Voskuil
First page: 292
Abstract: Structural control of civil infrastructure in response to large external loads, such as earthquakes or wind, is not widely employed due to challenges regarding information exchange and the inherent latencies in the system due to complex computations related to the control algorithm. This study employs front-end signal processing at the sensing node to alleviate computations at the control node and results in a simplistic sum of weighted inputs to determine a control force. The control law simplifies to U = WP, where U is the control force, W is a pre-determined weight matrix, and P is a deconstructed representation of the response of the structure to the applied excitation. Determining the optimal weight matrix for this calculation is non-trivial and this study uses the particle swarm optimization (PSO) algorithm with a modified homing feature to converge on a possible solution. To further streamline the control algorithm, various pruning techniques are combined with the PSO algorithm in order to optimize the number of entries in the weight matrix. These optimization techniques are applied in simulation to a five-story structure and the success of the resulting control parameters are quantified based on their ability to minimize the information exchange while maintaining control effectiveness. It is found that a magnitude-based pruning method, when paired with the PSO algorithm, is able to offer the most effective control for a structure subject to seismic base excitation.
Citation: Algorithms
PubDate: 2021-10-08
DOI: 10.3390/a14100292
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 293: A Unified Formulation of Analytical and
Numerical Methods for Solving Linear Fredholm Integral Equations
Authors: Efthimios Providas
First page: 293
Abstract: This article is concerned with the construction of approximate analytic solutions to linear Fredholm integral equations of the second kind with general continuous kernels. A unified treatment of some classes of analytical and numerical classical methods, such as the Direct Computational Method (DCM), the Degenerate Kernel Methods (DKM), the Quadrature Methods (QM) and the Projection Methods (PM), is proposed. The problem is formulated as an abstract equation in a Banach space and a solution formula is derived. Then, several approximating schemes are discussed. In all cases, the method yields an explicit, albeit approximate, solution. Several examples are solved to illustrate the performance of the technique.
Citation: Algorithms
PubDate: 2021-10-10
DOI: 10.3390/a14100293
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 294: Globally Optimizing QAOA Circuit Depth for
Constrained Optimization Problems
Authors: Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw, Travis S. Humble, George Siopsis
First page: 294
Abstract: We develop a global variable substitution method that reduces n-variable monomials in combinatorial optimization problems to equivalent instances with monomials in fewer variables. We apply this technique to 3-SAT and analyze the optimal quantum unitary circuit depth needed to solve the reduced problem using the quantum approximate optimization algorithm. For benchmark 3-SAT problems, we find that the upper bound of the unitary circuit depth is smaller when the problem is formulated as a product and uses the substitution method to decompose gates than when the problem is written in the linear formulation, which requires no decomposition.
Citation: Algorithms
PubDate: 2021-10-11
DOI: 10.3390/a14100294
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 295: Ant Colony Optimization with Warm-Up
Authors: Mattia Neroni
First page: 295
Abstract: The Ant Colony Optimization (ACO) is a probabilistic technique inspired by the behavior of ants for solving computational problems that may be reduced to finding the best path through a graph. Some species of ants deposit pheromone on the ground to mark some favorable paths that should be used by other members of the colony. Ant colony optimization implements a similar mechanism for solving optimization problems. In this paper a warm-up procedure for the ACO is proposed. During the warm-up, the pheromone matrix is initialized to provide an efficient new starting point for the algorithm, so that it can obtain the same (or better) results with fewer iterations. The warm-up is based exclusively on the graph, which, in most applications, is given and does not need to be recalculated every time before executing the algorithm. In this way, it can be made only once, and it speeds up the algorithm every time it is used from then on. The proposed solution is validated on a set of traveling salesman problem instances, and in the simulation of a real industrial application for the routing of pickers in a manual warehouse. During the validation, it is compared with other ACO adopting a pheromone initialization technique, and the results show that, in most cases, the adoption of the proposed warm-up allows the ACO to obtain the same or better results with fewer iterations.
Citation: Algorithms
PubDate: 2021-10-12
DOI: 10.3390/a14100295
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 296: Genz and Mendell-Elston Estimation of the
High-Dimensional Multivariate Normal Distribution
Authors: Lucy Blondell, Mark Z. Kos, John Blangero, Harald H. H. Göring
First page: 296
Abstract: Statistical analysis of multinomial data in complex datasets often requires estimation of the multivariate normal (mvn) distribution for models in which the dimensionality can easily reach 10–1000 and higher. Few algorithms for estimating the mvn distribution can offer robust and efficient performance over such a range of dimensions. We report a simulation-based comparison of two algorithms for the mvn that are widely used in statistical genetic applications. The venerable Mendell-Elston approximation is fast but execution time increases rapidly with the number of dimensions, estimates are generally biased, and an error bound is lacking. The correlation between variables significantly affects absolute error but not overall execution time. The Monte Carlo-based approach described by Genz returns unbiased and error-bounded estimates, but execution time is more sensitive to the correlation between variables. For ultra-high-dimensional problems, however, the Genz algorithm exhibits better scale characteristics and greater time-weighted efficiency of estimation.
Citation: Algorithms
PubDate: 2021-10-14
DOI: 10.3390/a14100296
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 297: Improving the Robustness of AI-Based
Malware Detection Using Adversarial Machine Learning
Authors: Shruti Patil, Vijayakumar Varadarajan, Devika Walimbe, Siddharth Gulechha, Sushant Shenoy, Aditya Raina, Ketan Kotecha
First page: 297
Abstract: Cyber security is used to protect and safeguard computers and various networks from ill-intended digital threats and attacks. It is getting more difficult in the information age due to the explosion of data and technology. There is a drastic rise in the new types of attacks where the conventional signature-based systems cannot keep up with these attacks. Machine learning seems to be a solution to solve many problems, including problems in cyber security. It is proven to be a very useful tool in the evolution of malware detection systems. However, the security of AI-based malware detection models is fragile. With advancements in machine learning, attackers have found a way to work around such detection systems using an adversarial attack technique. Such attacks are targeted at the data level, at classifier models, and during the testing phase. These attacks tend to cause the classifier to misclassify the given input, which can be very harmful in real-time AI-based malware detection. This paper proposes a framework for generating the adversarial malware images and retraining the classification models to improve malware detection robustness. Different classification models were implemented for malware detection, and attacks were established using adversarial images to analyze the model’s behavior. The robustness of the models was improved by means of adversarial training, and better attack resistance is observed.
Citation: Algorithms
PubDate: 2021-10-15
DOI: 10.3390/a14100297
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 298: SENSE: A Flow-Down Semantics-Based
Requirements Engineering Framework
Authors: Kalliopi Kravari, Christina Antoniou, Nick Bassiliades
First page: 298
Abstract: The processes involved in requirements engineering are some of the most, if not the most, important steps in systems development. The need for well-defined requirements remains a critical issue for the development of any system. Describing the structure and behavior of a system could be proven vague, leading to uncertainties, restrictions, or improper functioning of the system that would be hard to fix later. In this context, this article proposes SENSE, a framework based on standardized expressions of natural language with well-defined semantics, called boilerplates, that support a flow-down procedure for requirement management. This framework integrates sets of boilerplates and proposes the most appropriate of them, depending, among other considerations, on the type of requirement and the developing system, while providing validity and completeness verification checks using the minimum consistent set of formalities and languages. SENSE is a consistent and easily understood framework that allows engineers to use formal languages and semantics rather than the traditional natural languages and machine learning techniques, optimizing the requirement development. The main aim of SENSE is to provide a complete process of the production and standardization of the requirements by using semantics, ontologies, and appropriate NLP techniques. Furthermore, SENSE performs the necessary verifications by using SPARQL (SPIN) queries to support requirement management.
Citation: Algorithms
PubDate: 2021-10-15
DOI: 10.3390/a14100298
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 299: The Stock Index Prediction Based on SVR
Model with Bat Optimization Algorithm
Authors: Jianguo Zheng, Yilin Wang, Shihan Li, Hancong Chen
First page: 299
Abstract: Accurate stock market prediction models can provide investors with convenient tools to make better data-based decisions and judgments. Moreover, retail investors and institutional investors could reduce their investment risk by selecting the optimal stock index with the help of these models. Predicting stock index price is one of the most effective tools for risk management and portfolio diversification. The continuous improvement of the accuracy of stock index price forecasts can promote the improvement and maturity of China’s capital market supervision and investment. It is also an important guarantee for China to further accelerate structural reforms and manufacturing transformation and upgrading. In response to this problem, this paper introduces the bat algorithm to optimize the three free parameters of the SVR machine learning model, constructs the BA-SVR hybrid model, and forecasts the closing prices of 18 stock indexes in Chinese stock market. The total sample comes from 15 January 2016 (the 10th trading day in 2016) to 31 December 2020. We select the last 20, 60, and 250 days of whole sample data as test sets for short-term, mid-term, and long-term forecast, respectively. The empirical results show that the BA-SVR model outperforms the polynomial kernel SVR model and sigmoid kernel SVR model without optimized initial parameters. In the robustness test part, we use the stationary time series data after the first-order difference of six selected characteristics to re-predict. Compared with the random forest model and ANN model, the prediction performance of the BA-SVR model is still significant. This paper also provides a new perspective on the methods of stock index forecasting and the application of bat algorithms in the financial field.
Citation: Algorithms
PubDate: 2021-10-15
DOI: 10.3390/a14100299
Issue No: Vol. 14, No. 10 (2021)
- Algorithms, Vol. 14, Pages 300: Research on Building Target Detection
Based on High-Resolution Optical Remote Sensing Imagery
Authors: Yong Mei, Hao Chen, Shuting Yang
First page: 300
Abstract: High-resolution remote sensing image building target detection has wide application value in the fields of land planning, geographic monitoring, smart cities and other fields. However, due to the complex background of remote sensing imagery, some detailed features of building targets are less distinguishable from the background. When carrying out the detection task, it is prone to problems such as distortion and the missing of the building outline. To address this challenge, we developed a novel building target detection method. First, a building detection method based on rectangular approximation and region growth was proposed, and a saliency detection model based on the foreground compactness and local contrast of manifold ranking is used to obtain the saliency map of the building region. Then, the boundary prior saliency detection method based on the improved manifold ranking algorithm was proposed for the target area of buildings with low contrast with the background in remote sensing imagery. Finally, fusing the results of the rectangular approximation-based and saliency-based detection, the proposed fusion method improved the Recall and F1 value of building detection, indicating that this paper provides an effective and efficient high-resolution remote sensing image building target detection method.
Citation: Algorithms
PubDate: 2021-10-19
DOI: 10.3390/a14100300
Issue No: Vol. 14, No. 10 (2021)
