求解满瓶颈Steiner树

首先对Steiner树,瓶颈Steiner树研究现状加以介绍,指出满瓶颈Steiner树就是在已知图中找一颗树S,使给定的点集在S中的点都为叶子,且最大的边权值最小,然后给出满瓶颈Steiner树的定义,利用分解,转化,组合的思想,给出求解满瓶颈Steiner树问题的一个多项式算法,证明算法正确性,说明该算法的时间复杂性,最后给出相应的数值例子,说明算法正确性.     

离散萤火虫算法在车载网的应用

车载自组织网(Vehicular ad hoc network,VANET)是移动自组织网络之一,具有节点变动迅速、拓扑结构灵活、通信能力要求较高的特点。为提高车载自组织网络的可靠性,实现数据的安全共享和快速交互,将离散萤火虫(DFA)算法应用求解车载网络中具有服务质量约束的多播路由问题。根据VANET的路由特点,将该问题转化为延迟成本最小化约束优化问题,并将车载网络路径时延转化为萤火虫的荧光素值,然后将该算法用4个实例进行测试,并与Dijkstra最短路径算法、粒子群优化算法进行比较。研究结果表明:离散萤火虫算法性能更佳,可有效解决VANET中Steiner minimum tree(SMT)问题,成功取得最优路径。该算法在一定程度上稳定了网络拓扑结构,能够实时更新节点信息。     

一类网络系统中的容量扩张问题

考虑一种网络系统中的容量扩张问题：给定网络N（V,E,C^-）,如何对容量向量C^-进行扩张,在假设的每条过的扩张费用（包括固定费用与成本费用）的条件下,使得网络中最大容量树的容量尽可能提高,同时总的扩张费用不超过给定的预算D。讨论了此类问题的特性,并给出了解决问题的一个强多项式算法。     

社交网络中求最小正影响支配集的改进算法

网络中求解最小正影响支配集的问题已经被证明是NP难问题,且已有性能较好的贪心求解算法．通过分析现有的贪心近似算法（Wang-Greedy）和贪心启发式算法(Raei-Greedy),融合其贪心策略,提出了1个改进的贪心近似算法(Hybrid-Greedy)．理论分析表明,Hybrid-Greedy仍保持Wang-Greedy的近似比性能和时间复杂度．在一些较大规模的真实社交网络实例中的实验研究表明,Hybrid-Greedy在这些社交网络中所得解的质量较Wang-Greedy和Raei-Greedy有明显提高．     

多目标优化量子免疫算法求解基站选址问题

为了解决带容量约束WCDMA网络的基站选址问题,提出了一个基于多目标优化量子免疫算法的基站选址优化方案.设计了基站选址问题的数学模型,给出了多目标优化量子免疫算法框架,并进行了实验验证.实验结果表明：算法方案能以较小的基站建设代价满足覆盖要求,具有较好应用价值.     

基于Hopfield网络的极小值问题学习算法

针对 Hopfield神经网络 (HNN )所存在的极小值问题及缺乏学习能力的问题 ,提出了一种学习算法。将决定约束条件权值大小的系数作为学习参数 ,在参数空间里使参数向着 HNN能量上升最快的方向学习 ,使网络状态能够有效地从可能陷入的极小值状态中逃脱出来。对于在状态空间里陷入极小值状态的 HNN,首先在参数空间里修正参数 ,然后再返回到状态空间里进行状态更新 ,如此反复 ,直至找到最优解或满意解。算法的有效性通过仿真实验进行了验证。该算法分别被应用于 10城市和 2 0城市的旅行商问题 ,结果能够以很高的比率收敛于最优解     

应用最小费用流求解活动网络时间-费用模型

提出了利用最小费用流原理求解时间-费用优化模型的方法.应用对偶理论将费用-优化模型转换为适用于状态算法求解的最小费用流问题,采用互补松弛定理和状态算法推出了由对偶问题最优解求出原问题最优解的等式,以一个实例说明了利用上述方法求解时间-费用优化模型最优解的步骤.所提出的求解时间-费用优化模型的算法,提高了求解问题的效率,可用于大型工程网络的费用优化.     

