Algorithms doi: 10.3390/a14030083

Authors: Shijin Yuan Cheng Wang Bin Mu Feifan Zhou Wansuo Duan

A typhoon is an extreme weather event with strong destructive force, which can bring huge losses of life and economic damage to people. Thus, it is meaningful to reduce the prediction errors of typhoon intensity forecasting. Artificial and deep neural networks have recently become widely used for typhoon forecasting in order to ensure typhoon intensity forecasting is accurate and timely. Typhoon intensity forecasting models based on long short-term memory (LSTM) are proposed herein, which forecast typhoon intensity as a time series problem based on historical typhoon data. First, the typhoon intensity forecasting models are trained and tested with processed typhoon data from 2000 to 2014 to find the optimal prediction factors. Then, the models are validated using the optimal prediction factors compared to a feed-forward neural network (FNN). As per the results of the model applied for typhoons Chan-hom and Soudelor in 2015, the model based on LSTM using the optimal prediction factors shows the best performance and lowest prediction errors. Thus, the model based on LSTM is practical and meaningful for predicting typhoon intensity within 120 h.

]]>Algorithms doi: 10.3390/a14030082

Authors: Xu Li Qiming Sun

Identifying and ranking the node influence in complex networks is an important issue. It helps to understand the dynamics of spreading process for designing efficient strategies to hinder or accelerate information spreading. The idea of decomposing network to rank node influence is adopted widely because of low computational complexity. Of this type, decomposition is a dynamic process, and each iteration could be regarded as an inverse process of spreading. In this paper, we propose a new ranking method, Dynamic Node Strength Decomposition, based on decomposing network. The spreading paths are distinguished by weighting the edges according to the nodes at both ends. The change of local structure in the process of decomposition is considered. Our experimental results on four real networks with different sizes show that the proposed method can generate a more monotonic ranking list and identify node influence more effectively.

]]>Algorithms doi: 10.3390/a14030081

Authors: Johannes Fichte Markus Hecher Michael Morak Stefan Woltran

Efficient exact parameterized algorithms are an active research area. Such algorithms exhibit a broad interest in the theoretical community. In the last few years, implementations for computing various parameters (parameter detection) have been established in parameterized challenges, such as treewidth, treedepth, hypertree width, feedback vertex set, or vertex cover. In theory, instances, for which the considered parameter is small, can be solved fast (problem evaluation), i.e., the runtime is bounded exponential in the parameter. While such favorable theoretical guarantees exists, it is often unclear whether one can successfully implement these algorithms under practical considerations. In other words, can we design and construct implementations of parameterized algorithms such that they perform similar or even better than well-established problem solvers on instances where the parameter is small. Indeed, we can build an implementation that performs well under the theoretical assumptions. However, it could also well be that an existing solver implicitly takes advantage of a structure, which is often claimed for solvers that build on Sat-solving. In this paper, we consider finding one solution to instances of answer set programming (ASP), which is a logic-based declarative modeling and solving framework. Solutions for ASP instances are so-called answer sets. Interestingly, the problem of deciding whether an instance has an answer set is already located on the second level of the polynomial hierarchy. An ASP solver that employs treewidth as parameter and runs dynamic programming on tree decompositions is DynASP2. Empirical experiments show that this solver is fast on instances of small treewidth and can outperform modern ASP when one counts answer sets. It remains open, whether one can improve the solver such that it also finds one answer set fast and shows competitive behavior to modern ASP solvers on instances of low treewidth. Unfortunately, theoretical models of modern ASP solvers already indicate that these solvers can solve instances of low treewidth fast, since they are based on Sat-solving algorithms. In this paper, we improve DynASP2 and construct the solver DynASP2.5, which uses a different approach. The new solver shows competitive behavior to state-of-the-art ASP solvers even for finding just one solution. We present empirical experiments where one can see that our new implementation solves ASP instances, which encode the Steiner tree problem on graphs with low treewidth, fast. Our implementation is based on a novel approach that we call multi-pass dynamic programming (MDPSINC). In the paper, we describe the underlying concepts of our implementation (DynASP2.5) and we argue why the techniques still yield correct algorithms.

]]>Algorithms doi: 10.3390/a14030080

Authors: Qiuqi Han Guangyuan Zheng Chen Xu

Device-to-Device (D2D) communications, which enable direct communication between nearby user devices over the licensed spectrum, have been considered a key technique to improve spectral efficiency and system throughput in cellular networks (CNs). However, the limited spectrum resources cannot be sufficient to support more cellular users (CUs) and D2D users to meet the growth of the traffic data in future wireless networks. Therefore, Long-Term Evolution-Unlicensed (LTE-U) and D2D-Unlicensed (D2D-U) technologies have been proposed to further enhance system capacity by extending the CUs and D2D users on the unlicensed spectrum for communications. In this paper, we consider an LTE network where the CUs and D2D users are allowed to share the unlicensed spectrum with Wi-Fi users. To maximize the sum rate of all users while guaranteeing each user’s quality of service (QoS), we jointly consider user access and resource allocation. To tackle the formulated problem, we propose a matching-iteration-based joint user access and resource allocation algorithm. Simulation results show that the proposed algorithm can significantly improve system throughput compared to the other benchmark algorithms.

]]>Algorithms doi: 10.3390/a14030079

Authors: Salim Bouamama Christian Blum

This paper presents a performance comparison of greedy heuristics for a recent variant of the dominating set problem known as the minimum positive influence dominating set (MPIDS) problem. This APX-hard combinatorial optimization problem has applications in social networks. Its aim is to identify a small subset of key influential individuals in order to facilitate the spread of positive influence in the whole network. In this paper, we focus on the development of a fast and effective greedy heuristic for the MPIDS problem, because greedy heuristics are an essential component of more sophisticated metaheuristics. Thus, the development of well-working greedy heuristics supports the development of efficient metaheuristics. Extensive experiments conducted on a wide range of social networks and complex networks confirm the overall superiority of our greedy algorithm over its competitors, especially when the problem size becomes large. Moreover, we compare our algorithm with the integer linear programming solver CPLEX. While the performance of CPLEX is very strong for small and medium-sized networks, it reaches its limits when being applied to the largest networks. However, even in the context of small and medium-sized networks, our greedy algorithm is only 2.53% worse than CPLEX.

]]>Algorithms doi: 10.3390/a14030078

Authors: Ryan Dieter Lang Andries Petrus Engelbrecht

The choice of which objective functions, or benchmark problems, should be used to test an optimization algorithm is a crucial part of the algorithm selection framework. Benchmark suites that are often used in the literature have been shown to exhibit poor coverage of the problem space. Exploratory landscape analysis can be used to quantify characteristics of objective functions. However, exploratory landscape analysis measures are based on samples of the objective function, and there is a lack of work on the appropriate choice of sample size needed to produce reliable measures. This study presents an approach to determine the minimum sample size needed to obtain robust exploratory landscape analysis measures. Based on reliable exploratory landscape analysis measures, a self-organizing feature map is used to cluster a comprehensive set of benchmark functions. From this, a benchmark suite that has better coverage of the single-objective, boundary-constrained problem space is proposed.

]]>Algorithms doi: 10.3390/a14030077

Authors: Afra A. Alabbadi Maysoon F. Abulkhair

Recently, with the development of mobile devices and the crowdsourcing platform, spatial crowdsourcing (SC) has become more widespread. In SC, workers need to physically travel to complete spatial–temporal tasks during a certain period of time. The main problem in SC platforms is scheduling a set of proper workers to achieve a set of spatial tasks based on different objectives. In actuality, real-world applications of SC need to optimize multiple objectives together, and these objectives may sometimes conflict with one another. Furthermore, there is a lack of research dealing with the multi-objective optimization (MOO) problem within an SC environment. Thus, in this work we focused on task scheduling based on multi-objective optimization (TS-MOO) in SC, which is based on maximizing the number of completed tasks, minimizing the total travel costs, and ensuring the balance of the workload between workers. To solve the previous problem, we developed a new method, i.e., the multi-objective task scheduling optimization (MOTSO) model that consists of two algorithms, namely, the multi-objective particle swarm optimization (MOPSO) algorithm with our fitness function Alabbadi, et al. and the ranking strategy algorithm based on the task entropy concept and task execution duration. The main purpose of our ranking strategy is to improve and enhance the performance of our MOPSO. The primary goal of the proposed MOTSO model is to find an optimal solution based on the multiple objectives that conflict with one another. We conducted our experiment with both synthetic and real datasets; the experimental results and statistical analysis showed that our proposed model is effective in terms of maximizing the number of completed tasks, minimizing the total travel costs, and balancing the workload between workers.

]]>Algorithms doi: 10.3390/a14030075

Authors: Usman Mahmood Zening Fu Vince D. Calhoun Sergey Plis

Functional connectivity (FC) studies have demonstrated the overarching value of studying the brain and its disorders through the undirected weighted graph of functional magnetic resonance imaging (fMRI) correlation matrix. However, most of the work with the FC depends on the way the connectivity is computed, and it further depends on the manual post-hoc analysis of the FC matrices. In this work, we propose a deep learning architecture BrainGNN that learns the connectivity structure as part of learning to classify subjects. It simultaneously applies a graphical neural network to this learned graph and learns to select a sparse subset of brain regions important to the prediction task. We demonstrate that the model’s state-of-the-art classification performance on a schizophrenia fMRI dataset and demonstrate how introspection leads to disorder relevant findings. The graphs that are learned by the model exhibit strong class discrimination and the sparse subset of relevant regions are consistent with the schizophrenia literature.

]]>Algorithms doi: 10.3390/a14030076

Authors: Estrella Lucena-Sánchez Guido Sciavicco Ionel Eduard Stan

Air quality modelling that relates meteorological, car traffic, and pollution data is a fundamental problem, approached in several different ways in the recent literature. In particular, a set of such data sampled at a specific location and during a specific period of time can be seen as a multivariate time series, and modelling the values of the pollutant concentrations can be seen as a multivariate temporal regression problem. In this paper, we propose a new method for symbolic multivariate temporal regression, and we apply it to several data sets that contain real air quality data from the city of Wrocław (Poland). Our experiments show that our approach is superior to classical, especially symbolic, ones, both in statistical performances and the interpretability of the results.

]]>Algorithms doi: 10.3390/a14030074

Authors: Fabrice Saffre Hanno Hildmann

Genetic algorithms (GA’s) are mostly used as an offline optimisation method to discover a suitable solution to a complex problem prior to implementation. In this paper, we present a different application in which a GA is used to progressively adapt the collective performance of an ad hoc collection of devices that are being integrated post-deployment. Adaptive behaviour in the context of this article refers to two dynamic aspects of the problem: (a) the availability of individual devices as well as the objective functions for the performance of the entire population. We illustrate this concept in a video surveillance scenario in which already installed cameras are being retrofitted with networking capabilities to form a coherent closed-circuit television (CCTV) system. We show that this can be conceived as a multi-objective optimisation problem which can be solved at run-time, with the added benefit that solutions can be refined or modified in response to changing priorities or even unpredictable events such as faults. We present results of a detailed simulation study, the implications of which are being discussed from both a theoretical and practical viewpoint (trade-off between saving computational resources and surveillance coverage).

]]>Algorithms doi: 10.3390/a14030073

Authors: Dimitris Fotakis Loukas Kavouras Lydia Zakynthinou

The Dynamic Facility Location problem is a generalization of the classic Facility Location problem, in which the distance metric between clients and facilities changes over time. Such metrics that develop as a function of time are usually called “evolving metrics”, thus Dynamic Facility Location can be alternatively interpreted as a Facility Location problem in evolving metrics. The objective in this time-dependent variant is to balance the trade-off between optimizing the classic objective function and the stability of the solution, which is modeled by charging a switching cost when a client’s assignment changes from one facility to another. In this paper, we study the online variant of Dynamic Facility Location. We present a randomized O(logm+logn)-competitive algorithm, where m is the number of facilities and n is the number of clients. In the first step, our algorithm produces a fractional solution, in each timestep, to the objective of Dynamic Facility Location involving a regularization function. This step is an adaptation of the generic algorithm proposed by Buchbinder et al. in their work “Competitive Analysis via Regularization.” Then, our algorithm rounds the fractional solution of this timestep to an integral one with the use of exponential clocks. We complement our result by proving a lower bound of Ω(m) for deterministic algorithms and lower bound of Ω(logm) for randomized algorithms. To the best of our knowledge, these are the first results for the online variant of the Dynamic Facility Location problem.

]]>Algorithms doi: 10.3390/a14030072

Authors: Luca Tonti Alessandro Patti

