An Improved Iterated Greedy Algorithm for Solving Rescue Robot Path Planning Problem with Limited Survival Time

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.

A greedy path planning algorithm based on pre-path-planning and real-time-conflict for multiple automated guided vehicles in large-scale outdoor scenarios

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.

A Query-Based Greedy Approach for Authentic Influencer Discovery in SIoT

The authors propose an informed search greedy approach that efficiently identifies the influencer nodes in the social Internet of Things with the ability to provide legitimate information.Primarily,the proposed approach minimizes the network size and eliminates undesirable connections.For that,the proposed approach ranks each of the nodes and prioritizes them to identify an authentic influencer.Therefore,the proposed approach discards the nodes having a rank(α)lesser than 0.5 to reduce the network complexity.αis the variable value represents the rank of each node that varies between 0 to 1.Node with the higher value ofαgets the higher priority and vice versa.The threshold valueα=0.5 defined by the authors with respect to their network pruning requirements that can be vary with respect to other research problems.Finally,the algorithm in the proposed approach traverses the trimmed network to identify the authentic node to obtain the desired information.The performance of the proposed method is evaluated in terms of time complexity and accuracy by executing the algorithm on both the original and pruned networks.Experimental results show that the approach identifies authentic influencers on a resultant network in significantly less time than in the original network.Moreover,the accuracy of the proposed approach in identifying the influencer node is significantly higher than that of the original network.Furthermore,the comparison of the proposed approach with the existing approaches demonstrates its efficiency in terms of time consumption and network traversal through the minimum number of hops.

基于t混合模型和Greedy EM算法的彩色图像分割

为了快速更好地进行彩色图像分割,以图像的颜色、纹理及空间位置作为综合特征,基于t混合模型,提出了一种自适应的图像分割方法,即先采用贪婪的EM(Greedy EM)算法估计混合模型的参数,然后根据贝叶斯最小错误率准则对图像进行分割。由于t混合模型的稳健性和Greedy EM算法对于数据的初始化不敏感,且能收敛到全局最优,因此与其他的方法相比,不仅速度提高,而且能取得更好的分割结果。

基于Greedy算法的防空作战目标分配

依据防空作战中目标分配的一般原则,按目标分配方案中射击有利度最大的原则,提出了目标分配算法,并用组合优化算法中的Greedy算法进行了求解。结果表明该算法是一种较成熟、可靠的方法。

一类Fourier系数乘子函数类的最佳m-项逼近与Greedy算法的收敛条件及渐近估计

利用有限维空间的逼近性质,本文研究了由一类Fourier系数确定的乘子函数类Fq(α)(0<q≤∞)在Lp(1≤p≤∞)范数下由三角函数系给出的非线性最佳m-项逼近收敛的充分条件和必要条件。在此条件下,给出了此乘子函数类在三角函数系下最佳m-项逼近与相应的贪婪(Greedy)算法逼近的渐近估计。

一个乘子函数类的最佳m-项逼近与Greedy逼近的渐近阶

研究了函数类Fαq∶={f∈Lq(Td)||f|Fqα∶=‖(|k|α(ln+ |k|)l|^f(k)|)k∈Zd‖lq(Zd)≤1} (0<α<∞, l≥0,0<q≤∞)在三角函数系统下的非线性最佳m- 项逼近问题.给出了在Lp范数下其最佳m- 项逼近的强渐进阶,同时也给出了相应的Greedy算法的逼近结果.由此结果可以看出,Greedy算法在一定条件下实现了此函数类在三角系下的最佳m -项逼近.

Fourier系数乘子函数类在:Λ-Greedy逼近算法下的收敛界

利用三角函数系为逼近空间,将在图象压缩、偏微分方程的近似解、统计分类方面有着重要应用的非线性m-项逼近中的误差计算方法———-ΛGreedy逼近算法应用到Lp空间由Fourier系数及乘子函数确定的多(d)元乘子函数类上,利用乘子函数空间的性质,通过对由Fourier系数确定的乘子函数类由三角函数系给出的m-项逼近的性质的讨论,给出了在-ΛGreedy逼近算法下,一般乘子函数是空间分别在lp与Lp范数下逼近界的表达式.

碰撞数问题Greedy序集的结构

称一有限序集是一Greedy序集是指,它的每个关于碰撞数问题的Greedy线性扩张都是最优的。本文给出了Greedy序集的结构。