用Hopfield神经网络解决作业车间调度问题

对作业车间调度问题的换位矩阵表示方法进行了改进,给出新的作业车间调度问题的 Hopfield 神经网络计算能量函数表达式,然后提出改进的 Hopfield 神经网络作业车间调度方法。为了避免 Hopfield 神经网络容易收敛到局部极小的缺点,将模拟退火算法应用于 Hopfield 神经网络求解,提出随机神经网络作业车间调度方法。与已有算法相比,改进算法能够保证神经网络稳态输出为可行的作业车间调度方案。     

大型网络可靠性评估的增流减流交叉网流法

本文基于网络最大流原理,提出一种大型网络可靠性评估的增流减流交叉网流法。该方法通过削减某一状态下某些支路的网流来获取另一相关状态下各支路的网流初始直,从而大大减少了各状态下需要计算的增流次数。算例表明,该方法十分有效、此外,本文还就该方法与最小割集法进行了比较研究。     

一类网络容量扩充问题

给定一个连通网络,找两点之间的最短路,作为两点之间的流量路径。每条路径都有一定的需求,网络中每条边的容量至少为经过该边的所有路径的需求之和,若某条边的容量小于经过该边的所有路径的需求之和,则需要对其容量进行扩充。每种扩充方案的扩充费用是关于扩充容量的函数。本文给出解决该问题的一个多项式时间算法,使得各边容量达到需求,且总的扩充费用最小。     

城市交通网络目标配流模型

进行城市交通网络规划时,一方面需充分利用交通网络各路段的通行能力,另一方面又需考虑到某些路段为了控制交通拥挤、交通污染等而设置目标流量的要求,为此本文建立了已知固定交通需求下的双目标网络配流模型,并将此模型转化为等价的凸目标规划模型．通过求解最优控制不等式组模型的方法对配流模型进行求解．这模型及其算法在小型模拟网络上得到了实施．     

基于交叉点复杂度的空域通行能力优化方法

为解决空域拥挤导致通行能力下降的问题,提出了一种考虑交叉点复杂度的通行能力优化方法。首先,分析了实际民航运行中存在的痛点和难点,以及以往有关通行能力的研究缺少交叉点建模、管制员负荷测量困难和求解时间复杂度高的缺陷;第二,从高度层、交叉点和航班运行三个方面提出了空域的数学抽象方法,并根据节点的交叉数对空域的数学模型进行简化,剔除了没有交叉的导航台点,降低了空中交通网络抽象后节点矩阵稀疏的问题;第三,分析了交叉点对于通行能力的影响主要在于流量和交叉数两个方面,以这两个方面建立了交叉点的费用函数;第四,以延误最小为目标,以流量平衡、扇区和航路容量、流控容量和非负整数作为约束,建立了通行能力优化模型;第五,分析并指出存在负容差的空中交通网络更容易发生延误,并根据网络延误的特性提出了一种考虑延误反向传播的迭代算法。最后,以华北地区空域为例,从不同流控等级下的延误时间、受影响的航班数和算法计算时间三方面进行仿真。结果表明,模型和算法平均能降低33.58%的延误,且通过合理地分配改航、调时和调减最大程度减少延误。     

多目标模糊优化潮流模型及其基于神经网络的算法

提出了一种计算交流潮流的多目标模糊优化模型，模型中，同时考虑了发电费用最少及网损最小等多重目标，针对该模型，还提出了一种基于神经网络模型的新算法，该算法分别采用神经网络模型进行模糊集隶属函数的表达及优化问题的求解，从而将模糊优化同神经网络有机地结合起来，通过算例对所提模型及算法进行了验证。     

带转向延误的拥挤交通网络配流模型及算法

为了更加真实准确地反映道路网络的交通流状态,该文综合考虑拥挤交通网络的特点,建立了带转向延误和通行能力限制的交通网络配流模型,模型中路段和转向通行能力约束条件的Lagrange乘子等于因交通拥堵而产生的排队延误。该文采用动态罚函数算法,将原问题转化为一系列不带通行能力限制的传统交通分配问题进行求解,随后以Nguyen Dupuis网络为算例进行测试。计算结果表明:当流量达到通行能力时,排队延误就会产生,平衡流量满足Wardrop均衡准则。该模型能够很好地反映拥挤交通网络流量特点,提出的算法也具有很好的收敛性能。     

