基于Prim算法的度约束最小生成树问题研究

针对一类度约束最小生成树问题,基于传统最小生成树问题的Prim算法,设计了一种求解算法.该算法在保证网络中指定节点的度不变的前提下,构造了网络关于指定节点的最大度最小生成树.与经典的Gloveklingman算法进行了仿真比较,结果表明,该算法是求解度约束最小生成树问题的一种有效算法.     

用最小费用流的允许边算法求解指派问题

构造指派问题的最小费用最大流模型,并将基于对偶原理的允许边算法用于该模型,提出了求解指派问题的一种新算法。该算法按照互补松驰条件,通过修改已标号节点的势,在容量-费用网络中逐步扩大允许网络,并在其中增广流量,直至求得容量-费用网络的最小费用最大流,此最大流中的非0流边即对应于指派问题的最优指派。在迭代过程中,后续迭代充分利用了上一迭代的信息,有效节省了计算量。对于非标准指派问题,可以直接求解,而不需要先将其转化为标准形式。     

总流量可变的最小费用流问题及其求解

讨论在总流量可变动的情况下，网络最小费用流问题的解法。分别就单源单汇和多源多汇情况构造不同的辅助网络，将原网络中的最小费用流问题转化为辅助网络中的最小费用循环流问题，然后用瑕疵算法求最小费用循环流问题的最优解，这样在求出原网络中最小费用流的同时，也获得了总流量的最优取值。     

智能家居中的网络路由改进算法研究

在智能家居中搭建网络过程中，为优化网络路由算法，提高算法的全局搜索能力和收敛精度，提出一种基于BFA(细菌觅食算法)的优化算法。通过选取随机网络拓扑模型建立50节点网络拓扑图和100节点网络拓扑图，利用GFBA算法进行仿真实验，仿真结果表明：与现行的网络路由算法相比较，在网络费用以及收敛时间方面验证GFBA算法对于网络路由问题的适用性和优越性。     

一类度约束最小生成树问题的Dijkstra算法

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

用对偶原理求解最小费用流的一种新算法

基于对偶原理提出了求解最小费用流的一种新算法,该算法不需要传统方法中的构造剩余网络以及求最短路等步骤,而是保持互补松弛条件不变,通过在原网络中修改节点的势,给节点标号寻求目标流。并给出了新算法正确性的证明。算例表明该算法可明显减少迭代步骤。     

求解最大度约束下最小生成树的新算法

针对网络优化中度约束最小生成树问题的特征,融合破圈法的基本思想,提出了一种求解网络G关于指定节点的最大度约束下最小生成树的新算法。该算法在保证指定节点最大度的前提下,每次通过去掉圈中权最大的边,最终构造出网络G关于指定节点的最大度约束下的最小生成树。算法证明和算例都表明了该算法的有效性。     

最小费用流的直接优化

研究了广义最小费用流问题，给出并证明了最小费用流的直接优化算法。数据裕列表明，直接优化算法不仅有效而且可以弥补ＯＫＡ算法的缺陷，并能解决网络流规划的其他类型的问题。     

一种基于最小路径的多播路由优化算法

信息物理融合系统(Cyber-Physical Systems,CPS)底层是传感器、控制器和执行器等异构节点构成的无线自组网络,不同节点之间需要通过通信网络传送给感兴趣目标节点,传统的无线自组织网络一般采用单播或广播技术,但是这些往往实时性不高,通信开销大,不利于在CPS中受限节点间通信.该文针对信息物理融合系统中无线多播路由问题构建网络模型,演化为最小路径问题,数学模型为约束Steiner最小树问题,并针对该NP难问题通过启发式算法求解,再通过贪婪思想构建一种最小路径多播路由算法.最后通过与uCast以及SenCast等经典的多播路由算法仿真比较,得出其算法在实时性以及能耗等方面性能优异.     

无线传感器网络中能量全局优化精确数据收集

在多跳无线传感器网络进行精确数据收集时,靠近汇聚节点(sink节点)的传感器节点因为需转发其他节点的数据,其能量消耗快,容易使网络造成能量空洞,缩短网络寿命。为延长网络寿命,提出一种能量全局优化的精确数据收集算法(EGODGA),有效地收集传感器节点的数据。与经典的最短路径算法Dijkstra不同,EGODGA算法同时考虑链路代价和节点代价,找出从源节点到目的节点的最小代价路径,实现网络能量全局优化。仿真结果表明:在相同的条件下,与经典的最短路径算法Dijkstra和对瓶颈节点能量均衡问题解决较好的MAXLAT算法相比,EGODGA算法可以通过优化网络拓扑子树的节点数目,实现网络的能量均衡,缓解网络瓶颈问题,延长网络的整体寿命。     

进货量受限的运输和库存整合的批量问题

考虑由一个分销中心和一个零售商组成的单一产品两级动态经济批量问题,其中零售商在每一进货期的进货量都具有数量限制.目的是确定分销中心和零售商分别在什么时期进货以及进多少单位的货物,从而使分销中心和零售商的运输费用和库存费用总和最小.分析了最优解的性质,并且利用动态规划和最短路问题在O（n5）时间内解决了此问题.最后给出了此算法的一个算例,表明此算法是可行有效的.     

