Quantum algorithm for minimum dominating set problem with circuit design

Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems.This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs.To expedite the search process,a quantum algorithm employing Grover’s search is proposed.However,a challenge arises from the unknown number of solutions for the minimum dominating set,rendering direct usage of original Grover’s search impossible.Thus,a swap test method is introduced to ascertain the number of iterations required.The oracle,diffusion operators,and swap test are designed with achievable quantum gates.The query complexity is O(1.414^(n))and the space complexity is O(n).To validate the proposed approach,qiskit software package is employed to simulate the quantum circuit,yielding the anticipated results.

DSAS:A new macromolecular substructure solution program based on the modified phase-retrieval algorithm

Considering the pivotal role of single-wavelength anomalous diffraction(SAD) in macromolecular crystallography,our objective was to introduce DSAS,a novel program designed for efficient anomalous scattering substructure determination.DSAS stands out with its core components:a modified phase-retrieval algorithm and automated parameter tuning.The software boasts an intuitive graphical user interface(GUI),facilitating seamless input of essential data and real-time monitoring.Extensive testing on DSAS has involved diverse datasets,encompassing proteins,nucleic acids,and various anomalous scatters such as sulfur(S),selenium(Se),metals,and halogens.The results confirm DSAS’s exceptional performance in accurately determining heavy atom positions,making it a highly effective tool in the field.

Research on Evacuation Path Planning Based on Improved Sparrow Search Algorithm

Reducing casualties and property losses through effective evacuation route planning has been a key focus for researchers in recent years.As part of this effort,an enhanced sparrow search algorithm(MSSA)was proposed.Firstly,the Golden Sine algorithm and a nonlinear weight factor optimization strategy were added in the discoverer position update stage of the SSA algorithm.Secondly,the Cauchy-Gaussian perturbation was applied to the optimal position of the SSA algorithm to improve its ability to jump out of local optima.Finally,the local search mechanism based on the mountain climbing method was incorporated into the local search stage of the SSA algorithm,improving its local search ability.To evaluate the effectiveness of the proposed algorithm,the Whale Algorithm,Gray Wolf Algorithm,Improved Gray Wolf Algorithm,Sparrow Search Algorithm,and MSSA Algorithm were employed to solve various test functions.The accuracy and convergence speed of each algorithm were then compared and analyzed.The results indicate that the MSSA algorithm has superior solving ability and stability compared to other algorithms.To further validate the enhanced algorithm’s capabilities for path planning,evacuation experiments were conducted using different maps featuring various obstacle types.Additionally,a multi-exit evacuation scenario was constructed according to the actual building environment of a teaching building.Both the sparrow search algorithm and MSSA algorithm were employed in the simulation experiment for multiexit evacuation path planning.The findings demonstrate that the MSSA algorithm outperforms the comparison algorithm,showcasing its greater advantages and higher application potential.

Multi-strategy hybrid whale optimization algorithms for complex constrained optimization problems

A multi-strategy hybrid whale optimization algorithm(MSHWOA)for complex constrained optimization problems is proposed to overcome the drawbacks of easily trapping into local optimum,slow convergence speed and low optimization precision.Firstly,the population is initialized by introducing the theory of good point set,which increases the randomness and diversity of the population and lays the foundation for the global optimization of the algorithm.Then,a novel linearly update equation of convergence factor is designed to coordinate the abilities of exploration and exploitation.At the same time,the global exploration and local exploitation capabilities are improved through the siege mechanism of Harris Hawks optimization algorithm.Finally,the simulation experiments are conducted on the 6 benchmark functions and Wilcoxon rank sum test to evaluate the optimization performance of the improved algorithm.The experimental results show that the proposed algorithm has more significant improvement in optimization accuracy,convergence speed and robustness than the comparison algorithm.

Attribute Reduction of Neighborhood Rough Set Based on Discernment

For neighborhood rough set attribute reduction algorithms based on dependency degree,a neighborhood computation method incorporating attribute weight values and a neighborhood rough set attribute reduction algorithm using discernment as the heuristic information was proposed.The reduction algorithm comprehensively considers the dependency degree and neighborhood granulation degree of attributes,allowing for a more accurate measurement of the importance degrees of attributes.Example analyses and experimental results demonstrate the feasibility and effectiveness of the algorithm.

A Hybrid Genetic Algorithm for Reduct of Attributes in Decision System Based on Rough Set Theory

Knowledge reduction is an important issue when dealing with huge amounts of data. And it has been proved that computing the minimal reduct of decision system is NP-complete. By introducing heuristic information into genetic algorithm, we proposed a heuristic genetic algorithm. In the genetic algorithm, we constructed a new operator to maintaining the classification ability. The experiment shows that our algorithm is efficient and effective for minimal reduct, even for the special example that the simple heuristic algorithm can’t get the right result.

A Correntropy-based Affine Iterative Closest Point Algorithm for Robust Point Set Registration

