绝对值距离Steiner最小树问题的二进制粒子群算法

绝对值距离Steiner最小树问题是在铺设网络线缆等领域应用广泛的一个NP难的经典组合优化问题。针对此问题,提出基于最小生成树问题的二进制粒子群算法。该算法首先对网络节点进行编码,计算适应度函数值,并使用二进制粒子群算法求解Steiner点。数据实验结果表明,该算法具有实用性。     

k-割宽临界树的一些构造方法(k≥3)

起源于超大规模集成电路设计和网络通讯的图的割宽（cutwidth）问题,就是把一个含有n个顶点的图G的全部顶点分别安装在一条直线的不同的整数点上,使得跨越各顶点的边数的最大值（即稠密度）达到最小.文章得到了κ–割宽临界树的一些构造方法（κ≥3）.     

4种VLSI标准单元初始布局生成算法及其比较

由于超大规模集成电路（VLSI）标准单元布局问题的高度复杂性,选择适当的初始布局生成算法成为能否在合理的运行时间内获得高质量布局结果的关键因素之一.首先介绍了VLSI标准单元布局问题和优化目标的数学模型.在此数学模型的基础上,给出了4种标准单元初始布局生成算法基本思想及其详细的步骤.对这4种初始布局算法在标准测试例子上的实验结果进行比较,分析它们作为启发式算法初始种群的有效性.     

柱状网格的有向边搜索数上界问题

图的路宽在超大规模集成电路（VLSI）设计中有相当广泛的应用,其中与之相关联的是图的点搜索数及边搜索数问题.本文给出了有向柱状网格的有向边搜索数的上界.     

VLSI/ASIC进入亚微米深亚微米后出现的问题及解决的办法

这些年超大规模集成电路得到了飞速的发展,与此同时,随着器件特征尺寸的减小,尤其是进入深亚微米后出现了一系列新的问题。本文主要阐述了超大规模集成电路进入深亚微米后在设计方法和工艺上出现的问题,以及解决的方法。     

模拟退火算法在结构化布线中的应用

针对在综合布线工程中水平子系统的布线设计难以达到最优化的缺陷,提出了使用模拟退火算法来计算结构化布线方案,使得总体布线方案基本达到最优化。后续实验证明该算法在实际运用中是有效的,较传统布线方法能优化10％以上。     

Prim算法在建筑照明布线中的应用

在建筑照明布线设计中,每个回路的接线都有一个最优的走线方案,即所用的线路之和最短.在图论中,属于最小生成树的问题,可以用Prim算法解决.利用Access数据库进行图的顶点和边的存储、计算,可以简化计算步骤、减少计算时间和算法的复杂度.     

蚁群算法用于VLSI布线的优劣性分析

研究在VLSI布线中采用蚁群算法的优劣性.先介绍用蚁群算法实现阶梯叉树走线,再通过Matlab编程对蚁群算法和迷宫算法分别实现曼哈顿走线进行比较,结果表明,蚁群算法在VLSI布线中的适用性不受布线结构的限制,而且在得出最优解方面比迷宫算法具有优势,只是受计算速度的限制.一般来说,只要能够给出布线的具体要求,蚁群算法都可以合理地应用于VLSI布线中.     

基于改进FP-Growth算法的基因-疾病关系自动提取的应用研究

传统的医学文献检索算法FP-Growth算法存在效率低下、内存溢出等问题,据此提出了一个改进的FP-Growth算法.首先将数据集平均分块,以并行的方式构建FP-Tree树,以减少内存负担,再以粒子群算法优化FP-Growth的FP-Tree树迭代过程,并优化并发过程.经验证,改进后的算法能提高内存的使用率与算法的运行效率.     

阴阳对优化算法在旅行商问题中的推广与应用

YYPO算法是一个求解连续型优化问题的算法,TSP问题是一个经典的离散型优化问题。利用YYPO算法中保持开发点和探索点之间相互平衡的思想,并结合YYA算法中的交互算子,提出了一种求解TSP问题的新方法——离散型阴阳对优化算法(DYYPO)。选取TSPLIB中的10个节点数在300以下的算例测试了DYYPO算法的性能,测试结果表明,在求解TSP问题时,DYYPO算法在最优值、平均值和用时等方面具有一定的优势。     

一个改进的多播路由算法

Multicasting is a communication service that allows an application to efficiently transmit copies of data packets to a set of destination nodes. The problem of finding a minimum cost multicast tree can be formulated as a minimum Steiner tree problem in networks, which is NP-completeness. MPH (minimum path cost heuristic) algorithm is a famous solution to this problem. In this paper,we present a novel solution TPMPH (two phase minimum path cost heuristic) to improve the MPH by generating the nodes and the edges of multicast tree separately. The cost of multicast tree generated by the proposed algorithm with the same time as MPH is no more than that of MPH in the worst case. Extensive simulation results show that TPMPH can effectively improve the performance on MPH, and performs better in large-scale networks and wireless networks.     

