一种求解共享单车再平衡问题的遗传算法

共享单车再平衡问题(BRP)是单一商品旅行商问题(1-PDTSP)的扩展,是一类NP难问题。针对已有算法求解速度慢,不利于实现实时调度优化的缺点,提出一种求解BRP的非代际遗传算法。基于个体搜索机制保留优异个体,设计线路交叉算子和k点破坏修复变异算子,引入破坏修复机制,当算法收敛变慢时自动生成新个体进入种群以避免陷入局部最优解。应用BRP标准算例测试表明:在小规模算例上该算法均能找到最优解,平均CPU消耗为3.8 s;在中等规模与大规模算例上,该算法找到9个算例的最优解,并且其运算速度相较于分支定界算法和线路破坏与修复启发式算法提升77%以上。     

需求点位置随机的分批配送VRP优化

将需求点位置随机的分批配送车辆路径问题视为分区路径问题进行求解。文章建立多目标随机规划模型,并设计改进的局部迭代搜索算法求解。在调整的Solomon算例测试集及调整的Gehring和Homberger算例测试集上进行测试,结果表明本文设计的算法能有效解决此类问题,同时由于分批配送的引入,32个测试算例中50%以上的算例得到更优的解。同时,使用具有实际意义的系数在算例集上进行求解,最优解平均比构造算法提高9.75%和14%的最优解质量。     

Lagrange双支撑向量回归机

提出一种快速的支撑向量回归算法。首先将支撑向量回归的带有两组约束的二次规划问题转化为两个小的分别带有一组约束的二次规划问题,而每一个小的二次规划问题又采用一种快速迭代算法求解,该迭代算法能从任何初始点快速收敛,避免了二次优化问题求解,因此能显著提高训练速度。在多个标准数据集上的实验表明,该算法比传统支撑向量机快很多,同时具有良好的泛化性能。     

融合遗传和蚁群算法并行求解最短公共超串

依据各级缓存容量,将CPU主存中种群个体和蚂蚁个体数据划分存储到一级、二级和三级缓存中,以减少并行计算过程中数据在各级存储之间的传输开销,在CPU与GPU之间采取异步传送和不完全传送数据、GPU多个内核函数异步执行多个流的方法,设置GPU block线程数量为16的倍数、GPU共享存储器划分大小为32倍的bank,使用GPU常量存储器存储交叉概率、变异概率等需频繁访问的只读参数,将输入串矩阵和重叠部分长度矩阵只读大数据结构绑定到GPU纹理存储器,设计实现了一种多核CPU和GPU协同求解最短公共超串问题的计算、存储和通信高效的并行算法。求解多种规模的最短公共超串问题的实验结果表明,多核CPU与GPU协同并行算法比串行算法快70倍以上。     

考虑边位置信息的求解ETSP问题改进贪婪算法

分析了贪婪算法(Greedy algorithm,GRA)求解欧几里德旅行商问题(Euclidean Traveling SalesmanProblem,ETSP)的求解质量和求解耗时的特点,发现边位置信息是影响GRA的求解质量和求解耗时的主要因素,在Michael模型基础上提出了一种考虑添加边所在位置信息的改进贪婪算法(Improved Greedy algorithm,IMGRA),并阐述了IMGRA的设计思想和相应的构造方法.分别采用IMGRA和GRA求解了90个算例,结果表明:固定参数下的IMGRA平均求解质量较GRA提高55%,求解耗时降低20%.为此,对IMGRA比GRA求解质量更高和求解耗时更短的原因进行了分析.     

公共自行车交通系统调度算法

针对公共自行车交通系统的静态车辆调度问题,以运输成本最少为目标建立公共自行车交通系统调度模型,提出了一种将模拟退火算法融合到遗传算法中的混合启发式算法来求解该模型,增强算法的全局搜索能力和效率.通过实例结果表明,优化后运输车辆行驶路程比优化前减少了50％,说明遗传模拟退火算法具有良好的鲁棒性和收敛性,适合解决车辆的优化...     

一种求解带时间窗车辆路径问题的混合差分进化算法

