A greedy algorithm based on joint assignment of airport gates and taxiways in large hub airports

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.

GRAPH SPARSIFICATION BY UNIVERSAL GREEDY ALGORITHMS

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.

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.

An Innovative K-Anonymity Privacy-Preserving Algorithm to Improve Data Availability in the Context of Big Data

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.

Selection of Metaheuristic Algorithm to Design Wireless Sensor Network

The deployment of sensor nodes is an important aspect in mobile wireless sensor networks for increasing network performance.The longevity of the networks is mostly determined by the proportion of energy consumed and the sensor nodes’access network.The optimal or ideal positioning of sensors improves the portable sensor networks effectiveness.Coverage and energy usage are mostly determined by successful sensor placement strategies.Nature-inspired algorithms are the most effective solution for short sensor lifetime.The primary objective of work is to conduct a comparative analysis of nature-inspired optimization for wireless sensor networks(WSNs’)maximum network coverage.Moreover,it identifies quantity of installed sensor nodes for the given area.Superiority of algorithm has been identified based on value of optimized energy.The first half of the paper’s literature on nature-inspired algorithms is discussed.Later six metaheuristics algorithms(Grey wolf,Ant lion,Dragonfly,Whale,Moth flame,Sine cosine optimizer)are compared for optimal coverage of WSNs.The simulation outcomes confirm that whale opti-mization algorithm(WOA)gives optimized Energy with improved network coverage with the least number of nodes.This comparison will be helpful for researchers who will use WSNs in their applications.

An Algorithm for the Inverse Problem of Matrix Processing: DNA Chains, Their Distance Matrices and Reconstructing

We continue to consider one of the cybernetic methods in biology related to the study of DNA chains. Exactly, we are considering the problem of reconstructing the distance matrix for DNA chains. Such a matrix is formed on the basis of any of the possible algorithms for determining the distances between DNA chains, as well as any specific object of study. At the same time, for example, the practical programming results show that on an average modern computer, it takes about a day to build such a 30 × 30 matrix for mnDNAs using the Needleman-Wunsch algorithm;therefore, for such a 300 × 300 matrix, about 3 months of continuous computer operation is expected. Thus, even for a relatively small number of species, calculating the distance matrix on conventional computers is hardly feasible and the supercomputers are usually not available. Therefore, we started publishing our variants of the algorithms for calculating the distance between two DNA chains, then we publish algorithms for restoring partially filled matrices, i.e., the inverse problem of matrix processing. Previously, we used the method of branches and boundaries, but in this paper we propose to use another new algorithm for restoring the distance matrix for DNA chains. Our recent work has shown that even greater improvement in the quality of the algorithm can often be achieved without improving the auxiliary heuristics of the branches and boundaries method. Thus, we are improving the algorithms that formulate the greedy function of this method only. .

Dual-Objective Mixed Integer Linear Program and Memetic Algorithm for an Industrial Group Scheduling Problem

Group scheduling problems have attracted much attention owing to their many practical applications.This work proposes a new bi-objective serial-batch group scheduling problem considering the constraints of sequence-dependent setup time,release time,and due time.It is originated from an important industrial process,i.e.,wire rod and bar rolling process in steel production systems.Two objective functions,i.e.,the number of late jobs and total setup time,are minimized.A mixed integer linear program is established to describe the problem.To obtain its Pareto solutions,we present a memetic algorithm that integrates a population-based nondominated sorting genetic algorithm II and two single-solution-based improvement methods,i.e.,an insertion-based local search and an iterated greedy algorithm.The computational results on extensive industrial data with the scale of a one-week schedule show that the proposed algorithm has great performance in solving the concerned problem and outperforms its peers.Its high accuracy and efficiency imply its great potential to be applied to solve industrial-size group scheduling problems.

For LEO Satellite Networks: Intelligent Interference Sensing and Signal Reconstruction Based on Blind Separation Technology

