共查询到16条相似文献,搜索用时 78 毫秒
1.
基于加权绝对值距离Steiner最优树的选址问题 总被引:1,自引:0,他引:1
提出基于加权绝对值距离Steiner最优树思想的选址模型,给出了该模型的蚂蚁算法实现策略.在此基础上,分析了电子商务环境下企业配送中心选址问题,并用算例验证了该选址方案的可行性. 相似文献
2.
求解最小Steiner树的蚁群优化算法及其收敛性 总被引:11,自引:0,他引:11
最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用.蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法.本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架.把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解. 相似文献
3.
本文针对不确定语言信息的群决策问题,提出了一种解决多粒度不确定二元语义语言信息集结与决策的新方法。首先,根据各专家不确定语言短语决策信息,通过相关转化规则,量化为与其对应的二元语义区间数,并将其端点映射到二维坐标系中。其次,运用植物模拟生长算法(PGSA)求出各区间数端点坐标的加权Steiner点(专家群体最优结集点,即群体共识点)。其后,再由最优集结点,给出专家最优集结判断矩阵。从而,可以对决策方案的进行排序,以便给出最优群体决策方案。为了验证此方法的合理性和有效性,本文选择了两个其他学者的研究算例,对其进行了平行的算例研究。最终得到了与其相同的研究结果。 相似文献
4.
5.
6.
针对目前山西省废旧手机产生量逐年增加的实际情况,对山西省废旧手机回收处理中心的数量及选址进行研究.建立以运输费用及固定运营成本之和最小为目标函数的数学模型,引入山西省相关数据,通过改进模拟植物生长算法进行模型分析求解,并与未改进算法进行比较发现改进算法在解的质量及效率上均有显著的优越性.结果表明在山西省内建造5个废旧手机回收处理中心所需总费用最小,结果最优.这为山西省政府相关部门进行回收产业区域规划提供一些决策依据. 相似文献
7.
8.
9.
网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点.所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数).假定每一次广播的执行时间为一单位.网络G的广播过程是广播的时间安排,使所有结点均获得消息.最优广播问题是求总时间最少的广播过程.在G是树网络情形,文献中已给出时间界为O(n2)的算法.本文给出线性时间的简捷算法. 相似文献
10.
研究一个有趣的组合优化问题——二阶数乘问题.问题描述如下:给定n≥2个正整数a_1,a_2,…,a_n,设π为{1,2,…,n}的一个置换,表示该问题的一个解,试图找到一个置换π以至∑_(i=1)~n a_(π_i)a_(π_(i+1))最小,在这里π_(n+1)=π_1.给出了一个算法复杂度为O(n log n)的最优算法. 相似文献
11.
Steiner最小树问题是组合优化中经典的NP难题,在许多实际问题中有着广泛的应用,而三维欧氏Steiner最小树问题是对二维欧氏Steiner最小树问题的推广。由于三维欧氏Steiner树问题的求解非常困难,至今为止的相关成果较为少见。本文针对该问题,利用Delaunay四面体网格剖分技术,提出了一种混合型智能求解方法,不仅可以尽量避免拓扑结构陷入局部最优,且对较大规模的问题求解亦有良好的效果。算法在Matlab环境下编程实现,经实例测试,获得了满意的效果。 相似文献
12.
The Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the
plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics
are desired. We present two such heuristics, both of which utilize an efficient method for computing a locally optimal tree
with a given topology. The first systematically inserts Steiner points between edges of the minimal spanning tree meeting
at angles less than 120 degrees, performing a local optimization at the end. The second begins by finding the Steiner tree
for three of the fixed points. Then, at each iteration, it introduces a new fixed point to the tree, connecting it to each
possible edge by inserting a Steiner point, and minimizes over all connections, performing a local optimization for each.
We present a variety of test cases that demonstrate the strengths and weaknesses of both algorithms.
This revised version was published online in July 2006 with corrections to the Cover Date. 相似文献
13.
Joonmo Kim Mihaela Cardei Ionut Cardei Xiaohua Jia 《Journal of Global Optimization》2002,24(4):437-448
In this paper, we present the design of a Polynomial Time Approximation Scheme (PTAS) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. Previous research has focused on geometric analyses and different approximation algorithms have been designed. We propose a PTAS that provides a polynomial time, near-optimal solution with performance ratio 1+. The GOSST problem has some important applications. In network design, a fundamental issue for the physical construction of a network structure is the interconnection of many communication sites with the best choice of the connecting lines and the best allocation of the transmission capacities over these lines. Good solutions should provide paths with enough communication capacities between any two sites, with the least network construction costs. Also, the GOSST problem has applications in transportation, for road constructions and some potential uses in CAD in terms of interconnecting the elements on a plane to provide enough flux between any two elements. 相似文献
14.
将仿真技术和遗传算法相结合,根据生产车间的资源情况、优化目标等建立了生产调度仿真模型,然后对仿真输出结果进行统计,针对统计结果应用遗传算法对调度决策进行优化.仿真优化结果说明了该集成优化方法是有效性的. 相似文献
15.
The Hop-constrained Steiner Tree Problem is often used to model applications of multicast routing with QoS requirements. This paper introduces a distributed heuristic for the problem based on the application of dual ascent over a graph transformation introduced by Gouveia et al. The proposed algorithm is shown to yield significantly better solutions than the previously known algorithms. 相似文献