基于回溯搜索优化算法求解带时间窗和同时送取货的车辆路径问题

为了求解带时间窗和同时送取货的车辆路径问题(VRPSDPTW),首次设计了回溯搜索优化算法(BSA)求解该问题。使用随机选择法、最近邻居法、最远者优先法、剩余承载力和径向附加费节约算法产生初始种群。然后在BSA算法框架下,在交叉和变异操作中使用6种路径间搜索算子和4种路径内搜索算子更新当前局部最优解。选取文献[1]测试数据集中的6个算例,将BSA算法的计算结果与文献中已知的遗传算法、并行模拟退火算法和离散布谷鸟算法的结果进行比较,对算法性能进行测试。BSA算法获得了2个已知国际最好解,并更新了1个已知国际最好解。Friedman检验显示,在α=0.1%的显著性水平下,这4种算法不存在显著性差异。因此,所提出的BSA算法是求解VRPSDPTW的有效算法。

具有广泛学习策略的回溯搜索优化算法

回溯搜索优化算法(backtracking search optimization algorithm,BSA)是一种新型的进化算法。同其他进化算法类似,该算法仍存在收敛速度较慢的缺点。针对这一问题,在详细分析该算法原理的基础上,提出了具有广泛学习策略的改进算法。为了充分利用种群搜索到的较优位置,该策略首先利用提出的最优学习进化方程,通过与引入的随机进化方程之间随机选择来提高算法的收敛速度和搜索精度;另一方面,该策略利用提出的最优学习搜索方程,通过控制种群的搜索方向,促使种群尽快收敛至全局最优解。最后对20个复杂测试函数进行了仿真实验,并与其他3种目前流行的算法进行了比较,统计结果和Wilcoxon符号秩检验结果均表明,所提出的改进算法在收敛速度以及搜索精度方面具有明显优势。

基于差分进化的回溯搜索优化算法研究与改进

针对回溯搜索优化算法收敛速度慢和易早熟的缺点,提出了一种改进算法。首先,利用麦克斯韦分布产生变异尺度系数,并在此基础上提出了一种新的变异算子。新变异算子有效地加快了收敛速度。同时,在变异策略中添加了一种选择机制以增加全局搜索能力,避免出现早熟收敛。通过与差分进化的变异策略对比和经典测试函数的测试,实验结果表明改进算法不仅具有较快的收敛速度,而且具有良好的全局搜索能力。

带高效变异尺度系数和贪婪交叉策略的回溯搜索优化算法

针对回溯搜索优化算法(BSA)收敛速度慢的缺点,提出基于麦克斯韦-玻尔兹曼分布的变异尺度系数和带贪婪性的交叉策略,来提高算法收敛速度。利用麦克斯韦-玻尔兹曼分布产生变异尺度系数,能有效提高搜索效率,提高收敛速度;在交换维数较少的交叉策略中使用向优秀个体群学习过的变异种群进行交叉,在充分保证种群多样性的前提下为交叉策略添加了一定贪婪性,成功克服了以往算法添加贪婪性时易陷入局部最优的缺点。对15个标准测试函数进行仿真实验,结果显示,改进算法收敛速度较快,收敛精度较高,即使在高维多峰函数中,相同迭代次数后改进算法的搜索结果比原BSA平均高出近14个数量级,收敛精度均达到10-10以上。

具有组合变异策略的回溯搜索优化算法

针对回溯搜索优化算法收敛速度慢和易陷入局部最优的缺陷,提出了一种基于组合变异策略的改进回溯搜索优化算法。为了提高历史种群的多样性并扩大算法的搜索空间,在算法迭代过程中采用柯西种群生成策略,利用柯西分布尺度系数生成历史种群;引入基于混沌映射和伽玛分布的组合变异策略,在一定概率下对较差个体进行变异生成质量较好的个体;对新种群中越界个体采用越界处理策略,确保算法在预定的搜索空间内搜索。选取了11个标准测试函数,在低维和高维状态下进行数值仿真,并与3种表现良好的算法进行比较,结果表明该改进算法在收敛速度和收敛精度上有很大优势。

基于改进回溯搜索优化算法的应急资源调度

以连续性消耗应急系统为背景,建立以时间成本和运输成本最小化为目标的多资源多供应点调度模型。针对该模型的特点,对一种具有强全局搜索性的新智能算法——回溯搜索优化算法进行改进,设计变异操作中的变异尺度系数和交叉操作中的交叉概率策略,提高算法的收敛速度和求解精度。运用改进回溯搜索算法进行模型求解,仿真实例表明,改进回溯搜索优化算法在解决应急资源调度问题时拥有良好的性能,全局收敛性与求解精度均优于比较的回溯搜索优化算法、差分进化算法和粒子群算法,能够有效且合理地进行应急资源调度。

基于回溯搜索优化算法的运动想象脑机接口频带选择