一种求解工程调度中时间/成本权衡问题的遗传算法

结合工程调度中时间/成本权衡问题的特点,设计了一种有效的求解工程底线问题的遗传算法,基于该遗传算法提出了有效工期/成本曲线的绘制策略·对遗传算法解的编码方式、遗传算子的定义及算法结构进行了描述·通过对大量测试问题的求解实验表明,遗传算法是求解该问题的一种有效算法     

多产品三阶段供应链选址分配问题及其遗传算法

 建立了一种基于最小物流费用的多产品三阶段供应链选址分配模型,该模型综合考虑了原材料和产品的运输费、工厂的固定建设费及原材料采购费和产品加工费、销售中心的固定建设费和库存保管费等。在多产品三阶段供应链体系中,在供应商-工厂阶段,一个工厂不仅可以从不同的供应商处采购不同产品的原材料,而且同一种产品的原材料也可以从不同的供应商处采购;在工厂-销售中心和销售中心-顾客阶段,产品需求者虽然可以从不同供应者处采购不同产品,但同一种产品却只能从一个供应者处进货。根据模型的这些特点,本文结合选址问题的随机顺序编码和运输问题的优先权编码技术,设计了一种新的染色体编码方法,从而借助遗传算法实现了多产品三阶段供应链选址分配问题的求解。数值仿真结果表明,本文给出的染色体编码方案是恰当的,设计的遗传算法具有较高的搜索效率,能够快速稳定地求解多产品三阶段供应链选址分配问题。     

改进的产品投资算法

 在产品投资算法的基础上探讨了同时存在追加投资费用和浪费费用的教育投资问题,得到了一个好的算法,并对该算法的复杂性进行了分析.     

链路优化时延约束组播路由的遗传算法

针对网络的瓶颈路径易造成网络拥塞的现象,分析了链路负载不平衡的原因,重新给出链路代价定义,提出一种遗传算法求解该类组播路由问题.算法从链路代价权值转化开始,以满意的时延树为遗传算法的初始解集,然后在交叉操作过程中不断地用低链路代价的边代替树中高链路代价的边,以求得满足链路代价最优的组播树.仿真结果表明,该算法在考虑网络的负载均衡情况下,选择链路代价较低的空闲路径,快速、有效地构建满足时延要求,链路代价最小的组播树.     

装配型的生产存贮网络

本文考虑了无生产约束的确定型的装配型生产存贮网络,证明了问题可化为r-网络上的最小费用流问题,由此导出了一个动态规划算法,且证明了在特定的条件下,存在一个最优解具有套入结构。     

基于神经网络的逻辑最小造价覆盖算法

提出一种基于神经网络求解逻辑综合中最小造价覆盖问题的优化算法。首先给出了最小造价覆盖问题与能量函数的映射关系，并以此构造了改进的两级Ｈｏｐｆｉｅｌｄ网络模型。然后利用该网络的动态特性，求出最小造价覆盖问题的最优解。最后对算法进行了分析和小结。     

基于混合遗传算法的应急物资配送路径优化

为解决突发事件下应急物资的配送路径优化问题,以配送车辆的固定成本、运输成本、违反最大载重量以及右时间窗的惩罚成本之和最小为目标,构建了带时间窗约束的应急物资配送路径优化模型;通过将遗传算法与节约算法、大规模邻域搜索算法相结合,设计出了一种混合遗传算法对模型进行求解;最后用算例仿真验证了模型和算法的可行性。实验结果表明:设计的混合遗传算法在求解过程和求解结果上都比标准遗传算法更优,可见能够为解决应急物资的配送路径优化问题提供科学的决策依据。     

一种计算网格资源分配的混合优化算法

针对计算网格提出了一种时间和费用混合优化的资源分配算法,以最小化用户的时间和费用为目标函数,以预算和时限为约束条件,运用经济规律把网格资源分配给一组相互竞争的网格用户。首先将多用户竞争使用同一资源的问题形式转化为一个多目标优化问题;然后建立了该优化问题的评价函数,采用α-方法确定权重,得到一组优化的资源分配,使所有参与竞争资源的用户都得到一个优化解,满足了用户需求的异构性;模拟实验证明了该算法的有效性。     

基于模糊遗传算法的机组组合问题的求解

为求解机组组合问题,提出一种模糊优化与遗传算法紧密结合的新的模糊遗传算法.通过建立模糊推理规则,对交叉率和变异率进行模糊控制,从而提高了收敛速度,避免了不成熟收敛.将该模糊遗传算法应用于一工程算例中求解机组组合问题,与传统遗传算法相比,在同样的种群规模和终止准则下,采用该算法的收敛迭代次数减少,减幅最大达122次,而每次迭代计算时间最多仅增加约0.01 s;优化组合的发电成本减小,减幅最大时达总发电成本的0.73%.