机会约束的多选择背包问题的遗传算法求解

机会约束的多选择背包问题(CCMCKP)是一类具有重要应用价值的NP难组合优化问题,但目前还缺乏关于该问题求解方法的专门研究。为此,提出首个CCMCKP的求解框架,并基于该框架构建了两种求解方法:基于动态规划的RA-DP和基于遗传算法的RA-IGA。RA-DP是精确求解方法,具有最优性保证,但是在可接受的时间(1 h)内仅能求解小规模问题样例;相较而言,RA-IGA是近似求解方法,具有更好的可扩放性。仿真实验结果验证了所提求解方法的性能:在小规模问题样例上,RA-DP和RA-IGA都可以找到最优解;在中大规模问题样例上,RA-IGA表现出了比RA-DP显著更高的求解效率,它总是可以在给定时间(1 h)内快速获得可行解。在CCMCKP的后续研究中,RA-DP和RA-IGA可作为基准对比方法,而实验工作中所构建的测试样例集可作为该问题的标准测试集。

无选择性约束在汉语驴子句中的运用

通过分析汉语驴子句的语义和句法,证明了无选择性约束是分析汉语驴子句的最佳方式。首先深入分析了三种条件句形式的汉语驴子句,即光杆条件句、"如果"条件句和"都"条件句,对郑礼珊和黄正德主张的汉语驴子句的分类提出质疑,建议将后句中出现的代词和疑问词均视为变量,与前句中的疑问词一同受必要算子的无选择性约束,被赋予全称量化意义。在统一了汉语驴子句的句法结构的基础上,进一步证明了语义部分得出的结论,即除非句中出现明显的时间标志或表存在性质的暗示,汉语驴子句应由无选择性约束理论来分析,两个分句都包含一个变量,同时被句中的一个显性或者隐性的全称算子约束,表全称量化意义。

改进蚁群算法的多约束质量最优路径选择

在交通拥堵日益严重的形势下,当今大众对行车过程中的道路质量评定标准发生了重大变化,如何避开拥堵,寻找最优的出行路径,已成为智慧城市建设大力推进背景下亟待解决的重要科学问题和社会问题.首先,定义了质量最优路径的概念,并构建了多约束质量最优路径模型;然后,为更有效求解该模型实现最优路径选择,在基本蚁群路径寻优算法的基础上,通过增加算法对道路通畅度、道路舒适度、道路费用等路径质量信息的实时感知,改进了状态转移规则中的启发函数和信息素更新算子,提高了算法自适应于路径质量信息的动态调整能力.实验结果表明:文中改进的蚁群算法与其他蚁群路径寻优算法相比,明显提高了路径寻优的正确率和收敛速度,能够更加快速、准确地进行路径选择.

基于距离向量深度的多约束路径选择算法

为各种应用提供不同的服务质量(Quality of Service,QoS)保证是下一代高速网络面临的一个重要难题,而服务质量路由(Quality of Service routing,QoSR)则是其中的一项核心技术.本文针对不精确状态信息下的多约束QoSR问题,建立了一种用于求解此类多约束QoSR问题的临界点模型,提出了一种基于距离向量深度的多约束QoS路径选择算法(MCPSA),该算法以已有的QoS路由预计算算法为基础,设法选择一条能够最大程度适应不精确网络状态信息的路径,理论分析表明该算法具有一定的优势.最后,结合已有的路由预计算算法进行了大量的仿真试验,结果表明MCPSA具有很强的问题求解能力,能够有效克服路由状态信息的不确定性.

新扬州鸡约束选择指数的探讨

利用新扬州鸡开产日龄、30 0日龄产蛋数和 30 0日龄蛋重 3个性状的遗传参数与 6组经济加权值求解出 6个约束选择指数及其预期遗传进展、预估准确度和指数的遗传力 ;通过实际记录模拟选择和预期遗传进展分析。结果表明 :在IA、IB、IC、ID、IE 和IF6个约束选择指数中 ,IE

基于局部近似过滤的多约束服务选择方法

随着Web服务数量与用户需求的不断增长,如何在功能约束和QoS约束下选择Web服务去构建高质量的组合服务已成为Web服务领域的一项重要研究内容。然而,现有大多数Web服务选择方法仅仅解决了在多种QoS约束下选择服务的问题,忽略了服务间的功能性约束。为解决这一问题,该文提出一种基于局部近似过滤的多约束服务选择方法。该方法首先利用候选服务在多种约束下的被选关系,滤除部分不满足约束的服务,并估算每个剩余候选服务的局部适应度;然后,利用文中设计的有向粒子群算法,以候选服务的局部适应度为引导信息搜索出最优方案。实验结果表明了方法的有效性。

