关于Backtracking线搜索的一个注记

首次指出,与 Wolfe 线搜索、Goldstein 线搜索和精确线搜索等不同,在一般下降算法模型中使用 Backtracking 线搜索并不能保证全局收敛性。提出了一个改进方案,并在证明线搜索下降算法模型的一个一般全局收敛性定理的基础上,证明改进 Backtracking 线搜索方法能够保证全局收敛性。给出了改进 Backtracking 线搜索的下降算法至少线性收敛的一个充要条件。

Adaptive backtracking search optimization algorithm with pattern search for numerical optimization

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.

Applying the Method for Solving Traveling Salesman Problem Based on Backtracking Algorithm to Order Picking

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.

Backtracking Routing Mechanism for Improving Link Failure Recovery

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.

A new backtracking-based sparsity adaptive algorithm for distributed compressed sensing

A new iterative greedy algorithm based on the backtracking technique was proposed for distributed compressed sensing(DCS) problem. The algorithm applies two mechanisms for precise recovery soft thresholding and cutting. It can reconstruct several compressed signals simultaneously even without any prior information of the sparsity, which makes it a potential candidate for many practical applications, but the numbers of non-zero(significant) coefficients of signals are not available. Numerical experiments are conducted to demonstrate the validity and high performance of the proposed algorithm, as compared to other existing strong DCS algorithms.

Prediction and Backtracking Models of Life Cycle Cost Based on School Facility Conditions in South Korea

After the introduction of BTL （Build-Transfer-Lease） projects in 2005, most construction projects of school facilities have been implemented in BTL system. However, concern about whether the school facilities can be managed appropriately during the 20 year as operation and management period is increasing. Therefore, the necessity of reference for evaluation standard on operating costs and the establishment of LCC （life cycle costing） prediction models is coming to the fore. In this respect, the goal of this study was to extract the variables for LCC-related models and conduct analyses of the correlations of the variables using statistical analysis tool, in order to establish LCC prediction and backtracking model based on BTL project cases of school facilities. The prediction and backtracking model of LCC will be a key for budget equalization or optimum range as one way of estimating method using LCC by year and school type. In the future, it would provide the accurate reference for analyzing and managing the actual input costs against the plan and evaluating the practical cost for long-term facility management plan as the predictive management.

Improved Multi-Path Routing for QoS on MANET

A Mobile Ad hoc NETwork(MANET)is a self-configuring network that is not reliant on infrastructure.This paper introduces a new multipath routing method based on the Multi-Hop Routing(MHR)technique.MHR is the consecutive selection of suitable relay nodes to send information across nodes that are not within direct range of each other.Failing to ensure good MHR leads to several negative consequences,ultimately causing unsuccessful data transmission in a MANET.This research work consists of three portions.The first to attempt to propose an efficient MHR protocol is the design of Priority Based Dynamic Routing(PBDR)to adapt to the dynamic MANET environment by reducing Node Link Failures(NLF)in the network.This is achieved by dynamically considering a node’s mobility parameters like relative velocity and link duration,which enable the next-hop selection.This method works more efficiently than the traditional protocols.Then the second stage is the Improved Multi-Path Dynamic Routing(IMPDR).The enhancement is mainly focused on further improving the Quality of Service(QoS)in MANETs by introducing a QoS timer at every node to help in the QoS routing of MANETs.Since QoS is the most vital metric that assesses a protocol,its dynamic estimation has improved network performance considerably.This method uses distance,linkability,trust,and QoS as the four parameters for the next-hop selection.IMPDR is compared against traditional routing protocols.The Network Simulator-2(NS2)is used to conduct a simulation analysis of the protocols under consideration.The proposed tests are assessed for the Packet Delivery Ratio(PDR),Packet Loss Rate(PLR),End-to-End Delay(EED),and Network Throughput(NT).

Multi-Path Attention Inverse Discrimination Network for Offline Signature Verification

