In this paper, based on the following theoretical framework: Evolutionary Algorithms + Program Structures = Automatic Programming , some results on complexity of automatic programming for function modeling is given, w...In this paper, based on the following theoretical framework: Evolutionary Algorithms + Program Structures = Automatic Programming , some results on complexity of automatic programming for function modeling is given, which show that the complexity of automatic programming is an exponential function of the problem dimension N , the size of operator set ｜F｜ and the height of the program parse tree H . Following this results, the difficulties of automatic programming are discussed. Some function models discovered automatically from database by evolutionary modeling method are given, too.展开更多
The popular single-factor complexity measure cannot comprehensively reflect program complexity and the existing hybrid complexity measure cannot express the interactive behaviors of programs. To treat these problems, ...The popular single-factor complexity measure cannot comprehensively reflect program complexity and the existing hybrid complexity measure cannot express the interactive behaviors of programs. To treat these problems, in this paper, we propose a complexity measure based on program slicing（CMBPS）. CMPBS not only can evaluate factors which affect program complexity such as the length of the program, control flow, data flow and data types of output variables, but also can give expression of the interactive relation between programs. And we also prove that CMBPS satisfies all of Weyuker properties. Compared with the popular complexity measures, CMBPS is a well-structured complexity measure.展开更多
This paper considers problems of the mathematical simulation of gas turbine engines and power plants.A program complex is presented which is capable of automatizing solutions of many problems concerning the theromo-ga...This paper considers problems of the mathematical simulation of gas turbine engines and power plants.A program complex is presented which is capable of automatizing solutions of many problems concerning the theromo-gas-dynamic calculation of the engine flow passage at the stages of design,development and service.A universal mathematical model is provided which real- izes all calculation for engines of different structure schemes (including test-bench) under different regimes.This program complex includes modules WHICGBH.It can solve problems of optimiza- tion,identification and diagnostics.Software is realized on the computer ES and PC(IBM PC). Kazan Aviation Institute K.Marx Str.10 Kazan 420111 Elousi,USSR展开更多
Unmanned aerial vehicles(UAVs) may play an important role in data collection and offloading in vast areas deploying wireless sensor networks, and the UAV’s action strategy has a vital influence on achieving applicabi...Unmanned aerial vehicles(UAVs) may play an important role in data collection and offloading in vast areas deploying wireless sensor networks, and the UAV’s action strategy has a vital influence on achieving applicability and computational complexity. Dynamic programming(DP) has a good application in the path planning of UAV, but there are problems in the applicability of special terrain environment and the complexity of the algorithm.Based on the analysis of DP, this paper proposes a hierarchical directional DP(DDP) algorithm based on direction determination and hierarchical model. We compare our methods with Q-learning and DP algorithm by experiments, and the results show that our method can improve the terrain applicability, meanwhile greatly reduce the computational complexity.展开更多
In this paper, we propose an arc-search interior-point algorithm for convex quadratic programming with a wide neighborhood of the central path, which searches the optimizers along the ellipses that approximate the ent...In this paper, we propose an arc-search interior-point algorithm for convex quadratic programming with a wide neighborhood of the central path, which searches the optimizers along the ellipses that approximate the entire central path. The favorable polynomial complexity bound of the algorithm is obtained, namely O（nlog（（ x^0）~TS^0/ε）） which is as good as the linear programming analogue. Finally, the numerical experiments show that the proposed algorithm is efficient.展开更多
In this paper, the X-ray nondestructive test method of small defects in precision weldments with complex structure was presented. To resolve the difficulty of defect segmentation in variable grey image, the image proc...In this paper, the X-ray nondestructive test method of small defects in precision weldments with complex structure was presented. To resolve the difficulty of defect segmentation in variable grey image, the image processing based on Visual Basic programming method was adopted. The methods of automatic contrast and partial grey stretch were used to enhance the X-ray detection image which has relatively low contrast, then automatic threshold method was carried out to segment the two high intensity zones, and weld zones which contain the small defects was extracted. Smoothing and sharpen processing were proceeded on the extracted weld zones, and small defects in X-ray detection image of weldments with complex structure were segmented by using the method of background subtraction in the end. The effects of raster were eliminated, and because of that the image processing was only proceeded on the extracted weld zones, the calculated speed using the above provided algorithm was improved.展开更多
The existence of strongly polynomial algorithm for linear programming (LP) has been widely sought after for decades. Recently, a new approach called Gravity Sliding algorithm [1] has emerged. It is a gradient descendi...The existence of strongly polynomial algorithm for linear programming (LP) has been widely sought after for decades. Recently, a new approach called Gravity Sliding algorithm [1] has emerged. It is a gradient descending method whereby the descending trajectory slides along the inner surfaces of a polyhedron until it reaches the optimal point. In R3, a water droplet pulled by gravitational force traces the shortest path to descend to the lowest point. As the Gravity Sliding algorithm emulates the water droplet trajectory, it exhibits strongly polynomial behavior in R3. We believe that it could be a strongly polynomial algorithm for linear programming in Rn too. In fact, our algorithm can solve the Klee-Minty deformed cube problem in only two iterations, irrespective of the dimension of the cube. The core of gravity sliding algorithm is how to calculate the projection of the gravity vector g onto the intersection of a group of facets, which is disclosed in the same paper [1]. In this paper, we introduce a more efficient method to compute the gradient projections on complementary facets, and rename it the Sliding Gradient algorithm under the new projection calculation.展开更多
A code developed recently by the authors, for counting and computing the eigenvalues of a complex tridiagonal matrix, as well as the roots of a complex polynomial, which lie in a given region of the complex plane, is ...A code developed recently by the authors, for counting and computing the eigenvalues of a complex tridiagonal matrix, as well as the roots of a complex polynomial, which lie in a given region of the complex plane, is modified to run in parallel on multi-core machines. A basic characteristic of this code (eventually pointing to its parallelization) is that it can proceed with: 1) partitioning the given region into an appropriate number of subregions;2) counting eigenvalues in each subregion;and 3) computing (already counted) eigenvalues in each subregion. Consequently, theoretically speaking, the whole code in itself parallelizes ideally. We carry out several numerical experiments with random complex tridiagonal matrices, and random complex polynomials as well, in order to study the behaviour of the parallel code, especially the degree of declination from theoretical expectations.展开更多
基于回答集语义的逻辑程序(Answer Set Programming,ASP)是描述性问题求解的典范,广泛应用于规划、诊断、调度以及生物信息学等领域。为了增强ASP的表达能力,一些工作在ASP引入了数据库系统中的聚合函数约束,并提出了SPT,FLP等语义,抽...基于回答集语义的逻辑程序(Answer Set Programming,ASP)是描述性问题求解的典范,广泛应用于规划、诊断、调度以及生物信息学等领域。为了增强ASP的表达能力,一些工作在ASP引入了数据库系统中的聚合函数约束,并提出了SPT,FLP等语义,抽象约束剥离聚合函数约束的具体形式成为研究ASP语义等性质的重要工具,并得到了抽象约束逻辑程序的各种回答集语义之间的关系和复杂性问题等的相关结果。对此,进一步研究了仅含凸抽象约束原子抽象约束逻辑的性质,证明了仅含凸抽象约束原子的正规逻辑程序判定是否存在FLP回答集是Σ_(2)^(p)完全的,其审慎推理和大胆推理分别是Π_(2)^(p)完全的和Σ_(2)^(p)完全的。这些复杂性结果进一步理清了各类逻辑程序间的表达能力关系,为设计有效的回答集求解器提供了新的思路,也为进一步探索ASP在解决用凸抽象约束表示的问题中的应用提供了理论基础。展开更多
基金Supported by National Nature Science Foundation of China(6 0 0 730 4370 0 710 42 )
文摘In this paper, based on the following theoretical framework: Evolutionary Algorithms + Program Structures = Automatic Programming , some results on complexity of automatic programming for function modeling is given, which show that the complexity of automatic programming is an exponential function of the problem dimension N , the size of operator set ｜F｜ and the height of the program parse tree H . Following this results, the difficulties of automatic programming are discussed. Some function models discovered automatically from database by evolutionary modeling method are given, too.
基金Supported by the National High Technology Research and Development Program of China(863 Program)(2009AA01220)the National Natural Science Foundation of China(91118007)
文摘The popular single-factor complexity measure cannot comprehensively reflect program complexity and the existing hybrid complexity measure cannot express the interactive behaviors of programs. To treat these problems, in this paper, we propose a complexity measure based on program slicing（CMBPS）. CMPBS not only can evaluate factors which affect program complexity such as the length of the program, control flow, data flow and data types of output variables, but also can give expression of the interactive relation between programs. And we also prove that CMBPS satisfies all of Weyuker properties. Compared with the popular complexity measures, CMBPS is a well-structured complexity measure.
文摘This paper considers problems of the mathematical simulation of gas turbine engines and power plants.A program complex is presented which is capable of automatizing solutions of many problems concerning the theromo-gas-dynamic calculation of the engine flow passage at the stages of design,development and service.A universal mathematical model is provided which real- izes all calculation for engines of different structure schemes (including test-bench) under different regimes.This program complex includes modules WHICGBH.It can solve problems of optimiza- tion,identification and diagnostics.Software is realized on the computer ES and PC(IBM PC). Kazan Aviation Institute K.Marx Str.10 Kazan 420111 Elousi,USSR
基金supported by the National Natural Science Foundation of China(91648204 61601486)+1 种基金State Key Laboratory of High Performance Computing Project Fund(1502-02)Research Programs of National University of Defense Technology(ZDYYJCYJ140601)
文摘Unmanned aerial vehicles(UAVs) may play an important role in data collection and offloading in vast areas deploying wireless sensor networks, and the UAV’s action strategy has a vital influence on achieving applicability and computational complexity. Dynamic programming(DP) has a good application in the path planning of UAV, but there are problems in the applicability of special terrain environment and the complexity of the algorithm.Based on the analysis of DP, this paper proposes a hierarchical directional DP(DDP) algorithm based on direction determination and hierarchical model. We compare our methods with Q-learning and DP algorithm by experiments, and the results show that our method can improve the terrain applicability, meanwhile greatly reduce the computational complexity.
基金Supported by the National Natural Science Foundation of China(71471102)
文摘In this paper, we propose an arc-search interior-point algorithm for convex quadratic programming with a wide neighborhood of the central path, which searches the optimizers along the ellipses that approximate the entire central path. The favorable polynomial complexity bound of the algorithm is obtained, namely O（nlog（（ x^0）~TS^0/ε）） which is as good as the linear programming analogue. Finally, the numerical experiments show that the proposed algorithm is efficient.
文摘In this paper, the X-ray nondestructive test method of small defects in precision weldments with complex structure was presented. To resolve the difficulty of defect segmentation in variable grey image, the image processing based on Visual Basic programming method was adopted. The methods of automatic contrast and partial grey stretch were used to enhance the X-ray detection image which has relatively low contrast, then automatic threshold method was carried out to segment the two high intensity zones, and weld zones which contain the small defects was extracted. Smoothing and sharpen processing were proceeded on the extracted weld zones, and small defects in X-ray detection image of weldments with complex structure were segmented by using the method of background subtraction in the end. The effects of raster were eliminated, and because of that the image processing was only proceeded on the extracted weld zones, the calculated speed using the above provided algorithm was improved.
文摘The existence of strongly polynomial algorithm for linear programming (LP) has been widely sought after for decades. Recently, a new approach called Gravity Sliding algorithm [1] has emerged. It is a gradient descending method whereby the descending trajectory slides along the inner surfaces of a polyhedron until it reaches the optimal point. In R3, a water droplet pulled by gravitational force traces the shortest path to descend to the lowest point. As the Gravity Sliding algorithm emulates the water droplet trajectory, it exhibits strongly polynomial behavior in R3. We believe that it could be a strongly polynomial algorithm for linear programming in Rn too. In fact, our algorithm can solve the Klee-Minty deformed cube problem in only two iterations, irrespective of the dimension of the cube. The core of gravity sliding algorithm is how to calculate the projection of the gravity vector g onto the intersection of a group of facets, which is disclosed in the same paper [1]. In this paper, we introduce a more efficient method to compute the gradient projections on complementary facets, and rename it the Sliding Gradient algorithm under the new projection calculation.
文摘A code developed recently by the authors, for counting and computing the eigenvalues of a complex tridiagonal matrix, as well as the roots of a complex polynomial, which lie in a given region of the complex plane, is modified to run in parallel on multi-core machines. A basic characteristic of this code (eventually pointing to its parallelization) is that it can proceed with: 1) partitioning the given region into an appropriate number of subregions;2) counting eigenvalues in each subregion;and 3) computing (already counted) eigenvalues in each subregion. Consequently, theoretically speaking, the whole code in itself parallelizes ideally. We carry out several numerical experiments with random complex tridiagonal matrices, and random complex polynomials as well, in order to study the behaviour of the parallel code, especially the degree of declination from theoretical expectations.
文摘基于回答集语义的逻辑程序(Answer Set Programming,ASP)是描述性问题求解的典范,广泛应用于规划、诊断、调度以及生物信息学等领域。为了增强ASP的表达能力,一些工作在ASP引入了数据库系统中的聚合函数约束,并提出了SPT,FLP等语义,抽象约束剥离聚合函数约束的具体形式成为研究ASP语义等性质的重要工具,并得到了抽象约束逻辑程序的各种回答集语义之间的关系和复杂性问题等的相关结果。对此,进一步研究了仅含凸抽象约束原子抽象约束逻辑的性质,证明了仅含凸抽象约束原子的正规逻辑程序判定是否存在FLP回答集是Σ_(2)^(p)完全的,其审慎推理和大胆推理分别是Π_(2)^(p)完全的和Σ_(2)^(p)完全的。这些复杂性结果进一步理清了各类逻辑程序间的表达能力关系,为设计有效的回答集求解器提供了新的思路,也为进一步探索ASP在解决用凸抽象约束表示的问题中的应用提供了理论基础。
