（计算机应用技术专业论文）加权分治技术在set+packing问题中的应用与研究.pdf

摘要 n p 一完全理论是算法研究方面的重要的基本理论，它在计算机、 电气工程和运筹学方面都有重要的地位。本文主要以算法技巧为着眼 点来研究此类问题，希望在解决方式上有新的突破。 加权分治技术由f vf o m i n 首先提出，是在分析算法中产生的一 项新技术，该方法基于选择不同的量来描述分支子问题的大小，以求 从中得到在最差情况下最好的时间复杂度。在加权分治技术中采用伪 凸规划技术对回溯算法来确定各个权值，使得时间复杂度最小。我们 也给出了一种新方法，通过进化算法求解赋权函数以求得最小上界， 同样可以来确定权值，且比前种方法更加简单 根据加权分治技术的应用范围选定s e tp a c k i n g 问题进行深入研 究，依据所研究问题的差异。将s e tp a c k i n g 问题分成5 类，并给出 了具体的定义。在此基础上，分别介绍了求解这5 类问题的相关算法， 着重分析和比较了参数算法中所运用的各项技术，并提出了该问题算 法研究的发展方向。 对于g s p 问题本文给出了一个简单的递归算法，并利用加权分 治技术深入分析了其时间复杂度。以前对于g s p 问题转换成独立集 问题来求，并没有考虑到符号全集的大小，我们的算法将符号全集的 大小引入进来，通过应用加权分治技术来分析包含砧个子集且符号全 集为的s e tp a c k i n g 问题的一个简单的递归算法，得到其精确算法 的时间复杂度为d + ( 1 1 6 8 c + ) ，当n 0 ( 3 2 0 0 0 3 ) 代皱涪、着色法 2 9 】 o 0 2 6 7 ：懒)棱心化、着色法 3 0 0 ( 2 5 2 50 ( 1 6 3 ) 分治法、着色法 【3 l 】o ( 2 5 2 0 ( 1 2 8 1 着色法，分治法 f 3 2 1d ( 4 6 1 3 着色法、动态规划 从表2 - 1 中可以清楚看到很多算法中运用了多种技术的结合，我们主要根据 该算法在哪些关键技术上的突破来分为以下五部分 2 3 1 局部贪婪法 文献惭如首先通过在时间复杂度o ( m n ) t h 构建一k - 岫a lt r o tp a c k i n gm o ， 当i m o p 或者i m o l ! d m 可直接返回“y e s ”或者。n o 剩下只需要对肼n g h b e 生 情况进行分析若存在一个七大小的s e t p a c k i n g ，则该s e t p a c k i n g 中的每个元组 至少包含m o 中的一个元素，接下来可用穷举法找出1 个元素，进而形成k 个偏 集，偏集表示在该集合中有不超过k - 1 个元素用“+ ”表示 为了使穷举更加有效，并引入生成集概念 存在s e t p a c k i n gp 和集合芦，若p 中每个元组中都有元素在集合芦中，则芦 是p 的一个生成集 生成集的数日可通过递归式来求得，假设i m o l = h ，设d o , k ) 为m o 中包古k 个 元素的生成集的数目。有以下递归式 如果h k 或者m k k 或者k s od 魄盼= o 如= 果m h 或d 魄炉l 。佴铲喜p ) 狮一t t 1 ) s 杰叭f 。m ，l b * l 2 砖 偏集中其他的元素通过局部贪婪法进行猜点替换，若进行了一部分后无法继 续则需要对新加入的元素进行穷举后再用局部贪婪法，这部分的时间复杂度通过 s t i r l i n g s 公式近似后这一部分操作的时间复杂度为 o ( 艇m - 1 x ( * l r l e m 2 ) k + m - 2 ) l - 1 ( k z + k m n ) ) 经过以上3 步得到其整个算法 的总时间复杂度为o ( 砬暇m 1 ) ( 西一l 广1 屉唧【i 伽- 2 卜l 】( 矿十b ”n ) 】+ m ) 。特别 是在m = 3 时t 也就是3 - s dp a c k i n g 问题的时问复杂度为d + ( ( 5 7 k ) k n ) ( b 3 3 8 4 7 4 ) ， 硕士学位论文第二章s e tp a c k i n g 问题的研究进展 2 3 2 代数法 其主要思想是将s e tp a c k i n g 的实例转化成代数表达式来求解1 2 s i 。如存在 c = s l i 焉 ，u = u s i 且肛叫，硒) 是表示元组岛中所包含的元素，令 肛( yr ( 研广，b 实质上是一代数多项式的k 次方，而该代数多项式中的每个因 蔷 子其实是s e tp a c k i n g 中对应元组中的元素。通过k 次方后，若其表达式中仍有 因子中所有元素的幂指数都为1 ，则表明至少存在一个k 大小的s e tp a c k i n g ，其 时间复杂度的分析是针对代数式，为o i h 胪约。这是对s e tp a c k i n g 问题是否存 在k 个大小的s e t p a c k i n g 的判断，若要找出对应的k 个元组，需对r 个元组逐一 进行判断，因此总时间复杂度为0 ( h 2 2 ) ，可以推得3 s c tp a c k i n g 的确定性算 法的时间复杂度至少为0 ( 3 2 0 0 0 n ) 2 3 ，3 核心化法 3 - p s p 和3 d - m a t c h i n g 问题在定义和求解方法上都十分类似只是约束条件 上略有不同，二者都属于f p t 问题，因此也可对其进行核心化。 文献i 驯给出3 d - m a t c l t i n g 核心化算法，其算法思想是用一些特殊的模式三元 组与s 中的所有三元组来匹配，如果匹配的话，就丢掉一部分三元组，保留的三 元组的阅值由两个函数 和正来决定，正是k 的线性函数，正是k 的二次方函数， _ i 和正的大小证明详见文献【删在执行完核心化算法之后，可以分析出品中的 任意一个符号最多只能包含在卮个三元组中，那么如果s 存在一个最大的匹配， 匹配大小为毛也就是有3 t 个符号，每个符号最多出现在，主个三元组中，故经 核心化后s 最多可包含3 k x a = o ( ：) 个三元组，也就是问题的核为0 i 舻) 。同样的 算法也适用于3 - p s p 问题，也就是说通过核心化算法可以将一输入规模为4 的问 题转化成一输入规模为p 的问题，当k 值较小时，极大的减少了问题的大小 2 3 4 分治法 文献 划中提出求解图论问题中的一项新技术，该技术将分治法和着色法相结 合( d i v i d e a n dc o l o r ) 。这里所用的着色法并非是直接着k 种颜色，而是为了将图 进行划分，仅仅是对图着黑和自两种颜色，通过这种着色法后将问题划分成两个 子问题，再在这两子问题上用同样的方法处理，直至无法划分为止用此方法来 求解h - g r a p he d g e - p a c k i n g 问题，对图中的所有边着上两种不同的颜色，再根据 颜色来划分为两个子问题，之所以用着色法是可以通过着色方案使将不确定算法 来设计出确定算法整个算法的时间复杂度主要是着色方案的时间复杂度和分治 法的时间复杂度的乘积，最后得到d ( 1 6 h o ) 。同样的算法也可以运用到3 - s e t 1 0 碰士学位论文第二章s e tp a c k i n g 同题的研究进展 p a c k i n g 中，其时间复杂度为o * ( 1 扩) 在文献口“中提出了一种随机的分泊法，设在全集s 中寻找k 个元组标记为 最首先用随机法将品划分为相同大小的两部分，再循环的从每部分中寻找k 2 元组。对于3 - s e tp a c k i n g 而言，若取存在，设m 是包含3 女个元素的子集在 中，可以将出划分为血，和血两部分并使得正好a 包含3 2 k 个元素向1 2 个元 组和以也包含3 2 k 个元素m 2 个元组，这样的概率有f ：，l 2 n = o ( 1 ( 2 ”两) ， v “， 再循环对这两部分细分，最后得到其随机算法的时间复杂度为d ( 2 5 妒) = d + ( 2 5 2 3 勺 2 3 5 着色法 着色技术主要是通过发现额外的限制条件有效地降低目标问题的搜索空问， 其基本思想是给定元素集合u 和颜色集合c ，其中| u 产 ，l c l = k ，将u 中每个元 素都是用c 中的一种颜色进行着色通过假定原问题的目标解包台的1 个元素正好 被着色为嗣降不同的颜色，原问题将获得额外的着色约束条件从而得到简化 1 9 9 5 年n o g aa l o n 等人提出了一种称为彩色编码的技术( c o l o rc o d i n g t e c h n o l o g y ) 来求解一些n p 难问题，如矗路径( t 巾a l l l ) 问题p 3 州使用彩色编码技 术的关键步骤是产生着色方案。最初，人们设计的算法是假设目标路径中的k 个 结点恰好被胼十不同的颜色着色。他们提出的产生着色方案的过程首先将图中的 所有结点用脚 颜色随机着色，在搜索路径的过程中使用动态规划的方法递推找 到日标路径。矗路径问题的求解难度在于对路径简单性的判定，彩色编码算法可 简化这一步骤，从而大幅降低了问题的难度算法的时间复杂度从原来的 o ( 2 k k ! x 1 降低为o ( 2 x q 1 ) ) 算法中的假设条件成立的概率为麒，o b 一，因此算 法需要重复o ( 由以保证结果的成功概率为1 e - c ，c 为正常数，给出的彩色编码算 法中的产生着色方案和用动态规划搜索路径是相对独立的，并给出了确定式着色 方案产生方法通过散列公式，将q ； l 目完全映射到w = i s 2 1 中一个重要的定理。已知s 和s 的一个p a c k i n g p k ，如果s 中存 在斥l ，则有一个，h 满足下列条件：a 中的每个元组至少有两个元素在斥l 中 在解决3 - s e tp a c k i n ga u g m e n t a t i o n 问题时，利用上述定理，在斥l 中只要再 寻找 十3 个元素，再加上n 中的2 t 个元素，就可确定e k - i 。作者运用着色法来 寻找这k + 3 个元素，得到o ( 6 1 的着色机制，然后用另外弘种颜色对b 中的 元素进行着色，把上面得到的着色机制，加上p i 中的3 t 种颜色，这样就得到 4 k + 3 的着色机制，再运用动态规划的方法寻找凡l 如果，“存在的话，算法就 可返回n 1 个元组，这些元组中的元素都着了不同的颜色，时间复杂度为0 * ( 2 4 k ) 最后，该算法总的时间复杂度为d ( 6 1 个d ( 2 勺= d ( 4 6 1 2 4 本章小结 s e t p a c k i n g 问题起源于分割问题的应用，是在强约束条件对元素进行划分 在复杂性理论中，此问题是一类重要的n p 难问题，被广泛应用于调度、代码优 化和生物信息学等领域。特别是在参数计算理论产生后，此问题再次成为研究的 热点阀题。依据所研究问题的差异，本章将s e tp a c k i n g 问题分成5 类，并给出 了具体的定义在此基础上，分别介绍了求解这5 类问题的相关算法，着重分析 和比较了参数算法中所运用的各项技术，并提出了一些该问题算法研究的发展方 向 我们可归纳出求解此类问题的方法大致分为以下三类。一将其转换成最大独 立集或最大团来求解无论算法如何改进，其时间复杂度中总有个n 的指数，通 常认为n 是个很大的数，因此这方法几乎无法在实际应用中执行；二在多项式时 间内求其近似解，但我们可发现其相关的近似算法的近似率并不理想；三以参数 算法求解，现3 - s e t p a c k i n g 问题最好的f i t 算法的时间复杂度为d ( 4 6 1 3 。当 k 是个较小数时，其时间复杂度在实际操作中完全可以接受因此随着参数计算 理论的产生，更推动了这一问题的发展，使之成为近阶段的熟点研究问题 硕士学位论文第三章加权分治技术 第三章加权分治技术 加权分治技术由f v f o m i n 首先提出，是在分析算法中产生的一项新技术， 该方法基于选择不同的量来描述分支子问题的大小，以求从中得到在最差情况下 最好的时间复杂度其核心思想是期望找到最合适的量来描述子问题的大小，使 得在分支时能更准确、更有效的表明问题本身，从而降低其时间复杂度。 严格意义上来说该技术不是一种算法而是对算法进行分析的新的方式该 技术最大的优势在于在不修改原算法的基础上，仅仅依靠选取不同的量就能使其 时间复杂度降低，而且在理论基础上是完全可行的 本章对其进行了系统的研究，包括应用闯题、应用步骤、应用范围以及与参 数计算相结合等方面，较全面的分析了该技术的优劣。并提出了一种新颖简单的 分析方法来对权值进行求解，使得时间复杂度最小 3 i 加权分治技术具体应用 目前有关于该技术的文献仅有两篇，且国内尚无人涉及这方面这两篇文献 分别解决了最小支配集问题【1 】和最大独立集问题【4 】，并得到了很好的结果，其相 关内容如下。 3 1 1 最小支配集 在解决最小支配集问题嘲时，作者通过u f f i v 和s f f i f n v n e v 将最小支配集 问题转化成最小覆盖集问题，因为在图中n 【v 】由v 点支配所以d 若是图0 的 支配集当且仅当 n m 卜v ) 所对应的 n 【川卜e d 是覆盖集因此，每一个最小 覆盖集 n v l v e d 对应一个图g 中的最小支配集这里的u 是覆盖集中元素全 集，s 是所有子集。 1i n t r o s e ( s ) f 2 i 域i s i = 0 ) r c 衄0 ； 3 i t l 3 s ；rs ：踺固r e t u r n 脚c ( s 、 s ) ) ； 4 i f ( 3 u e o ( s ) 3 a t m i q t 地$ e s ：n s ) 舳 + m s e ( d d ( s s 髓 5t a k ej so f m a x i r m m a r d i n a l i 乜6 6 i f ( 1 司= 2 1r m u r np o l y - m s c ( $ ) 7r e t u r nm i n m s c ( s 毋) ，t 竹n ( d d ( 墨s ) ) ) ； 8 ， 田3 - 1 最小覆盖集的简单递归算法 1 4 硕士学位论文第三章加权分治技术 根据最小覆盖集问题的相关特性给出一简单的递归算法如图3 - 1 所示。根据 常规的分析方法设妊1 s i + i u i ，并令h 明是问题大小为女时搜索分支树的叶子数目 在展后分支时，当子集s 不在集覆盖中，可以直接删去子集所以问题大小变 为k - l ；当子集s 在集覆盖中时，不仅可以将子集s 移去，而且在子集5 中所包 含的元素都可以删除，由算法可知，如果i 研= 2 时，该问题可以在一个多项式时 间内解决，所以陀3 ，这样符号全集的大小可以减去3 ，因此整个问题的大小变 为4 。根据分析得到如下递推式子研明s _ p 【舡l 】+ p k - 4 ，由此可得到整个算法的 时间复杂度为0 * 0 3 8 0 3 岬，i s 两且1 u l _ n ，所以算法时间复杂度为 o f 1 9 0 5 2 ) 。 再运用加权分治技术对同样的算法进行详细的分析。通过如下的发现，移去 大小大的子集比移去大小小的子集更加有效；去掉频度大的元素比去掉频度小的 元素更加有效因此将子集大小和元素频度都考虑进来，分别对不同大小的子集 和不同频度的元素赋上不同的权值这样可令 k - k ( s ) = q 吩+ 啪 m 表示大小为i 的子集的数目；m j 表示频度为j 的元素的个数这里的权值 卿和巧将固定在【o ，l 】之问，确保了q 珥s i s i 和v j m j l v l 。因此艇；抽为 m 了能简化分析，做了如下假设： 1 、d 0 1 - - - - = j 1 = 1 且当三6 时，璐= 1 俨1 ； 2 、当鼬时，眶丛砷s a d h i 主要根据分支情况，通过详细的分析，当子集s 不在覆盖集中时，问题大小 可以减去酏m 2q i l + r l a + r z m z + 烈，z ) n ；当子集s 在覆盖集中时，闯题的 大小又可减少a k + h + ，。，+ a m l ，i ( o l 加+ 6 ，t ) ，这样可得到如 1 = 2l - 2 下递归式p 非】s 烈七一厶毛研】+ 烈七一厶k 】再利用q u a s i 伽珥o g m m m j n 矿刀 对权值进行求解，当等式一。a t 岫+ 一屿的最大实根最小时，权值设置如下， ( 曲，自i ，凹，d b ) ：o 3 7 7 4 ，0 7 5 4 8 ，0 9 0 9 5 ，0 9 7 6 4 ) 似，b ，v s 产- ( o 3 9 9 6 ，0 7 6 7 7 ，0 9 3 0 0 ，0 9 8 5 6 ) 在固定如上权值后可以得到a 1 2 3 5 4 ，因此其时间复杂度为d ( 1 2 3 5 4 21 ) ，即 0 + ( i 5 2 6 2 。 _ 顷士学位论文第三章加权分治拄术 3 1 2 最大独立集 根据最大独立集的相关特性，作者先给出了引理3 - i t 4 l 如下。 引理3 - 1 对于任何的图g ( i ) 如果g 中包括一连通分量c ，则耐6 3 = 碳c ) + 口( g - c ) ； ( 2 ) 如果有两个点v 和_ ，且m 叫 川( 1 ，支配v ) ，则口( g 产口( g 嵋) ( 3 ) 对于任意可折叠点v ，有耐g p l + d g i v ) ) 。 令口( g ) 表示图g 中最大独立集的大小。 由引理3 i 得到一个求解最大独立集简单的递归算法删j 。 i n tm 盼( g ) ( o ) i 坟( 年中) t e t l l r n0 ； ( 1 ) i f a c o m p o n e n tc b g r 咖m i s ( c ) + m i s ( g - c ；, ( 2 ) i f ( 3 n o d o va n dw ：州训州嵋) r h u l f f i 捃( 6 k y ) ) ； ( 3 ) i 妇a f o l d a b l e n o d e e d ( v ) s 4a n d ( 订c o n t a i n sa t m o s t 3a n t i - e d g e s ) t a k eo n es u c hn o d ev o f m i n i m u md e g r e e ； m t m l + m i s ( g i 谫； ( 4 ) s e l e c tan o d evo f m a x i m m t ld e g r e e ； 地t 咖m a x m 缸( ( v 重( 助，1 + 棚捃( 1 州v d ； ) 田3 - 2 最大独立集的简单递归算法 整个算法的时间复杂度分析主要根据分支情况根据常规的分析方法令研明 是问题大小为女时搜索分支树的叶子数目，且初始肛制g q 若i 卸时，h 七】= 1 从连通分量、支配及折叠情况可以明显看出( 1 ) 、( 2 ) 、( 3 ) 步的操作一定满足 研明s 尸【缸l 】在第( 4 ) 中若v 点的度数等于3 ，当v 点不在最大独立集中时 可阻直接将v 点移除，也同时排除v 点的所有镜像点或者折叠移去y 后度变为2 的点，这样至少k - 2 ；当v 点在最大独立集中时，因为可以直接去掉m v 】= 4 ，所 以可以得到公式h 明讲t - 2 】+ 研- 4 】若v 点的度数大于等于4 ，当y 点不在最大 独立集中时，可以直接将y 点移除，大小减l ，且最坏情况下点v 没有镜像点， 所以问题大小至少减少1 ；当v 点在最大独立集中时，因为可以直接去掉m v p 5 ， 由此可以得到公式研司s 尸f 矗1 】+ 尸【k - s 根据以上2 个公式进行求解可得算法 时间复杂度为d m 下面再运用加权分治技术对同样的算法进行更详细的分析可以发现移去一 度数大的点比去掉一度数小的点更加有效，因此将点的度数的因素考虑近来给 1 6 硕十学位论文 第三章加权分治技木 不同度数的点给定不同的权值。这样令 = ( g ) = q s h 。n i 表示图g 中度 数为i 的点的数目，这里的权值啦将固定在【o ，l 】为了能简化分析。将做如下 假设： l 、砷；叻：0 ； 2 、如果也7 ，则国f l ； 3 、当点的度数从牌到f - l ，其权值减少q = 呜一，假设 q q 伤a c 0 6 a 讳2 0 ； 主要根据分支情况，通过详细的分析，当点y 不在最大独立集中时，问题大 d 小可以减去m 吼+ n + m 哟q + m i a m ；当点v 在最大独立集中时， 如3 j 问题的大小又可减少a 。2 q + 啦玛+ a 吐+ a 。o n 雌一这样可得到如下 i 吣- z 递归式烈埘蔓d 一m ，】+ d 女一】再利用q u a 3 i c o “p r o 擘柚m i 3 ”对权值 进行求解，当等式一：a - h + a t 的最大实根最小时，权值设置如下， ( n k 峨，螺蚺户l o 5 1 3 9 ，0 7 7 8 3 ，0 9 2 3 0 ，0 9 8 4 2 ) 在固定如上权值后可以得到a o ，则对任意足够小的f ，有 v f ( x ，+ n 。 为了便于下面的分析，先把此类递归式求解问题规范化。 递归函数式：，( 力2 “擎，缸一屯) o - 1 ) 变量个数；整数d 表示。 目标向量i ：d 维欧氏空间上r 。的子集 把f ( x - 4 j ) 称为“项”，f o 一) 称为“被加子项”，f 表示第j “项”， 表示第f 项的第，个“被加子项”，x 和4 ，表示d 维欧氏空间上的向量- 每个 向量包含d 个变量。 3 3 2 设计思想 通过赋权技术来逼近待求解这类递归式的上界，为了求得最小上界，必须 先求得各个变量的最佳权值，赋权技术具体细节如下： 取向量w r s ，对输入递归式的每个被加子项f o 一) ，m 谚j ) 0 ，是 一个实数，且定义 f - 2 m 。a x ，f ( 3 - 2 ) 以式【3 1 ) 代替式( 3 _ 2 ) 中右边的，【砷，并且交换最大值的顺序，则得到以 下不等式； 硕士学位论文 第三章加权分治技术 s 。产e ( ) ，一嵋) ( 3 - 3 ) ， 作为递归出口记e ( 力= 1 如果0 o ，j + 佧，帕y = 1 对其他单变量递归式，类似 可求q ，i f f i 2 ，3 ，4 最后，取q = m a x 以 ，则，( 帕s e ( 帕= d ( ) 考虑一般的带约束条件的函数优化问题： 硕士学位论文 第三章加权分治技术 m i n f ( x ) ，j = “，毛，) “g ，( 曲o , j = 1 ，f ； ，( 功；0 ，_ ，= ，+ l ，m ； 其中： x = ( ，毛，) 为决策向量；玉在区闻，珥仲取值；z 为月 维欧氏空间上r 。的子集：，o ) ，g ，( x ) ， ，( 而均为维欧氏空问彤上的月元 函数；，d 为目标函数；g ，( 力为不等式约束条件； ，( 曲为等式约束条件。 可把k m i s 问题规范成如下形式的一般的带约束条件的函数优化问题，且 规范化后所求得的巳值是最大值： r a i n f ( x ) = c j 上一( 毒+ _ ) ，) o ：- ( 2 x + y ) s 0 ；一( 3 x + y ) s o ；- x o - 可得一0 + y ) s o l 叫 2 x + 力量0 l 一( k + j ，) s 0 ；x o t 碗士学位论文 第三章加权分治技术 一缸+ 力0 等约束条件：由约束品j = l ，可得等式约束x + 似n ) y 一1 = o 递归求解问题推广到一般的带约束条件的函数优化问题的函数模型如下： m i n f ( j ) = 气 j 上茹4 ，) o ；，c 虬一1 蔓0 i ；= 1 可求得( q ，奶，其中气= i n f j 勺，帚；一l ，且赋权向量的最优值收敛于点面， 对应进化算法豹目标值收敛于气 定理3 - l 令( c - ，动为进化算法所求得的最优解，令b 为进化算法有效约束项 的集合，对曰中任意第州以及第f 项的第，个被加子项，令p 。= c 一”。，则对 b 中任意第f 项，有，p u = l 证明：如果项f 只包括一个子项，则有访锄= o ，毛= l 否则由f 个约束求 得的解一定是最优解( ，动，此时对应方程( o = l 一，。= 4 3 所以 ，p j j = l 推论3 _ 1 对目标向量为；的输入递归式f ( 力，如果( 气，奶为进化算法所求 得的最优值，则，( h ) = f ( n t ) = d ( c ) 证明：如果对所有项f 有c 。= q + ，则由引理3 - 4 可证 接下来用进化算法求解c - 的最小最大值以及讨包含的各个变量的最优取 值。 从上述建立的模型可知，问题可归结为一个约束优化问题( c o a s t r a i n e d o p t i r n ：i z a t i o n p r o b l e m s ) 传统的优化方法求解这类问题时都是基于梯度的信息， 只适用于目标函数和约束条件可微的情形，而且求得的解多为局部最优解进 化算法( e v o l u t i o n a r ya l g o r i t h m s e a s ) 是一种模拟自然进化过程的全局优化方 法，它通过选择、交叉、变异等机制来提高个体的适应性同传统优化方法相 比，进化算法更适合于求解约束优化问题。 进化算法包括遗传算法( g e t i ca l g o r i t h m s , g a ) 、进化策略( e v o l u l i o n a r y s t r a t e g i e s e s ) 和进化规划( e v o l u t i o n a r y p r o g r a m m i n g , e i p ) 其中遗传算法的应 用最为广泛，其整体框架描述如下： i 、在一定编码方案下，随机产生一个初始种群： 2 ，用相应的解码方法，将编码后的个体转换成问题空间的决簟变量，并求 得个体的适应值l 3 、按照个体适应值的大小从种群中选出适应值较大的一些个体构成交配 池： 颈士学位论文第三章加权分治技术 4 、由交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一 代的种群； 5 、反复执行步骤2 4 ，直至满足收敛判据为止 使用遗传算法需要决定的运行参数有：编码串长度、种群大小、交叉和变 异概率。 近十年来，利用进化算法求解约束优化问题已有许多学者进行了广泛的研 究，并且提出了大量的约束优化进化算法( c o m 蜘n e do p 妇l i z a 舡e v o l u t i o n a r y a l g o r i 廿m 。c o e a s ) 文献御憾出了一种求解复杂约束优化问题的新方法 多目标约束优化进化算法( 即利用多目标优化技术求解约束优化问题) 。在这里 我们采用该文中提出的算法来求解本文所构建的数学模型，限于篇幅，本章仅 给出该算法的大致思路和框架 算法的整体流程如图4 - 3 所示。 b e g h i 选择合理的参数并随机产生主群体p ： 2 r e p e a t 2 1 执行基于群体的算法发生器模型；( 操作l 【5 1 彤b 2 2 执行不可行解存档和替换机制( i s a m 田；( 操作2 唧 u n t i l 满足停机准则 e n d 圉4 - 3 进化算法流程 其中，停机准则可以是用户能够接受的一个解或者是一个预先设定好的适 应值函数评价次数。 值得注意的是，在群体进化过程中，子代群体中的非劣个体数，从档案j 中 选出的用于替换群体p 中个体的个体数都是动态变化的c o e a s 具有两个明确 的目标：l 、群体快速地靠近或进入可行域；2 、收敛于全局最优解为了实现 第一个目标，上述整体流程中的操作2 可以不断地促使群体向可行域靠近为 了实现第二个日标，上述整体流程提供了另外一个操作( 操作1 ) 使得群体能够收 敛于全局最优解。同时，随着群体逐步进入可行域，操作2 的影响将变得越来 越小，这有利于群体后期的收敛 由上面的分析，用进化算法解决此类优化问题是非常有效的在子代群体 硕士学位论文 第三章加权分治技术 找出所有非劣个体需要在个体间进行2 卫五次比较，其中_ = i 是予代群体中非劣个 体的数目。在文献 5 0 1 提出的计算模型中，用非劣个体替代劣于个体需要进行血 次比较因此总共的比较次数是2 ( 2 互十”1 。 3 3 3 具体实现 程序在m a t l a b 环境下编译运行，由五个模块( 文件) 构成， c l o $ $ o v c l m ：采用单形交叉产生后代个体，并判断产生的个体是否在搜索空问内 f i t n e s s , m ：计算群体的适应度 i n f _ i n d , a r cm i dr e p m ：实现不可行解存档和替换机制。首先将“最好”的不可行 解存档，再将“最好”的不可行解随机替换集合p 中的个体。 m o d e l s n l ；执行基于群体的算法发生器模型。 m a i n m ：函数主体包含待求解问题的输入输出，初始值的设置 执行过程如下z 1 、产生初始群体p 设定迭代次数 2 、计算群体的适应度( 调用f i m e 目s m ) 程序语句如下 f i t = f i t n e s s ( p , i , p r o b l e m ) ；p r o b l e m 为一个整型值，代表待求解问题 3 、从p 中随机选择m u 个个体构成集合q 用于交叉核心代码如下 r a n d _ s e l - - r a n d i n t ( m u , 1 ， s , p o p s i z e ) ； q = p ( r a n ds e l ，：) ； 4 、通过单形交叉产生l n m b d a 个个体构成集合c 核心代码如下 c = c r o s s o v c r ( q , m u , s i m p l e x _ f a c t o r , m i n _ v a r , m a xv a r j a m b d a , n r c e a t ) ； i f , , 4 9 m p t y ( c ) f i tq = f i m c s s ( q ，1 , p r o b l e m ) ； 【丑tc n 吐i m 协c s s ( c ，2 , p r o b l e m ) ； 5 、从集合c 中找出所有非劣个体核心代码如下 h u mn o n d o m - - f i n d ( n m k _ i = = 0 ) ； r = c ( n u m _ n o n d o m , ：) ； f i t _ r = f i t _ c ( h u mn o n d o m , ：) ； 6 、执行基于群体的算法发生器和实现不可行解存档和替换机制核心代码 如下 p , f i q - - m o d e l s ( p , f l t , 丘t - q 足丘t _ r , r a a d _ s c l ，c o n d i t i o n _ 2 ) ； f f c o n d i t i o n1 + c o n d i t i o n _ 2 = = o 【p ，丘饥丘t _ a 】- - - i n fi n da r ca n d _ r e p ( g e n ，p , f i t , r , f i t _ r , a , f i ta , p o p s i z c ) ； e n d 硕士学位论文 第三幸趣l 权分治技木 7 、迭代次数加一如果小于步骤一设定的迭代次数，则循环执行2 - 6 否 则退出摇序，输出结果。 针对不同的问题，我们只需要在f i t n e s s m 中输入问题对应的输入表达式， 在m a i n m 中输入相应的初始值设置，其他部分不需要傲任何改动，具有很高的 适应性和可重用性 实验情况的分析将根据具体问题的求解放在下一章中给出。 3 4 本章小结 加权分治技术是在算法分析中产生的一项新技术，该方法基于选择不同的量 来描述分支子问题的大小，以求从中得到在最差情况下最好的时间复杂度我们 对其进行了系统的研究，包括应用问题、应用步骤以及应用范围等方面，较全面 的分析了该技术的优劣，也为问题选定的工作奠定了理论基础。 在加权分治技术中通常用伪凸规划技术来确定权值，我们提出了一种新颖简 单的分析方法获得此类问题的最小上界，使用进化算法对此类问题求解由于进 化算法采用多点并行搜索的搜索机制，因此大大提高了搜索速度，对求解舍多个 变量且约束条件非常复杂的复杂优化问题体现了优越的性能从而为此类问题提 供了一种通用的分析方法，大大降低了原问题的复杂性。 磺士学位论文第四章神基于 j 权分治技术的s e tp a c k i n g 算法 第四章一种基于加权分治技术的s e tp a c k i n g 算法 4 1 基本知识 s e t p a c k i n g 问题起源于分割问题的应用，是在强约束条件对元素进行划分 在复杂性理论中。此问题是一类重要的n p 完全问题被广泛应用于调度、代码 优化和生物信息学等领域其具体定义如下j 定义4 - 1 给定一个含有 个子集的集合占且组成这 个子集的符号全集的 大小为，目标是从集合了中寻找一个最大子集奠使s 中的任何两个元组之间 没有相同元素 此类问题被称之为常规的s e tp a c k i n g 问题( g s p ) 单独研究g s p 问题的相 关文献较少，其主要原因是研究g s p 算法就等同于研究最大独立集( m a x i m u m i n d e p e n d e n ts e t ) 和最大团( m a n h - n u mc l i q u e ) 等问题，因为可以把g s p 问题在 多项式时间内转化成这些问题。所以求解g s p 问题通常将其转换成晟大独立集 问题求解最大独立集问题的定义如下【i 】 定义4 - 2 在图c , ( v j z ) 中找到点的子集矿使得i 矿1 最大且在矿中的点相互之 间不存在边 对于最大独立集问题的算法研究已经有很长的一段历史首先由t a r j a n 提出 一个时间复杂度为0 ( 1 2 8 的的算法，打破了。( ? ) 的上界i 吲；1 9 7 7 年t a r j a n 和 t r o j a n o w s k i 又将其算法进行改进使时间复杂度降低到o ( 1 2 s 9 矿1 ) t 1 4 】；在1 9 8 6 年 b a n 给出一在多项式空问复杂度的改进算法将其时间复杂度降低到 0 ( t 2 3 4 6 ) 1 1 5 i ；随后由r o b s o n 将时同复杂度降到0 0 2 2 7 7 吖“最近f o m i n 通过 用加权分治技术将最大独立集合问题的时间复杂度降至“1 2 2 0 9 叶4 1 ，是现有解 决最大独立集的最佳算法 加权分治技术由f v f o m i n 首先提出，是在分析算法中产生的一项新技术， 该方法基于选择不同的量来描述分支子问题的太小，以求从中得到在最差情况下 最好的时甸复杂度。该方法已经成功的应用到求解最大独立集( d 吖1 2 2 0 叻) 1 4 1 和最小支配集( d + ( 1 5 1 3 6 ) 嘲中本文也是应用加权分泊技术来分析g s p 问题， 我们仍然将其转换成最大独立集来求解，且引入了符号全集的大小得到了一 个时间复杂度为d n l 1 6 8 6 n + 的算法当n n 4 时，比现有最佳的算法 ( 0 4 ( 1 2 2 0 9 ，b ) 更加有效嗍，且随着的减少其时间复杂度不断下降 硬士学位论文第明章一种基于加权分治技术的s e tp a c k i n g 算法 4 2 基本算法 给定一个g s p 实例，一组有限集合舅岛，焉，符号全集p 的大小为 根据问题的要求我们有以下的发现。 引理4 - l 对于任意的g s p 问题，存在如下3 个性质： ( 1 ) 如果一个子集合岛中所有元素的频度都为1 ，则s 必然属于每个最大s e t p a c k i n g ： ( 2 ) 当元素是唯一属于子集最时，则可以直接去掉元素，将不会影响最 后结果； ( 3 ) 当有两子集趴母s ，且s jc _ s t 时，则可直接去掉子集s i ，将不会影 响最后结果 证明：下面分别对引理4 1 中的3 个性质进行详细的说明 ( 1 ) 假设对于s e t p a d d n g 实例中子集岛中所有元素的频度都为1 ，其实 例的最大s e tp a c k i n g 为晶若最不属于s 呻，可以直接将置加入矾因为子集 岛不会和s 呻的任何子集相交，这样s 祷不是该实例的最大s e t p a c k i n g ，与假设 相反，所以西必然属于每个最大8 e tp a c k i n g ( 2 ) 假设对于一s e tp a c k i n g 实例中子集置中有元素”的频度为l ，将元素 “去掉后，其实例的最大s e t p a c k i i l g 为肌若盅不属于肿，说明s 必定至少与 s 呻的一个子集相交且与元素“无关i 若岛属于s ，中再加入元素”不会改变其 结果，因为元素”的频度为1 ，使得加入元素后子集最仍然不会与s 中的任何 集合相交 ( 3 ) 假设对于一s 畦p a k i n g 实例中包括母和母集合，且母母，其实例的 最大s e t p a c k i n g 为s ，若墨不属于s 中，去掉置不会影响结果；若品属于肿， 直接可以用爵来替代品心1 不会产生变化 证毕。 对于一g s p 实例，首先通过引理4 i 中的3 个性质对其进行预处理，经过 预处理后产生一个新的g s p 实例，使得该新实例中每个集合大小至少为2 ，且每 个元素的频度也至少为2 。对于这样的g s p 问题我们依旧将其转化成独立集问题 来做。g s p 问题可以在多项式时间内归约成独立集问题，其线性归约的具体方法 如下 给定一个g s p 实例，有n 个子集和个元素。将 个子集看作 个点， 个元素也看作个点，先从每个子集出发，与所包含的元素之问连边，再从每 个元素出发，将其相连的点两两连边，最后将个元素的点以及相连的边去掉， 形成了图g 。其时间复杂度为0 ( ，肿) 硕士学位论文第四章一种基于加权分治技术的s e tp a c k i n g 算法 定理4 - ig s p 问题中的一最大s e tp a c k i n g 当且仅当就是所构建图g 中的一 个最大独立集 证明：必要性。若s 是原问题最大s dp a c k i n g ，则对应的图g 中的点两两 之间必定没有边，这些点显然是一独立集又因为s 是最大s e tp a c k i n g 。若加 入任意一子集s 后，一定会有公共元素的出现，表明在图g 中若加入任意一点 的话，必然会出现边，所以对应s 中子集的所有点将是图g