基于多模型外部分析和Greedy-KP1M的多工况过程监控

传统的基于多元统计过程监控方法都是假设过程处于单一工况下,而随着进料负荷、产品组分等过程参数的改变,生产过程的工况也随之改变,传统方法便不再适用。针对工业过程中的多工况监控问题,提出了一种基于多模型外部分析和Greedy-KP1M的多工况过程监控方法。首先针对传统外部分析方法描述能力不足的问题,用多模型局部建模代替单一模型来获得更好的描述能力,同时获得监控残差,通过对残差进行监控从而去除多工况的影响,进而将核单簇可能性聚类(KP1M)用于对残差的监控上。该方法拥有和支持向量数据描述(SVDD)相当的监控效果,但计算复杂度却远远小于SVDD。同时,采用Greedy方法提取特征样本,进一步降低了算法计算复杂度。最后将上述方法应用在TE模型和乙烯裂解炉的监控上,结果证明了该方法的有效性。

Intelligent Greedy Perimeter Stateless Routing Scheme for Unmanned Aerial Vehicles

The dynamic behavior,rapid mobility,abrupt changes in network topology,and numerous other flying constraints in unmanned aerial vehicle(UAV)networks make the design of a routing protocol a challenging task.The data routing for communication between UAVs faces numerous challenges,such as low link quality,data loss,and routing path failure.This work proposes greedy perimeter stateless routing(GPSR)based design and implementation of a new adaptive communication routing protocol technique for UAVs,allowing multiple UAVs to communicate more effectively with each other in a group.Close imitation of the real environment is accomplished by considering UAVs’three-dimensional(3D)mobility in the simulations.The performance of the proposed intelligent greedy perimeter stateless routing(IGPSR)scheme has been evaluated based on end-to-end(E2E)delay,network throughput,and data loss ratio.The adapted scheme displayed on average 40%better results.The scenario has been implemented holistically on the network simulator software NS-3.

基于LTSA-Greedy-SVDD的过程监控

为解决实际工业过程中的非线性和非高斯问题,实现有效的过程监控,提出了一种基于局部切空间排列算法的过程监控方法。首先运用局部切空间排列算法对标准化后的正常样本数据提取出低维子流形以实现维数约减。之后利用Greedy方法提取特征样本以支持向量数据描述方法建立监控模型,最后采用相应统计量进行过程监控。以田纳西伊斯曼(TE)模型为仿真平台,仿真结果说明了该方法的有效性。

A Modi ed Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem

The flexible job shop scheduling problem(FJSP) is considered as an important problem in the modern manufacturing system. It is known to be an NP-hard problem. Most of the algorithms used in solving FJSP problem are categorized as metaheuristic methods. Some of these methods normally consume more CPU time and some other methods are more complicated which make them di cult to code and not easy to reproduce. This paper proposes a modified iterated greedy(IG) algorithm to deal with FJSP problem in order to provide a simpler metaheuristic, which is easier to code and to reproduce than some other much more complex methods. This is done by separating the classical IG into two phases. Each phase is used to solve a sub-problem of the FJSP: sequencing and routing sub-problems. A set of dispatching rules are employed in the proposed algorithm for the sequencing and machine selection in the construction phase of the solution. To evaluate the performance of proposed algorithm, some experiments including some famous FJSP benchmarks have been conducted. By compared with other algorithms, the experimental results show that the presented algorithm is competitive and able to find global optimum for most instances. The simplicity of the proposed IG provides an e ective method that is also easy to apply and consumes less CPU time in solving the FJSP problem.

Effective Iterated Greedy Algorithm for Flow-Shop Scheduling Problems 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.

GREEDY NON-DOMINATED SORTING IN GENETIC ALGORITHM-ⅡFOR VEHICLE ROUTING PROBLEM IN DISTRIBUTION