The iterative closest point(ICP)algorithm has the advantages of high accuracy and fast speed for point set registration,but it performs poorly when the point set has a large number of noisy outliers.To solve this problem,we propose a new affine registration algorithm based on correntropy which works well in the affine registration of point sets with outliers.Firstly,we substitute the traditional measure of least squares with a maximum correntropy criterion to build a new registration model,which can avoid the influence of outliers.To maximize the objective function,we then propose a robust affine ICP algorithm.At each iteration of this new algorithm,we set up the index mapping of two point sets according to the known transformation,and then compute the closed-form solution of the new transformation according to the known index mapping.Similar to the traditional ICP algorithm,our algorithm converges to a local maximum monotonously for any given initial value.Finally,the robustness and high efficiency of affine ICP algorithm based on correntropy are demonstrated by 2D and 3D point set registration experiments.

Immune algorithm for discretization of decision systems in rough set theory

Rough set theory plays an important role in knowledge discovery, but cannot deal with continuous attributes, thus discretization is a problem which we cannot neglect. And discretization of decision systems in rough set theory has some particular characteristics. Consistency must be satisfied and cuts for discretization is expected to be as small as possible. Consistent and minimal discretization problem is NP-complete. In this paper, an immune algorithm for the problem is proposed. The correctness and effectiveness were shown in experiments. The discretization method presented in this paper can also be used as a data pre- treating step for other symbolic knowledge discovery or machine learning methods other than rough set theory.

Unsupervised Quick Reduct Algorithm Using Rough Set Theory

Feature selection （FS） is a process to select features which are more informative. It is one of the important steps in knowledge discovery. The problem is that not all features are important. Some of the features may be redundant, and others may be irrelevant and noisy. The conventional supervised FS methods evaluate various feature subsets using an evaluation function or metric to select only those features which are related to the decision classes of the data under consideration. However, for many data mining applications, decision class labels are often unknown or incomplete, thus indicating the significance of unsupervised feature selection. However, in unsupervised learning, decision class labels are not provided. In this paper, we propose a new unsupervised quick reduct （QR） algorithm using rough set theory. The quality of the reduced data is measured by the classification performance and it is evaluated using WEKA classifier tool. The method is compared with existing supervised methods and the result demonstrates the efficiency of the proposed algorithm.

Prediction method of rock burst proneness based on rough set and genetic algorithm

A new method based on rough set theory and genetic algorithm was proposedto predict the rock burst proneness. Nine influencing factors were first selected, and then,the decision table was set up. Attributes were reduced by genetic algorithm. Rough setwas used to extract the simplified decision rules of rock burst proneness. Taking the practical engineering for example, the rock burst proneness was evaluated and predicted bydecision rules. Comparing the prediction results with the actual results, it shows that theproposed method is feasible and effective.

Heuristic Genetic Algorithm for Discretization of Continuous Attributes in Rough Set Theory

Discretization based on rough set theory aims to seek the possible minimum number of the cut set without weakening the indiscemibility of the original decision system. Optimization of discretization is an NP-complete problem and the genetic algorithm is an appropriate method to solve it. In order to achieve optimal discretization, first the choice of the initial set of cut set is discussed, because a good initial cut set can enhance the efficiency and quality of the follow-up algorithm. Second, an effective heuristic genetic algorithm for discretization of continuous attributes of the decision table is proposed, which takes the significance of cut dots as heuristic information and introduces a novel operator to maintain the indiscernibility of the original decision system and enhance the local research ability of the algorithm. So the algorithm converges quickly and has global optimizing ability. Finally, the effectiveness of the algorithm is validated through experiment.

A neurofuzzy system based on rough set theory and genetic algorithm

This paper presents a hybrid soft computing modeling approach for a neurofuzzy system based on rough set theory and the genetic algorithms (NFRSGA). The fundamental problem of a neurofuzzy system is that when the input dimension increases, the fuzzy rule base increases exponentially. This leads to a huge infrastructure network which results in slow convergence. To solve this problem, rough set theory is used to obtain the reductive rules, which are used as fuzzy rules of the fuzzy system. The number of rules decrease, and each rule does not need all the conditional attribute values. This results in a reduced, or not fully connected, neural network. The structure of the neural network is relatively small and thus the weights to be trained decrease. The genetic algorithm is used to search the optimal discretization of the continuous attributes. The NFRSGA approach has been applied in the practical application of building a soft sensor model for estimating the freezing point of the light diesel fuel in a Fluid Catalytic Cracking Unit (FCCU), and satisfying results are obtained.

Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

Currently,the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems.In this sense,metaheuristics have been a common trend in the field in order to design approaches to solve them successfully.Thus,a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments.Following the No Free Lunch theorem,we are interested in testing the performance of the Fruit Fly Algorithm,this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces,based on the foraging behavior of the fruit fly,which usually has much better sensory perception of smell and vision than any other species.On the other hand,the Set Coverage Problem is a well-known NP-hard problem with many practical applications,including production line balancing,utility installation,and crew scheduling in railroad and mass transit companies.In this paper,we propose different binarization methods for the Fruit Fly Algorithm,using Sshaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space.We are motivated with this approach,because in this way we can deliver to future researchers interested in this area,a way to be able to work with continuous metaheuristics in binary domains.This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost.

