共查询到20条相似文献,搜索用时 609 毫秒
1.
2.
在解决旅行商问题(Traveling Salesman Problem, TSP)上,提出了一种新的求解思路即基于K-means聚类思想下的改进型蚁群算法,目的是优化TSP最短路径。先将整体TSP中分布的全部节点利用K-means聚类思想将其分成若干子TSP,再通过对基础蚁群算法(Ant Colony Algorithm, ACA)中信息素更新策略的改进,解决传统蚁群算法在面对大规模TSP问题时有迭代时间长、收敛速度慢和易陷入局部最优解的缺陷。在对每一个子TSP求解最优路径后再将各部分连接,使其融合成为一条完整TSP的最优路径。经验证该算法不仅优化了最短路径降低了误差率,同时大大缩短运算时间,提高了运算效率。 相似文献
3.
4.
基于模拟退火算法的无网格节点生成技术 总被引:1,自引:0,他引:1
为克服目前无网格法布点技术仅适用于特定问题的缺点,在分析节点生成技术数学本质的基础上,提出了一种基于模拟退火算法的无网格节点生成技术.该算法结合k-means方法和模拟退火算法(SA)求解约束条件下的多峰值函数全局最小值,在待求计算域内和边界自动生成无网格计算节点,且节点为计算域对应质心Voronoi结构的质心点.该算法可以普遍用于包括凹域和多连通域等任意形状域的布点计算,尤其适用于给定边界节点位置情况下域内无网格节点的生成问题.将所生成节点用线段连接起来,也可以直接得到有限元网格. 相似文献
5.
提出了一种求解TSP问题的近似算法--嵌套插队算法.这种算法结合了启发式算法和随机化算法以及局
部寻优的思想。实验结果表明对于较小规模的TSP问题,直接用插队算法(QJA)就能以很大的概率获得已知最优
解。对于规模较大的TSP问题,嵌套插队算法(NQJA)能获得质量高于著名的启发式算法的解。另外,用嵌套插队
算法找到的China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对TSP问题而提出的,但其思
想也可以给求解其他NP难解的组合优化问题以启发。 相似文献
6.
在旅行商问题(TSP)的传统模型中,子回路消除约束的数量随着问题规模的增大具有指数增长的特性,极大地限制了TSP的求解效率。基于TSP的松弛问题,本文提出一种有效生成子回路消除约束的方法。该方法通过求解一系列线性整数规划,来实现TSP的精确快速求解。数值结果表明,本方法相比于采用Cplex直接求解,能够更快地找到TSP的最优解。 相似文献
7.
提出了一种求解TSP问题的近似算法一嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的TSP问题,直接用插队算法(QJA)就能以很大的概率获得巳知最优解。对于规模较大的TSP问题.嵌套插队算法(NQJA)能获得质量高于著名的启发式算法的解。另外,用嵌套插队算法找到的Chinal44的最短路径优于目前巳知的最短路径。嵌套插队算法是专门针对TSP问题而提出的,但其思想也可以给求解其他NP难解的组合优化问题以启发。 相似文献
8.
何湘竹 《中南民族大学学报(自然科学版)》2015,(4):89-93
提出了一种改进的基于教与学的优化算法(TLBO)求解旅行商(TSP)问题,阐述了TLBO算法的基本思想和求解步骤,给出了算法流程,针对算法在解决大规模问题时易陷入局部最优的缺陷,引入混沌搜索机制对其进行了改进.着重研究了改进后的TLBO算法求解TSP问题的求解结果和性能分析,通过benchmark实例进行了仿真实验,结果表明:与诸如遗传算法和粒子群优化算法等已有启发式算法相比,改进后的TLBO算法在求解TSP问题时性能更为优越,从而为TSP问题的求解找到了一条新途径. 相似文献
9.
《四川理工学院学报(自然科学版)》2017,(3):6-9
研究了需求可拆分的车辆路径问题(SDVRP)的基本数据模型,分析了相关解的基本特点,提出了一种改进的人工蜂群算法进行求解。首先,在不考虑车辆容量和拆分需求的前提下,求出TSP大路径;然后,对TSP大路径进行切割,在切割的地方对客户点的需求进行拆分;最后,在前述操作基础上形成初始解,采用改进人工蜂群算法进行优化。在人工蜂群阶段,三种蜜蜂在全局和邻域范围内不断优化当前解。通过仿真实验与其它算法对比,验证了提出的算法在有效性和稳定性上,具有良好的效果。 相似文献
10.
张晓玲 《大理学院学报:综合版》2009,8(4)
提出一种基于顶点的候选表进行交配的遗传算法(Candidate Crossover Genetic Algorithm,CCGA)求解旅行商问题(TSP).遗传算法(GAs)是一种广泛使用的全局优化算法,并且已经成功地用于求解TSP.但是传统的遗传算法的交配算子缺乏指导性和启发性,交配算子随机的选择父体基因进行交配,导致GAs求解速度慢、解的精度不高等不足.通过分析TSP问题本身的特征,给出了一个使用已有的邻接边的信息和路径信息生成顶点的候选表,然后基于顶点的候选表进行交配的交配算子,使用该交配算子的遗传算法在求解TSP问题时性能上得到了很大的提高,通过TSP Lib上的测试样例将该CCGA和传统的遗传算法进行比较.比较结果表明CCGA具有更大的优势,它能使算法求解到近似最优解和最优解只存在很小的偏差. 相似文献
11.
在全光网中,信号传输损伤会恶化动态光路连接的阻塞率性能,有必要在研究动态路由与波长分配RWA(routing and wavelength assignment)算法时考虑信号传输损伤的影响.介绍和阐述了全光网中的信号传输损伤及其对动态RWA算法性能的影响;结合已有的信号传输损伤模型提出了一种基于信号损伤限制的动态RWA算法,并对其性能进行了计算机仿真分析.仿真结果表明:该算法能有效地减小信号传输损伤对光网动态连接的阻塞率性能的影响,同时还具有较快的运算速度. 相似文献
12.
针对当前人脸识别算法的运行速度和识别准确率的矛盾,提出一种基于双向主成分法(Bidirectional PCA,BD-PCA)和K近邻法K-NN(K-nearest neighbor)的人脸识别算法。在VC6.0平台下基于ORL人脸库进行实验,首先利用双向PCA算法对训练人脸样本和测试人脸样本进行方向和列方向降维并提取特征脸;然后用K近邻方法对特征脸进行人脸匹配。实验表明,提出的算法在有效降低运算时间的同时,又能取得很高的识别准确率,具有一定的可行性。 相似文献
13.
针对WiMAX系统宏分集切换问题,提出了2种宏分集切换算法——MDHO和MDHO-H。MDHO算法对已有的Z算法进行了改进,选择信号强度最强的m个基站做为分集站。MDHO-H算法在MDHO算法的基础上加入了滞后因子。在相同切换场景下对3种算法进行了仿真比较。结果表明,MDHO算法和MDHO-H算法的切换次数比Z算法的切换次数分别减少了24%和53%。 相似文献
14.
传统的逆变器电压外环、电流内环控制策略无法完全消除静差;在双环控制基础上增加有效值外环的三环控制策略虽然能减少静差,但由于有效值算法较慢,影响了系统的动态性能。为进一步优化逆变器三环控制策略,提出了将快速有效值算法用于逆变器三环控制,并给出了2种快速有效值算法的实现原理和设计方法,通过比较得出了基于迭代法的有效值算法具有低噪声干扰、低谐波干扰等优点。将该算法用于逆变器三闭环控制系统,提高了闭环控制的实时性。通过仿真和实验验证了该方法的高稳定性和优良的动态性能。 相似文献
15.
认知无线电系统能否充分发挥其优势在很大程度上取决于信道估计的准确性和实时性。将基于新型时域内插的初始估计和EM跟踪应用于认知无线电系统,同时引入小波包对初始估计进行消噪处理,提出了一种新型的半盲信道估计方法。理论分析和仿真表明,该方法较好地解决了由于主用户存在造成的导频分布不均匀,保证了天线之间导频符号的相关性,且由于采用EM信道跟踪和小波包去噪进一步节省了频谱资源、提高了估计准确性。该方法可满足认知无线电信道估计实时性和准确性要求,具有较大的实际应用价值。 相似文献
16.
为了克服基于端到端单向时延的拓扑推断算法中需要时钟同步的缺点,根据端到端时延抖动的定义和特点提出了拓扑推断中端到端时延抖动的四元分组列车测量方法和基于端到端时延抖动的拓扑推断算法,其中端到端时延抖动的测量不需要节点间的时钟同步,并且实现简单.分析了基于端到端时延抖动推断网络拓扑的可行性和正确性,通过NS2进行了仿真.仿真结果表明,基于时延抖动推断拓扑结构的效果比基于端到端单向时延推断拓扑结构的效果好. 相似文献
17.
实值阴性选择算法V-detector在产生检测器时不能确保检测器具有较大的覆盖范围,其结果是检测器集合中的检测器数量过多,检测效率较低。为提高检测效率,提出了V-detector优化算法,一方面,通过合理确定检测器的中心点位置及检测半径,扩展了检测器的覆盖范围;另一方面,优化算法采用假设检验的判定方法判断检测器集合对非自体空间的覆盖率。假设检验融合到检测器集合的生成进程中,在确保检测器集合满足覆盖率要求的条件下,减少了检测器集合中的检测器数量。实验结果表明,与原算法相比,优化算法使检测器集合中检测器的数量大幅度下降,检测效率得到提高。 相似文献
18.
为了提高系统性能,从实数格基缩减出发,推广得到了一种通用的复数格基缩减算法,给出了其在V-BLAST系统中的应用。通过与MMSE扩展相结合,分析缩减与扩展的先后顺序,提出了MMSE-Ⅰ和MMSE-Ⅱ两类基于复数格基缩减算法的V-BLAST检测方案。分析和仿真结果表明,检测中采用复数格基缩减算法与实数算法相比,可以大幅降低复杂度而不影响系统性能;基于复数格基缩减的MMSE-Ⅱ逐层干扰抵消检测算法,可以解决格基缩减引起的有效发送符号之间的相关性问题,且性能接近于ML检测。为了进一步降低复杂度,给出了一种性能损失较小的次优排序方案。 相似文献
19.
针对传统的图像恢复方法存在的缺陷和不足,提出了一种基于差分进化算法的图像恢复方法。该方法的思路是,利用差分进化算法简单、通用和鲁棒性强等优点提高求解效率,优化图像恢复效果。通过将差分进化算法应用于图像恢复,并把恢复后的图像与使用遗传算法恢复的图像进行对比分析,实验表明了差分进化算法的稳定性、图像的清晰性明显优于遗传算法,基于差分进化的图像恢复具有良好的性能和显著的效果,因此差分进化算法比遗传算法更适用于图像恢复问题。 相似文献
20.
Petri网的合法变迁引发序列问题(LFS)是其可达性问题的子问题.前人在LFS判定时常因判定算法的指数级时空复杂度或算法难以推广至一般Petri网而受限.因此,基于Petri网T-不变量支集变迁与可达图有向环路上标注变迁的对应关系,综合应用线性代数与可达树分析,原LFS判定被缩减为以基础向量为发生数向量的LFSb判定.通过两棵可达树(分别以原网、初始标识;逆网、目的标识为根)层序轮流构造同时比较当前叶节点层中的标识,若算法终止前有相同标识出现,则LFSb(LFS)判定成功;反之,LFS判定失败.分析表明,算法的时间复杂度为多项式级别的,且适用于一般Petri网的LFS判定. 相似文献