基于模糊结构元的最小生成树问题的求解算法

针对梯形模糊数,定义了一种梯形模糊结构元.研究了边权值为梯形模糊数的模糊权值网络,建立了其最小生成树问题的数学模型,并利用梯形模糊结构元加权排序思想和Kruskal算法,设计了一种该问题的求解算法,给出了算法的复杂度分析和应用实例.文中的模型和算法对于边权值为其他类型模糊数的模糊权值网络同样有效.     

求解度约束最小生成树的一种改进算法

度约束最小生成树问题是网络设计和优化中的一个NP-hard问题。提出一种求解网络G关于指定节点的最大度约束最小生成树的改进算法。算法在保证指定节点最大度的前提下,通过选取剩余边中权最小的边加入当前网络,得到网络G关于指定节点的最大度最小生成树,同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较,表明新算法的有效性和通用性。     

基于最小代价和生成树的算法研究

最小生成树问题是一类经典的组合优化问题,已有许多快速有效的算法。但是在实际中更多存在这样的网络,除边有权值外,结点也有权值,并且结点的权值有多种情况,这就产生了基于代价和最小的生成树问题。根据结点权值的取值情况,对几种最小代价和生成树问题进行分类和求解,得到了一些有价值的性质和算法,有一定的实际应用背景。     

带模糊权值的最短路问题及启发式算法

研究网络链路权值是三角型模糊数时的最短路问题,建立模糊线性整数优化模型。通过引入目标函数的正、负理想点和隶属度概念,将模糊优化问题转化为确定系数的单目标优化问题,并给出求解算法。该算法通过调整反映决策者意图的目标函数权系数,得到决策者的满意解。对14个节点的实例网络进行仿真,经过6步就能得到令决策者满意的解,表明了模型和算法的有效性。     

基于“最小差值法”的网络模型耗费代价研究

最小生成树算法是数据结构中,求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变,有时还需兼顾其它的目标,一棵最小生成树不足以解决问题,因此找出所有的最小生成树是很有必要的,在此提出一种新的寻找所有最小生成树的算法--最小差值法。无向连通图网络通过去掉连枝生成最小生成树,一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中,用连枝的权与其它树枝的权分别作差,求最小差值。由最小差值是否为零,判断原有的最小生成树能否通过换进换出边,生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中,选择符合实时情况的最小生成树方案,该方案即为网络耗费代价的最优解。     

基于“最小差值法”的网络模型耗费代价研究

最小生成树算法是数据结构中,求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变,有时还需兼顾其它的目标,一棵最小生成树不足以解决问题,因此找出所有的最小生成树是很有必要的,在此提出一种新的寻找所有最小生成树的算法——最小差值法。无向连通图网络通过去掉连枝生成最小生成树,一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中,用连枝的权与其它树枝的权分别作差,求最小差值。由最小差值是否为零,判断原有的最小生成树能否通过换进换出边,生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中,选择符合实时情况的最小生成树方案,该方案即为网络耗费代价的最优解。     

求解度约束最小生成树问题的新算法

针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。     

物流网络中节点带权的Steiner最小树的参数算法

通过优化物流的运输网络,可以有效地降低物流成本。集中配送的物流网络优化问题可以转换成求解节点带权的Steiner最小树问题,这是一个NP-hard问题。运用参数理论,提出一种新的启发式解决算法P-NSMT。算法的思想是：首先尽可能只利用终端节点构造一棵连通的最小生成树,然后逐步向树中添加能减少生成树总权值的Steiner节点,最终生成一棵节点总数不超过参数k的Steiner最小树。实验表明,与同类型其他算法相比,P-NSMT算法具有更好的准确性和时间效率,特别适应于网络规模大、终端配送节点数目较少的物流网络。     

模糊联想记忆网络的增强学习算法

针对 Kosko提出的最大最小模糊联想记忆网络存在的问题 ,通过对这种网络连接权学习规则的改进 ,给出了另一种权重学习规则 ,即把 Kosko的前馈模糊联想记忆模型发展成为模糊双向联想记忆模型 ,并由此给出了模糊快速增强学习算法 ,该算法能存储任意给定的多值训练模式对集 .其中对于存储二值模式对集 ,由于其连接权值取值 0或 1,因而该算法易于硬件电路和光学实现 .实验结果表明 ,模糊快速增强学习算法是行之有效的 .     

基于最小生成树的加权中值滤波算法

根据图像纹理分布特点,提出一种基于最小生成树的加权中值滤波算法。依据最小生成树计算像素点的相关度,对像素点进行初次分类。对初次分类中不能确定性质的像素点,采用模糊理论进行二次分类。根据像素点的分类结果,保持像素点的原有灰度值或采用不同的滤波方法进行滤波处理。仿真实验结果表明,在去除噪声和图像细节保持方面,该算法优于其他中值滤波算法。     

