下载文档原格式
基于多态蚁群算法的测试用例自动生成
陈明师;刘晓洁;李涛
【期刊名称】《计算机应用研究》
【年(卷),期】2009(026)006
【摘要】提出了一种基于多态蚁群算法的测试数据自动生成方法.该方法使用二进制编码将输入数据转换为位串;然后在蚁群算法的基础上将蚁群分为三类,据其信息素的不同采用不同的移动准则,重点对侦察蚁和搜索蚁进行功能分析.将局部搜索与全局搜索结合起来,结合路径的相似度,缩小搜索空间;根据适应度函数确定最好路径,既解决局部最优化问题,又提高收敛效率.与基本蚁群算法对比,其结果显示该方法效率优于基本蚁群算法.
【总页数】2页(P2347-2348)
【作者】陈明师;刘晓洁;李涛
【作者单位】四川大学,计算机学院,成都,610065;四川大学,计算机学院,成
都,610065;四川大学,计算机学院,成都,610065
【正文语种】中文
【中图分类】TP311
【相关文献】
1.基于遗传蚁群算法的软件测试用例自动生成 [J], 王文;王雷
2.基于通信协议的接口测试用例自动生成框架 [J], 刘逻; 郭立红; 陈媛; 王俊杰
3.基于IFML元模型自动生成RIA用户界面测试用例研究 [J], 李丹丹;刘晓燕;曹荣
凯;严馨
4.基于遗传算法的测试用例自动生成方法综述 [J], 赫彦文;刘紫阳;李建义;彭新宇
5.基于混沌遗传算法的测试用例自动生成研究 [J], 黄陈辉;吴海涛;阮江涛;钱程因版权原因，仅展示原文概要，查看原文内容请购买。
[代码说明]蚁群算法解决VRP问题[算法说明]首先实现一个ant蚂蚁类，用此蚂蚁类实现搜索。
算法按照tsp问题去解决，但是在最后计算路径的时候有区别。
比如有10个城市,城市1是配送站，蚂蚁搜索的得到的路径是1,3,5,9,4,10,2,6,8,7。
计算路径的时候把城市依次放入派送线路中,每放入一个城市前，检查该城市放入后是否会超过车辆最大载重如果没有超过就放入如果超过，就重新开始一条派送路线……直到最后一个城市放完就会得到多条派送路线这样处理比较简单可以把vrp问题转为tsp问题求解但是实际效果还需要验证。
[作者]Wugsh@2011.12.16wuguangsheng@guangsheng.wu@%}%清除所有变量和类的定义clear;clear classes;%蚁群算法参数(全局变量)global ALPHA; %启发因子global BETA; %期望因子global ANT_COUNT; %蚂蚁数量global CITY_COUNT; %城市数量global RHO; %信息素残留系数!!!global IT_COUNT; %迭代次数global DAry; %两两城市间距离global TAry; %两两城市间信息素global CITYW Ary; %城市货物需求量global VW; %车辆最大载重%===================================================================%设置参数变量值ALPHA=1.0;BETA=2.0;RHO=0.95;IT_COUNT=200;VW=100;%=================================================================== %读取数据并根据读取的数据设置其他参数load data.txt; %从文本文件加载数据city_xy_ary=data(:,2:3); %得到城市的坐标数据CITYW Ary=data(:,4); %得到每个城市的货物需求量CITY_COUNT=length(CITYW Ary); %得到城市数量(包括配送站在内)ANT_COUNT=round(CITY_COUNT*2/3)+1; %根据城市数量设置蚂蚁数量,一般设置为城市数量的2/3%MMAS信息素参数%计算最大信息素和最小信息素之间的比值PBest=0.05; %蚂蚁一次搜索找到最优解的概率temp=PBest^(1/CITY_COUNT);TRate=(1-temp)/((CITY_COUNT/2-1)*temp); %最大信息素和最小信息素之间的比值%信息素的最大最小值开始的时候设置成多大无所谓%第一次搜索完成会生成一个最优解,然后用这个解会重新产生最大最小值Tmax=1; %信息素最大值Tmin=Tmax*TRate; %信息素最小值% 计算两两城市间距离DAry=zeros(CITY_COUNT);for i=1:CITY_COUNTfor j=1:CITY_COUNTDAry(i,j)=sqrt((city_xy_ary(i,1)-city_xy_ary(j,1))^2+(city_xy_ary(i,2)-city_xy_ary(j,2))^2);endend% 初始化城市间信息素TAry=zeros(CITY_COUNT);TAry=TAry+Tmax;%===================================================================%初始化随机种子rand('state', sum(100*clock));%另一种方法%rand('twister',sum(100*clock))%定义蚂蚁mayi=ant();Best_Path_Length=10e9; %最佳路径长度，先设置成一个很大的值tm1=datenum(clock); %记录算法开始执行时的时间FoundBetter=0; %一次搜索是否有更优解产生%开始搜索for i=1:IT_COUNTfprintf('开始第%d次搜索, 剩余%d次',i,IT_COUNT-i);FoundBetter=0; %搜索前先置为没有更优解产生for j=1:ANT_COUNT%蚂蚁搜索一次mayi=Search(mayi);%得到蚂蚁搜索路径长度Length_Ary(j)=get(mayi,'path_length');%得到蚂蚁搜索的路径Path_Ary{j}=get(mayi,'path');%保存最优解if (Length_Ary(j) < Best_Path_Length);Best_Path_Length=Length_Ary(j);Best_Path=Path_Ary{j};%有更优解产生,设置标志FoundBetter=1;endend%有更好解产生,进行2-OPT优化if (FoundBetter == 1)fprintf(' , 本次搜索找到更好解!');Best_Path=opt2(Best_Path);Best_Path_Length=PathLength(Best_Path);end%-------------------------------------------------------------%全部蚂蚁搜索完一次，更新环境信息素TAry=TAry*RHO;%只有全局最优蚂蚁释放信息素dbQ=1/Best_Path_Length;for k=2:CITY_COUNTm=Best_Path(k-1); %上一个城市编号n=Best_Path(k); %下一个城市编号%更新路径上的信息素TAry(m,n)=TAry(m,n)+dbQ;TAry(n,m)=TAry(m,n);end%更新最后城市返回出发城市路径上的信息素TAry(n,1)=TAry(n,1)+dbQ;TAry(1,n)=TAry(n,1);%-------------------------------------------------------------%更新完信息素,进行边界检查Tmax=1/((1-RHO)*Best_Path_Length); %信息素最大值Tmin=Tmax*TRate; %信息素最小值for m=1:CITY_COUNTfor n=1:CITY_COUNTif (TAry(m,n)>Tmax)TAry(m,n)=Tmax;endif (TAry(m,n)<Tmin)TAry(m,n)=Tmin;endendend%-------------------------------------------------------------%换行fprintf('\n');endtm2=datenum(clock); %记录算法结束执行时的时间fprintf('\n搜索完成, 用时%.3f秒, 最佳路径长为%.3f , 派送方案如下:：\n\n[1]',(tm2-tm1)*86400,Best_Path_Length);%=================================================================== %输出结果dbW=0;for i=2:CITY_COUNTm=Best_Path(i-1); %上一个城市n=Best_Path(i); %当前城市if (dbW+CITYW Ary(n)>VW) %运送的货物超过限制fprintf(' (满载率: %.1f%%)\n[1]-%d',dbW*100/VW,n);dbW=CITYW Ary(n); %运输的重量等于该城市的需求量else %没有超过限制fprintf('-%d',n);dbW=dbW+CITYWAry(n); %运输的重量加上该城市的需求量endendfprintf(' (满载率: %.1f%%)',dbW*100/VW);fprintf('\n\n');%====== [程序结束]===================================================== %对结果进行2-OPT优化function f=opt2(Line)%数组长度size=length(Line);NewLine=Line; % 返回结果先设置成原来路径Flag=1;while (Flag == 1)Flag=0;for i=1:size-2a=Line(1,1:i); %路径前段b=fliplr(Line(1,i+1:size)); %路径后段倒置c=cat(2,a,b); %新路径%新路径更好就替换if (PathLength(c)<PathLength(NewLine))NewLine=c;Flag=1;fprintf('\n======================= 2-OPT 优化成功! ===');endendend%返回结果f=NewLine;end1 14.5 13.0 0.02 12.8 8.5 0.13 18.4 3.4 0.44 15.4 16.6 1.25 18.9 15.2 1.56 15.5 11.6 0.87 3.9 10.6 1.38 10.6 7.6 1.79 8.6 8.4 0.610 12.5 2.1 1.211 13.8 5.2 0.412 6.7 16.9 0.913 14.8 2.6 1.314 1.8 8.7 1.315 17.1 11.0 1.916 7.4 1.0 1.717 0.2 2.8 1.118 11.9 19.8 1.519 13.2 15.1 1.620 6.4 5.6 1.721 9.6 14.8 1.51 0 0 02 3639 1315 123 4177 2244 134 3712 1399 145 3488 1535 536 3326 1556 457 3238 1229 228 4196 1004 119 4312 790 1110 4386 570 5611 3007 1970 4312 2562 1756 2413 2788 1491 6514 2381 1676 3215 1332 695 5616 3715 1678 6717 3918 2179 6718 4061 2370 2219 3780 2212 3420 3676 2578 5621 4029 2838 2422 4263 2931 2523 3429 1908 2624 3507 2367 4625 3394 2643 8726 3439 3201 3327 2935 3240 2228 3140 3550 2429 2545 2357 5630 2778 2826 2431 2370 2975 4332 1304 2312 12。
改进信息素蚁群算法测试用例生成技术李强，孙龙(工业和信息化部电子第五研究所，广州510610)摘要：软件测试用例的设计和生成是整个测试工作的重点和难点，往往需要耗费大量的时间，为了减少测试工作量，防止测试用例数目过多而导致爆炸，在传统蚁群算法的基础上，针对传统蚁群算法 初期搜索效率低、搜索信息素相对匮乏、搜索模型过于简单、正反馈机制容易产生停滞早熟现象等问 题，对蚁群算法进行系统化改进，建立蚁群搜索路径，改进信息素挥发系数，并将其用于软件测试用 例的自动生成，提高软件测试效率，降低测试代价。
关键词：蚁群算法；软件测试；用例生成；蚁群路径1概述软件测试是根据软件开发各阶段的需求说明和程序 的内部结构而精心设计一组测试用例，并利用这些测 试用例运行程序，以发现程序错误的过程'测试用例 集在软件测试过程中扮演着重要角色，直接决定着软件 的质量。
实际工程中测试用例集生成工作往往有极大的 盲目性，一些问题日益凸显，例如测试用例数量多，测 试覆盖率难提升，测试成本高等，因此，如何科学高效 地自动生成测试用例成为软件测试的研究重点。
多年 来，许多研究者对测试用例自动生成进行了广泛而深入 的研究，并取得了大量的研究成果，蚁群算法是一种模 拟进化算法，初步的研究表明该算法具有很好寻优性 能，且具有易于与其他算法融合、鲁棒性强、自适应自 组织能力强等优点。
Singh[2]将一种基于蚁群算法的白盒 测试技术与现有的黑白盒测试技术做比较，得出基于蚁 群算法的路径覆盖率更高的结论。
如今，蚁群算法已在 测试用例生成技术得到了很广泛的应用，但由于算法理 论本身的不足，缺少闭环反馈，蚁群的运动过程将趋向 于随机移动，使得初期搜索效率低，搜索信息素相对匮 乏，搜索模型过于简单，正反馈机制容易产生停滞早熟 现象等问题[3-5]。
为了克服蚁群算法的不足，将对蚁群算 法的信息素挥发系数策略进行改进，并构建蚁群搜索路 径模型，以达到提升搜索效率，抑制早熟、提高生成用 例覆盖率。
收稿日期：2011-09-15；修回日期：2011-10-26基金项目：国家自然科学基金资助项目（60973118）作者简介：聂鹏（1977-），男，陕西汉中人，博士研究生，主要研究方向为软件确保、软件测试、软件可靠性（zeanet@163．com ）；耿技（1963-），男，安徽合肥人，教授，博士研究生，主要研究方向为系统软件、软件确保、软件可靠性；秦志光（1956-），男，四川隆昌人，教授，博导，主要研究方向为计算机开放系统与网络安全性、信息系统安全．软件测试用例自动生成算法综述*聂鹏1，2，耿技1，秦志光1（1．电子科技大学计算机科学与工程学院，成都611731；2．江西财经大学，南昌330013）摘要：按照测试用例自动生成技术的不同，将测试用例自动生成算法分为随机、遗传、蚁群、粒子群四类，对上述各类算法的现状和进展进行介绍、分析和探讨。
最后，对软件测试用例自动生成的研究进行了总结。
关键词：软件测试；测试用例生成；随机测试；启发性测试中图分类号：TP311文献标志码：A文章编号：1001-3695（2012）02-0401-05doi ：10．3969/j．issn．1001-3695．2012．02．001Survey on automatic test case generation algorithms for software testingNIE Peng 1，2，GENG Ji 1，QIN Zhi-guang 1（1．School of Computer Science ＆Engineering ，University of Electronic Science ＆Technology of China ，Chengdu 611731，China ；2．Jiangxi University of Finance ＆Economics ，Nanchang 330013，China ）Abstract ：Based on the different techniques for the automatic test case generations ，there were four categories ，including ran-dom test algorithms ，genetic algorithms ，ant colony optimization algorithms ，and particle swarm optimization algorithms．Thispaper introduced ，analyzed ，and discussed the status and overview of the four categories．Finally ，it drew the conclusions for the automatic test case generation algorithms．Key words ：software testing ；test case generation ；random test ；heuristic test0引言IEEE 计算机协会在IEEE Std 829—1983［1］中对软件测试给出了定义：通过人工测试或自动测试的手段对软件的质量进行度量，用于检验被测软件实际运行结果是否与设计软件时的初衷相一致。
２００７，４３（１２）面向路径的测试是软件结构测试的主要测试方式之一。
面向路径的测试数据自动生成问题是软件测试的基本问题，可描述为：给定一个程序Ｐ和Ｐ中一条路经Ｗ，设Ｐ的输入空间为Ｄ，求ｘ∈Ｄ，使得Ｐ以ｘ为输入运行所经过的路径为Ｗ。
为了解决此问题人们提出了许多种方法：符号执行法、迭代松弛法和启发式算法。
用于生成路经测试数据的启发式算法包括禁忌搜索［１］、模拟退火［２］和遗传算法［３，４］。
和许多传统方法相比，模拟退火和遗传算法具有较高的适用性和高效性，但是任何方法都有其缺陷或不足，遗传算法存在局部搜索能力差及其早熟现象，而模拟退火算法存在全局搜索能力差、效率不高的问题。
为了弥补算法的不足，一种自然的想法是算法之间相互借鉴，实现优势互补。
文献［５］提出了模拟退火遗传算法，将模拟退火操作引入遗传算法，取得了一定的效果，生成测试数据的效率高于遗传算法。
另外一种更有研究意义的方法是遗传算法和蚁群算法相互借鉴生成软件测试数据。
蚁群算法是一种新兴的启发式算法，是由ＭａｒｃｏＤｏｒｉｇｏ等人提出的仿生寻优算法［６］。
参加寻径的蚂蚁通过留在链路上的信息素交互来选择新的路由，从而达到寻优的目的。
蚁群算法是一个增强型学习系统，具有分布式计算、易于与其它算法相融合、鲁棒性强等优点，在武器—目标分配、集成电路设计、网络路由选择、规划设计等领域的应用中表现出相当好的性能。
虽然蚁群算法在许多领域取得比较满意的结果，但在软件测试数据自动生成方面的研究还不曾见到。
蚁群算法虽然具有许多优点，但是由于搜索初期信息素相对匮乏，导致算法的搜索效率降低，正反馈机制容易产生停滞早熟现象。
为了克服蚁群算法的不足，可以引入遗传算法的变异操作，增加搜索的随机性、快速性和全局收敛性。
本文针对面向路径的测试数据自动生成特点，研究蚁群算法及其借鉴遗传算法的变异操作，用于测试数据自动生成问题，并和模拟退火遗传算法进行比较。
１蚂蚁路径网络模型构建蚁群算法生成测试数据首先要解决的问题是知识表示问题，即如何将被测程序的输入空间映射到适应于蚁群算法的蚂蚁路径。
为了适应输入空间中不同的数据结构的变量，通过位串形式离散化输入变量来构建映射模型，如图１所示。
设被测程序输入空间Ｄ的某一输入变量ｘ（ｘ１，ｘ２，…，ｘｎ），通过编码规则Ｃ转换为位串ｂ，Ｃ：ｘ→ｂ；ｂ与蚂蚁路径有向图Ｇ的一条路径ｐ相对应，Ｇ：ｂ→ｐ；经过蚁群算法得到新的路径ｐ′，ＡＣＡ：ｐ→ｐ′，再通过解码Ｃ－１将其对应的位串ｂ′转换为输入变量，Ｃ－１：ｂ′→ｘ′。
编码规则可以采用二进制编码或格雷编码，基于蚁群算法的软件测试数据自动生成傅博ＦＵＢｏ北京航空航天大学系统工程系，北京１０００８３ＤｅｐａｒｔｍｅｎｔｏｆＳｙｓｔｅｍＥｎｇｉｎｅｅｒｉｎｇ，ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＡｅｒｏｎａｕｔｉｃｓａｎｄＡｓｔｒｏｎａｕｔｉｃｓ，Ｂｅｉｊｉｎｇ１０００８３，ＣｈｉｎａＦＵＢｏ．Ａｕｔｏｍａｔｅｄｓｏｆｔｗａｒｅｔｅｓｔｄａｔａｇｅｎｅｒａｔｉｏｎｂａｓｅｄｏｎａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（１２）：９７－９９．Ａｂｓｔｒａｃｔ：Ｔｈｉｓｓｔｕｄｙｐｒｏｐｏｓｅｓａｋｉｎｄｏｆａｕｔｏｍａｔｉｃｔｅｓｔｄａｔａｇｅｎｅｒａｔｉｏｎｍｅｔｈｏｄｂａｓｅｄｏｎａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ．Ｂｙｕｓｉｎｇｂｉｔｃｏｄｉｎｇ，ａｍｏｄｅｌｆｒｏｍｉｎｐｕｔｄｏｍａｉｎｏｆｔｈｅｓｏｆｔｗａｒｅｕｎｄｅｒｔｅｓｔｔｏａｎｔｐａｔｈｓｏｆｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓｅｓｔａｂｌｉｓｈｅｄ．Ｐｈｅｒｏｍｏｎｅｔｒａｉｌｓｏｆｔｈｅｐａｔｈｓｄｅｐｅｎｄｏｎｂｒａｎｃｈｆｕｎｃｔｉｏｎｓｏｆｐｒｏｇｒａｍｉｎｓｔｒｕｍｅｎｔａｔｉｏｎ．Ａｃｃｏｒｄｉｎｇｔｏｔｈｅｐｈｅｒｏｍｏｎｅｔｒａｉｌｓ，ａｎｔｓｃｏｏｐｅｒａｔｅｔｏｆｉｎｄｔｈｅｂｅｓｔｐａｔｈｔｏｇｅｎｅｒａｔｅｓｏｆｔｗａｒｅｔｅｓｔｄａｔａ．Ｔｏｉｍｐｒｏｖｅａｎｔｐａｔｈｄｉｖｅｒｓｉｔｙａｎｄｄｅｃｒｅａｓｅｔｈｅｄｅｇｒｅｅｓｏｆｔｈｅｐｒｅｃｏｃｉｔｙａｎｄｓｔａｇｎａｔｉｏｎ，ａｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒａｎｄａｎａｄａｐｔｉｖｅｐｈｅｒｏｍｏｎｅｅｖａｐｏｒａｔｉｏｎｇｅｎｅａｒｅａｐｐｌｉｅｄ．ＣｏｍｐａｒａｔｉｖｅｅｘｐｅｒｉｍｅｎｔｓａｒｅｐｅｒｆｏｒｍｅｄｂｅｔｗｅｅｎａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍａｎｄＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ（ＳＡＧＡ）．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｉｎｄｉｃａｔｅｔｈａｔａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｏｕｔｐｅｒｆｏｒｍｓＳＡＧＡｉｎｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｔｅｓｔｄａｔａｇｅｎｅｒａｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：ｓｏｆｔｗａｒｅｔｅｓｔｉｎｇ；ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ａｕｔｏｍａｔｉｃｔｅｓｔｄａｔａｇｅｎｅｒａｔｉｏｎ摘要：提出了一种基于蚁群算法的测试数据自动生成方法。
该方法采用位串形式编码，实现了被测程序输入空间到蚂蚁路径网络的映射模型。
根据程序插装函数定义的路径信息素轨迹强度，蚂蚁进行群体协作搜索最佳路径，生成测试数据。
在基本蚁群算法基础上，通过引入变异算子和自适应挥发系数，提高了蚂蚁路径的多样性，克服了早熟停滞的缺陷。
和模拟退火遗传算法进行了对比实验研究，结果表明了该方法的可行性，生成测试数据的效率优于模拟退火遗传算法。
关键词：软件测试；蚁群算法；遗传算法；测试数据自动生成文章编号：１００２－８３３１（２００７）１２－００９７－０３文献标识码：Ａ中图分类号：ＴＰ３１１作者简介：傅博（１９６４－），男，高级工程师，博士研究生，主要研究方向为软件可靠性和人工智能。
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用９７２００７，４３（１２）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用二进制编码是一种较好的编码规则，它具有表达简单、实施快捷等优点。
设输入变量ｘ的输入参数ｘｉ（ｉ＝１，２，…，ｎ）的二进制编码字长为Ｎｉ，则ｘ的级联位串字长为：Ｎ＝ｎｉ＝１!Ｎｉ。
定义蚂蚁路径有向图Ｇ＝（Ｖ，Ｅ），节点集Ｖ＝｛ｖ１，ｖ２，…，ｖ２Ｎ｝，有向边集Ｅ＝｛ｅ１，ｅ２，…，ｅ４Ｎ｝。
其中：ｅ１＝（ｖ１，ｖ２），ｅ２＝（ｖ１，ｖＮ＋２），…，ｅ４Ｎ＝（ｖ２Ｎ，ｖＮ＋１）。
一个含有Ｎ条有向边的序列构成一条路径，用含有Ｎ个节点的序列表示为：ｐ（ｖｓ，ｖｔ）＝｛ｖ１′，ｖ２′，…，ｖｊ′，…，ｖＮ′｝，其中起点ｖｓ和终点ｖｔ均为ｖ１′（ｓ＝ｔ＝１，２，…，２Ｎ，ｊ＝１，２，…，Ｎ）。
当ｖｊ′为ｖｋ，则ｖｊ＋１′（当ｊ＝Ｎ时，ｖｊ＋１′＝ｖ１′）为：ｖｊ＋１′＝（ｖｋ＋１ＯＲｖｋ＋１＋Ｎ），１≤ｋ≤Ｎ－１（ｖｋ＋１ＯＲｖｋ＋１－Ｎ），１＋Ｎ≤ｋ≤２Ｎ－１（ｖ１ＯＲｖ１＋Ｎ），ｋ＝ＮＯＲｋ＝２#%%%$%%%&Ｎ（１）蚂蚁路径网络由Ｎ层节点组成的有向图，每层两个节点分别表示二进制位串取值为０和１的状态。
因此，有向图中每一条路径对应一个字长为Ｎ的二进制位串，而该位串对应输入域中的一个输入变量。
２蚁群算法生成软件测试数据原理蚁群算法生成软件测试数据是在知识表示的基础上，应用蚁群算法完成知识推理，生成所需要的测试数据。
基本原理是将一群蚂蚁智能体放在路径有向图Ｇ中，通过蚂蚁移动、释放信息素等行动搜索最优路径ｐ＊，从而寻找符合被测程序中选定程序路径Ｗ的输入变量。
基本原理如图２所示。
适应度评价依赖于程序路径的分支谓词，采用程序插装技术，按照分支谓词的特点插入分支判断函数。
设被测程序选定路径上有ｍ个分支点，ｎ个参数，则ｍ个分支函数为：Ｆ＝ｍｉ＝１!!（"ｉ）（２）其中!（ｘ）＝０，ｘ≤０ｘ，ｘ＞’０。
根据适应度的评价结果，对蚂蚁经过的路径按适应度的大小释放信息素。
蚂蚁依据路径上的信息素轨迹强度大小选择移动方向，而且路径上的信息素会随时间不断消散。
在每次循环中，把最优的蚂蚁路径保留下来，当此最优路径使得公式（２）中Ｆ等于０时，停止准则终止蚂蚁搜索，经路径解码输出相应测试数据。
３蚁群算法及其改进基本蚁群算法最先用于求解ＴＳＰ问题，ＴＳＰ问题属于典型的离散优化问题。
针对测试数据生成问题，位串形式构建的蚂蚁路径网络已经完成了将连续优化问题转化为离散优化问题，使得采用蚁群算法生成测试数据成为可能。
它和ＴＳＰ问题主要不同之处在于：节点布置具有层次化、对称性特点，每层两个节点只能由公式（１）向着同一个方向的节点构成有向边；有向边按照同一个方向构成不同的路径；当输入变量元素多、精度高时，蚂蚁路径网络模型呈明显窄带形状；这些特点导致蚁群算法必须进行相应更改，以适应测试数据的自动生成。
３．１状态移动规则蚂蚁在当前节点ｖｊ′＝ｖｋ按照公式（１）只能转移到其中两个节点之一ｖｊ＋１′。
当１≤ｋ≤（Ｎ－１）时，ｖｊ＋１′为：ｖｊ＋１′＝ｖｋ＋１，τ（ｖｋ，ｖｋ＋１）≥τ（ｖｋ，ｖｋ＋１＋Ｎ），ｑ≤ｑ０ｖｋ＋１＋Ｎ，其’它当（１＋Ｎ）≤ｋ≤（２Ｎ－１）时，ｖｊ＋１′为：ｖｊ＋１′＝ｖｋ＋１，τ（ｖｋ，ｖｋ＋１）≥τ（ｖｋ，ｖｋ＋１－Ｎ），ｑ≤ｑ０ｖｋ＋１－Ｎ，其’它当ｋ＝Ｎ或ｋ＝２Ｎ时，ｖｊ＋１′为：ｖｊ＋１′＝ｖ１，τ（ｖｋ，ｖ１）≥τ（ｖｋ，ｖ１＋Ｎ），ｑ≤ｑ０ｖ１＋Ｎ，其’它τ（ｖｋ，ｖｋ＋１）为有向边（ｖｋ，ｖｋ＋１）信息素轨迹强度，ｑ∈［０，１］为随机数，ｑ０∈［０，１］为参数。
３．２路径随机变异蚂蚁路径网络具有单向对称性，虽然降低了路径网络的复杂度，便于蚂蚁的群体搜索，但是增加了路径的相似性。
由于初期信息素相对匮乏，使得各个路径上信息素轨迹强度差异不够明显，收敛到较好路径的的速度较慢。
在搜索的后期，由于解的相似性增加，正反馈机制容易产生停滞早熟现象，陷入局部最优路径。
为了解决这些问题，可以引用遗传算法中的变异操作，引入路径变异算子，增加路径搜索的多样性，有利于跳出局部最优路径，提高搜索速度。
随机生成随机数ｋ∈［０，Ｎ］，对路径ｐ（ｖｓ，ｖｔ）中节点ｖｋ进行变异，当ｋ≤Ｎ时，ｖｋ＝ｖｋ＋Ｎ，否则ｖｋ＝ｖｋ－Ｎ。
路径变异节点数以输入参数的数量而定，如对于有ｎ个参数的输入变量，路径变异节点数为ｎ个，可以对ｎ个参数实施均匀变异，从而保证参数变异的均匀一致性。
３．３挥发系数进度表由于挥发系数（１－ρ）的存在，使得那些从未搜索到的路径９８２００７，４３（１２）的信息素轨迹强度降低甚至接近于０，突出了路径多样性不足的问题，所以残留系数ρ应该选取较大的值。
