The backtracking search optimization algorithm（BSA） is one of the most recently proposed population-based evolutionary algorithms for global optimization. Due to its memory ability and simple structure, BSA has powe...The backtracking search optimization algorithm（BSA） is one of the most recently proposed population-based evolutionary algorithms for global optimization. Due to its memory ability and simple structure, BSA has powerful capability to find global optimal solutions. However, the algorithm is still insufficient in balancing the exploration and the exploitation. Therefore, an improved adaptive backtracking search optimization algorithm combined with modified Hooke-Jeeves pattern search is proposed for numerical global optimization. It has two main parts： the BSA is used for the exploration phase and the modified pattern search method completes the exploitation phase. In particular, a simple but effective strategy of adapting one of BSA＇s important control parameters is introduced. The proposed algorithm is compared with standard BSA, three state-of-the-art evolutionary algorithms and three superior algorithms in IEEE Congress on Evolutionary Computation 2014（IEEE CEC2014） over six widely-used benchmarks and 22 real-parameter single objective numerical optimization benchmarks in IEEE CEC2014. The results of experiment and statistical analysis demonstrate the effectiveness and efficiency of the proposed algorithm.展开更多
In the distribution center, the way of order picking personnel to pick goods has two kinds: single picking and batch picking. Based on the way of the single picking and assumed warehouse model, in order to reduce the ...In the distribution center, the way of order picking personnel to pick goods has two kinds: single picking and batch picking. Based on the way of the single picking and assumed warehouse model, in order to reduce the walking path of order picking, the order picking problem is transformed into the traveling salesman problem in this paper. Based on backtracking algorithm, the order picking path gets optimized. Finally verifing the optimization method under the environment of VC++6.0, order picking path in the warehouse model get optimized, and compared with the traditional order picking walking paths. The results show that in small and medium-sized warehouse, the optimization method proposed in this paper can reduce order picking walking path and improve the work efficiency as well as reduce the time cost.展开更多
Failure-insensitive routing is a good mechanism to avoid packet dropping and disconnection of forwarding when some links fail, but multiple failure links may bring routing loop for the mechanism. Backtracking routing ...Failure-insensitive routing is a good mechanism to avoid packet dropping and disconnection of forwarding when some links fail, but multiple failure links may bring routing loop for the mechanism. Backtracking routing algorithm based on inverse shortest path tree rooted at destination is presented. The feasible restoration routing is obtained through searching from the start of the failure link and tracing back to the leaves of the shortest path tree with the destination as the root. The packets are forwarded from the mounted point with smaller sequence to the mount point with bigger sequence to decrease the possible of loop in case of multi-failures. The simulations and analysis indicate that backtracking routing algorithm improves the network survivability especially for large network, at the cost of the computation complexity in the same order as failure insensitive routing.展开更多
In this paper, we propose a new hybrid method called SQPBSA which combines backtracking search optimization algorithm （BSA） and sequential quadratic programming （SQP）. BSA, as an exploration search engine, gives a...In this paper, we propose a new hybrid method called SQPBSA which combines backtracking search optimization algorithm （BSA） and sequential quadratic programming （SQP）. BSA, as an exploration search engine, gives a good direction to the global optimal region, while SQP is used as a local search technique to exploit the optimal solution. The experiments are carried on two suits of 28 functions proposed in the CEC-2013 competitions to verify the performance of SQPBSA. The results indicate the proposed method is effective and competitive.展开更多
Quality traceability plays an essential role in assembling and welding offshore platform blocks.The improvement of the welding quality traceability system is conducive to improving the durability of the offshore platf...Quality traceability plays an essential role in assembling and welding offshore platform blocks.The improvement of the welding quality traceability system is conducive to improving the durability of the offshore platform and the process level of the offshore industry.Currently,qualitymanagement remains in the era of primary information,and there is a lack of effective tracking and recording of welding quality data.When welding defects are encountered,it is difficult to rapidly and accurately determine the root cause of the problem from various complexities and scattered quality data.In this paper,a composite welding quality traceability model for offshore platform block construction process is proposed,it contains the quality early-warning method based on long short-term memory and quality data backtracking query optimization algorithm.By fulfilling the training of the early-warning model and the implementation of the query optimization algorithm,the quality traceability model has the ability to assist enterprises in realizing the rapid identification and positioning of quality problems.Furthermore,the model and the quality traceability algorithm are checked by cases in actual working conditions.Verification analyses suggest that the proposed early-warningmodel for welding quality and the algorithmfor optimizing backtracking requests are effective and can be applied to the actual construction process.展开更多
A large number of sparse signal reconstruction algorithms have been continuously proposed, but almost all greedy algorithms add a fixed number of indices to the support set in each iteration. Although the mechanism of...A large number of sparse signal reconstruction algorithms have been continuously proposed, but almost all greedy algorithms add a fixed number of indices to the support set in each iteration. Although the mechanism of selecting the fixed number of indexes improves the reconstruction efficiency, it also brings the problem of low index selection accuracy. Based on the full study of the theory of compressed sensing, we propose a dynamic indexes selection strategy based on residual update to improve the performance of the compressed sampling matching pursuit algorithm (CoSaMP). As an extension of CoSaMP algorithm, the proposed algorithm adopts a residual comparison strategy to improve the accuracy of backtracking selected indexes. This backtracking strategy can efficiently select backtracking indexes. And without increasing the computational complexity, the proposed improvement algorithm has a higher exact reconstruction rate and peak signal to noise ratio (PSNR). Simulation results demonstrate the proposed algorithm significantly outperforms the CoSaMP for image recovery and one-dimensional signal.展开更多
An efficient and stable structure preserving algorithm, which is a variant of the QR like (SR) algorithm due to Bunse-Gerstner and Mehrmann, is presented for computing the eigenvalues and stable invariant subspaces of...An efficient and stable structure preserving algorithm, which is a variant of the QR like (SR) algorithm due to Bunse-Gerstner and Mehrmann, is presented for computing the eigenvalues and stable invariant subspaces of a Hamiltonian matrix. In the algorithm two strategies are employed, one of which is called dis-unstabilization technique and the other is preprocessing technique. Together with them, a so-called ratio-reduction equation and a backtrack technique are introduced to avoid the instability and breakdown in the original algorithm. It is shown that the new algorithm can overcome the instability and breakdown at low cost. Numerical results have demonstrated that the algorithm is stable and can compute the eigenvalues to very high accuracy.展开更多
A binary tree can be represented by a code reflecting the traversal of the corresponding regular binary tree in given monotonic order. A different coding scheme based on the branches of a regular binary tree with n-no...A binary tree can be represented by a code reflecting the traversal of the corresponding regular binary tree in given monotonic order. A different coding scheme based on the branches of a regular binary tree with n-nodes is proposed. It differs from the coding scheme generally used and makes no distinction between internal nodes and terminal nodes. A code of a regular binary tree with nnodes is formed by labeling the left branches by O’s and the right branches by l’s and then traversing these branches in pre-order. Root is always assumed to be on a left branch.展开更多
This paper describes the construction and enumeration of mixed orthogonal arrays (MOA) to produce optimal experimental designs. A MOA is a multiset whose rows are the different combinations of factor levels, discrete ...This paper describes the construction and enumeration of mixed orthogonal arrays (MOA) to produce optimal experimental designs. A MOA is a multiset whose rows are the different combinations of factor levels, discrete values of the variable under study, having very well defined features such as symmetry and strength three (all main interactions are taken in consideration). The applied methodology blends the fields of combinatorics and group theory by applying the ideas of orbits, stabilizers and isomorphisms to array generation and enumeration. Integer linear programming was used in order to exploit the symmetry property of the arrays under study. The backtrack search algorithm was used to find suitable arrays in the underlying space of possible solutions. To test the performance of the MOAs, an engineered system was used as a case study within the stage of parameter design. The analysis showed how the MOAs were capable of meeting the fundamental engineering design axioms and principles, creating optimal experimental designs within the desired context.展开更多
We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian...We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.展开更多
A fault-tolerant and heuristic routing algorithm for faulty hypercube sys-tems is described. To improve the efficiency, the algorithm adopts a heuristic backtracking strategy and each node has an array to record its a...A fault-tolerant and heuristic routing algorithm for faulty hypercube sys-tems is described. To improve the efficiency, the algorithm adopts a heuristic backtracking strategy and each node has an array to record its all neighbors'faulty link information to avoid unnecessary searching for the known faulty links. Furthermore, the faulty link information is dynamically accumulated and the technique of heuristically searching for optimal link is used. The algo rithm routes messages through the minimum feasible path between the sender and receiver if at Ieast one such path ekists, and ta.kes the optimal path with higher probability when faulty links exist in the faulty hypercube.展开更多
Solving a quantified constraint satisfaction problem(QCSP)is usually a hard task due to its computational complexity.Exact algorithms play an important role in solving this problem,among which backtrack algorithms are...Solving a quantified constraint satisfaction problem(QCSP)is usually a hard task due to its computational complexity.Exact algorithms play an important role in solving this problem,among which backtrack algorithms are effective.In a backtrack algorithm,an important step is assigning a variable by a chosen value when exploiting a branch,and thus a good value selection rule may speed up greatly.In this paper,we propose two value selection rules for existentially and universally quantified variables,respectively,to avoid unnecessary searching.The rule for universally quantified variables is prior to trying failure values in previous branches,and the rule for existentially quantified variables selects the promising values first.Two rules are integrated into the state-of-the-art QCSP solver,i.e.,QCSP-Solve,which is an exact solver based on backtracking.We perform a number of experiments to evaluate improvements brought by our rules.From computational results,we can conclude that the new value selection rules speed up the solver by 5 times on average and 30 times at most.We also show both rules perform well particularly on instances with existentially and universally quantified variables occurring alternatively.展开更多
This paper deals with model genemtion for equational theories, i.e, auto-matically generating (finite) models of a given set of (logical) equations. Ourmethod of finite model generation and a tool for automatic constr...This paper deals with model genemtion for equational theories, i.e, auto-matically generating (finite) models of a given set of (logical) equations. Ourmethod of finite model generation and a tool for automatic construction of finitealgebras is described. Some examples are given to show the applications of ourprogram. We argue that, the combination of model generators and theoremprovers enables us to get a better understanding of logical theories. A briefcomparison between our tool and other similar tools is also presented.展开更多
基金supported by the National Natural Science Foundation of China(61271250)
文摘The backtracking search optimization algorithm（BSA） is one of the most recently proposed population-based evolutionary algorithms for global optimization. Due to its memory ability and simple structure, BSA has powerful capability to find global optimal solutions. However, the algorithm is still insufficient in balancing the exploration and the exploitation. Therefore, an improved adaptive backtracking search optimization algorithm combined with modified Hooke-Jeeves pattern search is proposed for numerical global optimization. It has two main parts： the BSA is used for the exploration phase and the modified pattern search method completes the exploitation phase. In particular, a simple but effective strategy of adapting one of BSA＇s important control parameters is introduced. The proposed algorithm is compared with standard BSA, three state-of-the-art evolutionary algorithms and three superior algorithms in IEEE Congress on Evolutionary Computation 2014（IEEE CEC2014） over six widely-used benchmarks and 22 real-parameter single objective numerical optimization benchmarks in IEEE CEC2014. The results of experiment and statistical analysis demonstrate the effectiveness and efficiency of the proposed algorithm.
文摘In the distribution center, the way of order picking personnel to pick goods has two kinds: single picking and batch picking. Based on the way of the single picking and assumed warehouse model, in order to reduce the walking path of order picking, the order picking problem is transformed into the traveling salesman problem in this paper. Based on backtracking algorithm, the order picking path gets optimized. Finally verifing the optimization method under the environment of VC++6.0, order picking path in the warehouse model get optimized, and compared with the traditional order picking walking paths. The results show that in small and medium-sized warehouse, the optimization method proposed in this paper can reduce order picking walking path and improve the work efficiency as well as reduce the time cost.
基金Supported by the National Natural Science Foundation of China (60502028)
文摘Failure-insensitive routing is a good mechanism to avoid packet dropping and disconnection of forwarding when some links fail, but multiple failure links may bring routing loop for the mechanism. Backtracking routing algorithm based on inverse shortest path tree rooted at destination is presented. The feasible restoration routing is obtained through searching from the start of the failure link and tracing back to the leaves of the shortest path tree with the destination as the root. The packets are forwarded from the mounted point with smaller sequence to the mount point with bigger sequence to decrease the possible of loop in case of multi-failures. The simulations and analysis indicate that backtracking routing algorithm improves the network survivability especially for large network, at the cost of the computation complexity in the same order as failure insensitive routing.
基金Acknowledgements This work was supported by the NSFC-Guangdong Joint Fund （U1201258）, the National Natural Science Foundation of China （Grant No. 61573219）, the Shandong Natural Science Funds for Distinguished Young Scholars （JQ201316）, the Fundamental Research Funds of Shandong University （2014JC028）, and the Natural Science Foundation of Fujian Province of China （2016J01280）.
文摘In this paper, we propose a new hybrid method called SQPBSA which combines backtracking search optimization algorithm （BSA） and sequential quadratic programming （SQP）. BSA, as an exploration search engine, gives a good direction to the global optimal region, while SQP is used as a local search technique to exploit the optimal solution. The experiments are carried on two suits of 28 functions proposed in the CEC-2013 competitions to verify the performance of SQPBSA. The results indicate the proposed method is effective and competitive.
基金funded by Ministry of Industry and Information Technology of the People’s Republic of China[Grant No.2018473].
文摘Quality traceability plays an essential role in assembling and welding offshore platform blocks.The improvement of the welding quality traceability system is conducive to improving the durability of the offshore platform and the process level of the offshore industry.Currently,qualitymanagement remains in the era of primary information,and there is a lack of effective tracking and recording of welding quality data.When welding defects are encountered,it is difficult to rapidly and accurately determine the root cause of the problem from various complexities and scattered quality data.In this paper,a composite welding quality traceability model for offshore platform block construction process is proposed,it contains the quality early-warning method based on long short-term memory and quality data backtracking query optimization algorithm.By fulfilling the training of the early-warning model and the implementation of the query optimization algorithm,the quality traceability model has the ability to assist enterprises in realizing the rapid identification and positioning of quality problems.Furthermore,the model and the quality traceability algorithm are checked by cases in actual working conditions.Verification analyses suggest that the proposed early-warningmodel for welding quality and the algorithmfor optimizing backtracking requests are effective and can be applied to the actual construction process.
文摘A large number of sparse signal reconstruction algorithms have been continuously proposed, but almost all greedy algorithms add a fixed number of indices to the support set in each iteration. Although the mechanism of selecting the fixed number of indexes improves the reconstruction efficiency, it also brings the problem of low index selection accuracy. Based on the full study of the theory of compressed sensing, we propose a dynamic indexes selection strategy based on residual update to improve the performance of the compressed sampling matching pursuit algorithm (CoSaMP). As an extension of CoSaMP algorithm, the proposed algorithm adopts a residual comparison strategy to improve the accuracy of backtracking selected indexes. This backtracking strategy can efficiently select backtracking indexes. And without increasing the computational complexity, the proposed improvement algorithm has a higher exact reconstruction rate and peak signal to noise ratio (PSNR). Simulation results demonstrate the proposed algorithm significantly outperforms the CoSaMP for image recovery and one-dimensional signal.
文摘An efficient and stable structure preserving algorithm, which is a variant of the QR like (SR) algorithm due to Bunse-Gerstner and Mehrmann, is presented for computing the eigenvalues and stable invariant subspaces of a Hamiltonian matrix. In the algorithm two strategies are employed, one of which is called dis-unstabilization technique and the other is preprocessing technique. Together with them, a so-called ratio-reduction equation and a backtrack technique are introduced to avoid the instability and breakdown in the original algorithm. It is shown that the new algorithm can overcome the instability and breakdown at low cost. Numerical results have demonstrated that the algorithm is stable and can compute the eigenvalues to very high accuracy.
文摘A binary tree can be represented by a code reflecting the traversal of the corresponding regular binary tree in given monotonic order. A different coding scheme based on the branches of a regular binary tree with n-nodes is proposed. It differs from the coding scheme generally used and makes no distinction between internal nodes and terminal nodes. A code of a regular binary tree with nnodes is formed by labeling the left branches by O’s and the right branches by l’s and then traversing these branches in pre-order. Root is always assumed to be on a left branch.
文摘This paper describes the construction and enumeration of mixed orthogonal arrays (MOA) to produce optimal experimental designs. A MOA is a multiset whose rows are the different combinations of factor levels, discrete values of the variable under study, having very well defined features such as symmetry and strength three (all main interactions are taken in consideration). The applied methodology blends the fields of combinatorics and group theory by applying the ideas of orbits, stabilizers and isomorphisms to array generation and enumeration. Integer linear programming was used in order to exploit the symmetry property of the arrays under study. The backtrack search algorithm was used to find suitable arrays in the underlying space of possible solutions. To test the performance of the MOAs, an engineered system was used as a case study within the stage of parameter design. The analysis showed how the MOAs were capable of meeting the fundamental engineering design axioms and principles, creating optimal experimental designs within the desired context.
基金the National Science Foundation Grant (10871130) of Chinathe Ph.D.Foundation Grant (0527003)+1 种基金the Shanghai Leading Academic Discipline Project (T0401)the Science Foundation Grant (05DZ11) of Shanghai Education Committee
文摘We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.
文摘A fault-tolerant and heuristic routing algorithm for faulty hypercube sys-tems is described. To improve the efficiency, the algorithm adopts a heuristic backtracking strategy and each node has an array to record its all neighbors'faulty link information to avoid unnecessary searching for the known faulty links. Furthermore, the faulty link information is dynamically accumulated and the technique of heuristically searching for optimal link is used. The algo rithm routes messages through the minimum feasible path between the sender and receiver if at Ieast one such path ekists, and ta.kes the optimal path with higher probability when faulty links exist in the faulty hypercube.
基金We would like to thank Dr.Peter Nightingale for the source code of QCSP-Solve.The work described in this paper was supported by the National Natural Science Foundation of China(Granted Nos.61972063,61763003,61672122,61602077,61402070)the Fundamental Research Funds for the Central Universities(3132019029,3132019355).
文摘Solving a quantified constraint satisfaction problem(QCSP)is usually a hard task due to its computational complexity.Exact algorithms play an important role in solving this problem,among which backtrack algorithms are effective.In a backtrack algorithm,an important step is assigning a variable by a chosen value when exploiting a branch,and thus a good value selection rule may speed up greatly.In this paper,we propose two value selection rules for existentially and universally quantified variables,respectively,to avoid unnecessary searching.The rule for universally quantified variables is prior to trying failure values in previous branches,and the rule for existentially quantified variables selects the promising values first.Two rules are integrated into the state-of-the-art QCSP solver,i.e.,QCSP-Solve,which is an exact solver based on backtracking.We perform a number of experiments to evaluate improvements brought by our rules.From computational results,we can conclude that the new value selection rules speed up the solver by 5 times on average and 30 times at most.We also show both rules perform well particularly on instances with existentially and universally quantified variables occurring alternatively.
文摘This paper deals with model genemtion for equational theories, i.e, auto-matically generating (finite) models of a given set of (logical) equations. Ourmethod of finite model generation and a tool for automatic construction of finitealgebras is described. Some examples are given to show the applications of ourprogram. We argue that, the combination of model generators and theoremprovers enables us to get a better understanding of logical theories. A briefcomparison between our tool and other similar tools is also presented.