在基于运动想象的脑机接口（BCI）中,特征提取是影响整个系统性能的一个关键部分.共空域模式（CSP）是一种有效的特征提取算法,它能很好地提取与事件相关去同步/同步（ERD/ERS）生理特征相关的节律信息,因而在BCI系统中得到广泛应用.然而,CSP算法的分类性能极大地依赖于EEG信号的滤波频带.一般情况下,大都采用8～ 30 Hz的带通滤波器滤波,因为这个宽带包含了产生ERD/ERS想象的mu（8 ～ 12 Hz）和beta（18 ～ 26 Hz）节律.为了更加精准的定位最佳频带,将8 ～ 30 Hz的宽带滤波细分为大小不等的子带滤波,利用回溯搜索优化算法（BSA）与CSP相结合来选择最优频带,并以分类错误率作为BSA的适应度值（即频带选择标准）.使用该算法对5个受试者的实验数据进行了交叉验证分类实验.实验结果表明,最优频带的平均分类正确率比宽带（8 ～30 Hz）可高出7.91％.

一种高效自学习性回溯搜索优化算法

针对回溯搜索优化算法收敛速度慢的问题,文中在理论分析的基础上,分别对变异算子和交叉算子进行了改进。设计了双种群引导形式的变异算子,并引入一种基于麦克斯韦-玻尔兹曼分布变异尺度系数,有效地增加了变异方程的搜索效率,并设计了一种带有自学习性的交叉策略,使得回溯搜索优化算法的收敛速度和全局搜索性能均得到了一定的提高,通过数值实验,说明了改进的有效性。

回溯搜索优化算法辅助的多阈值图像分割

阈值法是一种简单且有效的图像分割技术。然而阈值求解的计算量随阈值的增加而呈指数级别增长,这给多阈值图像分割带来巨大挑战。为了克服计算量过大问题,视多阈值分割模型为优化问题,分别将Otsu法和Kapur法作为目标函数,采用回溯搜索优化算法求解目标函数,实现多阈值图像分割。将提出的多阈值分割算法应用于自然图像分割,并与其他算法比较,实验结果说明基于回溯搜索优化算法的多阈值图像分割技术是可行的,而且具有较好的分割效果。

求解随机型双边装配线平衡问题的混合回溯搜索优化算法

针对现实生产中普遍存在的操作时间为随机的双边装配线平衡问题,提出一种混合回溯搜索优化算法。该算法将变邻域搜索算法的局部搜索能力融入到回溯搜索优化算法的全局搜索中,从而实现广度搜索和深度搜索的平衡。运用基于随机键的编码将用于求解连续问题的回溯搜索优化算法应用于离散组合优化问题,同时提出一种基于均衡双边负载的边选择策略和减少工位空闲时间的任务选择策略的解码方法,并将该方法同另外4种解码方法进行对比,以验证其优越性。标杆算例测试表明,所提出的算法具有可行性和有效性。

数值积分的回溯搜索优化算法

针对数值积分问题,提出了基于回溯搜索优化算法(Backtracking Search Optimization Algorithm,BSA)不等距节点分割的数值积分方法。该方法将不等距节点的定位看作是一个优化问题,用回溯搜索优化算法寻找最优分割节点,然后在分割而成的每个小区间上应用辛普森公式计算函数的数值积分。与同类算法的对比实验表明,该方法在收敛速度和积分精度上都表现出较强的竞争力。

回溯搜索优化算法研究进展

回溯搜索优化算法(Backtracking Search Optimization Algorithm,BSA)是一种新兴、高效的启发式算法,在短短4年间内已经受到了学术界和工程界的广泛关注。针对BSA的改进及其应用研究进行了系统的综述。首先,从初始化种群、繁殖算子、控制参数和嵌入局部搜索机制等方面分类阐述了算法的改进研究;然后,从算法的基础应用和工程应用研究等方面分类介绍了算法的应用研究进展;最后,根据算法的自身优缺点和当前研究情况,展望了该算法值得进一步研究的可能方向。

基于元胞自动机的动态回溯搜索优化算法

针对传统回溯搜索优化算法存在收敛速度慢、搜索精度不高等问题,提出了一种基于元胞自动机和正交实验设计的改进算法。首先将正交实验设计方法引入算法的交叉算子中,得出具有代表性的优质子代个体;然后在元胞自动机邻居模型的基础上,对个体展开领域内多父代正交交叉操作,提高算法的开采能力和搜索效率;最后对参与交叉的种群引入动态优秀个体比例权重进行选择更新,并采用新的动态变异方程,平衡算法的全局搜索和局部搜索能力。通过对12个标准测试函数进行仿真实验,并与其他六种表现良好的算法进行比较,结果表明,改进的算法在收敛速度以及寻优精度方面都具有明显优势。

基于回溯搜索优化算法的BP神经网络年径流预测

