最小顶点覆盖问题的DNA分子算法

最小顶点覆盖问题是找给定图G中覆盖每条边的最小顶点子集,这个问题即是一个著名的NP 完全问题。给出了基于分子生物技术的图的顶点覆盖问题的DNA算法。算法的关键是数学问题到DNA链的映射,对图中的顶点进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离。依据分子生物学的实验方法,提出的算法是有效和可行的。最后指出了该算法的优点、存在问题及下一步的研究方向。     

TSP的DNA计算算法

提出了TSP的DNA算法,共有六个步骤:首先将TSP转化为有向图的经过所有点最短闭链问题并进行编码;其次从某点开始用有目的的终止技术——芯片技术、保护基技术以及杂交实验——得到起点和终点相同的DNA链;再用分离实验产生经过所有顶点的DNA链;然后用电泳实验取出链长最短的DNA链;最后用标记实验解读最优解集。讨论了算法的复杂性并用实例说明了算法的有效性。还讨论了推广的TSP——推销员在城市有停留时间——的算法的变化——只需改变编码方式,以及实验的简化问题。最后说明了本算法提出的一种新的合成技术——有目的的终止技术的优势和前景。     

背包问题的闭环DNA算法

提出了闭环DNA分子的结构多样性,即闭环DNA分子在同一个位置上具有不同的DNA序列.提出了双约束的整数规划背包问题闭环DNA算法,即对变量取值进行DNA编码并形成所有可能解;用批接入实验、电泳实验和批删除实验筛选出可行解,用批接入实验、电泳实验得到最优解;通过检测实验输出所有最优解.由一个算例说明算法的有效性.针对减少DNA编码和内切酶数量的问题改进了算法;对有特殊要求的背包问题提出了解决方法.     

最优指派问题DNA算法

对求最小值的最优指派数学模型,设计并实现了DNA计算算法。首先经过特殊的DNA编码将二维的决策变量和二维的效益值编入DNA序列中;然后通过杂交实验和分离实验得到指派问题的全部可行解;最后通过电泳实验和检测实验获得最优指派问题的最优解。证明了算法的复杂性并举例说明了算法的可行性。分别给出了求最大值的最优指派问题和人数与工作数不等的最优指派问题的处理方法。     

基于灰色关联分析的分层模糊神经网络

为解决“模糊规则爆炸”问题,提出一种基于模糊神经网络从试验样本抽取模糊规则的方法。首先,根据灰色关联分析的结果,将输入变量进行两两组合建立分层模糊子系统。其次对每个模糊子系统设计分层参数、结构优化算法。在权值学习过程中,模糊进化规划与分层方法相结合,网络的各层权值独立优化,并且各层权值优化问题简化为二次型问题,降低了权值优化过程中的计算复杂性。最终能够实现整个模糊神经网络的分层优化,各层神经元单独训练且训练结果互不影响。与常规的前向进化神经网络方法相比较,该方法通过对神经元的部分解群体的进化,缩短了个体的编码长度,显著地减少了计算量。同时这种方法不但能够很大程度上简化适应值的计算,更重要的是能够降低适应值空间的复杂性,从而能够加速进化算法收敛到全局最优点。     

图顶点着色问题的DNA粘贴算法

利用DNA粘贴模型的巨大并行性,从图顶点着色问题的本质出发,先把着色问题分解成顶点独立集问题和顶点划分问题并给出这两个问题的DNA粘贴算法,然后调用这两个算法解决了图顶点着色问题。实例证明DNA粘贴算法在理论上可以实现的。     

0-1规划问题的闭环DNA算法

提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项系数和检测标记进行五组DNA编码并形成所有可能解;再利用接入实验、电泳实验和删除实验筛选出可行解,进而得到所有最优解;最后通过检测实验输出实验结果。给出了算法的正确性的证明并讨论了算法复杂性,给出一个算例说明了算法的有效性。对算法进行了改进,改进后的算法适用于可以含有负数的实数系数0-1规划问题。     