Collision between rigid three-dimensional objects is a very common modelling problem in a wide spectrum of scientific disciplines, including Computer Science and Physics. It spans from realistic animation of polyhedral shapes for computer vision to the description of thermodynamic and dynamic properties in simple and complex fluids. For instance, colloidal particles of especially exotic shapes are commonly modelled as hard-core objects, whose collision test is key to correctly determine their phase and aggregation behaviour. In this work, we propose the Oriented Cuboid Sphere Intersection (OCSI) algorithm to detect collisions between prolate or oblate cuboids and spheres. We investigate OCSI’s performance by bench-marking it against a number of algorithms commonly employed in computer graphics and colloidal science: Quick Rejection First (QRI), Quick Rejection Intertwined (QRF) and a vectorized version of the OBB-sphere collision detection algorithm that explicitly uses SIMD Streaming Extension (SSE) intrinsics, here referred to as SSE-intr. We observed that QRI and QRF significantly depend on the specific cuboid anisotropy and sphere radius, while SSE-intr and OCSI maintain their speed independently of the objects’ geometry. While OCSI and SSE-intr, both based on SIMD parallelization, show excellent and very similar performance, the former provides a more accessible coding and user-friendly implementation as it exploits OpenMP directives for automatic vectorization.

]]>Algorithms doi: 10.3390/a14030071

Authors: Vladimir Gurvich Mikhail Vyalyi

We study the algorithmic complexity of solving subtraction games in a fixed dimension with a finite difference set. We prove that there exists a game in this class such that solving the game is EXP-complete and requires time 2Ω(n), where n is the input size. This bound is optimal up to a polynomial speed-up. The results are based on a construction introduced by Larsson and Wästlund. It relates subtraction games and cellular automata.

]]>Algorithms doi: 10.3390/a14030070

Authors: Fumitaka Ito Masahiko Naito Naoyuki Katabami Tatsuie Tsukiji

Custodian capture occurs when a player has placed two of his pieces on the opposite sides of an orthogonal line of the opponent’s men. Each piece moves like the rook in Chess. Different cultures played it from pre-modern times in two-player strategy board games, Ludus Latrunculorum (Kowalski’s reconstruction), Hasami shogi in Japan, Mak-yek in Thailand and Myanmar, Ming Mang in Tibet, and so on. We prove that a custodian capture game on n×n square board is EXPTIME hard if the first player to capture five or more men in total wins.

]]>Algorithms doi: 10.3390/a14030069

Authors: Guoliang Feng Wei Lu Jianhua Yang

A novel design method for time series modeling and prediction with fuzzy cognitive maps (FCM) is proposed in this paper. The developed model exploits the least square method to learn the weight matrix of FCM derived from the given historical data of time series. A fuzzy c-means clustering algorithm is used to construct the concepts of the FCM. Compared with the traditional FCM, the least square fuzzy cognitive map (LSFCM) is a direct solution procedure without iterative calculations. LSFCM model is a straightforward, robust and rapid learning method, owing to its reliable and efficient. In addition, the structure of the LSFCM can be further optimized with refinements the position of the concepts for the higher prediction precision, in which the evolutionary optimization algorithm is used to find the optimal concepts. Withal, we discussed in detail the number of concepts and the parameters of activation function on the impact of FCM models. The publicly available time series data sets with different statistical characteristics coming from different areas are applied to evaluate the proposed modeling approach. The obtained results clearly show the effectiveness of the approach.

]]>Algorithms doi: 10.3390/a14030068

Authors: Joachim Niehren Momar Sakho

We consider the problem of determinizing and minimizing automata for nested words in practice. For this we compile the nested regular expressions (NREs) from the usual XPath benchmark to nested word automata (NWAs). The determinization of these NWAs, however, fails to produce reasonably small automata. In the best case, huge deterministic NWAs are produced after few hours, even for relatively small NREs of the benchmark. We propose a different approach to the determinization of automata for nested words. For this, we introduce stepwise hedge automata (SHAs) that generalize naturally on both (stepwise) tree automata and on finite word automata. We then show how to determinize SHAs, yielding reasonably small deterministic automata for the NREs from the XPath benchmark. The size of deterministic SHAs automata can be reduced further by a novel minimization algorithm for a subclass of SHAs. In order to understand why the new approach to determinization and minimization works so nicely, we investigate the relationship between NWAs and SHAs further. Clearly, deterministic SHAs can be compiled to deterministic NWAs in linear time, and conversely NWAs can be compiled to nondeterministic SHAs in polynomial time. Therefore, we can use SHAs as intermediates for determinizing NWAs, while avoiding the huge size increase with the usual determinization algorithm for NWAs. Notably, the NWAs obtained from the SHAs perform bottom-up and left-to-right computations only, but no top-down computations. This NWA behavior can be distinguished syntactically by the (weak) single-entry property, suggesting a close relationship between SHAs and single-entry NWAs. In particular, it turns out that the usual determinization algorithm for NWAs behaves well for single-entry NWAs, while it quickly explodes without the single-entry property. Furthermore, it is known that the class of deterministic multi-module single-entry NWAs enjoys unique minimization. The subclass of deterministic SHAs to which our novel minimization algorithm applies is different though, in that we do not impose multiple modules. As further optimizations for reducing the sizes of the constructed SHAs, we propose schema-based cleaning and symbolic representations based on apply-else rules that can be maintained by determinization. We implemented the optimizations and report the experimental results for the automata constructed for the XPathMark benchmark.

]]>Algorithms doi: 10.3390/a14020067

Authors: Jin Nakabe Teruhiro Mizumoto Hirohiko Suwa Keiichi Yasumoto

As the number of users who cook their own food increases, there is increasing demand for an optimal cooking procedure for multiple dishes, but the optimal cooking procedure varies from user to user due to the difference of each user’s cooking skill and environment. In this paper, we propose a system of presenting optimal cooking procedures that enables parallel cooking of multiple recipes. We formulate the problem of deciding optimal cooking procedures as a task scheduling problem by creating a task graph for each recipe. To reduce execution time, we propose two extensions to the preprocessing and bounding operation of PDF/IHS, a sequential optimization algorithm for the task scheduling problem, each taking into account the cooking characteristics. We confirmed that the proposed algorithm can reduce execution time by up to 44% compared to the base PDF/IHS, and increase execution time by about 900 times even when the number of required searches increases by 10,000 times. In addition, through the experiment with three recipes for 10 participants each, it was confirmed that by following the optimal cooking procedure for a certain menu, the actual cooking time was reduced by up to 13 min (14.8% of the time when users cooked freely) compared to the time when users cooked freely.

]]>Algorithms doi: 10.3390/a14020066

Authors: Camille Champion Anne-Claire Brunet Rémy Burcelin Jean-Michel Loubes Laurent Risser

In this paper, we present a new framework dedicated to the robust detection of representative variables in high dimensional spaces with a potentially limited number of observations. Representative variables are selected by using an original regularization strategy: they are the center of specific variable clusters, denoted CORE-clusters, which respect fully interpretable constraints. Each CORE-cluster indeed contains more than a predefined amount of variables and each pair of its variables has a coherent behavior in the observed data. The key advantage of our regularization strategy is therefore that it only requires to tune two intuitive parameters: the minimal dimension of the CORE-clusters and the minimum level of similarity which gathers their variables. Interpreting the role played by a selected representative variable is additionally obvious as it has a similar observed behaviour as a controlled number of other variables. After introducing and justifying this variable selection formalism, we propose two algorithmic strategies to detect the CORE-clusters, one of them scaling particularly well to high-dimensional data. Results obtained on synthetic as well as real data are finally presented.

]]>Algorithms doi: 10.3390/a14020065

Authors: Danny Hucke Carl Philipp Reh

A grammar-based compressor is an algorithm that receives a word and outputs a context-free grammar that only produces this word. The approximation ratio for a single input word is the size of the grammar produced for this word divided by the size of a smallest grammar for this word. The worst-case approximation ratio of a grammar-based compressor for a given word length is the largest approximation ratio over all input words of that length. In this work, we study the worst-case approximation ratio of the algorithms Greedy, RePair and LongestMatch on unary strings, i.e., strings that only make use of a single symbol. Our main contribution is to show the improved upper bound of O((logn)8·(loglogn)3) for the worst-case approximation ratio of Greedy. In addition, we also show the lower bound of 1.34847194⋯ for the worst-case approximation ratio of Greedy, and that RePair and LongestMatch have a worst-case approximation ratio of log2(3).

]]>Algorithms doi: 10.3390/a14020064

Authors: Roman Vavrek Jiří Bečica Viera Papcunová Petra Gundová Jana Mitríková

Multi-criteria analysis is a decision-making and efficiency assessment tool for application in both the private and public sectors. Its application is preceded by the selection of suitable indicators and a homogenous set of variants, as well as suitable methods based on the nature of the input data. The goal of the submitted research is to highlight the importance of selecting suitable indicators using a case study assessment of the financial health of a municipality—more precisely, the efficiency of management of this municipality. Four key indicators, thirty-two homogenous subjects, and one multi-criteria analysis method were identified in this study based on the theoretical foundations of the specific issue. These elements were processed into a total of 14 variants depending on the number of assessed indicators. Then, these results were subjected to statistical verification alongside verification using the Jaccard index. Based on the acquired results, we highlight the need for correct and expert identification of the relevant sets of alternatives (the criteria matrix) and expert discussion, which should precede the selection of the assessed indicators and objectify this selection process as much as possible. Assessment based on a low number of indicators was shown to be insufficient, highly variable, and diverse, and these differences were partially eliminated as the number of assessed indicators increased.

]]>Algorithms doi: 10.3390/a14020063

Authors: Ronald D. Hagan Michael A. Langston

Recent discoveries of distinct molecular subtypes have led to remarkable advances in treatment for a variety of diseases. While subtyping via unsupervised clustering has received a great deal of interest, most methods rely on basic statistical or machine learning methods. At the same time, techniques based on graph clustering, particularly clique-based strategies, have been successfully used to identify disease biomarkers and gene networks. A graph theoretical approach based on the paraclique algorithm is described that can easily be employed to identify putative disease subtypes and serve as an aid in outlier detection as well. The feasibility and potential effectiveness of this method is demonstrated on publicly available gene co-expression data derived from patient samples covering twelve different disease families.

]]>Algorithms doi: 10.3390/a14020062

Authors: Subhash Bhagat Bibhuti Das Abhinav Chakraborty Krishnendu Mukhopadhyaya

For a given positive integer k, the k-circle formation problem asks a set of autonomous, asynchronous robots to form disjoint circles having k robots each at distinct locations, centered at a set of fixed points in the Euclidean plane. The robots are identical, anonymous, oblivious, and they operate in Look–Compute–Move cycles. This paper studies the k-circle formation problem and its relationship with the k-epf problem, a generalized version of the embedded pattern formation problem, which asks exactly k robots to reach and remain at each fixed point. First, the k-circle formation problem is studied in a setting where the robots have an agreement on the common direction and orientation of one of the axes. We have characterized all the configurations and the values of k, for which the k-circle formation problem is deterministically unsolvable in this setting. For the remaining configurations and the values of k, a deterministic distributed algorithm has been proposed, in order to solve the problem. It has been proved that for the initial configurations with distinct robot positions, if the k-circle formation problem is deterministically solvable then the k-epf problem is also deterministically solvable. It has been shown that by modifying the proposed algorithm, the k-epf problem can be solved deterministically.

]]>Algorithms doi: 10.3390/a14020061

Authors: Kuan Liu Haiyuan Liu Dongyan Sun Lei Zhang

The reconstruction of gene regulatory networks based on gene expression data can effectively uncover regulatory relationships between genes and provide a deeper understanding of biological control processes. Non-linear dependence is a common problem in the regulatory mechanisms of gene regulatory networks. Various methods based on information theory have been developed to infer networks. However, the methods have introduced many redundant regulatory relationships in the network inference process. A recent measurement method called distance correlation has, in many cases, shown strong and computationally efficient non-linear correlations. In this paper, we propose a novel regulatory network inference method called the distance-correlation and network topology centrality network (DCNTC) method. The method is based on and extends the Local Density Measurement of Network Node Centrality (LDCNET) algorithm, which has the same choice of network centrality ranking as the LDCNET algorithm, but uses a simpler and more efficient distance correlation measure of association between genes. In this work, we integrate distance correlation and network topological centrality into the reasoning about the structure of gene regulatory networks. We will select optimal thresholds based on the characteristics of the distribution of each gene pair in relation to distance correlation. Experiments were carried out on four network datasets and their performance was compared.

]]>Algorithms doi: 10.3390/a14020060

Authors: Shunichi Ohmori Kazuho Yoshimoto

We consider the facility layout problem (FLP) in which we find the arrangements of departments with the smallest material handling cost that can be expressed as the product of distance times flows between departments. It is known that FLP can be formulated as a linear programming problem if the relative positioning of departments is specified, and, thus, can be solved to optimality. In this paper, we describe a custom interior-point algorithm for solving FLP with relative positioning constraints (FLPRC) that is much faster than the standard methods used in the general-purpose solver. We build a compact formation of FLPRC and its duals, which enables us to establish the optimal condition very quickly. We use this optimality condition to implement the primal-dual interior-point method with an efficient Newton step computation that exploit special structure of a Hessian. We confirm effectiveness of our proposed model through applications to several well-known benchmark data sets. Our algorithm shows much faster speed for finding the optimal solution.

]]>Algorithms doi: 10.3390/a14020059

