一种尺寸可变的装箱问题的在线近似算法

给定物品系列,要求将所有物品装入到不同类型的箱子中,以实现从第一个箱子到最后一个箱子被使用的箱子的总尺寸最小化。本文用最坏情况绝对性能研究在线算法,对于两种箱子规格和,我们给出了一种最坏绝对性能比最多是2.75的在线近似算法。     

一种尺寸可变的装箱问题的在线近似算法

用最坏情况绝对性能研究尺寸可变的装箱问题的在线算法,对于两种箱子规格a和b,给出了一种最坏绝对性能比最多是2.75的在线近似算法.     

最小费用箱子覆盖问题及其算法

提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用2个参数.针对局外最小费用箱子覆盖问题,给出了一个求解该问题的最坏情况渐近性能比为1/2算法C-FF1.同时给出了一个求解该问题的局内算法C-FF2,其绝对性能比为1/2,并证明了不存在绝对性能比大于1的算法.     

带启动重量的脆度装箱问题

讨论如下定义的带启动重量的脆度装箱问题：设有许多等长的一维箱子,给定一个物品集,每个物品有2个参数（脆度和重量）,若箱子是首次装入物品,则需要添加额外的启动重量,在装箱的过程中要保证每个箱子的启动重量和所装物品重量之和不能超过该箱子内物品的最小脆度,问怎样安排物品使所用箱子数最小．该问题是一个新的组合优化问题,来源于CDMA蜂窝通信系统中的信道分配．本研究给出了一个求解该问题的线性脱线算法C-NFI,分析了其最坏情况渐进性能比为2,并给出了相应的试验结果．     

带核元的带拒绝装箱问题

讨论了如下定义的带核元带拒绝装箱问题:设有许多等长的箱子,给定一个带核元的物品集,每个非核元有2个参数:大小和罚值.非核元物品可以放入箱子也可被拒绝放入箱子.如果某物品被拒绝放入箱中,则产生惩罚值,同时要求核元不允许被拒绝且每只箱子中所装核元个数不超过1,问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,在多处理器任务调度及内部互联网信息管理等问题中有着广泛的应用背景.提出了一个求解该问题的局外近似算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果.     

在线A形装箱问题: 模型及算法研究

A形装箱问题是由生产实际引发的一个新的数学模型,它是经典一维装箱问题的一种变形--每样物品有高度和半径两个参数.把装箱问题的经典算法推广到在线A形装箱问题,并分别从最坏情形分析与数值模拟两方面对算法进行了比较,得到了不同而且有趣的结果. 证明了 First Fit算法的渐近竞争比为2, 而其它在线启发式算法如Next Fit, Worst Fit, Best Fit(BF), Almost Worst Fit, Harmonic的渐近竞争比皆为无界; 通过数值模拟,在平均意义下BF的性质最好.     

事件反应仿真模型

介绍了事件反应仿真模型建模的特点 .以信号交叉口和公交停靠站范围内的事件反应模型建模为例 ,介绍了将车辆在多种约束条件影响下的逻辑分析过程进行情形划分的方法 .研究表明 ,清晰且符合逻辑的情形划分是事件反应模型准确描述各种交通现象的关键     

多目标优化的微分进化算法

将微分进化算法的应用范围从求解无约束单目标优化推广到求解一般情形的多目标优化.与传统优化算法及一般的进化算法相比,该算法特点在于直接将约束条件以及多目标性结合到进化算子中.算例表明,该算法是有效的.     

一种启发式的分布式最大独立集算法

从最大独立集问题的0-1整数规划数学描述入手,首先针对树图情形提出了一种基本的分布式树（Tree）算法,并证明该算法在树图情形下是最优的,然后将该Tree算法针对一般图情形进行了启发式的修正,得到一种新的分布式修正树（m-Tree）算法.理论分析表明,当图为树或二分图时,m-Tree算法可以简化为基于信用传播（BP）的分布式算法,是对BP算法的一种推广.仿真结果表明,对于树或二分图情形,m-Tree算法与BP算法都能收敛至最优解;对于一般图情形,m-Tree算法的收敛性能与权和性能均远优于BP算法,并且其权和性能接近最优解.     

求解组合拍卖问题最大值的贪婪算法

为有效解决组合拍卖问题,从基约束条件下,下模函数最大值问题的基本结论出发,逐步过渡到求解组合拍卖问题的贪婪算法,给出一种新的近似算法,分析了该算法的性能保证.该算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法结合,从而使其具有更好的性能保证,并从理论上证明了该算法的可靠性和有效性.     

2-Space Bounded Online Cube and Hypercube Packing

