Search

We study the quadratic cycle cover problem (QCCP), which aims to find a node-disjoint cycle cover in a directed graph with minimum interaction cost between successive arcs. We derive several semidefinite programming (SDP) relaxations and use facial reduction to make these strictly feasible. We investigate a nontrivial relationship between the transformation matrix used in the reduction and the structure of the graph, which is exploited in an efficient algorithm that constructs this matrix for any instance of the problem. To solve our relaxations, we propose an algorithm that incorporates an augmented Lagrangian method into a cutting-plane framework by utilizing Dykstra's projection algorithm. Our algorithm is suitable for solving SDP relaxations with a large number of cutting-planes. Computational results show that our SDP bounds and efficient cutting-plane algorithm outperform other QCCP bounding approaches from the literature. Finally, we provide several SDP-based upper bounding techniques, among which is a sequential Q-learning method that exploits a solution of our SDP relaxation within a reinforcement learning environment. Summary of Contribution: The quadratic cycle cover problem (QCCP) is the problem of finding a set of node-disjoint cycles covering all the nodes in a graph such that the total interaction cost between successive arcs is minimized. The QCCP has applications in many fields, among which are robotics, transportation, energy distribution networks, and automatic inspection. Besides this, the problem has a high theoretical relevance because of its close connection to the quadratic traveling salesman problem (QTSP). The QTSP has several applications, for example, in bioinformatics, and is considered to be among the most difficult combinatorial optimization problems nowadays. After removing the subtour elimination constraints, the QTSP boils down to the QCCP. Hence, an in-depth study of the QCCP also contributes to the construction of strong bounds for the QTSP. In this paper, we study the application of semidefinite programming (SDP) to obtain strong bounds for the QCCP. Our strongest SDP relaxation is very hard to solve by any SDP solver because of the large number of involved cutting-planes. Because of that, we propose a new approach in which an augmented Lagrangian method is incorporated into a cutting-plane framework by utilizing Dykstra's projection algorithm. We emphasize an efficient implementation of the method and perform an extensive computational study. This study shows that our method is able to handle a large number of cuts and that the resulting bounds are currently the best QCCP bounds in the literature. We also introduce several upper bounding techniques, among which is a distributed reinforcement learning algorithm that exploits our SDP relaxations. [ABSTRACT FROM AUTHOR]

The problem of finding optimal block designs can be formulated as a combinatorial optimization, but its resolution is still a formidable challenge. This paper presents a general and user-friendly algorithm, namely Modified Particle Swarm Optimization (MPSO), to construct optimal or near-optimal block designs. It can be used for several classes of block designs such as binary, non-binary and test-control block designs with correlated or uncorrelated observations. In order to evaluate the algorithm, we compare our results with the optimal designs presented in some published papers. An advantage of our algorithm is its independency to the sizes of blocks and the structure of correlations. [ABSTRACT FROM AUTHOR]

The quantum alternating operator ansatz (QAOA) and its predecessor, the quantum approximate optimization algorithm, are one of the most widely used quantum algorithms for solving combinatorial optimization problems. However, as there is yet no rigorous proof of convergence for the QAOA, we provide one in this paper. The proof involves retracing the connection between the quantum adiabatic algorithm and the QAOA, and naturally suggests a refined definition of the 'phase separator' and 'mixer' keywords. [ABSTRACT FROM AUTHOR]

In real-world applications, feature selection is crucial for enhancing the performance of data science and machine learning models. Typically, feature selection is a complex combinatorial optimization problem and a multi-objective optimization problem. Its primary goals are to reduce the dimensionality of the dataset and enhance the performance of machine learning algorithms. The selection of features in high-dimensional datasets is challenging due to the intricate relationships between features, which pose significant challenges to the performance and computational efficiency of algorithms. This paper introduces a Knowledge-Guided Competitive Co-Evolutionary Algorithm (KCCEA) for feature selection, especially for high-dimensional features. In the proposed algorithm, we make improvements to the foundational dominance-based multi-objective evolutionary algorithm in two aspects. First, the use of feature correlation as knowledge to guide evolution enhances the search speed and quality of traditional multi-objective evolutionary algorithm solutions. Second, a dynamically allocated competitive–cooperative evolutionary mechanism is proposed, integrating the improved knowledge-guided evolution with traditional evolutionary algorithms, further enhancing the search efficiency and diversity of solutions. Through rigorous empirical testing on various datasets, the KCCEA demonstrates superior performance compared to basic multi-objective evolutionary algorithms, providing effective solutions to multi-objective feature selection problems while enhancing the interpretability and effectiveness of prediction models. [ABSTRACT FROM AUTHOR]

In this paper, we study the knapsack problem with conflict pair constraints. After a thorough literature survey on the topic, our study focuses on the special case of bipartite conflict graphs. For complete bipartite (multipartite) conflict graphs, the problem is shown to be NP-hard but solvable in pseudo-polynomial time, and it admits an FPTAS. Extensions of these results to more general classes of graphs are also presented. Further, a class of integer programming models for the general knapsack problem with conflict pair constraints is presented, which generalizes and unifies the existing formulations. The strength of the LP relaxations of these formulations is analyzed, and we discuss different ways to tighten them. Experimental comparisons of these models are also presented to assess their relative strengths. This analysis disclosed various strong and weak points of different formulations of the problem and their relationships to different types of problem data. This information can be used in designing special purpose algorithms for KPCC involving a learning component. [ABSTRACT FROM AUTHOR]

As a classical combinatorial optimization problem, the traveling salesman problem (TSP) has been extensively investigated in the fields of Artificial Intelligence and Operations Research. Due to being NP-complete, it is still rather challenging to solve both effectively and efficiently. Because of its high theoretical significance and wide practical applications, great effort has been undertaken to solve it from the point of view of intelligent search. In this paper, we propose a two-stage probe-based search optimization algorithm for solving both symmetric and asymmetric TSPs through the stages of route development and a self-escape mechanism. Specifically, in the first stage, a reasonable proportion threshold filter of potential basis probes or partial routes is set up at each step during the complete route development process. In this way, the poor basis probes with longer routes are filtered out automatically. Moreover, four local augmentation operators are further employed to improve these potential basis probes at each step. In the second stage, a self-escape mechanism or operation is further implemented on the obtained complete routes to prevent the probe-based search from being trapped in a locally optimal solution. The experimental results on a collection of benchmark TSP datasets demonstrate that our proposed algorithm is more effective than other state-of-the-art optimization algorithms. In fact, it achieves the best-known TSP benchmark solutions in many datasets, while, in certain cases, it even generates solutions that are better than the best-known TSP benchmark solutions. [ABSTRACT FROM AUTHOR]

