八角形斯坦纳树问题的文化基因算法

针对多端线网互连问题,提出以超大规模集成电路物理设计中布线阶段应用较多的斯坦纳树为切入点,采用一种基于种群的全局搜索和基于个体的局部启发式搜索相结合的文化基因算法,对八角形斯坦纳树的结构进行优化,从而进一步缩减线长.使用Prim算法预处理取得初始种群,并重新修改了原本的文化基因的编码以及相关操作,以便可以处理八角形斯坦纳树构建这一离散问题,利用八角形结构,使其能在全局范围内,快速收敛并全局寻优.实验结果表明,所提算法能获得较好拓扑的八角形斯坦纳树,快速得到多端线网最优或者较优的布线结果,缩减布线的线长.     

最小直线斯坦纳树及其在详细布线中的应用

在面向区域的详细布线中,最小直线斯坦纳树(MRST)可为单个线网产生满足连线最短要求的最佳初始布线模式,可为全局最优布线大大减小搜索空间。一般说,构造MRST是NP完备问题,为了降低问题的复杂度,需要研究生成MRST的实用有效算法。本文讨论了两种这样的算法,并结合例题说明,MRST只是局部最优树,在实际布线应用中要综合考虑其它布线质量因素,对当前线网的初始MRST进行调整或动态修改。     

布局中的布线拥挤度估计及其优化

针对版图设计阶段越来越严重的布线拥挤问题,提出了一种有效降低布线拥挤度的标准单元布局算法.它是在高质量线长优化布局之后对布线拥挤度进行单独优化.该算法使用一种新的改进的布线模型对芯片的布线情况进行估计,采用以线网为中心移动的优化方法解决局部区域内的布线拥挤问题.实验结果表明,该算法在使线网总长略微增加的同时使芯片的布线拥挤度问题得到了很好的解决.     

VLSI标准单元阵列布局问题的一个高效遗传算法

研究可有效处理几万至百万个单元规模VLSI标准单元阵列布局问题的遗传算法,使之能在合理的时间内获得高质量的布局结果.为了提高布局质量,针对布局的二维特性设计了新型线网交叉算子和局部搜索技术,并提出了三阶段算法框架以协调算法的全局搜索和局部搜索.为了降低算法的时间和空间复杂度,使算法可处理大规模问题,采用了交叉算子局部化和小规模种群的思想,同时使用了多种保持种群多样性的策略以提高小规模种群的进化性能.对Peko suite3、4标准测试电路的实验结果表明,基于这些策略的遗传算法是有效的.     

求解边坡最小安全系数的混合文化基因算法

基于瑞典圆弧法的数学模型,提出一种有效用于求解边坡稳定最小安全系数的混合文化基因算法.该算法结合了遗传算法优秀的全局搜索能力与低温状态下模拟退火算法的快速局部收敛特性,使算法在全局搜索和局部搜索之间达到较好平衡.通过典型工程实例分析,验证了该混合文化基因算法在搜索边坡最小安全系数及其所对应的最危险滑动面位置的有效性.     

基于混沌遗传算法的QoS组播路由

针对遗传算法在搜索最优组播树的过程中易发生早熟收敛的缺点,提出一种抑制早熟的混沌遗传算法.利用混沌的随机性和遍历性,将混沌扰动算子加入到遗传算法的操作中,当判断种群有早熟发生时,就对该种群进行类似变异的混沌扰动操作,从而增加了种群的多样性,既保留遗传算法的全局搜索能力又能有效改善算法性能.仿真结果表明,该算法能克服早熟收敛的缺点,又能快速、有效地构造出满足QoS约束要求的最优组播树.     

一种求解约束优化问题的改进差分进化算法