In LEO satellite communication networks,the number of satellites has increased sharply, the relative velocity of satellites is very fast, then electronic signal aliasing occurs from time to time. Those aliasing signals make the receiving ability of the signal receiver worse, the signal processing ability weaker,and the anti-interference ability of the communication system lower. Aiming at the above problems, to save communication resources and improve communication efficiency, and considering the irregularity of interference signals, the underdetermined blind separation technology can effectively deal with the problem of interference sensing and signal reconstruction in this scenario. In order to improve the stability of source signal separation and the security of information transmission, a greedy optimization algorithm can be executed. At the same time, to improve network information transmission efficiency and prevent algorithms from getting trapped in local optima, delete low-energy points during each iteration process. Ultimately, simulation experiments validate that the algorithm presented in this paper enhances both the transmission efficiency of the network transmission system and the security of the communication system, achieving the process of interference sensing and signal reconstruction in the LEO satellite communication system.

Intelligent Optimization Under Multiple Factories: Hybrid Flow Shop Scheduling Problem with Blocking Constraints Using an Advanced Iterated Greedy 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 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.

Quality of experience based scheduling algorithm in LTE network with various traffics

Quality of experience(QoE)based scheduling algorithm of long term evalution(LTE)network with various traffics is studied.Utility functions are adopted to estimate mean opinion score(MOS)for different traffics and a new MOS metric called normalized MOS is defined.A scheduling algorithm based on normalized MOS and greedy algorithm is proposed,aiming at maximizing the entirety MOS level of the whole users in the cell.We compare the performance of the proposed algorithm with other typical scheduling algorithms and the simulation results show that the algorithm proposed outperform other ones in term of QoE and fairness.

Strict greedy design paradigm applied to the stochastic multi-armed bandit problem

The process of making decisions is something humans do inherently and routinely,to the extent that it appears commonplace. However,in order to achieve good overall performance,decisions must take into account both the outcomes of past decisions and opportunities of future ones. Reinforcement learning,which is fundamental to sequential decision-making,consists of the following components: 1 A set of decisions epochs; 2 A set of environment states; 3 A set of available actions to transition states; 4 State-action dependent immediate rewards for each action.At each decision,the environment state provides the decision maker with a set of available actions from which to choose. As a result of selecting a particular action in the state,the environment generates an immediate reward for the decision maker and shifts to a different state and decision. The ultimate goal for the decision maker is to maximize the total reward after a sequence of time steps.This paper will focus on an archetypal example of reinforcement learning,the stochastic multi-armed bandit problem. After introducing the dilemma,I will briefly cover the most common methods used to solve it,namely the UCB and εn- greedy algorithms. I will also introduce my own greedy implementation,the strict-greedy algorithm,which more tightly follows the greedy pattern in algorithm design,and show that it runs comparably to the two accepted algorithms.

Exploring Hybrid Genetic Algorithm Based Large-Scale Logistics Distribution for BBG Supermarket

In the large-scale logistics distribution of single logistic center,the method based on traditional genetic algorithm is slow in evolution and easy to fall into the local optimal solution.Addressing at this issue,we propose a novel approach of exploring hybrid genetic algorithm based large-scale logistic distribution for BBG supermarket.We integrate greedy algorithm and hillclimbing algorithm into genetic algorithm.Greedy algorithm is applied to initialize the population,and then hill-climbing algorithm is used to optimize individuals in each generation after selection,crossover and mutation.Our approach is evaluated on the dataset of BBG Supermarket which is one of the top 10 supermarkets in China.Experimental results show that our method outperforms some other methods in the field.

Automatic spectrum recognition system for charge state analysis in electron cyclotron resonance ion sources

