Genetic algorithm-based heuristics for an open shop scheduling problem with setup,processing, and removal times separated

This report proposes a solution to the open shop scheduling problem with the objective of minimizing total job tardiness in the system. Some practical processing restrictions, such as independent setup and dependent removal times, are taken into account as well. The addressed problem is first described as a 0–1 integer programming model, and is then solved optimally. Subsequently, some hybrid genetic-based heuristics are proposed to solve the problem in an acceptable computation time. To demonstrate the adaptability of these heuristics, some performance comparisons are made with solutions provided by running either a mathematical programming model or certain classic meta-heuristics such as genetic algorithm, simulated annealing, and tabu search in various manufacturing scenarios. The experimental results show that the hybrid genetic-based heuristics perform well, especially the DGA. However, these heuristics require some more additional computations but are still acceptable.     

Replica Exchange Light Transport

We solve the light transport problem by introducing a novel unbiased Monte Carlo algorithm called replica exchange light transport, inspired by the replica exchange Monte Carlo method in the fields of computational physics and statistical information processing. The replica exchange Monte Carlo method is a sampling technique whose operation resembles simulated annealing in optimization algorithms using a set of sampling distributions. We apply it to the solution of light transport integration by extending the probability density function of an integrand of the integration to a set of distributions. That set of distributions is composed of combinations of the path densities of different path generation types: uniform distributions in the integral domain, explicit and implicit paths in light (particle/photon) tracing, indirect paths in bidirectional path tracing, explicit and implicit paths in path tracing, and implicit caustics paths seen through specular surfaces including the delta function in path tracing. The replica‐exchange light transport algorithm generates a sequence of path samples from each distribution and samples the simultaneous distribution of those distributions as a stationary distribution by using the Markov chain Monte Carlo method. Then the algorithm combines the obtained path samples from each distribution using multiple importance sampling. We compare the images generated with our algorithm to those generated with bidirectional path tracing and Metropolis light transport based on the primary sample space. Our proposing algorithm has better convergence property than bidirectional path tracing and the Metropolis light transport, and it is easy to implement by extending the Metropolis light transport.     

<Emphasis Type="Italic">New-Age</Emphasis>: A Negative Bias Temperature Instability-Estimation Framework for Microarchitectural Components

Degradation of device parameters over the lifetime of a system is emerging as a significant threat to system reliability. Among the aging mechanisms, wearout resulting from Negative Bias Temperature Instability (NBTI) is of particular concern in deep submicron technology generations. While there has been significant effort at the device and circuit level to model and characterize the impact of NBTI, the analysis of NBTI’s impact at the architectural level is still at its infancy. To facilitate architectural level aging analysis, a tool capable of evaluating NBTI vulnerabilities early in the design cycle has been developed that evaluates timing degradation due to NBTI. The tool includes workload-based temperature and performance degradation analysis across a variety of technologies and operating conditions, revealing a complex interplay between factors influencing NBTI timing degradation.     

基于免疫克隆退火算法的P2P路由算法

为改善P2P网络中传统路由算法存在的不足,结合免疫克隆算法和模拟退火算法的优点,提出一种基于免疫克隆退火算法的P2P路由算法。该算法充分考虑节点间延迟、带宽和费用等差异。实验结果表明,该算法能有效提高路由效率,减少路由延迟,整体性能优于其他路由算法。     

基于和声搜索和模拟退火的混合算法解决TSP问题

和声搜索是一种新的启发式优化算法,算法模拟了音乐创作中乐师们凭借自己的记忆,通过反复地调整乐队中各乐器的音调,最终能达到一个美妙的和声状态的过程.针对和声搜索算法容易陷入局部最优的缺陷,将其与模拟退火算法结合,得到了两种混合算法.实验表明混合算法针对TSP问题具有较高的求解质量.     

基于九轴MEMS定位系统误差分析与补偿算法研究

基于九轴MEMS定位系统,对由陀螺仪零偏造成的位移平面偏转误差进行分析与补偿。通过实验与推导,首次给出偏差的定量分析和误差传播的数学模型。为估计偏差,设计了一种新的状态向量中仅包含陀螺仪零偏的、简化扩展卡尔曼滤波（ SEKF）技术,克服了无加速度计辅助条件下的偏差估计问题,降低了计算量,能够很好地满足位移实时估计需求。硬件实验证明：经过偏差补偿的九轴MEMS定位系统,能够准确估计有限范围内周期性运动的位移,幅值定位精确度达到90%。该系统可用于无人机、机器人定位等领域。     

基于受约束偏置的概率矩阵分解算法

在概率矩阵分解(PMF)模型拟合之后,评分较少用户的特征趋近于先验分布的平均值,导致对其评分预测接近物品的平均评分.受约束概率矩阵分解(CPMF)未考虑到不同评分系统的整体差异以及数据集内部用户与物品存在的固有属性.针对以上问题,提出将传统矩阵分解中的用户和物品偏置项以及全局平均分结合受约束概率矩阵分解来建立新的矩阵分解算法.算法利用整体平均分衡量不同评分系统,在采用偏置来表示用户以及物品之间相互独立的属性的同时,引入约束使行为相近用户拥有相近的用户偏置,从而提高预测精度.在两个真实数据集上的实验结果表明,该算法相对于PMF和CPMF算法预测精度得到了提高.     

在中学排课问题中实用的模拟退火算法应用

针对中学排课问题,提出了一种分阶段的模拟退火算法解决方案.中学排课问题难点主要在于如何解决课表中存在的大量冲突以及如何优化课表.初始化随机生成一张带有冲突的课表,经过算法第一阶段,人工干预异化解结构,使课表可行;算法第二阶段引导性的改变课表结构使课表满足通用的软约束条件;算法第三阶段采用启发式随机邻域异化操作,变异课表,产生更优解.为了满足实际生产环境中对课表多元化的需求,在UI界面中提供可以手动调节课表机制.经过实验发现,改进后的模拟退火算法在解决中学排课问题时收敛速度更快,运行效率更高,并且在迭代次数较少的情况下,也能产生可行解.     

开发可统计任意密码子用法的软件BestCodon

密码子偏好是自然现象,分析密码子的用法可以优化表达基因,即密码子优化,从而调节目的基因在特定宿主中的表达水平。现有密码子用法分析软件多数只限于单个密码子,适用于密码子对和密码子三联体的较少见。本文提出1种可统计任意密码子用法的软件结构,开发出1个密码子用法统计软件BestCodon,拥有序列检查和密码子用法统计2个模块。检查模块可代替人工校对,剔除输入序列中非规范字符,为后续分析提供正确的、符合规范的数据。统计模块根据用户指定的密码子组合类型,结果返回特定的密码子用法表。本文还探讨序列检查和密码子用法统计中计算机的运算特性,结果表明该软件检查1条长达150000 bp的序列仅耗时约0.2 s,而从中统计密码子十联体的用法仅耗时约0.1 s。     

A Constraint-Based Approach for Deriving 3-D Structures of Cyclic Polypeptides

This paper presents an hybrid algorithm for deriving 3-D structures of cyclic polypeptides. The algorithm combines constraint-based techniques with the most widely used methods for non-cyclic polypeptides. The empirical results demonstrate that the proposed hybrid algorithm outperforms traditional methods especially with respect to running times.