Heterogeneous architecture-based systems-on-chip enable the development of flexible and powerful multifunctional RF systems. In complex and dynamic environments where applications arrive continuously and stochastically, real-time scheduling of multiple applications to appropriate processor resources is crucial for fully utilizing the heterogeneous SoC's resource potential. However, heterogeneous resource-scheduling algorithms still face many problems in practical situations, including generalized abstraction of applications and heterogeneous resources, resource allocation, efficient scheduling of multiple applications in complex mission scenarios, and how to ensure the effectiveness combining with real-world applications of scheduling algorithms. Therefore, in this paper, we design the Multi-Application Scheduling Algorithm, named MASA, which is a two-phase scheduler architecture based on Deep Reinforcement Learning. The algorithm is made up of neural network scheduler-based task prioritization for dynamic encoding of applications and heuristic scheduler-based task mapping for solving the processor resource allocation problem. In order to achieve stable and fast training of the network scheduler based on the actor–critic strategy, we propose optimization methods for the training of MASA: reward dynamic alignment (RDA), earlier termination of the initial episodes, and asynchronous multi-agent training. The performance of the MASA is tested with classic directed acyclic graph and six real-world application datasets, respectively. Experimental results show that MASA outperforms other neural scheduling algorithms and heuristics, and ablation experiments illustrate how these training optimizations improve the network's capacity. [ABSTRACT FROM AUTHOR]

The ant system (AS) and scheduling problem are well-known concepts in literature. Ant algorithms have been known to be an effective tool for solving combinatorial optimization problems. Elitist AS (EAS), rank-based AS (RAS), ant colony system (ACS), and max-min AS (MMAS) are the variants of the AS algorithm; they are triggered by the different ways of updating the pheromone trail τ, computing the visibility η, and/or other parameters in the basic AS model. The main contribution of this article is twofold. First, the basic AS and its controlled parameters are presented, the key variants of the ant algorithms are explained, and major changes of each variant from the basic model are tracked. Second, sixty papers are collected between 2015 and 2020 based on a search strategy for tracking the implementation of different AS variants in solving scheduling problems. Numerous findings based on a statistical analysis of the collected papers are reported and discussed. This study will allow the researcher to understand the essence of the ant algorithm, recognize the fundamental differences in its five systems, and determine how each of them can be implemented. Tracking a sample of articles that apply an ant algorithm for a specific case study gives researchers new ideas on how to adjust the original model to fit their problem. [ABSTRACT FROM AUTHOR]

The introduction of 5G technologies has enabled the possibility of designing and building several new classes of networked information systems that were previously impossible to implement due to limitations on data throughput or the reliability of transmission channels. Among them, one of the most interesting and successful examples with a highly positive impact in terms of the quality of urban environments and societal and economical welfare is a system of semi-autonomous connected vehicles, where IoT devices, data centers, and fleets of smart vehicles equipped with communication and computational resources are combined into a heterogeneous and distributed infrastructure, unifying hardware, networks, and software. In order to efficiently provide various services (e.g., patrolling, pickup and delivery, monitoring), these systems typically rely on collecting and broadcasting large amounts of data (e.g., sensor data, GPS traces, or maps), which need to be properly collected and processed in a timely manner. As is well documented in the literature, one of the most effective ways to achieve this purpose, especially in a real-time context, is to adopt a graph model of the data (e.g., to model communication networks, roads, or interactions between vehicles) and to employ suitable graph algorithms to solve properly defined computational problems of interest (e.g., shortest paths or distributed consensus). While research in this context has been extensive from a theoretical perspective, works that have focused on the implementation, deployment, and evaluation of the practical performance of graph algorithms for real-world systems of autonomous vehicles have been much rarer. In this paper, we present a study of this kind. Specifically, we first describe the main features of a real-world information system employing semi-autonomous connected vehicles that is currently being tested in the city of L'Aquila (Italy). Then, we present an overview of the computational challenges arising in the considered application domain and provide a systematic survey of known algorithmic results for one of the most relevant classes of computational problems that have to be addressed in said domain, namely, pickup and delivery problems. Finally, we discuss implementation issues, adopted software tools, and the deployment and testing phases concerning one of the algorithmic components of the mentioned real-world system dedicated to handling a specific problem of the above class, namely, the pickup and delivery multi-vehicle problem with time windows. [ABSTRACT FROM AUTHOR]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

This paper introduces a new variant of the Bees Algorithm (BA) called Bees Algorithm with 2-parameter (BA2), which is a population-based metaheuristic algorithm designed to solve continuous and combinatorial optimisation problems. The proposed algorithm simplified the BA's parameters by combining exploration and exploitation strategies while preserving the algorithm's core principles to efficiently search for optimal solutions. The paper provides a detailed description of the algorithm's core principles and its application to two engineering problems, the air-cooling system design (ACSD) and the printed circuit board assembly sequence optimisation (PASO). The results show that BA2 outperforms previous versions of the basic BA in terms of convergence speed and solution quality. However, the authors acknowledge that further research is needed to test the scalability and generalisability of the algorithm to larger and more diverse optimisation problems. Overall, this paper provides valuable insights into the potential of metaheuristics for solving real-world optimisation problems. [ABSTRACT FROM AUTHOR]

