共查询到20条相似文献,搜索用时 203 毫秒
1.
SizeScale:求解旅行商问题(TSP)的新算法 总被引:9,自引:0,他引:9
旅行商(TSP)问题是组合优化中最典型的NP-Hard问题之一,目前关于该问题的启发式算法主要分布为两类:环路构造算法和环路改进算法,对于第1类算法,首次提出了在环路构造中成批加入顶点,同时在构造过程对环路进行局部优化的思想,由上得到了一种新的算法:SizeScale-Construct,它的解质量极大地改进了现有的环路构造算法,对于2类算法,在分析局部最优解与全局最优解之间关系的基础上,提出了另一个采用局部最优解的交集作为初始环路的新算法:SizeScale-Improve,实验结果表明该算法在解的质量和求解速度上都较大地改进了现有最好的环路改进算法;另一方面,理论上对于最坏情况和平均情况时间复杂度的分析表明这两个算法是实用的。 相似文献
2.
针对不同污染程度的水域提出重点监测区域的集中性覆盖监测问题.在重点监测区域的传感器网络部署之前,对于监测水域大面积覆盖监测问题采用一种基于加权因子调整的粒子群优化(PSO)算法,对比了不同粒子群数目对网络覆盖能力的影响.仿真结果表明:PSO算法保证在最大覆盖率的条件下,实现传感器网络节点快速自适应均匀部署,运算速度快且能够避免局部最优;网络覆盖能力先随粒子群数目的增加而增大,当粒子群个数达到20后,网络覆盖能力随之减小;网络实现最大范围均匀部署之后,能较好地保障重点水域的集中性覆盖监测,从而保障真实客观的水质监测数据. 相似文献
3.
随着旅行商问题(TSP)规模的增大,传统蚁群算法的运行时间会增大,算法的解精度也会降低,并且算法很容易陷入局部最优的情况。提出的分层递进算法的思想源于分工合作的产品线组装流程,首先利用改进的密度峰聚类算法确定拐点,从而选举出聚类中心,根据聚类中心确定包含的数据点;其次将初始的TSP问题分割成较小的簇,这些簇称为二类TSP问题;再经自适应信息素更新策略的蚁群算法运算,找出每个簇的最优解,进一步将簇与簇之间相近的节点构成的边断开;然后两簇之间断开的节点重组成全局最优解;最终通过局部优化策略对重组的优化解进一步优化,从而在保证算法解质量的前提下有效地缩短了运行时间。从TSPLIB中选取小规模、大规模基准案例,通过Matlab仿真验证了改进算法具有更好的鲁棒性,特别是在大规模基准案例中显著地减少了算法运行时间。 相似文献
4.
对MANET环境下的多连接查询技术进行了研究,提出了一种利用缓冲的多连接算法.该算法从全局和局部两方面对查询进行了优化,全局优化阶段获得一个能量最优的查询计划,该计划确定出各子查询及其结果放置节点;局部优化阶段为每个子查询确定执行计划.实验证明,提出的方法不仅能显著地减少查询执行的能量消耗,而且能很好地适应MANET网络中节点多跳通信和拓扑动态变化的特点. 相似文献
5.
基于改进的小世界网络的组搜索算法及其应用 总被引:1,自引:0,他引:1
针对合成氨工艺中,合成塔出口氨含量软测量神经网络模型的参数优化问题,提出了一种改进的小世界网络模型,并将其引入到组搜索优化算法中。改进后的小世界网络在计算节点之间相连接的概率时考虑节点间的距离因素,相距较近的节点间比相距较远的节点之间更容易连接。将改进后的小世界网络引入组搜索算法后,种群中的追随者在每次迭代中,根据当前迭代次数及与其它个体间的距离计算自身与其它个体的相连接概率,相连概率随着迭代增加而线性增大,随着个体间距离的增加而指数递减。追随者根据相连概率选择与自身相连接的个体,再用与其相连的个体构建自身的邻域并选取邻域中的最优个体作为局部最优解个体。追随者更新自身位置时不仅参考整个种群中的全局最优个体,还同时参考自身邻域中的局部最优个体。该算法能够提高种群中个体的多样性,具有更好的全局搜索能力和收敛速度。将该算法应用于氨合成塔出口氨含量软测量建模问题中,对神经网络模型的参数进行优化,并与其它3种方法比较。仿真结果表明,基于改进的小世界网络模型的组搜索算法能够获得更好的模型参数,提高软测量模型的精度。 相似文献
6.
7.
为了解决混合无线传感器网络的节点覆盖率低的问题,提出了改进粒子群的混合无线传感器网络节点覆盖迭代优化算法.在该算法中,首先将混合无线传感器网络节点覆盖模型转化为在网络系统中动态的求覆盖率最大值的节点部署位置寻优问题;然后提出利用改进粒子群算法对节点覆盖优化方案进行粒子及其权值映射,并依据粒子粒距聚类度和粒子信息熵对粒子权值进行调整,再依据粒子适应度值对粒子局部最优值和全局最优值进行更新;最后迭代地对粒子的位置和速度进行计算,输出具有最优覆盖率的节点部署方案.仿真结果证明,该算法能够有效的提升网络覆盖率,且算法的收敛速度快. 相似文献
8.
9.
10.
针对车辆路径问题中选取客户节点易陷入局部最优的缺点,引入节约法并结合路径权重和距离启发因子来改进选取 客户节点的决策规则。根据粒子实际运动过程的特点和伊藤算法在迭代过程中逐步收敛的特性,结合算法的波动算子和漂移算子设计了对路径权重的更新规则,提升了算法的收敛速度。通过增大波动系数和提高环境温度来应对伊藤算法迭代过程中出现的搜索停滞、局部最优现象。引入2-opt局部优化算法来优化当前迭代取得的最优解。实验结果表明,改进后的伊藤算法有效地加快了收敛速度,提高了搜索全局最优解的能力。 相似文献
11.
水质传感器优化布置是指在城镇配水管网中最优位置布置水质传感器对污染物进行检测,从而达到监测预警的目的,其本质是一类大规模离散组合优化问题。首先从数学上对该问题进行分析,论证了其具有NP-Complete特性;然后针对该问题计算开销大等特点,提出了基于Spark云计算模型的分布式遗传算法;最后以一个典型的复杂配水管网为对象进行实验,仿真结果表明,所提出的算法不仅具有搜索速度快、精度高等优点,而且还具有较好的线性加速比。 相似文献
12.
Babu G.P. Murty N.M. Keerthi S.S. 《IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics》2000,30(1):10-24
In this paper, a stochastic connectionist approach is proposed for solving function optimization problems with real-valued parameters. With the assumption of increased processing capability of a node in the connectionist network, we show how a broader class of problems can be solved. As the proposed approach is a stochastic search technique, it avoids getting stuck in local optima. Robustness of the approach is demonstrated on several multi-modal functions with different numbers of variables. Optimization of a well-known partitional clustering criterion, the squared-error criterion (SEC), is formulated as a function optimization problem and is solved using the proposed approach. This approach is used to cluster selected data sets and the results obtained are compared with that of the K-means algorithm and a simulated annealing (SA) approach. The amenability of the connectionist approach to parallelization enables effective use of parallel hardware. 相似文献
13.
14.
为了解决空气污染源反演的盲目性和低效率问题,本文提出了一种基于改进型蚁群算法(modified-ant colony optimization, M-ACO)的空气污染源反演方法.利用点源高斯扩散模型建立污染源反演模型,采取蚁群算法(ant colony optimization, ACO)来求解.针对蚁群算法中存在的缺点,引入遗传算法的选择交叉思想,从而丰富种群的多样性来避免陷入局部极值;同时设计奖惩因子机制,对信息素更新规则进行改进来使算法更快地收敛,进而归纳为M-ACO算法.通过对比实验,证明了M-ACO算法相比于传统ACO算法来说,能够使得污染源的反演结果更准确和高效,为空气污染源反演的实际应用提供了有效的理论支撑. 相似文献
15.
16.
A new connectionist network topology called the regression network is proposed. The structural and underlying mathematical features of the regression network are investigated. Emphasis is placed on the intricacies of the optimization process for the regression network and some measures to alleviate these difficulties of optimization are proposed and investigated. The ability of the regression network algorithm to perform either nonparametric or parametric optimization, as well as a combination of both, is also highlighted. It is further shown how the regression network can be used to model systems which are poorly understood on the basis of sparse data. A semi-empirical regression network model is developed for a metallurgical processing operation (a hydrocyclone classifier) by building mechanistic knowledge into the connectionist structure of the regression network model. Poorly understood aspects of the process are provided for by use of nonparametric regions within the structure of the semi-empirical connectionist model. The performance of the regression network model is compared to the corresponding generalization performance results obtained by some other nonparametric regression techniques. 相似文献
17.
淮河流域是我国水环境治理的重点之一.由于淮河流域水情复杂,所以容易发生水污染事件.本文立足于突发水污染情况,研究如何调动闸坝和水库的生态用水并在最短时间内初步治理水污染问题.闸坝调度问题是组合优化问题,水资源调度效率为目标函数,约束条件包括蓄水、水中物质浓度和闸坝距离等.本文采用人工鱼群调度算法(AFSA),并加以约束条件,满足治水需求.人工鱼群算法有快速的跟踪变化和跳出局部极值的优点,能避免算法初期早熟的问题.实验结果表明,基于人工鱼群算法的生态水调度方法,在处理这类问题,不仅精确有效,并且能在较少的迭代次数内找到满意解,具有很高的可行性,参考性. 相似文献
18.
19.
20.
Zhu Ping Wei Hui 《计算机工程与设计》1997,(5)
符号主义和连结主义是人工智能研究的两个主要流派。近年来,将两者结合起来的研究引起了广泛的兴趣。此文提出一种有语义的连结主义推理模型-分层前馈模型FNRM,及其世界抽象。描述了它的推理过程和学习过程。最后讨论进一步研究的问题。 相似文献