Distributed hierarchical search for balanced energy consumption routing spanning trees in wireless sensor networks

We provide a new heuristic method approach to search for degree-balanced and small weight routing spanning trees in a network. The method is a modification of Kruskal’s minimum spanning tree search algorithm and is based on a distributed search by hierarchical clusters. It provides spanning trees with a lower maximum weighted degree, a bigger diameter, and can be used for balanced energy consumption routing in wireless sensor networks (WSN’s). The method can be naturally implemented in parallel or as a simple locally distributed algorithm. Simulations for a realistic case scenario WSN are done based on the transmission energy matrix. The simulation results show that the proposed approach can extend the functional lifetime of a WSN in terms of sensor transmission energy by 3–4 times. We also show that the results can be further improved by using a preliminary clustering of the input network.     

Rough‐fuzzy quadratic minimum spanning tree problem

A quadratic minimum spanning tree problem determines a minimum spanning tree of a network whose edges are associated with linear and quadratic weights. Linear weights represent the edge costs whereas the quadratic weights are the interaction costs between a pair of edges of the graph. In this study, a bi‐objective rough‐fuzzy quadratic minimum spanning tree problem has been proposed for a connected graph, where the linear and the quadratic weights are represented as rough‐fuzzy variables. The proposed model is formulated by using rough‐fuzzy chance‐constrained programming technique. Subsequently, three related theorems are also proposed for the crisp transformation of the proposed model. The crisp equivalent models are solved with a classical multi‐objective solution technique, the epsilon‐constraint method and two multi‐objective evolutionary algorithms: (a) nondominated sorting genetic algorithm II (NSGA‐II) and (b) multi‐objective cross‐generational elitist selection, heterogeneous recombination, and cataclysmic mutation (MOCHC) algorithm. A numerical example is provided to illustrate the proposed model when solved with different methodologies. A sensitivity analysis of the example is also performed at different confidence levels. The performance of NSGA‐II and MOCHC are analysed on five randomly generated instances of the proposed model. Finally, a numerical illustration of an application of the proposed model is also presented in this study.     

基于多源信息聚类和IRC-RBM的混合推荐算法

针对协同过滤存在的数据稀疏性问题，提出了融合多源信息聚类和IRC-RBM的混合推荐算法。首先以用户信任度和项目时间权重作为聚类依据，利用最小生成树的K-means聚类算法对用户进行聚类分析，生成K个相似用户集合，在聚类分析的基础上进行评分预测；最后通过线性加权的方式，把聚类后评分矩阵和IRC-RBM模型生成的评分矩阵进行加权融合，用Top-N进行推荐。实验结果表明，相比较传统的推荐算法，该混合算法在准确率上有了显著的提升。     

Low latency and energy efficient routing tree for wireless sensor networks with multiple mobile sinks

We propose the minimum Wiener index spanning tree (MWST) as a routing topology that is suitable for sensor networks with multiple mobile base nodes. However, it was proved that finding a spanning tree with the minimum Wiener index from a weighted graph is NP-hard. To address this problem and analyze the effectiveness of the MWST as the routing tree on sensor networks with multiple mobile base nodes, we designed two algorithms: a branch and bound algorithm for small-scale wireless sensor networks and a simulated annealing algorithm for large-scale wireless sensor networks. The simulation results show that MWST outperforms the minimum spanning tree (MST), one of the representative spanning trees used in many routing protocols for sensor networks, in terms of energy efficiency and packet delay.     

Degree constrained minimum spanning tree problem: a learning automata approach

Degree-constrained minimum spanning tree problem is an NP-hard bicriteria combinatorial optimization problem seeking for the minimum weight spanning tree subject to an additional degree constraint on graph vertices. Due to the NP-hardness of the problem, heuristics are more promising approaches to find a near optimal solution in a reasonable time. This paper proposes a decentralized learning automata-based heuristic called LACT for approximating the DCMST problem. LACT is an iterative algorithm, and at each iteration a degree-constrained spanning tree is randomly constructed. Each vertex selects one of its incident edges and rewards it if its weight is not greater than the minimum weight seen so far and penalizes it otherwise. Therefore, the vertices learn how to locally connect them to the degree-constrained spanning tree through the minimum weight edge subject to the degree constraint. Based on the martingale theorem, the convergence of the proposed algorithm to the optimal solution is proved. Several simulation experiments are performed to examine the performance of the proposed algorithm on well-known Euclidean and non-Euclidean hard-to-solve problem instances. The obtained results are compared with those of best-known algorithms in terms of the solution quality and running time. From the results, it is observed that the proposed algorithm significantly outperforms the existing method.