On-Line Scheduling of Unit Time Jobs with Rejection on Uniform Machines

The authors consider the problem of on-line scheduling of unit execution time jobs on uniform machines with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected. The objective is to minimize the total completion time of the accepted jobs and the total penalty of the rejection jobs. The authors propose an on-line algorithm and prove that the competitive ratio is 1/2 （2 W √3） ≈ 1.86602.     

非均匀类簇密度聚类的多粒度自学习算法

针对非均匀类簇密度聚类问题,从商空间粒度理论出发,提出一种多粒度自学习聚类算法 (multi-granularity self learning clustering algorithm, MSCA)。算法通过构造聚合树结构和定义粒度函数对问题逐层求解,并在每层聚合过程中根据聚合区间以自学习的方式动态确定聚合粒度,解决了传统聚类算法从非均匀类簇密度数据中无法得到不同层次的聚合特征且参数对经验依赖性过高的问题。理论和实验表明,MSCA算法可以发现任意形状类簇,有效处理噪声,并能发现关键聚合层,具有较好的计算复杂性。     

Application of improved equivalent edge currents in synthetic aperture radar imaging

Target modeling and scattering function calculating are important prerequisites and groundwork for the synthetic aperture radar (SAR) imaging simulation. According to the difficult problems that normal methods cannot calculate the scattering function of electrically large object under the condition to wideband, an effective method of improved equivalent edge currents is presented and applied to SAR imaging simulation for the first time. This method improves calculating velocity and has relatively high precision. The concrete steps of applying the method are given. By way of the simulation experiment, the effectiveness of the method is verified.     

求解约束优化问题的动量粒子群算法

为解决约束优化问题,提出使用双可行域吸引子策略改进动量粒子群算法。该算法只需初始种群中有一个粒子位于可行域内,随着搜索过程的进行,整个种群自动进入可行域内搜索。一方面,在搜索过程早期,由于可行域内粒子少,所有粒子移向相同的吸引子,整个种群迅速进入可行域内。另一方面,随着进入可行域粒子的增多,由于每个粒子使用距本身最近的可行域吸引子,较好地维持了种种群的多样性,避免早熟现象的发生,使算法具有较好的寻优性能。与国际上当前解决约束优化问题的粒子群算法在4个标准约束优化函数上测试比较,实验结果表明本算法取得的最优值要优于其它粒子群算法。

Abstract：

The strategy that two good positions in feasible region worked as attractors was incorporated into momentum particle swarm optimization algorithm in order to resolve constrained optimization problems. The resulting algorithm only requires that one of the initial particles is in the feasible region, and then all particles in the swam automatically move into the feasible region. On the one hand, in the early iterations few particles appear in the feasible region and hence all particles move toward the same attractors, so the particles soon enter into the feasible region. On the other hand, as the number of particles in the feasible region increases, each particle adopts the most near attractor so that each particle has different attractor. Therefore, the algorithm maintains the diversity of the population, alleviates the premature, and hence achieves good performance. The algorithm is compared with other particle swarm optimization algorithms on four benchmark functions. The experimental results show that the solution of the algorithm is better than that of others.     

一种截窗查询的多障碍物快速碰撞检测算法

依赖于地理信息系统的越野路径规划,由于存在大量分布不规律的环境障碍物,严重影响路径规划的计算速度,借鉴截窗查询的思想,给出了基于一维数据结构的矩形截窗查询算法,该算法有效减少了规划过程所需碰撞检测的障碍物个数,大幅提高规划速度,在环境障碍物动态更新的情况下,其性能优于区间树的截窗查询方法。

Abstract：

Path planning based on GIS is a fundamental problem in many applications. It is the main problem affecting the planning time because of the multi-obstacles in field environment. A novel rectangle windowing query method was proposed in order to improve the compute efficiency of collision free test. The method reduces the numbers of obstacles needed to test and speeds the planning process, and is more suitable with the dynamic environment of obstacles changing than the interval tree method.     

Multi-objective fuzzy particle swarm optimization based on elite archiving and its convergence

A fuzzy particle swarm optimization （PSO） on the basis of elite archiving is proposed for solving multi-objective optimization problems. First, a new perturbation operator is designed, and the concepts of fuzzy global best and fuzzy personal best are given on basis of the new operator. After that, particle updating equations are revised on the basis of the two new concepts to discourage the premature convergence and enlarge the potential search space; second, the elite archiving technique is used during the process of evolution, namely, the elite particles are introduced into the swarm, whereas the inferior particles are deleted. Therefore, the quality of the swarm is ensured. Finally, the convergence of this swarm is proved. The experimental results show that the nondominated solutions found by the proposed algorithm are uniformly distributed and widely spread along the Pareto front.     

Wigner-Ville distribution and cross Wigner-Ville distribution of noisy signals

The Wigner-Ville distribution （WVD） and the cross Wigner-Ville distribution （XWVD） have been shown to be efficient in the estimation of instantaneous frequency （IF）. But the statistical result of the IF estimation from XWVD peak is much better than using WVD peak. The reason is given from a statistical point of view. Theoretical studies show that XWVD of the analyzed signal can be estimated from XWVD of the noise-contaminated signal. The estimation is unbiased, and the variance is equal to that of noise. In this case, WVD cannot be estimated from W-VD of the noise-contaminated signal. Therefore, higher SNR is required when WVD is used to analyze signals.     

一种再制造物流网络设施定位优化方法

针对包含正向和逆向的再制造物流网络,提出一种由3种设施组成的2层物流设施定位优化方法,并给出0-1整数规划模型.基于遗传算法的全局搜索能力,全面考虑了正向流和逆向流及其它们之间的相互约束处理,避免了传统拉格朗日启发式算法中求上下限的繁琐计算过程.仿真实验表明提出方法的有效性.     

复杂性研究的计算方法

计算、算法与复杂性研究有着密切的关系,计算方法已经上升为一种复杂性研究的科学方法。计算复杂性使用的研究方法基本上是计算方法,算法复杂性研究的算法描述也是一种计算方法。计算方法还在复杂适应系统理论、人工生命等复杂性分支学科中扮演了重要的角色。计算方法不但在复杂性研究中有重要的作用,而且在一般方法论意义上也已经变得不可或缺,甚至走向了计算主义。     

基于自组装DNA计算的RSA密码系统破译方案

自组装DNA计算在解决NP问题,尤其是破译密码系统方面,具有传统计算机无法比拟的优势。采用DNA分子瓦编码信息,借助于分子瓦之间的粘性末端进行自组装,给出了乘法运算的实现方案。在此基础上,通过引入非确定性的指派分子瓦,提出了一种用自组装DNA计算破译RSA公钥密码系统的非确定性算法。通过创建数以亿计的参与计算的DNA分子瓦,在DNA计算能力允许的范围内,该算法可以并行地测试每个可能的因子,以高概率地分解整数。该方法最大的优点是充分利用了DNA分子瓦具有的海量存储能力、生化反应的巨大并行性以及组装的自发有序性。