Content of Theory·Algorithm in our journal

Published in last 1 year |  In last 2 years |  In last 3 years |  All Please wait a minute... For Selected: Download Citations EndNote Ris BibTeX Toggle Thumbnails Select Research on Directed Clique Enumeration with Strongly Connected Constraint CHEN Jiujian, DAI Qiangqiang, LI Ronghua, WANG Guoren Journal of Frontiers of Computer Science and Technology    2024, 18 (5): 1211-1222.   DOI: 10.3778/j.issn.1673-9418.2303079 Directed edges in a directed graph can represent the direction of relationships or the transmission of data. Introducing connectivity constraints in the mining of dense subgraphs can enhance the connections between vertices. Accordingly, by combining the definitions of maximal cliques and strongly connected components, a directed clique is a subgraph structure where the underlying graph is a complete subgraph and the vertices are strongly connected. Existing work has proposed an output-sensitive algorithm for enumerating maximal directed cliques, but it suffers from lots of repeated enumerations and complex deduplication operations. To address these issues, a novel recursive enumeration algorithm based on depth-first search and the characteristics of directed clique extension is proposed. The algorithm divides the outgoing and incoming neighbors into candidate and excluded sets respectively. While preserving the structure of complete subgraph, it constantly tries to extend the directed cliques and ensures that they are strongly connected. Additionally, the algorithm adopts a pivot pruning strategy based on common neighbors, achieving efficiency optimization of over a thousand times on dense graphs. Furthermore, the algorithm utilizes two optimization designs for the search space: firstly, a pre-processing step is introduced to divide subgraphs and narrow the search for the recursion; secondly, a bitwise compression representation is proposed for vertex sets to improve the efficiency of set operations. Experimental results on real-world graphs demonstrate that the proposed algorithm achieves a speedup of more than 50x compared with the existing output-sensitive algorithm. Reference | Related Articles | Metrics Abstract （59） PDF （59） Select Self-competitive Hindsight Experience Replay with Penalty Measures WANG Zihao, QIAN Xuezhong, SONG Wei Journal of Frontiers of Computer Science and Technology    2024, 18 (5): 1223-1231.   DOI: 10.3778/j.issn.1673-9418.2303031 Self-competitive hindsight experience replay (SCHER) is an improved strategy proposed based on the hindsight experience replay (HER) algorithm. The HER algorithm generates virtual labeled data by replaying experiences to optimize the model in the face of sparse environmental rewards. However, the HER algorithm has two problems: firstly, it cannot handle the large amount of repetitive data generated due to sparse rewards, which contaminates the experience pool; secondly, virtual goals may randomly select intermediate states that are not helpful in completing the task, leading to learning bias. To address these issues, the SCHER algorithm proposes two improvement strategies: firstly, increase the adaptive reward signal to penalize meaningless actions made by agents and quickly avoid such operations; secondly, use self-competition strategy to generate two sets of data for the same task, analyze and compare them, and find the key steps that enable the agent to succeed in different environments, thereby improving the accuracy of generated virtual goals. Experimental results show that the SCHER algorithm can better utilize the experience replay technique, increasing the average task success rate by 5.7 percentage points, and has higher accuracy and generalization ability. Reference | Related Articles | Metrics Abstract （86） PDF （43） Select Family of Maximal Consistent Alliance Interval Sets in Incomplete Heterogeneous Conflict Information System LUO Junfang, ZHANG Shuo, HU Mengjun Journal of Frontiers of Computer Science and Technology    2024, 18 (5): 1232-1242.   DOI: 10.3778/j.issn.1673-9418.2305081 As effective tools for dealing with uncertainty, three-way decision models have been widely applied in the study of conflict analysis. However, existing three-way conflict analysis models are mostly based on single-type conflict information systems, which fail to address the challenges of practical situations where agents may have missing or multiple types of ratings. Furthermore, the existing definitions of alliance sets are typically based on a given agent. Particularly, agents in an alliance set are allied to the given agent, but they are not necessarily allied with each other. To address these issues, this paper proposes a three-way conflict analysis model in an incomplete heterogeneous conflict information system. Additionally, this paper presents the definition and algorithm of a family of maximal consistent alliance interval sets, where agents are allied with each other. Firstly, the incomplete heterogeneous conflict information system with single-dimensional multi-type ratings is transformed into a two-dimensional fuzzy incomplete conflict information system with two-dimensional single-type ratings. This is achieved by defining the support and opposition degrees for different rating types of agents. Secondly, the agent-based alliance, conflict, and neutral interval sets using optimistic and pessimistic distance functions between agents are defined. Finally, a family of maximal consistent alliance interval sets is defined and obtained by adopting the algorithm of maximal clique enumeration. Reference | Related Articles | Metrics Abstract （45） PDF （40） Select Clustering Multivariate Time Series Data Based on Shape Extraction with Compactness Constraint ZHANG Chi, CHEN Mei, ZHANG Jinhong Journal of Frontiers of Computer Science and Technology    2024, 18 (5): 1243-1258.   DOI: 10.3778/j.issn.1673-9418.2212038 Aiming at the naturalness and structural complexity of multivariate time series (MTS) data as well as the inability of existing algorithms to accurately identify clusters of high-dimensional time series data, the shape extraction multivariate time series clustering algorithm C-Shape under compactness constraints is proposed. Firstly, C-Shape performs largest triangle three buckets processing on the complex MTS to achieve the purpose of using fewer data while keeping the original shape unchanged. The raw data and the processed data are then selected to calculate the compactness between them to ensure the reduced spatial dimensionality is reasonable. Next, new cluster centers are obtained by using shape extraction while effectively preserving the shape integrity of the data, and the final cluster is formed by iteration. C-Shape can avoid the difficulty of grasping the low dimensional spatial dimensionality of the traditional down-sampling algorithm by fully taking into account the similarity between the shapes of the processed data and raw data. To validate its performance, C-Shape is tested with two classical and seven excellent time series clustering algorithms presented in recent years on the eight normal and four imbalanced MTS datasets with dimensions ranging from tens to thousands, respectively. Experimental results demonstrate all C-Shape clustering capabilities outperform those of the nine baseline algorithms, with an average improvement of 16.33% in Rand index and an average improvement of 69.71% in time performance. Thus C-Shape is an accurate and efficient multivariate time series clustering algorithm. Reference | Related Articles | Metrics Abstract （73） PDF （86） Select Multi-strategy Improved Dung Beetle Optimizer and Its Application GUO Qin, ZHENG Qiaoxian Journal of Frontiers of Computer Science and Technology    2024, 18 (4): 930-946.   DOI: 10.3778/j.issn.1673-9418.2308020 Dung beetle optimizer (DBO) is an intelligent optimization algorithm proposed in recent years. Like other optimization algorithms, DBO also has disadvantages such as low convergence accuracy and easy to fall into local optimum. A multi-strategy improved dung beetle optimizer (MIDBO) is proposed. Firstly, it improves acceptance of local and global optimal solutions by brood balls and thieves, so that the beetles can dynamically change according to their own searching ability, which not only improves the population quality but also maintains the good searching ability of individuals with high fitness. Secondly, the follower position updating mechanism in the sparrow search algorithm is integrated to disturb the algorithm, and the greedy strategy is used to update the location, which improves the convergence accuracy of the algorithm. Finally, when the algorithm stagnates, Cauchy Gaussian variation strategy is introduced to improve the ability of the algorithm to jump out of the local optimal solution. Based on 20 benchmark test functions and CEC2019 test function, the simulation experiment verifies the effectiveness of the three improved strategies. The convergence analysis of the optimization results of the improved algorithm and the comparison algorithms and Wilcoxon rank sum test prove that MIDBO has good optimization performance and robustness. The validity and reliability of MIDBO in solving practical engineering problems are further verified by applying MIDBO to the solution of automobile collision optimization problems. Reference | Related Articles | Metrics Abstract （239） PDF （259） Select Approach to Multi-path Coverage Testing Based on Path Similarity Table and Individual Migration QIAN Zhongsheng, SUN Zhiwang, YU Qingyuan, QIN Langyue, JIANG Peng, WAN Zilong, WANG Yahui Journal of Frontiers of Computer Science and Technology    2024, 18 (4): 947-962.   DOI: 10.3778/j.issn.1673-9418.2301018 The application of genetic algorithm in multi-path coverage testing is a research hotspot. In the process of iteration between the old and new populations, the old population may contain excellent individuals from other sub-populations, which are not fully utilized, resulting in resource waste. At the same time, the number of individuals in the population will be much greater than that of reachable paths, and each individual will go through a reachable path. This causes multiple individuals to pass through the same path, leading to repeated calculation of the similarity between the individual and the target path. Based on this, a multi-path coverage testing method combined with path similarity table and individual migration is proposed to improve testing efficiency. By storing the calculated path similarity value in the path similarity table, the value can be avoided from being calculated repeatedly and the testing time can be reduced. In the evolutionary process, the individual path is compared with other target paths, and if the similarity reaches the threshold, the excellent individual is migrated to the sub-population corresponding to the path, which improves the utilization rate of individuals and reduces the evolutionary generation. Experiments show that, compared with other six classic methods, the proposed method reduces the average generation time on eight programs by up to 44.64%, and the minimum is 2.64%, and the average evolution generation is reduced by up to 35.08%, and the minimum is 6.13%. Therefore, the proposed method effectively improves the test efficiency. Reference | Related Articles | Metrics Abstract （88） PDF （73） Select Few-Shot Knowledge Graph Completion Based on Selective Attention LIN Sui, LU Chaohai, JIANG Wenchao, LIN Xiaoshan, ZHOU Weilin Journal of Frontiers of Computer Science and Technology    2024, 18 (3): 646-658.   DOI: 10.3778/j.issn.1673-9418.2212076 Most few-shot knowledge graph completion models have some problems, such as low ability to learn relation representation and rarely attaching importance to the relative location and interaction between query entity pair when the relation between entities is complex or triples’ neighborhood is sparse. A selective attention mechanism and interaction awareness (SAIA) based few-shot knowledge graph completion algorithm is proposed. Firstly, by introducing selective attention mechanism in the process of aggregating neighbor information, the neighbor encoder pays more attention to important neighbors to reduce adverse effects of noise neighbors. Secondly, SAIA utilizes the information related to task relation in the background knowledge graph to learn more accurate relation embedding in the process of relationship representation learning. Finally, in order to mine the interaction information and location information between entities in knowledge graph, a common interaction rate index (CIR) of entity pair is designed to measure the degree of association between entities in 3-hop path. Then, SAIA combines entity pair semantic information to predict new fact. Experimental results show that SAIA outperforms the state-of-the-art few-shot knowledge graph completion methods. Compared with the optimal results of baseline models, the proposed method achieves 5-shot link prediction performance improvement of 0.038, 0.011, 0.028 and 0.052 on NELL-one dataset and 0.034，0.037，0.029 and 0.027 on Wiki-one dataset by the metric MRR, Hits@10, Hits@5 as well as Hits@1, which verifies the effectiveness and feasibility of SAIA. Reference | Related Articles | Metrics Abstract （184） PDF （270） Select Smooth Non-negative Low-Rank Graph Representation for Clustering QIAN Luoxiong, CHEN Mei, ZHANG Chi, ZHANG Jinhong, MA Xueyan Journal of Frontiers of Computer Science and Technology    2024, 18 (3): 659-673.   DOI: 10.3778/j.issn.1673-9418.2212041 The existing low-rank graph representation algorithms fail to capture the global representation structure of data accurately, and cannot make full use of the valid information of data to guide the construction of the representation graph, then the constructed representation graph does not have a connected structure suitable for clustering. A smooth non-negative low-rank graph representation method for clustering (SNLRR) is proposed to solve these problems. To more accurately capture the global representation structure of data, SNLRR uses a logarithmic determinant function that is more consistent with the rank characteristics of the matrix to replace the kernel norm to estimate the rank function smoothly, which can effectively reduce the impact of larger singular values of the matrix on the rank estimation, balance the contribution of all singular values to the rank estimation, enhance the accuracy of the rank estimation, so as to more accurately capture the global representation structure of the data. The distance regularization term is also introduced to adaptively assign the optimal nearest neighbor learning representation matrix for each data point to capture the local representation structure of data. Besides, SNLRR applies rank constraint on the Laplace matrix of representation matrix so that the learned representation graph has the same number of connected components as the real number of clusters, that is, the resulting representation graph has a interconnected structure suitable for clustering. Experimental results on seven datasets with high dimensions and complex distribution, using eight comparison algorithms, show that the clustering performance of SNLRR algorithm is better than that of the eight comparison algorithms, with an average increase of 0.2073 in accuracy and 0.1758 in NMI. Therefore, SNLRR is a graph representation clustering algorithm that can effectively handle data with high dimensions and complex distribution. Reference | Related Articles | Metrics Abstract （96） PDF （117） Select Possibilistic Distribution Distance Measure: Robust Domain Adaptation Learning Method DAN Yufang, TAO Jianwen Journal of Frontiers of Computer Science and Technology    2024, 18 (3): 674-692.   DOI: 10.3778/j.issn.1673-9418.2211120 Domain adaptation (DA) aims to solve the problem of inconsistent distribution between training dataset and test dataset, which has attracted extensive attention. Most of the existing DA methods solve this problem by the maximum mean discrepancy (MMD) criterion or its variants. However, the noise data may lead to a significant drift of domain mean, which will reduce the performance of MMD and its variants to some extent. To this end, this paper proposes a robust domain adaptation method with possibilistic distribution distance measure. Firstly, the traditional MMD criterion is transformed into a new possibilistic clustering model, which aims to reduce the impact from noise data. This paper constructs a robust possibilistic distribution distance measure (P-DDM) criterion. It further improves the robust effectiveness of domain distribution alignment by adding the fuzzy entropy regularization term. Secondly, a domain adaptation visual classifier based on P-DDM (C-PDDM) is proposed. It adopts a graphical Laplacian matrix for preserving the geometric consistency of data in source domain and target domain. It can improve the label propagation performance. In order to improve generalization, it maximizes the use of source domain discrimination information to minimize the domain discrimination error. Theoretical analysis confirms that the proposed P-DDM is an upper bound of the traditional distribution distance measurement method MMD criterion under certain conditions. Therefore, minimizing the P-DDM can effectively optimize the MMD objective. Finally,  it is compared with several representative domain adaptation methods, and the experimental results  on 6 visual benchmark datasets (Office31, Office-Caltech, Office-Home, PIE, MNIST-UPS, and COIL20) show that the proposed method achieves an average improvement of about 5% on generalization performance and an average improvement of about 10% on robustness performance. Reference | Related Articles | Metrics Abstract （140） PDF （75） Select Strategy Selection and Outcome Evaluation of Three-Way Decisions Based on Reinforcement Learning LIU Xiaoxue, JIANG Chunmao Journal of Frontiers of Computer Science and Technology    2024, 18 (2): 378-386.   DOI: 10.3778/j.issn.1673-9418.2210090 The trisecting-acting-outcome (TAO) model of three-way decision (3WD) consists of three steps: trisect a whole, design action strategies, and outcome analysis and measurement. Currently, research on outcome evaluation aims to measure the pre- and post-change in outcomes following the implementation of strategies, and it is still unable to predict which strategy will achieve the maximum effect. To narrow down this gap, this paper focuses on the “acting” and “outcome” of the TAO model and introduces a method for strategy selection and outcome prediction for the change-based three-way decision based on Q-learning in reinforcement learning. Firstly, the approach is to treat the altered tri-partition and the acting in the change-based three-way decision TAO model as states and actions in reinforcement learning, respectively, and to consider the process of obtaining a newly altered tri-partition each time under the acting of action or strategy as a cycle. The reward generated by each cycle is calculated using cumulative prospect theory, and the interaction process between the agent and the environment is represented by a Markov decision process. Secondly, a target reward is set, and the state when the cumulative reward of each cycle reaches the target reward is taken as the termination state of the Markov decision process. Then a Q-learning algorithm is used to iterate a set of actions that achieve the target reward in the shortest cycle and then the action set is used to predict the future utility of the change-based three-way decision. Finally, an example is employed to illustrate the applicability and effectiveness of the method. Reference | Related Articles | Metrics Abstract （135） PDF （106） Select Multivariate Time Series Density Clustering Algorithm Using Shapelet Space SHENG Jinchao, DU Mingjing, SUN Jiarui, LI Yurui Journal of Frontiers of Computer Science and Technology    2024, 18 (2): 387-402.   DOI: 10.3778/j.issn.1673-9418.2211099 Multivariate time series clustering has become an important research topic in the task of time series analysis. Compared with univariate time series, the research of multivariate time series is more complex and difficult. Although many clustering algorithms for multivariate time series have been proposed, these algorithms still have difficulties in solving the accuracy and interpretation at the same time. Firstly, most of the current work does not consider the length redundancy and variable correlation of multivariable time series, resulting in large errors in the final similarity matrix. Secondly, the data are commonly used in the clustering process with the division paradigm, when the numerical space presents a complex distribution, this idea does not perform well, and it does not have the explanatory power of each variable and space. To address the above problems, this paper proposes a multivariate time series adaptive weight density clustering algorithm using Shapelet (high information-rich continuous subsequence) space (MDCS). This algorithm firstly performs a Shapelet search for each variable, and obtains its own Shapelet space through an adaptive strategy. Then, it weights the numerical distribution generated by each variable to obtain a similarity matrix that is more consistent with the characteristics of data distribution. Finally, the data are finally allocated using the shared nearest neighbor density peak clustering algorithm with improved density calculation and secondary allocation. Experimental results on several real datasets demonstrate that MDCS has better clustering results compared with current state-of-the-art clustering algorithms, with an average increase of 0.344 and 0.09 in the normalized mutual information and Rand index, balancing performance and interpretability. Reference | Related Articles | Metrics Abstract （255） PDF （624） Select Multi-objective Dwarf Mongoose Optimization Algorithm with Leader Guidance and Dominated Solution Evolution Mechanism ZHAO Shijie, ZHANG Hongyi, MA Shilin Journal of Frontiers of Computer Science and Technology    2024, 18 (2): 403-424.   DOI: 10.3778/j.issn.1673-9418.2211001 In the face of the increasingly complex multi-objective optimization problems, it is necessary to develop novel multi-objective optimization algorithms to meet the challenges. This paper proposes a multi-objective dwarf mongoose optimization algorithm (MODMO) with leader guidance and dominated solution dynamic reduction evolution mechanism. In the leader guidance mechanism, a dynamic trade-off factor is introduced to regulate the search radius of the scout mongoose exploring the mound. At the same time, an external archive is constructed with a non-inferior solution set and the leader is determined according to the non-dominated ranking level, and then the scout mongoose is guided to advance to the multi-objective frontier to improve the convergence of the algorithm. The dominant solution dynamic reduction evolution strategy is constructed to overcome the redundancy problem in the process of maintaining the external archive of non-inferior solutions. It dynamically selects the dominant solutions based on the dominance relationship and crowding distance and stores them in the external archive. The dominant solution information is integrated into the population evolution to realize the mining of multi-objective potential frontier and enhance the diversity of the algorithm. Compared with five representative algorithms on ZDT, DTLZ and WFG benchmark functions, experimental results show that MODMO algorithm has significant advantages in convergence and diversity. Reference | Related Articles | Metrics Abstract （183） PDF （142） Select Many-Objective Evolutionary Algorithm with Vector Angle Selection and Indicator Deletion GU Qinghua, LUO Jiale, LI Xuexian Journal of Frontiers of Computer Science and Technology    2024, 18 (2): 425-438.   DOI: 10.3778/j.issn.1673-9418.2208111 Given that the challenge for evolutionary algorithms when solving many-objective optimization problems lies in balancing the convergence and diversity, a many-objective evolutionary algorithm based on vector angle selection and indicator deletion (MOEA/AS-ID), is proposed. In this algorithm, a coordinated mechanism that includes two strategies is designed in the environmental selection process to delete the solutions with poor convergence and diversity one by one, retaining the elitist to participate in the evolution process for the next generation. To be specific, the former strategy based on vector angle selection is used to select a pair of solutions with a similar search direction in the objective space, and the latter indicator-based deletion strategy which uses the [ISDE+] indicator (indicator shift-based density estimation) that takes into account the convergence and diversity of a single solution, is employed to compare the selected pair of solutions and delete the solution with a smaller indicator value, then encourage the population to converge to the Pareto optimal front toward all directions. Finally, the balance between convergence and diversity of the solution set is achieved. On DTLZ (Deb-Thiele-Laumanns-Zitzler), SDTLZ (scaled DTLZ), and MaF (many-objective function) three benchmark test suites with various characteristics，MOEA/AS-ID and six recently proposed many-objective evolutionary algorithms covering all current types perform extensive comparative simulation experiments and numerical results analysis. Simulation results and numerical analysis show that MOEA/AS-ID has strong competitiveness in balancing the convergence and diversity when solving many-objective optimization problems with various characteristics. Reference | Related Articles | Metrics Abstract （100） PDF （44） Select Feature Selection Combining Artificial Bee Colony with [K-means] Clustering SUN Lin, LIU Menghan, XUE Zhan’ao Journal of Frontiers of Computer Science and Technology    2024, 18 (1): 93-110.   DOI: 10.3778/j.issn.1673-9418.2212075 K-means clustering is a simple and efficient, fast in convergence and easy to implement statistical analysis method. However, the traditional [K-means] clustering algorithm is sensitive to the selection of initial clustering centers and easy to fall into a local optimum, and at the same time, most unsupervised feature selection algorithms are easy to ignore the relationship between features. To solve the above issues, this paper proposes a feature selection algorithm combining artificial bee colony with [K-means] clustering. Firstly, to make the similarity of samples in the same cluster high and the similarity of the samples in different clusters low, a new fitness function is constructed based on the clustering degree within the cluster and the dispersion degree between the clusters, which can better reflect the characteristics of each sample, and then a new probability expression of the honey source being selected is constructed. Secondly, the weight which decreases gradually with the increase of the number of iterations is designed, and the honey source location update expression that makes the search range of the bee colony dynamically indent is proposed. Thirdly, to make up for the limitation of the traditional Euclidean distance which only considers the cumulative difference between vectors when calculating the distance, a weighted Euclidean distance expression which simultaneously considers both the different influence degrees of the samples and the similarity of the samples is constructed. Finally, the standard deviation and distance correlation coefficient are introduced to define feature discrimination and feature representativeness, and the product of them is used to measure the importance of features. Experimental results show that the proposed algorithm accelerates the convergence speed of artificial bee colony algorithm and improves the clustering effect of [K-means] algorithm, and also effectively improves the classification effect of feature selection. Reference | Related Articles | Metrics Abstract （113） PDF （126） Select Deep Learning Compiler Load Balancing Optimization Method for Model Training WANG Li, GAO Kai, ZHAO Yaqian, LI Rengang, CAO Fang, GUO Zhenhua Journal of Frontiers of Computer Science and Technology    2024, 18 (1): 111-126.   DOI: 10.3778/j.issn.1673-9418.2209026 For computing-intensive artificial intelligence (AI) training tasks, the computational graph is more complex, and data loading, task division of the computational graph, and load balancing of task scheduling have become the key factors affecting the computing performance. This paper proposes three optimization methods to make the task scheduling of model training in deep learning compilers reach the load balance state. Firstly, the load balance between CPU and back-end computing devices is realized by automatically establishing an efficient pipeline for data loading and model training, which improves the overall energy efficiency of the system. Secondly, the layered optimization technology of computational graph is used to realize the load balance of computational graph when the back-end devices are scheduling. Finally, this paper improves the resource utilization of back-end devices by automatically establishing efficient pipeline between layers. Experimental results show that the proposed optimization method achieves the system load balancing in the process of automatically mapping the training tasks to underlying hardware devices. Compared with traditional deep learning frameworks and compilers such as TensorFlow, nGraph, etc., this paper achieves 2%~10% performance improvement in the training of different AI models, and the overall power consumption of the training system can be reduced by more than 10%. Reference | Related Articles | Metrics Abstract （315） PDF （486） Select Density Backbone Clustering Algorithm Based on Adaptive Threshold ZHANG Jinhong, CHEN Mei, ZHANG Chi Journal of Frontiers of Computer Science and Technology    2023, 17 (12): 2880-2895.   DOI: 10.3778/j.issn.1673-9418.2208003 The existing clustering algorithms are inaccurate to identify arbitrary clusters, sensitive to density changes within clusters, sensitive to outliers and difficult to determine the threshold. An adaptive threshold-constrained density cluster backbone clustering algorithm (DCBAT) is proposed to solve the problems. Firstly, the adaptive reachability density threshold is defined in combination with the skewness coefficient and points density mean. Under the constraint of the threshold, the core points with higher local densities and higher relative distances are grouped according to the reachability, and the initial clusters backbones are obtained. The non-core points are then assigned into the cluster which their nearest neighbors with higher density belong to. Finally, the adaptive density D-value threshold is proposed in combination with D-value mean and scale factor. According to the threshold, the initial cluster is separated at the point where the density varies sharply, and the final clusters are obtained. DCBAT fully considers the internal structure and distribution of the data when clustering, thereby improving the clustering performance. The performance of this algorithm is demonstrated compared with five excellent algorithms k-means,DBSCAN, OPTICS, CFDP and MulSim on eight datasets with various dimensions and types. DCBAT algorithm has the advantages of good recognition of arbitrary clusters, insensitivity to density changes within clusters, insensitivity to outliers and stable clustering result. Its overall performance is superior to comparison algorithms. Reference | Related Articles | Metrics Abstract （134） PDF （173） Select Remora Optimization Algorithm Combining Joint Opposite Selection and Host Switching JIA Heming, WEN Changsheng, WU Di, RAO Honghua, LIU Qingxin, LI Shanglong Journal of Frontiers of Computer Science and Technology    2023, 17 (12): 2896-2912.   DOI: 10.3778/j.issn.1673-9418.2210057 The remora optimization algorithm (ROA) is a meta heuristic optimization algorithm proposed in 2021. It simulates the behavior of parasitic attachment to the host, empirical attack and host foraging in the ocean. The structure of ROA is simple and easy to implement, but the overall situation is slightly insufficient, which easily leads to ROA’s slow convergence speed and even difficult convergence in the later period. To solve the above problems, host switching mechanism is added in the exploration phase, and new host beluga is introduced to improve the exploration ability of original ROA. At the same time, through adding joint opposite selection strategy, the ability of the algorithm to jump out of the local optimum is enhanced, and the comprehensive optimization performance of the algorithm is further improved. Through the above improvements, an improved remora optim-ization algorithm (IROA) is proposed, which integrates the joint opposite selection and host switching mechanism. In order to verify the performance and improvement advantages of IROA, IROA is compared with the original ROA, six typical original algorithms and four improved algorithms on ROA. Experimental results of CEC2020 standard test function show that IROA has stronger optimization ability and higher convergence accuracy. Finally, the advantages and engineering applicability of the improved algorithm are further verified by solving the car crashworthiness design problem. Reference | Related Articles | Metrics Abstract （152） PDF （135） Select Multi-objective Black Widow Algorithm Guided by Competitive Mechanism and Pheromone Mechanism FU Yanming, XU Liqiang, QI Kangheng, SHEN Yuming, QU Chiwen Journal of Frontiers of Computer Science and Technology    2023, 17 (12): 2913-2927.   DOI: 10.3778/j.issn.1673-9418.2207004 Black widow optimization algorithm (BWOA) is a swarm intelligence optimization algorithm, which has the advantages of fast convergence and high precision. However, the update strategy adopted by BWOA is too simple, and it is easy to fall into the local optimal solution. Moreover, the search ability in multi-dimensional space is lacking, the population structure is single, and the convergence and diversity of the algorithm need to be improved.  In order to improve the comprehensive performance of BWOA and make it applicable to multi-objective optimization problems, this paper proposes a multi-objective black widow optimization algorithm (MBWOA) guided by a competition mechanism and an improved pheromone mechanism. MBWOA adopts the method of dynamic allocation of populations, which divides the populations into two in the iterative process and uses different competition mechanisms to enhance the diversity of the populations in the iterative process and improve the convergence of the algorithm. At the same time, it uses the improved pheromone mechanism to guide offspring individuals that have gone through the competition mechanism to optimize in the direction of population gap, improve the distribution of population, and enhance the convergence ability of the algorithm. Using MBWOA and four comparison algorithms to conduct comparative experiments on three indicators of IGD, HV and Spread respectively, the results show that MBWOA has better convergence accuracy, convergence speed and diversity. Finally, the effectiveness of the used mechanism is confirmed by the experiments of MBWOA and the comparison algorithms on three indicators. Reference | Related Articles | Metrics Abstract （187） PDF （280） Select Incremental Feature Selection Oriented for Data with Hierarchical Structure SHE Yanhong, HUANG Wanli, HE Xiaoli, QIAN Ting Journal of Frontiers of Computer Science and Technology    2023, 17 (12): 2928-2941.   DOI: 10.3778/j.issn.1673-9418.2308062 In the big data era, the sample size is becoming increasingly large, the data dimensionality is also becoming extremely high, moreover, there exists hierarchical structure between different class labels. This paper investigates incremental feature selection for hierarchical classification based on the dependency degree of inclusive strategy and solves the hierarchical classification problem where labels are distributed at arbitrary nodes in tree structure. Firstly, the inclusive strategy is used to reduce the negative sample space by exploiting the hierarchical label structure. Secondly, a new fuzzy rough set model is introduced based on inclusive strategy, and a dependency calculation algorithm based on the inclusive strategy and a non-incremental feature selection algorithm are also proposed. Then, the dependency degree based on the inclusive strategy is proposed by adopting the incremental mechanism. Based on these, two incremental feature selection frameworks based on two strategies are designed. Lastly, a comparative study with the method based on the sibling strategy is performed. The?feasibility?and?efficiency?of the proposed algorithms are verified by numerical experiments. Reference | Related Articles | Metrics Abstract （59） PDF （72） Select Resource-Constrained Project Scheduling Problems Oriented Two-Stage Imperialist Competitive Algorithm LI Bin, HUANG Qibin Journal of Frontiers of Computer Science and Technology    2023, 17 (11): 2620-2639.   DOI: 10.3778/j.issn.1673-9418.2208055 The resource-constrained project scheduling problem is a classic combinatorial optimization problem with a wide range of engineering applications. Since the 1960s, many optimization algorithms have been used to solve this problem, but most intelligent optimization algorithms do not perform well in the whole problem space. Aiming at this challenge, a two-stage evolutionary imperialist competitive algorithm (TSE-ICA) is proposed. Firstly, based on the block extraction strategy obtained by the critical-path method, two assimilation operators are presented for diversification and convergence, respectively. The two-stage evolution framework of TSE-ICA is constructed by selecting appropriate assimilation operators in different stages. Then, the block-based improved revolution mechanism includes two neighborhood search strategies of insertion and out-of-order, and the empire competition mechanism  realizes the adaptive adjustment of parameters for each empire by collecting the convergence information of them. Lastly, the memory is used to guide the evolution of the population and improve the convergence rate. The design of experiment technique of Taguchi method is applied to determining the optimal parameter setting for TSE-ICA. In the following numerical experiment, the TSE-ICA is implemented and tested by 3 instance sets (J30, J60 and J120) from the standard instance library of PSPLIB. Moreover, the empirical statistical data of TSE-ICA are compared with 17 advanced state-of-the-art algorithms based on two evaluation criteria. Experimental results show that the TSE-ICA has well optimization performance and convergence efficiency, which proves the effectiveness of the proposed improved mechanism and the problem applicability of the TSE-ICA preliminarily. Reference | Related Articles | Metrics Abstract （129） PDF （85） Select Incremental Reduced Lagrangian Asymmetric ν-Twin Support Vector Regression ZHANG Shuaixin, GU Binjie, PAN Feng Journal of Frontiers of Computer Science and Technology    2023, 17 (11): 2640-2650.   DOI: 10.3778/j.issn.1673-9418.2207050 Lagrangian asymmetric ν-twin support vector regression is a prediction algorithm with good generalization performance. However, it is unsuitable for the scenarios where the samples are provided incrementally. Therefore, an incremental Lagrangian asymmetric ν-twin support vector regression (IRLAsy-ν-TSVR) algorithm is proposed. Firstly, the constrained optimization problems are transformed into unconstrained ones by introducing the plus functions, and the semi-smooth Newton method is utilized to directly solve them in the primal space to accelerate the convergence speed. Then, the matrix inverse lemma is adopted to realize efficient incremental update of the Hessian matrix inversion in the semi-smooth Newton method and save time. Next, to reduce the memory cost caused by the sample accumulation, the column and row vectors of the augmented kernel matrix are filtered by the reduced technology to approximate the original augmented kernel matrix, and this ensures the sparsity of the solution. Finally, the feasibility and efficacy of the proposed algorithm are validated on the benchmark datasets. The results show that compared with some state-of-the-art algorithms, the IRLAsy-ν-TSVR algorithm inherits the generali-zation performance of the offline algorithm and can obtain sparse solution, which is more suitable for online learning of large-scale datasets. Reference | Related Articles | Metrics Abstract （85） PDF （63） Select Clustering Algorithm for Constructing Connected Graphs with Reverse Nearest Neighbors LONG Jianwu, WANG Qiang Journal of Frontiers of Computer Science and Technology    2023, 17 (11): 2651-2662.   DOI: 10.3778/j.issn.1673-9418.2207017 The development of big data era makes the application of clustering algorithms more and more widespread, but most current clustering algorithms are sensitive to noisy data and cannot identify datasets with complex structures such as non-convex shapes. To address this problem, a clustering algorithm for constructing connected graph with reverse nearest neighbor is proposed. Firstly, a density calculation is designed to obtain the density of data points, and a dynamic noise discriminator is constructed to denoise the data so as to weaken the effect of noise on the clustering process. Secondly, considering that reverse neighbors better reflect the connection between data points and surrounding points, a clustering method is designed to construct reverse nearest neighbor connectivity graphs for the denoised data to identify data structure information within clusters, and to merge clusters using a given number of clusters. Finally, when classifying the noise points into clusters, considering that only classifying them into the closest clusters may lead to inaccurate classification results, a noise classification method is designed to take the density information into account to obtain the final clustering results. To verify the effectiveness of the proposed method, the clustering results of proposed algorithm are compared with those of five other clustering algorithms, and the external evaluation metrics Acc (cluster accuracy) and NMI (normalized mutual information) are used to evaluate the clustering results. Experimental results show that the clustering results of the proposed algorithm are better than those of comparison algorithms on the noisy datasets with complex structures such as non-convex shapes. Reference | Related Articles | Metrics Abstract （145） PDF （139） Select Reachability Algorithm Based on Key Points Labeling for Sparse Graphs MIAO Weihua, WEI Hui Journal of Frontiers of Computer Science and Technology    2023, 17 (10): 2426-2434.   DOI: 10.3778/j.issn.1673-9418.2212016 Reachability queries of directed graphs are fundamental when studying various network problems, such as querying whether two persons follow each other in a social network. However, with the increasing size of networks, traditional algorithms have become unacceptable due to their huge time or space complexity. Therefore, it is necessary to use a suitable reachability algorithm according to the structural characteristics of the network. A sparse graph consists of several directed spanning trees with a small number of non-tree edges. The GRKPL (graph reachability indexing via key points labeling) algorithm splits the reachability problem in sparse graphs into two parts: the tree reachability problem and the impact of adding non-tree edges. The first part is solved by the interval labeling method, and the second part is solved by constructing a key point set, which transforms all the reachability queries in the original graph into queries in the key point set. The key point set includes all nodes covered by non-tree edges and the lowest common ancestors between adjacent nodes after these nodes are sorted in the preorder traversal order. And it is proven that the size of the key point set is of the same order of magnitude as the size of the non-tree edges in the original graph. Finally, GRKPL is tested on ten small- and medium-scale and four large-scale realistic datasets. GRKPL performs well on small- and medium-scale datasets, with an average 49.8% reduction in query processing time and 65.1% reduction in space occupation compared to other algorithms. Reference | Related Articles | Metrics Abstract （115） PDF （110） Select Multi-view Graph Clustering with View Relation Learning and Graph Learning YUAN Zhu, GAO Qingwei, WANG Lin, ZHAO Dawei, LU Yixiang, SUN Dong, ZHU De Journal of Frontiers of Computer Science and Technology    2023, 17 (10): 2435-2449.   DOI: 10.3778/j.issn.1673-9418.2206090 Simple and efficient multi-view graph clustering methods have received a lot of attention in recent years. Most existing multi-view graph clustering algorithms do not sufficiently mine the information hidden in multi-view data, resulting in sub-optimal clustering results. To address this problem, a multi-view graph clustering algorithm combining view relation learning and graph learning (MVG) is proposed. The method integrates graph fusion and spectral clustering learning in a unified framework based on multi-view self-expressions. View self-expression learning is extended to reveal the low-dimensional subspace distribution of high-dimensional data, jointly constrai-ning the geometric structure of the multi-view data distribution. And the complementary information between the multi-view view data is exploited to optimize the similarity graphs for each view. The spectral clustering input graphs and the weights occupied by different views are alternatively optimized. Finally, by learning the graph structure of the fusion graph, a connection with spectral clustering is established and a high-quality spectral clustering input graph is constructed. The information hidden in the multi-view data is fully explored and exploited to be highly competitive in terms of clustering performance. Experiments are conducted on five widely used multi-view datasets to verify the effectiveness and feasibility of the algorithm. The experimental data on the reuters-1200 dataset show 0.22, 0.09, 0.115, 0.152, 0.032 and 0.185 improvement over the next best method in terms of clustering evaluation metrics respectively. Reference | Related Articles | Metrics Abstract （189） PDF （206） Select Dual Ant Colony Optimization with Neighborhood Coupling Mechanism and Bilateral Filtering WU Lisheng, YOU Xiaoming, LIU Sheng Journal of Frontiers of Computer Science and Technology    2023, 17 (9): 2092-2106.   DOI: 10.3778/j.issn.1673-9418.2205099 To overcome the slow convergence and premature stagnation of the ant colony algorithm in solving traveling salesman problem (TSP), a dual ant colony optimization with neighborhood coupling mechanism and bilateral filtering (NBACO) is proposed. Firstly, the ant colony is dynamically divided into soldier ants and commanding ants by the combat power index. The soldier ants are mainly responsible for improving the solution accuracy of the algorithm, and the commander ants are mainly responsible for improving the convergence speed of the algorithm. And these two kinds of ants coordinate together to balance the relationship between the accuracy and convergence speed of the algorithm effectively. Secondly, to increase the choosing possibility of the public path in the algorithm, a neighborhood coupling mechanism is used to disseminate a little pheromone both in the public area and its neighborhood adaptively when the commanding ants visit this area, so that a high convergence speed of the algorithm is achieved, which can increase the probability of ants choosing public area and its neighborhood. Furthermore, while the algorithm falls into a local optimum, a bilateral filtering strategy based on Gini impurity is introduced to dynamically decrease the pheromone of the current optimal path. In this strategy, the pheromone concentration difference between the optimal path and its neighboring paths is reduced, which can greatly help the algorithm get rid of the local optimum and increase the probability of ants choosing other non-optimal paths at the next iteration. Finally, from a large number of TSP instances, the experimental results show that the improved ant colony algorithm can balance the solution accuracy and convergence speed of the algorithm effectively. Reference | Related Articles | Metrics Abstract （106） PDF （108） Select Global and Local Structure Learning for Multi-view Subspace Clustering QIAO Yuxin, GE Hongwei, SONG Peng Journal of Frontiers of Computer Science and Technology    2023, 17 (9): 2107-2117.   DOI: 10.3778/j.issn.1673-9418.2201077 Constrained bilinear factorization multi-view subspace clustering algorithm (CBF-MSC) ignores local struc-ture information of views, resulting in loss of information and thus affecting the effect of multi-view clustering. To solve the above problems, a multi-view subspace clustering algorithm based on global and local structure learning (constrained bilinear factorization by learning global and local structures for multi-view subspace clustering, CBF-LGLS) is proposed. The algorithm considers the consistency and complementarity of views, and considers that the coefficient matrices of different views should have the same clustering attributes, rather than being consistent among multiple views, so as to fully explore the underlying data distribution and clustering attributes of mining views. Moreover, the algorithm also fully considers the local structure information of the view, effectively captures the internal differences of a single view and reduces the loss of information. Then, the algorithm comprehensively considers the local structure information of views, effectively capturing the internal differences of a single view and reducing the loss of information. In addition, the algorithm adopts an adaptive weighting method to reduce the impact of noise and redundancy on clustering effect. For the traditional pattern of predefined similarity matrices for each view, an adaptive distance regularization method is adopted to fully consider the geometric structure of a single view and the same cluster structure between views, thereby improving clustering performance. The algorithm is tested on widely-used datasets and compared with mainstream algorithms. The results show that the proposed algorithm obtains good clustering effect and convergence. Reference | Related Articles | Metrics Abstract （233） PDF （198） Select HHO Algorithm Based on Bidirectional Experience Guidance and Extreme Individual Regulation CHAI Yan, REN Sheng Journal of Frontiers of Computer Science and Technology    2023, 17 (9): 2118-2136.   DOI: 10.3778/j.issn.1673-9418.2203134 In order to improve the optimization accuracy and iteration speed of Harris hawks optimization (HHO) algorithm, a bidirectional experience guided and extreme individual regulated HHO algorithm (BEHHO) is proposed. Firstly, Circle chaotic mapping is used to homogenize the initial population to effectively avoid individual aggregation and improve the coverage of the Harris hawks population to the solution space region, laying foundation for algorithm optimization. Secondly, the bidirectional experience guidance strategy is introduced to strengthen the rounding mechanism of the algorithm, the evolution experience of the global optimal individual and the historical optimal individual is used to guide the individual to search for the optimal direction, and the differential disturbance term of the adaptive random individual is used to strengthen the ability of the population to explore the neighborhood and improve the convergence accuracy of the algorithm. Furthermore, considering important impact of algorithm extreme individual on the global update process, the optimal individual t - distribution variation is used to avoid algorithm into local extremum, and the reverse solution of the worst individual is generated by reverse dynamic learning to improve the convergence speed indirectly. At the same time, greedy principle is adopted to retain the dominant individual to ensure the accuracy of the algorithm’s progeny individual tends to be better. Finally, the global convergence of the algorithm is analyzed based on Markov chain. By comparing the optimization of benchmark test functions, Wilcoxon rank sum test and CEC2014 complex functions, the improved algorithm is proven to have excellent solving performance and robust robustness, and the superiority of BEHHO algorithm in practical problems is verified by welding beam design problems in engineering optimization. Reference | Related Articles | Metrics Abstract （129） PDF （122） Select Research on Periodic Triangle Enumeration Algorithm for Temporal Graphs REN Zebin, LI Ronghua, DAI Yongheng, WANG Guoren Journal of Frontiers of Computer Science and Technology    2023, 17 (8): 1833-1841.   DOI: 10.3778/j.issn.1673-9418.2202004 Real-world graphs are usually temporal graphs, and their edges are associated with timestamps. With the development of algorithms on graph data mining and the increase of needs in real-world, data mining algorithms for temporal graphs have started to become a hot topic. Periodicity is a very important feature in temporal data. Patterns that occur periodically in real world usually indicate important features. In data mining algorithms for static graphs, triangle enumeration is a fundamental and important problem. In this paper, a new triangle model is proposed based on the temporal graph, the periodic triangle. In this paper, periodic data mining is combined with triangle enumeration algorithms in graphs, and an efficient algorithm for periodic triangle enumeration in temporal graphs is proposed. This algorithm contains three components: the first one is an efficient multi-level pruning algorithm which can delete vertices and edges which are not in any periodic triangle at low cost; the second one is a maximal periodic enumeration algorithm that can avoid enumeration on overlapping communities in time axis; the third one is an efficient periodic triangle enumeration algorithm that prunes unnecessary vertices and edges while enumeration. Experiments show that the algorithm proposed in this paper can enumerate periodic triangles in graphs efficiently. Reference | Related Articles | Metrics Abstract （143） PDF （78） Select Design and Implementation of Efficient Multi-branch Predictor YANG Ling, ZHOU Jinwen, WANG Jing, LAN Mengqiao, DING Zijian, YANG Shi, WANG Yongwen, HUANG Libo Journal of Frontiers of Computer Science and Technology    2023, 17 (8): 1842-1851.   DOI: 10.3778/j.issn.1673-9418.2207069 Branch prediction is a momentous technology guarantee for processor performance, especially for the widely used superscalar processor. The properties of the branch predictor significantly affect the overall performance, power consumption, and area of the processor. To obtain a more cost-effective branch predictor in the superscalar processor, an attempt is made to use a single TAGE (tagged geometric history length) predictor to predict the branches within the fetch width. The championship branch prediction platform is used to evaluate the performance of the predictor, and its prediction ability is sufficient to meet the prediction conditions. However, in practice, conflicts in both the predictor and branch target buffer affect its performance. To solve the above problem, this paper adds additional prediction paths based on a single TAGE branch predictor and independently saves and predicts additional branch instruction information. This predictor is implemented in the processor using hardware description language and compared with a single TAGE branch predictor to perform standard benchmark programs for embedded processors, dhrystone, coremark and embench. Experimental results show that the performance of the optimized branch predictor is improved by 14.1 percentage points, while the storage overhead is only increased by 9.06%. Finally, through the analysis of the experimental data, it is found that this scheme is not only conducive to the prediction of additional branch instructions, but also can achieve more accurate prediction of single branch instruction through more accurate acquisition of branch history information. Reference | Related Articles | Metrics Abstract （363） PDF （376） Select Attention Learning Particle Swarm Optimization Algorithm Guided by Aggrega-tion Indicator ZHAO Xiaoyan, SONG Wei Journal of Frontiers of Computer Science and Technology    2023, 17 (8): 1852-1866.   DOI: 10.3778/j.issn.1673-9418.2201044 Although the particle swarm optimization (PSO) algorithm has demonstrated good performance in solving many optimization problems, maintaining population diversity while ensuring convergence accuracy, preventing the swarm from getting trapped in local optima, and balancing exploration and exploitation remain important research problems for PSO algorithms. In response to these issues, this paper proposes an attention learning particle swarm optimization algorithm guided by aggregation indicator (ALPSO-AI). Firstly, to effectively maintain population diversity, the entire population is divided into equally sized subswarms, which are recombined during the evolution process. In each generation, different particles in the subswarms adaptively select multiple high-quality learning objects based on their performance. An external archive is established to guide the search and evaluate the evolutionary progress of the population. Secondly, an attention mechanism is introduced to assign different attention weights to each learning object based on the difference between its performance and the updated particle??s fitness value. Thus, a high-quality learning prototype is generated for particle updates. Different scales of attention allocation methods are designed to meet the diverse search requirements in the early and late stages of the search process, enabling both global and local search capabilities. Furthermore, an aggregation indicator is introduced to the archive, which assesses the current population??s evolutionary level by examining the similarity of fitness values around the current best particle. When the aggregation indicator reaches a threshold, local search is initiated to enhance the overall convergence capability of the algorithm. Experimental evaluations are conducted on the 28 benchmark functions from the CEC2013 test suite in both 30 and 50 dimensions. ALPSO-AI is compared with five popular PSO variants and other optimization algorithms. Experimental results confirm the superiority of ALPSO-AI. The effectiveness of attention learning and the aggregation indicator is also thoroughly validated. Reference | Related Articles | Metrics Abstract （168） PDF （108） Select Improved Sparrow Search Algorithm Combining Ranking-Based Elastic Collision WANG Zikai, HUANG Xueyu, ZHU Donglin, GUO Wei Journal of Frontiers of Computer Science and Technology    2023, 17 (8): 1867-1878.   DOI: 10.3778/j.issn.1673-9418.2205037 To improve the shortcomings of the sparrow search algorithm (SSA), such as the loss of diversity due to inadequate population initialization results and the susceptibility to interference from individual location information during exploration and exploitation, which affect the accuracy of the search, an improved sparrow search algorithm based on fusion ranking elastic collision, referred to as XSSA, is proposed. Firstly, an improved iterative chaotic map with infinite collapses (ICMIC) improves the dispersion degree of the initial population distribution. Then, the Gaussian random walk strategy is used to balance the exploration and development capabilities of the algorithm. In addition,  sorted elastic collision policy is imposed on all individuals after the discoverer is updated, which avoids premature convergence of the algorithm to the local extreme value. Finally, a multi-strategy boundary processing mechanism is formulated according to the characteristics of optimization at different stages to retain the population and avoid the loss of diversity. At the same time, the position of individuals beyond the boundary is re-updated in combination with important position information, so that the processed position is more reasonable and provides quality guarantee for the next iterative search. The simulation experiments are performed on 12 benchmark functions, and the convergence accuracy graph demonstrates the performance of the algorithm. By means of contribution tests for each strategy, Wilcoxon rank sum test and the comprehensive ranking of Friedman test, the effectiveness, uniqueness and better optimization performance of XSSA are proven. Reference | Related Articles | Metrics Abstract （136） PDF （64） Select Density Peaks Clustering Combining Relative Local Density and Nearest Neighbor Relationship WANG Weina, ZHU Yu, REN Yan Journal of Frontiers of Computer Science and Technology    2023, 17 (8): 1879-1892.   DOI: 10.3778/j.issn.1673-9418.2205032 When the density peaks algorithm deals with datasets with different densities, the wrong center points may be selected, and the problem of associated errors may occur in the sample allocation process. To solve the above problems, a density peaks clustering algorithm based on the relative local density and nearest neighbor relationship is proposed. The weights of sparse balance are introduced into the definition of local density, and the definition of relative local density is proposed. The density peak can be found according to the relative local density, which avoids the error of selecting the density peak in the dataset with large sparse differences, and ensures the accuracy of the center point selection. The nearest neighbor allocation strategy is proposed by combining the nearest neighbor criterion and threshold limit to suppress the allocation error effectively. The modified allocation strategy based on the mean value of the distance within the class is proposed to enhance the accuracy of the algorithm for boundary point clustering. The proposed algorithm is compared with DPC, DPC-MND, FKNN-DPC, DBSCAN, OPTICS, AP, and K-means algorithms on 5 synthetic datasets and 5 UCI datasets, and the experimental results demonstrate that the proposed algorithm has sound clustering performance in metrics of adjusted mutual information, adjusted Rand index, and Fowlkes-Mallows index. Friedman test shows that the algorithm has the best performance. Reference | Related Articles | Metrics Abstract （142） PDF （126） Select Multi-GPU Programming Model for Subgraph Matching in Large Graphs LI Cenhao, CUI Pengjie, YUAN Ye, WANG Guoren Journal of Frontiers of Computer Science and Technology    2023, 17 (7): 1576-1585.   DOI: 10.3778/j.issn.1673-9418.2111062 Subgraph matching is an important method of data mining in complex networks. In recent years, the subgraph matching algorithm based on GPU (graphics processing units) has shown obvious speed advantages.However, due to the large scale of graph data and a large number of intermediate results of subgraph matching, the memory capacity of a single GPU soon becomes the main bottleneck for processing subgraph matching algorithm of large graph. Therefore, this paper proposes a multi-GPU programming model for large graph subgraph matching. Firstly, the framework of subgraph matching algorithm based on multi-GPU is proposed, and the cooperative operation of subgraph matching algorithm on multi-GPU is realized, which solves the problem of graph scale of subgraph matching on GPU. Secondly, a dynamic adjustment technique based on query graph is used to deal with cross-partition subgraph sets, which solves the cross-partition subgraph matching problem caused by graph segmentation. Finally, based on the characteristics of SIMT (single instruction multiple threads) architecture on GPU, a priority scheduling strategy is proposed to ensure the internal load balancing of GPU, and a pipeline mechanism of shared memory is designed to optimize the cache contention of multi-core concurrency. Experiments show that the proposed multi-GPU programming model can get the correct matching results on billions of datasets. Compared with the latest GPU-based solution, the proposed algorithm framework can achieve 1.2 to 2.6 times of acceleration ratio. Reference | Related Articles | Metrics Abstract （253） PDF （176） Select Hybrid Algorithm of Sparrow Algorithm and Arithmetic Optimization Algorithm Based on Hamiltonian Graph TIAN Lu, LIU Sheng Journal of Frontiers of Computer Science and Technology    2023, 17 (7): 1586-1598.   DOI: 10.3778/j.issn.1673-9418.2110060 Aiming at the shortcomings of sparrow search algorithm (SSA), such as decreased population diversity in the late iteration and easily falling into local optimal solution, a hybrid algorithm of sparrow search algorithm and arithmetic optimization algorithm based on Hamiltonian graph (HSSAAOAH) is proposed. Firstly, the multiplica-tion and division operator of arithmetic optimization algorithm (AOA) is introduced into the discoverer-follower model and reconnaissance mechanism of SSA. The high distribution of multiplication and division operator is used to improve the randomness of later optimization. Secondly, the population composed by all the individuals is transferred into an undirected weight graph. After each iteration, a Hamiltonian cycle and its length composed of individuals will be computed according to a modified cycle algorithm, and the population optimization trend is measured by the ratio of the Hamiltonian cycle length. Then, for the progeny that fails to perform effective convergence, a certain number of individuals are randomly generated to replace the last ones according to the greedy algorithm, which improves the quality of solution and enhances the ability to jump out of local extrema. Finally, HSSAAOAH and different optimization algorithms are simulated on the benchmark function and two engineering design problems. The results show that HSSAAOAH algorithm has faster convergence speed, higher optimization accuracy, and good robustness and optimization performance. Reference | Related Articles | Metrics Abstract （106） PDF （116） Select Least Squares Support Vector Machine for Minimizing VC Dimensional Expectation Upper Bound LI Hao, WANG Shitong Journal of Frontiers of Computer Science and Technology    2023, 17 (7): 1599-1608.   DOI: 10.3778/j.issn.1673-9418.2112108 Machine learning is an important aspect of modern computer technology, and the support vector machine method has been widely used in all walks of life because of its good performance in recent years. The performance of support vector machine can be measured by VC (Vapnik-Chervonenkis) dimension, which is an index to measure the complexity of the machine. In theory, low VC dimension can be well generalized. However, for some classifier methods based on traditional support vector machine, the upper bound of VC dimension of support vector machine may be infinite when dealing with a variety of data. Although good results have been obtained in practice and application, it can not guarantee good generalization, resulting in poor results for some special data. Therefore, this paper proposes an improved LSSVM (least squares support vector machines) algorithm. Based on LSSVM algorithm, this paper minimizes the upper bound of VC dimension and finds the desired best projection scheme. Finally, this paper brings it into LSSVM algorithm to classify the data. Experimental results show that the error rate of the classifier is lower than that of the traditional least squares support vector machine on the benchmark dataset, which means that the proposed algorithm makes the test accuracy better than the comparison algorithm with the approximate number of support vectors, and improves the generalization ability of the algorithm. Reference | Related Articles | Metrics Abstract （115） PDF （76） Select Single-Cell Differentiation Trajectory Inference Algorithm with Iterative Feature Selection HE Hongjian, YIN Yiting, XIE Jiang Journal of Frontiers of Computer Science and Technology    2023, 17 (7): 1609-1621.   DOI: 10.3778/j.issn.1673-9418.2203047 The construction of cell differentiation trajectories from single-cell transcriptomic data or proteomic data by single-cell trajectory inference methods can help to understand the developmental process of normal tissues or provide pathologically relevant information. However, the accuracy and robustness of current single-cell trajectory inference algorithms are still a challenge, one of the reasons is the noise caused by the detection of a large number of unrelated genes in single-cell sequencing. In order to solve this problem, a trajectory inference method iterTIPD (iterative trajectory inference based on probability distribution) based on iterative feature selection is proposed. Its innovation lies in iteratively applying feature selection methods widely used for screening differentially expressed genes to linear or branching single-cell RNA sequencing data, and improving the accuracy and robustness of cell pseudotime ordering by selecting the gene subset that contributes the most to the constructed differentiation trajectory. Experimental results on four scRNA-seq datasets show that iterTIPD can effectively improve the accuracy and robustness of the single-cell trajectory inference algorithm. IterTIPD also improves the performance of other trajectory inference algorithms, proving generalization of iterTIPD. The differentiation trajectory of neural stem cells is reconstructed by iterTIPD algorithm, and the comparison shows that the differentiation trajectory is highly consistent with the known neural stem cell differentiation trajectory. Meanwhile, Top2a and Gja1 may be novel markers defining activated neural stem cell subpopulations. Reference | Related Articles | Metrics Abstract （194） PDF （176） Select Surrogate-Assisted Evolutionary Algorithms with Adaptive Constraint Evaluation WEI Fengfeng, CHEN Weineng Journal of Frontiers of Computer Science and Technology    2023, 17 (6): 1301-1320.   DOI: 10.3778/j.issn.1673-9418.2203078 Many real-world optimization problems have not only expensive objectives but also expensive constraints. However, most existing surrogate-assisted evolutionary algorithms (SAEAs) evaluate all constraints of the candidates. With limited number of evaluations, it is wasteful to constantly evaluate constraints whose feasible area is large. To solve this problem, this paper studies SAEAs for expensive constrained optimization problems, and proposes an adaptive constraint evaluation strategy. It can adaptively evaluate constraints with less feasible information according to the population evolution, saving expensive evaluations wasted on constraints with more feasible information. The algorithm can adaptively select and evaluate constraints within limited budget of expensive evaluation to better evolve the population. To verify the effectiveness and scalability of this strategy, this paper designs two Gaussian regression model-assisted differential evolution algorithms cooperated with the adaptive constraint evaluation strategy. Experiments demonstrate the proposed SAEAs perform better in 11 out of 15 problems. Besides, they can achieve more than 94% efficiency improvement with the time delay on evaluations. Specifically, the efficiency improvement is larger than 98% in 91.67% test cases. Experiments in 4 engineering optimization problems demonstrate that SAEAs with the adaptive constraint evaluation strategy have promising applications in real-world optimization problems. Reference | Related Articles | Metrics Abstract （147） PDF （161） Select MSV-Net: Visual Super-Resolution Reconstruction for Scientific Simulated Data of Mixed Surface-Volume CAO Siming, WANG Xiaohua, WANG Hongkun, CAO Yi Journal of Frontiers of Computer Science and Technology    2023, 17 (6): 1321-1328.   DOI: 10.3778/j.issn.1673-9418.2112069 High fidelity visual analysis usually relies on high-resolution grid data of coupled geometric models generated by large-scale scientific simulation, which brings great challenges to data storage and smooth interaction. Therefore, this paper proposes a super-resolution reconstruction method for large-scale scientific simulated data of mixed surface-volume, which is MSV-Net. The network is an end-to-end deep neural network, which realizes the joint learning of hybrid rendering mapping from low resolution data to high resolution data through multi-layer nonlinear transformation. The network without the fully connected layer, can not only reduce the network parameters, but also improve the flexibility and reusability of the network. In addition, MSV-Dataset, a surface-volume mixed dataset for large-scale electromagnetic simulation application is constructed for model training and verification. This dataset consists of mixed rendered images using nontransparent geometric model rendering coupled with semitransparent volume rendering. The proposed method is compared with a variety of traditional and deep learning methods. The quantitative analysis results show that the MOS absolute evaluation index of this method reaches 4.1, and the reconstruction accuracy is second only to the real image; it takes 66.28 s to directly draw mixed data with 1500×1500 image resolution, but only 4.14 s with the proposed method. The interaction performance is improved about 15 times. Reference | Related Articles | Metrics Abstract （159） PDF （109） Select Multi-model Adaptation Method of Possibilistic Clustering Assumption DAN Yufang, TAO Jianwen, ZHAO Yue, PAN Jie, ZHAO Baoqi Journal of Frontiers of Computer Science and Technology    2023, 17 (6): 1329-1342.   DOI: 10.3778/j.issn.1673-9418.2112076 Graph based semi-supervised learning (GSSL) has been attracting more and more attention with its intui-tiveness and good learning performance in the machine learning community. However, it is found that existing graph based semi-supervised learning method has the problem of poor robustness and sensitivity to noise and abnor-mal data by analysis. In addition, the premise for the GSSL to have good performance is that the training data and test data are independently identically distribution (IID), which leads to some limitations in practical applications. In order to solve above problems, this paper proposes a novel clustering method based on structure risk minimization model, called a multi-model adaptation method of possibilistic clustering assumption (MA-PCA), and effectively minimizes the influence from the noise and abnormal instances based on different data distributions in some reproduced kernel Hilbert space. Its main ideas are as follows: the negative impact of noise and abnormal data on the method is reduced through fuzzy entropy; considering the effective multi-model adaptive learning of training data and test data in the same distribution and different distributions, it can also obtain good performance by rela-xing the constraint of IID between training data and test data; the algorithm implementation and convergence the-orem are given. A large number of experiments and in-depth analysis on multiple real visual datasets show that the proposed method has superior or comparable robustness and generalization performance. Reference | Related Articles | Metrics Abstract （110） PDF （286） Select Multi-chaotic Sparrow Search Algorithm Based on Learning Mechanism LI Guangyang, PAN Jiawen, QIAN Qian, YIN Jibin, FU Yunfa, FENG Yong Journal of Frontiers of Computer Science and Technology    2023, 17 (5): 1057-1074.   DOI: 10.3778/j.issn.1673-9418.2204030 To solve the shortcomings of sparrow search algorithm (SSA), such as falling into local extremum easily influenced by initial solution and slow convergence in late iteration, a multi-chaotic sparrow search algorithm  based on learning mechanism (MMCSSA) is proposed. Firstly, the centroid opposition-based learning strategy (COBL) is introduced to generate elite population to enhance the exploration of multi-source high-quality search areas, and then the local extreme escape ability and convergence performance of the algorithm are improved. Secondly, a scaled golden sine algorithm is proposed and embedded in SSA to improve the guidance search mode and enhance the global search ability of the algorithm. Thirdly, a multi-chaos mapping strategy based on learning mechanism is proposed, which utilizes the characteristics of multi-chaos and multi-disturbance, and enforces different disturb-ance features on the algorithm by dynamically calling different chaotic maps. When chaotic perturbation fails, Gaussian mutation strategy is introduced to deeply develop the current solution. The two strategies cooperate and promote each other, greatly enhancing the ability of the algorithm to escape from local optimal. Finally, the proposed algorithm is applied to 12 benchmark functions with different characteristics, and the results show that compared with other algorithms, MMCSSA has better performance in convergence accuracy, optimization speed and robustness. Reference | Related Articles | Metrics Abstract （246） PDF （169） page Page 1 of 2 Total 53 records First page Prev page Next page Last page