Advanced computing

Select

Optimal path convergence method based on artificial potential field method and informed sampling

LI Wei, JIN Shijun

Journal of Computer Applications 2021, 41 (10): 2912-2918. DOI: 10.11772/j.issn.1001-9081.2020122021

Abstract （371）

PDF （1628KB）（346）

Save

The Rapidly exploring Random Tree star (RRT ^*) algorithm ensures its probabilistic completeness and asymptotic optimality in the path planning process, but still has problems such as slow convergence speed and large and dense sampling space. In order to speed up the convergence of the algorithm, a fast obtaining method of optimal path based on artificial potential field method and informed set sampling was proposed. First, the artificial potential field method was used to construct an initial path from the starting point to the target point. Then, the positions of and the distance between the starting point and the target point as well as the path cost of the initial path were used as parameters to construct the initial informed sampling set. At last, the sampling was limited in the informed set, and the range of the informed sampling set was adjusted during the running process of the algorithm to accelerate the path convergence speed. Simulation experiments show that, Potential Informed-RRT ^* (PI-RRT ^*) algorithm based on the artificial potential field combined with informed sampling method reduces the number of sampling points by about 67%, and shortens the algorithm running time by about 74.5% on average compared with RRT ^* algorithm; and has the number of sampling points reduced by about 40%-50%, the algorithm running time shortened by about 62.5% on average compared with Informed RRT ^* (Informed-RRT ^*) algorithm. The proposed optimal path convergence method greatly reduces the number of redundant sampling and the algorithm running time, has higher algorithm efficiency, and converges to the optimal path with faster speed.

Reference | Related Articles | Metrics

Select

Task allocation strategy in unmanned aerial vehicle-assisted mobile edge computing

WANG Daiwei, XU Gaochao, LI Long

Journal of Computer Applications 2021, 41 (10): 2928-2936. DOI: 10.11772/j.issn.1001-9081.2020121917

Abstract （375）

PDF （800KB）（361）

Save

In the scenario of using Unmanned Aerial Vehicle (UAV) as the data collector for computation offloading to provide Mobile Edge Computing (MEC) services to User Equipment (UE), a wireless communication strategy to achieve efficient UE coverage through UAV was designed. Firstly, under the condition of a given UE distribution, for the UAV flight trajectory and communication strategy, an optimization method of Successive Convex Approximation (SCA) was used to obtain an approximate optimal solution that was able to minimize the global energy. In addition, for scenarios with large-scale distribution of UEs or a large number of tasks, an adaptive clustering algorithm was proposed to divide the UEs on the ground into as few clusters as possible, and to ensure the offloading data of all UEs in each cluster was able to be collected in one flight. Finally, the computation offloading data collection tasks of the UEs in each cluster were allocated to one flight, so that the goal of reducing the number of dispatches required for a single UAV or the UAV number of dispatches required for multiple UAVs to complete the task was achieved. The simulation results show that the proposed method can generate fewer clusters than the K-Means algorithm and converge quickly, and is suitable for UAV-assisted computation offloading scenarios with widely distributed UEs.

Reference | Related Articles | Metrics

Select

Improved grey wolf optimizer for location selection problem of railway logistics distribution center

HAO Pengfei, CHI Rui, QU Zhijian, TU Hongbin, CHI Xuexin, ZHANG Diyou

Journal of Computer Applications 2021, 41 (10): 2905-2911. DOI: 10.11772/j.issn.1001-9081.2020121994

Abstract （354）

PDF （1101KB）（238）

Save

The single mechanism based Grey Wolf Optimizer (GWO) is easy to fall into local optimum and has slow convergence speed. In order to solve the problems, an Improved Grey Wolf Optimization (IGWO) was proposed to solve the actual location selection problem of railway logistics distribution center. Firstly, based on the basic GWO, the theory of good point set was introduced to initialize the population, which improved the diversity of the initial population. Then, the D-value Elimination Strategy (DES) was used to increase the global optimization ability, so as to achieve an efficient optimization mode. The simulation results show that, compared with the standard GWO, IGWO has the fitness value increased by 3%, and the accuracy of the optimal value increased by up to 7 units in 10 test functions. Compared with Particle Swarm Optimization (PSO) algorithm, Differential Evolution (DE) algorithm and Genetic Algorithm (GA), IGWO has the location selection speed increased by 39.6%, 46.5% and 65.9% respectively, and the location selection velocity is significantly improved. The proposed algorithm can be used for railway logistics center location selection.

Reference | Related Articles | Metrics

Select

Fuzzy granulation prediction of traffic flow based on improved whale optimization support vector machine

TONG Lin, GUAN Zheng

Journal of Computer Applications 2021, 41 (10): 2919-2927. DOI: 10.11772/j.issn.1001-9081.2020122048

Abstract （263）

PDF （884KB）（194）

Save

Focusing on the problems of Support Vector Machine (SVM) in traffic flow prediction:volatility and low prediction accuracy, an SVM model using Fuzzy Information Granulation (FIG) and Improved Whale Optimization Algorithm(IWOA) was proposed to predict the traffic flow trends and dynamic ranges. Firstly, the FIG method was performed to the data to obtain the Upper bound (Up), Lower bound (Low) and Trend value (R) of the traffic flow change interval. Secondly, in the population initialization of Whale Optimization Algorithm (WOA), the dynamic opposition-based learning was used to increase the population diversity, and the nonlinear convergence factor and adaptive weight were introduced to enhance the global search and local optimization capabilities of the algorithm. After that, the IWOA model was established and the complexity of IWOA was analyzed. Finally, with the Mean Square Error (MSE) of the predicted traffic flow as the objective function, the hyperparameters of SVM were optimized continuously in the iteration process of IWOA, and a traffic flow interval prediction model based on FIG-IWOA-SVM was established. The tests on domestic and foreign traffic flow datasets were carried out. The results show that, in the prediction of foreign traffic flow, compared with Support Vector Machine based on Genetic Algorithm optimization (GA-SVM), Support Vector Machine based on Particle Swarm Optimization algorithm (PSO-SVM) and Support Vector Machine based on Whale Optimization Algorithm (WOA-SVM), the proposed IWOA-SVM model has the Mean Absolute Error (MAE) reduced by 89.5%, 81.5% and 1.5% respectively. Compared with the FIG-GA-SVM, FIG-PSO-SVM and FIG-WOA-SVM models, the FIG-IWOA-SVM model has higher prediction accuracy and the more stable prediction range in the traffic flow dynamic interval and trend prediction. Experimental results show that, without increasing the complexity of the algorithm, the proposed FIG-IWOA-SVM model can reasonably predict the change trend and change interval of traffic flow, and provide a basis for subsequent traffic planning and flow control.