Outlier detection is of great significance in the domain of data mining. Its task is to find those target points that are not identical to most of the object generation mechanisms. The existing algorithms are mainly divided into density-based algorithms and distance-based algorithms. However, both approaches have some drawbacks. The former struggles to handle low-density modes, while the latter cannot detect local outliers. Moreover, the outlier detection algorithm is very sensitive to parameter settings. This paper proposes a new two-parameter outlier detection (TPOD) algorithm. The method proposed in this paper does not need to manually define the number of neighbors, and the introduction of relative distance can also solve the problem of low density and further accurately detect outliers. This is a combinatorial optimization problem. Firstly, the number of natural neighbors is iteratively calculated, and then the local density of the target object is calculated by adaptive kernel density estimation. Secondly, the relative distance of the target points is computed through natural neighbors. Finally, these two parameters are combined to obtain the outlier factor. This eliminates the influence of parameters that require users to determine the number of outliers themselves, namely, the top-n effect. Two synthetic datasets and 17 real datasets were used to test the effectiveness of this method; a comparison with another five algorithms is also provided. The AUC value and F1 score on multiple datasets are higher than other algorithms, indicating that outliers can be found accurately, which proves that the algorithm is effective. [ABSTRACT FROM AUTHOR]

In this paper, we focus on Hitting-Set , a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity , we estimate the number of queries to the oracle based on the parameter k , the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized d -partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al. (SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A 1 , ... , A d of vertices in H and answers whether there is a hyperedge in H that intersects each set A i , where i ∈ { 1 , 2 , ... , d }. For d = 2 , the GPIS oracle is nothing but BIS oracle. We show that d - Hitting-Set , the hitting set problem for d -uniform hypergraphs, can be solved using O ˜ d (k d log ⁡ n) GPIS queries. Additionally, we also showed that d - Decision-Hitting-Set , the decision version of d - Hitting-Set can be solved with O ˜ d (min ⁡ { k d log ⁡ n , k 2 d 2 }) GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d - Decision-Hitting-Set requires Ω (( k + d d )) GPIS queries. [ABSTRACT FROM AUTHOR]

This paper investigates the use of Oracle PL/SQL and Genetic Algorithms for performing bulk resource scheduling tasks. To achieve this current theory and information from literature were examined, in order to select a suitable set of methods and algorithms. The findings of this paper are that PL/SQL and Genetic Algorithms when combined with knowledge bases provides an acceptable level of accuracy and speed when scheduling multiple of constrained resources. [ABSTRACT FROM AUTHOR]

In this paper, we have done a rapid and very simple algorithm that resolves the multiple objective combinatorial optimization problem. This, by determining a basic optimal solution, which is a strong spanning tree constructed, according to a well-chosen criterion. Consequently, our algorithm uses notions of Bellman's algorithm to determine the best path of the network, and Ford Fulkerson's algorithm to maximise the flow value. The Simplex Network Method that permits to reach the optimality conditions manipulates the two algorithms. In short, the interest of our work is the optimization of many criteria taking into account the strong spanning tree, which represents the central angular stone of the network. To illustrate that, we propose to optimize a bi-objective distribution problem. [ABSTRACT FROM AUTHOR]

The unit commitment problem (UCP), which includes the unit schedule and power dispatch, is a nonlinear high-dimensional and highly constrained mixed-integer combinatorial optimization problem. One challenge herein is to obtain high-quality solutions considering various constraints. Developing a competitive hybrid method is a mainstream study goal in this field, which has focused on the unit schedule optimization but less on power dispatch. Inspired by the advantage of genetic algorithms (GAs) in solving combinational optimization problems and the characteristic of grey prediction evolution algorithm (GPE) with strong exploration ability, this paper proposes a novel hybrid GA and GPE method, termed hGAGPE, to solve the UCP. In hGAGPE, GPE, as a novel real parameter stochastic search algorithm based on the grey prediction theory for data mining, is first employed to solve the power dispatch of the UCP. Meanwhile, the unit schedule is performed by the popular GA. Additionally, some heuristic repair mechanisms based on the priority list and an elite selection mechanism are incorporated to enhance the performance of hGAGPE. The proposed hGAGPE is evaluated on six test systems with generating units in the range of 10 to 100 during a 24-h scheduling period. The numerical results demonstrate the feasibility and effectiveness of hGAGPE in comparison with other existing approaches. [ABSTRACT FROM AUTHOR]

Recently, graph neural network (GNN)-based algorithms were proposed to solve a variety of combinatorial optimization problems [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber, Nat. Mach. Intell. 4, 367-377 (2022)].GNNwas tested in particular on randomly generated instances of these problems. The publication [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber, Nat. Mach. Intell. 4, 367-377 (2022)] stirred a debate whether the GNN-based method was adequately benchmarked against best prior methods. In particular, critical commentaries [M. C. Angelini, F. Ricci-Tersenghi, Nat. Mach. Intell. 5, 29-31 (2023)] and [S. Boettcher, Nat. Mach. Intell. 5, 24-25 (2023)] point out that a simple greedy algorithm performs better than the GNN. We do not intend to discuss the merits of arguments and counterarguments in these papers. Rather, in this note, we establish a fundamental limitation for running GNN on random instances considered in these references, for a broad range of choices of GNN architecture. Specifically, these barriers hold when the depth of GNN does not scale with graph size (we note that depth 2 was used in experiments in [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber, Nat. Mach. Intell. 4, 367-377 (2022)]), and importantly, these barriers hold regardless of any other parameters of GNN architecture. These limitations arise from the presence of the overlap gap property (OGP) phase transition, which is a barrier for many algorithms, including importantly local algorithms, of which GNN is an example. At the same time, some algorithms known prior to the introduction of GNN provide best results for these problems up to the OGP phase transition. This leaves very little space for GNN to outperform the known algorithms, and based on this, we side with the conclusions made in [M. C. Angelini, F. Ricci-Tersenghi, Nat. Mach. Intell. 5, 29-31 (2023)] and [S. Boettcher, Nat. Mach. Intell. 5, 24-25 (2023)]. [ABSTRACT FROM AUTHOR]

The two-dimension strip packing problem (2DSPP) is an NP-hard combinatorial optimization problem, and it has a wide range of applications. The order in which the rectangles are placed in the strip is the key to solving the 2DSPP. In this paper, the corner increment multi-level scoring strategy and the two-step selection strategy are proposed to make the selection of rectangles more reasonable. The hierarchical construction strategy is used to improve the constructive heuristic algorithm to expand the search space of the rectangle selection. Based on this, this paper proposes a multi-strategy rectangle selection algorithm TSMSA for solving 2DSPP. Comparing experiments with 7 excellent algorithms for solving 2DSPP on 737 instances of the benchmark dataset shows that the instance number of the optimal solution obtained by TSMSA is 1.05~2.9 times that of the other 7 algorithms. [ABSTRACT FROM AUTHOR]

The maximum internal spanning tree (MIST) problem is to find a spanning tree with maximum number of internal node for an undirected graph. It is a variation of the well-known minimum spanning tree problem and is NP-hard. Evolutionary algorithms (EAs) have been successfully applied to solve many NP-hard combinatorial optimization problems in numerical empirical studies. However, researchers know little about their performance guarantees from theory aspect. This paper designs a valid fitness function to guide the well-studied evolutionary algorithm, (1 + 1) EA , to optimize the MIST problem, and presents theoretical analysis to show that it can obtain a performance guarantee of 2 and 5/3 in expected runtime O (n m 2) and O (n m 4) , respectively. Moreover, this paper proves that the (1+1) EA can achieve a performance guarantee of 3 for a variation of the MIST problem, where each vertex is associated with a weight. In addition, comparison analyses on two family instance graphs are presented to show that (1 + 1) EA is better than two local search algorithms. This theoretical study provides insight into the process of (1 + 1) EA constructing a performance guarantee solution for the MIST problem. [ABSTRACT FROM AUTHOR]

Online social networks have become major battlegrounds for political campaigns, viral marketing, and the dissemination of news. As a consequence, “bad actors” are increasingly exploiting these platforms, which is a key challenge for their administrators, businesses and society in general. The spread of fake news is a classical example of the abuse of social networks by these bad actors. While some have advocated for stricter policies to control the spread of misinformation in social networks, this often happens in detriment of their democratic and organic structure. In this paper, we aim to limit the influence of a target group in a social network via the removal of a few users/links. We formulate the influence limitation problem in a data-driven fashion, by taking into account past propagation traces. More specifically, our algorithms find critical edges to be removed in order to decrease the influence of a target group based on past data. The idea is to control the diffusion processes while minimizing the amount of disturbance in the network structure. Moreover, we consider two types of constraints over edge removals, a budget constraint and also a, more general, set of matroid constraints. These problems lead to interesting challenges in terms of algorithm design. For instance, we are able to show that influence limitation is APX-hard and propose deterministic and probabilistic approximation algorithms for the budgeted and the matroid version of the problem, respectively. Experiments show that the proposed approaches outperform several baselines. [ABSTRACT FROM AUTHOR]

Fog radio access network (Fog-RAN), which pushes caching and computing capabilities to the network edge, is capable of efficiently delivering content to users by using carefully designed caching placement and content replacement algorithms. In this paper, the transmission scheme design and coding parameter optimization will be considered for coded caching in Fog-RAN, where the reliability of content delivery, i.e., content outage probability, is used as the performance metric. The problem will be formulated as a complicated multi-objective probabilistic combinatorial optimization. A novel maximum $b$ -matching approach will then be proposed to obtain the Pareto optimal solution with fairness constraint. Based on the fast message passing approach, a distributed algorithm with a low memory usage of $O(M+N)$ is also proposed, where $M$ is the number of users and $N$ is the number of fog access points (Fog-APs). Although it is usually very difficult to derive the closed-form formulas for the optimal solution, the approximation formulas of the content outage probability will also be obtained as a function of coding parameters. The asymptotic optimal coding parameters can then be obtained by defining and deriving the outage exponent region and diversity-multiplexing region. Simulation results will illustrate the accuracy of the theoretical derivations, and verify the outage performance of the proposed approach. Therefore, this paper not only proposes a practical distributed Fog-AP selection algorithm for coded caching but also provides a systematic way to evaluate and optimize the performance of Fog-RANs. [ABSTRACT FROM AUTHOR]

In the scenario of device-free localization under multiple effects, the accuracy of localization based on compressed sensing theory is severely affected. Most existing localization techniques directly ignore multiple path effects. However, it is not practical to ignore the multiple path effect due to its high signal strength, which can provide localization information. In this paper, we formulate the sensing matrix optimization problem in compressed sensing for device-free localization scenarios based on multiple reflections. To solve this problem, we model it as a constrained combinatorial optimization problem and propose a hybrid meta-heuristic algorithm. First, smart reflection surfaces and virtual node models are used to construct the desired communication links. Second, we iteratively improve the properties of the measurement matrix by using K-means clustering to obtain reasonable thresholds, and use a meta-heuristic algorithm to optimize the sensing matrix. Finally, the simulation results show that the proposed method efficiently optimizes the sensing matrix and achieves fast and high-precision localization while conserving communication resources. [ABSTRACT FROM AUTHOR]

Combinatorial metaheuristic optimization algorithms have newly become a remarkable domain for handling real-world and engineering design optimization problems. In this paper, the Whale Optimization Algorithm (WOA) and the Woodpecker Mating Algorithm (WMA) are combined as HWMWOA. WOA is an effective algorithm with the advantage of global searching ability, where the control parameters are very less. But WOA is more probable to get trapped in the local optimum points and miss diversity of population, therefore suffering from premature convergence. The fundamental goal of the HWMWOA algorithm is to overcome the drawbacks of WOA. This betterment includes three basic mechanisms. First, a modified position update equation of WMA by efficient exploration ability is embedded into HWMWOA. Second, a new self-regulation Cauchy mutation operator is allocated to the proposed hybrid method. Finally, an arithmetic spiral movement with a novel search guide pattern is used in the suggested HWMWOA algorithm. The efficiency of the suggested algorithm is appraised over 48 test functions, and the optimal outcomes are compared with 15 most popular and newest metaheuristic optimization algorithms. Moreover, the HWMWOA algorithm is applied for simultaneously optimizing the parameters of SVM (Support Vector Machine) and feature weighting to handle the data classification problem on several real-world datasets from the UCI database. The outcomes prove the superiority of the suggested hybrid algorithm compared to both WOA and WMA. In addition, the results represent that the HWMWOA algorithm outperforms other efficient techniques impressively. [ABSTRACT FROM AUTHOR]

In recent years, metaheuristic methods have shown remarkable efficacy in resolving complex combinatorial challenges across a broad spectrum of fields. Nevertheless, the escalating complexity of these problems necessitates the continuous development of innovative techniques to enhance the performance and reliability of these methods. This paper aims to contribute to this endeavor by examining the impact of solution initialization methods on the performance of a hybrid algorithm applied to the set union knapsack problem (SUKP). Three distinct solution initialization methods, random, greedy, and weighted, have been proposed and evaluated. These have been integrated within a sine cosine algorithm employing k-means as a binarization procedure. Through testing on medium- and large-sized SUKP instances, the study reveals that the solution initialization strategy influences the algorithm's performance, with the weighted method consistently outperforming the other two. Additionally, the obtained results were benchmarked against various metaheuristics that have previously solved SUKP, showing favorable performance in this comparison. [ABSTRACT FROM AUTHOR]

The use of optimal control theory for motion planning is a challenging task. Cell mapping offers a way to formulate combinatorial optimization problems, allowing the inclusion of complex cost functions as well as multi-objective optimization problems. This paper presents a suboptimal solution for a trajectory planning problem in a workspace with obstacles, for a differential drive mobile robot. This method relies on the use of any linearization technique that allows the regularization of the combinatorial optimization problem. We explore some classical problems in optimal control, i.e., distance, control effort, and navigation time), as well as the multi-objective optimization problem (MOP). We also performed a comparison with two classical path planning algorithms, namely A ∗ and R R T ∗ , to validate the proposed method when the multi-objective optimization problem includes distance in the cost function, achieving a compromise of less than 2 % for the worst-case scenario for our case study. [ABSTRACT FROM AUTHOR]