对带时间窗的车辆路径问题进行研究,建立以最小化车辆数量和行驶路程为目标的多目标数学模型,提出一种结合改进差分进化算法和变邻域下降搜索的基于Pareto支配的混合差分进化算法。首先重新定义了个体的生成方式。其次,结合双种群策略和变邻域下降搜索技术来平衡算法的全局探索能力和局部开发能力,并在搜索过程中用随机个体替代种群中的重复个体,维持种群的多样性。然后引入Pareto支配的概念来评价个体的优劣性,并采用擂台法则构造非支配解集。最后对18个不同规模的Solomon算例的求解结果表明,算法在行驶路程和车辆数量上的求解质量比人工蜂群算法分别平均提高了2.04%和14.95%,且与已知最优解相比,在车辆数量的求解质量上平均提高了14.53%,验证了所提算法的有效性。     

基于MapReduce的动态自适应蚁群算法设计与实现

针对基本蚁群算法( ACO)在处理中等规模旅行商问题( TSP)上消耗时间过长的问题,提出一种基于MapReduce的动态自适应蚁群算法( MDACO)。该算法在信息素更新策略方面动态地调整信息素挥发系数,使蚁群能够自适应地寻找较优的路径结果,而且采用MapReduce计算模型将蚁群算法中循环迭代部分并行化,最终将其部署在Hadoop云计算平台上运行。当TSP节点数为150及以上时,该算法比基本蚁群算法的运行时间平均减少43.2%,路径寻优结果也得到进一步改善。仿真结果表明,该算法在保证问题求解质量以及提高求解速度方面具有优越性。     

基于混合蚁群算法的冷链电动汽车车辆路径问题

用电动汽车进行冷链物流配送符合绿色物流的发展趋势。针对电动汽车冷链配送需消耗更多能源以维持低温环境,而电动汽车续驶里程短、充电时间长,致使运营成本高的现象,思考了电动汽车配送中的冷链车辆路径问题（REVRP）。考虑电动汽车能耗特点和社会充电站的充电需求,构建了以总配送成本最小为优化目标的线性规划模型,而目标函数由固定成本和可变成本构成,其中可变成本包含运输成本和制冷成本。模型考虑容量约束和电量约束,并设计混合蚁群（HACO）算法对其进行求解,其中重点设计了适合社会充电站的转移规则以及4种局部优化算子。在改进Solomon基准算例的基础上,形成了小规模和大规模两个算例集,并通过实验比较了蚁群（ACO）算法和局部优化算子的性能。实验结果表明,在小规模算例集中,传统ACO算法与CPLEX求解器均能找到精确解,而ACO算法在运算时间方面可节省99.6%;而在大规模算例集中,与ACO算法相比,结合4种局部优化算子的HACO算法的平均优化效率提升了4.45%。所提算法能够在有限时间内得出电动汽车REVRP的可行解。     

带时间窗的同时取送货车辆路径问题建模及模因求解算法

为解决逆向物流背景下的带时间窗的同时取送货车辆路径问题（VRPSPDTW）,根据实际情况建立了相应的车辆路径问题模型,并采用模因算法进行求解。在模型的求解过程中使用引导弹射搜索（GES）生成初始种群,在种群进化的过程中采用边界组合交叉（EAX）产生子代,并采用多种邻域结构对子代进行修复、教育,以提高解的质量和算法的搜索效率。通过在Wang和Chen测试数据集上与遗传算法（GA）、并行模拟退火（p-SA）算法、离散布谷鸟（DCS）算法进行比较,实验结果显示：在小规模算例进行求解时,所提算法全部取得了当前最优解;对标准规模算例进行求解时,所提算法使70%的算例更新或获取了当前最优解,获得的最优求解算例结果与当前最优解相比有超过5%的提升,充分验证了所提算法求解VRPSPDTW的良好性能。     

Branch-and-Bound-Based Local Search Heuristics for Train Timetabling on Single-Track Railway Network