Signature verification,which is a method to distinguish the authenticity of signature images,is a biometric verification technique that can effectively reduce the risk of forged signatures in financial,legal,and other business envir-onments.However,compared with ordinary images,signature images have the following characteristics:First,the strokes are slim,i.e.,there is less effective information.Second,the signature changes slightly with the time,place,and mood of the signer,i.e.,it has high intraclass differences.These challenges lead to the low accuracy of the existing methods based on convolutional neural net-works(CNN).This study proposes an end-to-end multi-path attention inverse dis-crimination network that focuses on the signature stroke parts to extract features by reversing the foreground and background of signature images,which effectively solves the problem of little effective information.To solve the problem of high intraclass variability of signature images,we add multi-path attention modules between discriminative streams and inverse streams to enhance the discriminative features of signature images.Moreover,a multi-path discrimination loss function is proposed,which does not require the feature representation of the samples with the same class label to be infinitely close,as long as the gap between inter-class distance and the intra-class distance is bigger than the set classification threshold,which radically resolves the problem of high intra-class difference of signature images.In addition,this loss can also spur the network to explore the detailed infor-mation on the stroke parts,such as the crossing,thickness,and connection of strokes.We respectively tested on CEDAR,BHSig-Bengali,BHSig-Hindi,and GPDS Synthetic datasets with accuracies of 100%,96.24%,93.86%,and 83.72%,which are more accurate than existing signature verification methods.This is more helpful to the task of signature authentication in justice and finance.

Non-Backtracking Random Walks and a Weighted Ihara’s Theorem

We study the mixing rate of non-backtracking random walks on graphs by looking at non-backtracking walks as walks on the directed edges of a graph. A result known as Ihara’s Theorem relates the adjacency matrix of a graph to a matrix related to non-backtracking walks on the directed edges. We prove a weighted version of Ihara’s Theorem which relates the transition probability matrix of a non-backtracking walk to the transition matrix for the usual random walk. This allows us to determine the spectrum of the transition probability matrix of a non-backtracking random walk in the case of regular graphs and biregular graphs. As a corollary, we obtain a result of Alon et al. in [1] that in most cases, a non-backtracking random walk on a regular graph has a faster mixing rate than the usual random walk. In addition, we obtain an analogous result for biregular graphs.

非合作博弈背景下基于BSA的配电网优化重构

为缓解分布式电源大规模接入对配电网安全稳定运行的影响,提出一种考虑分布式电源输出功率的不确定性的有源配电网优化重构方法.首先,采用非合作博弈理论研究电网调度人员与“大自然”之间的博弈关系,将配电网系统中光伏单元的不确定性视为“大自然”博弈方;其次,以有功网损、负荷均衡度、电压偏差最小为目标函数,建立有源配电网优化重构模型,通过回溯搜索算法(backtracking search algorithm,BSA)进行迭代求解,得到最优重构方案;最后,在IEEE33节点系统进行仿真分析,验证模型的正确性及求解算法的有效性.研究结果表明,相较传统重构方法,本文方法更充分考虑了分布式电源输出功率的不确定性,并且在最恶劣的情况发生时,得到的重构策略能够使配电网系统的有功网损、负荷均衡度、电压偏差指标分别降低0.31%、0.59%、0.48%.

入侵意图分析下的软件定义网络DDoS攻击检测方法

为在数据样本回溯期内解决因本地信息熵值增大而造成的服务攻击问题,维护软件定义网络的运行安全性,提出入侵意图分析下的软件定义网络分布式拒绝服务(DDoS)攻击检测方法。按照软件定义网络场景重构原则,确定因果网转换标准,实现对识别参数的更新处理,完成攻击性行为的入侵意图分析,再定义DDoS数据集,根据攻击行为的时空特性,求解模型参数的取值范围,完成入侵意图分析下软件定义网络DDoS攻击检测方法的设计。实验结果表明,在该算法控制下数据样本回溯期为10 min,低于传统算法,能够较好维护软件定义网络的运行安全性。

基于非回溯矩阵中心性的超图可靠性研究