This paper focuses on developing an appropriate combinatorial optimization technique for solving the optimal sizing problem of hybrid ac–dc microgrids. A novel two-stage iterative approach is proposed. In the first stage, a meta-heuristic technique based on a tailor-made genetic algorithm is used to tackle the optimal sizing problem, while, in the second, a non-linear solver is deployed to solve the operational problem subject to the obtained design/investment decisions. The proposed approach, being able to capture technical characteristics such as voltage and frequency through a detailed power flow algorithm, provides accurate solutions and, therefore, can address operational challenges of microgrids. Its capability to additionally capture contingencies ensures that the proposed sizing solutions are suitable both during normal operation and transient states. Finally, the genetic algorithm provides convergence of the model with relative computational simplicity. The proposed model is applied to a generalizable microgrid comprising of ac and dc generators and loads, as well as various types of storage technologies in order to demonstrate the benefits. The load and natural resources data correspond to real data. [ABSTRACT FROM AUTHOR]

Many important problems in engineering management can be formulated as Resource Assignment Problem (RAP). The Workers Assignment Problem (WAP) is considered as a sub-class of RAP which aims to find an optimal assignment of workers to a number of tasks in order to optimize certain objectives. WAP is an NP-hard combinatorial optimization problem. Due to its importance, several algorithms have been developed to solve it. In this paper, it is considered that a manager is required to provide a training course to his workers in order to improve their level of skill or experience to have a sustainable competitive advantage in the industry. The training cost of each worker to perform a particular job is different. The WAP is to find the best assignment of workers to training courses such that the total training cost is minimized. Two metaheuristic optimizations named Whale Optimization Algorithm (WOA) and Flower Pollination Algorithm (FPA) are utilized to final the optimal solution that reduces the total cost. MATLAB Software is used to perform the simulation of the two proposed methods into WAP. The computational results for a set of randomly generated problems of various sizes show that the FPA is able to find good quality solutions. [ABSTRACT FROM AUTHOR]