The Electron Cyclotron Resonance(ECR)ion source is a critical device for producing highly charged ion beams in various applications.Analyzing the charge-state distribution of the ion beams is essential,but the manual analysis is labor-intensive and prone to inaccuracies due to impurity ions.An automatic spectrum recognition system based on intelligent algorithms was proposed for rapid and accurate chargestate analysis of ECR ion sources.The system employs an adaptive window-length Savitzky-Golay(SG)filtering algorithm,an improved automatic multiscale peak detection(AMPD)algorithm,and a greedy matching algorithm based on the relative distance to accurately match different peaks in the spectra with the corresponding charge-state ion species.Additionally,a user-friendly operator interface was developed for ease of use.Extensive testing on the online ECR ion source platform demonstrates that the system achieves high accuracy,with an average root mean square error of less than 0.1 A for identifying charge-state spectra of ECR ion sources.Moreover,the system minimizes the stand-ard deviation of the first-order derivative of the smoothed signal to 81.1846 A.These results indicate the capability of the designed system to identify ion beam spectra with mass numbers less than Xe,including Xe itself.The proposed automatic spectrum recognition system represents a significant advancement in ECR ion source analysis,offering a rapid and accurate approach for charge-state analysis while enhancing supply efficiency.The exceptional performance and successful imple-mentation of the proposed system on multiple ECR ion source platforms at IMPCAS highlight its potential for widespread adoption in ECR ion source research and applications.

Coded Multicasting for Content Delivery over Predictable Time-Varying Satellite Communication Networks

With the development of astronautic technology, communication satellites now have a tremendous gain in both quantity and quality, and have already shown their capability on multi-functional converged communication other than telecommunication. Under this circumstance, increasing the transmission efficiency of satellite communication network becomes a top priority. In this paper, we focus on content delivery service on satellite networks, where each ground station may have prefetched some file fragments. We cast this problem into a coded caching framework so as to exploit the coded multicast gain for minimizing the satellite communication load. We first propose an optimization-based coded multicast scheme by considering the special property that the satellite network topology is predictable and timevariant. Then, a greedy based fast algorithm is proposed, which can tremendously reduce the computation complexity with a small loss in optimality. Simulation experiments conducted on two Walker constellation satellite networks show that our proposed coded multicast method can efficiently reduce the communication load of satellite networks.

Generation of Low-Delay and High-Stability Multicast Tree

Delay and stability are two key factors that affect the performance of multicast data transmission in a network.However,current algorithms of tree generation hardly meet the requirements of low delay and high sta-bility simultaneously.Given a general network,the generation algorithm of a multicast tree with minimum delay and maximum stability is an NP-hard problem,without a precise and efficient algorithm.To address these challenges,this paper studies the generation of low-delay and high-stability multicast trees under the model of spanning tree based on stability probability,degree-constrained,edge-weighted for multicast(T-SDE).A class of algorithms was proposed which creates the multicast tree greedy on the ratio of fan-out to delay(RFD)and probability of stability of terminal to obtain a high performance in multicast.The proposed algorithms greedily select terminals with a large RFD and a high probability of stability as forwarding nodes in the generation of the multicast tree,where the larger RFD and higher stability of upstream nodes are beneficial to achieve a low transmission delay and high stability in multicast.The proposed RFD can be compatible with the original model,which can take advantage of network connectivity during the generation of a multicast tree.This paper carries out simulation experiments on Matlab R2016b to measure the performance of the proposed algorithm.Experimental results show that the proposed algorithm can provide a smaller height,higher stability,and a lower transmission delay of the resulting multicast tree than other solutions.The spanning tree of the proposed algorithms can support low transmission delay and high stability in multicast transmission.

Collision-free Scheduling of Multi-bridge Machining Systems： A Colored Traveling Salesman Problem-based Approach