Vehicle routing problem in distribution （VRPD） is a widely used type of vehicle routing problem （VRP）, which has been proved as NP-Hard, and it is usually modeled as single objective optimization problem when modeling. For multi-objective optimization model, most researches consider two objectives. A multi-objective mathematical model for VRP is proposed, which considers the number of vehicles used, the length of route and the time arrived at each client. Genetic algorithm is one of the most widely used algorithms to solve VRP. As a type of genetic algorithm （GA）, non-dominated sorting in genetic algorithm-Ⅱ （NSGA-Ⅱ） also suffers from premature convergence and enclosure competition. In order to avoid these kinds of shortage, a greedy NSGA-Ⅱ （GNSGA-Ⅱ） is proposed for VRP problem. Greedy algorithm is implemented in generating the initial population, cross-over and mutation. All these procedures ensure that NSGA-Ⅱ is prevented from premature convergence and refine the performance of NSGA-Ⅱ at each step. In the distribution problem of a distribution center in Michigan, US, the GNSGA-Ⅱ is compared with NSGA-Ⅱ. As a result, the GNSGA-Ⅱ is the most efficient one and can get the most optimized solution to VRP problem. Also, in GNSGA-Ⅱ, premature convergence is better avoided and search efficiency has been improved sharply.

Enhancing the synchronizability of networks by rewiring based on tabu search and a local greedy algorithm

By considering the eigenratio of the Laplacian matrix as the synchronizability measure, this paper presents an efficient method to enhance the synchronizability of undirected and unweighted networks via rewiring. The rewiring method combines the use of tabu search and a local greedy algorithm so that an effective search of solutions can be achieved. As demonstrated in the simulation results, the performance of the proposed approach outperforms the existing methods for a large variety of initial networks, both in terms of speed and quality of solutions.

Simulating Greedy Propagation of P2P Worms

Greedy propagation policy for unstructured P2P worms employs the neighboring node list of each node in peer-to-peer （P2P） network to speed up the propagation of P2P worms. After describing the technique background of P2P worms, the algorithm of greedy propagation is addressed. Simulating design for this novel propagation policy is also described. Then, the effects of the greedy propagation policy on spreading speed, convergence speed, and attacking traffic in static P2P worms are simulated and discussed. The primary experimental results show that the greedy propagation is harmful and can bring severe damages to P2P network.

GTK:A Hybrid-Search Algorithm of Top-Rank-k Frequent Patterns Based on Greedy Strategy

Currently,the top-rank-k has been widely applied to mine frequent patterns with a rank not exceeding k.In the existing algorithms,although a level-wise-search could fully mine the target patterns,it usually leads to the delay of high rank patterns generation,resulting in the slow growth of the support threshold and the mining efficiency.Aiming at this problem,a greedy-strategy-based top-rank-k frequent patterns hybrid mining algorithm(GTK)is proposed in this paper.In this algorithm,top-rank-k patterns are stored in a static doubly linked list called RSL,and the patterns are divided into short patterns and long patterns.The short patterns generated by a rank-first-search always joins the two patterns of the highest rank in RSL that have not yet been joined.On the basis of the short patterns satisfying specific conditions,the long patterns are extracted through level-wise-search.To reduce redundancy,GTK improves the generation method of subsume index and designs the new pruning strategies of candidates.This algorithm also takes the use of reasonable pruning strategies to reduce the amount of computation to improve the computational speed.Real datasets and synthetic datasets are adopted in experiments to evaluate the proposed algorithm.The experimental results show the obvious advantages in both time efficiency and space efficiency of GTK.

A Relaxed Greedy Block Kaczmarz Method for Solving Large Consistent Linear Systems

Many problems in science and engineering require solving large consistent linear systems. This paper presents a relaxed greedy block Kaczmarz method (RGBK) and an accelerated greedy block Kaczmarz method (AGBK) for solving large-size consistent linear systems. The RGBK algorithm extends the greedy block Kaczmarz algorithm (GBK) presented by Niu and Zheng in [1] by introducing a relaxation parameter to the iteration formulation of GBK, and the AGBK algorithm uses different iterative update rules to minimize the running time. The convergence of the RGBK is proved and a method to determine an optimal parameter is provided. Several examples are presented to show the effectiveness of the proposed methods for overdetermined and underdetermined consistent linear systems with dense and sparse coefficient matrix.

Low Complexity Precoded Greedy Power Allocation Algorithms for OFDM Communication Systems

In this paper, an enhanced greedy bit and power allocation algorithms for orthogonal frequency division multiplexing (OFDM) communication systems are introduced. These algorithms combine low complexity greedy power allocation algorithms with a simplified maximum ratio combining (MRC) precoding technique at the transmitter for maximizing the average data throughput of OFDM communication systems. Results of computer simulations show that precoding is an effective technique for improving the throughput performance of the proposed bit and power allocation algorithms.