A NEW UNSUPERVISED CLASSIFICATION ALGORITHM FOR POLARIMETRIC SAR IMAGES BASED ON FUZZY SET THEORY

In this letter, a new method is proposed for unsupervised classification of terrain types and man-made objects using POLarimetric Synthetic Aperture Radar (POLSAR) data. This technique is a combi-nation of the usage of polarimetric information of SAR images and the unsupervised classification method based on fuzzy set theory. Image quantization and image enhancement are used to preprocess the POLSAR data. Then the polarimetric information and Fuzzy C-Means (FCM) clustering algorithm are used to classify the preprocessed images. The advantages of this algorithm are the automated classification, its high classifica-tion accuracy, fast convergence and high stability. The effectiveness of this algorithm is demonstrated by ex-periments using SIR-C/X-SAR (Spaceborne Imaging Radar-C/X-band Synthetic Aperture Radar) data.

Active set truncated-Newton algorithm for simultaneous optimization of distillation column

An active set truncated-Newton algorithm (ASTNA) is proposed to solve the large-scale bound constrained sub-problems. The global convergence of the algorithm is obtained and two groups of numerical experiments are made for the various large-scale problems of varying size. The comparison results between ASTNA and the subspace limited memory quasi-Newton algorithm and between the modified augmented Lagrange multiplier methods combined with ASTNA and the modified barrier function method show the stability and effectiveness of ASTNA for simultaneous optimization of distillation column.

Bi-extrapolated subgradient projection algorithm for solving multiple-sets split feasibility problem

This paper deals with a bi-extrapolated subgradient projection algorithm by intro- ducing two extrapolated factors in the iterative step to solve the multiple-sets split feasibility problem. The strategy is intend to improve the convergence. And its convergence is proved un- der some suitable conditions. Numerical results illustrate that the bi-extrapolated subgradient projection algorithm converges more quickly than the existing algorithms.

A Modified Genetic Algorithm for Maximum Independent Set Problems

genetic algorithm is proposed for maximum independent set problems. A specially designed mutation operato is adopted to search the solution space more efficienily, where adjacen relation of a graph is inte-grated. The DIMACS benchmark graphs are used to test our algorithm, and the results show that the algorithm outper-forms our previous version. Moreover two new low bounds are found for graphs in DIMACS.

Neutrosophic Adaptive Clustering Optimization in Genetic Algorithm and Its Application in Cubic Assignment Problem

In optimization theory,the adaptive control of the optimization process is an important goal that people pursue.To solve this problem,this study introduces the idea of neutrosophic decision-making into classical heuristic algorithm,and proposes a novel neutrosophic adaptive clustering optimization thought,which is applied in a novel neutrosophic genetic algorithm(NGA),for example.The main feature of NGA is that the NGA treats the crossover effect as a neutrosophic fuzzy set,the variation ratio as a structural parameter,the crossover effect as a benefit parameter and the variation effect as a cost parameter,and then a neutrosophic fitness function value is created.Finally,a high order assignment problem in warehousemanagement is taken to illustrate the effectiveness of NGA.

Efficient Information Set Decoding Based on Genetic Algorithms

In this paper, we describe a hard-decision decoding technique based on Genetic Algorithms (HDGA), which is applicable to the general case of error correcting codes where the only known structure is given by the generating matrix G. Then we present a new soft-decision decoding based on HDGA and the Chase algorithm (SDGA). The performance of some binary and non-binary Linear Block Codes are given for HDGA and SDGA over Gaussian and Rayleigh channels. The performances show that the HDGA decoder has the same performances as the Berlekamp-Massey Algorithm (BMA) in various transmission channels. On the other hand, the performances of SDGA are equivalent to soft-decision decoding using Chase algorithm and BMA (Chase-BMA). The complexity of decoders proposed is also discussed and compared to those of other decoders.

Local Search-Inspired Rough Sets for Improving Multiobjective Evolutionary Algorithm

In this paper we present a new optimization algorithm, and the proposed algorithm operates in two phases. In the first one, multiobjective version of genetic algorithm is used as search engine in order to generate approximate true Pareto front. This algorithm is based on concept of co-evolution and repair algorithm for handling nonlinear constraints. Also it maintains a finite-sized archive of non-dominated solutions which gets iteratively updated in the presence of new solutions based on the concept e-dominance. Then, in the second stage, rough set theory is adopted as local search engine in order to improve the spread of the solutions found so far. The results, provided by the proposed algorithm for benchmark problems, are promising when compared with exiting well-known algorithms. Also, our results suggest that our algorithm is better applicable for solving real-world application problems.