求解MSA问题的新型单亲遗传算法

多序列联配(MSA)在生物信息学研究中占有重要地位,MSA问题是一个典型的NP问题,遗传算法是求解NP完全问题的一种理想方法。文章针对MSA问题,提出了一种新型单亲遗传算法(PGA),不使用交叉算子,只使用变异和选择算子。并根据群体的多样性自适应调节变异概率,有效消除了算法中的欺骗性条件,使用灾变算子来确保算法的搜索能力。整个算法模拟了自然界进化的周期性,较好地解决了群体的多样性和收敛深度的矛盾。算法的分析和测试表明,该算法是有效的。

基于MSA特征和模拟退火优化的遥感图像多目标关联算法

由于当前遥感成像技术一般只能获取采样稀疏的遥感图像,无法准确估计目标的状态信息,因此传统的利用状态特征进行关联的方法并不适合遥感图像的目标关联。选取不依赖于时间的目标图像特征作为关联量又无法处理大场景中多个目标关联引起的模糊性。针对上述问题,本文提出了基于多尺度自卷积不变矩特征匹配和模拟退火优化的多目标关联算法。首先提取目标的多尺度自卷积矩(MSA)特征,计算特征间匹配概率,构造整体关联代价矩阵,并设置自适应温度更新函数和双阈值对模拟退火算法进行改进,快速寻求全局最优解。实验结果表明,该算法能够有效地利用遥感图像特征信息,消除关联模糊性,高效解决多目标关联问题。

基于行程质量的随机用户平衡分配模型

提出行程质量的概念以描述出行者在不确定环境下的路径选择准则。将行程质量定义为行程时间和行程时间可靠性的线性加权和,综合了影响路径选择的两个不同的重要因素:行程时间和行程时间可靠性。假定在路段通行能力随机变化的情况下出行者以估计行程质量费用最小作为路径选择的标准,建立了基于行程质量的随机用户平衡分配模型。证明了模型解的等价性和唯一性,给出了求解模型的MSA算法。在一个小型测试网络上的计算结果表明:模型能够反映出行者在随机路网中的路径选择行为。

基于网络均衡的交叉口分流率计算方法

为研究交通需求的空间分布对网络瓶颈的影响,提出了基于网络均衡的交叉口分流率计算方法.以随机型用户均衡网络为对象,研究网络均衡状态下的路段选择率、交叉口分流率及其相互关系.以Dial加载为基础,根据概率原理和权理论推导得出单路段和双路段选择率的计算公式.根据交通网络均衡状态下的路段选择率和MSA算法与Dial加载的关系,推导了交叉口分流率和分叉流量的计算公式.用数值实验验证了提出的方法的可行性.

交通分布-交通分配组合模型研究

在交通规划实践中,交通分布和交通分配问题作为“四阶段预测模型”各自独立,尽管两个问题紧密相关.因此,有必要建立交通分布-交通分配组合模型,来反映这种反馈.文中介绍了Evans模型,并说明了逐次平均法求解模型的步骤,最后用算例说明了具体算法.这种方法完全可以用M icrosoft Exce l计算,计算方法简单,可以为组合模型的求解提供新的思路.

基于遗传算法与星比对的多序列比对混合算法

多序列比对(MSA)是一个典型的NP完全问题,星比对是一种有效的多序列比对算法。文章针对MSA问题提出了将遗传算法与星比对算法结合在一起的混合算法,该算法充分发挥了遗传算法和星比对算法的优越性,可提高求解MSA问题的计算精度和计算速度,整个算法模拟了自然界进化的周期性,较好的解决了群体的多样性和收敛深度的矛盾。实验表明,该算法是有效的。

出行策略与行程时间不确定下的公交客流分配方法

利用杭州市公交线路站点GIS数据和车辆运行GPS数据进行分析,将公交车到站时间分为站点停靠时间和站间行程时间,得到公交车站点之间运行可能总时间的分布概率.通过实际的公交路网结构,定义扩展的公交网络有效路径.在考虑公交线路联合发车频率和根据乘客路径选择的广义成本下,建立出行策略与行程时间不确定下的公交客流分配模型,并将公交线路发车时刻表引入用户均衡模型中,设计了基于扩展网络最短路的Method of Successive Average(MSA)算法求解,通过对两个交通小区间高峰小时的客流分配结果验证模型和算法的有效性.