For the past decades, practitioners and researchers have been fascinated by the job-shop scheduling problems (JSSP) and have proposed many pristine meta-heuristic algorithms to solve them. JSSP is an NP-hard problem and a combinatorial optimization problem. This paper proposes a highly efficient and superior performance strategy for the artificial algae algorithm (AAA) integrated with the differential evolution (DE), denoted AAADE, to solve JSSP. The new movement algae colonies using DE operators are introduced to the proposed hybrid artificial algae algorithm and DE (AAADE). To improve AAA's intensification ability, the movement using the DE mutation is implemented into the AAA. In the new hybrid method, the DE crossover can update its position based on both movements (helical and DE movements) to increase randomization. Two categories of problems verify the efficiency and validity of the proposed hybrid algorithm, AAADE, namely, CEC 2014 benchmark functions and different job-shop scheduling problems. The AAADE results are compared with other algorithms in the literature. Hence, comparisons numerical experiments validated and verified the quality of the proposed algorithm. Experimental results validate the effectiveness of the proposed hybrid method in producing excellent solutions that are promising and competitive to the state-of-the-art heuristic-based algorithms reported in the literature in most of the benchmark functions in CEC'14 and JSSP. [ABSTRACT FROM AUTHOR]

This paper studies a shuffled linear regression problem. As a variant of ordinary linear regression, it requires estimating not only the regression variable, but also permutational correspondences between the covariates and responses. While existing formulations require the underlying ground-truth correspondences to be an ideal bijection such that all pieces of data should match, such a requirement barely holds in real-world applications due to either missing data or outliers. In this work, we generalize the formulation of shuffled linear regression to a broader range of conditions where only a part of the data should correspond. To this end, the effective recovery condition and NP-hardness of the proposed formulation are also studied. Moreover, we present a simple yet effective algorithm for deriving the solution. Its global convergence property and convergence rate are also analyzed in detail. Distinct tasks validate the effectiveness of our proposed formulation and the solution method. [ABSTRACT FROM AUTHOR]

Multi-Objective Combinatorial Optimization(MOCO), which consists of several conflicting objectives to be optimized, finds an ever-increasing number of uses in many real-world applications. In past years, the research of MOCO mainly focuses on evolutionary algorithms. Recently, constraint-based methods come into the view and have been proved to be effective on MOCO problems. This paper builds on the previous works of constraint-based algorithm MCSEnumPD(AAAI-18) using path diversification method. Due to the inadequacy that the original method fails to prune the redundant search space effectively, this paper proposes the definition of infeasible path and develops a novel algorithm that exploits the properties of unsatisfiable cores, referred as CgPDMCS. The approach extends MCSEnumPD algorithm with a core-guided path diversification method, which avoids solving infeasible paths representing the supersets of the unsatisfiable cores. Experimental results show that the novel approach provides further performance gains over the previous constraint-based algorithms, especially for the instances tightly constrained. [ABSTRACT FROM AUTHOR]

