The distributed permutation flow shop scheduling problem(DPFSP)has received increasing attention in recent years.The iterated greedy algorithm(IGA)serves as a powerful optimizer for addressing such a problem because o...The distributed permutation flow shop scheduling problem(DPFSP)has received increasing attention in recent years.The iterated greedy algorithm(IGA)serves as a powerful optimizer for addressing such a problem because of its straightforward,single-solution evolution framework.However,a potential draw-back of IGA is the lack of utilization of historical information,which could lead to an imbalance between exploration and exploitation,especially in large-scale DPFSPs.As a consequence,this paper develops an IGA with memory and learning mechanisms(MLIGA)to efficiently solve the DPFSP targeted at the mini-malmakespan.InMLIGA,we incorporate a memory mechanism to make a more informed selection of the initial solution at each stage of the search,by extending,reconstructing,and reinforcing the information from previous solutions.In addition,we design a twolayer cooperative reinforcement learning approach to intelligently determine the key parameters of IGA and the operations of the memory mechanism.Meanwhile,to ensure that the experience generated by each perturbation operator is fully learned and to reduce the prior parameters of MLIGA,a probability curve-based acceptance criterion is proposed by combining a cube root function with custom rules.At last,a discrete adaptive learning rate is employed to enhance the stability of the memory and learningmechanisms.Complete ablation experiments are utilized to verify the effectiveness of the memory mechanism,and the results show that this mechanism is capable of improving the performance of IGA to a large extent.Furthermore,through comparative experiments involving MLIGA and five state-of-the-art algorithms on 720 benchmarks,we have discovered that MLI-GA demonstrates significant potential for solving large-scale DPFSPs.This indicates that MLIGA is well-suited for real-world distributed flow shop scheduling.展开更多
This study presents a novel hybrid topology optimization and mold design framework that integrates process fitting,runner system optimization,and structural analysis to significantly enhance the performance of injecti...This study presents a novel hybrid topology optimization and mold design framework that integrates process fitting,runner system optimization,and structural analysis to significantly enhance the performance of injection-molded parts.At its core,the framework employs a greedy algorithm that generates runner systems based on adjacency and shortest path principles,leading to improvements in both mechanical strength and material efficiency.The design optimization is validated through a series of rigorous experimental tests,including three-point bending and torsion tests performed on key-socket frames,ensuring that the optimized designs meet practical performance requirements.A critical innovation of the framework is the development of the Adjacent Element Temperature-Driven Prestress Algorithm(AETDPA),which refines the prediction of mechanical failure and strength fitting.This algorithm has been shown to deliver mesh-independent accuracy,thereby enhancing the reliability of simulation results across various design iterations.The framework’s adaptability is further demonstrated by its ability to adjust optimization methods based on the unique geometry of each part,thus accelerating the overall design process while ensuring struc-tural integrity.In addition to its immediate applications in injection molding,the study explores the potential extension of this framework to metal additive manufacturing,opening new avenues for its use in advanced manufacturing technologies.Numerical simulations,including finite element analysis,support the experimental findings and confirm that the optimized designs provide a balanced combination of strength,durability,and efficiency.Furthermore,the integration challenges with existing injection molding practices are addressed,underscoring the framework’s scalability and industrial relevance.Overall,this hybrid topology optimization framework offers a computationally efficient and robust solution for advanced manufacturing applications,promising significant improvements in design efficiency,cost-effectiveness,and product performance.Future work will focus on further enhancing algorithm robustness and exploring additional applications across diverse manufacturing processes.展开更多
Effective path planning is crucial for mobile robots to quickly reach rescue destination and complete rescue tasks in a post-disaster scenario.In this study,we investigated the post-disaster rescue path planning probl...Effective path planning is crucial for mobile robots to quickly reach rescue destination and complete rescue tasks in a post-disaster scenario.In this study,we investigated the post-disaster rescue path planning problem and modeled this problem as a variant of the travel salesman problem(TSP)with life-strength constraints.To address this problem,we proposed an improved iterated greedy(IIG)algorithm.First,a push-forward insertion heuristic(PFIH)strategy was employed to generate a high-quality initial solution.Second,a greedy-based insertion strategy was designed and used in the destruction-construction stage to increase the algorithm’s exploration ability.Furthermore,three problem-specific swap operators were developed to improve the algorithm’s exploitation ability.Additionally,an improved simulated annealing(SA)strategy was used as an acceptance criterion to effectively prevent the algorithm from falling into local optima.To verify the effectiveness of the proposed algorithm,the Solomon dataset was extended to generate 27 instances for simulation.Finally,the proposed IIG was compared with five state-of-the-art algorithms.The parameter analysiswas conducted using the design of experiments(DOE)Taguchi method,and the effectiveness analysis of each component has been verified one by one.Simulation results indicate that IIGoutperforms the compared algorithms in terms of the number of rescue survivors and convergence speed,proving the effectiveness of the proposed algorithm.展开更多
With continuous advancements in artificial intelligence(AI), automatic piano-playing robots have become subjects of cross-disciplinary interest. However, in most studies, these robots served merely as objects of obser...With continuous advancements in artificial intelligence(AI), automatic piano-playing robots have become subjects of cross-disciplinary interest. However, in most studies, these robots served merely as objects of observation with limited user engagement or interaction. To address this issue, we propose a user-friendly and innovative interaction system based on the principles of greedy algorithms. This system features three modules: score management, performance control, and keyboard interactions. Upon importing a custom score or playing a note via an external device, the system performs on a virtual piano in line with user inputs. This system has been successfully integrated into our dexterous manipulator-based piano-playing device, which significantly enhances user interactions.展开更多
Flow shop scheduling problem with time lags is a practical scheduling problem and attracts many studies. Permutation problem（PFSP with time lags） is concentrated but non-permutation problem（non-PFSP with time lags...Flow shop scheduling problem with time lags is a practical scheduling problem and attracts many studies. Permutation problem（PFSP with time lags） is concentrated but non-permutation problem（non-PFSP with time lags） seems to be neglected. With the aim to minimize the makespan and satisfy time lag constraints, efficient algo- rithms corresponding to PFSP and non-PFSP problems are proposed, which consist of iterated greedy algorithm for permutation（IGTLP） and iterated greedy algorithm for non-permutation （IGTLNP）. The proposed algorithms are verified using well-known simple and complex instances of permutation and non-permutation problems with various time lag ranges. The permutation results indicate that the proposed IGTLP can reach near optimal solution within nearly 11% computational time of traditional GA approach. The non-permutation results indicate that the proposed IG can reach nearly same solution within less than 1% com- putational time compared with traditional GA approach. The proposed research combines PFSP and non-PFSP together with minimal and maximal time lag consideration, which provides an interesting viewpoint for industrial implementation.展开更多
The density-based clustering algorithm presented is different from the classical Density-Based Spatial Clustering of Applications with Noise (DBSCAN) (Ester et al., 1996), and has the following advantages: first, Gree...The density-based clustering algorithm presented is different from the classical Density-Based Spatial Clustering of Applications with Noise (DBSCAN) (Ester et al., 1996), and has the following advantages: first, Greedy algorithm substitutes for R*-tree (Bechmann et al., 1990) in DBSCAN to index the clustering space so that the clustering time cost is decreased to great extent and I/O memory load is reduced as well; second, the merging condition to approach to arbitrary-shaped clusters is designed carefully so that a single threshold can distinguish correctly all clusters in a large spatial dataset though some density-skewed clusters live in it. Finally, authors investigate a robotic navigation and test two artificial datasets by the proposed algorithm to verify its effectiveness and efficiency.展开更多
This paper extends the application of compressive sensing(CS) to the radar reconnaissance receiver for receiving the multi-narrowband signal. By combining the concept of the block sparsity, the self-adaption methods, ...This paper extends the application of compressive sensing(CS) to the radar reconnaissance receiver for receiving the multi-narrowband signal. By combining the concept of the block sparsity, the self-adaption methods, the binary tree search,and the residual monitoring mechanism, two adaptive block greedy algorithms are proposed to achieve a high probability adaptive reconstruction. The use of the block sparsity can greatly improve the efficiency of the support selection and reduce the lower boundary of the sub-sampling rate. Furthermore, the addition of binary tree search and monitoring mechanism with two different supports self-adaption methods overcome the instability caused by the fixed block length while optimizing the recovery of the unknown signal.The simulations and analysis of the adaptive reconstruction ability and theoretical computational complexity are given. Also, we verify the feasibility and effectiveness of the two algorithms by the experiments of receiving multi-narrowband signals on an analogto-information converter(AIC). Finally, an optimum reconstruction characteristic of two algorithms is found to facilitate efficient reception in practical applications.展开更多
Nonlinear m-term approximation plays an important role in machine learning, signal processing and statistical estimating. In this paper by means of a nondecreasing dominated function, a greedy adaptive compression num...Nonlinear m-term approximation plays an important role in machine learning, signal processing and statistical estimating. In this paper by means of a nondecreasing dominated function, a greedy adaptive compression numerical algorithm in the best m -term approximation with regard to tensor product wavelet-type basis is pro-posed. The algorithm provides the asymptotically optimal approximation for the class of periodic functions with mixed Besov smoothness in the L q norm. Moreover, it depends only on the expansion of function f by tensor pro-duct wavelet-type basis, but neither on q nor on any special features of f.展开更多
Using a relaying system to provide spatial diversity and improve the system performance is a tendency in the wireless cooperative communications. Amplify-and-forward （AF） mode with a low complexity is easy to be imp...Using a relaying system to provide spatial diversity and improve the system performance is a tendency in the wireless cooperative communications. Amplify-and-forward （AF） mode with a low complexity is easy to be implemented. Under the consideration of cooperative communication systems, the scenario includes one information source, M relay stations and N destinations. This work proposes a relay selection algorithm in the Raleigh fading channel. Based on the exhaustive search method, easily to realize, the optimal selection scheme can be found with a highly complicated calculation. In order to reduce the computational complexity, an approximate optimal solution with a greedy algorithm applied for the relay station selection is proposed. With different situations of the communication systems, the performance evaluation obtained by both the proposed algorithm and the exhaustive search algorithm are given for comparison. It shows the proposed algorithm could provide a solution approach to the optimal one.展开更多
With the rapid development of civil aviation in recent years,the management and assignment of airport resources are becoming more and more difficult.Among the various airport resources,gates and taxiways are very impo...With the rapid development of civil aviation in recent years,the management and assignment of airport resources are becoming more and more difficult.Among the various airport resources,gates and taxiways are very important,therefore,many researchers focus on the airport gate and taxiway assignment problem.However,the joint assignment algorithm of airport gates and taxiways with realistic airport data has not been well studied.A greedy algorithm based on joint assignment of airport gates and taxiways using the data of a large hub airport in China is proposed.The objective is maximizing the ratio of fixed gates and minimizing the ratio of taxiway collisions.Simulation results show that it outperforms other assignment schemes.展开更多
Reconfigurable battery systems(RBSs)provide a promising alternative to traditional battery systems due to their flexible and dynamically changeable topological structures that can be adapted to different battery charg...Reconfigurable battery systems(RBSs)provide a promising alternative to traditional battery systems due to their flexible and dynamically changeable topological structures that can be adapted to different battery charging and discharging strategies.A critical system parameter known as the maximum allowable current(MAC)is pivotal to RBS operation.This parameter is instrumental in maintaining the current of each individual battery within a safe range and serves as a guiding indicator for the system’s reconfiguration,ensuring its safety and reliability.This paper proposes a method for calculating the MAC of an arbitrary RBS using a greedy algorithm in conjunction with a directed graph model of the RBS.Using the shortest path of the battery,the greedy algorithm transforms the exhaustion of the switch states in the brute-force algorithm or variable search without utilizing structures in the heuristic algorithms in the combination of the shortest paths.The directed graph model,based on an equivalent circuit,provides a specific method for calculating the MAC of a given structure.The proposed method is validated using 2 previously published RBS structures and an additional one with a more complex structure.The results are the same as those from the brute-force algorithm,but the proposed method substantially improves the computational efficiency,being theoretically N_(s)2^(N_(s))−^(N_(b))log_(10)N_(b) times faster than the brute-force algorithm for an RBS with N_(b) batteries and N_(s) switches.Another advantage of the proposed method is its ability to calculate the MAC of RBSs with arbitrary structures and variable batteries,even in scenarios with random isolated batteries.展开更多
Internet of things networks often suffer from early node failures and short lifespan due to energy limits.Traditional routing methods are not enough.This work proposes a new hybrid algorithm called ACOGA.It combines A...Internet of things networks often suffer from early node failures and short lifespan due to energy limits.Traditional routing methods are not enough.This work proposes a new hybrid algorithm called ACOGA.It combines Ant Colony Optimization(ACO)and the Greedy Algorithm(GA).ACO finds smart paths while Greedy makes quick decisions.This improves energy use and performance.ACOGA outperforms Hybrid Energy-Efficient(HEE)and Adaptive Lossless Data Compression(ALDC)algorithms.After 500 rounds,only 5%of ACOGA’s nodes are dead,compared to 15%for HEE and 20%for ALDC.The network using ACOGA runs for 1200 rounds before the first nodes fail.HEE lasts 900 rounds and ALDC only 850.ACOGA saves at least 15%more energy by better distributing the load.It also achieves a 98%packet delivery rate.The method works well in mixed IoT networks like Smart Water Management Systems(SWMS).These systems have different power levels and communication ranges.The simulation of proposed model has been done in MATLAB simulator.The results show that that the proposed model outperform then the existing models.展开更多
A connected and undirected graph model of active distribution networks with considering the function of interconnecting switches is constructed in this paper.Based on this model,the island partition problem of active ...A connected and undirected graph model of active distribution networks with considering the function of interconnecting switches is constructed in this paper.Based on this model,the island partition problem of active distribution networks can be described as a 1-neighbour knapsack problem.An effective heuristic algorithm named prospective greedy algorithm is then proposed to solve this problem.Case studies on PG&E 69-bus network show the validity of the proposed model and algorithm.展开更多
The distributed hybrid flow shop scheduling problem(DHFSP),which integrates distributed manufacturing models with parallel machines,has gained significant attention.However,in actual scheduling,some adjacent machines ...The distributed hybrid flow shop scheduling problem(DHFSP),which integrates distributed manufacturing models with parallel machines,has gained significant attention.However,in actual scheduling,some adjacent machines do not have buffers between them,resulting in blocking.This paper focuses on addressing the DHFSP with blocking constraints(DBHFSP)based on the actual production conditions.To solve DBHFSP,we construct a mixed integer linear programming(MILP)model for DBHFSP and validate its correctness using the Gurobi solver.Then,an advanced iterated greedy(AIG)algorithm is designed to minimize the makespan,in which we modify the Nawaz,Enscore,and Ham(NEH)heuristic to solve blocking constraints.To balance the global and local search capabilities of AIG,two effective inter-factory neighborhood search strategies and a swap-based local search strategy are designed.Additionally,each factory is mutually independent,and the movement within one factory does not affect the others.In view of this,we specifically designed a memory-based decoding method for insertion operations to reduce the computation time of the objective.Finally,two shaking strategies are incorporated into the algorithm to mitigate premature convergence.Five advanced algorithms are used to conduct comparative experiments with AIG on 80 test instances,and experimental results illustrate that the makespan and the relative percentage increase(RPI)obtained by AIG are 1.0%and 86.1%,respectively,better than the comparative algorithms.展开更多
With the wide application of automated guided vehicles(AGVs) in large scale outdoor scenarios with complex terrain,the collaborative work of a large number of AGVs becomes the main trend.The effective multi-agent path...With the wide application of automated guided vehicles(AGVs) in large scale outdoor scenarios with complex terrain,the collaborative work of a large number of AGVs becomes the main trend.The effective multi-agent path finding(MAPF) algorithm is urgently needed to ensure the efficiency and realizability of the whole system. The complex terrain of outdoor scenarios is fully considered by using different values of passage cost to quantify different terrain types. The objective of the MAPF problem is to minimize the cost of passage while the Manhattan distance of paths and the time of passage are also evaluated for a comprehensive comparison. The pre-path-planning and real-time-conflict based greedy(PRG) algorithm is proposed as the solution. Simulation is conducted and the proposed PRG algorithm is compared with waiting-stop A^(*) and conflict based search(CBS) algorithms. Results show that the PRG algorithm outperforms the waiting-stop A^(*) algorithm in all three performance indicators,and it is more applicable than the CBS algorithm when a large number of AGVs are working collaboratively with frequent collisions.展开更多
Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications,such as simplification of social networks,least squares problems,and numerical solution of symmetric posit...Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications,such as simplification of social networks,least squares problems,and numerical solution of symmetric positive definite linear systems.In this paper,inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit(OMP),we introduce a deterministic,greedy edge selection algorithm,which is called the universal greedy approach(UGA)for the graph sparsification problem.For a general spectral sparsification problem,e.g.,the positive subset selection problem from a set of m vectors in R n,we propose a nonnegative UGA algorithm which needs O(mn^(2)+n^(3)/ϵ^(2))time to find a 1+ϵ/β/1-ϵ/β-spectral sparsifier with positive coefficients with sparsity at most[n/ϵ^(2)],where β is the ratio between the smallest length and largest length of the vectors.The convergence of the nonnegative UGA algorithm is established.For the graph sparsification problem,another UGA algorithm is proposed which can output a 1+O(ϵ)/1-O(ϵ)-spectral sparsifier with[n/ϵ^(2)]edges in O(m+n^(2)/ϵ^(2))time from a graph with m edges and n vertices under some mild assumptions.This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for.The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear,i.e.O(m^(1+o(1)))for some o(1)=O((log log(m))^(2/3)/log^(1/3)(m)).Finally,extensive experimental results,including applications to graph clustering and least squares regression,show the effectiveness of proposed approaches.展开更多
We investigate the efficiency of weak greedy algorithms for m-term expansional approximation with respect to quasi-greedy bases in general Banach spaces.We estimate the corresponding Lebesgue constants for the weak th...We investigate the efficiency of weak greedy algorithms for m-term expansional approximation with respect to quasi-greedy bases in general Banach spaces.We estimate the corresponding Lebesgue constants for the weak thresholding greedy algorithm（WTGA） and weak Chebyshev thresholding greedy algorithm.Then we discuss the greedy approximation on some function classes.For some sparse classes induced by uniformly bounded quasi-greedy bases of L_p,12 the WCGA is better than the TGA.展开更多
The development of technologies such as big data and blockchain has brought convenience to life,but at the same time,privacy and security issues are becoming more and more prominent.The K-anonymity algorithm is an eff...The development of technologies such as big data and blockchain has brought convenience to life,but at the same time,privacy and security issues are becoming more and more prominent.The K-anonymity algorithm is an effective and low computational complexity privacy-preserving algorithm that can safeguard users’privacy by anonymizing big data.However,the algorithm currently suffers from the problem of focusing only on improving user privacy while ignoring data availability.In addition,ignoring the impact of quasi-identified attributes on sensitive attributes causes the usability of the processed data on statistical analysis to be reduced.Based on this,we propose a new K-anonymity algorithm to solve the privacy security problem in the context of big data,while guaranteeing improved data usability.Specifically,we construct a new information loss function based on the information quantity theory.Considering that different quasi-identification attributes have different impacts on sensitive attributes,we set weights for each quasi-identification attribute when designing the information loss function.In addition,to reduce information loss,we improve K-anonymity in two ways.First,we make the loss of information smaller than in the original table while guaranteeing privacy based on common artificial intelligence algorithms,i.e.,greedy algorithm and 2-means clustering algorithm.In addition,we improve the 2-means clustering algorithm by designing a mean-center method to select the initial center of mass.Meanwhile,we design the K-anonymity algorithm of this scheme based on the constructed information loss function,the improved 2-means clustering algorithm,and the greedy algorithm,which reduces the information loss.Finally,we experimentally demonstrate the effectiveness of the algorithm in improving the effect of 2-means clustering and reducing information loss.展开更多
Chip multiprocessors(CMPs) allow thread level parallelism,thus increasing performance.However,this comes with the cost of temperature problem.CMPs require more power,creating non uniform power map and hotspots.Aiming ...Chip multiprocessors(CMPs) allow thread level parallelism,thus increasing performance.However,this comes with the cost of temperature problem.CMPs require more power,creating non uniform power map and hotspots.Aiming at this problem,a thread scheduling algorithm,the greedy scheduling algorithm,was proposed to reduce the thermal emergencies and to improve the throughput.The greedy scheduling algorithm was implemented in the Linux kernel on Intel's Quad-Core system.The experimental results show that the greedy scheduling algorithm can reduce 9.6%-78.5% of the hardware dynamic thermal management(DTM) in various combinations of workloads,and has an average of 5.2% and up to 9.7% throughput higher than the Linux standard scheduler.展开更多
This paper presents a framework for constructing surrogate models for sensitivity analysis of structural dynamics behavior.Physical models involving deformation,such as collisions,vibrations,and penetration,are devel-...This paper presents a framework for constructing surrogate models for sensitivity analysis of structural dynamics behavior.Physical models involving deformation,such as collisions,vibrations,and penetration,are devel-oped using the material point method.To reduce the computational cost of Monte Carlo simulations,response surface models are created as surrogate models for the material point system to approximate its dynamic behavior.An adaptive randomized greedy algorithm is employed to construct a sparse polynomial chaos expansion model with a fixed order,effectively balancing the accuracy and computational efficiency of the surrogate model.Based on the sparse polynomial chaos expansion,sensitivity analysis is conducted using the global finite difference and Sobol methods.Several examples of structural dynamics are provided to demonstrate the effectiveness of the proposed method in addressing structural dynamics problems.展开更多
基金supported in part by the National Key Research and Development Program of China under Grant No.2021YFF0901300in part by the National Natural Science Foundation of China under Grant Nos.62173076 and 72271048.
文摘The distributed permutation flow shop scheduling problem(DPFSP)has received increasing attention in recent years.The iterated greedy algorithm(IGA)serves as a powerful optimizer for addressing such a problem because of its straightforward,single-solution evolution framework.However,a potential draw-back of IGA is the lack of utilization of historical information,which could lead to an imbalance between exploration and exploitation,especially in large-scale DPFSPs.As a consequence,this paper develops an IGA with memory and learning mechanisms(MLIGA)to efficiently solve the DPFSP targeted at the mini-malmakespan.InMLIGA,we incorporate a memory mechanism to make a more informed selection of the initial solution at each stage of the search,by extending,reconstructing,and reinforcing the information from previous solutions.In addition,we design a twolayer cooperative reinforcement learning approach to intelligently determine the key parameters of IGA and the operations of the memory mechanism.Meanwhile,to ensure that the experience generated by each perturbation operator is fully learned and to reduce the prior parameters of MLIGA,a probability curve-based acceptance criterion is proposed by combining a cube root function with custom rules.At last,a discrete adaptive learning rate is employed to enhance the stability of the memory and learningmechanisms.Complete ablation experiments are utilized to verify the effectiveness of the memory mechanism,and the results show that this mechanism is capable of improving the performance of IGA to a large extent.Furthermore,through comparative experiments involving MLIGA and five state-of-the-art algorithms on 720 benchmarks,we have discovered that MLI-GA demonstrates significant potential for solving large-scale DPFSPs.This indicates that MLIGA is well-suited for real-world distributed flow shop scheduling.
文摘This study presents a novel hybrid topology optimization and mold design framework that integrates process fitting,runner system optimization,and structural analysis to significantly enhance the performance of injection-molded parts.At its core,the framework employs a greedy algorithm that generates runner systems based on adjacency and shortest path principles,leading to improvements in both mechanical strength and material efficiency.The design optimization is validated through a series of rigorous experimental tests,including three-point bending and torsion tests performed on key-socket frames,ensuring that the optimized designs meet practical performance requirements.A critical innovation of the framework is the development of the Adjacent Element Temperature-Driven Prestress Algorithm(AETDPA),which refines the prediction of mechanical failure and strength fitting.This algorithm has been shown to deliver mesh-independent accuracy,thereby enhancing the reliability of simulation results across various design iterations.The framework’s adaptability is further demonstrated by its ability to adjust optimization methods based on the unique geometry of each part,thus accelerating the overall design process while ensuring struc-tural integrity.In addition to its immediate applications in injection molding,the study explores the potential extension of this framework to metal additive manufacturing,opening new avenues for its use in advanced manufacturing technologies.Numerical simulations,including finite element analysis,support the experimental findings and confirm that the optimized designs provide a balanced combination of strength,durability,and efficiency.Furthermore,the integration challenges with existing injection molding practices are addressed,underscoring the framework’s scalability and industrial relevance.Overall,this hybrid topology optimization framework offers a computationally efficient and robust solution for advanced manufacturing applications,promising significant improvements in design efficiency,cost-effectiveness,and product performance.Future work will focus on further enhancing algorithm robustness and exploring additional applications across diverse manufacturing processes.
基金supported by the Opening Fund of Shandong Provincial Key Laboratory of Network based Intelligent Computing,the National Natural Science Foundation of China(52205529,61803192)the Natural Science Foundation of Shandong Province(ZR2021QE195)+1 种基金the Youth Innovation Team Program of Shandong Higher Education Institution(2023KJ206)the Guangyue Youth Scholar Innovation Talent Program support received from Liaocheng University(LCUGYTD2022-03).
文摘Effective path planning is crucial for mobile robots to quickly reach rescue destination and complete rescue tasks in a post-disaster scenario.In this study,we investigated the post-disaster rescue path planning problem and modeled this problem as a variant of the travel salesman problem(TSP)with life-strength constraints.To address this problem,we proposed an improved iterated greedy(IIG)algorithm.First,a push-forward insertion heuristic(PFIH)strategy was employed to generate a high-quality initial solution.Second,a greedy-based insertion strategy was designed and used in the destruction-construction stage to increase the algorithm’s exploration ability.Furthermore,three problem-specific swap operators were developed to improve the algorithm’s exploitation ability.Additionally,an improved simulated annealing(SA)strategy was used as an acceptance criterion to effectively prevent the algorithm from falling into local optima.To verify the effectiveness of the proposed algorithm,the Solomon dataset was extended to generate 27 instances for simulation.Finally,the proposed IIG was compared with five state-of-the-art algorithms.The parameter analysiswas conducted using the design of experiments(DOE)Taguchi method,and the effectiveness analysis of each component has been verified one by one.Simulation results indicate that IIGoutperforms the compared algorithms in terms of the number of rescue survivors and convergence speed,proving the effectiveness of the proposed algorithm.
基金Supported by the Natural Science Foundation of China(62072388)Public Technology Service Platform Project of Xiamen City(3502Z20231043)Fujian Sunshine Charity Foundation.
文摘With continuous advancements in artificial intelligence(AI), automatic piano-playing robots have become subjects of cross-disciplinary interest. However, in most studies, these robots served merely as objects of observation with limited user engagement or interaction. To address this issue, we propose a user-friendly and innovative interaction system based on the principles of greedy algorithms. This system features three modules: score management, performance control, and keyboard interactions. Upon importing a custom score or playing a note via an external device, the system performs on a virtual piano in line with user inputs. This system has been successfully integrated into our dexterous manipulator-based piano-playing device, which significantly enhances user interactions.
基金Supported by National Natural Science Foundation of China(Grant No.71301008)Beijing Municipal Natural Science Foundation of China(Grant No.9144030)
文摘Flow shop scheduling problem with time lags is a practical scheduling problem and attracts many studies. Permutation problem（PFSP with time lags） is concentrated but non-permutation problem（non-PFSP with time lags） seems to be neglected. With the aim to minimize the makespan and satisfy time lag constraints, efficient algo- rithms corresponding to PFSP and non-PFSP problems are proposed, which consist of iterated greedy algorithm for permutation（IGTLP） and iterated greedy algorithm for non-permutation （IGTLNP）. The proposed algorithms are verified using well-known simple and complex instances of permutation and non-permutation problems with various time lag ranges. The permutation results indicate that the proposed IGTLP can reach near optimal solution within nearly 11% computational time of traditional GA approach. The non-permutation results indicate that the proposed IG can reach nearly same solution within less than 1% com- putational time compared with traditional GA approach. The proposed research combines PFSP and non-PFSP together with minimal and maximal time lag consideration, which provides an interesting viewpoint for industrial implementation.
文摘The density-based clustering algorithm presented is different from the classical Density-Based Spatial Clustering of Applications with Noise (DBSCAN) (Ester et al., 1996), and has the following advantages: first, Greedy algorithm substitutes for R*-tree (Bechmann et al., 1990) in DBSCAN to index the clustering space so that the clustering time cost is decreased to great extent and I/O memory load is reduced as well; second, the merging condition to approach to arbitrary-shaped clusters is designed carefully so that a single threshold can distinguish correctly all clusters in a large spatial dataset though some density-skewed clusters live in it. Finally, authors investigate a robotic navigation and test two artificial datasets by the proposed algorithm to verify its effectiveness and efficiency.
基金supported by the National Natural Science Foundation of China(61172159)
文摘This paper extends the application of compressive sensing(CS) to the radar reconnaissance receiver for receiving the multi-narrowband signal. By combining the concept of the block sparsity, the self-adaption methods, the binary tree search,and the residual monitoring mechanism, two adaptive block greedy algorithms are proposed to achieve a high probability adaptive reconstruction. The use of the block sparsity can greatly improve the efficiency of the support selection and reduce the lower boundary of the sub-sampling rate. Furthermore, the addition of binary tree search and monitoring mechanism with two different supports self-adaption methods overcome the instability caused by the fixed block length while optimizing the recovery of the unknown signal.The simulations and analysis of the adaptive reconstruction ability and theoretical computational complexity are given. Also, we verify the feasibility and effectiveness of the two algorithms by the experiments of receiving multi-narrowband signals on an analogto-information converter(AIC). Finally, an optimum reconstruction characteristic of two algorithms is found to facilitate efficient reception in practical applications.
基金Supported by National Natural Science Foundation of China (No. 60872161, 10501026, 60675010 and 10626029)Natural Science Foundation of Tianjin (No. 08JCYBJC09600)China Postdoctoral Science Foundation ( No. 20070420708).
文摘Nonlinear m-term approximation plays an important role in machine learning, signal processing and statistical estimating. In this paper by means of a nondecreasing dominated function, a greedy adaptive compression numerical algorithm in the best m -term approximation with regard to tensor product wavelet-type basis is pro-posed. The algorithm provides the asymptotically optimal approximation for the class of periodic functions with mixed Besov smoothness in the L q norm. Moreover, it depends only on the expansion of function f by tensor pro-duct wavelet-type basis, but neither on q nor on any special features of f.
基金supported by National Science Council under Grant No.101-2221-E-029-020-MY3
文摘Using a relaying system to provide spatial diversity and improve the system performance is a tendency in the wireless cooperative communications. Amplify-and-forward （AF） mode with a low complexity is easy to be implemented. Under the consideration of cooperative communication systems, the scenario includes one information source, M relay stations and N destinations. This work proposes a relay selection algorithm in the Raleigh fading channel. Based on the exhaustive search method, easily to realize, the optimal selection scheme can be found with a highly complicated calculation. In order to reduce the computational complexity, an approximate optimal solution with a greedy algorithm applied for the relay station selection is proposed. With different situations of the communication systems, the performance evaluation obtained by both the proposed algorithm and the exhaustive search algorithm are given for comparison. It shows the proposed algorithm could provide a solution approach to the optimal one.
基金the National Natural Science Foundation of China(No.U1633115,61571021)the Science and Technology Foundation of Beijing Municipal Commission of Education(No.KM201810005027).
文摘With the rapid development of civil aviation in recent years,the management and assignment of airport resources are becoming more and more difficult.Among the various airport resources,gates and taxiways are very important,therefore,many researchers focus on the airport gate and taxiway assignment problem.However,the joint assignment algorithm of airport gates and taxiways with realistic airport data has not been well studied.A greedy algorithm based on joint assignment of airport gates and taxiways using the data of a large hub airport in China is proposed.The objective is maximizing the ratio of fixed gates and minimizing the ratio of taxiway collisions.Simulation results show that it outperforms other assignment schemes.
文摘Reconfigurable battery systems(RBSs)provide a promising alternative to traditional battery systems due to their flexible and dynamically changeable topological structures that can be adapted to different battery charging and discharging strategies.A critical system parameter known as the maximum allowable current(MAC)is pivotal to RBS operation.This parameter is instrumental in maintaining the current of each individual battery within a safe range and serves as a guiding indicator for the system’s reconfiguration,ensuring its safety and reliability.This paper proposes a method for calculating the MAC of an arbitrary RBS using a greedy algorithm in conjunction with a directed graph model of the RBS.Using the shortest path of the battery,the greedy algorithm transforms the exhaustion of the switch states in the brute-force algorithm or variable search without utilizing structures in the heuristic algorithms in the combination of the shortest paths.The directed graph model,based on an equivalent circuit,provides a specific method for calculating the MAC of a given structure.The proposed method is validated using 2 previously published RBS structures and an additional one with a more complex structure.The results are the same as those from the brute-force algorithm,but the proposed method substantially improves the computational efficiency,being theoretically N_(s)2^(N_(s))−^(N_(b))log_(10)N_(b) times faster than the brute-force algorithm for an RBS with N_(b) batteries and N_(s) switches.Another advantage of the proposed method is its ability to calculate the MAC of RBSs with arbitrary structures and variable batteries,even in scenarios with random isolated batteries.
文摘Internet of things networks often suffer from early node failures and short lifespan due to energy limits.Traditional routing methods are not enough.This work proposes a new hybrid algorithm called ACOGA.It combines Ant Colony Optimization(ACO)and the Greedy Algorithm(GA).ACO finds smart paths while Greedy makes quick decisions.This improves energy use and performance.ACOGA outperforms Hybrid Energy-Efficient(HEE)and Adaptive Lossless Data Compression(ALDC)algorithms.After 500 rounds,only 5%of ACOGA’s nodes are dead,compared to 15%for HEE and 20%for ALDC.The network using ACOGA runs for 1200 rounds before the first nodes fail.HEE lasts 900 rounds and ALDC only 850.ACOGA saves at least 15%more energy by better distributing the load.It also achieves a 98%packet delivery rate.The method works well in mixed IoT networks like Smart Water Management Systems(SWMS).These systems have different power levels and communication ranges.The simulation of proposed model has been done in MATLAB simulator.The results show that that the proposed model outperform then the existing models.
文摘A connected and undirected graph model of active distribution networks with considering the function of interconnecting switches is constructed in this paper.Based on this model,the island partition problem of active distribution networks can be described as a 1-neighbour knapsack problem.An effective heuristic algorithm named prospective greedy algorithm is then proposed to solve this problem.Case studies on PG&E 69-bus network show the validity of the proposed model and algorithm.
基金This work was jointly supported by the National Natural Science Foundation of Shandong Province(No.ZR2023MF022)National Natural Science Foundation of China(Nos.61973203,62173216,and 62173356)Guangyue Youth Scholar Innovation Talent Program Support from Liaocheng University(No.LCUGYTD2022-03).
文摘The distributed hybrid flow shop scheduling problem(DHFSP),which integrates distributed manufacturing models with parallel machines,has gained significant attention.However,in actual scheduling,some adjacent machines do not have buffers between them,resulting in blocking.This paper focuses on addressing the DHFSP with blocking constraints(DBHFSP)based on the actual production conditions.To solve DBHFSP,we construct a mixed integer linear programming(MILP)model for DBHFSP and validate its correctness using the Gurobi solver.Then,an advanced iterated greedy(AIG)algorithm is designed to minimize the makespan,in which we modify the Nawaz,Enscore,and Ham(NEH)heuristic to solve blocking constraints.To balance the global and local search capabilities of AIG,two effective inter-factory neighborhood search strategies and a swap-based local search strategy are designed.Additionally,each factory is mutually independent,and the movement within one factory does not affect the others.In view of this,we specifically designed a memory-based decoding method for insertion operations to reduce the computation time of the objective.Finally,two shaking strategies are incorporated into the algorithm to mitigate premature convergence.Five advanced algorithms are used to conduct comparative experiments with AIG on 80 test instances,and experimental results illustrate that the makespan and the relative percentage increase(RPI)obtained by AIG are 1.0%and 86.1%,respectively,better than the comparative algorithms.
基金Supported by the National Key Research and Development Program of China(No.2020YFC1807904).
文摘With the wide application of automated guided vehicles(AGVs) in large scale outdoor scenarios with complex terrain,the collaborative work of a large number of AGVs becomes the main trend.The effective multi-agent path finding(MAPF) algorithm is urgently needed to ensure the efficiency and realizability of the whole system. The complex terrain of outdoor scenarios is fully considered by using different values of passage cost to quantify different terrain types. The objective of the MAPF problem is to minimize the cost of passage while the Manhattan distance of paths and the time of passage are also evaluated for a comprehensive comparison. The pre-path-planning and real-time-conflict based greedy(PRG) algorithm is proposed as the solution. Simulation is conducted and the proposed PRG algorithm is compared with waiting-stop A^(*) and conflict based search(CBS) algorithms. Results show that the PRG algorithm outperforms the waiting-stop A^(*) algorithm in all three performance indicators,and it is more applicable than the CBS algorithm when a large number of AGVs are working collaboratively with frequent collisions.
基金supported by NSFC grant(Nos.12001026,12071019)supported by the National Science Fund for Distinguished Young Scholars grant(No.12025108)+1 种基金Beijing Natural Science Foundation(No.Z180002)NSFC grant(Nos.12021001,11688101).
文摘Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications,such as simplification of social networks,least squares problems,and numerical solution of symmetric positive definite linear systems.In this paper,inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit(OMP),we introduce a deterministic,greedy edge selection algorithm,which is called the universal greedy approach(UGA)for the graph sparsification problem.For a general spectral sparsification problem,e.g.,the positive subset selection problem from a set of m vectors in R n,we propose a nonnegative UGA algorithm which needs O(mn^(2)+n^(3)/ϵ^(2))time to find a 1+ϵ/β/1-ϵ/β-spectral sparsifier with positive coefficients with sparsity at most[n/ϵ^(2)],where β is the ratio between the smallest length and largest length of the vectors.The convergence of the nonnegative UGA algorithm is established.For the graph sparsification problem,another UGA algorithm is proposed which can output a 1+O(ϵ)/1-O(ϵ)-spectral sparsifier with[n/ϵ^(2)]edges in O(m+n^(2)/ϵ^(2))time from a graph with m edges and n vertices under some mild assumptions.This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for.The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear,i.e.O(m^(1+o(1)))for some o(1)=O((log log(m))^(2/3)/log^(1/3)(m)).Finally,extensive experimental results,including applications to graph clustering and least squares regression,show the effectiveness of proposed approaches.
文摘We investigate the efficiency of weak greedy algorithms for m-term expansional approximation with respect to quasi-greedy bases in general Banach spaces.We estimate the corresponding Lebesgue constants for the weak thresholding greedy algorithm（WTGA） and weak Chebyshev thresholding greedy algorithm.Then we discuss the greedy approximation on some function classes.For some sparse classes induced by uniformly bounded quasi-greedy bases of L_p,12 the WCGA is better than the TGA.
基金Foundation of National Natural Science Foundation of China(62202118)Scientific and Technological Research Projects from Guizhou Education Department([2023]003)+1 种基金Guizhou Provincial Department of Science and Technology Hundred Levels of Innovative Talents Project(GCC[2023]018)Top Technology Talent Project from Guizhou Education Department([2022]073).
文摘The development of technologies such as big data and blockchain has brought convenience to life,but at the same time,privacy and security issues are becoming more and more prominent.The K-anonymity algorithm is an effective and low computational complexity privacy-preserving algorithm that can safeguard users’privacy by anonymizing big data.However,the algorithm currently suffers from the problem of focusing only on improving user privacy while ignoring data availability.In addition,ignoring the impact of quasi-identified attributes on sensitive attributes causes the usability of the processed data on statistical analysis to be reduced.Based on this,we propose a new K-anonymity algorithm to solve the privacy security problem in the context of big data,while guaranteeing improved data usability.Specifically,we construct a new information loss function based on the information quantity theory.Considering that different quasi-identification attributes have different impacts on sensitive attributes,we set weights for each quasi-identification attribute when designing the information loss function.In addition,to reduce information loss,we improve K-anonymity in two ways.First,we make the loss of information smaller than in the original table while guaranteeing privacy based on common artificial intelligence algorithms,i.e.,greedy algorithm and 2-means clustering algorithm.In addition,we improve the 2-means clustering algorithm by designing a mean-center method to select the initial center of mass.Meanwhile,we design the K-anonymity algorithm of this scheme based on the constructed information loss function,the improved 2-means clustering algorithm,and the greedy algorithm,which reduces the information loss.Finally,we experimentally demonstrate the effectiveness of the algorithm in improving the effect of 2-means clustering and reducing information loss.
基金Projects(2009AA01Z124,2009AA01Z102) supported by the National High Technology Research and Development Program of ChinaProjects(60970036,61076025) supported by the National Natural Science Foundation of China
文摘Chip multiprocessors(CMPs) allow thread level parallelism,thus increasing performance.However,this comes with the cost of temperature problem.CMPs require more power,creating non uniform power map and hotspots.Aiming at this problem,a thread scheduling algorithm,the greedy scheduling algorithm,was proposed to reduce the thermal emergencies and to improve the throughput.The greedy scheduling algorithm was implemented in the Linux kernel on Intel's Quad-Core system.The experimental results show that the greedy scheduling algorithm can reduce 9.6%-78.5% of the hardware dynamic thermal management(DTM) in various combinations of workloads,and has an average of 5.2% and up to 9.7% throughput higher than the Linux standard scheduler.
基金support from the National Natural Science Foundation of China(Grant Nos.52174123&52274222).
文摘This paper presents a framework for constructing surrogate models for sensitivity analysis of structural dynamics behavior.Physical models involving deformation,such as collisions,vibrations,and penetration,are devel-oped using the material point method.To reduce the computational cost of Monte Carlo simulations,response surface models are created as surrogate models for the material point system to approximate its dynamic behavior.An adaptive randomized greedy algorithm is employed to construct a sparse polynomial chaos expansion model with a fixed order,effectively balancing the accuracy and computational efficiency of the surrogate model.Based on the sparse polynomial chaos expansion,sensitivity analysis is conducted using the global finite difference and Sobol methods.Several examples of structural dynamics are provided to demonstrate the effectiveness of the proposed method in addressing structural dynamics problems.
