基于k-ary消减的快速最大公约数算法

最大公约数(GCD)算法中,对于输入B和C,利用Sorenson的右移k-ary消减思想提出一个算法用于寻找整数x和y,使得x和y满足Bx-Cy在二进制表示下低比特位部分为0,即Bx-Cy=0(mod 2e),其中e是常数正整数。利用该算法能够右移较多比特并大规模降低循环次数。再结合模算法,提出了快速GCD算法,其输入规模为n比特时最差复杂度仍然是O(n2),但最好的情况下复杂度能达到O(n log2n log log n)。实验数据表明,对于20万以上比特规模的输入,快速GCD算法比Binary GCD算法速度快;对100万比特规模的输入,快速GCD算法速度是Binary GCD算法的两倍。

最大公约数线性表达式系数的非递归算法

本文中我们给出了计算两个整数最大公约数及其组合系数的非递归算法及其在C语言环境中相应的程序.与其它的程序相比,该程序节约了运行的时间开销与空间开销,运行效率得到了提高.

基于C/C++语言最大公约数算法的研究

设计出了基于C/C++语言最大公约数算法程序,通过分析算法,提出了程序设计语言教学的几点建议。

两种最大公约数算法的量化分析

为了验证Euclid算法和Stein算法在高精度条件下的真实运行效率,以随机生成的多组高精度正整数,并分别按同位、异位、完全随机、斐波那契数列相邻项4种情况对这两种最大公约数算法的平均执行效率进行比较。实验发现:四种情况下的平均执行耗时Euclid算法均低于Stein算法;随着参数精度越高,Euclid算法的平均耗时越优于Stein算法;在随机高精度参数条件下,Stein算法比Euclid算法平均执行时间多约26.24%。

最大公约数的多种算法

本文总结了四大类计算最大公约数的方法。与其他类似的文章不同，本文给出了最大公约数的格式严格的数学定义，对两种主要算法（欧几里德算法和Steh算法）的正确性给出了形式化的数学证明：同时，对每种算法作者还以标准C语言给出了可移植的实现。

浅谈如何设计算法求最大公约数

算法作为高中数学新增内容，受到老师和同学们的普遍关注．本文就教材《算法案例》一节中的一个案例“写出求两个正整数a，b（a〉b）的最大公约数的一个算法”，谈一谈求最大公约数的多种算法设计．笔者希望通过本文能使同学们体会到算法思想已经渗透到人们生活与生产的方方面面．

求最大公约数的两种算法案例

求最大公约数有两种经典算法,即辗转相除法与更相减损术。一、辗转相除法辗转相除法最早出现于公元300年的古希腊作家欧几里得的《几何原本》中,也被称为欧几里得算法,其主要作用是求两个正整数的最大公约数。

基于改进二进制粒子群算法优化DBN的轴承故障诊断

针对滚动轴承故障振动信号非平稳性的特点,对二进制粒子群优化算法(binary particles swarm optimization,BPSO)和深度信念网络(deep belief network,DBN)进行研究,提出一种基于局部均值分解(local mean decomposition,LMD)和IBPSO-DBN的轴承故障诊断方法。提出用加权惯性权重改进BPSO迭代过程中的固定权重,再用改进BPSO优化DBN的隐含层神经元个数和学习率。该方法先对信号进行LMD,提取出各PF分量的散布熵和时域指标,并构建特征矩阵,然后把特征矩阵输入改进BPSO-DBN模型中训练,实现滚动轴承故障诊断和分类。采用试验轴承数据做验证并与其他诊断方法对比,结果表明,基于LMD和BPSO-DBN的滚动轴承故障诊断方法具有较好的故障识别率。

一种多种群二进制算术优化算法及其应用

针对算术优化算法(AOA)无法对离散二进制型问题进行优化的局限,提出一种使用sigmoid函数变体实现的离散二进制算术优化算法(BAOA_S),解决了原始算法无法用于离散二进制变量优化的问题。进一步提出一种基于突变策略实现的多种群二进制算术优化算法(multi-swarm binary arithmetic optimization algorithms,MS-BAOA)。该算法将原始种群划分为多个子种群,子种群间通过通信策略进行交流,并使用突变策略进一步增强种群多样性,克服了BAOA_S无法跳出局部最优解的缺陷。基于CEC2013基准函数将MS-BAOA与BAOA_S、二进制粒子群算法(binary particle swarm optimization algorithm,BPSO)、二进制灰狼优化算法(binary gray wolf optimizer,BGWO)、二进制鱼群迁徙算法(binary fish migration optimization algorithm,BFMO)以及二进制均衡优化器(binary equilibrium optimizer,BiEO)进行了对比,实验结果显示MS-BAOA总体上优于对比算法。将MS-BAOA应用于配电网故障区段定位中,实验结果显示该算法能够对配电网单点故障以及多点故障实现快速精准定位,进一步验证了该算法的实用性。