Reference | Related Articles | Metrics

Select

Improved feature selection and classification algorithm for gene expression programming based on layer distance

ZHAN Hang, HE Lang, HUANG Zhangcan, LI Huafeng, ZHANG Qiang, TAN Qing

Journal of Computer Applications 2021, 41 (9): 2658-2667. DOI: 10.11772/j.issn.1001-9081.2020111801

Abstract （251）

PDF （1220KB）（258）

Save

Concerning the problem that the interpretable mapping relationship between data features and data categories do not be revealed by general feature selection algorithms. on the basis of Gene Expression Programming (GEP),by introducing the initialization methods, mutation strategies and fitness evaluation methods,an improved Feature Selection classification algorithm based on Layer Distance for GEP(FSLDGEP) was proposed. Firstly,the selection probability was defined to initialize the individuals in the population directionally, so as to increase the number of effective individuals in the population. Secondly, the layer neighborhood of the individual was proposed, so that each individual in the population would mutate based on its layer neighborhood, and the blind and unguided problem in the process of mutation was solved。Finally, the dimension reduction rate and classification accuracy were combined as the fitness value of the individual, which changed the population evolutionary mode of single optimization goal and balanced the relationship between the above two. The 5-fold and 10-fold verifications were performed on 7 datasets, the functional mapping relationship between data features and their categories was given by the proposed algorithm, and the obtained mapping function was used for data classification. Compared with Feature Selection based on Forest Optimization Algorithm (FSFOA), feature evaluation and selection based on Neighborhood Soft Margin (NSM), Feature Selection based on Neighborhood Effective Information Ratio (FS-NEIR)and other comparison algorithms, the proposed algorithm has obtained the best results of the dimension reduction rate on Hepatitis, Wisconsin Prognostic Breast Cancer (WPBC), Sonar and Wisconsin Diagnostic Breast Cancer (WDBC) datasets, and has the best average classification accuracy on Hepatitis, Ionosphere, Musk1, WPBC, Heart-Statlog and WDBC datasets. Experimental results shows that the feasibility, effectiveness and superiority of the proposed algorithm in feature selection and classification are verified.

Reference | Related Articles | Metrics

Select

Improved butterfly optimization algorithm based on cosine similarity

CHEN Jun, HE Qing

Journal of Computer Applications 2021, 41 (9): 2668-2677. DOI: 10.11772/j.issn.1001-9081.2020111776

Abstract （502）

PDF （1469KB）（410）

Save

Aiming at the problems that Butterfly Optimization Algorithm (BOA) tends to fall into local optimum and has poor convergence, a Multi-Strategy Improved BOA (MSBOA) was proposed. Firstly, the cosine similarity position adjustment strategy was introduced to the algorithm, rotation transformation operator and scaling transformation operator were used to update the positions, so as to effectively maintain the population diversity of the algorithm. Secondly, dynamic switching probability was introduced to balance the transformation between the local phase and the global phase of the algorithm. Finally, a hybrid inertia weight strategy was added to accelerate convergence. Solving 16 benchmark test functions, as well as the Wilcoxon rank-sum test and CEC2014 test functions were to verify, the effectiveness and robustness of the proposed algorithm. Experimental results show that compared with BOA, some BOAs with different improvement strategies and some swarm intelligence algorithms, MSBOA has significant improvement in convergence accuracy and convergence speed.

Reference | Related Articles | Metrics

Select

Dynamic mapping method for heterogeneous multi-core system under thermal safety constraint

AN Xin, YANG Haijiao, LI Jianhua, REN Fuji

Journal of Computer Applications 2021, 41 (9): 2631-2638. DOI: 10.11772/j.issn.1001-9081.2020111870

Abstract （286）

PDF （1107KB）（227）

Save

The heterogeneous multi-core platform provides flexibility for system design by integrating different types of processing cores, so that applications can dynamically select different types of processing cores according to their requirements and realize efficient operation of applications. With the development of semiconductor technology, the number of integrated cores on a single chip has increased, making the modern multi-core processors have a higher power density, and this will cause the chip temperature to rise, which will eventually cause a certain negative impact on the system performance. To make the performance advantages of heterogeneous multi-core processing system fully utilized, a dynamic mapping method was proposed to maximize the performance of heterogeneous multi-core systems under the premise of satisfying temperature safe power. In this method, two heterogeneous indices of heterogeneous multi-core systems including core type and thermal susceptibility were considered to determine the mapping scheme:the first heterogeneous index is the core type. Different types of processing cores have different characteristics, so they are suitable for processing different applications. The second heterogeneous index is thermal susceptibility. Different processing core positions on the chip have different thermal susceptibility. The processing cores closer to the center receive more heat transfer from other processing cores, so that they have higher temperature. For the above, a neural network performance predictor was created to match threads to processing core types, and the Thermal Safe Power (TSP) model was used to map the matched threads to specific locations on the chip. Experimental results show that the proposed method achieves about 53% increase of the average number of instructions executed by the program in each clock cycle-Instruction Per Cycle (IPC) under the premise of ensuring thermal safety constraints compared with the common Round Robin Scheduler (RRS).

