基于贪婪算法的自动排课表系统的研究与实现

排课表问题是一个具有不确定性、NP完全的组合优化问题.为了能够有效地解决排课表问题,提出了一种基于二分查找策略的贪婪算法来解决限制条件非常复杂的排课表问题.该算法把教室的可容纳人数以及可用的时间综合起来看成是一种可用的资源,对资源按照二叉排序树的形式进行排序,并把要申请教室的课程看成是资源的索取者,通过对资源树的搜索遍历,寻找合适的教学节点.在排课表过程的效率与排课表结果的可用性中取得了一个较好的平衡点.     

最小顶点覆盖问题的闭环DNA算法

提出了闭环DNA计算模型的基本概念及其基本生化实验,并给出了解决最小顶点覆盖问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造顶点覆盖补集的构想;再通过电泳实验得到最小顶点覆盖的补集,由补集得到最小顶点覆盖。这使得算法的设计独特而新颖;由于算法仅用到基本的生化实验,这使得算法的实现简捷、可靠。     

基于闭环DNA计算的最大独立集问题的算法

提出闭环DNA计算模型及其基本生化实验,给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造所有最大独立集的构想,即通过多次删除实验使顶点集合逐步满足独立集的要求,最后达到最大独立集。该方法使得算法的设计简单明了。算法仅用到基本的删除实验,实现简捷、可靠。     

SBR 污水生化处理系统的最优控制及改进

针对序批式反应器污水处理工艺，提出一种以排水质量指标为约束条件，以能量消耗最小为日标的最优控制方案．由于生化过程机理复杂，导致这个最优问题求解困难．所构造的解法是首先建立通用的序批式反应器模型；然后借助仿真工具试差求取次优解．为解决搜索求解计算量大的问题，进一步结合进退法提出了一种改进的优化算法，显著提高了求解效率。     

基于闭环DNA的指派问题算法

给出了闭环DNA计算模型及其生化实验。用闭环DNA计算模型设计出了指派问题的DNA算法。首先对决策变量进行二维DNA编码来存放决策变量和效益值，然后通过有目的的终止技术和删除实验得到指派问题的全部可行解，最后通过电泳实验和检测实验获得最优指派问题的最优解。举例说明了算法的可行性。最后，为减少DNA编码数量和缩短DNA编码的码长，讨论了算法的两种改进方法。     

基于自组装模型的最大团问题DNA计算算法

DNA计算在解决NP完全问题时,有着传统图灵机无法比拟的优势.但是随着DNA计算研究的不断深入,传统DNA计算模型显现出杂交错误率和生化操作复杂性过高的缺点.如何提高DNA计算结果的准确性在DNA计算研究中日显重要.针对NP完全的最大团问题,引入DNA自组装模型,提出了一种求解最大团问题的DNA计算算法.算法通过减少实验的操作步骤数,以降低生化解的错误率,给出了DNA分子的编码方案及结果检测的实验方法.算法设计的tiles种类为(O)(n+|E|),生化操作复杂性为(o)(1),其中n为图的顶点数,|E|为边数.与求解最大团问题的其他DNA算法的对比分析表明,本算法不仅明显提高了生化解的准确性,且算法的生化实验复杂度低,具有良好的实验操作性.     

基于立方体染色的排课表模型

根据立方体染色思想,建立排课表模型,引入关联锁原理,将排课表约束条件转化为立方体点线面关系,增强该模型的收敛性,从而更好地解决排课问题。分析结果表明,在教师、课程、学生等信息已知的情况下,该模型可给出教学资源消耗的最小值,达到合理利用教学资源的目的。     

基于DNA进化算法求解工件尺寸不同的单机批调度问题

工件尺寸不同的批调度问题兼具古典调度和批调度的性质,单机环境下该问题的制造跨度为NP完全问题.本文提出一种改进的DNA进化算法对单机问题的制造跨度进行优化,引入分裂、水平选择、变异、垂直选择四种算子,对其中的垂直选择算子做了重新设计,采用概率选择机制对变异个体进行选择,避免进化过程陷入局部最优.在解码时,采用Batch First Fit算法对进化过程产生的解作分批处理.实验中对各类不同规模的算例均进行仿真,结果表明改进的DNA进化算法的有效性.     

基于闭环DNA模型的八皇后问题算法

给出了闭环DNA计算模型及其基本生化实验,提出了基于闭环DNA的求解八皇后问题全部可行解的DNA算法,分析了算法的实现步骤及其实现方式并得到了全部的可行解。最后讨论了算法的复杂性。     

基于粘贴模型的图顶点着色问题的DNA算法

为了用生化实验的方法解决图的顶点着色问题，基于粘贴模型的巨大并行性，将着色问题转化为可满足性问题，提出一个基于粘贴模型的DNA算法。通过一个实例给出了操作步骤，并对生化反应过程进行了模拟，得出具体的着色方案，证明了该算法的可行性。     

基于h-距离的DNA编码序列设计

针对DNA编码序列设计问题,将其转换为带约束的多目标优化问题,在单链DNA集合中引入h-距离,构造了DNA序列间的共享函数,应用小种群遗传算法,对DNA编码序列设计问题进行求解。与已有结果比较,算法可以得到更好的DNA序列且计算效率较高。算法可用于DNA计算中编码序列的具体设计。     

旅行商问题的闭环DNA算法

旅行商问题TSP是NP完全问题,在工程实践中有着广泛的应用,利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式,与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA 计算模型及其改进;随后提出了一种基于改进的闭环模型求解TSP问题的算法,并对算法的实验过程进行了详细的描述;最后运用该算法解决了一个小规模的TSP问题算例,结果表明,该算法能在较低的时间复杂度内有效地解决TSP问题。     

基于地理区域的Ad hoc网络组密钥管理方案*

由于Ad hoc网络拓扑结构的动态性、无线传输媒体的开放性等特点,使得网络容易受到各种安全威胁。提出一种新的密钥协商算法MGDH,并且结合MGDH提出一种可扩展的基于地理区域的组密钥管理方案(RGKM)。方案中无须可信赖的第三方,从而解决了单点失效问题,通过引入反向路由的思想,在保证安全性的同时减少了网络的通信量,有效实现了网络的能量平衡。     

基于Hadoop的聚类算法实现个性化推荐

对于具有海量信息的个性化推荐问题。K—means聚类算法的传统实现方式已不能快速准确地满足要求。基于目前最为流行的开源云计算平台Hadoop及分布式计算框架MapReduce,实现K—means聚类算法的并行化。给出该算法的具体实现,实验表明能够较好地解决时间瓶颈问题。     

Sparse group lasso and high dimensional multinomial classification

The sparse group lasso optimization problem is solved using a coordinate gradient descent algorithm. The algorithm is applicable to a broad class of convex loss functions. Convergence of the algorithm is established, and the algorithm is used to investigate the performance of the multinomial sparse group lasso classifier. On three different real data examples the multinomial group lasso clearly outperforms multinomial lasso in terms of achieved classification error rate and in terms of including fewer features for the classification. An implementation of the multinomial sparse group lasso algorithm is available in the R package msgl. Its performance scales well with the problem size as illustrated by one of the examples considered—a 50 class classification problem with 10 k features, which amounts to estimating 500 k parameters.     

一种加群Z上离散对数问题的DNA计算算法

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用。研究一种加群Zp+上离散对数问题的DNA计算算法。算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成。其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间。本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数)。最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性。