Multi-bridge machining systems(MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially overlapping workspaces.Their scheduling problems can be abstracted into a serial-colored travelling salesman problem in which each salesman has some exclusive cities and some cities shared with its neighbor(s). To solve it, we develop a greedy algorithm that selects a neighboring city satisfying proximity. The algorithm allows a salesman to select randomly its shared cities and runs accordingly many times. It can thus be used to solve job scheduling problems for MBMS. Subsequently, a collision-free scheduling method is proposed to address both job scheduling and collision resolution issues of MBMS. It is an extension of the greedy algorithm by introducing time window constraints and a collision resolution mechanism. Thus, the augmented greedy algorithm can try its best to select stepwise a job for an individual machine such that no time overlaps exist between it and the job sequence of the neighboring machine dealt in the corresponding overlapping workspace; and remove such a time overlap only when it is inevitable. Finally, we conduct a case study of a large triplebridge waterjet cutting system by applying the proposed method.

Recursive Dictionary-Based Simultaneous Orthogonal Matching Pursuit for Sparse Unmixing of Hyperspectral Data

The sparse unmixing problem of greedy algorithms still remains a great challenge at finding an optimal subset of endmembers for the observed data from the spectral library,due to the usually high correlation of the spectral library.Under such circumstances,a novel greedy algorithm for sparse unmixing of hyperspectral data is presented,termed the recursive dictionary-based simultaneous orthogonal matching pursuit(RD-SOMP).The algorithm adopts a block-processing strategy to divide the whole hyperspectral image into several blocks.At each iteration of the block,the spectral library is projected into the orthogonal subspace and renormalized,which can reduce the correlation of the spectral library.Then RD-SOMP selects a new endmember with the maximum correlation between the current residual and the orthogonal subspace of the spectral library.The endmembers picked in all the blocks are associated as the endmember sets of the whole hyperspectral data.Finally,the abundances are estimated using the whole hyperspectral data with the obtained endmember sets.It can be proved that RD-SOMP can recover the optimal endmembers from the spectral library under certain conditions.Experimental results demonstrate that the RD-SOMP algorithm outperforms the other algorithms,with a better spectral unmixing accuracy.

Extraction of coastline in high-resolution remote sensing images based on the active contour model

While executing tasks such as ocean pollution monitoring,maritime rescue,geographic mapping,and automatic navigation utilizing remote sensing images,the coastline feature should be determined.Traditional methods are not satisfactory to extract coastline in high-resolution panchromatic remote sensing image.Active contour model,also called snakes,have proven useful for interactive specification of image contours,so it is used as an effective coastlines extraction technique.Firstly,coastlines are detected by water segmentation and boundary tracking,which are considered initial contours to be optimized through active contour model.As better energy functions are developed,the power assist of snakes becomes effective.New internal energy has been done to reduce problems caused by convergence to local minima,and new external energy can greatly enlarge the capture region around features of interest.After normalization processing,energies are iterated using greedy algorithm to accelerate convergence rate.The experimental results encompassed examples in images and demonstrated the capabilities and efficiencies of the improvement.

In silico method for studying property combination of traditional Chinese herbs

Objective:This paper discusses the composition of prescription qualitative,quantitative design principles and methods based on herbal property combination,describing the method application in new prescription design.Method:Qualitative property-combination pattern(PP)calculation was based on bipartite graphing and performing a greedy algorithm which was designed to optimize obtaining a new herbal prescription.Quantitative PP calculation was based on the qualitative computation.To calculate the Euclidean distance for the PP of the new prescription,an optimized algorithm for solving the unknown minimum Euclidean distance was used with,the new weighted proportions.Finally,non-linear optimization software was used to find the minimum Euclidean distance.Results:Using the PP of classic prescription Large Yin-Nourishing Pill,applying quantitative PP calculation a new prescription was created.Mathematical algorithms based on property combinations of traditional Chinese herbs can be applied to identify compatibility and synergies of herbs within prescriptions,especially classic formulas.Conclusion:In silico methods can then be used to create new prescriptions or modify existing ones depending on need.This type of automated approach may increase efficiency in designing new drugs based on Chinese herbs.

OPTIMIZATION OF MULTIPLE-CHANNEL COOPERATIVE SPECTRUM SENSING WITH DATA FUSION RULE IN COGNITIVE RADIO NETWORKS

This paper focuses on multi-channel Cooperative Spectrum Sensing (CSS) where Secondary Users (SUs) are assigned to cooperatively sense multiple channels simultaneously. A multi-channel CSS optimization problem of joint spectrum sensing and SU assignment based on data fusion rule is formulated, which maximizes the total throughput of the Cognitive Radio Network (CRN) subject to the constraints of probabilities of detection and false alarm. To address the optimization problem, a Branch and Bound (BnB) algorithm and a greedy algorithm are proposed to obtain the optimal solutions. Simulation results are presented to demonstrate the effectiveness of our proposed algorithms and show that the throughput improvement is achieved through the joint design. It is also shown that the greedy algorithm with a low complexity achieves the comparable performance to the exhaustive algorithm.