高光谱结合离散二进制粒子群算法对久保桃可溶性固形物含量的检测

可溶性固形物(SSC)是评价久保桃内部品质的重要指标。传统的SSC检测有损、费时、费力;快速、无损检测久保桃的SSC含量对于其品质分级有着重要意义。离散二进制粒子群算法(BPSO)是在标准粒子群算法(PSO)的基础上,更新速度公式得到的,具有精度高,收敛快的特点,多用于离散空间的优化问题。基于高光谱技术结合BPSO算法及BPSO的组合特征波长选择算法对久保桃的SSC含量预测进行研究。首先采集198个久保桃样本的高光谱信息,获取久保桃900~1700nm范围内的光谱信息,计算感兴趣区域的平均光谱作为有效光谱数据,同时测量久保桃的SSC值。采用K-S(Kennard-Stone)算法将样本划分为校正集(147个)和预测集(51个)。使用BPSO特征波长选择算法对久保桃的原始光谱数据进行特征波长提取,并与竞争性自适应重加权算法(CARS)、连续投影法(SPA)、无信息变量选择法(UVE)等特征波长选择算法比较。同时为了避免单一算法建模中的不稳定问题,提出了基于BPSO的一次组合(BPS0+CARS、BPSO+SPA、BPSO+UVE)和二次组合[(BPSO+CARS)-SPA]、[(BPSO+SPA)-SPA]、[(BPSO+UVE)-SPA]特征波长提取方法。基于上述10种特征波长提取方法分别建立支持向量机(LS-SVM)模型和遗传算法(GA)优化的支持向量机模型(GA-SVM)模型。结果表明,基于BPSO算法提取特征波长建立的模型预测性能均高于其他单一特征波长方法,建立的两种模型预测集决定系数R_(p)^(2)均达到0.97以上;基于BPSO的组合算法中,二次组合(BPSO+SPA)-SPA算法建立的LS-SVM在特征波长数量较少的情况下对久保桃SSC含量预测性能最高,校正集和预测集决定系数R_(c)^(2)为0.982,R_(p)^(2)为0.955,均方根误差RMSEC为0.108,RMSEP为0.139。该模型预测性能略低于BPSO算法,但其仅用了22个特征波长进行建模,极大地简化了模型。说明(BPSO+SPA)-SPA是一种有效的特征波长提取方法,为水果SSC含量的无损检测提供了新的检测方法。

基于混合二进制灰狼算法的入侵检测特征选择方法

为了减少数据集的冗余特征对入侵检测分类器训练用时和检测精度的影响,对二进制灰狼算法的变异概率问题进行分析,重构逼近向量表达式,改善算法的种群变异机制,加快特征降维,减少分类器训练用时;融入粒子群算法的迭代决策形式,增强算法寻优能力;采用混合二进制灰狼算法进行包裹式特征选择,使得数据集特征结构适合于决策树分类器。经NSL-KDD数据集测试,该方法对DoS、Probe攻击流量的检测精度较好,适合用于数据平衡分布的数据集。

基于二进制正弦余弦算法的频谱分配方法

为解决频谱资源短缺问题,提出一种基于二进制正弦余弦算法(Binary Sine Cosine Algorithm,BSCA)的认知无线电频谱分配方法。在算法中构造非线性振幅调节因子,有助于动态调整迭代期间的搜索步长,提高算法全局搜索能力和收敛精度;利用二进制代码转换公式将正弦余弦算法推广至离散域;将改进后的二进制正弦余弦算法进行频谱分配的仿真实验,并与粒子群优化算法、遗传算法、量子遗传算法作对比,结果表明BSCA具有同时取得较高的网络效益与公平度的优势。

基于改进二进制蛇优化算法的配电网故障定位

分布式电源(distributed generation,DG)大规模接入给配电系统带来更多不确定性、随机性,系统运行方式更复杂,传统故障定位方法难以适应新型电力系统构建。提出了一种基于改进二进制蛇优化算法(improved binary snake optimization,IBSO)的新型故障区段定位方法。利用SPM混沌映射生成高质量的随机数序列,以提高算法种群中个体的随机性,并引入了遗传算法的动态变异策略,根据不同的搜索状态和进化阶段来调整变异率和变异方式,提高算法的灵活性和准确性。通过仿真证明,该方法适用于在含有分布式电源的配电网中定位单一和多重故障区段,相比蛇优化算法、传统二进制粒子群算法以及遗传算法在收敛性、快速性和准确性方面更优。

