基于遗传算法的动态体系结构选择

章鹤松

摘要：随着可移动环境的改变，软件系统正经历许多环境变化，这些变化影响着软件提供的服务质量。为了维持软件的正常性能，我们必须重配置，如果一个应用软件面临环境的变化和有许多的软件体系结构实例时，重配置会变成一个复杂的问题。我们提出了一种新的方法，该方法在应对移动环境的时候可以自动进行体系结构的选择。该方法使软件系统在当前的环境下选出最好的体系结构实例；为了快速地找到最好的实例，我们利用遗传算法来实现选择的过程。此外，我们提供了一种绩效评价来证明该方法在寻找最佳结果时最有效。

关键词：移动环境；软件体系结构；遗传算法；绩效评价

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）34-0165-02

1 概述

用户的满意度代表用户需求和优先权的质量属性，在执行期间，不同用户依赖各自用户的实例进行变化。因此，一个应用程序必须包含不同的功能来适应不同的用户需求；软件体系结构作为软件的宏伟蓝图和支撑骨架，在软件体系中起着决定性的作用[1]，它从全局的角度为系统提供结构组成及其相互关系等信息，为人们宏观把握软件的整体结构和动态演化提供了一条有效途径[2]。本文的研究目标是提供一种方法在环境和需求实时的变化时从大量的候选者中来自动地选择合适的软件体系结构种群。我们使用提出的相互依赖图来精确地制定软件体系结构选择问题。为了处理这个问题，我们利用遗传算法提供了一种新的方法来自动进行软件体系结构的选择。

2 相关实例

移动应用程序被多种因素影响而变化，这种变化可能影响应用程序的性能，为了控制这些变化，我们需要知道用户需求从哪方面影响应用程序。

为了适应用户需求的变化，软件系统有多种变化的函数，如“丰富的GUI”等，如图1所示。这些备选项代表候选函数，使得应用程序可以允许环境和质量的变化，GUI可能会影响应用程序的使用性和持久性，这种影响被量化，量化能把描述关系变得能明确，如HCD对可读性有积极影响（表示为”+”）。（质量属性包括响应，使用性，持久性和可读性）。

3 体系结构的选择问题

我们使用软目标相互依赖图（SIG）制定质量属性，SIG通过无功能需求的框架来制定。一个SIG代表质量属性（如，无功能需求的属性）之间的关系，一个软目标代表一个质量属性，用云状框表示。两个软目标之间的相互依赖用连接两软目标的横线表示，通过识别软目标并连接它们，SIG代表一个应用程序的质量属性。质量属性通过一种质量变量来制定，在SIG的软目标之间，只有最高的质量属性被质量变量考虑，因为它们在我们的方法中作为优先级和价值评估的目标。质量变量[qi]用一个实数来描述质量变量代替的质量属性的应用程序的满意度。一组质量变量Q代表用户的所有满意度，这些质量变量聚集起来代表全部的满意度。一个用来衡量用户所有满意度的值函数U被定义为：

其中，Q是一组质量变量，W是一组权重值，每个[wi]是对应的质量变量[qi]的值，n是质量变量的个数，所有权重值的总和等于1（如[inwi=1]）。

4 基于遗传算法的体系结构选择

4.1 遗传算法的步骤

遗传算法作为一种通用、高效的优化算法，已应用到工程计算的各个领域[3]。在遗传算法中，目标问题被一串基因代替，这个串为染色体，遗传算法使用染色体替换确定染色体的初始种群。重复以下的过程直到一个终止条件的出现：（1）基于一个明确的交叉概率和运行交叉操作来选择父类染色体；（2）基于一个确定的变异概率来选择染色体和突变染色体；（3）评估后代的适应值；（4）从后代中选择下一个后代种群。

4.2 用基因代替体系结构实例

应用遗传算法确定应用程序的主要问题是将问题空间编码为一组染色体，在这种方法里，我们将体系结构实例编码为染色体，因为我们的目的是从一系列实例中寻找到最优的实例，我们使用体系结构决策变量来编码实例，如图2所示。

4.3 交叉和变异

对于交叉和变异操作，我们使用两点交叉和全数字的变异概率。两点交叉获得两个染色体和对每个染色体选择两个位置，然后在两个位置之间交换染色体的数字[4]。执行交叉操作后，该算法执行变异操作，交叉步骤产生的后代的数字通过变异率[Pm]来随机的改变。通过交叉和变异产生的后代被作为下一代的候选种群。

4.4 适应值和选择

执行交叉和变异操作后，下一步是选择操作，该算法评估所有后代和染色体的适应值，适应值更高的保留下来。种群的大小决定了遗传算法的效率和效益，如果种群太小，它不能有效地探寻搜索空间，如果太大可能破坏它的效率。实际地，我们的方法取样至少是[δ-l]个染色体的数量，其中，[δ]是体系结构决策变量中选择项值的平均个数，l是染色体的长度。

通过使用以上章节的描述过程，当环境和需求都改变的时候，我们的方法能够从搜索空间中找到最好的解。

5 算法评估

我们开展两个绩效测试，第一个测试是测量从搜索空间寻找一个最优解需要的运行时间，因为遗传算法是随机的算法，因此很难预测寻找到最优解所需要的时间，然而我们只考虑接近最优解是最好的解，如图3所示。

第二个测试是显示更大数量的体系结构决策变量的结果，我们近似地认为精英染色体与以前的后代相比是最好的或者是最接近最好。在这次测试中，所需要的代数为[10-l-δ]，如图4所示；实际上，超过4秒对用户来说都不会满意，因此，应用程序在使用我们的方法时必须控制体系结构决策变量的数量在40以内。

6 结束语

随着软件市场把它的范围扩大到移动环境时，环境的变化需要移动应用程序改变它们的体系结构配置，通过体系结构选择问题来对该问题建模，一个移动应用程序在当前的环境和用户需求下搜索它的可能的体系结构实例和选择一个最优解。

我们基于遗传算法对体系结构选择问题来定义一种新颖的方法，该方法使得软件系统能够自动的搜索可能的体系结构实例（搜索空间），在很短的时间内和在当前的环境和需求下找到一个最优实例。该方法的评估表明，即使应用程序需要搜索相当多的实例时，我们的方法都可以计算一个应用程序的体系结构选择。

参考文献：

[1] 刘晓斌，杨贯中，欧阳柳波，等.软件体系结构动态演化的元胞自动机模型研究[J].计算机工程与应用，2015（9）.

[2] 徐洪珍，曾国荪，陈波.软件体系结构动态演化的条件超图文法及分析[J].软件学报，2011（6）.

[3] 王春水，肖学柱，陈汉明.遗传算法的应用举例[J].计算机仿真，2005（6）.

[4] 韩瑞锋. 遗传算法原理与应用实例[M]. 北京：兵器工业出版社， 2010.