基于赋权图上优化问题的dna计算方法研究

《基于赋权图上优化问题的dna计算方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学博士学位论文赋权图上优化问题的DNA计算方法研究姓名：韩爱丽申请学位级别：博士专业：计算机软件与理论指导教师：朱大铭20080405山东大学博十学位论文摘要在赋权图上优化问题的DNA计算方法研究中，权值的DNA编码方法是求解问题的关键。本文讨论了中国邮递员、旅行商、最大权团、最小生成树等赋权图上经典优化问题的DNA计算方法，改进了它们原有DNA计算模型中的权值编码方法，给出TN用改进DNA编码方法求解的新DNA算法。我们通过设计赋权无向图的广义边图给出了中国邮递员问题的一种DNA编码方法及计算模型，通过设计赋权图的相对长度图给出了旅行商问题的一种DN

2、A编码方法及计算模型，通过选取DNA序列的最佳逆补比对给出了最小生成树问题的基于逆补比对的一种DNA编码方法及计算模型，并通过改进已有的DNA编码方法给出了最大权团问题、顶点覆盖问题及o／1背包问题的DNA计算模型。我们给出的DNA计算模型提高了DNA计算中数值表示和处理能力。具体研究工作如下：对于中国邮递员问题，我们首先提出了广义边图的概念，然后设计了一种新的基于广义边图的DNA编码方法及DNA算法。所提出的广义边图DNA编码方法利用边到点映射把赋权图中的边映射为顶点，构造给定赋权图的广义边图，使得赋权图中的边权值转换为广义边图中顶点的权值，从而利用顶点的

3、编码长度表示权值，使得权值的处理变得更容易。具体地说，对于任一赋权连通无向图G=(形D，首先通过边到点映射把图G转换为广义边图G’=(矿，F)，其中每个顶点vf，∈矿对应于图G的一条边e，。若图G中边e，与ej邻接，则在G’中顶点Ⅳ和v／之间加一条无向边：若图G中vf的度数为奇数，则在与M关联的边对应的G，的顶点上添加自环。用于编码图G’中顶点v。7的DNA串s，的长度等于图G中边e，的权值。用于编码图G，中边e扩k(v，，，Ⅳ)的DNA串％为曲的后半部分与s，的前半部分并置后的逆补。这种编码方法提高了用DNA计算求解赋权图上具有边权值的优化问题的数值表示和

4、处理能力。对于旅行商问题，我们首先提出了权值序号和相对长度图的概念，然后设计了一种基于相对长度图的DNA编码方法和一种改进的DNA编码方法，并给出了相应的DNA算法。对于任一赋权连通无向图G=(一目，所提出的相对长度DNA编码方法利用权值的序号和相对长度图代替权值本身来对权值进行编码。由于该编码方法中用于编码权值的DNA串的长度只与权值的序号有关，与权值IIJ东大学博+学位论文本身无关，因此它能直接处理整数或实数权值，甚至很小或很大的权值，并且所获得的最优解不与DNA串的长度成正比，这就使得这种编码方法能处理一个较宽范围的权值。所提出的改进DNA编码方法用两

5、条不同长度的DNA串去编码每条边，其中较长DNA串由首段、权值段及尾段三部分组成，较短DNA串是较长串权值段的逆补。该编码方法是对先前的权编码方法的一种改进，改进后的编码方法生成的是稳定的DNA双链而不是单双交替的DNA串，因而更容易生成问题的最优解。对于最小生成树问题，我们设计了一种基于顶点识别码的DNA编码方法以及一种基于DNA序列的逆补比对的DNA编码方法，并给出了相应的DNA计算模型。由于非线性的最小生成树不能直接用线性的DNA串表示，因此不能直接给出最小生成树问题的基于DNA计算基本操作的DNA编码方法及DNA算法。对于任一赋权连通无向图G=(K目

6、，所提出的基于顶点识别码的DNA编码方法用一个长度为，=max{lloganl，6)的识别码一去编码图G的每个顶点M，用一个长度为2p=2×max{w帕，)的DNA串Sg去编码图G的每条边e扩，其中呀的长度为w盯的前部分标记为s。盯l，长度为w{：，的后部分标记为s，．．蛇，并对图G的任意两条相邻边P{：『和饥，增加一个长度为W扩毗的DNA串J。批=砌(钆蛇s叫)作为附加码。基于所提出的DNA编码方法，我们给出了最小生成树问题的一种基于顶点识别码的DNA算法，该算法首先获得对应于最小生成树的Euler回路，然后把Euler回路转化为最小生成树。在此基础上，针

7、对DNA双链中碱基之间的互补／非互补、同向／!IiE同向关系，提出了DNA序列的补比对和逆补比对的概念，给出了DNA序列的补比对和逆补比对的计分方法，并利用DNA序列的逆补比对的计分方法给出了最小生成树问题的一种新DNA编码方法及DNA算法。对于任一赋权连通无向图G=(K司，v，∈乃e∥∈E，1≤i,j≤刀，其中边e扩上的权值为w玎，用一个长度为，=max{Il094nl，6}的识别码n去编码每个顶点'，，，用一个长度为印=2×max{w∥，，)的DNA串s矿去编码每条边e扩，然后计算Swijl，‰归，rj的逆补比对‰卵，aswflc2，嘶，并选取DNA串s

8、缈=Lower(a删2l仅力+Lower(a,。#x