针对BP神经网络易陷入局部极值及初始权阈值参数难以确定的不足,利用一种新型进化算法——回溯搜索优化算法(BSA)优化BP神经网络初始权值和阈值,提出BSA-BP年径流预测模型,并构建PSO-BP、GA-BP及BP模型作对比模型,以云南省清水江站年径流预测为例进行实例研究。结果表明:BSA-BP模型预测精度优于PSO-BP、GA-BP及BP模型。利用BSA算法优化BP神经网络的初始权值和阈值,可有效提高BP神经网络的预测精度和泛化能力。

基于回溯搜索优化算法的图像分割

阈值法是一种简单且有效的图像分割技术。但是随着阈值数目的增加,求解阈值的计算量增大并且实时性降低,这给多阈值图像分割带来了很大的困难。为了克服这一困难,把多阈值分割看作一个优化问题。将最大类间方差法当作要优化的函数,用回溯搜索优化算法求解要优化的函数,从而实现多阈值图像分割。将提出的多阈值算法应用于基准测试图像上,并与传统阈值分割法比较。实验结果表明:回溯搜索优化算法很好的解决了最大类间方差算法求解多阈值分割实时性差的问题,并验证了该算法应用在图像分割上是可行的。

基于回溯搜索优化的卷积混合语音盲分离

针对独立矢量分析(IVA)算法初始分离矩阵取值对分离性能影响较大的局限性,提出了基于回溯搜索优化的卷积混合语音盲分离算法。采用频域各频率点IVA分离信号的复数峭度和作为目标函数,利用回溯搜索优化算法(BSA)对初始分离矩阵进行优化调整,更好地实现了语音信号的盲分离。在分离过程中,采用复Givens旋转变换原理将对分离矩阵的求解转化为对旋转角度的求解,有效减少了BSA的参数编码维数,降低了优化求解难度。针对语音信号的卷积混合分离实验表明,该算法具有良好的分离效果,其分离性能较之基本IVA算法显著提升。

回溯搜索优化改进矩阵填充的高效位置指纹库构建

针对基于信号强度指示(RSSI)的位置指纹定位过程中用于其离线位置指纹库构建的全采法采集工作量较大、位置指纹库构建效率较低、而插值法通常精度有限等问题,提出一种基于回溯搜索优化算法改进奇异值阈值(SVT)矩阵填充(MC)算法的离线位置指纹库高效构建方法。首先,利用定位区域内采集到的部分参考点的位置指纹数据建立低秩矩阵填充模型;然后通过基于奇异值阈值的低秩矩阵填充算法来求解该模型,进而快速准确重构出完整的位置指纹数据库;同时,针对传统矩阵填充算法最优解模糊及平滑性欠佳的问题,引入回溯搜索优化算法,以核范数最小建立适应度函数,对矩阵填充算法的寻优过程进行改进,进一步提高了求解精度。实验结果表明,利用所提方法构建的位置指纹库与实际采集的位置指纹库之间的平均误差仅为2.705 4 d B,平均定位误差仅相差0.086 3 m,但却节约了近50%的离线采集工作量。上述结果表明所提算法用于离线位置指纹库构建可以在保证精度的基础上,有效降低离线采集阶段的工作量,显著提高位置指纹库构建效率,在一定程度上提高位置指纹定位方法的实用性。

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

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

引导小生境回溯优化算法

回溯搜索优化算法(BSA)是近年提出的一种新型优化算法,针对其收敛速度较慢、易陷于局部最优的缺点,提出了一种基于最优个体引导和小生境技术相结合的改进BSA算法。本方法首先在BSA的变异操作中引入向最优个体学习的策略,以提高算法的收敛速度;其次,设计一种新的小生境排挤技术,根据每个个体到其他个体距离的平均最小值确定小生境半径,排除部分相似性较高的个体;结合群体当前的最差信息,设计一种新的变异方法产生一定数量的新个体补充到新的种群中,维持群体数量的恒定并增强群体多样性。改进的BSA算法充分考虑了算法的收敛速度和群体的多样性,较大地提高了传统BSA算法的性能。对10个典型函数进行仿真测试,并与其他算法结果进行对比,实验结果表明,改进算法在收敛速度与精度方面具有较好的效果。

基于回溯搜索算法的导联选择脑机接口研究

在脑机接口(BCI)中,传统的共空域模式(CSP)算法在提取特征信号与事件相关去同步/同步(ERD/ERS)的信息上得到了很好的效果。但是CSP算法受限于电极导联数、EEG信号的时间段和频带等因素,如电极导联数的增加,CSP算法容易过拟合,数据记录容易混乱,使得运算变得复杂,增加运算时间,降低数据分类正确率。所以,CSP算法存在局限性。使用回溯搜索优化算法(BSA)能够为CSP算法自动挑选出一组导联数组子集,并且以分类错误率作为BSA算法的目标函数进行实验。实验采用两类实验数据(第三、四届国际BCI竞赛数据集)进行交叉验证分类实验。实验结果表明,两类数据的导联数目大幅度减少,分类正确率有所提高。