（计算机应用技术专业论文）软件过程中活动规划与资源分配方法的研究.pdf

哈尔滨上程大学硕士学位论文 摘要 软件项目开发过程中如何将有限的资源在所有活动之间进行分配，从而 使整个软件项目的各个指标达到最优，同时每个活动根据分配的资源来组织 具体的工作，使它们自己的各个目标达到最优，这个问题一直以来是软件工 程专家们在深入研究的问题。 本文正是针对以上问题，以遗传算法为基础，研究了软件项目中活动的 规划和资源分配方法，为用计算机技术实现软件项目管理，提高软件质量提 供了宝贵的借鉴。本文在阐述软件过程中活动规划与资源分配问题的特殊性 的基础上，针对基于r u p ( r a t i o n a l 统一过程) 模式的软件过程，建立了软 件过程中活动规划与资源分配问题的数学模型，运用遗传算法的思想及整合 处理对数学模型进行求解。另外，本文采用图论的方法来解决软件过程中串 行、并行以及交叉耦合活动的判定与规划问题；提出模糊综合评价方法对人 员( 人力资源) 的能力进行评估，为遗传算法的应用打下了基础，提高了算 法的准确性。 根据上述的理论研究，并通过具体实例予以仿真验证，得出如下结论： 一是该方法在满足活动执行的先后逻辑次序的基础上，努力缩短了软件项目 ( 产品) 丌发周期：二是该方法优化资源的使用，能够提高资源的利用效率。 关键词：软件过程；活动分配；活动规划；遗传算法：图论：模糊综合评价 堕玺堡三型盔兰鎏圭兰堡鎏圣 a b s t r a c t i ti sa na t t r a c t i v e p r o b l e mf o rs o f t w a r ee n g i n e e rt h a th o wt oa l l o tl i m i t e d r e s o u r c et oa l lk i n do fa c t i v i t i e sa n dh o wt om a k ef u l lu s eo fr e s o u r c ef o re a c h a c t i v i t yi no r d e rt oo p t i m i z es o f t w a r ep r o c e s sm u l t i - f a c t o r s a i m i n ga tm a n yp r o b l e m sa b o v e m e n t i o n e d ，t h i s a r t i c l ef o c u s e so nt h e r e s e a r c ho ft h ea c t i v i t i e s s c h e d u l i n ga n dr e s o u r c ea s s i g n m e n ti n t h es o f t w a r e p r o c e s s b a s e do ng e n e t i c a l g o r i t h m b ya p p l y i n g t h em e t h o do fa c t i v i t i e s s c h e d u l i n ga n dr e s o u r c ea s s i g n m e n t ，t h eq u a l i t yo ft h es o f t w a r ei sh e i g h t e n e d ，i t i s p o s s i b l et om a n a g es o f t w a r ep r o j e c tw i t h t h eh e l po f c o m p u t e r i nt h ef u t u r ei n t h i sa r t i c l e ，t h ea u t h o re x p o u n d st h ep a r t i c u l a r i t yo ft h ea c t i v i t i e ss c h e d u l i n ga n d r e s o u r c ea s s i g n m e n tp r o b l e m ；s e t su pt h em a t h e m a t i c sm o d e lo ft h ea c t i v i t i e s s c h e d u l i n ga n dr e s o u r c ea s s i g n m e n tp r o b l e ma c c o r d i n gt ot h em o d e lo fr a t i o n a l u n i f i e dp r o c e s s ；p u t sf c ) r w a r dt h em e t h o do fa c t i v i t i e ss c h e d u l i n ga n dr e s o u r c e a s s i g n m e n tb a s e do ng e n e t i ca l g o r i t h m a tt h es a m et i m e ，t h er e c o g n i t i o no f p a r a l l e l a c t i v i t i e sa n ds e r i e sa c t i v i t i e sa n dc o u p l i n ga c t i v i t i e si nt h es o f t w a r e p r o c e s sc a nb es o l v e db yg r a p ht h e o r yk n o w l e d g e ；t h ee v a l u a t i o no ft h es t a f f s c a p a c i t yc a nb es o l v e db yf u z z ys y n t h e t i ce v a l u a t i o nt h e o r y t h e s et e c h n i q u e s m a k ef o u n d a t i o nf o rp u t t i n gf o r w a r dd e t a i lg e n e t i c a l g o r i t h m i na d d i t i o nt ot h e o r yr e s e a r c ha b o v e m e n t i o n e d ，as i m u l a t i o nr e s u l to ft h e m e t h o df o ra c t i v i t i e ss c h e d u l i n ga n dr e s o u r c ea s s i g n m e n ti ns o f t w a r ep r o c e s si s p r e s e n t e d a n dc o n c l u s i o n sa r eg i v e n ：t h em e t h o dc a nn o to n l ye x p e d i t et h e s o f t w a r ed e v e l o p m e n tb a s e do nr i g h ta c t i v i t i e se x e c u t i o ns e r i e sb u ta l s oo p t i m i z e r e s o u r c ea s s i g n m e n ta n di n c r e a s et h eu t i l i z a t i o nr a t i oo f t h er e s o u r c e k e y w o r d s ：s o f t w a r ep r o c e s s ；a c t i v i t ya s s i g n m e n t ；a c t i v i t ys c h e d u l i n g ；g e n e t i c a l g o r i t h m ；g r a p ht h e o r y ；f u z z ys y n t h e t i ce v a l u a t i o n 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 问题的提出 典型地说，软件开发项目成败的关键因素有三个：时间、成本和质量m 。 然而当我们把它们当作箭一样射向目标时，却经常会因为种种原因而无法正 中靶心。 资源的有效控制和合理分配、活动的合理规划与分配、软件过程的进度 安排成为软件过程的核心。在软件过程中，如果计划不周、组织不当，就会 产生脱节、窝工、停工、等待资源等现象，造成人力、物力、财力的浪费。 目前，我国的软件企业正处于高速发展、继续规范管理并以项目为主导的环 境中。软件企业每天面临的不仅仅是几个越来越大的大型项目，而是成百上 千不断发生和进行的项目。产生这种变化的因素是多方面的，这包括客户需 求的不断提高导致软件产品生命周期缩短；软件产品开发项目数量大增；新 技术导致了对研究和开发项目需求的增加等。在这种多项目并发、技术含量 高、变化速度快、资源有限的环境下，如何对软件过程中活动、资源、软件 开发进度实施科学的管理，加强团队的能力，实现软件过程的规范化、国际 化，提高软件的质量，缩短软件开发周期，是当前我国软件工程专家们面临 的重大课题。 软件过程是一个复杂的过程，它涉及多种因素，如开发环境、软件规模、 项目规划管理，等等。现在软件项目规模越来越大，往往一个计划好的项目， 在开发中会不知不觉的变得难以控制。一些调查表明，大约7 0 的软件丌发 项目超出了估算时间，大型项目平均超出计划交付时间2 0 n5 0 ，9 0 以上 的软件项目开发费用超出预算，并且项目越大，超出项目计划的程度越高。 怎样科学的管理软件过程，激励开发人员，提高软件开发的生产率，按时、 按预算提供满足客户要求、具有国际市场竞争力的软件产品，软件项目丌发 前进行科学的预算，即进行科学的规划和分配，就变得非常重要。 哈尔滨工程犬学硕士学位论文 所谓活动规划和资源分配就是对软件过程各个阶段中活动所耗费的时 间、活动的规划和分配、人力资源的分配等进行计算，并给出一个较准确的 结果，为软件项目管理人员合理安排开发计划提供重要的依据”：。长期以来， 软件开发人员基本上处于进退两难的境地中，一方面它们为解决开发中所碰 到的各种问题，工作太刻苦，挤不出时间钻研有效的实用技术；另一方面， 如果他们不发现和掌握加快软件丌发速度的方法，他们就永远都不会有足够 的时i b i 。软件开发人员一直被估算不准、功能蔓延、团队人员流失等问题所 困扰，在“尽快交工”计划的压力下，如何在开发进度与软件质量之问达到 最理想的平衡，成为软件开发人员最关心的问题。 ； 本文f 是针对上述软件过程中的种种问题，研究软件过程中活动规划和 资源分配的方法，充分考虑了时间、人力资源等因素，为软件项目管理人员 合理安排开发计划提供重要的依据，提高了软件的质量，缩短了软件的开发 周期。 1 2 论文研究课题的意义 一般的软件项目着眼于软件开发的行为和开发过程的分解，对软件开发 过程中活动组织与资源问题不够重视。随着软件工程研究的进展，人们对软 件过程中有关的资源问题给予了充分的注意。在一个软件过程中不仅要考虑 软件的丌发行为，还要考虑所需的资源及环境条件：不仅要考虑软件的静态 性，如软件过程描述，还要考虑软件的动态性，如软件过程的实施与控制； 不仅要考虑软件过程的正常状态，还要考虑软件过程的异常状态( 如资源的 变化、环境的变化等复杂因素) ，以便于对软件过程有效的组织、管理和控制。 软件项目的目的基本上有两个：一是在满足活动执行的先后逻辑次序的 基础上，努力缩短软件项目( 产品) 开发周期；二是优化资源的使用，提高 资源的利用效率。为了能够在尽可能短的时间内丌发出功能复杂的产品，软 件项目中的人员必须高度协作、密切交流。软件过程中的活动规划与资源分 配问题从本质上讲是一个资源的优化配置问题，但是与一般意义上的资源优 化配置问题相比，软件过程中的活动规划与资源分配问题有着自身的特殊性， 表现如下： 哈尔滨工程人学硕士学位论文 ( 1 ) 资源的侧重点不同：软件项目开发活动是一项创造性的脑力劳动， 丌发过程中耗费的资源主要是项目丌发人员的智力，因而人力资源的规划是 软件项目丌发过程中资源规划的重点。 ( 2 ) 活动执行模式的多样性：一项活动可以由一个人来完成，也可以由 掌握该项技术的若干个人员的任意组合来完成，不同的参与者组合会对活动 的完成周期产生重大影响。 ( 3 ) 人员才能的差异性：受教育背景和工作经验等方面团素的不同导致 了每个资源实体( 人员) 的技能有着较大的差异。另外，同样的活动由不同的 人员来完成，任务周期也会因人员的技能不同而有所变化，这就增加了求解 的复杂性。 ( 4 ) 资源的间断性：很多基于资源约束的项目规划中都作了以下假设： 在整个项目进展过程中资源总量恒定。但对于设计型项目，由于存在人员调 动、轮班、休假等因素，导致资源总量不稳定、对人力资源进行规划时必须 考虑其影响。 ( 5 ) 过程的反复性：软件项目开发过程是个不断的探索过程，因此在 软件过程中不可避免地存在着反复( 或迭代) ，如何协调和处理这些反复对设 计过程造成的冲击也是一个十分棘手的问题。 软件项目的开发过程是一个在保证各种约束( 时间、设备、人员) 满足 条件下，为实现某个指标而对所有变量进行赋值的过程”，而本文所研究的 课题正是充分考虑了上述问题，结合人工智能( a i ) 技术，提出了一个基于时 问、资源等因素的软件项目开发过程推进计划的方法和技术。此计划为人员 指明在何时由谁完成何种活动。 针对软件过程的特点，本文提出了一个基于遗传算法的活动规划与资源 分配方法，综合考虑了时序、资源、活动执行时间、各活动的并行关系等能 够使各个活动顺利进行的关键因素，保证资源的有效利用和信息的平滑流动。 本课题用遗传算法来解决软件项目开发过程中的活动管理问题，对于保证串 行活动尽可能并行、消除不必要的返工、缩短研发时间、降低开发成本、推 进软件产业的进展具有重要的实际意义；对软件工程和人工智能技术的研究 与应用具有科学意义。 哈尔滨上程大学硕士学位论文 1 3 软件过程中活动规划与资源分配问题的研究动态 规划与分配问题，是一种组合优化问题，具有很深刻的数学思想和理论 基础，可描述为在资源有限的条件下将事件安排到时间段。根据约束条件、 优化目标、问题领域的不同又可分为很多种类，比如时间表问题、运筹学中 的指派问题等。规划与分配方法广泛应用在工艺、制造、装配、工厂作业调 度、铁路时间表安排、中小学时间表及大学时间表安排等领域。 从数学的角度看，规划与分配问题是一个典型的n p 完全问题，无法用通 用方法得出唯一的精确解，需要借助各种启发式算法逐渐逼近最优解，传统 的规划与分配方法有两类”1 ： 1 ) 面向活动选择的启发式算法：大规模资源优化问题的难度主要源于 资源的竞争性，而其核心问题是当一个活动结束后，如何安排当前 状态下候选活动集( 即由所有前序活动都已经结束的活动组成的集 合) 中的活动执行次序。确定候选活动的执行次序必须基于一定的规 则，这些规则可以归纳为以下几类，：( 1 ) 基于活动的规则；( 2 ) 基 于网络的规则；( 3 ) 基于c p m 的规则；( 4 ) 基于资源的规则。除此 以外，还有诸如分枝定界法、t a b u 搜索法以及g p o p 、r a n d o m 等其它 一些启发方法，各种方法的适用范围和求解效率均有所不同。 2 ) 面向方案选择的启发式算法：面向方案选择的启发式算法与面向活 动选择的启发式算法有所不同，后者通过逐步选取一个或多个待规 划的活动，在求解的最终阶段形成个规划方案，在这种情况下， 一个活动一旦被选取并进行了规划，就永远都不能进行二次规划了； 而前者从一个或者多个已知的方案出发，分析其目标函数值，然后 遵循某种规律进行迭代，形成新的方案或者方案群体，分析其目标 函数值后继续迭代，逐步向最优解靠近。目前常用的面向方案选择 的启发式算法主要有两种，即模拟退火算法( s i m u l a t e d a 1 9 0 t it h m ，s a ) 和遗传算法( g e n e t i ca l g o r it h m ，g a ) 。 规划与分配在管理中起到非常重要的作用，但是，遗憾的是规划与分配 方法还没有应用到软件过程的管理中，目前软件开发的整个过程，包括人员、 活动的分配、进度的安排等都采用古老而且不够准确的方法估算方法。 4 哈尔滨 ：程大学硕士学位论文 软件项目开发是一个逐渐改进的过程，刚开始的时候，对要做的工作只 有模糊的认识，随着项目工作的进行，认识越来越清晰。由于开始时对要开 发的软件的认识比较模糊，所以对开发时间和工作量以及资源的分配的估算 也就比较模糊。估算只有随着对软件本身的认识清晰后才可能逐渐清晰，这 其实意味着软件过程估算实际上是一个逐渐改进的过程。 估算过程包含以下三个步骤n ，： ( 1 ) 估算软件项目规模( 代码行或功能点) 。虽然一些项目能够直接跳到估 算进度本身，但是有效的估算需要首先估算要开发软件的规模。 ( 2 ) 估算工作量( 人月) 。如果有了准确的规模估算，而且组织中有类似项 目绩效的历史数据，计算工作量就很容易了。 ( 3 ) 估算进度( 日历月份) 。一旦估算了规模和工作量，估算进度变得近乎 微不足道，但是得到一个能为多方人士接受的现实的进度估算是项目 中最难的一部分。 目前对具有多活动、并行活动的软件过程中活动、人力资源规划和分配 的研究还处于原则性的探索和讨论阶段。或者是根据经验予以估算，然后借 助一些项目管理软件( 如m i c r o s o f t 公司的p r o j e c t2 0 0 0 等) 对陔估算方案进 行检验和评价，根据检测结果手工调整估算方案，再用软件仿真去验证。这 种规划方法要求规划人员具有丰富的经验，而且在活动网络图复杂、人员技 能差异明显时规划工作显得愈发复杂。 随着人工智能技术的不断发展，遗传算法越来越受到重视，遗传算法。 是模拟自然选择的生物学规律，通过杂交和变异等操作，能够更好地逼近全 局最优解。遗传算法改进了模拟退火算法的不足：从单个方案到单个方案的 迭代，点到点的优化。能够做到自身独立于搜索规则，从一代方案到另一代 方案的迭代，群体到群体的优化。正是因为遗传算法的强健性和对复杂问题 的求解能力，将遗传算法应用于软件过程中活动规划与资源分配是可行的。 在本文各章节中所提到的活动规划与资源分配，实指软件过程中的活动 规划与资源分配，以后不再赘述。 ：立a j 堡；! ；垒盔耋至圭兰生笙圣 1 4 活动规划与资源分配相关技术领域的一般方法 软件是逻辑结构，不是物理结构，因而不能在开始生产之前便对其系统 有一个详细的关于结构方面的描述定义。由于这种未来结构的不确定性，导 致了估算的不确定性，在项目执行过程中，经常出现到项目的某。旱程碑或 报告期时，项目的进度早于或者晚于计划进度，已经发生的实际成本低于或 高于计划成本；。 用计算机来实现软件过程中活动的有效规划与资源分配，对于提高估算 的准确性、保证串行活动尽可能并行进行、消除不必要的返工、缩短研发时 问、降低开发成本具有重要意义。 随着人工智能技术的发展和优化方法研究成果的不断推出，人工智能理 论应用于软件过程中各项活动与资源有效控制与规划方面得到了研究，如专 家系统、人工神经元网络m ，等等。 ( 1 ) 专家系统 专家系统的应用有两个目的，一个是促进专家的经验和工作方法的传播， 帮助缺乏经验的新手；另一个是提高决策的效率和质量，提高决策的一致性、 合理性、可行性。专家系统有以准则形式使用试探法及专家知识来判断的方 法，同时有结合浅层推理和深层推理的方法。 专家系统应用于软件项目开发过程中活动的有效规划与资源的合理分配 可以采用基于规则的推理，运用完备的知识库的方法，还可以采用基于模型 推理的方法，比如：把软件项目分成三种项目类型：系统软件、商业软件、 封装商品软件。对于不同的类型都有相应的理论模型，进行有效控制和进度 计划，这种方法易于计算机化，运行速度快，但是获得完备的知识、建立准 确的模型方面难度较大。 ( 2 ) 遗传算法 遗传算法是一种完全区别于传统优化技术的新的优化方法，它以生物进 化过程为“机理”，即“优胜劣汰、适者生存”；并模拟人类“优生学原理” 利用随机交换信息思想使子代不断向着性能优化方向发展。同时，在遗传操 作过程中对生产的子代个体进行评价，保证了优越的遗传竞争机制。从而使 得子代性能优于父代。遗传算法具有算法简单、收敛速度快、计算时f 日j 只与 6 哈尔滨一i ：程大学硕十学位论文 变量数成正比等特点，可以搜索到全局最优解或近似全局最优解。 遗传算法作为一种自适应全局优化方法而逐步得到各学科研究人员的普 遍重视。遗传算法的一般步骤是初始种群产生、编码的确立、适值函数的确 定、遗传策略的选择等。 软件项目丌发过程中活动的有效规划与资源的合理分配在数学上是一个 多变量、多约束的单目标优化问题，在进行有效的软件过程活动规划与资源 分配过程中，不仅要考虑静态约束，如软件过程活动序列，还要考虑动态因 素，如资源、人员。常规数学方法如线性规划、非线性规划、动态规划、凸 网络流规划等方法”“在处理一个大规模优化问题时都要在应用条件上作一定 的假设或近似处理，并有各自的局限性，特别是在处理多重约束上遇到了困 难。遗传算法搜索最优解的过程是有指导性的，一定程度的避免了以上问题。 ( 3 ) 人工神经元网络 人工神经元网络( n n ) 最大的特点是采用神经元及它们之问的有向权重 连接起来隐含处理问题的知识，并具有以下特点：较强的学习能力，在确定 了心的基本结构后，运用学习算法对训练样本进行训练，可以实现知识的自 我组织；自我学习能力，在学习完成之后，还具有一定的泛化能力：容错能 力比较强；神经元之间的计算具有相对独立性，便于并行处理，因此n n 的执 行速度比较快。 n n 存在着不足：在使用之前需要大量的、有代表性的样本供其学习， 而且学习算法收敛的速度一般比较慢。学习完成之后，如果系统结构发生变 化，则需要增加新的学习样本重新学习。 ( 4 ) 基于运筹学的方法 运筹学“。主要研究经济活动和军事活动中能用数量来表达的有关策划、 管理方面的问题。当然，随着客观实际的发展，运筹学的许多内容不但研究 经济和军事活动，有些已经深入到日常生活当中去了。运筹学可以根据问题 的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性 的合理安排，已达到最好的效果。运筹学包含很多内容：数学规划( 线性规 划；非线性规划；整数规划；组合规划等) 、图论、网络流、决策分析、排队 论、可靠性数学理论、库存论、对策论、搜索论、模拟等等。 哈尔滨1 程人学硕士学位论文 1 5 本文的主要工作 早期的软件项目开发模型主要考虑软件开发的行为，包括软件丌发过程 的分解，对软件开发过程中活动的组织和资源问题考虑较少。随着软件工程 研究的进展，对软件过程本身的研究逐步展开，对于软件过程有关的资源问 题给予了充分重视。 本文正是考虑了软件项目开发过程活动的组织和资源问题，对整个软件 生命周期的一切活动进行全面、有效的管理。面对涉及学科多、用户要求高、 参加人员多、开发时间长的软件项目提出了在确定的资源范围内有效地、合 理地组织人力、物力在最短的时间内完成软件项目的软件过程中活动规划与 资源分配方法。 传统的规划与分配方法比如：基于活动规则的规划方法、基于网络规则 的规划方法、基于c p m 规则的规划方法等，这些方法主要是以活动邻接矩阵 为依据，先选定第一个活动予以规划，然后从初始候选活动集( 即山所有前 序活动都已经完成的待规划活动组成的集合) 中依赖某种规则选择一个活动 予以规划，接着从当前候选活动集中依规则选取新的规划对象，如此反复， 直至所有的活动规划完毕。该方法有一个明显的缺陷，即一个活动一旦被选 中并予以规划，则在后续的规划过程中就不能对其进行任何修改，这对于单 模式( 活动所需的资源固定、周期固定) 、中小规模问题而言尚有一定的适应 性，但对于多模式、大规模的规划与分配问题显然不能取得很好的效果。通 过前面的介绍，已经知道遗传算法不仅对于单模式、中小规模问题有一定的 适应性，而且对于多模式、大规模的规划与分配问题也能取得很好的效果。 本文的活动规划与资源分配方法要达到的目标是将合适的人( 担当不同 的角色) 分配给合适的活动，使软件项目周期最短，分配结果要满足软件项 目开发过程所要求的时剧条件。 综上所述，本文的主要工作有： 1 ，分析和探讨遗传算法，包括介绍遗传算法的技术特点，遗传算法的 基本操作，遗传规划的基本理论，遗传规划的流程等，通过对遗传 算法的分析，建立活动规划与资源分配的理论基础。 2详细阐述活动规划与资源分配方法。分析基于r u p ( 统一软件过程) r 哈尔滨丁程火学硕士学位论文 模式的软件过程中活动规划与资源分配的特点：不确定性、影响因素 的多样性和动态性；对活动规划与资源分配问题进行描述；提出基 于遗传算法的活动规划与资源分配方法，对整个问题给出由总体到 具体的解决步骤。 3 ，分析活动规划与资源分配方法中的三个关键技术：串行、并行、交 叉耦合活动的识别与规划；模糊综合评价；遗传算法，为活动规划 与资源分配方法的提出建立了基础。 4 阐述遗传算法求解活动规划与资源分配问题的求解策略和求解步 骤；举出具体实例，来验证活动规划与资源分配方法的有效性和f 确性；把遗传算法与其他规划与分配算法进行比较，说明遗传算法 的优越性。 从第二章起，本文将按照上述顺序逐步论述。逐步把活动规划与资源分 配方法从整体到细节，从理论到实践清楚明白地论述。 哈尔滨上程大学硕士学位论文 第2 章遗传算法的基本原理 2 1 遗传算法的概念及其特点 遗传算法( g e n e t i ca g o r i t h m s ，g a ) 在6 0 年代开始研究，并在7 0 年代 主要由m i c h i g a n 大学h o l l a n d 等人发展起来。遗传算法是- * 9 基于自然选择 和基因遗传学原理的优化搜索方法。 遗传算法的创立过程有两个研究目的：一是抽象和严谨地解释自然界的 适应过程；二是为了将自然生物系统的重要机理运用到工程系统、计算机系 统或商业系统等人工系统的设计中。 遗传算法是基于自然选择和基因遗传学原理的搜索算法，遗传算法有以 下特点m 1 ： ( 1 ) 遗传算法是对参数的编码进行操作，而非对参数本身。 ( 2 ) 遗传算法是从许多点开始并行操作，而非局限于点，因而可以 有效地防止搜索过程收敛于局部最优解。 ( 3 ) 遗传算法通过目标函数来计算适配值，而不需要其他推导和附加 信息，从而对问题的依赖性较小。 ( 4 ) 遗传算法的寻优期则是由概率决定的，两菲确定性的。 ( 5 ) 遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全 随机搜索。 ( 6 ) 遗传算法对于待寻优的函数基本无限制，它既不要求函数连续， 也不要求函数可微，既可以是数学解析式所表达的显函数，又可以是映射矩 阵甚至是神经网络等隐函数，因而应用范围较广。 ( 7 ) 遗传算法具有并行计算的特点，因而可通过大规模并行计算来提 高计算速度。 ( 8 ) 遗传算法更适合大规模复杂问题的优化。 ( 9 ) 遗传算法计算简单，功能强。 遗传算法可描述如下： ( 1 ) 定义问题与目标函数f 。 ( 2 ) 选择候选解作为初始种群，每个解用一个二进制位串x 表示，称 哈尔滨工程大学硕士学位论文 为个体。算法中的个体相当于染色体，其元素相当于基因。 ( 3 ) 根据目标函数，对每个染色体x ，i = l ，2 ，p ，计算适值f ( x ) 。 ( 4 ) 为每个染色体制定一个与其适值成正比的繁殖概率q ，i = l ，2 ， p 。 ( 5 ) 根据概率q 选择染色体，所选染色体通过交叉和变异等操作产生 新一代染色体种群。 ( 6 ) 如果找到了满意的解或达到了预定的计算时间，则过程结束。否 则返回( 3 ) 。 2 2 遗传算法的基本操作 h o l l a n d 的遗传算法，通常称为简单遗传算法。操作的简单和作用的强大 是遗传算法的两个主要特点。一般的遗传算法都包含三个基本操作： ( a ) 复制( r e p r o d u c t i o no p e r a t o r ) 复制就是从一个种群中选择适值高的个体放八交配池，准备以此产生新 的种群，这个过程就对应着“物竞天择，适者生存”的原理。选择采用随机 的机制，适值高的个体被选择的概率大，适值低的个体被选择的概率小。 复制过程由两部分组成：首先，根据适应度按照不同的选择方法从群体 中选出一个亲代个体 其次，被选出的亲代个体在未经过任何变化的条件下 从当前代复制到新一代中。 根据适应度，有许多不同的亲代选择方法。 1 ) 适应度一比例选择法。 2 ) 贪婪选择法。 3 ) 级差选择法。 4 ) 竞争选择法。这种方法是：首先从群体中随机选出一组个体，然 后在该组个体中选出一个具有较高适应度的个体。 ( b ) 交叉( c r o s s o v e ro p e r a t o r ) 交叉就是分别用两个个体的基因重新组合成新的一代的操作，使上一代 的优良特性能够传递到下一代，并产生新的特性。复制和交叉使保证种群进 化的主要操作，尤其是交叉，在遗传算法中起着核心作用。 ( c ) 变异( m u t a t i o no p e r a t o r ) 只有复制和交叉还不能保证完全避免丢失一些重要的遗传物质，若某一 代种群的所有个体的某一位均为0 ，则无论怎样复制与交叉，其后代的该位 1 1 哈尔滨一l 程犬s - - 硕士学位论文 均不能变为1 。如果优秀个体的该位为1 ，则这种优秀个体单靠复制与交叉就 不能实现了，而通过变异就可能实现。所谓变异，就是随机地改变一个个体 的某一位，从而产生新一代的个体。变异操作使用的概率应当很小，但它在 种群进化中却起着重要的作用。变异操作不仅可以保证实现搜索的目标，而 且可以提高搜索的效率。变异能使群体中个体结构发生变化。在遗传算法中 变异有利于形成群体结构的多样性，可防止过早出现同一化趋势。变异仅在 单个亲代个体上实麓，选择该亲代个体的概率与归一化适应度成正比例，变 异后产生一个子代个体。 产生变异的方法是：首先在符号表达式的算法树上随机选定一个结点， 该结点称为变异点，变异点可以是树的内节点( 即函数) ，也可以是树的叶子 ( 终止符) ；然后删掉变异点和变异点以下的子树，用随机方式产生一棵新子 树( 方法同初始个体的产生) 插入到该变异点处。该新子树由参数控制，控 制参数主要是子树的大小( 用深度表示) 。 下面通过一个例子说明算法的工作流程。 例：求整数函数f ( x ) = x 2 在区间 0 ，3 1 上取得的最大值点。 解：算法的步骤如下： ( 1 ) 问题是求最大值点，目标函数可取为x 2 。 ( 2 ) 用一个5 位的二进制位串表示个体，对应区间 0 ，3 1 上的3 2 个 整数。随机的选取4 个位串作为初始种群，位串与对应的整数如 下： o l l o l1 3 l l o o o2 4 o 】0 0 08 1 0 0 i l1 9 ( 3 ) 根据目标函数，对每个位串计算适值，如表2 1 所示。 表2 i 初始种群 编号位串参数值目标函数繁殖概率 1 。 0 1 1 0 l1 31 6 90 1 4 4 21 1 0 0 02 45 7 60 4 9 2 30 1 0 0 086 40 0 5 5 41 0 0 i l1 93 6 1 o 3 0 9 总计1 1 7 01 0 0 0 ( 4 ) 为每个位串制定一个与其适值成正比的繁殖概率，如图2 1 所示。 图2 1 繁殖过程中各位串选取区间 ( 5 ) 通过复制、交叉、变异生成下一代种群。复制过程就是按照繁殖概 率选择4 个位串。选择的方法很多，最简单的方法是在区间 0 ，1 内按照繁 殖概率的大小划分成4 个小区间如图2 1 所示，再根据在区间 0 ，1 内均匀 分布的随机变量的取值进行选择，该随机变量的值落在哪个小区间，就选取 哪个个体。 选出的4 个位串是：1 、2 、2 、4 ，将这4 个位串放入交配池。交叉过程分 为两步，首先随机地选择交配的对象，然后随机地选择交叉的位置，进行交 叉操作。选择交叉的位置的方法是，对于位串长度l ，随机地在区问 1 ，l 一】 上产生一个整数k 作为交叉位置。设交配的对象选为1 、2 和2 、4 。对位串1 、2 ， 产生的k = 4 ，交叉过程为 0 1 1 0i10 1 1 0 0 l + 1 1 0 0f0i 1 0 0 l 对位串2 、4 ，产生的k = 2 ，交叉过程为 1 】 0 0 01 1 0 l l l 1 0l0 1 11 0 0 0 0 通过复制和交叉产生的新一代种群，如表2 2 所示。 表2 2 第二代种群 编号位串参数值目标函数 l0 1 1 0 01 21 4 4 21 1 0 0 12 56 2 5 31 1 0 1 l2 77 2 9 41 0 0 0 01 62 5 6 总计 1 7 5 4 自 口 o 从表2 2 中可见，目标函数之和由1 1 7 0 增加到1 7 5 4 ，种群的品质获得了提 现在考虑变异，设变异率取0 0 0 1 ，则每1 0 0 0 位中有一位发生变异。目 1 3 哈尔滨工程大学硕士学位论文 种群中共有4 * 5 - 2 0 位，期望的变异数为2 0 女0 0 0 1 - 0 0 2 位。当前这一代遗传过 程并未发生变异。 2 3 遗传规划概念及其特征 遗传规划提出了一种全新的结构描述方法，其实质是用广义的层次化计 算机程序描述问题。这种广义的计算机程序能根据环境状况动念改变其结构 和大小，在工程中具有广泛的代表性，因为许多工程问题可归结为对特定的 输入产生特定的输出的计算机程序。 遗传规划的任务就是要发现能反映问题实质的计算机程序。因此，在遗 传规划中，解决问题的过程就是在由许多可行的计算机程序组成的搜索空间 中，寻找出一个具有最佳适应度的计算机程序，遗传规划恰好提供了一套寻 找具有最好适应度的计算机程序的方法。 在遗传觌划中，群体由成于上万个计算机程序组成。进化过程遵从优胜 劣汰，适者生存的自然法则。这一过程包括复制、交换及变异等若干个进化 方式。子代计算机程序通过自然选择和遗传机制而产生。 总的看来，遗传规划求解问题时的重要特征如下： ( 1 ) 产生的结果具有层次化的特点。 ( 2 ) 随着进化的延续，个体不断朝问题答案的方向动态地发展。 ( 3 ) 不需事先确定或限制最终答案的结构或大小，遗传规划将根据环境 自动确定。这样，系统观测物理世界的窗口得以扩大，最终导致找到问题的 真实答案。 ( 4 ) 输入、中间结果和输出是阔题的自然描述，无需或者少需对输入数 据的预处理和对输出结果的后处理。由此而产生的计算机程序便是由问题自 然描述的函数组成。 2 4 遗传规划的一般步骤 遗传规划通过下列步骤获得问题的真实答案： ( 1 ) 随机产生初始群体，即产生众多由函数和变量随机组成的计算机程序。 ( 2 ) 运行群体中的每一个计算机程序( 个体) ，根据其解决问题的好坏赋予一 适应度。 ( 3 ) 依据下列两个主要步骤生成新的计算机程序群体： 1 4 哈尔滨工程大学硕十学位论文 ( a ) 把当前一代计算机程序复制成新一代计算机程序，被复制的个体依据 其适应度随机选定。 ( b ) 通过在双亲个体随机选定的部位进行交换产生新的计算机程序，双亲 个体也依据适应度随机选定。 ( 4 ) 迭代执行( 2 ) 、( 3 ) ，直到终止准则满足为止。 图2 2 遗传规划的基本流程 哈尔滨工程人学硕士学位论文 遗传规划的流程图如上图2 2 所示，其中m 表示群体中的个体数，变量i 表 示一个个体，变量g e n 是当前代的代号。 2 5 遗传规划基本原理 ( 1 ) 初始群体生成 初始群体由众多初始个体组成，初始个体为所要解决问题的各种可能的 符号表达式( 算法树) ，它通过随机方法产生。初始个体的生成可采用不同 的方法，不同的方法将产生不同的初始个体。常用的方法有三种，即完全法、 生长法和混合法。 ( 2 ) 适应性度量 适应性是遗传规划中自然选择的驱动力。利用适应性来控制群体中结构 改变的过程。度量适应性的方法有多种：一种是显式方法，另一种是隐式方 法。在显式方法中，借助于具体问题的显式估值方法，对个体赋予一适应性 测度值。常见的适应性测度有下列四种：原始适应度、标准适应度、调整适 应度、归一化适应度。 ( 3 ) 终止准则 终止准则一般有两个：一是当最大容许进化代数g 满足时，进化过程立 即停止；二是当预先设定的问题求解成功条件满足时( 例如：群体中的某个 体标准适应度达到0 ) ，进化过程立即停止。 ( 4 ) 结果标定 结果标定的第一种方法是找出一个全局最佳个体，该最佳个体在进化中 的任意一代群体中都会出现。 另一个可选用的结果标定方法是在进化停止时标定出群体中的一个最佳 个体( 即末代最佳个体) 。 第三种方法是将整个群体或按与适应度成比例选定的一个子群作为最佳 结果，子群大小视具体情况而定。 ( 5 ) 辅助算子 除了复制和交换这两个主要的遗传算子外，还有下列五个辅助遗传算 子：突变( m u t a t i o n ) 、排列( p e r m u z a t i o n ) 、编辑( g d i t i n g ) 、封装 ( b n c a p s u l a t i o n ) 、自残( d e c i m a t i o n ) ，这些算子仅根据需要偶然使用。下面 只简单介绍两个： 哈尔滨工程大学硕士学位论文 排列( p e r m u t a t i o n ) 遗传规划中的排列算子是遗传算法的倒序算子的一种推广。遗传规划中， 排列操作也在单个个体上进行，该个体的选择原则仍同于复制和交换。排列 操作的结果是产生一个新的子代个体。 排列操作方法是：首先选定一个个体的算法树的内节点( 即函数点) ，如 果在选定点的函数有k 个自变量，那么可从k ! 种可能排列中选出一种；然后对 选定点的函数的自变量进行随机排列。 编辑( e d i t i n g ) 在遗传规划中，编辑算子提供了一种编辑和简化符号表达式的手段。一 般的编辑规则如下：如果个函数只有常数自变量，而且它对符号表达式中 其它内容不产生负面影响，那么该函数就用具体的函数值来代替。此外，编 辑操作还应用一套与值域有关的编辑规则集。 编辑操作有两种使用方法：( 1 ) 编辑操作完全在外部执行，与遗传规划 的运行独立。( 2 ) 编辑操作在进化过程中运行，这样在输出的结果中只可观 看编辑后的个体。 2 6 遗传算法在活动规划与资源分配上的应用 如何合理地使用人员、物资、资本等资源是企业降低软件项目成本、缩 短开发周期的关键。对软件项目中的活动进行有效的规划和资源的合理分配 作为企业提高客户需求响应能力、适应市场变化的重要手段，在本质上也是 一种寻求资源得到合理配嚣的手段”3w 。软件项目开发过程中如何将有限的 资源在所有活动之间进行分配，从而使整个软件项目的各个指标达到最优， 同时每个活动则根据分配的资源来组织具体的工作，使它们自己的目标达到 最优，这个问题一直以来是软件工程专家们在深入研究的问题。 本文以遗传算法为基础，研究了软件项目中活动的规划和资源分配问题， 为用计算机技术实现软件项目管理、提高软件质量提供了宝贵的借鉴。 在一些传统的分配方法中，通常考虑的都是单因素最优匹配问题，而事 实上，现实中的问题大都是基于多因素多目标的，如多因素群决策问题等。 候选者对活动的合理分配就是一个多因素群匹配问题，无论是一个活动，办 或是一个人员，都具有不同的特征和要求，相应也就有不同的衡量指标，且 17 哈尔滨1 程大学硕士学位论文 这些指标的表达大多是不确定性的。 本文的研究建立在对活动、角色作如下设定的基础上“k( 1 ) 对于每一 个活动可能由一个或多个人员完成，由多个人员组成的工作小组是一多功能 体，能完成一定的活动或活动序列。( 2 ) 活动、人员都是多属性的实体，相 应有多个衡量指标。( 3 ) 对于某个活动，满足特定条件的人员对浚活动构成 个角色，每一人员都可能成为多角色实体，角色是联系活动与人员问的桥 梁。( 4 ) 软件过程中活动规划与资源分配就是寻求人员对于活动的最优或较 优匹配，使软件项目在预定的时间内，或用更短的时间完成。 软件过程的活动规划与资源分配问题可以描述为：己知一个由n 个相互 关联的活动组成的约束网络，m 个人员负责完成这些活动，m 个人员对n 个活 动的胜任程度用一个m x 阶矩阵来表达，每个活动可以由胜任该项任务的任 意一个人员或者人员的组合柬完成，该任务的完成周期也随着参与人员的不 同而发生相应的变化。求怎样把活动分配给人员才能使得整个项目的完成周 期最短? 目前对这一问题的处理大都先根据经验予以规划，然后借助一些项目管 理软件( 如m i c r o s o f t 的p r o j e c t2 0 0 0 等) 对该规划方案进行检验和评价。 项目管理软件可以检测出方案中存在的资源冲突，方案规划人员根据检测结 果，手工调整规划方案，再用软件去验证，如此反复，直至最后得到一个较 优的结果m “。这种规划方法对规划人员的经验要求很高，而且在项目网络复 杂性增大，人员技能差异明显的时候规划显得愈发复杂。 软件项目开发过程的目标是各个活动的完成周期相对于各指定完成工期 的拖期最小，下级部门的目标是利用上级分配的资源使自己的工期最短。在 考虑各个活动拥有充分的独立资源时，每给定一个资源分配方案，各个活动 就能求出一个相应的最短工期，所以整个问题是求一个最优的分配方案，这 个方案不是一下子就能求解出来的，需要不断的迭代，得出最优解。于是本 文采用面向方案选择的启发式算法：先给定一个或者若干个活动分配方案， 分析其目标函数值，然后遵循某种规律进行迭代，形成新的方案或者方案群 体，分析其目标函数值后继续迭代，逐步向最优解靠近。目前常用的面向方 案选择的启发式算法主要有两种，即模拟退火算法( s i m u l a t e da l g o r i t h m ，s a ) 和遗传算法( g e n e t i ca l g o r i t h m ，g a ) 。s a