Reference | Related Articles | Metrics

Select

Loop-level speculative parallelism analysis of kernel program in TACLeBench

MENG Huiling, WANG Yaobin, LI Ling, YANG Yang, WANG Xinyi, LIU Zhiqin

Journal of Computer Applications 2021, 41 (9): 2652-2657. DOI: 10.11772/j.issn.1001-9081.2020111792

Abstract （257）

PDF （1190KB）（218）

Save

Thread-Level Speculation (TLS) technology can tap the parallel execution potential of programs and improve the utilization of multi-core resources. However, the current TACLeBench kernel benchmarks are not effectively analyzed in TLS parallelization. In response to this problem, the loop-level speculative execution analysis scheme and analysis tool were designed. With 7 representative TACLeBench kernel benchmarks selected, firstly, the initialization analysis was performed to the programs, the program hot fragments were selected to insert the loop identifier. Then, the cross-compilation was performed to these fragments, the program speculative thread and the memory address related data were recorded, and the maximun potential of the loop-level parallelism was analyzed. Finally, the program runtime characteristics (thread granularity, parallelizable coverage, dependency characteristics) and the impacts of the source code on the speedup ratio were comprehensively discussed. Experimental results show that:1) this type of programs is suitable for TLS acceleration, compared with serial execution results, under the loop structure speculative execution, the speedup ratios for most programs are above 2, and the highest speedup ratio in them can reach 20.79; 2) by using TLS to accelerate the TACLeBench kernel programs, most applications can effectively make use of 4-core to 16-core computing resources.

Reference | Related Articles | Metrics

Select

Relay computation and dynamic diversion of computing-intensive large flow data

LIAO Jia, CHEN Yang, BAO Qiulan, LIAO Xuehua, ZHU Zhousen

Journal of Computer Applications 2021, 41 (9): 2646-2651. DOI: 10.11772/j.issn.1001-9081.2020111725

Abstract （274）

PDF （1199KB）（250）

Save

In view of the problems such as the slow computation of large flow data, the high computation pressure on the server, a set of relay computation and dynamic diversion model of computing-intensive large flow data was proposed. Firstly, in the distributed environment, the in-memory data storage technology was used to determine the computation amounts and complexity levels of the computation tasks. At the same time, the nodes were sorted by the node resource capacity, and the tasks were dynamically allocated to different nodes for parallel computing. Meanwhile, the computation tasks were decomposed by a relay processing mode, so as to guarantee the performance and accuracy requirements of high flow complex computing tasks. Through analysis and comparison, it can be seen that the running time of multiple nodes is shorter than that of the single node, and the computation speed of multiple nodes is faster than that of the single node when dealing with data volume of more than 10 000 levels. At the same time, when the model is applied in practice, it can be seen that the model can not only reduce the running time in high concurrency scenarios but also save more computing resources.

Reference | Related Articles | Metrics

Select

Computation offloading policy for machine learning in mobile edge computing environments

GUO Mian, ZHANG Jinyou

Journal of Computer Applications 2021, 41 (9): 2639-2645. DOI: 10.11772/j.issn.1001-9081.2020111734

Abstract （350）

PDF （1127KB）（327）

Save

Concerning the challenges of the diversity of data sources, non-independent and identical distribution of data and the heterogeneity of both computing capabilities and energy consumption of edge devices in Internet of Things (IoT), a computation offloading policy in Mobile Edge Computing (MEC) network that deploys both centralized learning and federated learning was proposed. Firstly, a system model of computation offloading related to both centralized learning and federated learning was built, considering the network transmission delay, computation delay and energy consumption of centralized learning and federated learning models. Then, with the system delay minimization as optimization object, considering the constraints of energy consumption and the training times based on machine learning accuracy, a computation offloading optimization model for machine learning was constructed. After that, the game for this computation offloading was formulated and analyzed. Based on the analysis results, an Energy-Constrained Delay-Greedy (ECDG) algorithm was proposed, which found the optimal solutions for the model via a two-stage policy of greedy decision and energy-constrained decision updating. Compared to the centralized-greedy and Federated Learning with Client Selection (FedCS) algorithms, ECDG algorithm has the lowest average learning delay, which is 1/10 of that in the centralized-greedy algorithm, and 1/5 of that in the FedCS algorithm. The experimental results show that, ECDG algorithms can automatically select the optimal machine learning models by computation offloading so that it can efficiently reduce the average machine learning delay, improve the energy efficiency of edge devices and satisfy the Quality of Service (QoS) requirements of IoT applications.

Reference | Related Articles | Metrics

Select

Chaotic elite Harris hawks optimization algorithm

TANG Andi, HAN Tong, XU Dengwu, XIE lei

Journal of Computer Applications 2021, 41 (8): 2265-2272. DOI: 10.11772/j.issn.1001-9081.2020101610

Abstract （469）

PDF （1295KB）（333）

Save

Aiming at the shortcomings of Harris Hawks Optimization (HHO) algorithm, such as low convergence accuracy, low convergence speed and being easy to fall into local optimum, a Chaotic Elite HHO (CEHHO) algorithm was proposed. Firstly, the elite hierarchy strategy was introduced to make full use of the dominant population to enhance the population diversity and improve the convergence speed and accuracy of the algorithm. Secondly, the Tent chaotic map was used to adjust the key parameters of the algorithm. Thirdly, a nonlinear energy factor adjustment strategy was adopted to balance the exploitation and exploration of the algorithm. Finally, the Gaussian random walk strategy was used to disturb the optimal individual, and when the algorithm was stagnant, the random walk strategy was used to make the algorithm jump out of the local optimum effectively. Through the simulation experiments of 20 benchmark functions in different dimensions, the optimization ability of the algorithm was evaluated. Experimental results show that the improved algorithm outperforms Whale Optimization Algorithm (WOA), Grey Wolf Optimization (GWO) algorithm, Particle Swarm Optimization (PSO) algorithm, and Biogeography-Based Optimization (BBO) algorithm, and the performance of this algorithm is significantly better than that of original HHO algorithm, which prove the effectiveness of the improved algorithm.