The modified formulation and two branch-and-bound-based local search heuristic algorithms for train timetabling in single-track railway network in the planning application are proposed. The original local search heuristic is modified such that when a neighbor of a currently tested resolved conflict for improvement is evaluated, the depth-first search branch-and-bound algorithm is employed with two branching rules: least-lower-bound and least-delay-time. The detailed implementation of the proposed heuristic algorithms are described, including the neighborhood definitions of overtaking and crossing conflicts, the procedure to detect overtaking and crossing conflicts, and a recursive procedure for the depth-first search branch-and-bound algorithm. The proposed heuristic algorithms, the original heuristic, the equivalent manual solution method and the exact solution method are compared using a toy problem and four problems (26-train, 50-train, 76-train and 108-train) in the Thailand Southern line railway network, which consisted of 266 single-track segments, 15 double-track segments, 282 stations/sidings, and total distance of 1577 km. The proposed heuristic algorithm with the least-lower-bound branching rule outperforms the other heuristics in terms of the solution quality with up to 2.827 % improvement over the equivalent manual solution method and less than 8 % optimality gap. The proposed heuristic algorithms require longer time to terminate than the original heuristic. The proposed heuristic algorithm with the least-lower-bound branching rule converges faster than that with the least-delay-time branching rule in all test problems. Based on the empirical results, the proposed heuristic algorithms are solvable in polynomial time. Furthermore, the proposed heuristic algorithm with the least-lower-bound branching rule is enhanced by embedding a uniform sampling strategy, and it is found that the total CPU time can be saved by about 50 % with marginally worse solution quality.     

嵌入式软件编译时能耗演化优化算法

编译选项的选择优化为降低嵌入式软件能耗提供了一种可行且有效的解决方案.GA-FP算法将频繁模式挖掘应用到演化过程中并已取得了较好的结果.然而,GA-FP还存在事务表规模较大、频繁选项模式的启发信息不全和时效性不好以及单点变异效率不高的缺点,潜在地影响了解质量和收敛速度.针对这些问题,文中提出一种嵌入式软件编译时能耗演化优化算法GA-MFPM.GA-MFPM借助逐代替换参考点和事务表的机制以降低事务表大小;在此基础上提出可获取更多启发式信息的频繁编译选项挖掘算法,并采用逐代挖掘的策略以保持频繁选项模式的时效性;进一步设计最大频繁模式匹配算法进行多点变异,以提高优化质量和收敛速度.通过与GA-FP在5个不同领域的8个典型案例下实验对比的结果表明:本文GA-MFPM获取了较GA-FP更低的软件能耗(平均降低2.4%,最高降低16.1%)和更快的收敛速度(平均加快57.6%,最高加快97.5%).     

核电站数字化反应堆保护系统中央处理器负荷率分析与测试

核电站对数字化反应堆保护系统的一书央处理器的负荷率有严格要求。本文首先对核电站数字化反应堆保护系统中央处理器的负荷率进行了理论分析,得出了负荷率计算公式;然后设计了相应的负荷率测试方法0j测试装置,完成了实际的测试工作;对测试所得实验数据进行处理,得出测试结果,结果表明数字化反应堆保护系统的中央处理器负衍率符合技术嘤求,且主控CPU的负荷率比备用CPU负荷率要高。     

Fermi架构下的时域高斯滤波并行算法

为提高图形图像处理中高斯滤波算法模块的计算速度,将高斯滤波与Fermi平台相结合,设计了一种高斯滤波时域的并行算法。数据测试结果显示,与基于CPU的实现相比,采用Fermi架构的GPU处理不仅可以得到误差精度小于0.0001的计算结果,而且可以取得较大的加速效果。在数据规模为512×112×128和滤波窗口大小为11的情况下能够达到约210倍的加速效果。     

一种求解二元约束满足问题自适应粒子群算法

提出了一种求解二元约束满足问题的自适应粒子群算法（SAPSO）,其中每个粒子具有两种状态,定义了一个反应粒子活跃程度的变量以决定粒子所属的状态。为了平衡粒子不同进化阶段的开发和探测能力,在SAPSO中引入了随着每个粒子的进化状态和粒子群的进化状态动态改变的惯性权重。利用自适应的选取方式代替随机选择的盲目搜索方式,使群体在解空间搜索时,能够自适应地去探索新的区域,选择有希望找到更优解的地方搜索。使用随机约束满足问题的实验表明,改进后的算法比原算法（PS-CSP）能以更快的速度收敛到全局解。算法的效率大约提高两倍,平均迭代次数大约为原来的一半。     