遗传BP网络转速辨识器的设计及在DTC中的应用

为实现无速度传感器直接转矩控制,有时采用神经网络转速辨识器,但前馈神经网络结构难以确定,运用BP算法时又极易陷入局部解。将遗传算法和BP算法结合,采用混合编码的遗传算法优化神经网络的结构及网络初始权值,再利用BP算法对网络权值进行精确调节;这种将遗传算法与BP算法相结合的GA BP算法,实现了遗传算法的全局搜索能力与BP算法的局部寻优性能的互补结合。将所设计的神经网络转速辨识器运用到直接转矩控制系统当中,利用MATLAB/SIMULINk实现无速度传感器控制系统的仿真实验结果表明,该算法具有良好辨识效果。     

停机位分配问题的顶点着色模型及算法

给出了停机位分配问题顶点着色模型及其分解算法.通过改良一种时间冲突算法,构建了航班使用停机位的时间冲突集合.以"先到先服务"原则为基础,把停机位分配问题转化为顶点着色问题,并建立了相应模型.利用笔者独创的分解算法,停机位的作业能力可得到改善.算法的计算复杂度为O(n2).该算法的特点在于:1)将顶点、颜色划分为若干个不同等级的集合;2)将顶点按照所属集合的等级、度进行分解,得到顶点的分解序列.在用一种颜色ck(1≤k≤K;K是可用颜色数)给顶点着色时,优先给这样一个顶点着色:该顶点能被着ck色,且其分解序列号最大.最后将该算法应用于一个算例,得到了最优解.     

基于改进花朵授粉算法的风电预测神经网络模型北大核心CSCDCSSCI

针对常规Elman神经网络容易陷入局部最优、泛化能力不足等缺点,提出一种将花朵授粉算法和Elman神经网络相结合的风电预测新方法。采用逻辑自映射函数构建混沌序列,将混沌变量映射到问题的解空间,使缺乏变异机制的花粉粒集具有较强的自适应能力,有效地防止算法后期最优解趋同的现象;利用变换系数动态收缩自变量范围,降低算法陷入局部极值的概率,使算法的搜索效率得到有效提高。结合预测需求和网络特征,对花粉粒参数进行编码,确定Elman神经网络的最佳权值和阈值。算例分析表明,所提出的风电预测神经网络模型在保证概率预测精度的条件下能达到较好的预测效果,为短中期风电功率预测提供了一种可行的解决思路。     

赋权Hamilton路的DNA计算模型

DNA计算是一种基于生化反应的新型计算方式 ,目前已成为一个非常热门的研究领域。首先简单介绍了DNA分子的结构、计算机理及实现方式。然后 ,在Adleman工作的基础上 ,给出了赋权 (有向与无向 )型Hamil ton路问题的DNA计算模型。通过权值的转换方式 ,指出此模型对于任意实数权值的赋权图均适应。最后 ,指出了该模型存在的问题及进一步研究的方向。研究结果进一步证实了DNA计算的可行性。     

Pollard p-1因子分解的DNA计算机改进算法

如何有效地对大整数进行因子分解,是数学上的一个难题.RSA密码体制的安全性正是基于此困难问题.利用DNA计算机超大规模的并行运算能力和数据存储能力,提出一种基于分子生物技术的因子分解问题改进的DNA计算机算法.以因子分解的Pollardp-1算法为基础,设计了基于DNA计算的平方-乘算法以及求取最大公因数的欧几里得子算法,仿真实验结果表明了算法的可行性和有效性.     

利用多群体DNA遗传算法求解线性规划问题