Reference | Related Articles | Metrics

Select

Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem

ZHANG Wenqiang, XING Zheng, YANG Weidong

Journal of Computer Applications 2021, 41 (8): 2249-2257. DOI: 10.11772/j.issn.1001-9081.2020101675

Abstract （349）

PDF （1458KB）（404）

Save

Flexible Job-shop Scheduling Problem (FJSP) is a widely applied combinatorial optimization problem. Aiming at the problems of multi-objective FJSP that the solution process is complex and the algorithm is easy to fall into the local optimum, a Hybrid Particle Swarm Optimization algorithm with Multi-Region Sampling strategy (HPSO-MRS) was proposed to optimize both the makespan and total machine delay time. The multi-region sampling strategy was able to reorganize the positions of the Pareto frontiers that the particles belonging to, and guide the corresponding moving directions for the particles in multiple regions of the Pareto frontiers after sampling. Thus, the convergence ability of particles in multiple directions was adjusted, and the ability of uniform distribution was improved to a certain extent. In addition, in the encoding and decoding aspect, the decoding strategy with interpolation mechanism was used to eliminate the potential local left shift; in the particle updating aspect, the particle update method of traditional Particle Swarm Optimization (PSO) algorithm was combined with the crossover and mutation operators of Genetic Algorithm (GA), which improved the diversity of search process and avoid the algorithm from falling into the local optimum. The proposed algorithm was tested on benchmark problems Mk01-Mk10 and compared with Hybrid Particle Swarm Optimization algorithm (HPSO), Non-dominated Sorting Genetic Algorithm Ⅱ (NSGA-Ⅱ), Strength Pareto Evolutionary Algorithm 2 (SPEA2) and Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) on algorithm effectiveness and operation efficiency. Experimental results of significance analysis showed that, HPSO-MRS was significantly better than the comparison algorithms on the convergence evaluation indexes Hyper Volume (HV) and Inverted Generational Distance (IGD) in 85% and 77.5% of the control groups, respectively. In 35% of the control groups, the distribution index Spacing of the algorithm was significantly better than those of the comparison algorithms. And there was no situation that the proposed algorithm was significantly worse than the comparison algorithms on the three indexes. It can be seen that, compared with the others, the proposed algorithm has better convergence and distribution performance.

Reference | Related Articles | Metrics

Select

Deep pipeline 5×5 convolution method based on two-dimensional Winograd algorithm

HUANG Chengcheng, DONG Xiaoxiao, LI Zhao

Journal of Computer Applications 2021, 41 (8): 2258-2264. DOI: 10.11772/j.issn.1001-9081.2020101668

Abstract （442）

PDF （1087KB）（322）

Save

Aiming at problems such as high memory bandwidth demand, high computational complexity, long design and exploration cycle, and inter-layer computing delay of cascade convolution in two-dimensional Winograd convolution algorithm, a double-buffer 5×5 convolutional layer design method based on two-dimensional Winograd algorithm was proposed. Firstly, the column buffer structure was used to complete the data layout, so as to reuse the overlapping data between adjacent blocks and reduce the memory bandwidth demand. Then, the repeated intermediate calculation results in addition process of Winograd algorithm were precisely searched and reused to reduce the computational cost of addition, so that the energy consumption and the design area of the accelerator system were decreased. Finally, according to the calculation process of Winograd algorithm, the design of 6-stage pipeline structure was completed, and the efficient calculation for 5×5 convolution was realized. Experimental results show that, on the premise that the prediction accuracy of the Convolutional Neural Network (CNN) is basically not affected, this calculation method of 5×5 convolution reduces the multiplication computational cost by 83% compared to the traditional convolution, and has the acceleration ratio of 5.82; compared with the method of cascading 3×3 two-dimensional Winograd convolutions to generate 5×5 convolutions, the proposed method has the multiplication computational cost reduced by 12%, the memory bandwidth demand decreased by about 24.2%, and the computing time reduced by 20%.

Reference | Related Articles | Metrics

Select

Machine breakdown rescheduling of flexible job shop based on improved imperialist competitive algorithm

ZHANG Guohui, LU Xixi, HU Yifan, SUN Jinghe

Journal of Computer Applications 2021, 41 (8): 2242-2248. DOI: 10.11772/j.issn.1001-9081.2020101664

Abstract （341）

PDF （1072KB）（342）

Save

For the flexible job shop rescheduling problem with machine breakdown, an improved Imperialist Competition Algorithm (ICA) was proposed. Firstly, a flexible job shop dynamic rescheduling model was established with the maximum completion time, machine energy consumption and total delay time as the objective functions, and linear weighting method was applied to three objectives. Then, the improved ICA was proposed to retain the excellent information for the next generation. A roulette selection mechanism was added after the assimilation and revolutionary steps of the general ICA, so that the excellent genes in the initial empire were able to be retained, and the updated empire quality was better and closer to the optimal solution. Finally, after the machine breakdown, the event-driven rescheduling strategy was adopted to reschedule the unprocessed job procedures after the breakdown point. Through production examples, simulation experiments were carried out on three hypothetical machine breakdown scenarios, and the proposed algorithm was compared with improved Genetic Algorithm (GA) and Genetic and Simulated Annealing Algorithm (GASA). Experimental results show that the proposed improved ICA is effective and feasible.

Reference | Related Articles | Metrics

Select

Survey of research progress on crowdsourcing task assignment for evaluation of workers’ ability