基于免疫——蚂蚁算法的多约束QoS路由选择

针对多约束QoS路由选择问题,将其转化为一个多约束赋权图最短路径问题,选择费用、带宽、时延、丢失率为QoS参数。借鉴人体免疫系统的适应能力和蚂蚁算法的全局寻优能力提出了一种新的融合算法即免疫——蚂蚁算法。免疫算法把目标函数和制约条件作为抗原,目标函数的优化解对应为抗体,使得求解过程的收敛方向得以控制;利用蚂蚁算法产生和更新抗体,抗体交叉、变异操作以及对与抗原亲和力高的抗体进行记忆,均能促进快速求解。实验结果表明:免疫——蚂蚁算法表现出了超越免疫算法和蚂蚁算法的优点,大幅度提高了路由选择的效率。

约束选择指数的通径分析及决策分析

建立了约束选择指数的通径分析化模型,分析其实质为约束选择指数的相关遗传力分解模型。进而运用通径分析的决策分析方法对约束选择指数进行决策分析,定义各性状对聚合遗传值的决策系数,各性状的决策系数代表其对聚合遗传值的综合决定作用。通过各性状的决策系数可以确定主选性状、限制性状和辅助性状, 使育种者在育种时,可直接选择个体的表型就能达到使复合育种值进展最大的目的。

约束选择指数的通径分析化模型

建立了在各种约束条件下的综合选择指数（无约束、约束和最宜３种选择）的通径分析化模型。该模型可以分析出选择指数中任一性状ｘ＿ｉ对由它而使聚合遗传经济值Ｈ的相关进展ＣＧＳ＿（Ｈ（ｉ））的直接贡献ａ＿ｉ和ｘ＿ｉ通过ｘ＿ｊ对ＣＧＳ＿（Ｈ（ｉ））的间接进展，给出ｘ＿ｉ与Ｈ之间的全部路径信息，以确定主选性状、辅助性状和限制性状。结果表明，好的选择指效应由生物和经济的双重意义来确定。约束选择指数在育种上改变了经济权重的无约束选择，经济权重的改变是由约束条件引起的。

MPLS流量工程中基于约束的路由选择技术研究

在介绍MPLS流量工程基本概念的基础上,对流量工程的核心技术———基于约束的路由选择进行了系统的研究,并重点对基于约束路由研究的难点、计算方式、度量参数的选择作了深入的探讨,结合存在的问题,提出了今后基于约束路由可能的发展方向。

基于矢量测量的多约束路径选择

多约束路径(multi-constrained path,简称MCP)选择问题是QoS路由问题面临的重要挑战之一.现有的MCP算法不能兼顾降低计算复杂性、提高响应速度和防止可行解丢失等方面的缺点.另外,单纯依靠线性路径长度方程(LPLF)或非线性路径长度方程(NLPLF)都不能有效解决QoS路由问题.定义了崭新的法线测量路径长度方程,并基于该方程提出了解决m约束MCP问题的NMMCP(normal measure based MCP)算法.NMMCP不仅是在线计算与预计算,同时也是LPLF与NLPLF的良好折衷.通过引入Pareto最优理论,NMMCP具有非线性前瞻机制.大量仿真实验表明,NMMCP解决MCP问题是非常有效的.

草根NGO参与公共危机管理的约束性因素与路径选择

随着全球化、组织化、信息化的发展,政府垄断公共事务的管理模式正在发生深刻的变革。公共危机管理的复杂性必然要求政府、市场和社会的合作共治。作为社会力量的重要组织形式—草根NGO的专业性和灵活性弥补了政府在公共危机管理中的不足。然而,草根NGO现阶段的参与只是一种体制外的参与,存在制度、公信力、资金、人力及自身能力等约束性因素。本文针对这些问题,基于草根NGO处于发展的初级阶段这一现实,提出了建立合作型关系来优化草根NGO参与公共危机管理的路径。

中国商业银行利率风险管理的约束与行为选择

中国商业银行为什么存在着利率风险管理的弱化?这种选择是否满足于商业银行在约束条件下最优的理性行为?本文通过对中国商业银行利率风险管理的具体约束条件的分析,从成本收益角度,在理论上解释了中国商业银行行为的理性选择。