We consider the problem of packing d-dimensional cubes into the minimum number of 2-space bounded unit cubes. Given a sequence of items, each of which is a d-dimensional.d 3/ hypercube with side length not greater than 1 and an infinite number of d-dimensional.d 3/ hypercube bins with unit length on each side, we want to pack all of the items in the sequence into the minimum number of bins. The constraint is that only two bins are active at anytime during the packing process. Each item should be orthogonally packed without overlapping other items. Items are given in an online manner without the knowledge of or information about the subsequent items. We extend the technique of brick partitioning for square packing and obtain two results: a three-dimensional box and d-dimensional hyperbox partitioning schemes for cube and hypercube packing, respectively. We design5.43-competitive and 32/21 2d-competitive algorithms for cube and hypercube packing, respectively. To the best of our knowledge these are the first known results on 2-space bounded cube and hypercube packing.     

基于主成分因素分析法的展开型数据单维性检验研究

以拓广的等级展开模型(GGUM)模拟6种情形下的展开型数据,使用主成分因素分析法检验展开型数据的单维性.研究发现:在项目位置参数服从均匀分布且被试特质同质性较强的情形下,前2个因子的特征值比(E₁/E₂)小于3,其余情形的比值均大于3; 当被试样本特质同质性较弱时,特征值大于1的因子有3个,其余情形的因子有2个; 当测验项目位置参数服从两端分布时,项目2因素负荷图呈“括号”形; 当测验项目位置参数服从均匀分布时,项目2因素负荷图呈“马蹄”形.研究结果表明:能力反应数据单维性的检验标准并不适用于展开型数据,当从因子特征值比、项目负荷图判定展开型数据的单维性时,应考虑项目位置参数分布特点和被试样本特质的同质性程度.     

基于梯度调节规则的图像修复算法研究

当前较多图像修复算法采用单一大小样本块进行图像修复,不能适应图像不同差异的纹理丰富度变化,使得修复结果存在块效应以及模糊效应等不足。本文利用图像的梯度值,设计了基于梯度调节规则的图像修复算法。将图像的梯度信息引入优先权计算,联合数据项、置信度项目构造优先权计算函数,以计算优先修复块。利用图像的梯度变化率,建立梯度调节规则,用以调节样本块大小,适应不同的纹理丰富度。引入SSD(Sumofsquareddifferences)函数从源区域中寻找最优匹配块,实现图像修复。实验结果显示,所设计方法修复的图像具有良好的视觉效果。     

全球观测应力场应力取向数据的加权统计分析

论文将全球划分成一系列的5°×5°基本单元，通过对世界应力图计划中的全球应力指标数据进行加权系数法统计分析，计算了全球应力场在尺度为500km左右的平均应力取向；用Rayleigh检验检验了应力取向是否为随机分布；讨论了应力取向的统计分析和检验结果.统计结果显示考虑了加权系数情况下的有关统计结果相对比较符合实际，它提高了高质量数据在统计分析中的作用，并降低了观测数据呈随机分布特征的可能性.     

一种基于前缀广义表的快速间接关联挖掘算法

间接关联是数据挖掘领域中一种数据项之间的关联关系,可有效地应用于市场营销及Web日志分析等领域.现有的间接关联挖掘算法采用Apriori算法框架,需挖掘出所有的频繁项目集,因而存在挖掘效率低的缺陷.为此,提出了一种基于前缀广义表的快速间接关联挖掘算法,该算法无须生成所有的频繁项目集且仅须扫描数据库2遍,可有效提高间接关联的挖掘效率.     

小样本问题的算法比较

将不相关线性判别分析(ULDA)和零空间线性判别分析(NLDA)两种思想结合起来,提出了处理小样本问题的六种算法,并通过实验说明了这六种算法的分类有效性.     

一种基于协同过滤的电动汽车充电推荐方法

 基于大量的充电行为数据,建立电动汽车用户的充电兴趣模型,将用户感兴趣但未发现的最佳充电选择推荐给用户,实现充电行为有序引导是一个重要问题。本文针对电动汽车充电提出一种基于协同过滤算法的推荐模型,得出最佳推荐模型参数指标,充电10次以下的新用户采用基于用户的协同过滤算法,充电10次以上的老用户采用基于物品的协同过滤算法;基于用户的协同过滤算法的最佳邻居数和推荐列表长度均为3;基于物品的协同过滤算法的最佳推荐列表长度为4。指出负荷聚合商可以结合参与需求响应计划的情况,对推荐列表进行再优化,将与需求响应冲突的推荐信息过滤掉,从而实现有序充电控制。     

利用遗传算法的异步转移模式自愈环容量设计

自愈环是通信网的重要组成部分 ,自愈环的容量设计是双向自愈环规划的一个重要方面。该文以环路各段实际分配到的业务量总数尽可能平衡 ,从而环容量需求达到最小为优化目标 ,研究遗传算法在异步转移模式 (ATM)通信网双向自愈环容量设计中的应用 ,利用遗传算法的全局优化能力进行优化设计 ,解决了一个 NP(Nondeterministicpolynom ial)完全问题。针对节点对之间的业务量可分离和不可分离的两种情况建立了遗传算法的数学模型 ,并对不同规模的自愈环容量设计进行了计算机模拟。结果表明 :与其它方法相比较 ,该方法可以获得更好的设计结果 ,降低环容量的需求。