MA Hua, CHEN Yuepeng, TANG Wensheng, LOU Xiaoping, HUANG Zhuoxuan

Journal of Computer Applications 2021, 41 (8): 2232-2241. DOI: 10.11772/j.issn.1001-9081.2020101629

Abstract （354）

PDF （1533KB）（519）

Save

With the rapid development of internet technology and sharing economy mode, as a new crowd computing mode, crowdsourcing has been widely applied and become a research focus recently. Aiming at the characteristics of crowdsourcing applications, to ensure the completion quality of crowdsourcing tasks, the existing researches have proposed different crowdsourcing task assignment methods from the perspective of the evaluation of worker's ability. Firstly, the crowdsourcing's concept and classification were introduced, and the workflow and task characteristics of the crowdsourcing platform were analyzed. Based on them, the existing research works on the evaluation of workers' ability were summarized. Then, the crowdsourcing task assignment methods and the related challenges were reviewed from three different aspects, including matching-based, planning-based and role-based collaboration. Finally, the research directions of future work were put forward.

Reference | Related Articles | Metrics

Select

Constrained multi-objective optimization algorithm based on coevolution

ZHANG Xiangfei, LU Yuming, ZHANG Pingsheng

Journal of Computer Applications 2021, 41 (7): 2012-2018. DOI: 10.11772/j.issn.1001-9081.2020081344

Abstract （533）

PDF （975KB）（336）

Save

In view of the problem that it is difficult for constrained multi-objective optimization algorithms to effectively balance convergence and diversity, a new constrained multi-objective optimization algorithm based on coevolution was proposed. Firstly, a population with certain number of feasible solutions was obtained by using the feasible solution search method based on steady-state evolution. Then, this population was divided into two sub-populations and both convergence and diversity were achieved by coevolution of the two sub-populations. Finally, standard constrained multi-objective optimization problems CF1~CF7, DOC1~DOC7 and the practical engineering problems were used for simulation experiments to test the solution performance of the proposed algorithm. Experimental results show that compared with Nondominated Sorting Genetic Algorithm Ⅱ based on Constrained Dominance Principle (NSGA-Ⅱ-CDP), Two-Phase algorithm (ToP), Push and Pull Search algorithm (PPS) and Two-Archive Evolutionary Algorithm for Constrained multiobjective optimization (C-TAEA), the proposed algorithm achives good results in both Inverted Generational Distance (IGD) and HyperVolume (HV), indicating that the proposed algorithm can effectively balance convergence and diversity.

Reference | Related Articles | Metrics

Select

Construction method of cloud manufacturing virtual workshop for manufacturing tasks

ZHAO Qiuyun, WEI Le, SHU Hongping

Journal of Computer Applications 2021, 41 (7): 2003-2011. DOI: 10.11772/j.issn.1001-9081.2020081245

Abstract （271）

PDF （1325KB）（242）

Save

To quickly select and organize relevant manufacturing resources and guarantee the execution of manufacturing tasks under the cloud manufacturing mode, a construction method of cloud manufacturing virtual workshop was proposed for manufacturing tasks. In this method, the manufacturing processes were abstracted into manufacturing task execution chains, in which the nodes were corresponding to manufacturing equipment cloud services or inspection cloud services and the directed edges were corresponding to logistics cloud services. At the same time, the cloud services were organized and managed through the industry domain, location domain and type domain to construct smaller candidate sets of cloud services with reducing the computing amount of function matching, performance matching, price matching and time matching, thus constructing cloud manufacturing virtual workshops rapidly. The numerical example analysis shows that compared to other methods, the proposed method can select cloud services in a shorter time and ensure that the Quality of Service (QoS) of the selected cloud services is better in the relevant domains.

Reference | Related Articles | Metrics

Select

Parallel design and implementation of synthetic view distortion change algorithm in reconfigurable structure

JIANG Lin, SHI Jiaqi, LI Yuancheng

Journal of Computer Applications 2021, 41 (6): 1734-1740. DOI: 10.11772/j.issn.1001-9081.2020091462

Abstract （277）

PDF （1262KB）（267）

Save

Focused on the high computational time complexity of the depth map based Synthesized View Distortion Change (SVDC) algorithm in 3D High Efficiency Video Coding (3D-HEVC), a new parallelization method of SVDC algorithm based on hybrid granularity was proposed under the reconfigurable array structure. Firstly, the SVDC algorithm was divided into two parts:Virtual View Synthesis (VVS) and distortion value calculation. Secondly, the VVS part was accelerated by pipeline operation, and the distortion value calculation part was accelerated by dividing into two levels:task level, which means dividing the synthesized image according to pixels, and instruction level, that is dividing the distortion values inside the pixel by the calculation process. Finally, a reconfigurable mechanism was used to parallelize the VVS part and distortion value calculation part. Theoretical analysis and hardware simulation results show that, in terms of execution time, the proposed method has the speedup ratio of 2.11 with 4 Process Elements (PEs). Compared with the SVDC algorithms based on Low Level Virtual Machine (LLVM) and Open Multi-Processing (OpenMP), the proposed method has the calculation time reduced by 18.56% and 21.93% respectively. It can be seen that the proposed method can mine the parallelism of the SVDC algorithm, and effectively shorten the execution time of the SVDC algorithm by combining with the characteristics of the reconfigurable array structure.

Reference | Related Articles | Metrics

Select

Self-organized migrating algorithm for multi-task optimization with information filtering

CHENG Meiying, QIAN Qian, NI Zhiwei, ZHU Xuhui

Journal of Computer Applications 2021, 41 (6): 1748-1755. DOI: 10.11772/j.issn.1001-9081.2020091390

Abstract （403）

PDF （1172KB）（275）

Save