Software Defined Networking (SDN) is the novel networking paradigm where decoupling of the control plane from the data plane has its inherent advantages. Controller Placement Problem (CPP) involves placing the optimal number of controllers at the appropriate locations while meeting prerequisites such as latency, load balancing, energy and computational time. To achieve scalability, deployment of multiple controllers on large-scale SDN is one of the key challenges. CPP can be addressed as a multi-objective combinatorial optimization problem whose solution is a trade-off between multiple optimization parameters. In this paper, a novel population-based meta-heuristic algorithm viz. Naked Mole-Rat (NMR) Algorithm has been proposed to optimize the location for controller placement based on Switch-Controller (SC), Controller-Controller (CC) latency while maintaining load balancing among the controllers. The ideas and mechanisms are illustrated using two publicly available standard topologies viz. Ernet and Savvis. The controller localization approach implemented with NMR algorithm has slightly a better result as compared with the Bat algorithm. [ABSTRACT FROM AUTHOR]

The Graph Coloring Problem is a well-known NP-hard problem. Over the years, numerous scholars have been pursuing efficient algorithms to obtain high-quality solutions. Nested Rollout Policy Adaptation (NRPA) is a Monte Carlo Tree Search algorithm for single-player games, and it has been proven effective and good in combinatorial optimization problems. In this paper, we use for the first time the NRPA algorithm combined with the destruction and reconstruction ideas of the Iterative Greedy algorithm to solve the Graph Coloring Problem. First, the basic principle of the NRPA algorithm is introduced. Then, NRPA is extended by using mixed sorting, destruction and reconstruction, and the Diversity-NRPA algorithm is proposed, which improves the diversity of the algorithm. Finally, Diversity-NRPA is applied to solve the Graph Coloring Problem by combining it with the knowledge of the graph theory field. We evaluate the performance of Diversity-NRPA on DIMACS, a well-known graph benchmark instance, and compare it with traditional graph coloring algorithms. The experimental results show that the Diversity-NRPA algorithm can achieve excellent performance in both solution quality and search efficiency in solving the Graph Coloring problem. [ABSTRACT FROM AUTHOR]

In many cities and regions, decision makers independently develop Train Operation Plan (TOP) for each line in the rail transit network, resulting in a lack of TOP Synchronization (TOPS). Considering the entire network as a whole, researchers have realized that synchronous optimization is of great significance. In this paper, we formulate two Mixed-Integer Linear Programming (MILP) models to optimize demand-driven TOP in the network. The former is an Asynchronous TOP Optimization (ATOPO) model, while the latter is a Synchronous TOP Optimization (STOPO) model. The bi-objective models simultaneously determine train frequency, train timetable, and rolling stock circulation under small-granularity passenger demand to minimize trains' total cost and passengers' total time. Then, we propose the Nondominated Sorting Coevolutionary Memetic Algorithm (NSCMA) to solve the combinatorial optimization problems. The hybrid heuristic algorithm incorporates Coevolutionary Memetic Algorithm (CMA) into Advanced and Adaptive Nondominated Sorting Genetic Algorithm II (AANSGA-II) to ameliorate the evolution process for elite individuals. On this basis, we study the case of Shenyang Metro to verify the models and the algorithm. The results demonstrate that the STOPO model is better than the ATOPO model in reducing trains' total cost and passengers' total time. In addition, NSCMA is better than AANSGA-II in obtaining elite individuals. [ABSTRACT FROM AUTHOR]

• The adaptive bulk search is a QUBO solver alternative to quantum annealing. • The cyclic-min algorithm is a SA-like algorithm without random number generation. • The bit permutated cyclic-min algorithm provides near-optimal solutions for QUBO. • Our scalable implementation attains linear improvement of the search rate. A wide range of combinatorial optimization problems can be reduced to the Ising model, and equivalently the quadratic unconstrained binary optimization (QUBO) problem. Thus, in recent years, researchers have proposed to solve QUBO on FPGAs, GPUs, and special-purpose processors. The adaptive bulk search (ABS) is a previously-proposed framework for solving QUBO in parallel on multiple GPUs. In the ABS, a CPU host performs a GA-based global search while GPUs asynchronously perform many local searches in parallel. An original ABS adopts a simple local search algorithm called a cyclic-min algorithm, which does not use pseudo random numbers. However, the lack of randomness may cause a potential drawback of restricted bit-flipping operations in a local search. To avoid this drawback, this paper proposes a cyclic-min algorithm with randomly-generated multiple bit permutations, which enables a more effective local search with random number generation in CPUs (not in GPUs). Furthermore, this paper introduces a scalable implementation of the ABS with MPI and OpenMP. Our experimental results on TSUBAME3.0 show that the solution quality improves and the throughput linearly increases as the number of GPUs increases; with 256 GPUs, it evaluates 20.1 × 10 12 solutions per second. [ABSTRACT FROM AUTHOR]

The Fixed Set Search (FSS) is a novel metaheuristic that adds a learning mechanism to the Greedy Randomized Adaptive Search Procedure (GRASP). In recent publications, its efficiency has been shown on different types of combinatorial optimization problems like routing, machine scheduling and covering. In this paper the FSS is adapted to multi-objective problems for finding Pareto Front approximations. This adaptation is illustrated for the bi-objective Minimum Weighted Vertex Cover Problem (MWVCP). In this work, a simple and effective bi-objective GRASP algorithm for the MWVCP is developed in the first stage. One important characteristic of the proposed GRASP is that it avoids the use of weighted sums of objective functions in the local search and the greedy algorithm. In the second stage, the bi-objective GRASP is extended to the FSS by adding a learning mechanism adapted to multi-objective problems. The conducted computational experiments show that the proposed FSS and GRASP algorithm significantly outperforms existing methods for the bi-objective MWVCP. To fully evaluate the learning mechanism of the FSS, it is compared to the underlying GRASP algorithm on a wide range of performance indicators related to convergence, distribution, spread and cardinality. [ABSTRACT FROM AUTHOR]

