软件发布规划遗传算法探讨

王志刚++高磊

摘 要：好的软件发布规划可以有效改善软件质量，降低开发费用。然而，软件发布规划是一个不良问题，适宜采用进化方法求解。遗传算法是一种进化方法，其基本原则是“优胜劣汰，适者生存”，将问题中的个体看成染色体，通过遗传变异等一系列模拟生物的进化过程来寻求最优解。将软件发布规划问题与遗传算法相结合，构造可行的遗传变异进化方式和遗传算法，为实际求解软件发布规划问题提供可行操作。

关键词关键词：软件发布规划；进化；遗传算法；染色体

DOIDOI：10.11907/rjdk.162416

中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2016）011005603

0 引言

软件发布规划问题中存在许多不确定因素，是一种典型的不良问题，该问题也是几十年来许多计算机科学家致力研究的一个问题。较早研究软件最优发布问题的是A·Goel和K·Okumoto，他们提出了软件可靠性GO 模型，在此基础上，还提出了软件期望总费用模型；GO模型成为很多软件科研人员后续研究和改进的基础。Koch和Kubat从成本和利润角度出发，提出了一种基于JM的可靠性模型，并提出了惩罚费用概念[1]。文献[2]对软件发布过程中的关键因素进行了研究，在软件安全生命周期的基础上提出了一个改进的适合于中小型企业的软件安全开发流程。Saliu O和Ruhe G[3]提出了基于进化的软件发布决策支持模型。目前这些软件发布决策模型中存在的不足是对软件发布规划过程中难以定性的软因素没有进行全面考量。

本文在软件发布规划问题形式化的基础上，运用遗传算法研究软件发布规划问题，探讨遗传算法在软件发布规划求解时的算法适应性问题及处理流程。遗传算法的逐步适应和多样化，也使其适合解决软件发布规划这类不良问题。

1 基本思想

遗传算法从一个初始种群开始，随机全局搜索，它遵循“适者生存，优胜劣汰”的生物学进化原理，对优化的种群解集进行优化筛选与迭代，不断进化，最终得到接近最优的解。在每一轮进化开始之前，需要查找和选择当前种群中适应度较大的个体，适应度越大说明基因越好。然后借助遗传算子进行组合交叉变异等操作，从而得到新的种群；种群中适应度低的个体将被淘汰掉，其整体的适应度也会不断提高，迭代过程直到满足条件为止；新生成的种群比父代更加优秀，能更好地适应生存环境；最终获得的种群将是历代种群中最优秀的，通过解码还原便得到解决问题的近似最优解。遗传进化的每个步骤被抽象为数学运算过程，种群中的个体称为染色体，用一串符号来代替。算法开始时随机初始化一个N在 150～500 之间的种群（父个体 1、父个体 2…父个体 N），并计算每个个体的适应度函数，再根据优化原则衍生进化与计算下一代。

1.1 编码方法

编码方法影响基因空间到问题表现空间的映射和遗传算子对个体的操作。目前针对不同问题有多种不同的编码方式，常用的编码有二进制、实数、证书或者字母排列和一般数据结构；根据结构不同还可以分为一维或二维编码。

1.2 算法的基本操作

遗传基因产生子代的过程有选择、交叉和变异等三种操作。一般的运算过程会用到其中的2～3种操作。

（1）选择。又称复制，是在父代种群中选取优秀的个体来生产新的种群。选择目的是让优良的个体有机会通过配对交叉繁殖遗传到下一代。选择策略跟编码方式无关，由适应度决定，根据个体的适应度值以一定的规则或方法来选择优良的个体，主要原则是按适应度比例或者排序进行计算。

轮盘赌算法[4]是一种常用的回放式随机取样方法。在该算法作用下，每个染色体进入下一代的概率是它的适应度值在所有染色体适应度值之和中占的比例，适应度越高被选中的可能性就越大，进入下一代的机会也越大。每个染色体在轮盘中所占扇区面积和其适应度成正比；随机转动轮盘，当轮盘停止转动时指针所指扇区对应的个体被选中。这个方法选中适应度比较高的个体的机会较多，但也存在问题，由于种群规模限制和随机操作等原因，使得个体实际被选中的次数与期望值之间可能存在一定的误差，适应度相近的个体不一定会被选中，适应度小的个体也有机会被选中，这样保证了群体的多样性。

选择操作还有（μ+λ）选择、竞争选择、稳态复制、排序与变换比例和共享等。

（2）交叉。所谓交叉是指按某种方式交换两个相互配对染色体的部分基因，从而产生两个新的染色体。交叉运算是遗传算法区别于其它进化运算的重要特征。

交叉运算首先需运用随机方式将种群中的染色体进行两两配对，如果种群中有N个染色体，将这N个染色体配成N/2对，交叉操作在这些配好对的染色体对之间进行。

（3）变异。选择和交叉操作并不能保证不遗漏一些重要的遗传信息，变异操作能较好地减少遗漏。变异操作首先在群体中随机选择一个染色体，然后以一定的概率随机改变其编码串中某个码位的值，这个概率值介于0.001与0.1之间，称之为变异概率。[5]

自然界中，生物个体由于偶然因素的作用发生基因突变，可能导致染色体的适应度增强或降低，但能增加生物遗传基因的多样性。遗传算法中的变异虽然没有交叉操作那么重要，却为产生新个体提供了机会，可起到恢复位串多样性的作用，通过和交叉运算相配合能适当提高遗传算法的搜索效率。

变异方法主要有基本位变异、有效基因变异、自适应有效基因变异、概率自调整变异、均匀变异和非均匀变异等。其中基本位变异相对简单和常用。

1.3 适应度函数