Authors: Roman Zoun Kay Schallert David Broneske Ivayla Trifonova Xiao Chen Robert Heyer Dirk Benndorf Gunter Saake

Mass spectrometers enable identifying proteins in biological samples leading to biomarkers for biological process parameters and diseases. However, bioinformatic evaluation of the mass spectrometer data needs a standardized workflow and system that stores the protein sequences. Due to its standardization and maturity, relational systems are a great fit for storing protein sequences. Hence, in this work, we present a schema for distributed column-based database management systems using a column-oriented index to store sequence data. In order to achieve a high storage performance, it was necessary to choose a well-performing strategy for transforming the protein sequence data from the FASTA format to the new schema. Therefore, we applied an in-memory map, HDDmap, database engine, and extended radix tree and evaluated their performance. The results show that our proposed extended radix tree performs best regarding memory consumption and runtime. Hence, the radix tree is a suitable data structure for transforming protein sequences into the indexed schema.

]]>Algorithms doi: 10.3390/a14020058

Authors: Alessio Ferone Antonio Maratea

Data streams are ubiquitous and related to the proliferation of low-cost mobile devices, sensors, wireless networks and the Internet of Things. While it is well known that complex phenomena are not stationary and exhibit a concept drift when observed for a sufficiently long time, relatively few studies have addressed the related problem of feature drift. In this paper, a variation of the QuickReduct algorithm suitable to process data streams is proposed and tested: it builds an evolving reduct that dynamically selects the relevant features in the stream, removing the redundant ones and adding the newly relevant ones as soon as they become such. Tests on five publicly available datasets with an artificially injected drift have confirmed the effectiveness of the proposed method.

]]>Algorithms doi: 10.3390/a14020057

Authors: Ryan Feng Yu Yao Ella Atkins

Autonomous vehicles require fleet-wide data collection for continuous algorithm development and validation. The smart black box (SBB) intelligent event data recorder has been proposed as a system for prioritized high-bandwidth data capture. This paper extends the SBB by applying anomaly detection and action detection methods for generalized event-of-interest (EOI) detection. An updated SBB pipeline is proposed for the real-time capture of driving video data. A video dataset is constructed to evaluate the SBB on real-world data for the first time. SBB performance is assessed by comparing the compression of normal and anomalous data and by comparing our prioritized data recording with an FIFO strategy. The results show that SBB data compression can increase the anomalous-to-normal memory ratio by ∼25%, while the prioritized recording strategy increases the anomalous-to-normal count ratio when compared to an FIFO strategy. We compare the real-world dataset SBB results to a baseline SBB given ground-truth anomaly labels and conclude that improved general EOI detection methods will greatly improve SBB performance.

]]>Algorithms doi: 10.3390/a14020056

Authors: Gokarna Sharma Ramachandran Vaidyanathan Jerry L. Trahan

We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and use colored lights (the robots with lights model). We assume obstructed visibility where a robot cannot see another robot if a third robot is positioned between them on the straight line segment connecting them. In this paper, we consider the problem of positioning N autonomous robots on a plane so that every robot is visible to all others (this is called the Complete Visibility problem). This problem is fundamental, as it provides a basis to solve many other problems under obstructed visibility. In this paper, we provide the first, asymptotically optimal, O(1) time, O(1) color algorithm for Complete Visibility in the asynchronous setting. This significantly improves on an O(N)-time translation of the existing O(1) time, O(1) color semi-synchronous algorithm to the asynchronous setting. The proposed algorithm is collision-free, i.e., robots do not share positions, and their paths do not cross. We also introduce a new technique for moving robots in an asynchronous setting that may be of independent interest, called Beacon-Directed Curve Positioning.

]]>Algorithms doi: 10.3390/a14020055

Authors: Enrico Bianchi Paolo Penna

This work studies clustering algorithms which operates with ordinal or comparison-based queries (operations), a situation that arises in many active-learning applications where “dissimilarities” between data points are evaluated by humans. Typically, exact answers are costly (or difficult to obtain in large amounts) while possibly erroneous answers have low cost. Motivated by these considerations, we study algorithms with non-trivial trade-offs between the number of exact (high-cost) operations and noisy (low-cost) operations with provable performance guarantees. Specifically, we study a class of polynomial-time graph-based clustering algorithms (termed Single-Linkage) which are widely used in practice and that guarantee exact solutions for stable instances in several clustering problems (these problems are NP-hard in the worst case). We provide several variants of these algorithms using ordinal operations and, in particular, non-trivial trade-offs between the number of high-cost and low-cost operations that are used. Our algorithms still guarantee exact solutions for stable instances of k-medoids clustering, and they use a rather small number of high-cost operations, without increasing the low-cost operations too much.

]]>Algorithms doi: 10.3390/a14020054

Authors: Chen Fu Jianhua Yang

The problem of classification for imbalanced datasets is frequently encountered in practical applications. The data to be classified in this problem are skewed, i.e., the samples of one class (the minority class) are much less than those of other classes (the majority class). When dealing with imbalanced datasets, most classifiers encounter a common limitation, that is, they often obtain better classification performances on the majority classes than those on the minority class. To alleviate the limitation, in this study, a fuzzy rule-based modeling approach using information granules is proposed. Information granules, as some entities derived and abstracted from data, can be used to describe and capture the characteristics (distribution and structure) of data from both majority and minority classes. Since the geometric characteristics of information granules depend on the distance measures used in the granulation process, the main idea of this study is to construct information granules on each class of imbalanced data using Minkowski distance measures and then to establish the classification models by using “If-Then” rules. The experimental results involving synthetic and publicly available datasets reflect that the proposed Minkowski distance-based method can produce information granules with a series of geometric shapes and construct granular models with satisfying classification performance for imbalanced datasets.

]]>Algorithms doi: 10.3390/a14020053

Authors: Qibing Jin Nan Lin Yuming Zhang

K-Means Clustering is a popular technique in data analysis and data mining. To remedy the defects of relying on the initialization and converging towards the local minimum in the K-Means Clustering (KMC) algorithm, a chaotic adaptive artificial bee colony algorithm (CAABC) clustering algorithm is presented to optimally partition objects into K clusters in this study. This algorithm adopts the max–min distance product method for initialization. In addition, a new fitness function is adapted to the KMC algorithm. This paper also reports that the iteration abides by the adaptive search strategy, and Fuch chaotic disturbance is added to avoid converging on local optimum. The step length decreases linearly during the iteration. In order to overcome the shortcomings of the classic ABC algorithm, the simulated annealing criterion is introduced to the CAABC. Finally, the confluent algorithm is compared with other stochastic heuristic algorithms on the 20 standard test functions and 11 datasets. The results demonstrate that improvements in CAABA-K-means have an advantage on speed and accuracy of convergence over some conventional algorithms for solving clustering problems.

]]>Algorithms doi: 10.3390/a14020052

Authors: Zhichao Sun Kang Zhou Xinzheng Yang Xiao Peng Rui Song

Transit network optimization can effectively improve transit efficiency, improve traffic conditions, and reduce the pollution of the environment. In order to better meet the travel demands of passengers, the factors influencing passengers’ satisfaction with a customized bus are fully analyzed. Taking the minimum operating cost of the enterprise as the objective and considering the random travel time constraints of passengers, the customized bus routes are optimized. The K-means clustering analysis is used to classify the passengers’ needs based on the analysis of the passenger travel demand of the customized shuttle bus, and the time stochastic uncertainty under the operating environment of the customized shuttle bus line is fully considered. On the basis of meeting the passenger travel time requirements and minimizing the cost of service operation, an optimization model that maximizes the overall satisfaction of passengers and public transit enterprises is structured. The smaller the value of the objective function is, the lower the operating cost. When the value is negative, it means there is profit. The model is processed by the deterministic processing method of random constraints, and then the hybrid intelligent algorithm is used to solve the model. A stochastic simulation technique is used to train stochastic constraints to approximate uncertain functions. Then, the improved immune clonal algorithm is used to solve the vehicle routing problem. Finally, it is proved by a case that the method can reasonably and efficiently realize the optimization of the customized shuttle bus lines in the region.

]]>Algorithms doi: 10.3390/a14020051

Authors: Nalinda Kulathunga Nishath Rajiv Ranasinghe Daniel Vrinceanu Zackary Kinsman Lei Huang Yunjiao Wang

The nonlinearity of activation functions used in deep learning models is crucial for the success of predictive models. Several simple nonlinear functions, including Rectified Linear Unit (ReLU) and Leaky-ReLU (L-ReLU) are commonly used in neural networks to impose the nonlinearity. In practice, these functions remarkably enhance the model accuracy. However, there is limited insight into the effects of nonlinearity in neural networks on their performance. Here, we investigate the performance of neural network models as a function of nonlinearity using ReLU and L-ReLU activation functions in the context of different model architectures and data domains. We use entropy as a measurement of the randomness, to quantify the effects of nonlinearity in different architecture shapes on the performance of neural networks. We show that the ReLU nonliearity is a better choice for activation function mostly when the network has sufficient number of parameters. However, we found that the image classification models with transfer learning seem to perform well with L-ReLU in fully connected layers. We show that the entropy of hidden layer outputs in neural networks can fairly represent the fluctuations in information loss as a function of nonlinearity. Furthermore, we investigate the entropy profile of shallow neural networks as a way of representing their hidden layer dynamics.

]]>Algorithms doi: 10.3390/a14020049

Authors: Alessia Sarica Maria Grazia Vaccaro Andrea Quattrone Aldo Quattrone

Cluster analysis is widely applied in the neuropsychological field for exploring patterns in cognitive profiles, but traditional hierarchical and non-hierarchical approaches could be often poorly effective or even inapplicable on certain type of data. Moreover, these traditional approaches need the initial specification of the number of clusters, based on a priori knowledge not always owned. For this reason, we proposed a novel method for cognitive clustering through the affinity propagation (AP) algorithm. In particular, we applied the AP clustering on the regression residuals of the Mini Mental State Examination scores—a commonly used screening tool for cognitive impairment—of a cohort of 49 Parkinson’s disease, 48 Progressive Supranuclear Palsy and 44 healthy control participants. We found four clusters, where two clusters (68 and 30 participants) showed almost intact cognitive performance, one cluster had a moderate cognitive impairment (34 participants), and the last cluster had a more extensive cognitive deficit (8 participants). The findings showed, for the first time, an intra- and inter-diagnostic heterogeneity in the cognitive profile of Parkinsonisms patients. Our novel method of unsupervised learning could represent a reliable tool for supporting the neuropsychologists in understanding the natural structure of the cognitive performance in the neurodegenerative diseases.

]]>Algorithms doi: 10.3390/a14020050

Authors: Li Wang Xi Wang Xilong Cai

The sharing mode of the logistics industry can effectively solve the new problems arising from the rapid development of the express industry. However, only when the interests are reasonably distributed can the sharing mode be implemented for a long time. This paper discusses the connotation of unified warehouse and distribution, designs the operation mode of a unified warehouse and distribution, and solves the profit distribution problem of a unified warehouse and distribution alliance based on the improved Shapley value method. Firstly, the traditional Shapley value method is improved by using a comprehensive correction factor, including the proportions of investment, risk, and innovative research contributions. Secondly, each factor’s weight is determined by the analytic hierarchy process (AHP), and the profits are distributed according to the contribution of each express enterprise to the alliance. Finally, an example is given to verify the validity of the modified algorithm. It proves that the modified Shapley value method can effectively solve the problem of profit distribution.

]]>Algorithms doi: 10.3390/a14020048

Authors: András Faragó Zohre R. Mojaveri

The Disjoint Connecting Paths problem and its capacitated generalization, called Unsplittable Flow problem, play an important role in practical applications such as communication network design and routing. These tasks are NP-hard in general, but various polynomial-time approximations are known. Nevertheless, the approximations tend to be either too loose (allowing large deviation from the optimum), or too complicated, often rendering them impractical in large, complex networks. Therefore, our goal is to present a solution that provides a relatively simple, efficient algorithm for the unsplittable flow problem in large directed graphs, where the task is NP-hard, and is known to remain NP-hard even to approximate up to a large factor. The efficiency of our algorithm is achieved by sacrificing a small part of the solution space. This also represents a novel paradigm for approximation. Rather than giving up the search for an exact solution, we restrict the solution space to a subset that is the most important for applications, and excludes only a small part that is marginal in some well-defined sense. Specifically, the sacrificed part only contains scenarios where some edges are very close to saturation. Since nearly saturated links are undesirable in practical applications, therefore, excluding near saturation is quite reasonable from the practical point of view. We refer the solutions that contain no nearly saturated edges as safe solutions, and call the approach safe approximation. We prove that this safe approximation can be carried out efficiently. That is, once we restrict ourselves to safe solutions, we can find the exact optimum by a randomized polynomial time algorithm.

]]>Algorithms doi: 10.3390/a14020047