In this paper, a carton heterogeneous vehicle routing problem with a collection depot is presented, which can collaboratively pick the cartons from several carton factories to a collection depot and then from the depot to serve their corresponding customers by using of heterogeneous fleet. Since the carton heterogeneous vehicle routing problem with a collection depot is a very complex problem, particle swarm optimization (PSO) is used to solve the problem in this paper. To improve the performance of the PSO, a self-adaptive inertia weight and a local search strategy are used. At last, the model and the algorithm are illustrated with two test examples. The results show that the proposed PSO is an effective method to solve the multi-depot vehicle routing problem, and the carton heterogeneous vehicle routing problem with a collection depot. Moreover, the proposed model is feasible with a saving of about 28 % in total delivery cost and could obviously reduce the required number of vehicles when comparing to the actual instance. [ABSTRACT FROM AUTHOR]

Elevator systems in buildings face challenges due to unpredictable passenger flow, which can make scheduling elevators complicated to optimize their operation. Most of the existing algorithms are developed based on pattern recognition and may not be effective in scenarios where patterns are difficult to classify, especially when elevator operations involve uncertain human behaviors. To address this issue, this paper proposes a time-dependent optimization model that considers long-term and multi-floor peaks, with a focus on peak floors. The proposed model accounts for dynamic scheduling patterns of elevators and represents passenger flow direction as a relation matrix. The proposed direction optimization method contains several functions to guide iteration direction and improve the efficiency of an iteration process based on classical algorithms. This method also ensures the stability of Markov chains by adjusting an iteration process. The feasibility of the proposed method is supported by the relevant theory, and experimental results show that the direction-optimized algorithms outperform classical algorithms, resulting in the superb operating efficiency of elevators at a lower cost. This paper contributes to the development of efficient algorithms for scheduling elevators in complex traffic patterns, which can improve performance of elevator group systems in buildings. The proposed method is not only limited to elevators but can also be extended to other transportation systems with flow requirements. • Estimating the relation between peak floors without pattern recognition. • Four relations are defined to classify the passenger flow. • Dynamically modifying three metaheuristic algorithms' iteration law. • The application for transportation systems with unpredictable flow. [ABSTRACT FROM AUTHOR]

Periodic vehicle routing problem with time windows (PVRPTWs) is an important combinatorial optimization problem that can be applied in different fields. It is essentially a multiobjective optimization problem due to the problem nature. In this paper, a typical multiobjective PVRPTW with five objectives is first defined and new nonsymmetric real-world multiobjective PVRPTW instances are generated. Then, a hybrid multiobjective memetic algorithm is proposed for solving multiobjective PVRPTW. In the proposed algorithm, a two-phase strategy is devised to improve the comprehensive performance in terms of the convergence and diversity. In this strategy, several extreme solutions near an approximate Pareto front (PF) are identified at Phase I, and then the approximate PF is extended at Phase II. The proposed algorithm is extensively tested on both real-world instances and traditional instances. Experiment results show that the proposed algorithm outperforms two representative competitor algorithms on most of the instances. The effectiveness of the two-phase strategy is also confirmed. [ABSTRACT FROM AUTHOR]

In designing ideal multiple recursive random number (RN) generators (MRGs), the best set of multipliers, in terms of the lattice structure of the RNs produced, is sought. As the order of the MRG increases, the number of possible sets of multipliers to be examined grows exponentially This paper proposes a genetic algorithm for designing good MRGs. The set of multipliers associated with the MRG is encoded as a binary string. Via the operations of reproduction, crossover, and mutation, new sets of multipliers are generated. The spectral values of the MRGs are calculated to guide the search process. As an illustration, the proposed algorithm is employed to find good sets of multipliers for MRGs of orders three and four. The results are better than those derived from other studies. To conclude, this paper not only finds better MRGs of orders three and four, but also develops an algorithm for designing MRGs of higher orders. [ABSTRACT FROM AUTHOR]

In this paper, a new clustering algorithm based on gravitational search algorithm (CGSA) for solving unit commitment (UC) problem is proposed. The UC problem is a combinatorial optimization problem that minimizing quadratic objective function under system and unit constraints. The GSA is a recent introduced algorithm to solve optimization problem that inspired by Newtonian law of gravity. A novel version of GSA, named Clustered-GSA (CGSA) is a flexible and well-balanced mechanism for enhancing exploration and exploitation abilities. The proposed algorithm is tested for standard 100 unit system, IEEE 118 bus system and practical Taiwan 38 bus power system. The effectiveness of proposed algorithm results are compared to those reported in the literature. [ABSTRACT FROM AUTHOR]

In this paper methods and algorithms are examined for solving one important problem of transport logistics, namely formation of roadmap. The proposed mathematical model is based on the well-known multi-depot heterogeneous vehicle routing problem with time windows algorithm. Modifications of the model provide additional conditions and restrictions. Algorithmic support of information transport system in an enterprise is connected with features of the vehicle routing problem. The suggested solution is based on modified Clarke and Wright Algorithm and Variable Neighborhood Search. The risk on the roads and the cost of toll roads are calculated, too. [ABSTRACT FROM AUTHOR]

When a conflict or plan change occurs in the process of cloud service execution, if the initial scheme is not rescheduled in time, it can lead to a delivery delay and a series of nonlinear losses. The cloud service rescheduling (CSRS) problem is considered as a particularly hard combinatorial optimization problem with multi-participants, which is significantly different from traditional flow shop rescheduling problem. It is difficult to coordinate the relationship of service suppliers and construct a reward mechanism to encourage them to participate in the rescheduling. According to the various strategies of service suppliers that do or do not participate in the rescheduling, a game theory model was constructed. The main aim of this paper is to explore how to minimize the reward of suppliers and ensure that the game model develops in a desired direction. Hence, a novel hybrid approach using shuffled frog leading algorithm (SFLA) and Nash equilibrium (NE) theory was proposed to solve the CSRS problem. In addition, we carried out a case study to demonstrate that the SFLA and NE approaches can be implemented for realistically sized problem sets and that the cost savings are significant [ABSTRACT FROM AUTHOR]