基于捕食模型与蚁群算法的多约束QoS路由选择

针对多约束QoS路由选择问题,将其转化为一个多约束赋权图,求符合最小时延和最小丢包率且满足最小成本的多目标问题。利用捕食模型调整最小时延和最小丢包率这两个目标的权值,快速找到非劣解集;再结合蚁群算法很强的全局寻优能力,完成最小成本的路由选择。实例计算结果证明了算法的可行性。

无线多媒体传感器网络中高效多约束QoS路径选择

为满足对环境进行更细粒度和更精确监测的迫切需求,无线多媒体传感网应运而生.对能量受限和拓扑结构动态改变的无线多媒体传感器网络而言,要在其中传送大数据量、大信息量的图像、音频和视频等多QoS约束条件的多媒体业务流,多约束QoS路径选择是一个巨大挑战和迫切需要解决的关键问题.该问题已经被证明是NP全问题.对此,人们提出了多项式时间和伪多项式时间启发式算法.但这些算法都是针对有线网提出的,计算复杂度高或者性能差,无法保证最终解的质量,并不适合无线多媒体传感器网.为此,本文提出一种新型高效的基于改进的模拟退火的多约束QoS路径选择方案,从冷却进度表中起决定作用的两个参数:控制参数T的衰减函数,控制参数T的终值Tf出发,构造出更精细的冷却进度表;此外,还研究了不同随机数发生器对算法搜索性能的影响.理论分析和实验仿真结果表明所提算法是一种高效的多约束QoS路径选择算法,在不牺牲算法复杂度的情况下,能提高最终解的质量,因此在性能方面优于其它现有的算法.

方向选择约束单纯形算法

一、引言人们一直致力于求解线性规划的单纯形算法的改进工作.1976年,Powell 发表过降低基维数的改进单纯形算法,这个算法是将基矩阵的一个块用基矩阵的其它块的乘积来表示,虽然实现了降低基维数,节省了存贮空间,却增加了计算次数,减慢了计算速度.Sethi and Thompson 针对线性规划问题也提出过竞争和非竞争约束(candidate andnoncandidate constraints)的概念.他们发现,随机生成的实验问题,其总约束中大约只有15%—25%是竞争约束,并提出了一个仅对竞争约束进行旋转运算的单纯形算法.他们的算法,对某些特殊的线性规划提高了求解速度,但并不减少基的维数,并不节省内存空间,增加了程序复杂性.1984年,Sethi and Thompson 又提出 PAPA 算法,再次利用线性规划问题通常只有少量竞争约束这个事实来提高求解速度.但 PAPA 算法往往要在原问题的可行域外运行.况且,上面提到的各种算法,均不能从理论上表明,它们较标准改进单纯形算法到底节省了多少存贮单元和节省了多少计算次数.

最大概率延迟约束路径选择算法

Qo S路由问题是下一代互联网的核心问题之一 ,而不准确状态下的路径选择问题是其中的难点问题。本文提出解决延迟约束路径选择问题的算法。首先给出链路的概率模型 ,在此基础上提出了延迟参数的路径选择算法。仿真实验证明 ,算法性能优异 ,并具有较好的稳定性。

时延约束费用最小路由选择算法

给出了两种新的边选择函数———费用下限函数 (LBC)和最大剩余时延 费用下限函数 (LBC RDM) ,并提出了时延约束费用最小路由的DCLC LBC和DCLC LBCRDM算法 ,大量随机网络模拟结果表明 ,DCLC LBC和DCLC LBCRDM算法性能相近 ,在费用竞争性和平均路由长度等指标上均明显好于目前的DCLC

改进分布式遗传算法多约束QoS移动IP路由选择

结合分布式遗传算法和Cascade模型的优点,提出改进分布式遗传算法,并将改进后的算法用于解决移动IP的多约束服务质量(QoS)路由选择。该算法在分群操作的基础上,根据每个子群进化的优劣程度动态地划分子群大小、控制子群间个体的迁移方向,使路径搜索更快、更好地收敛于最优。

基于改进分布式遗传算法多约束QoS移动IP路由选择(英文)

结合分布式遗传算法和C ascade模型的优点,提出了改进分布式遗传算法,并将改进后的算法用于解决移动IP的多约束服务质量路由选择.该算法在分群操作的基础上,根据每个子群进化的优劣程度动态地划分子群大小、控制子群间个体的迁移方向,使路径搜索更快、更好地收敛于全局最优.