Authors: Xiaoting Mo Xinglu Liu Wai Kin (Victor) Chan

The imbalanced distribution of shared bikes in the dockless bike-sharing system (a typical example of the resource-sharing system), which may lead to potential customer churn and lost profit, gradually becomes a vital problem for bike-sharing firms and their users. To resolve the problem, we first formulate the bike-sharing system as a Markovian queueing network with higher-demand nodes and lower-demand nodes, which can provide steady-state probabilities of having a certain number of bikes at one node. A model reduction method is then designed to reduce the complexity of the proposed model. Subsequently, we adopt an operator-based relocation strategy to optimize the reduced network. The objective of the optimization model is to maximize the total profit and act as a decision-making tool for operators to determine the optimal relocation frequency. The results reveal that it is possible for most of the shared bikes to gather at one low-demand node eventually in the long run under the influence of the various arrival rates at different nodes. However, the decrease of the number of bikes at the high-demand nodes is more sensitive to the unequal demands, especially when the size of the network and the number of bikes in the system are large. It may cause a significant loss for operators, to which they should pay attention. Meanwhile, different estimated values of parameters related with revenue and cost affect the optimization results differently.

]]>Algorithms doi: 10.3390/a14020046

Authors: Volodymyr Dzyura Pavlo Maruschak Olegas Prentkovskis

The analytical dependences for determining the overlap area of V-shaped grooves of partially regular microrelief shifted by an angular pitch of 0.5° are established. The V-shaped grooves are formed on the end surface of the rotary body by vibration. In addition, the intersection between groove elements can be of different types. The relationship between the geometric parameters of V-shaped grooves and their location is determined. The influence of geometrical parameters of grooves on the overlap area is established depending on their location. Measures are proposed to ensure that the burnishing area is the same at different distances from the center of rotation of the rotary body end surface on which the partially regular microrelief is formed. A graph showing the dependence of the overlap area of two grooves on the axial pitch between them is constructed, and a block diagram of the algorithm for determining the optimal value of the axial pitch is developed.

]]>Algorithms doi: 10.3390/a14020045

Authors: Rafael D. Tordecilla Pedro J. Copado-Méndez Javier Panadero Carlos L. Quintero-Araujo Jairo R. Montoya-Torres Angel A. Juan

The location routing problem integrates both a facility location and a vehicle routing problem. Each of these problems are NP-hard in nature, which justifies the use of heuristic-based algorithms when dealing with large-scale instances that need to be solved in reasonable computing times. This paper discusses a realistic variant of the problem that considers facilities of different sizes and two types of uncertainty conditions. In particular, we assume that some customers’ demands are stochastic, while others follow a fuzzy pattern. An iterated local search metaheuristic is integrated with simulation and fuzzy logic to solve the aforementioned problem, and a series of computational experiments are run to illustrate the potential of the proposed algorithm.

]]>Algorithms doi: 10.3390/a14020044

Authors: Dominik Köppl

We present algorithms computing the non-overlapping Lempel–Ziv-77 factorization and the longest previous non-overlapping factor table within small space in linear or near-linear time with the help of modern suffix tree representations fitting into limited space. With similar techniques, we show how to answer substring compression queries for the Lempel–Ziv-78 factorization with a possible logarithmic multiplicative slowdown depending on the used suffix tree representation.

]]>Algorithms doi: 10.3390/a14020043

Authors: Pedro Maristany de las Casas Ralf Borndörfer Luitgard Kraus Antonio Sedeño-Noda

The Dynamic Multiobjective Shortest Path problem features multidimensional costs that can depend on several variables and not only on time; this setting is motivated by flight planning applications and the routing of electric vehicles. We give an exact algorithm for the FIFO case and derive from it an FPTAS for both, the static Multiobjective Shortest Path (MOSP) problems and, under mild assumptions, for the dynamic problem variant. The resulting FPTAS is computationally efficient and beats the known complexity bounds of other FPTAS for MOSP problems.

]]>Algorithms doi: 10.3390/a14020041

Authors: Markus Rabe Jesus Gonzalez-Feliu Jorge Chicaiza-Vaca Rafael D. Tordecilla

The introduction of automated parcel locker (APL) systems is one possible approach to improve urban logistics (UL) activities. Based on the city of Dortmund as case study, we propose a simulation-optimization approach integrating a system dynamics simulation model (SDSM) with a multi-period capacitated facility location problem (CFLP). We propose this integrated model as a decision support tool for future APL implementations as a last-mile distribution scheme. First, we built a causal-loop and stock-flow diagram to show main components and interdependencies of the APL systems. Then, we formulated a multi-period CFLP model to determine the optimal number of APLs for each period. Finally, we used a Monte Carlo simulation to estimate the costs and reliability level with random demands. We evaluate three e-shopper rate scenarios with the SDSM, and then analyze ten detailed demand configurations based on the results for the middle-size scenario with our CFLP model. After 36 months, the number of APLs increases from 99 to 165 with the growing demand, and stabilizes in all configurations from month 24. A middle-demand configuration, which has total costs of about 750,000&euro;, already locates a suitable number of APLs. If the budget is lower, our approach offers alternatives for decision-makers.

]]>Algorithms doi: 10.3390/a14020042

Authors: Marvin Kastner Nicole Nellen Anne Schwientek Carlos Jahn

At container terminals, many cargo handling processes are interconnected and occur in parallel. Within short time windows, many operational decisions need to be made and should consider both time efficiency and equipment utilization. During operation, many sources of disturbance and, thus, uncertainty exist. For these reasons, perfectly coordinated processes can potentially unravel. This study analyzes simulation-based optimization, an approach that considers uncertainty by means of simulation while optimizing a given objective. The developed procedure simultaneously scales the amount of utilized equipment and adjusts the selection and tuning of operational policies. Thus, the benefits of a simulation study and an integrated optimization framework are combined in a new way. Four meta-heuristics&mdash;Tree-structured Parzen Estimator, Bayesian Optimization, Simulated Annealing, and Random Search&mdash;guide the simulation-based optimization process. Thus, this study aims to determine a favorable configuration of equipment quantity and operational policies for container terminals using a small number of experiments and, simultaneously, to empirically compare the chosen meta-heuristics including the reproducibility of the optimization runs. The results show that simulation-based optimization is suitable for identifying the amount of required equipment and well-performing policies. Among the presented scenarios, no clear ranking between meta-heuristics regarding the solution quality exists. The approximated optima suggest that pooling yard trucks and a yard block assignment that is close to the quay crane are preferable.

]]>Algorithms doi: 10.3390/a14020040

Authors: Katherine Mary Malan

Fitness landscapes were proposed in 1932 as an abstract notion for understanding biological evolution and were later used to explain evolutionary algorithm behaviour. The last ten years has seen the field of fitness landscape analysis develop from a largely theoretical idea in evolutionary computation to a practical tool applied in optimisation in general and more recently in machine learning. With this widened scope, new types of landscapes have emerged such as multiobjective landscapes, violation landscapes, dynamic and coupled landscapes and error landscapes. This survey is a follow-up from a 2013 survey on fitness landscapes and includes an additional 11 landscape analysis techniques. The paper also includes a survey on the applications of landscape analysis for understanding complex problems and explaining algorithm behaviour, as well as algorithm performance prediction and automated algorithm configuration and selection. The extensive use of landscape analysis in a broad range of areas highlights the wide applicability of the techniques and the paper discusses some opportunities for further research in this growing field.

]]>Algorithms doi: 10.3390/a14020039

Authors: Carlos Lassance Vincent Gripon Antonio Ortega

Deep Learning (DL) has attracted a lot of attention for its ability to reach state-of-the-art performance in many machine learning tasks. The core principle of DL methods consists of training composite architectures in an end-to-end fashion, where inputs are associated with outputs trained to optimize an objective function. Because of their compositional nature, DL architectures naturally exhibit several intermediate representations of the inputs, which belong to so-called latent spaces. When treated individually, these intermediate representations are most of the time unconstrained during the learning process, as it is unclear which properties should be favored. However, when processing a batch of inputs concurrently, the corresponding set of intermediate representations exhibit relations (what we call a geometry) on which desired properties can be sought. In this work, we show that it is possible to introduce constraints on these latent geometries to address various problems. In more detail, we propose to represent geometries by constructing similarity graphs from the intermediate representations obtained when processing a batch of inputs. By constraining these Latent Geometry Graphs (LGGs), we address the three following problems: (i) reproducing the behavior of a teacher architecture is achieved by mimicking its geometry, (ii) designing efficient embeddings for classification is achieved by targeting specific geometries, and (iii) robustness to deviations on inputs is achieved via enforcing smooth variation of geometry between consecutive latent spaces. Using standard vision benchmarks, we demonstrate the ability of the proposed geometry-based methods in solving the considered problems.

]]>Algorithms doi: 10.3390/a14020038

Authors: Amr Mohamed AbdelAziz Louai Alarabi Saleh Basalamah Abdeltawab Hendawi

The wide spread of Covid-19 has led to infecting a huge number of patients, simultaneously. This resulted in a massive number of requests for medical care, at the same time. During the first wave of Covid-19, many people were not able to get admitted to appropriate hospitals because of the immense number of patients. Admitting patients to suitable hospitals can decrease the in-bed time of patients, which can lead to saving many lives. Also, optimizing the admission process can minimize the waiting time for medical care, which can save the lives of severe cases. The admission process needs to consider two main criteria: the admission time and the readiness of the hospital that will accept the patients. These two objectives convert the admission problem into a Multi-Objective Problem (MOP). Pareto Optimization (PO) is a common multi-objective optimization method that has been applied to different MOPs and showed its ability to solve them. In this paper, a PO-based algorithm is proposed to deal with admitting Covid-19 patients to hospitals. The method uses PO to vary among hospitals to choose the most suitable hospital for the patient with the least admission time. The method also considers patients with severe cases by admitting them to hospitals with the least admission time regardless of their readiness. The method has been tested over a real-life dataset that consisted of 254 patients obtained from King Faisal specialist hospital in Saudi Arabia. The method was compared with the lexicographic multi-objective optimization method regarding admission time and accuracy. The proposed method showed its superiority over the lexicographic method regarding the two criteria, which makes it a good candidate for real-life admission systems.

]]>Algorithms doi: 10.3390/a14020037

Authors: Shixun Wang Qiang Chen

Boosting of the ensemble learning model has made great progress, but most of the methods are Boosting the single mode. For this reason, based on the simple multiclass enhancement framework that uses local similarity as a weak learner, it is extended to multimodal multiclass enhancement Boosting. First, based on the local similarity as a weak learner, the loss function is used to find the basic loss, and the logarithmic data points are binarized. Then, we find the optimal local similarity and find the corresponding loss. Compared with the basic loss, the smaller one is the best so far. Second, the local similarity of the two points is calculated, and then the loss is calculated by the local similarity of the two points. Finally, the text and image are retrieved from each other, and the correct rate of text and image retrieval is obtained, respectively. The experimental results show that the multimodal multi-class enhancement framework with local similarity as the weak learner is evaluated on the standard data set and compared with other most advanced methods, showing the experience proficiency of this method.

]]>Algorithms doi: 10.3390/a14020036

Authors: Jonathan Mwaura Andries P. Engelbrecht Filipe V. Nepomuceno

Multimodal problems are single objective optimisation problems with multiple local and global optima. The objective of multimodal optimisation is to locate all or most of the optima. Niching algorithms are the techniques utilised to locate these optima. A critical factor in determining the success of niching algorithms is how well the search space is covered by the candidate solutions. For niching algorithms, high diversity during the exploration phase will facilitate location and identification of many solutions while a low diversity means that the candidate solutions are clustered at optima. This paper provides a review of measures used to quantify diversity, and how they can be utilised to quantify the dispersion of both the candidate solutions and the solutions of niching algorithms (i.e., found optima). The investigated diversity measures are then used to evaluate the distribution of candidate solutions and solutions when the enhanced species-based particle swarm optimisation (ESPSO) algorithm is utilised to optimise a selected set of multimodal problems.

]]>Algorithms doi: 10.3390/a14020035

Authors: Davide Bilò Luciano Gualà Stefano Leucci Guido Proietti