ZigBee无线传感器网络树状路由协议研究

介绍了基于IEEE802.15.4和ZigBee标准的无线传感器网络协议,给出了ZigBee网络的地址分配方法,然后描述了用于ZigBee网络的路由协议：树状路由和网状路由,在此基础上详细分析了树状路由协议,包括网络层帧格式、路由算法.最后建立了一个簇树网对树状路由协议进行测试,证明树状路由的可靠传输,为基于ZigBee簇树网的无线传感器网络的开发应用提供有价值的参考.     

多配送中心车辆路径问题的两阶段算法

对多配送中心车辆路径问题进行描述,并建立该问题的数学模型,设计了求解多配送中心车辆路径问题的两阶段算法。第一阶段把多配送中心车辆路径问题转化成单配送中心车辆路径问题,提出基于边界客户分配法的转化策略;第二阶段对单配送中心车辆路径问题进行求解,采用禁忌搜索算法进行优化求解,最后表明算法的有效性和可行性。     

波分复用光网络设计中的RWA问题

文章介绍目前波分复用光网络设计中的RWA问题,根据网络结构的复杂度和节点个数的多少,从静态波长路由分配法和动态波长路由分配法两种方式,探讨解决RWA问题.在静态波长路由分配法中主要针对网络中不具有波长转换和各节点的业务需求关系,将预先分配好的波长路由关系存入网络中的各节点,以解决静态RWA问题,而在动态波长路由分配法中主要针对网络中具有波长转换这一特点,根据图论中的相关理论以求得网络中波长数和路由的关系,从而解决动态RWA问题.     

4-正则图的纵横扩张优化

针对4-正则图的平面嵌入的纵横扩张的特殊性，某些4-正则图类的最小折数纵横扩张已经有了线性算法．本文通过基纵横扩张，提供了从一个4-正则图扩充为另一个4-正则图的方式。使得从原图的最小折数基纵横扩张自然导出扩充图的最小折数基纵横扩张．     

基于自由树的中心的MAODV改进算法

MAODV路由协议是应用于移动Ad Hoc网络的一个组播路由协议,协议中的组长选取具有较大的随机性。本文分析了协议中组长的位置选取的相关特征,并在此基础上提出了基于自由树的中心的MAODV改进,改进算法避免了MAODV路由协议中组长处于组播共享树叶子结点的位置,减少了数据分组的传输次数,降低了网络传输的延迟。     

Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem

INTRODUCTION The vehicle routing problem (VRP), which was first introduced by Dantzig and Ramser (1959), is a well-known combinatorial optimization problem in the field of service operations management and logis- tics. The capacitated vehicle routing problem (CVRP) is an NP-hard problem for simultaneously determining the routes for several vehicles from a central depot to a set of customers, and then return to the depot without exceeding the capacity constraints of each vehicle. In pr…     

多约束QoS路由算法综述

保证服务质量的QoS路由（Quality of Service Routing）是网络中解决QoS问题的一项关键技术。QoS路由的主要目标是为接入的业务选择满足服务质量要求的传输路径,同时保证整个网络资源的有效利用。度量参数选择问题、寻路问题和路由信息不准确问题是QoS路由中的几个主要研究内容。多约束QoS路由算法通常是NPC问题,本文先对QoS路由中的问题进行分娄,再对当前研究的一些多约束QoS路由算法进行了归纳与分析。这些算法对于在Internet中实现QoS有着重要的指导意义。     

互联网络RCP(n)的组播路由算法

互联网络RCP(Ringed Crossed cube Petersen)拓扑结构被提出后并没有给出组播算法.本文利用RCP(n)网络的正则性、良好的可扩展性,以及比Qn,HP(n),RHP(n)网络直径更短和构造开销更小这些特性,按照构造组播树的方法,给出了RCP(n)网络的组播路由算法,并对该算法作了性能分析.     

逆向需求模糊的多车辆集散货物路线问题

研究了一类新的车辆路线问题（VRP）——整合逆向物流的多车辆路线问题（MVRPRL）．该问题的特点是客户可以同时取货和发货,而且客户发货量是在路线安排前是不确定的．首先用三角模糊数表示客户发货量,建立了基于模糊置信度理论的多目标模型;然后设计了基于模拟的改进禁忌算法来求解该模型：用模拟的方法计算路线失败值,在路线搜索中采用路线内部改善和路线间改善两类邻域操作,而且采用了重起策略．计算结果表明该方法优于传统的扫描算法,整合逆向物流的运输费用比正逆向分别运输之和减少了43％．