准循环LDPC码的两种典型快速译码算法研究

该文从译码速率、硬件实现的复杂度和误码率3个方面对比研究了两种典型的高速译码算法:Turbo型和积算法与并行加权比特翻转算法。以准循环LDPC码为对象,给出了Turbo型和积算法和并行加权比特翻转算法的实现时序、硬件复杂度以及误码率性能,其中,并行加权比特翻转算法的高效时序结构是首次给出的。计算机仿真结果表明,这两种算法都能够在迭代次数较少时取得良好的性能。

系统最优与随机用户平衡共存的交通网络组合模型

在实际交通系统中,往往系统最优(SO)原则与随机用户平衡(SUE)原则共存.首先给出SO与SUE共存时的组合式条件,然后将整个交通需求分成遵循SO原则及遵循SUE原则的两个子系统,在两个子系统为固定需求的前提下,给出一个兼顾SO与SUE的更符合实际的综合模型,证明此模型的一阶条件满足SO与SUE共存时的组合式条件,并根据相继平均算法(MSA)思想设计了算法.

截断随机出行时间下可靠网络均衡模型

针对现有随机交通网络均衡模型未考虑路径出行时间的有界性和准时到达概率对出行者路径选择行为影响的问题,基于截断随机出行时间,提出了克服其局限性的可靠网络均衡条件,该均衡条件下没有出行者可以通过单方面改变出行路径来提高准时到达概率.构建了该均衡条件的等价变分不等式(VI)模型,并证明了其等价性和解的存在性.设计了基于路径的相继平均(MSA)算法对模型求解.采用Nguyen-Dupuis网络对可靠网络均衡模型和MSA算法的有效性进行了测试.研究结果表明:该算法能够快速收敛到较高精度;与不考虑随机出行时间有界性的模型相比,网络均衡状态下的准时到达概率和流量分布均存在差异,最大路段流量相对变化值达到38.5%;增加出行时间预算和降低出行时间上界均可以有效提高起讫点间的准时到达概率.

动态广义出行费用随机用户平衡

为描述弹性需求下降级路网中出行者路径选择行为,为出行者和管理者提供决策参考,采用行程时间、行程时间可靠性及货币费用的加权和定义动态广义出行费用.假定在路网随机变化的情况下,出行者以估计广义出行费用最小为路径选择标准,建立基于动态广义出行费用的随机用户平衡模型,并给出求解模型的MSA算法.通过在一个算例路网上测试,结果表明:出行者对待风险的不同态度、降级系数和货币费用均对道路流量分配影响显著,并与经验相吻合,说明所提出的基于动态广义出行费用的随机用户平衡模型能够真实反映出行者在随机路网中的路径选择行为.

用户平衡算法中目标函数值与迭代次数关系研究

在计算机实现用户平衡和随机用户平衡交通分配中应用较多的几种算法,如方向搜索法和相继平均法等的基础上,针对不同阻抗函数条件和多OD点对间流量分配问题中运用这几种算法的计算结果进行对比分析,得出目标函数值、检验数和迭代次数3者之间变化关系。结果显示,各种算法中目标函数值并不完全随着迭代次数的增加而严格递减,检验数的变化也不完全与目标函数值的变化同步,且不同条件下这种目标函数值、检验数与迭代次数的关系也不尽相同。

基于多步分解算法的解盲源分离新方法

在利用二阶统计量实现盲源分离问题中,混迭矩阵经过白化以后转变成了酉矩阵。针对酉矩阵各列之间相互正交的特性,提出一种关于酉矩阵某一列的最小二乘对称代价函数。通过基于梯度下降法的三迭代算法,交替估计三二次代价函数中的各组待定参数,搜索代价函数最小点,从而得到对应能量最大信号源的酉矩阵的一列。利用系统化的多步分解算法(MSA),依次估计酉矩阵的一列,最终得到整个酉矩阵的估计。仿真结果表明,与经典的通过连续Givens旋转求酉矩阵的SOBI算法相比,该算法全局拒噪水平至少改善了9dB,而所需计算时间仅为SOBI的二分之一,更有效地解决了盲源分离问题。

基于多步分解算法的解卷积混合盲源分离新方法