Network creation games have been extensively used as mathematical models to capture the key aspects of the decentralized process that leads to the formation of interconnected communication networks by selfish agents. In these games, each user of the network is identified by a node and selects which link to activate by strategically balancing his/her building cost with his/her usage cost (which is a function of the distances towards the other player in the network to be built). In these games, a widespread assumption is that players have a common and complete information about the evolving network topology. This is only realistic for small-scale networks as, when the network size grows, it quickly becomes impractical for the single users to gather such a global and fine-grained knowledge of the network in which they are embedded. In this work, we weaken this assumption, by only allowing players to have a partial view of the network. To this aim, we borrow three popular traceroute-based knowledge models used in network discovery: (i) distance vector, (ii) shortest-path tree view, and (iii) layered view. We settle many of the classical game theoretic questions in all of the above models. More precisely, we introduce a suitable (and unifying) equilibrium concept which we then use to study the convergence of improving and best response dynamics, the computational complexity of computing a best response, and to provide matching upper and lower bounds to the price of anarchy.

]]>Algorithms doi: 10.3390/a14020034

Authors: Maria-Evangelia Papadaki Nicolas Spyratos Yannis Tzitzikas

The continuous accumulation of multi-dimensional data and the development of Semantic Web and Linked Data published in the Resource Description Framework (RDF) bring new requirements for data analytics tools. Such tools should take into account the special features of RDF graphs, exploit the semantics of RDF and support flexible aggregate queries. In this paper, we present an approach for applying analytics to RDF data based on a high-level functional query language, called HIFUN. According to that language, each analytical query is considered to be a well-formed expression of a functional algebra and its definition is independent of the nature and structure of the data. In this paper, we investigate how HIFUN can be used for easing the formulation of analytic queries over RDF data. We detail the applicability of HIFUN over RDF, as well as the transformations of data that may be required, we introduce the translation rules of HIFUN queries to SPARQL and we describe a first implementation of the proposed model.

]]>Algorithms doi: 10.3390/a14020033

Authors: Algorithms Editorial Office Algorithms Editorial Office

Peer review is the driving force of journal development, and reviewers are gatekeepers who ensure that Algorithms maintains its standards for the high quality of its published papers [...]

]]>Algorithms doi: 10.3390/a14020032

Authors: Frank Werner

This Special Issue of Algorithms is of a different nature than other Special Issue in the journal, which are usually dedicated to a particular subjects in the area of algorithms [...]

]]>Algorithms doi: 10.3390/a14020031

Authors: Dushko Stavrov Gorjan Nadzinski Stojche Deskovski Mile Stankovski

In this paper, we discuss an improved version of the conventional PID (Proportional&ndash;Integral&ndash;Derivative) controller, the Dynamically Updated PID (DUPID) controller. The DUPID is a control solution which preserves the advantages of the PID controller and tends to improve them by introducing a quadratic error model in the PID control structure. The quadratic error model is constructed over a window of past error points. The objective is to use the model to give the conventional PID controller the awareness needed to battle the effects caused by the variation of the parameters. The quality of the predictions that the model is able to deliver depends on the appropriate selection of data used for its construction. In this regard, the paper discusses two algorithms, named 1D (one dimensional) and 2D (two dimensional) DUPID. Appropriate to their names, the former selects data based on one coordinate, whereas the latter selects the data based on two coordinates. Both these versions of the DUPID controller are compared to the conventional PID controller with respect to their capabilities of controlling a Continuous Stirred Tank Reactor (CSTR) system with varying parameters in three different scenarios. As a quantifying measure of the control performance, the integral of absolute error (IAE) metric is used. The results from the performed simulations indicated that the two versions of the DUPID controller improved the control performance of the conventional PID controller in all scenarios.

]]>Algorithms doi: 10.3390/a14020030

Authors: Linhuai Tang Zhihong Huang Gang Cai Yong Zheng Jiamin Chen

Due to high parallelism, field-programmable gate arrays are widely used as accelerators in engineering and scientific fields, which involve a large number of operations of vector and matrix. High-performance accumulation circuits are the key to large-scale matrix operations. By selecting the adder as the reduction operator, the reduction circuit can implement the accumulation function. However, the pipelined adder will bring challenges to the design of the reduction circuit. To solve this problem, we propose a novel reduction circuit based on binary tree path partition, which can simultaneously handle multiple data sets with arbitrary lengths. It divides the input data into multiple groups and sends them to different iterations for calculation. The elements belonging to the same data set in each group are added to obtain a partial result, and the partial results of the same data set are added to achieve the final result. Compared with other reduction methods, it has the least area-time product.

]]>Algorithms doi: 10.3390/a14020029

Authors: Haohao Zhou Xiangzhi Wei

In this paper, we propose a particle swarm optimization variant based on a novel evaluation of diversity (PSO-ED). By a novel encoding of the sub-space of the search space and the hash table technique, the diversity of the swarm can be evaluated efficiently without any information compression. This paper proposes a notion of exploration degree based on the diversity of the swarm in the exploration, exploitation, and convergence states to characterize the degree of demand for the dispersion of the swarm. Further, a disturbance update mode is proposed to help the particles jump to the promising regions while reducing the cost of function evaluations for poor particles. The effectiveness of PSO-ED is validated on the CEC2015 test suite by comparison with seven popular PSO variants out of 12 benchmark functions; PSO-ED achieves six best results for both 10-D and 30-D.

]]>Algorithms doi: 10.3390/a14010028

Authors: Damianos P. Melidis Wolfgang Nejdl

Predicting biological properties of unseen proteins is shown to be improved by the use of protein sequence embeddings. However, these sequence embeddings have the caveat that biological metadata do not exist for each amino acid, in order to measure the quality of each unique learned embedding vector separately. Therefore, current sequence embedding cannot be intrinsically evaluated on the degree of their captured biological information in a quantitative manner. We address this drawback by our approach, dom2vec, by learning vector representation for protein domains and not for each amino acid base, as biological metadata do exist for each domain separately. To perform a reliable quantitative intrinsic evaluation in terms of biology knowledge, we selected the metadata related to the most distinctive biological characteristics of a domain, which are its structure, enzymatic, and molecular function. Notably, dom2vec obtains an adequate level of performance in the intrinsic assessment&mdash;therefore, we can draw an analogy between the local linguistic features in natural languages and the domain structure and function information in domain architectures. Moreover, we demonstrate the dom2vec applicability on protein prediction tasks, by comparing it with state-of-the-art sequence embeddings in three downstream tasks. We show that dom2vec outperforms sequence embeddings for toxin and enzymatic function prediction and is comparable with sequence embeddings in cellular location prediction.

]]>Algorithms doi: 10.3390/a14010027

Authors: Bi Kouaï Bertin Kayé Moustapha Diaby Moussa Koivogui Souleymane Oumtanaga

This study aims to compare the results of a memetic algorithm with those of the two-phase decomposition heuristic on the external depot production routing problem in a supply chain. We have modified the classical scheme of a genetic algorithm by replacing the mutation operator by three local search algorithms. The first local search consists in exchanging two customers visited the same day. The second consists in trying an exchange between two customers visited at consecutive periods and the third consists in removing a customer from his current tour for a better insertion in any tour of the same period. The tests that were carried out on 128 instances of the literature have highlighted the effectiveness of the memetic algorithm developed in this work compared to the two-phase decomposition heuristic. This is reflected by the fact that the results obtained by the memetic algorithm lead to a reduction in the overall average cost of production, inventory, and transport, ranging from 3.65% to 16.73% with an overall rate of 11.07% with regard to the results obtained with the two-phase decomposition heuristic. The outcomes will be beneficial to researchers and supply chain managers in the choice and development of heuristics and metaheuristics for the resolution of production routing problem.

]]>Algorithms doi: 10.3390/a14010026

Authors: Yiran Xue Rui Wu Jiafeng Liu Xianglong Tang

Existing crowd evacuation guidance systems require the manual design of models and input parameters, incurring a significant workload and a potential for errors. This paper proposed an end-to-end intelligent evacuation guidance method based on deep reinforcement learning, and designed an interactive simulation environment based on the social force model. The agent could automatically learn a scene model and path planning strategy with only scene images as input, and directly output dynamic signage information. Aiming to solve the &ldquo;dimension disaster&rdquo; phenomenon of the deep Q network (DQN) algorithm in crowd evacuation, this paper proposed a combined action-space DQN (CA-DQN) algorithm that grouped Q network output layer nodes according to action dimensions, which significantly reduced the network complexity and improved system practicality in complex scenes. In this paper, the evacuation guidance system is defined as a reinforcement learning agent and implemented by the CA-DQN method, which provides a novel approach for the evacuation guidance problem. The experiments demonstrate that the proposed method is superior to the static guidance method, and on par with the manually designed model method.

]]>Algorithms doi: 10.3390/a14010025

Authors: Piotr M. Marusak

A method for the advanced construction of the dynamic matrix for Model Predictive Control (MPC) algorithms with linearization is proposed in the paper. It extends numerically efficient fuzzy algorithms utilizing skillful linearization. The algorithms combine the control performance offered by the MPC algorithms with nonlinear optimization (NMPC algorithms) with the numerical efficiency of the MPC algorithms based on linear models in which the optimization problem is a standard, easy-to-solve, quadratic programming problem with linear constraints. In the researched algorithms, the free response obtained using a nonlinear process model and the future trajectory of the control signals is used to construct an advanced dynamic matrix utilizing the easy-to-obtain fuzzy model. This leads to obtaining very good prediction and control quality very close to those offered by NMPC algorithms. The proposed approach is tested in the control system of a nonlinear chemical control plant&mdash;a CSTR reactor with the van de Vusse reaction.

]]>Algorithms doi: 10.3390/a14010024

Authors: Diogo Remoaldo Isabel Jesus

This paper presents the results obtained for the maximum power point tracking (MPPT) technique applied to a photovoltaic (PV) system, composed of five solar panels in series using two different methodologies. First, we considered a traditional Perturb and Observe (P&amp;O) algorithm and in a second stage we applied a Fuzzy Logic Controller (FLC) that uses fuzzy logic concepts to improve the traditional P&amp;O; both were implemented in a boost converter. The main aim of this paper is to study if an artificial intelligence (AI) based MPPT method, can be more efficient, stable and adaptable than a traditional MPPT method, in varying environment conditions, namely solar irradiation and/or environment temperature and also to analyze their behaviour in steady state conditions. The proposed FLC with a rule base collection of 25 rules outperformed the controller using the traditional P&amp;O algorithm due to its adaptative step size, enabling the FLC to adapt the PV system faster to changing environment conditions, guessing the correct maximum power point (MPP) faster and achieving lower oscillations in steady state conditions, leading to higher generated energy due to lower losses both in steady state and dynamic environment conditions. The simulations in this study were performed using MATLAB (Version 2018)/Simulink.

]]>Algorithms doi: 10.3390/a14010023

Authors: Markus Rabe Majsa Ammouriova Dominik Schmitt Felix Dross

The distribution process in business-to-business materials trading is among the most complex and in transparent ones within logistics. The highly volatile environment requires continuous adaptations by the responsible decision-makers, who face a substantial number of potential improvement actions with conflicting goals, such as simultaneously maintaining a high service level and low costs. Simulation-optimisation approaches have been proposed in this context, for example based on evolutionary algorithms. But, on real-world system dimensions, they face impractically long computation times. This paper addresses this challenge in two principal streams. On the one hand, reinforcement learning is investigated to reduce the response time of the system in a concrete decision situation. On the other hand, domain-specific information and defining equivalent solutions are exploited to support a metaheuristic algorithm. For these approaches, we have developed suitable implementations and evaluated them with subsets of real-world data. The results demonstrate that reinforcement learning exploits the idle time between decision situations to learn which decisions might be most promising, thus adding computation time but significantly reducing the response time. Using domain-specific information reduces the number of required simulation runs and guides the search for promising actions. In our experimentation, defining equivalent solutions decreased the number of required simulation runs up to 15%.

]]>Algorithms doi: 10.3390/a14010022

Authors: Chuan-Min Lee

This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the {k}-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly chordal graphs, clique perfect graphs, total graphs, split graphs, line graphs, and dually chordal graphs. We give equations to compute the {k}-clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the {k}-clique transversal problem is polynomial-time solvable for graphs whose clique transversal numbers equal their clique independence numbers. We also show the relationship between the signed and generalization clique problems and present NP-completeness results for the considered problems on k-trees with unbounded k, planar graphs, doubly chordal graphs, total graphs, split graphs, line graphs, and dually chordal graphs.

]]>Algorithms doi: 10.3390/a14010021

Authors: Christoph Hansknecht Imke Joormann Sebastian Stiller