The Self-Organized Migrating Algorithm (SOMA) only can solve the single task, and the "implicit parallelism" of SOMA is not fully exploited. Aiming at the shortcomings, a new Self-Organized Migrating Algorithm for Multi-task optimization with Information Filtering (SOMAMIF) was proposed to solve multiple tasks concurrently. Firstly, the multi-task uniform search space was constructed, and the subpopulations were set according to the number of tasks. Secondly, the current optimal fitness of each subpopulation was judged, and the information transfer need was generated when the evolution of a task stagnated in a successive generations. Thirdly, the useful information was chosen from the remaining subpopulations and the useless information was filtered according to a probability, so as to ensure the positive transfer and readjust the population structure at the same time. Finally, the time complexity and space complexity of SOMAMIF were analyzed. Experimental results show that, SOMAMIF converges rapidly to the global optimal solution 0 when solving multiple high-dimensional function problems simultaneously; compared with those of the original datasets, the average classification accuracies obtained on two datasets by SOMAMIF combing with the fractal technology to extract the key home returning constraints from college students with different census register increase by 0.348 66 percentage points and 0.598 57 percentage points respectively.

Reference | Related Articles | Metrics

Select

Communication coverage reduction method of parallel programs based on dominant relation

ZHANG Chen, TIAN Tian, YANG Xiuting, GONG Dunwei

Journal of Computer Applications 2021, 41 (6): 1741-1747. DOI: 10.11772/j.issn.1001-9081.2020091369

Abstract （269）

PDF （944KB）（300）

Save

The increase of communication scale and non-deterministic communication make the communication test of Message-Passing Interface (MPI) parallel programs more difficult. In order to solve the problems, a new method of reducing communication coverage based on dominant relation was proposed. Firstly, based on the correspondence between communications and communication statements, the reduction problem of communications was converted into a reduction problem of communication statements. Then, the dominant relation of statements was used to solve the reduction set of communication statement set. Finally, the communications related to the reduction set were selected as the targets to be covered, so that the test data covering these targets covered all the communications. The proposed method was applied to 7 typical programs under test. Experimental results show that, compared with the test data generation method with all communication as coverage targets, the proposed method can reduce the generation time of test data by up to 95% without reducing the coverage rate of communications, indicating that the proposed method can improve the generation efficiency of communication coverage test data.

Reference | Related Articles | Metrics

Select

Maximum common induced subgraph algorithm based on vertex conflict learning

WANG Yu, LIU Yanli, CHEN Shaowu

Journal of Computer Applications 2021, 41 (6): 1756-1760. DOI: 10.11772/j.issn.1001-9081.2020091381

Abstract （404）

PDF （962KB）（500）

Save

The traditional branching strategies of Maximum Common induced Subgraph (MCS) problem rely on the static properties of graphs and lack learning information about historical searches. In order to solve these problems, a branching strategy based on vertex conflict learning was proposed. Firstly, the reduction value of the upper bound was used as the reward to the branch node for completing a matching action. Secondly, when the optimal solution was updated, the optimal solution obtained actually was the result of continuous inference of the branch nodes. Therefore, the appropriate rewards were given to the branch nodes on the complete search path to strengthen the positive effect of these vertices on search. Finally, the value function of matching action was designed, and the vertices with the maximum cumulative rewards would be selected as new branch nodes. On the basis of Maximum common induced subgraph Split (McSplit) algorithm, an improved McSplit Reinforcement Learning and Routing (McSplitRLR) algorithm combined with the new branching strategy was completed. Experimental results show that, with the same computer and solution time limit, excluding the simple instances solved by all comparison algorithms within 10 seconds, compared to the state-of-the-art algorithms of McSplit and McSplit Solution-Biased Search (McSplitSBS), McSplitRLR solves 109 and 33 more hard instances respectively, and the solution rate increases by 5.6% and 1.6% respectively.

Reference | Related Articles | Metrics

Select

Consensus of two-layer multi-agent systems subjected to cyber-attack

WANG Yunyan, HU Aihua

Journal of Computer Applications 2021, 41 (5): 1399-1405. DOI: 10.11772/j.issn.1001-9081.2020081159

Abstract （438）

PDF （1150KB）（384）

Save

The consensus problem of the two-layer multi-agent systems subjected to cyber-attacks was studied. Aiming at the two-layer multi-agent systems composed of the leaders' layer and the followers' layer, the situation as the following was given:the neighboring agents in the leaders' layer were cooperative, the adjacent agents in the followers' layer were cooperative or competitive, and there was a restraining relationship between some corresponding agents in the leaders' layer and the followers' layer. The consensus problem among the nodes of leaders' layer, followers' layer and two-layer multi-agent systems subjected to cyber-attack was discussed. Based on the related knowledge such as Linear Matrix Inequality (LMI), Lyapunov stability theory and graph theory, the sufficient criteria for consensus between the nodes in the leaders' layer multi-agent system, bipartite consensus between the nodes in the followers' layer multi-agent system and node-to-node bipartite consensus between the nodes in the two-layer multi-agent systems were given. Finally, the numerical simulation examples were given, and the consensus of the two-layer multi-agent systems subjected to cyber-attack was realized, which verified the validity of the proposed criteria.

Reference | Related Articles | Metrics

Select

Coevolutionary ant colony optimization algorithm for mixed-variable optimization problem

WEI Mingyan, CHEN Yu, ZHANG Liang

Journal of Computer Applications 2021, 41 (5): 1412-1418. DOI: 10.11772/j.issn.1001-9081.2020081200

Abstract （330）

PDF （2082KB）（386）

Save