近年来,超图作为网络科学的一个研究热点,引起了广泛的关注。超图区别于传统图的结构特点在于它的超边可以同时连接多个节点,从而形成更为复杂和高阶的关系。在这样的网络结构中,有效地识别重要的节点和超边成为一个关键的挑战。特征向量中心性是一个常见的度量标准,但当网络中存在着极大度值的枢纽节点时,使用特征向量中心性度量方法会使结果表现出局域性,限制了该方法的应用场景。因此,将超图转化成对应的线图,在此基础上使用非回溯矩阵中心性这一方法,该方法在评估超边重要性时表现出更好的均匀性和区分度。此外,还探讨了特征向量中心性和非回溯矩阵中心性在超图中节点重要性评估上的应用。通过比较这两种方法,研究发现非回溯矩阵中心性在区分节点重要程度方面具有更明显的优势。研究不仅包括理论分析和模型构建,还包括对真实世界数据的实证。为了验证所提方法和结论,选取了6个真实世界超图作为实验对象。通过在这些超图上的应用,证明了非回溯矩阵中心性在识别重要节点和超边方面的有效性。研究为超图中关键元素的识别提供了一种新的视角和方法,对于理解和分析实际复杂网络系统,具有重要的理论和实践意义。

考虑折返行为的元胞自动机人员疏散模型

为研究行人折返行为对疏散的影响,考虑多出口对行人的吸引力、人员相互作用力、火源蔓延威胁以及折返场吸引力的共同影响,在元胞自动机模型的基础上提出基于静态场、动态场、火源场以及折返场共同作用的行人疏散场域模型,研究不同折返比例、折返区域、人员密度、出口数量和位置情况下折返行为对疏散进程的影响。研究结果表明:少量折返行为对总疏散时间影响较小,而群体性折返行为的存在会增加总体疏散时间,随着折返比例的增加,疏散时间随之增加。折返区域离出口越近,对总体疏散效率的影响越小。折返行为对疏散进程的影响效果,随着人员密度的增加不断增强。在双出口条件下,对侧设置出口位置能有效减少折返行为对疏散进程的负面影响。研究结果可为提高紧急情况下的疏散效率提供参考。

时间敏感网络中基于EDWF-MTTF的启发式调度算法

随着工业控制和信息网络的快速融合发展,基于以太网的时间敏感网络受到了广泛关注。时间敏感网络采用时间触发通信调度来保证数据传输的确定性。然而,现有调度算法难以快速计算大规模周期性流量的调度表。因此,设计了基于带权重的最早截止时间-最大传输时间优先的启发式调度算法,通过灵活适配流量排序权重以及回溯增强等方法,可以在较短时间内解决工业自动化场景中大规模流量的调度问题。实验结果表明,相比经典整数线性规划方法,带权重的最早截止时间-最大传输时间优先的启发式调度算法能更快地计算出大规模周期性流量调度表的较优解。

基于回溯树的动态容重比平衡货物配载研究

针对零担物流货物装载率低下的现状,研究货物有限条件下多车多品种货物的货物配载问题,构建以最小化车辆数量、最大化车辆总容积和总载重量利用率为目标的多目标数学模型,考虑到单件货物的装载会对车辆以及车辆集合的剩余容积和剩余载重量产生影响,设计基于动态容重比平衡法和装载回溯树的启发式算法,对算法结果进行非支配排序,得到帕累托解集,计算帕累托解集内每个解的拥挤距离,并选择拥挤距离最大的解为最优装载方案。以算法计算精度和时间复杂度为标准,将所设计算法与NSGA-2、CPLEX算法进行对比分析,算例结果验证了算法的有效性。

双区型仓库订单分批与拣选协同优化研究