针对原始差分进化算法在求解约束全局优化问题时存在陷入局部最优的缺陷,提出一种改进的差分进化算法.该算法在保留原始差分进化算法全局搜索能力的基础上,采用基于规则的方法进行约束处理和种群个体的比较及选择,并利用种群相似度和最优变异操作改善种群进行全局范围搜索的多样性,提高算法跳出局部最优的能力.数值实验表明,该算法稳定性较好,目标函数评价次数较少,收敛速度较快,全局寻优能力较强,不仅能有效求解连续变量约束优化问题,也适用于离散变量或混合变量优化问题.     

基于物种选择的遗传算法求解约束非线性规划问题

将信赖域思想和基于稳定进化策略思想相结合,提出一种基于物种选择的遗传算法.根据当前代最优点,采用稳定最优种群数目和收缩最优种群边界的方法将种群划分为最优种群和全局种群,并提出基于构造优化方向的一种新的交叉算子.研究结果表明:对这2种群按不同的策略协调进化,较好地平衡了种群的多样性和选择压力,兼顾了局部搜索和全局搜索;缺少合适的搜索方向是进化后阶段收敛速度慢的重要原因之一;本算法能有效地提高遗传算法的收敛速度,并具有比较好的鲁棒性.     

基于基因重组的新颖克隆选择算法

受生物免疫系统免疫机制的启发,提出了一种新的克隆选择算法RBCSA.首先,根据B细胞免疫反应中的基因重组原理引入了一种新的基因重组复合算子来加强种群个体之间的信息交互,进而提高算法全局搜索的能力.然后,对克隆选择算法中的超变异算子进行了改进,进一步加强了算法的局部搜索和寻优的能力.最后,结合新提出的基因重组算子和改进的超变异算子,提出了一种新的基于基因重组的克隆选择算法,并通过求解16个常用的全局最优化问题的经典测试函数进行仿真实验,结果表明RBCSA算法具有很好的平衡全局探索和局部寻优的能力,有效地提升了克隆选择算法的寻优性能,尤其对于高维最优化测试函数.另外,与现有其他进化算法相比,RBCSA算法显示出了很强的竞争力.     

一种考虑环境作用的协同免疫遗传算法

在综合考虑了环境对生物进化的影响、免疫算法的结构以及遗传算法部分算子的基础上,提出一种考虑环境作用的协同免疫遗传算法(ESIGA),以实现提高算法搜索速度和全局搜索能力的目标.在该算法中,设计了克隆环境演化算子和自适应探索算子,并构造了3个子种群协同进化以发挥克隆环境演化算子的影响,从而提高算法的全局搜索能力.引入的自适应探索算子和克隆环境演化算子,使算法具备了一定的学习能力,可加速搜索和防止早熟.构建的主种群和协同种群相互影响,使得算法对环境具有改良能力,加强了克隆环境演化算子的性能,而精英种群则加强了算法在优质个体邻域的搜索能力.采用13个常用无约束优化问题测试函数对算法做了检验,测试数据表明:ESIGA算法与正交遗传算法相比,其搜索速度要快于正交遗传算法1～2倍,并能够处理1 000维的高维优化问题.     

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

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

基于Logistic回归模型和凝聚函数的多示例学习算法

实时多媒体网络中,带延迟与延迟抖动约束的斯坦利树问题是一个研究热点.这种带约束的斯坦利树被证明是NP-完全问题.提出了一种基于禁忌搜索的带延迟与延迟抖动约束最小代价组播路由算法.实验结果表明,该算法对于实际网络是有效的.这种方法使得IP组播把数据同时发送到组成员时有效地利用了网络资源.

Abstract：

The delay and delay variation-bounded Steiner tree problem is animportant multicast routing issue in real-time multimedia networks.Such a constrained Steiner tree problem is known to be NP-complete.A multicast routing algorithm is presented,which is based on tabu search to produce routing trees having a minimal network cost under delay and delay variation constraints.The approach makes IP multicast utilize resources efficiently in delivering data to a group of members simultaneously.     

基于进化规划的网络多目标路由算法