For Mixed-Variable Optimization Problem (MVOP) containing both continuous and categorical variables, a coevolution strategy was proposed to search the mixed-variable decision space, and a Coevolutionary Ant Colony Optimization Algorithm for MVOP (CACOA _MV) was developed. In CACOA _MV, the continuous and categorical sub-populations were generated by using the continuous and discrete Ant Colony Optimization (ACO) strategies respectively, the sub-vectors of continuous and categorical variables were evaluated with the help of cooperators, and the continuous and categorical sub-populations were respectively updated to realize the efficient coevolutionary search in the mixed-variable decision space. Furthermore, the ability of global exploration to the categorical variable solution space was improved by introducing a smoothing mechanism of pheromone, and a "best+random cooperators" restart strategy facing the coevolution framework was proposed to enhance the efficiency of coevolutionary search. By comparing with the Mixed-Variable Ant Colony Optimization (ACO _MV) algorithm and the Success History-based Adaptive Differential Evolution algorithm with linear population size reduction and Ant Colony Optimization (L-SHADE _ACO), it is demonstrated that CACOA _MV is able to perform better local exploitation, so as to improve approximation quality of the final results in the target space; the comparison with the set-based Differential Evolution algorithm with Mixed-Variables (DE _MV) shows that CACOA _MV is able to better approximate the global optimal solutions in the decision space and has better global exploration ability. In conclusion, CACOA _MV with the coevolutionary strategy can keep a balance between global exploration and local exploitation, which results in better optimization ability.

Reference | Related Articles | Metrics

Select

Vehicle number optimization approach of autonomous vehicle fleet driven by multi-spatio-temporal distribution task

ZHENG Liping, WANG Jianqiang, ZHANG Yuzhao, DONG Zuofan

Journal of Computer Applications 2021, 41 (5): 1406-1411. DOI: 10.11772/j.issn.1001-9081.2020081183

Abstract （279）

PDF （1248KB）（706）

Save

A stochastic optimization method was proposed in order to solve the vehicle number allocation problem of the minimum autonomous vehicle fleet driven by spatio-temporal multi-tasks of terminal delivery. Firstly, the influence of service time and waiting time on the route planning of autonomous vehicle fleet was analyzed to build the shortest route model, and the service sequence network was constructed based on the two-dimensional spatio-temporal network. Then, the vehicle number allocation problem of the minimum autonomous vehicle fleet was converted into a network maximum flow problem through the network transformation, and a minimum fleet model was established with the goal of minimizing the vehicle number of the fleet. Finally, the Dijkstra-Dinic algorithm combining Dijkstra algorithm and Dinic algorithm was designed according to the model features in order to solve the vehicle number allocation problem of the minimum autonomous vehicle fleet. Simulation experiments were carried out in four different scales of service networks, the results show that:under different successful service rates, the minimum size of autonomous vehicle fleet is positively correlated with the scale of service network, and it decreases with the increase of waiting time and gradually tends to be stable, the One-stop operator introduced into the proposed algorithm greatly improves the search efficiency, and the proposed model and algorithm are suitable for the calculation of the minimum vehicle fleet in large-scale service network.

Reference | Related Articles | Metrics

Select

Two-stage task offloading strategy based on game theory in cloud-edge environment

WANG Yijie, FAN Jiafei, WANG Chenyu

Journal of Computer Applications 2021, 41 (5): 1392-1398. DOI: 10.11772/j.issn.1001-9081.2020071091

Abstract （367）

PDF （910KB）（572）

Save

Mobile Edge Computing (MEC) provides an effective solution to the conflict between computationally intensive applications and resource constrained mobile devices. However, most studies on the MEC offloading only consider the resource allocation between mobile devices and MEC servers, and ignore the huge computing resources in the cloud computing centers. In order to make full use of cloud and MEC resources, a task offloading strategy of cloud-edge collaboration was proposed. Firstly, the task offloading problem of the cloud-edge servers was transformed into a game problem. Then, the existence and uniqueness of Nash Equilibrium (NE) in this game were proved, and the solution to this game problem was obtained. Finally, a two-stage task offloading algorithm based on game theory was proposed to solve the task offloading scheme, and the performance of this algorithm was evaluated by performance indicators. The simulation results show that the total overhead of using the proposed algorithm is reduced by 72.8%, 47.9%, and 2.65% compared with those of local execution, cloud server execution and MEC server execution, respectively. The numerical results confirm that the proposed strategy can achieve higher energy efficiency and lower task offloading overhead, and extend scale well with the number of mobile devices increases.

Reference | Related Articles | Metrics

Select

Multi-user task offloading strategy based on stable allocation

MAO Yingchi, XU Xuesong, LIU Pengfei

Journal of Computer Applications 2021, 41 (3): 786-793. DOI: 10.11772/j.issn.1001-9081.2020060861

Abstract （329）

PDF （1162KB）（965）

Save

With the emergence of many computation-intensive applications, mobile devices cannot meet user requirements such as delay and energy consumption due to their limited computing capabilities. Mobile Edge Computing (MEC) offloads user task computing to the MEC server through a wireless channel to significantly reduce the response delay and energy consumption of tasks. Concerning the problem of multi-user task offloading, a Multi-User Task Offloading strategy based on Stable Allocation (MUTOSA) was proposed to minimize energy consumption while ensuring the user delay requirement. Firstly, based on the comprehensive consideration of delay and energy consumption, the problem of multi-user task offloading in the independent task scenario was modeled. Then, based on the idea of delayed reception in the stable allocation of game theory, an adjustment strategy was proposed. Finally, the problem of multi-user task unloading was solved through continuous iteration. Experimental results show that, compared with the benchmark strategy and heuristic strategy, the proposed strategy can meet the delay requirements of more users, increase user satisfaction by about 10% on average, and reduce the total energy consumption of user devices by about 50%. It shows that the proposed strategy can effectively reduce energy consumption with ensuring the user delay requirement, and can effectively improve the user experience for delay-sensitive applications.

Reference | Related Articles | Metrics

Select

Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution

RAN Jiamin, NI Zhiwei, PENG Peng, ZHU Xuhui

Journal of Computer Applications 2021, 41 (3): 794-802. DOI: 10.11772/j.issn.1001-9081.2020060940