二进制登山队优化算法及其在特征选择中的应用

特征选择的主要目的是缩减和精炼数据的特征集,使得生成的特征子集可以进一步提高模型的学习精度。针对特征选择这一特定问题,提出了一种二进制登山队优化算法BMTBO(Binary Mountaineering Team-Based Optimization)。该算法属于二进制版本的群智能优化算法,并采用倒“S”形和“V”形数值空间转换函数,实现了在特征选择时,不仅可以降低特征维数,而且可以降低模型学习的误差率。为验证BMTBO算法的实际效果,在15个公共测试数据集上进行实验。实验结果显示,与现有方法相比,BMTBO算法的平均分类准确率最多可提升1百分点,证明所提出的算法在提高模型学习精度方面的可行性与有效性。

基于新颖二进制人工蜂群算法求解带权集合覆盖问题

带权集合覆盖问题(WSCP)是一个著名的NP-hard问题。为了利用人工蜂群算法(ABC)高效求解带权集合覆盖问题,提出了一个新颖二进制ABC(记作nBABC)。在nBABC中,首先提出了随机学习和继承性相结合的全局进化算子,以提高算法的全局勘探能力。其次,基于动态调整策略提出了自适应随机取反算子,以维持勘探与开发的平衡。在借鉴近似算法的思想提出处理WSCP不可行解的修复算法WSCP-GRA和优化算法WSCP-GOA的基础上,利用nBABC给出了求解WSCP的一个新方法。为了验证nBABC求解WSCP的高效性,利用它求解OR-Library中45个WSCP实例,与多个算法的比较表明:nBABC能够求得所有实例的最优值,比已有求解WSCP的算法更具竞争力。

求解0-1背包问题的二进制狼群算法

狼群算法(wolf pack algorithm,WPA)源于狼群在捕食及其猎物分配中所体现的群体智能,已被成功应用于复杂函数求解。在此基础上,通过定义运动算子,对人工狼位置、步长和智能行为重新进行二进制编码设计,提出了一种解决离散空间组合优化问题的二进制狼群算法(binary wolf pack algorithm,BWPA)。该算法保留了狼群算法基于职责分工的协作式搜索特性,选取离散空间的经典问题——0-1背包问题进行仿真实验,具体通过10组经典的背包问题算例和BWPA算法与经典的二进制粒子群算法、贪婪遗传算法、量子遗传算法在求解3组高维背包问题时的对比计算,例证了算法具有相对更好的稳定性和全局寻优能力。

基于混合二进制粒子群-遗传算法的测试优化选择研究

测试优化选择是一个组合优化问题。通过对测试选择的目标和约束条件进行深入分析,建立了其数学模型,并提出了一种混合粒子群-遗传算法用于求解满足测试性指标要求的最小完备测试集。该算法将遗传算法中的遗传算子引入到二进制粒子群算法中,既避免陷入局部最优和早熟收敛现象,又提高了搜索效率。大量实验证明,对于测试优化选择问题,混合粒子群-遗传算法能够快速有效的获得全局最优解。

改进二进制粒子群优化算法在配电网络重构中的应用

配电网络重构是一个非常复杂的大规模组合优化问题。网络重构中,能否得到有效解,即保证辐射状网络,是一个很关键的问题。对电网拓扑进行简化,配合破圈法更新粒子,得到100%的有效解,大大提高了计算速度。提出一种应用于配电网络重构的改进二进制粒子群优化算法,并结合禁忌搜索算法,使PSO算法跳出局部最优化陷阱,改善了算法的搜索效果,加快了寻优速度。最后对IEEE 69节点系统进行计算,并与相关文献结果进行对比,表明本文改进算法具有快速、高效的全局寻优能力。

改进的RFID二进制搜索防碰撞算法

标签冲突是射频识别技术(RFID)不可避免的问题,在ABS算法和动态调整二进制搜索算法的基础上提出了一种改进的二进制搜索算法,该算法简化了阅读器发送的指令和冲突检测过程,并采用动态方式传输EPC数据。仿真结果表明,相比于目前的二进制搜索算法,这种算法能极大地减少阅读器与标签之间的通信量,有效地提高标签的识别速度,具有良好的应用前景。