该文提出一种基于二阶统计量的时域多步分解算法求解卷积混合盲源分离问题。引入白化处理,将混迭矩阵转变成酉矩阵,同时,根据源信号不同延时下相关矩阵所具有的块状对角结构,将酉矩阵分为不同的列块。针对各列块之间相互正交的特性,提出一种关于某一特定列块的最小二乘三二次代价函数。利用一种常规的基于梯度下降法的三迭代算法,交替估计代价函数中的3组待定参数,搜索其最小点,得到酉矩阵一个列块的估计。利用系统化的多步分解算法(MSA),依次估计酉矩阵的每个列块,最终得到整个酉矩阵的估计,进而恢复出源信号。仿真结果表明,新方法性能优于经典的SUB方法及新近提出的JBD-NonU方法,可有效地解决卷积混合盲源分离问题。

双系统共存的交通网络组合模型研究

文章讨论了系统最优(SO)原则与随机用户平衡(SUE)原则共存的情况。首先给出了SO与SUE共存时的组合式条件,然后将整个交通需求分成遵守SO原则及遵守SUE原则的两个子系统,在两个子系统为固定需求的前提下,给出一个兼顾SO与SUE的更符合实际的综合模型,证明了此模型的一阶条件满足SO与SUE共存时的组合式条件,并根据相继平均算法(MSA)思想设计了算法。

考虑快捷性和舒适性出行偏好的网络混合均衡

为建立更科学、出行舒适的交通分配模型,探讨了路段舒适性的定义与量化,建立了舒适性出行偏好的网络均衡模型。将出行者划分为快捷性偏好和舒适性偏好两种类型,假设网络中两种出行者同时存在,构建与混合均衡条件等价的多用户混合均衡模型,并对该混合均衡模型的MSA求解算法进行设计。研究结果表明:舒适性路径选择行为形成的均衡流分布模式与快捷性的均衡流分布模式不同,两种路径选择行为导致的网络均衡状态均为混合均衡状态的特例。舒适性的交通分配模型可以弥补传统交通分配模型的不足,所预测的网络交通流分布形态也更准确,可为交通管控方案提供新的思路。

一种鉴定蛋白质突变和翻译后修饰的算法

提出的MSA(Modified Spectral Alignment)算法,改进了SA(Spectral Alignment)算法中D(k)和k-最佳Spectral Alignment的求解方式,并在算法中引入"双端考虑"。实验结果数据表明,MSA算法有效地提高了鉴定含突变或翻译后修饰的蛋白质的能力。

基于列车时刻表的城际铁路客流分配研究

目前,城际铁路配流大多基于列车开行方案,配流的结果时刻信息度不高。为促进基于时刻表的城际铁路配流研究,建立基于城际铁路列车时刻表的客流分配方法,构造旅客乘车过程的时空网络,并定义影响城际间旅客出行选择的广义出行费用,提出基于随机加载的列车客流分配方法,并得到分配方案,使旅客对乘车方案的表达更加直观。

大城市客运铁路枢纽客流分配模型

不同时段内,不同区位的旅客会根据不同的接驳方式及城际列车班次进行城际出行.只根据城际间的出行成本无法准确地刻画旅客的出行.在已知不同时段内城市间各分区OD客流、城际列车时刻表和铁路枢纽布局的前提下,构建城市内接驳交通网络;利用多项Logit模型,建立各个交通分区到铁路车站的接驳子模型;进而利用列车时刻表得到城际出行成本,并考虑列车拥挤造成的成本增加,根据总成本最小原则及接驳子模型,构建分时段的铁路枢纽客流分配模型.通过改进的MSA算法进行求解,得到各时段内各交通分区到铁路车站、以及铁路车站之间的客流量.最后通过算例,对方法的可行性及有效性进行了验证.

轨道交通沿线常规公交线路优化方法

为研究轨道交通网络下常规公交线路的最优布设,考虑乘客出行行为,建立了双层模型。下层模型中,考虑候车时间、走行时间、票价、拥挤度、换乘次数等因素,以巢式Logit(NL)模型计算出行选择概率,利用MSA算法求解线路分配流量;以候车时间最少和运行成本最低为下层目标函数,利用遗传算法求解不同时段最优发车间隔;上层模型中,以乘客总候车时间最少、客流周转量最大、乘客出行成本最少、公交车辆运行成本最少为上层目标函数,带入下层模型的客流量求得最优线路组合,最后利用算例对该方法进行论证,模型和算法能较好的解决所研究问题。