适应度函数（评价函数）是根据目标函数确定的用于区分群体总个体好坏的标准，是算法演化过程的驱动力和自然选择的重要依据。适应度函数的值一般为非负，因为在绝大多数情况下都期望适应度值越大越好。而目标函数则正负都有可能，也即求最大值或最小值问题，还有多目标同时需要优化的情况。基于以上原因，需要将目标函数与适应度函数进行一定转换，以满足适应度函数的要求。染色体适应度值的计算方法如下：

（1）对染色体编码串解码解析处理，获得染色体的表现型。

（2）用目标函数计算表现型的值。

（3）根据问题的类型，由目标函数值按一定的转换规则求出染色体的适应度值。

2 软件发布规划问题的遗传进化描述

不良问题存在很多不确定性因素使得研究的问题很难描述和得以解决。这类问题主要有两个特点：一是没有明确的形式化方法用以表达问题；二是没有明确的停止规则。依据这两个特点可以将软件发布规划划为不良问题[6]。进化是一个逐渐求精和力求多样化的过程，其计算算法是一种软计算方法，涉及计算搜索、学习、优化和建模方法等。在决策问题求解过程中，所有元素都会不断发生变化，所以决策问题的演化，适宜采用进化算法推导。

软件发布规划决策变量用f（i）来表示某个特征，则N个特征集合是{f（1），f（2），…，f（N）}，规划在K个发布计划中发布。这个发布规划的特征用决策向量X来描述，X=（x（1），x（2），…，x（N）），如果特征f（i）在第k次发布，则x（i）=k[7]。

规划中的某个特征发布阶段的值即x（i）对应着遗传算法的基因，向量X构成一个染色体，通过遗传算法的迭代进化计算过程产生的最终后代，便是软件发布规划问题所需要的解集。

3 求解软件发布规划问题的遗传算法设计

3.1 算法整体流程

基于遗传算法的软件发布规划问题的求解过程如下：

（1）初始化参数。

（2）随机创建n个染色体，构造种群。

（3）检测种群冲突，若有冲突则消除，无则进入（4）。

（4）计算染色体的适应度值，若达到终止条件则转到（8）。

（5）根据计算得到的适应度值进行选择操作，得到中间代。

（6）选择符合要求的个体进行交叉和变异等操作。

（7）用新种群替换旧种群，转到（3）。

（8）对获得的解集进行人工评估，选出最优方案。

算法流程如图1所示。

3.2 编码方式

为了适应软件发布规划过程中的编码和解码，便于进行遗传迭代过程中交叉变异等操作，软件发布规划问题的解决过程采取实数编码方式。

4 结语

本文运用遗传算法对软件发布规划问题进行了研究，基于遗传算法这种进化的方法设计了解决软件发布规划获取发布规划决策的算法。从理论上讲，通过最后的评估计算，求得的解也只是最优推荐解，因为整个规划过程中存在一些难以精确的因素，所以通过这种方式的计算也只能是尽力达到最优。

参考文献：

[1] 胡海宏.软件可靠性模型与软件最优发布问题的研究[D].南京：南京邮电大学，2011.

[2] 冯博.软件安全开发关键技术的研究和现实[D].北京：北京邮电大学，2010.

[3] SALIU O， RUHE G. Supporting software release planning decisions for evolving systems[C].Proceedings of the 29th IEEE/NASA Software Engineering Workshop. Greenbelt， MD， USA， 2005：1424.

[4] 谢景燕， 安金霞， 朱纪洪.考虑不完美排错情况的NHPP类软件可靠性增长模型[J]. 软件学报，2010（5）：942949.

[5] 汪晓飞.基于多维编码方案的遗传算法在高校排课系统中的应用[D].成都：四川师范大学，2008.

[6] 王志刚，高磊.软件发布规划的迭代求解过程[J].现代计算机，2013（12）：3941.

[7] 王志刚，高磊.软件发布规划的形式化探讨[J].计算机时代，2013（12）：1214.

[8] 王志刚，高磊.软件发布规划案例研究[J].软件导刊，2014（12）：13.

[9] 胡华军.软件最优发布时间决策研究[D].成都：电子科技大学，2009.

[10] ZIY H， RICHARDSON DJ， KLSCH R. The uncertainty principle in software engineering[R]. Technical report UCITR9633， University of California， Irvine， 1996.

[11] CARLSHAMRE P. Release planning in marketdriven software product development：provoking an understanding[J]. Requirements Engineering，2002（3）：139151.

[12] RUHE G， NGOTHE A. Hybrid intelligence in software release planning[J]. International journal on hybrid intelligent systems. 2004（1）：99110.

[13] DU G， RICHTER M， AND RUHE G. An explanation oriented dialogue approach and its application to wicked planning problems[J]. Journal of Computing and informatics， 2006（25）：10011027.

[14] 邓铁清，任艮全，刘英博. 基于遗传算法的工作流个人工作列表资源调度[J].软件学报，2012， 23（7）：17021716.

[15] 滕云龙.软件可靠性与费用模型的研究[D].成都：电子科技大学，2008.

[16] 杨标. 软件可靠性模型与软件最优发布问题的研究[D].成都：电子科技大学，2007.

[17] 冯静，朱小冬，甘茂治.软件发布周期费用估算方法研究[J]. 微计算机信息，2006，22（7）：288290.

[18] 刘甜.软件发布机制的研究与应用[D]. 石家庄：石家庄铁道大学，2014.

[19] 许琦.基于遗传算法的高校排课问题的研究[D].广州：华南理工大学，2012.

[20] 李云.基于遗传算法的动态路径优化[D].太原：太原理工大学，2013.

（责任编辑：陈福时）