The time-dependent traveling salesman problem (TDTSP) asks for a shortest Hamiltonian tour in a directed graph where (asymmetric) arc-costs depend on the time the arc is entered. With traffic data abundantly available, methods to optimize routes with respect to time-dependent travel times are widely desired. This holds in particular for the traveling salesman problem, which is a corner stone of logistic planning. In this paper, we devise column-generation-based IP methods to solve the TDTSP in full generality, both for arc- and path-based formulations. The algorithmic key is a time-dependent shortest path problem, which arises from the pricing problem of the column generation and is of independent interest&mdash;namely, to find paths in a time-expanded graph that are acyclic in the underlying (non-expanded) graph. As this problem is computationally too costly, we price over the set of paths that contain no cycles of length k. In addition, we devise&mdash;tailored for the TDTSP&mdash;several families of valid inequalities, primal heuristics, a propagation method, and a branching rule. Combining these with the time-dependent shortest path pricing we provide&mdash;to our knowledge&mdash;the first elaborate method to solve the TDTSP in general and with fully general time-dependence. We also provide for results on complexity and approximability of the TDTSP. In computational experiments on randomly generated instances, we are able to solve the large majority of small instances (20 nodes) to optimality, while closing about two thirds of the remaining gap of the large instances (40 nodes) after one hour of computation.

]]>Algorithms doi: 10.3390/a14010020

Authors: Adrian Serrano-Hernandez Rocio de la Torre Luis Cadarso Javier Faulin

E-commerce has boosted in the last decades because of the achievements of the information and telecommunications technology along with the changes in the society life-style. More recently, the groceries online purchase (or e-grocery), has also prevailed as a way of making the weekly shopping, particularly, the one including fresh vegetables and fruit. Furthermore, this type of virtual shopping in supermarkets is gaining importance as the most efficient delivery system in cost and time. Thus, we have evaluated in this study the influence of the cooperation-based policies on costs and service quality among different supermarkets in Pamplona, Spain. Concerning methodology, first of all, we carried out a survey in Pamplona having the purpose of modelling the demand patterns about e-grocery. Second, we have developed an agent-based simulation model for generating scenarios in non-cooperative, limited cooperation, and full cooperation settings, considering the real data obtained from the survey analysis. At this manner, Vehicle Routing Problems (VRP) and Multi Depot VRPs (MDVRP) are dynamically generated and solved within the simulation framework using a biased-randomization algorithm. Finally, the results show significant reductions in distance driven and lead times when employing horizontal cooperation in e-grocery distribution.

]]>Algorithms doi: 10.3390/a14010019

Authors: Mario Andrés Muñoz Michael Kirley

In this paper, we investigate how systemic errors due to random sampling impact on automated algorithm selection for bound-constrained, single-objective, continuous black-box optimization. We construct a machine learning-based algorithm selector, which uses exploratory landscape analysis features as inputs. We test the accuracy of the recommendations experimentally using resampling techniques and the hold-one-instance-out and hold-one-problem-out validation methods. The results demonstrate that the selector remains accurate even with sampling noise, although not without trade-offs.

]]>Algorithms doi: 10.3390/a14010018

Authors: Michael Li Santoso Wibowo Wei Li Lily D. Li

Extreme learning machine (ELM) is a popular randomization-based learning algorithm that provides a fast solution for many regression and classification problems. In this article, we present a method based on ELM for solving the spectral data analysis problem, which essentially is a class of inverse problems. It requires determining the structural parameters of a physical sample from the given spectroscopic curves. We proposed that the unknown target inverse function is approximated by an ELM through adding a linear neuron to correct the localized effect aroused by Gaussian basis functions. Unlike the conventional methods involving intensive numerical computations, under the new conceptual framework, the task of performing spectral data analysis becomes a learning task from data. As spectral data are typical high-dimensional data, the dimensionality reduction technique of principal component analysis (PCA) is applied to reduce the dimension of the dataset to ensure convergence. The proposed conceptual framework is illustrated using a set of simulated Rutherford backscattering spectra. The results have shown the proposed method can achieve prediction inaccuracies of less than 1%, which outperform the predictions from the multi-layer perceptron and numerical-based techniques. The presented method could be implemented as application software for real-time spectral data analysis by integrating it into a spectroscopic data collection system.

]]>Algorithms doi: 10.3390/a14010017

Authors: Rose Nakasi Ernest Mwebaze Aminah Zawedde

Effective determination of malaria parasitemia is paramount in aiding clinicians to accurately estimate the severity of malaria and guide the response for quality treatment. Microscopy by thick smear blood films is the conventional method for malaria parasitemia determination. Despite its edge over other existing methods of malaria parasitemia determination, it has been critiqued for being laborious, time consuming and equally requires expert knowledge for an efficient manual quantification of the parasitemia. This pauses a big challenge to most low developing countries as they are not only highly endemic but equally low resourced in terms of technical personnel in medical laboratories This study presents an end-to-end deep learning approach to automate the localization and count of P.falciparum parasites and White Blood Cells (WBCs) for effective parasitemia determination. The method involved building computer vision models on a dataset of annotated thick blood smear images. These computer vision models were built based on pre-trained deep learning models including Faster Regional Convolutional Neural Network (Faster R-CNN) and Single Shot Multibox Detector (SSD) models that help process the obtained digital images. To improve model performance due to a limited dataset, data augmentation was applied. Results from the evaluation of our approach showed that it reliably detected and returned a count of parasites and WBCs with good precision and recall. A strong correlation was observed between our model-generated counts and the manual counts done by microscopy experts (posting a spear man correlation of &rho; = 0.998 for parasites and &rho; = 0.987 for WBCs). Additionally, our proposed SSD model was quantized and deployed on a mobile smartphone-based inference app to detect malaria parasites and WBCs in situ. Our proposed method can be applied to support malaria diagnostics in settings with few trained Microscopy Experts yet constrained with large volume of patients to diagnose.

]]>Algorithms doi: 10.3390/a14010016

Authors: Jalal Al-Afandi András Horváth

Genetic Algorithms are stochastic optimization methods where solution candidates, complying to a specific problem representation, are evaluated according to a predefined fitness function. These approaches can provide solutions in various tasks even, where analytic solutions can not be or are too complex to be computed. In this paper we will show, how certain set of problems are partially solvable allowing us to grade segments of a solution individually, which results local and individual tuning of mutation parameters for genes. We will demonstrate the efficiency of our method on the N-Queens and travelling salesman problems where we can demonstrate that our approach always results faster convergence and in most cases a lower error than the traditional approach.

]]>Algorithms doi: 10.3390/a14010015

Authors: Vittorio Bilò Michele Flammini Luca Moscardelli

We consider the problem of determining a routing in all-optical networks, in which some couples of nodes want to communicate. In particular, we study this problem from the point of view of a network provider that has to design suitable payment functions for non-cooperative agents, corresponding to the couples of nodes wishing to communicate. The network provider aims at inducing stable routings (i.e., routings corresponding to Nash equilibria) using a low number of wavelengths. We consider three different kinds of local knowledge that agents may exploit to compute their payments, leading to three corresponding information levels. Under complete information, the network provider can design a payment function, inducing the agents to reach a Nash equilibrium mirroring any desired routing. If the price to an agent is computed only as a function of the wavelengths used along connecting paths (minimal level) or edges (intermediate level), the most reasonable functions either do not admit Nash equilibria or admit very inefficient ones, i.e., with the largest possible price of anarchy. However, by suitably restricting the network topology, a constant price of anarchy for chains and rings and a logarithmic one for trees can be obtained under the minimal and intermediate levels, respectively.

]]>Algorithms doi: 10.3390/a14010014

Authors: Nicola Prezza

Text indexing is a classical algorithmic problem that has been studied for over four decades: given a text T, pre-process it off-line so that, later, we can quickly count and locate the occurrences of any string (the query pattern) in T in time proportional to the query&rsquo;s length. The earliest optimal-time solution to the problem, the suffix tree, dates back to 1973 and requires up to two orders of magnitude more space than the plain text just to be stored. In the year 2000, two breakthrough works showed that efficient queries can be achieved without this space overhead: a fast index be stored in a space proportional to the text&rsquo;s entropy. These contributions had an enormous impact in bioinformatics: today, virtually any DNA aligner employs compressed indexes. Recent trends considered more powerful compression schemes (dictionary compressors) and generalizations of the problem to labeled graphs: after all, texts can be viewed as labeled directed paths. In turn, since finite state automata can be considered as a particular case of labeled graphs, these findings created a bridge between the fields of compressed indexing and regular language theory, ultimately allowing to index regular languages and promising to shed new light on problems, such as regular expression matching. This survey is a gentle introduction to the main landmarks of the fascinating journey that took us from suffix trees to today&rsquo;s compressed indexes for labeled graphs and regular languages.

]]>Algorithms doi: 10.3390/a14010013

Authors: Antonella Guzzo

This article is the editorial of the &ldquo;Process Mining and Emerging Applications&rdquo; (https://www [...]

]]>Algorithms doi: 10.3390/a14010012

Authors: Abdelraouf Ishtaiwi Feda Alshahwan Naser Jamal Wael Hadi Muhammad AbuArqoub

For decades, the use of weights has proven its superior ability to improve dynamic local search weighting algorithms&rsquo; overall performance. This paper proposes a new mechanism where the initial clause&rsquo;s weights are dynamically allocated based on the problem&rsquo;s structure. The new mechanism starts by examining each clause in terms of its size and the extent of its link, and its proximity to other clauses. Based on our examination, we categorized the clauses into four categories: (1) clauses small in size and linked with a small neighborhood, (2) clauses small in size and linked with a large neighborhood, (3) clauses large in size and linked with a small neighborhood, and (4) clauses large in size and linked with a large neighborhood. Then, the initial weights are dynamically allocated according to each clause category. To examine the efficacy of the dynamic initial weight assignment, we conducted an extensive study of our new technique on many problems. The study concluded that the dynamic allocation of initial weights contributes significantly to improving the search process&rsquo;s performance and quality. To further investigate the new mechanism&rsquo;s effect, we compared the new mechanism with the state-of-the-art algorithms belonging to the same family in terms of using weights, and it was clear that the new mechanism outperformed the state-of-the-art clause weighting algorithms. We also show that the new mechanism could be generalized with minor changes to be utilized within the general-purpose stochastic local search state-of-the-art weighting algorithms.

]]>Algorithms doi: 10.3390/a14010011

Authors: Marta Galvani Chiara Bardelli Silvia Figini Pietro Muliere

Bootstrap resampling techniques, introduced by Efron and Rubin, can be presented in a general Bayesian framework, approximating the statistical distribution of a statistical functional ϕ(F), where F is a random distribution function. Efron&rsquo;s and Rubin&rsquo;s bootstrap procedures can be extended, introducing an informative prior through the Proper Bayesian bootstrap. In this paper different bootstrap techniques are used and compared in predictive classification and regression models based on ensemble approaches, i.e., bagging models involving decision trees. Proper Bayesian bootstrap, proposed by Muliere and Secchi, is used to sample the posterior distribution over trees, introducing prior distributions on the covariates and the target variable. The results obtained are compared with respect to other competitive procedures employing different bootstrap techniques. The empirical analysis reports the results obtained on simulated and real data.

]]>Algorithms doi: 10.3390/a14010010

Authors: Robert Nebeluk Maciej Ławryńczuk

This work is concerned with the tuning of the parameters of Model Predictive Control (MPC) algorithms when used for industrial tasks, i.e., compensation of disturbances that affect the process (process uncontrolled inputs and measurement noises). The discussed simulation optimisation tuning procedure is quite computationally simple since the consecutive parameters are optimised separately, and it requires only a very limited number of simulations. It makes it possible to perform a multicriteria control assessment as a few control quality measures may be taken into account. The effectiveness of the tuning method is demonstrated for a multivariable distillation column. Two cases are considered: a perfect model case and a more practical case in which the model is characterised by some error. It is shown that the discussed tuning approach makes it possible to obtain very good control quality, much better than in the most common case in which all tuning parameters are constant.

]]>Algorithms doi: 10.3390/a14010009

Authors: João Paulo Costalonga Robert J. Kingan Sandra R. Kingan

A 3-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB 40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex. To test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of G&prime; from the cycles of G, where G&prime; is obtained from G by one of the two operations above. We eliminate isomorphic duplicates using certificates generated by McKay&rsquo;s isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with n vertices and m edges from the non-isomorphic minimally 3-connected graphs with n&minus;1 vertices and m&minus;2 edges, n&minus;1 vertices and m&minus;3 edges, and n&minus;2 vertices and m&minus;3 edges.

]]>Algorithms doi: 10.3390/a14010008

Authors: Davide Bilò Luciano Gualà Guido Proietti