连续时间网络上的最小费用流问题

建立了连续时间网络上的最小费用流问题的数学模型；证明了连续时间网络中的增广流的存在性定理和最优性定理；最后给出求最小费用流的算法．     

神经网络在CDMA移动通信上行链路功率控制中的应用研究

提出了一种神经网络功率控制方案,研究了该方案在码分多址 (CDMA)移动通信中实现最小发送功率控制问题。首先导出了最小发送功率控制模型。而后,利用最陡下降方法得到了求解该模型的神经网络的原理框图,并分析了用该网络进行最小发送功率控制的基本理论和实际性能,探讨了该网络相关参数的确定方法。最后用计算机仿真法模拟出该方案的运行性能。仿真结果表明与最小功率分配算法相比,神经网络功率控制方案可以提高基站接收信号的平均信扰比,降低信扰比的平均偏差,提高信扰比达到目标信扰比 90%以上的用户数量,从而可以降低用户信号的中断概率、提高信道容量。     

基于主动网络的最优化流量控制

主动网络的分布式计算能力为网络流量控制提供了新途径,将网络的流量控制归结为一个用户收益的全局最优化问题,提出了改进的分布式算法来求解并设计了基于这种算法的主动网络最优化流量控制协议,证明了通过选取适当的收益函数,只需在主动结点中提供FIFO的调度机制就可根据用户需求分配不同的带宽,从而达到了区分服务的目的,仿真结果证明了协议的有效性。     

智能电网中基于平衡树的无线Mesh接入网络路由算法

在智能电网(smart grid,SG)接入层的无线Mesh网络(wireless mesh networks,WMNs)应用中,针对数据流过度地集中在关键节点而导致数据拥塞问题发生,提出一种基于平衡树的无线Mesh网络路由算法。在传统AODV(ad hoc on-demand distance vector routing)算法的基础上,使用平衡树模型,综合考虑节点剩余容量和转发数据所需的路由跳数建立路由判据模型,合理地选择下一跳中继节点,均衡节点数据流。路由算法仿真采用OPNET平台实现,就网络的吞吐量、通信时延以及网络丢包率3个重要方面,对所提的路由算法与传统AODV算法的性能进行了对比分析。仿真结果表明,提出的算法能够有效地解决无线Mesh网络中的数据拥塞问题,相比于传统AODV算法能明显提高网络吞吐量,减小网络通信时延和丢包率,进而提高网络整体的可靠性。     

考虑乘客选择行为的地铁车站承载能力瓶颈识别方法

乘客选择行为引起地铁车站客流量分布动态变化,并导致拥堵的传播,是承载能力瓶颈产生的关键因素之一.通过分析乘客在站服务事件链,构建地铁车站系统中设施设备关联网络.在分析乘客选择行为作用下的关联网络特性的基础上,建立了节点约束下的车站客流分配模型,并引入动态惩罚函数求解该模型,结合求解结果,提出通过节点受影响程度指标来识别能力瓶颈.以上海地铁陆家浜路站为例分析,与StaPass软件的仿真结果进行对比,验证了该方法的可行性和准确性,有助于快速分析不同客流条件下车站客流分布,并确定能力瓶颈.     

基于蚁群算法的多源组播流量均衡的研究

针对现有组播路由技术因路由单一而导致的不能满足多源组播网络中流量均衡的问题,基于蚁群算法提出了一种组播流量均衡的方法--LDA(load distribution algorithm)。LDA主要包括选择候选路由和组播调度两个模块,通过与常用的特定源组播路由协议(PIM SSM)相结合,从整体上考虑均衡网络负载的同时,一方面减小了组播数据包传递的时延,另一方面减小了丢包率。仿真实验结果表明,在PIM SSM的基础上,该方法能有效提高网络资源的利用率,降低组播数据传输时因排队造成的过大的时延和丢包率。