鲁棒模型预测控制在变风量空调系统中的应用

在变风量空调系统中二次泵压差控制可以有效地减少空调能耗,为克服二次泵模型的不确定性,提高二次泵变频调速控制的响应速度和精度,采用基于线性矩阵不等式的鲁棒预测控制策略。算法分为离线和在线两个部分,离线时首先用传统算法得出目标函数上界,以此为已知量重新优化得到一系列较大的渐近稳定的不变椭圆集。在线时,每个采样周期用三个相邻的椭圆集优化来对状态变量进行精确定位,并给出控制量。给出在线优化的理论证明。通过和传统算法的仿真比较,表明该算法的有效性。二次泵压差控制的实验表明该算法可得到较大的可行域,系统响应快,控制效果好。     

LTE无线系统终端省电机制研究

针对长期演进(LTE)系统恒功率休眠模式中存在的低业务、高功耗等缺点,提出一种变功率休眠算法。该算法可根据终端业务要求,动态改变休眠周期,以提高终端的待机时间,并以该算法为基础,探讨休眠状态终端的平均响应时间和平均功耗等问题。仿真实验表明,与恒功率休眠算法相比,该变功率休眠算法可以减少功耗6%~12%。     

基于趋化校正的哈里斯鹰优化算法

针对哈里斯鹰优化（HHO）算法收敛速度慢、易陷入局部最优的缺点,提出了一种改进HHO算法,即基于趋化校正（CC）的哈里斯鹰优化（CC-HHO）算法。首先,通过计算最优解下降率和变化权重来识别收敛曲线的状态;其次,将细菌觅食优化（BFO）算法的CC机制引入局部搜索阶段来提高寻优的精确性;再次,将生物在运动时的能量消耗规律融入逃逸能量因子和跳跃距离的更新过程中,从而更好地平衡算法的探索与开发;然后,对最优解和次优解的不同组合进行精英选择来拓展算法全局搜索的广泛性;最后,当搜索陷入局部最优时,通过对逃逸能量施加扰动来实现强制跳出。通过10个基准函数对改进算法的性能进行测试,结果显示CC-HHO算法对单峰函数的搜索精度比引力搜索算法（GSA）、粒子群优化（PSO）算法、鲸优化算法（WOA）以及另外4种改进的HHO算法提升超过10个数量级;对多峰函数也有超过1个数量级的优势;在保证搜索稳定性平均提升超过10%的前提下,所提算法的收敛速度明显优于上述几种优化算法,收敛趋势更加明显。实验结果表明,CC-HHO算法有效地提高了原算法的搜索效率和鲁棒性。     

基于GPU的H.264并行解码算法

针对并行处理H.264标准视频流解码问题,提出基于CPU/GPU的协同运算算法。以统一设备计算架构(CUDA)语言作为GPU编程模型,实现DCT逆变换与帧内预测在GPU中的加速运算。在保持较高计算精度的前提下,结合CUDA混合编程,提高系统的计算性能。利用NIVIDIA提供的CUDA语言,在解码过程中使DCT逆变换和帧内预测在GPU上并行实现,将并行算法与CPU单机实现进行比较,并用不同数量的视频流验证并行解码算法的加速效果。实验结果表明,该算法可大幅提高视频流的编解码效率,比CPU单机的平均计算加速比提高10倍。     

调节缓存器宽度和布线宽度相结合的优化算法

介绍了将调节缓存器宽度和布线宽度相结合的一种减小连线延迟的优化算法—B＆W算法。算法是以Elmore迟延模型为基础的。该算法在GWSA1的算法基础上考虑调节缓存器宽度的作用,因而比单独的调节布线宽度的算法在运算速度上要快的多。例如它在有8000个缓存器和连线段的情况下,CPU时间仅为0．215秒。B＆W算法同时是一种叠代搜索算法,它能够达到最优解。而且算法可以扩展应用到互连树的情况下,这使它的应用更加广泛。