多目标路由问题要求极小化网络带宽资源消耗 ,它与图论中 NP完全的 Steiner问题等价 ,不存在多项式时间算法 ,只能采用近似算法或启发式算法 .进化算法是一类有效求解优化问题的新算法 .应用进化算法中的进化规划方法 ,求解 Steiner问题 ,提出了一种新的多目标路由算法 .仿真结果显示 ,该算法性能高于启发式方法     

欧氏Steiner最小树的Delaunay三角网混合智能求解方法

欧氏Steiner最小树问题是组合优化中一个经典的NP难题,在许多实际问题中有着广泛的应用.由于使用普通智能算法求解较大规模问题时,极易陷入拓扑结构的局部最优,因此,基于Delaunay三角网技术并结合智能算法的有关思想,设计了一种改进的混合型智能求解方法,可大幅度提高算法在寻找更好拓扑结构上的有效性.算法在Matlab环境下编程实现,经大量STEINLIB中的标准数据实例测试和验证,获得了满意的效果,为求解较大规模的欧氏Steiner最小树问题提供了新的有效方法.     

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

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

图的Steiner最小树的竞争决策算法

图的Steiner最小树问题是一个著名的NP难题,在通讯网络、VLSI等工程实践中有着重要的应用.在分析图的Steiner最小树问题数学性质的基础上,提出了图的Steiner最小树的竞争决策算法.为了验证算法的有效性,求解了OR-Library中的基准问题,测试结果表明了算法具有较好的求解效果.     

针对VLSI布线的多层X结构斯坦纳最小树构建算法

考虑到粒子群优化算法具有非常出色的全局优化能力,针对X结构布线问题的复杂性提出了X结构下的多层Steiner最小树构建算法.实验结果表明,该算法可以在合理的时间内取得优异的布线解.     

改进的WPAN网状自适应树路由算法

为扩大无线个人区域网(WPAN)的网络覆盖范围,增强网络的可靠性,研究了网状自适应树算法应用于大规模网络可能产生的地址溢出问题。通过将整个网络划分为更小的子网络,利用分区方法构建分区网状自适应树,并结合分区网状自适应树的分层拓扑结构,提出一种改进的网状自适应树路由协议算法。实验结果表明,该算法在不增加路由开销和网络负载的情况下扩大了网络覆盖范围,并有效减小了端到端时延,提高了报文发送成功率和通信效率,在不同规模的网络中均保持了较好的性能,为提高无线个域网的覆盖性和可靠性提供了理论依据。     

多Sink无线传感器网络鲁棒路由协议

针对多Sink无线传感器网络中由Sink节点失效引起的局部数据拥塞,进而导致网络鲁棒性减弱的问题,提出基于侦听机制和模糊控制的多Sink无线传感器网络鲁棒路由协议．该协议采用侦听机制．建立并维护多维树状拓扑路由,避免了采用泛洪方式组网而造成的资源浪费;加入以负载、丢包和跳数为目标的模糊控制算法,进行路由选择,均衡了网络负载．仿真结果表明,该路由协议在一定程度上缓解了网络中Sink节点失效造成的大量丢包以及数据拥塞问题．增强了网路的鲁棒性．     

基于出行偏好和路径长度的路径规划方法

针对基于最短路径的路径规划方法只关注路径长度, 而基于轨迹的路径规划方法过度依赖用户偏好的问题, 提出一种同时考虑用户出行偏好和路径长度的路径规划方法. 首先, 利用长短期记忆模型从历史出行轨迹中提取用户的出行偏好; 其次, 采用Markov链Monte Carlo采样技术将用户的出行偏好引入启发式搜索算法A*中, 在道路网络中搜索得到符合用户出行偏好且较短的路径; 最后, 以北京市路网和出租车轨迹数据作为测试数据, 将该方法与基于最短路径的规划方法和基于轨迹的路径规划方法进行实验对比. 实验结果表明, 该路径规划方法更稳定, 并且其规划的路径具有较高的准确度、 较短的行驶距离和行程时间.