Consider a communication network represented by a directed graph G=(V,E) of n nodes and m edges. Assume that edges in E are partitioned into two sets: a set C of edges with a fixed non-negative real cost, and a set P of edges whose costs are instead priced by a leader. This is done with the final intent of maximizing a revenue that will be returned for their use by a follower, whose goal in turn is to select for his communication purposes a subnetwork of Gminimizing a given objective function of the edge costs. In this paper, we study the natural setting in which the follower computes a single-source shortest paths tree of G, and then returns to the leader a payment equal to the sum of the selected priceable edges. Thus, the problem can be modeled as a one-round two-player Stackelberg Network Pricing Game, but with the novelty that the objective functions of the two players are asymmetric, in that the revenue returned to the leader for any of her selected edges is not equal to the cost of such an edge in the follower&rsquo;s solution. As is shown, for any ϵ&gt;0 and unless P=NP, the leader&rsquo;s problem of finding an optimal pricing is not approximable within n1/2&minus;ϵ, while, if G is unweighted and the leader can only decide which of her edges enter in the solution, then the problem is not approximable within n1/3&minus;ϵ. On the positive side, we devise a strongly polynomial-time O(n)-approximation algorithm, which favorably compares against the classic approach based on a single-price algorithm. Finally, motivated by practical applications, we consider the special cases in which edges in C are unweighted and happen to form two popular network topologies, namely stars and chains, and we provide a comprehensive characterization of their computational tractability.

]]>Algorithms doi: 10.3390/a14010007

Authors: Kui Ji Jianxiao Ma

Reserve capacity is the core of reliability analysis based on road network capacity. This article optimizes its bi-level programming model: the upper-level model has added service level coefficient and travel time limit, which realizes the unification of capacity and travel time reliability analysis to a certain extent. Stochastic user equilibrium (SUE) model based on origin has been selected as the lower-level model, which added capacity constraints to optimize distribution results, and allows the evaluation of reliability to be continued. Through the SUE model, the iterative step size of the method of successive averages can be optimized to improve the efficiency of the algorithm. After that, the article designs the algorithm flow of reliability analysis based on road network capacity, and verifies the feasibility of the designed algorithm with an example. Finally, combined with the conclusion of reliability analysis, this article puts forward some effective methods to improve the reliability of the urban road network.

]]>Algorithms doi: 10.3390/a14010006

Authors: Joonas Hämäläinen Tommi Kärkkäinen Tuomo Rossi

Two new initialization methods for K-means clustering are proposed. Both proposals are based on applying a divide-and-conquer approach for the K-means‖ type of an initialization strategy. The second proposal also uses multiple lower-dimensional subspaces produced by the random projection method for the initialization. The proposed methods are scalable and can be run in parallel, which make them suitable for initializing large-scale problems. In the experiments, comparison of the proposed methods to the K-means++ and K-means‖ methods is conducted using an extensive set of reference and synthetic large-scale datasets. Concerning the latter, a novel high-dimensional clustering data generation algorithm is given. The experiments show that the proposed methods compare favorably to the state-of-the-art by improving clustering accuracy and the speed of convergence. We also observe that the currently most popular K-means++ initialization behaves like the random one in the very high-dimensional cases.

]]>Algorithms doi: 10.3390/a14010005

Authors: Dominik Köppl Tomohiro I Isamu Furuya Yoshimasa Takabatake Kensuke Sakai Keisuke Goto

Re-Pairis a grammar compression scheme with favorably good compression rates. The computation of Re-Pair comes with the cost of maintaining large frequency tables, which makes it hard to compute Re-Pair on large-scale data sets. As a solution for this problem, we present, given a text of length n whose characters are drawn from an integer alphabet with size &sigma;=nO(1), an O(min(n2,n2lglog&tau;nlglglgn/log&tau;n)) time algorithm computing Re-Pair with max((n/c)lgn,nlg&tau;)+O(lgn) bits of working space including the text space, where c&ge;1 is a fixed user-defined constant and &tau; is the sum of &sigma; and the number of non-terminals. We give variants of our solution working in parallel or in the external memory model. Unfortunately, the algorithm seems not practical since a preliminary version already needs roughly one hour for computing Re-Pair on one megabyte of text.

]]>Algorithms doi: 10.3390/a14010004

Authors: Ralf Borndörfer Fabian Danecker Martin Weiser

We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our discrete-continuous optimization for enhanced resolution (DisCOptER) method computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are governed by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.

]]>Algorithms doi: 10.3390/a14010003

Authors: Pavel V. Gapeev Libo Li Zhuoshu Wu

We derive explicit solutions to the perpetual American cancellable standard put and call options in an extension of the Black&ndash;Merton&ndash;Scholes model. It is assumed that the contracts are cancelled at the last hitting times for the underlying asset price process of some constant upper or lower levels which are not stopping times with respect to the observable filtration. We show that the optimal exercise times are the first times at which the asset price reaches some lower or upper constant levels. The proof is based on the reduction of the original optimal stopping problems to the associated free-boundary problems and the solution of the latter problems by means of the smooth-fit conditions.

]]>Algorithms doi: 10.3390/a14010002

Authors: Emanuel Chereji Mircea-Bogdan Radac Alexandra-Iulia Szedlak-Stinean

This paper presents the performance of two sliding mode control algorithms, based on the Lyapunov-based sliding mode controller (LSMC) and reaching-law-based sliding mode controller (RSMC), with their novel variants designed and applied to the anti-lock braking system (ABS), which is known to be a strongly nonlinear system. The goal is to prove their superior performance over existing control approaches, in the sense that the LSMC and RSMC do not bring additional computational complexity, as they rely on a reduced number of tuning parameters. The performance of LSMC and RSMC solves the uncertainty in the process model which comes from unmodeled dynamics and a simplification of the actuator dynamics, leading to a reduced second order process. The contribution adds complete design details and stability analysis is provided. Additionally, performance comparisons with several adaptive, neural networks-based and model-free sliding mode control algorithms reveal the robustness of the proposed LSMC and RSMC controllers, in spite of the reduced number of tuning parameters. The robustness and reduced computational burden of the controllers validated on the real-world complex ABS make it an attractive solution for practical industrial implementations.

]]>Algorithms doi: 10.3390/a14010001

Authors: Saleh A. Bawazeer Saleh S. Baakeem Abdulmajeed A. Mohamad

Radial basis function (RBF) is gaining popularity in function interpolation as well as in solving partial differential equations thanks to its accuracy and simplicity. Besides, RBF methods have almost a spectral accuracy. Furthermore, the implementation of RBF-based methods is easy and does not depend on the location of the points and dimensionality of the problems. However, the stability and accuracy of RBF methods depend significantly on the shape parameter, which is primarily impacted by the basis function and the node distribution. At a small value of shape parameter, the RBF becomes more accurate, but unstable. Several approaches were followed in the open literature to overcome the instability issue. One of the approaches is optimizing the solver in order to improve the stability of ill-conditioned matrices. Another approach is based on searching for the optimal value of the shape parameter. Alternatively, modified bases are used to overcome instability. In the open literature, radial basis function using QR factorization (RBF-QR), stabilized expansion of Gaussian radial basis function (RBF-GA), rational radial basis function (RBF-RA), and Hermite-based RBFs are among the approaches used to change the basis. In this paper, the Taylor series is used to expand the RBF with respect to the shape parameter. Our analyses showed that the Taylor series alone is not sufficient to resolve the stability issue, especially away from the reference point of the expansion. Consequently, a new approach is proposed based on the partition of unity (PU) of RBF with respect to the shape parameter. The proposed approach is benchmarked. The method ensures that RBF has a weak dependency on the shape parameter, thereby providing a consistent accuracy for interpolation and derivative approximation. Several benchmarks are performed to assess the accuracy of the proposed approach. The novelty of the present approach is in providing a means to achieve a reasonable accuracy for RBF interpolation without the need to pinpoint a specific value for the shape parameter, which is the case for the original RBF interpolation.

]]>Algorithms doi: 10.3390/a13120346

Authors: Hao Jia Chen Guo Lina Zhao Zhao Xu

This work uses the sliding mode control method to conduct the finite-time synchronization of chaotic systems. The utilized parameter selection principle differs from conventional methods. The designed controller selects the unknown parameters independently from the system model. These parameters enable tracking and prediction of the additional variables that affect the chaotic motion but are difficult to measure. Consequently, the proposed approach avoids the limitations of selecting the unknown parameters that are challenging to measure or modeling the parameters solely within the relevant system. This paper proposes a novel nonsingular terminal sliding surface and demonstrates its finite-time convergence. Then, the adaptive law of unknown parameters is presented. Next, the adaptive sliding mode controller based on the finite-time control idea is proposed, and its finite-time convergence and stability are discussed. Finally, the paper presents numerical simulations of chaotic systems with either the same or different structures, thus verifying the proposed method&rsquo;s applicability and effectiveness.

]]>Algorithms doi: 10.3390/a13120345

Authors: Laith Abualigah Amir H. Gandomi Mohamed Abd Elaziz Abdelazim G. Hussien Ahmad M. Khasawneh Mohammad Alshinwan Essam H. Houssein

Text clustering is one of the efficient unsupervised learning techniques used to partition a huge number of text documents into a subset of clusters. In which, each cluster contains similar documents and the clusters contain dissimilar text documents. Nature-inspired optimization algorithms have been successfully used to solve various optimization problems, including text document clustering problems. In this paper, a comprehensive review is presented to show the most related nature-inspired algorithms that have been used in solving the text clustering problem. Moreover, comprehensive experiments are conducted and analyzed to show the performance of the common well-know nature-inspired optimization algorithms in solving the text document clustering problems including Harmony Search (HS) Algorithm, Genetic Algorithm (GA), Particle Swarm Optimization (PSO) Algorithm, Ant Colony Optimization (ACO), Krill Herd Algorithm (KHA), Cuckoo Search (CS) Algorithm, Gray Wolf Optimizer (GWO), and Bat-inspired Algorithm (BA). Seven text benchmark datasets are used to validate the performance of the tested algorithms. The results showed that the performance of the well-known nurture-inspired optimization algorithms almost the same with slight differences. For improvement purposes, new modified versions of the tested algorithms can be proposed and tested to tackle the text clustering problems.

]]>Algorithms doi: 10.3390/a13120344

Authors: Takeo Hagiwara Tatsuie Tsukiji

Langton&rsquo;s ant is a deterministic cellular automaton studied in many fields, artificial life, computational complexity, cryptography, emergent dynamics, Lorents lattice gas, and so forth, motivated by the hardness of predicting the ant&rsquo;s macroscopic behavior from an initial microscopic configuration. Gajardo, Moreira, and Goles (2002) proved that Langton&rsquo;s ant is PTIME -hard for reachability. On a twisted torus, we demonstrate that it is PSPACE hard to determine whether the ant will ever visit almost all vertices or nearly none of them.

]]>Algorithms doi: 10.3390/a13120343

Authors: Roxana-Elena Mihaescu Mihai Chindea Constantin Paleologu Serban Carata Marian Ghenescu

Solving the person re-identification problem involves making associations between the same person&rsquo;s appearances across disjoint camera views. Further, those associations have to be made on multiple surveillance cameras in order to obtain a more efficient and powerful re-identification system. The re-identification problem becomes particularly challenging in very crowded areas. This mainly happens for two reasons. First, the visibility is reduced and occlusions of people can occur. Further, due to congestion, as the number of possible matches increases, the re-identification is becoming challenging to achieve. Additional challenges consist of variations of lightning, poses, or viewpoints, and the existence of noise and blurring effects. In this paper, we aim to generalize person re-identification by implementing a first attempt of a general system, which is robust in terms of distribution variations. Our method is based on the YOLO (You Only Look Once) model, which represents a general object detection system. The novelty of the proposed re-identification method consists of using a simple detection model, with minimal additional costs, but with results that are comparable with those of the other existing dedicated methods.

]]>Algorithms doi: 10.3390/a13120342

Authors: Guojing Huang Qingliang Chen Congjian Deng

With the development of E-commerce, online advertising began to thrive and has gradually developed into a new mode of business, of which Click-Through Rates (CTR) prediction is the essential driving technology. Given a user, commodities and scenarios, the CTR model can predict the user&rsquo;s click probability of an online advertisement. Recently, great progress has been made with the introduction of Deep Neural Networks (DNN) into CTR. In order to further advance the DNN-based CTR prediction models, this paper introduces a new model of FO-FTRL-DCN, based on the prestigious model of Deep&amp;Cross Network (DCN) augmented with the latest optimization technique of Follow The Regularized Leader (FTRL) for DNN. The extensive comparative experiments on the iPinYou datasets show that the proposed model has outperformed other state-of-the-art baselines, with better generalization across different datasets in the benchmark.

]]>Algorithms doi: 10.3390/a13120341

Authors: Elias Koukoutsis Constantin Papaodysseus George Tsavdaridis Nikolaos V. Karadimas Athanasios Ballis Eirini Mamatsi Athanasios Rafail Mamatsis

Recently, very large-scale decision support systems (DSSs) have been developed, which tackle very complex problems, associated with very extensive and polymorphic information, which probably is geographically highly dispersed. The management, updating, modification and upgrading of the data and program core of such an information system is, as a rule, a very difficult task, which encompasses many hazards and risks. The purpose of the present work was (a) to list the more significant of these hazards and risks and (b) to introduce a new general methodology for designing decision support (DS) systems that are robust and circumvent these risks. The core of this new approach was the introduction of a meta-database, called teleological, on the base of which management, updating, modification, reduction, growth and upgrading of the system may be safely and efficiently achieved. The very same teleological meta-database can be used for the construction of a sound decision support system, incorporating elements of a previous one at a future stage.

]]>Algorithms doi: 10.3390/a13120340