Hybridized algorithms are commonly employed to improve the performance of any existing method. However, an optimal learning algorithm composed of evolutionary and swarm intelligence can radically improve the quality of the final neuron states and has not received creative attention yet. Considering this issue, this paper presents a novel metaheuristics algorithm combined with several objectives—introduced as the Hybrid Election Algorithm (HEA)—with great results in solving optimization and combinatorial problems over a binary search space. The core and underpinning ideas of this proposed HEA are inspired by socio-political phenomena, consisting of creative and powerful mechanisms to achieve the optimal result. A non-systematic logical structure can find a better phenomenon in the study of logic programming. In this regard, a non-systematic structure known as Random k Satisfiability (RANkSAT) with higher-order is hosted here to overcome the interpretability and dissimilarity compared to a systematic, logical structure in a Discrete Hopfield Neural Network (DHNN). The novelty of this study is to introduce a new multi-objective Hybrid Election Algorithm that achieves the highest fitness value and can boost the storage capacity of DHNN along with a diversified logical structure embedded with RANkSAT representation. To attain such goals, the proposed algorithm tested four different types of algorithms, such as evolutionary types (Genetic Algorithm (GA)), swarm intelligence types (Artificial Bee Colony algorithm), population-based (traditional Election Algorithm (EA)) and the Exhaustive Search (ES) model. To check the performance of the proposed HEA model, several performance metrics, such as training–testing, energy, similarity analysis and statistical analysis, such as the Friedman test with convergence analysis, have been examined and analyzed. Based on the experimental and statistical results, the proposed HEA model outperformed all the mentioned four models in this research. [ABSTRACT FROM AUTHOR]

An autonomous search for sources of gamma radiation in an outdoor environment is a domain suitable for the deployment of a heterogeneous robotic team, consisting of an Unmanned Aerial (UAV) and an Unmanned Ground (UGV) Vehicle. The UAV is convenient for fast mapping of the area and identifying regions of interest, whereas the UGV can perform highly accurate localization. It is assumed that the regions of interest are identified by the UAV during an initial reconnaissance, while performing a simple motion pattern. This paper proposes a path planning algorithm for the UGV, which guarantees accurate source localization in multiple preselected regions and minimizes the total path length. The problem is formulated as the Generalized Travelling Salesman Problem (GTSP) defined for discrete sets of suitable maneuvers (circular arcs), ensuring source localization in the given regions. The problem is successfully solved by a modified version of the state of the art GTSP solver, Generalized Large Neighborhood Search with Arcs (GLNSarc). Apart from adapting the GLNS, other aspects of the planning task are addressed: problem discretization and informed sampling of valid circular arcs, variants of weighting the nonrestricted trajectory segments between the arcs and postprocessing of the discretely planned trajectory in the continuous domain. [ABSTRACT FROM AUTHOR]

The Weapon-Target Assignment (WTA) problem aims to assign a set of weapons to a number of assets (targets), such that the expected value of survived targets is minimized. The WTA problem is a nonlinear combinatorial optimization problem known to be NP-hard. This paper applies several existing techniques to linearize the WTA problem. One linearization technique (Camm et al. in Oper Res 50(6):946–955, 2002) approximates the nonlinear terms of the WTA problem via convex piecewise linear functions and provides heuristic solutions to the WTA problem. Such approximation problems are, though, relatively easy to solve from the computational point of view even for large-scale problem instances. Another approach proposed by O'Hanley et al. (Eur J Oper Res 230(1):63–75, 2013) linearizes the WTA problem exactly at the expense of incorporating a significant number of additional variables and constraints, which makes many large-scale problem instances intractable. Motivated by the results of computational experiments with these existing solution approaches, a specialized new exact solution approach is developed, which is called branch-and-adjust. The proposed solution approach involves the compact piecewise linear convex under-approximation of the WTA objective function and solves the WTA problem exactly. The algorithm builds on top of any existing branch-and-cut or branch-and-bound algorithm and can be implemented using the tools provided by state-of-the-art mixed integer linear programming solvers. Numerical experiments demonstrate that the proposed specialized algorithm is capable of handling very large scale problem instances with up to 1500 weapons and 1000 targets, obtaining solutions with optimality gaps of up to 2.0 % within 2 h of computational runtime. [ABSTRACT FROM AUTHOR]

The application mapping problem is an NP-hard combinatorial optimization problem in network-on-chip (NoC) design. Applications of size ($n$ $ >$ 30) cannot be solved optimally by an exact algorithm in reasonable time, and the evolutionary algorithms have drawn the attention of NoC researchers. In this paper, we propose a new effective optimization method based on the discrete particle swarm optimization framework, which includes the novel principles for representation, velocity computing, and position-updating of the particles. In our proposed method, particles are allowed to swing between elite and regular pools, and a simple local search procedure is applied on elite particles to exploit the promising solutions. Extensive computational studies using standard benchmark instances and task graphs for free (TGFF) random instances reveal that the proposed optimization algorithm is able to attain the best results, and thus competes very favorably with the previously proposed heuristic approaches. A stability analysis and the two-sided Wilcoxon rank sum tests are also presented to shed light on the robust behavior of the algorithm. [ABSTRACT FROM AUTHOR]

Under the social background of the rapid development of big data, human beings have gradually moved towards a comprehensive digital era, and people have begun to apply digital technology in various fields. Therefore, it is necessary to study methods that can efficiently process big data and solve problems such as data intelligence. Intelligent products and applications that we use everywhere in our lives are changing people's lives. Among them, location service is one of the important technical supports. No matter which software is opened on the mobile phone, it will prompt us to open location service. Location prediction is an important part of location-based services and plays an indispensable role in the recommendation system and urban resource planning. At present, GPS-based trajectory data is widely concerned in position prediction task. GPS trajectory data belongs to spatiotemporal series data, which not only contains time and position information but also contains abundant context information in trajectory sequence. Most of the traditional position prediction methods focus on the position sequence in GPS trajectory but do not fully mine the context information in the trajectory, which leads to poor prediction results. The intelligent optimization algorithm greatly enriches the optimization technology and provides a feasible solution for those combinatorial optimization problems which are difficult to deal with by traditional optimization technology. GPS trajectory data has the advantages of wide coverage, quick update, easy collection, and low cost, and it also implies abundant road network information. As a result, GPS trajectory data of users has gradually become a new data source for automatic construction of urban road network and has also become a research hotspot of many scholars. In this paper, the idea of swarm intelligence algorithm and swarm intelligence algorithm are used to design and implement a data analysis and behavior prediction system for calculating GPS user trajectory, aiming at solving the shortcomings of existing GPS tracking and positioning. [ABSTRACT FROM AUTHOR]