针对经典遗传算法存在的问题 ,提出了多群体DNA遗传算法。该方法在经典遗传算法的基础上 ,通过借鉴生物学及社会学 ,引入了多群体及DNA片断等概念 ,并提出迁移与自适应变异算法 ,可以提高遗传算法的有效性与收敛性。为了验证算法的有效性 ,将该算法应用于线性规划问题的求解。在求解过程中 ,首先利用熵障碍对偶方法对原问题进行转换 ,然后使用多群体DNA遗传算法对转换后的目标函数进行求解。仿真结果表明 ,该方法具有良好的全局搜索能力和较快的收敛速度。以上工作为解决大规模线性规划问题的求解提供了全新的思路和方法 ,对遗传算法应用的发展具有重要意义     

基于遗传算法的ATM网络中VCC路由选择方法

针对遗传算法强大的全局寻优和并行处理能力 ,提出了一种改进的遗传算法调度ATM网络动态路由的新算法。综述了使用遗传算法进行通信网络节点选择的问题 ,指出了原有算法进行遗传算法优化时存在的不足 ,并提出一种新的基于动态惩罚的解决策略 ,其思想是在进化的过程中 ,逐渐减小对可行解惩罚的力度 ,使网络向可行解逼近。通过简单模型的仿真 ,验证了动态惩罚策略的可行性和有效性。     

飞机排班航班串编制模型及算法研究

分析了飞机排班计划的编制流程,主要针对其中的航班串编制问题进行了深入研究,建立了航班串编制VRP模型,模型不仅考虑了航班时间、出港到港机场衔接之间的约束,而且还考虑了客流量、维修基地机场的约束。为了求解模型,构造了一种基于单亲遗传算子的免疫算法,采用适合模型的抗体编码方式,并使用单亲遗传算子生成新抗体。应用实际的航班信息进行航班串编制的仿真研究结果表明,文中的模型和算法切实可行。     

Membrane-inspired quantum shuffled frog leaping algorithm for spectrum allocation

To solve discrete optimization difficulty of the spectrum allocation problem,a membrane-inspired quantum shuffled frog leaping(MQSFL) algorithm is proposed.The proposed MQSFL algorithm applies the theory of membrane computing and quantum computing to the shuffled frog leaping algorithm,which is an effective discrete optimization algorithm.Then the proposed MQSFL algorithm is used to solve the spectrum allocation problem of cognitive radio systems.By hybridizing the quantum frog colony optimization and membrane computing,the quantum state and observation state of the quantum frogs can be well evolved within the membrane structure.The novel spectrum allocation algorithm can search the global optimal solution within a reasonable computation time.Simulation results for three utility functions of a cognitive radio system are provided to show that the MQSFL spectrum allocation method is superior to some previous spectrum allocation algorithms based on intelligence computing.     

Closed circle DNA algorithm of change positive-weighted Hamilton circuit problem

Chain length of closed circle DNA is equal. The same closed circle DNA's position corresponds to different recognition sequence, and the same recognition sequence corresponds to different foreign DNA segment, so closed circle DNA computing model is generalized. For change positive-weighted Hamilton circuit problem, closed circle DNA algorithm is put forward. First, three groups of DNA encoding are encoded for all arcs, and deck groups are designed for all vertices. All possible solutions axe composed. Then, the feasible solutions axe filtered out by using group detect experiment, and the optimization solutions are obtained by using group insert experiment and electrophoresis experiment. Finally, all optimization solutions are found by using detect experiment. Complexity of algorithm is concluded and validity of DNA algorithm is explained by an example. Three dominances of the closed circle DNA algorithm are analyzed, and characteristics and dominances of group delete experiment axe discussed.     

最短路问题的闭环DNA算法

提出了不等长闭环DNA分子的概念,由此推广了闭环DNA计算模型。给出了固定端点的最短路问题闭环DNA算法,该算法首先对每条弧进行了三组DNA编码,再用有目的的终止技术合成固定端点的所有链,然后通过接入实验和电泳实验得到最短路,并通过检测实验输出所有最短路径。得出了算法的复杂性,为说明算法的有效性给出了一个算例。最后讨论了最短路问题闭环DNA算法在变权网络、自由终点或固定中间点的最短路问题中的应用,并给出了相应的解决方法。由此说明该算法具有广泛的适应性。