Authors: Gianpaolo Ghiani Tommaso Adamo Pierpaolo Greco Emanuela Guerriero

In recent years, there have been several attempts to use machine learning techniques to improve the performance of exact and approximate optimization algorithms. Along this line of research, the present paper shows how supervised and unsupervised techniques can be used to improve the quality of the solutions generated by a heuristic for the Time-Dependent Travelling Salesman Problem with no increased computing time. This can be useful in a real-time setting where a speed update (or the arrival of a new customer request) may lead to the reoptimization of the planned route. The main contribution of this work is to show how to reuse the information gained in those settings in which instances with similar features have to be solved over and over again, as it is customary in distribution management. We use a method based on the nearest neighbor procedure (supervised learning) and the K-means algorithm with the Euclidean distance (unsupervised learning). In order to show the effectiveness of this approach, the computational experiments have been carried out for the dataset generated based on the real travel time functions of two European cities: Paris and London. The overall average improvement of our heuristic over the classical nearest neighbor procedure is about 5% for London, and about 4% for Paris.

]]>Algorithms doi: 10.3390/a13120339

Authors: Jonathan Li Rohan Potru Farhad Shahrokhi

We implement and test the performances of several approximation algorithms for computing the minimum dominating set of a graph. These algorithms are the standard greedy algorithm, the recent Linear programming (LP) rounding algorithms and a hybrid algorithm that we design by combining the greedy and LP rounding algorithms. Over the range of test data, all algorithms perform better than anticipated in theory, and have small performance ratios, measured as the size of output divided by the LP objective lower bound. However, each have advantages over the others. For instance, LP rounding algorithm normally outperforms the other algorithms on sparse real-world graphs. On a graph with 400,000+ vertices, LP rounding took less than 15 s of CPU time to generate a solution with performance ratio 1.011, while the greedy and hybrid algorithms generated solutions of performance ratio 1.12 in similar time. For synthetic graphs, the hybrid algorithm normally outperforms the others, whereas for hypercubes and k-Queens graphs, greedy outperforms the rest. Another advantage of the hybrid algorithm is to solve very large problems that are suitable for application of LP rounding (sparse graphs) but LP formulations become formidable in practice and LP solvers crash, as we observed on a real-world graph with 7.7 million+ vertices and a planar graph on 1,000,000 vertices.

]]>Algorithms doi: 10.3390/a13120338

Authors: Ting Huang Zhengping Weng Gang Liu Zhenwen He

To manage multidimensional point data more efficiently, this paper presents an improvement, called HD-tree, of a previous indexing method, called D-tree. Both structures combine quadtree-like partitioning (using integer shift operations without storing internal nodes, but only leaves) and hash tables (for searching for the nodes stored). However, the HD-tree follows a brand-new decomposition strategy, which is called half decomposition strategy. This improvement avoids the generation of nodes containing only a small amount of data and the sequential search of the hash table, so that it can save storage space while having faster I/O and better time performance when building the tree and querying data. The results demonstrate convincingly that the time and space performance of HD-tree is better than that of D-tree regardless of uniform or uneven data, which are less affected by data distribution.

]]>Algorithms doi: 10.3390/a13120337

Authors: Mathias Kühn Michael Völker Thorsten Schmidt

Project Planning and Control (PPC) problems with stochastic job processing times belong to the problem class of Stochastic Resource-Constrained Multi-Project Scheduling Problems (SRCMPSP). A practical example of this problem class is the industrial domain of customer-specific assembly of complex products. PPC approaches have to compensate stochastic influences and achieve high objective fulfillment. This paper presents an efficient simulation-based optimization approach to generate Combined Priority Rules (CPRs) for determining the next job in short-term production control. The objective is to minimize project-specific objectives such as average and standard deviation of project delay or makespan. For this, we generate project-specific CPRs and evaluate the results with the Pareto dominance concept. However, generating CPRs considering stochastic influences is computationally intensive. To tackle this problem, we developed a 2-phase algorithm by first learning the algorithm with deterministic data and by generating promising starting solutions for the more computationally intensive stochastic phase. Since a good deterministic solution does not always lead to a good stochastic solution, we introduced the parameter Initial Copy Rate (ICR) to generate an initial population of copied and randomized individuals. Evaluating this approach, we conducted various computer-based experiments. Compared to Standard Priority Rules (SPRs) used in practice, the approach shows a higher objective fulfilment. The 2-phase algorithm can reduce the computation effort and increases the efficiency of generating CPRs.

]]>Algorithms doi: 10.3390/a13120336

Authors: Guo Qiu He

Evaluation of agricultural investment climate has essential reference value for site selection, operation and risk management of agricultural outward foreign direct investment projects. This study builds a back propagation neural network-based agricultural investment climate evaluation model, which has 22 indicators of four subsystems that take political climate, economic climate, social climate, and technological climate as the input vector, and agricultural investment climate rating as the output vector, to evaluate the agricultural investment climate in 16 Central and Eastern European (CEE) countries. The overall spatial distribution characteristics demonstrate that the best agricultural investment climate is in the three Baltic countries, followed by the Visegrad Group and Slovenia sector, and then the Balkan littoral countries. The findings may provide insights for entrepreneurs who aim to invest in agriculture abroad and contribute to the improvement of these countries&rsquo; investment climate.

]]>Algorithms doi: 10.3390/a13120334

Authors: Joshua Vendrow Jamie Haddock Deanna Needell Lorraine Johnson

Lyme disease is a rapidly growing illness that remains poorly understood within the medical community. Critical questions about when and why patients respond to treatment or stay ill, what kinds of treatments are effective, and even how to properly diagnose the disease remain largely unanswered. We investigate these questions by applying machine learning techniques to a large scale Lyme disease patient registry, MyLymeData, developed by the nonprofit LymeDisease.org. We apply various machine learning methods in order to measure the effect of individual features in predicting participants&rsquo; answers to the Global Rating of Change (GROC) survey questions that assess the self-reported degree to which their condition improved, worsened, or remained unchanged following antibiotic treatment. We use basic linear regression, support vector machines, neural networks, entropy-based decision tree models, and k-nearest neighbors approaches. We first analyze the general performance of the model and then identify the most important features for predicting participant answers to GROC. After we identify the &ldquo;key&rdquo; features, we separate them from the dataset and demonstrate the effectiveness of these features at identifying GROC. In doing so, we highlight possible directions for future study both mathematically and clinically.

]]>Algorithms doi: 10.3390/a13120335

Authors: Lida Kanari Adélie Garin Kathryn Hess

Methods of topological data analysis have been successfully applied in a wide range of fields to provide useful summaries of the structure of complex data sets in terms of topological descriptors, such as persistence diagrams. While there are many powerful techniques for computing topological descriptors, the inverse problem, i.e., recovering the input data from topological descriptors, has proved to be challenging. In this article, we study in detail the Topological Morphology Descriptor (TMD), which assigns a persistence diagram to any tree embedded in Euclidean space, and a sort of stochastic inverse to the TMD, the Topological Neuron Synthesis (TNS) algorithm, gaining both theoretical and computational insights into the relation between the two. We propose a new approach to classify barcodes using symmetric groups, which provides a concrete language to formulate our results. We investigate to what extent the TNS recovers a geometric tree from its TMD and describe the effect of different types of noise on the process of tree generation from persistence diagrams. We prove moreover that the TNS algorithm is stable with respect to specific types of noise.

]]>Algorithms doi: 10.3390/a13120333

Authors: Raúl de Celis Pablo Solano Luis Cadarso

The Guidance, Navigation and Control (GNC) of air and space vehicles has been one of the spearheads of research in the aerospace field in recent times. Using Global Navigation Satellite Systems (GNSS) and inertial navigation systems, accuracy may be detached from range. However, these sensor-based GNC systems may cause significant errors in determining attitude and position. These effects can be ameliorated using additional sensors, independent of cumulative errors. The quadrant photodetector semiactive laser is a good candidate for such a purpose. However, GNC systems&rsquo; development and construction costs are high. Reducing costs, while maintaining safety and accuracy standards, is key for development in aerospace engineering. Advanced algorithms for getting such standards while eliminating sensors are cornerstone. The development and application of machine learning techniques to GNC poses an innovative path for reducing complexity and costs. Here, a new nonlinear hybridization algorithm, which is based on neural networks, to estimate the gravity vector is presented. Using a neural network means that once it is trained, the physical-mathematical foundations of flight are not relevant; it is the network that returns dynamics to be fed to the GNC algorithm. The gravity vector, which can be accurately predicted, is used to determine vehicle attitude without calling for gyroscopes. Nonlinear simulations based on real flight dynamics are used to train the neural networks. Then, the approach is tested and simulated together with a GNC system. Monte Carlo analysis is conducted to determine performance when uncertainty arises. Simulation results prove that the performance of the presented approach is robust and precise in a six-degree-of-freedom simulation environment.

]]>Algorithms doi: 10.3390/a13120332

Authors: Sai Prashanth Josyula Johanna Törnquist Krasemann Lars Lundberg

In railway traffic systems, whenever disturbances occur, it is important to effectively reschedule trains while optimizing the goals of various stakeholders. Algorithms can provide significant benefits to support the traffic controllers in train rescheduling, if well integrated into the overall traffic management process. In the railway research literature, many algorithms are proposed to tackle different versions of the train rescheduling problem. However, limited research has been performed to assess the capabilities and performance of alternative approaches, with the purpose of identifying their main strengths and weaknesses. Evaluation of train rescheduling algorithms enables practitioners and decision support systems to select a suitable algorithm based on the properties of the type of disturbance scenario in focus. It also guides researchers and algorithm designers in improving the algorithms. In this paper, we (1) propose an evaluation framework for train rescheduling algorithms, (2) present two train rescheduling algorithms: a heuristic and a MILP-based exact algorithm, and (3) conduct an experiment to compare the two multi-objective algorithms using the proposed framework (a proof-of-concept). It is found that the heuristic algorithm is suitable for solving simpler disturbance scenarios since it is quick in producing decent solutions. For complex disturbances wherein multiple trains experience a primary delay due to an infrastructure failure, the exact algorithm is found to be more appropriate.

]]>Algorithms doi: 10.3390/a13120331

Authors: Joseph Gesnouin Steve Pechberti Guillaume Bresson Bogdan Stanciulescu Fabien Moutarde

Understanding the behaviors and intentions of humans is still one of the main challenges for vehicle autonomy. More specifically, inferring the intentions and actions of vulnerable actors, namely pedestrians, in complex situations such as urban traffic scenes remains a difficult task and a blocking point towards more automated vehicles. Answering the question &ldquo;Is the pedestrian going to cross?&rdquo; is a good starting point in order to advance in the quest to the fifth level of autonomous driving. In this paper, we address the problem of real-time discrete intention prediction of pedestrians in urban traffic environments by linking the dynamics of a pedestrian&rsquo;s skeleton to an intention. Hence, we propose SPI-Net (Skeleton-based Pedestrian Intention network): a representation-focused multi-branch network combining features from 2D pedestrian body poses for the prediction of pedestrians&rsquo; discrete intentions. Experimental results show that SPI-Net achieved 94.4% accuracy in pedestrian crossing prediction on the JAAD data set while being efficient for real-time scenarios since SPI-Net can reach around one inference every 0.25 ms on one GPU (i.e., RTX 2080ti), or every 0.67 ms on one CPU (i.e., Intel Core i7 8700K).

]]>Algorithms doi: 10.3390/a13120330

Authors: Mohamed Ismail Milica Orlandić

Hyperspectral image classification has been increasingly used in the field of remote sensing. In this study, a new clustering framework for large-scale hyperspectral image (HSI) classification is proposed. The proposed four-step classification scheme explores how to effectively use the global spectral information and local spatial structure of hyperspectral data for HSI classification. Initially, multidimensional Watershed is used for pre-segmentation. Region-based hierarchical hyperspectral image segmentation is based on the construction of Binary partition trees (BPT). Each segmented region is modeled while using first-order parametric modelling, which is then followed by a region merging stage using HSI regional spectral properties in order to obtain a BPT representation. The tree is then pruned to obtain a more compact representation. In addition, principal component analysis (PCA) is utilized for HSI feature extraction, so that the extracted features are further incorporated into the BPT. Finally, an efficient variant of k-means clustering algorithm, called filtering algorithm, is deployed on the created BPT structure, producing the final cluster map. The proposed method is tested over eight publicly available hyperspectral scenes with ground truth data and it is further compared with other clustering frameworks. The extensive experimental analysis demonstrates the efficacy of the proposed method.

]]>