针对订单分拣效率低下导致商品出库缓慢的问题,提出一种基于双区型仓库订单分批与拣选的协同优化模型,设计求解模型的CWDP-BSA(clarke-wright and dynamic programming&backtracking search algorithm)协同优化算法。在节约算法中引入快速排序法对订单组合的距离节约值排序,考虑AGV承载量,运用多阶段决策过程最优策略得出状态转移方程求解订单分批模型,确定初始分批方案;并采取多因子选择的回溯搜索算法求解拣选路径模型,以此确定初始拣选方案。再以以上两方案为基础,建立新的基于订单时间窗的订单分批和拣选协同优化模型并求解,进一步优化订单分批和拣选方案。最后通过对比实验得出,平均每批次订单的拣选距离减少了约24.56%,优化后的拣选时间比优化前缩短了约11.4%,在求解不同规模算例时,CWDP-BSA算法的求解结果优于CPLEX软件和其他算法,验证了模型与算法的稳定性和有效性。实验表明,协同优化后的订单分批与物品拣选策略能够有效提升订单出库效率。

基于启发式回溯算法的平面移动式立体车库RGV调度策略

为了提高立体车库路径规划阶段的兑现率,对有轨引导小车(rail guided vehicle,RGV)运行过程及行程时间进行分析,给出了符合并行调度模式的路径重叠率计算方法,针对立体车库作业特征提出了一种值排序启发式(value ordering heuristics,VOH)回溯算法,构建路径节点滑动时间窗,以单位时间窗内任务请求数作为约束函数,通过评估函数对扩展结点性能进行估值并排序,并利用VOH-预剪枝策略对部分结点进行剪枝,以此提高算法求解速度。在非齐次泊松到达过程下进行仿真,实验结果表明,值排序启发式回溯算法可有效降低RGV并行运行过程中时间、空间的路径重叠率,在该实验规模的立体车库模型中发挥稳定,表现为在RGV平均利用率基本不变的前提下具有更小的平均服务时间,当顾客到达率为40、25、10、5 veh/h时,RGV平均服务时间分别减少18.07%、13.29%、12.46%、4.27%,为提升立体车库运行效率提供参考。

Dice系数前向预测的快速正交正则回溯匹配追踪算法

为了提高压缩感知重构算法的成功率与重构精度,该文提出基于Dice前向预测的正交正则回溯匹配追踪算法(DLARBOMP)。在该算法中,首先从匹配准则与预选阶段原子选取的角度,利用Dice系数代替原子内积计算相关度,保留原始信号信息的特性,以此选择与残差最匹配的原子,提高算法的重构精度。同时,针对信号重构过程回溯算法的时间过长问题,在每次原子迭代过程中,该文利用正则化选择多个原子而非单个原子,实现重构精度与重构时间的平衡。最后,通过稀疏1维信号与2维图像信号重构的实验结果,显示了所提DLARBOMP算法在1维信号重构时兼顾了性能与效率,在2维压缩图像信号重构时提高其峰值信噪比(PSNR),优于正交匹配追踪(OMP)及其最新改进贪婪类算法。

运行时间周期化工业机器人模型迭代寻优NURBS轨迹插补

为满足工业机器人高精度复杂曲线运动的需求,本文提出运行时间周期化工业机器人模型迭代寻优NURBS轨迹插补算法.首先,根据轨迹最大轮廓误差和机器人动力学特性对曲线分段.随后,提出优化回溯算法,使各子曲线段均可用S曲线加减速规划.之后,为保证机器人在进给速度极小值处不超速,将各加减速阶段运行时间调整为插补周期的整数倍,并对子曲线段衔接处速度平滑处理.最后,提出模型迭代寻优曲线插补,大大降低了速度波动率.仿真试验表明,该方法插补轨迹的各项指标均满足要求且最大速度波动率仅为0.000099%.真机试验也验证了该方法可有效减小轨迹误差.

最小支配阈值集问题的降阶回溯算法

图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出上界子算法、下界子算法和降阶子算法,并基于这些子算法提出了一种可以减小问题规模同时得到最优解的降阶回溯算法BAR;最后,通过一个示例分析和若干随机算例测试验证了降阶回溯算法可有效降低问题的求解难度。