Abstract （371）

PDF （1196KB）（393）

Save

Focusing on the task allocation problem in spatial crowdsourcing, with the consideration of the influence of the spatial crowdsourcing workers' service quality on the allocation results, a task allocation strategy with the quality evaluation of worker's service was proposed. Firstly, in each spatio-temporal environment, the evaluation element of spatial crowdsourcing workers was added to establish a multi-objective model that fully considers the service quality and distance cost of the workers. Secondly, the algorithm convergence speed was increased and the global optimization ability was improved by improving the initialization and coding strategy, position movement strategy and neighborhood search strategy of the discrete glowworm swarm optimization algorithm. Finally, the improved algorithm was used to solve the model. Experimental results on the simulated and real datasets show that, compared with other swarm intelligence algorithms, the proposed algorithm can improve the total score of task allocation by 2% to 25% on datasets with different scales. By considering the service quality of workers, the proposed algorithm can effectively improve the efficiency of task allocation and the final total score.

Reference | Related Articles | Metrics

Select

Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem

LI Ping, WANG Fen, CHEN Qidong, SUN Jun

Journal of Computer Applications 2021, 41 (3): 803-811. DOI: 10.11772/j.issn.1001-9081.2020060800

Abstract （288）

PDF （1095KB）（458）

Save

For solving the problem of multi-objective community detection in complex network, a Discrete Random Drift Particle Swarm Optimization (DRDPSO) algorithm was proposed. Firstly, by performing random coding operation on communities and using discretization operation for random drift optimization algorithm, the local network structure was improved and the global modularity value was gradually enhanced. Secondly, two objective functions, Kernel K-Means (KKM) and Ratio Cut (RC), were used to control the community size in the network and ameliorate the modularity resolution ratio. Finally, the Pareto non-inferior solution sets were updated step by step according to the multi-objective solving strategy, and the objective community structures satisfying the requirements were selected from the Pareto non-inferior solution sets. To verify the effectiveness of proposed algorithm, the comparison experiments of DRDPSO algorithm with other community detection algorithms were carried out on three generation networks with 10 different parameter configurations and three real networks. And the community detection results obtained by different algorithms were compared and analyzed by using two evaluation indicators of best community. Experimental results show that using DRDPSO algorithm for solving the multi-objective community detection problem in complex network, the probability of obtaining the highest community detection evaluation indexes (normalized mutual information and modularity) is more than 95%. The application of DRDPSO algorithm in real network can further improve the accuracy and robustness of network community division.

Reference | Related Articles | Metrics

Select

Design of FPGA accelerator with high parallelism for convolution neural network

WANG Xiaofeng, JIANG Penglong, ZHOU Hui, ZHAO Xiongbo

Journal of Computer Applications 2021, 41 (3): 812-819. DOI: 10.11772/j.issn.1001-9081.2020060996

Abstract （581）

PDF （1115KB）（778）

Save

Most of the algorithms based on Convolutional Neural Network (CNN) are computation-intensive and memory-intensive, so they are difficult to be applied in embedded fields such as aerospace, mobile robotics and smartphones which have low-power requirements. To solve this problem, a Field Programmable Gate Array (FPGA) accelerator with high parallelism for CNN was proposed. Firstly, four kinds of parallelism in CNN algorithm that can be used for FPGA acceleration were compared and studied. Then, a Multi-channel Convolutional Rotating-register Pipeline (MCRP) structure was proposed to concisely and effectively utilize the convolution kernel parallelism of CNN algorithm. Finally, using the strategy of input/output channel parallelism+convolution kernel parallelism, a CNN accelerator architecture with high parallelism was proposed based on MCRP structure, and to verify the design rationality of the architecture, it was deployed on the XCZU9EG chip of XILINX. Under the condition of making full use of the on-chip Digital Signal Processor (DSP) resources, the peak computing capacity of the proposed CNN accelerator reached 2 304 GOPS(Giga Operations Per Second). Taking SSD-300 algorithm as the test object, this CNN accelerator had the actual computing capacity of 1 830.33 GOPS, and the hardware utilization rate of 79.44%. Experimental results show that, the MCRP structure can effectively improve the computing capacity of CNN accelerator, and the CNN accelerator based on MCRP structure can generally meet the computing capacity requirements of most applications in the embedded fields.

Reference | Related Articles | Metrics

Select

Binary particle swarm optimization algorithm based on novel S-shape transfer function for knapsack problem with a single continuous variable

WANG Zekun, HE Yichao, LI Huanzhe, ZHANG Fazhan

Journal of Computer Applications 2021, 41 (2): 461-469. DOI: 10.11772/j.issn.1001-9081.2020050710

Abstract （249）

PDF （1113KB）（435）

Save

In order to solve the Knapsack Problem with a single Continuous variable (KPC) efficiently, a novel S-shape transfer function based on Gauss error function was proposed, and a new approach of transforming a real vector into a 0-1 vector by using the proposed transfer function was given, thereby a New Binary Particle Swarm Optimization algorithm (NBPSO) was proposed. Then, based on the second mathematical model of KPC and the combination of NBPSO and the effective algorithm to deal with the infeasible solutions of KPC, a new approach to solve KPC was proposed. For validating the performance of NBPSO in solving KPS, NBPSO was utilized to solve four kinds of large-scale KPC instances, and the obtained calculation results were compared with those of Binary Particle Swarm Optimization algorithms (BPSOs) based on other S and V-shape transfer functions, Single-population Binary Differential Evolution with Hybrid encoding (S-HBDE), Bi-population Binary Differential Evolution with Hybrid encoding (B-HBDE) and Binary Particle Swarm Optimization algorithm (BPSO). The comparison results show that NBPSO is superior to the comparison algorithms in average calculation result and stability, illustrating that NBPSO has the performance better than other algorithms.

Reference | Related Articles | Metrics

Project Articles