Material de Apoio da Pesquisa

Uma Adaptação dos Operadores Genéticos para o Problema do Próximo Release com Interdependência entre Requisitos


Italo Yeltsin, Allysson Allex Araújo, Altino Dantas, Jerffeson Souza

GOES.UECE | Universidade Estadual do Ceará - Brasil

1 - Resumo

O Problema do Próximo Release consiste em selecionar um conjunto de requisitos para serem entregues na próxima \textit{release} do sistema, maximizando a importância. Ao se considerar as interdependências entre requisitos, mais restrições são adicionadas e as características dos requisitos tornam-se dinâmicas, de forma que os algoritmos tenham de ser melhor adaptados para esse novo problema. Este trabalho apresenta uma adaptação de algoritmo genético para tratar as relações entre requisitos na resolução deste problema, tendo como foco a geração da população inicial e a reparação de indivíduos inválidos. Experimentos mostram que o algoritmo proposto apresenta soluções melhores em comparação com os algoritmos genéticos utilizados normalmente.

Palavras-chave: Problema do Próximo Release. Algoritmo Genético. Engenharia de Software Baseada em Busca.


2 - Instâncias

As instâncias utilizadas são dividas em reais e artificiais. As instâncias reais foram obtidas online em https://sites.google.com/site/mrkarim/data-sets. As artificiais foram geradas aleatoriamente. Todas as instâncias estão disponibilizadas abaixo:

Nome da Instância Qtd. Requisitos (%) interdependências Baixar
Todas Todas as Instâncias
Exemplo de Instância Exemplo de Instância
I_S_25_5 25 5 - Visualizar I_S_25_5
I_S_25_25 25 - Visualizar I_S_25_25
I_S_25_50 50 - Visualizar I_S_25_50
I_S_50_5 50 5 - Visualizar I_S_50_5
I_S_50_25 25 - Visualizar I_S_50_25
I_S_50_50 50 - Visualizar I_S_50_50
I_S_100_5 100 5 - Visualizar I_S_100_5
I_S_100_25 25 - Visualizar I_S_100_25
I_S_100_50 50 - Visualizar I_S_100_50
I_S_250_5 250 5 - Visualizar I_S_250_5
I_S_250_25 25 - Visualizar I_S_250_25
I_S_250_50 50 - Visualizar I_S_250_50
I_S_500_5 500 5 - Visualizar I_S_500_5
I_S_500_25 25 - Visualizar I_S_500_25
I_S_500_50 50 - Visualizar I_S_500_50
dataset-1 50 68 - Visualizar dataset-1
dataset-2 25 52 - Visualizar dataset-2

3 - Estudo Empírico

F = Fitness e T(ms) = Tempo em milissegundos

As tabelas abaixo mostram a média e o desvio padrão de Fitness e Tempo para 30 execuções de cada Algoritmo e instância. As tabelas 1, 2 e 3 apresentam os valores obtidos com 100, 500 e 1000 gerações, respectivamente.

Tabela 1 - 100 gerações.
Instância AG 1 AG 2 AG 3 AG 4 AG 5 AG 6
IS_25_5 94.81±1.8 95.98±1.08 96.14±1.03 96.53±0.66 96.69±0.39 96.76±0.0 F
80.57±66.63 29.3±14.27 37.13±17.83 25.96±14.39 52.29±88.99 46.73±25.36 T
IS_25_25 101.95±8.22 105.51±9.61 105.39±9.48 106.15±9.64 106.36±9.68 106.43±9.67 F
53.5±54.35 28.38±10.16 34.18±12.97 24.86±10.25 40.28±64.08 41.54±18.72 T
IS_25_50 100.96±9.62 111.13±11.18 103.88±9.64 111.74±11.16 111.96±11.18 112.03±11.18 F
43.71±46.49 27.71±8.36 32.29±10.94 24.38±8.41 35.98±52.7 37.93±16.13 T
IS_50_5 123.51±39.95 131.34±36.36 126.66±40.32 132.19±36.72 132.74±37.28 132.86±37.36 F
49.57±41.52 37.75±18.86 46.79±26.86 33.02±16.65 46.86±49.41 58.45±38.26 T
IS_50_25 136.72±44.45 143.77±40.98 140.29±45.31 145.17±41.88 146.48±43.22 146.73±43.43 F
54.88±38.65 47.65±26.12 56.38±30.77 41.38±22.4 54.14±46.53 69.0±40.23 T
IS_50_50 143.47±43.39 151.24±41.03 146.37±43.6 153.38±42.44 155.15±43.96 155.45±44.19 F
55.9±35.36 49.98±24.45 59.46±28.95 43.4±20.95 56.63±42.85 71.82±37.27 T
IS_100_5 167.76±71.81 174.69±68.89 171.74±74.12 176.86±69.66 179.47±72.16 179.72±72.16 F
80.26±68.17 77.47±71.1 93.92±88.6 66.51±59.87 85.4±80.88 110.66±101.21 T
IS_100_25 188.66±87.02 195.84±85.39 194.49±91.83 197.11±84.47 203.47±92.66 203.95±93.11 F
98.69±80.39 99.37±88.34 117.79±104.22 83.36±71.64 107.09±94.95 139.56±121.72 T
IS_100_50 197.33±85.66 205.91±85.5 203.32±90.14 207.24±84.71 217.2±95.66 218.19±96.61 F
110.23±82.54 108.74±87.47 130.63±104.78 91.88±71.75 120.92±97.71 154.69±122.5 T
IS_250_5 242.16±157.17 249.29±153.37 250.28±164.82 249.11±149.18 264.16±167.58 265.45±168.84 F
263.12±465.97 275.94±509.42 315.66±564.31 183.54±284.01 246.37±387.82 305.95±468.45 T
IS_250_25 270.47±174.58 275.62±168.39 280.67±184.24 273.67±162.15 300.75±197.32 304.26±202.43 F
392.4±604.49 390.0±605.7 465.39±717.08 265.44±375.33 355.73±506.56 409.49±553.84 T
IS_250_50 284.62±173.72 294.42±172.96 296.57±184.2 291.18±165.87 331.7±215.02 336.87±221.96 F
466.72±629.82 437.76±601.34 547.37±738.8 307.69±385.87 424.19±535.57 474.31±572.22 T
IS_500_5 329.71±228.62 337.84±224.16 344.28±242.18 330.0±208.6 378.11±261.81 386.56±274.09 F
1116.17±2332.76 1159.46±2576.29 1305.78±2723.25 542.33±896.85 786.24±1356.62 835.47±1366.69 T
IS_500_25 352.73±235.46 360.15±230.56 366.84±247.19 351.66±215.7 417.48±289.52 429.62±306.41 F
1587.72±2819.04 1471.28±2727.55 1841.18±3259.47 778.8±1217.03 1107.68±1747.94 1105.97±1638.85 T
IS_500_50 350.95±227.67 372.9±227.9 364.5±239.13 369.62±219.05 445.93±299.32 461.38±319.03 F
1731.73±2777.4 1583.74±2668.81 2013.92±3215.3 900.37±1261.29 1312.56±1855.17 1271.26±1699.95 T
dataset-1 5109.26±146.89 5180.43±145.09 5268.5±92.23 5255.0±133.26 5350.69±46.24 5362.83±0.89 F
382.26±156.6 459.53±306.19 529.83±320.22 438.3±372.06 504.43±254.91 648.06±318.75 T
dataset-2 2821.42±2290.2 2857.66±2325.03 2904.03±2365.36 2897.12±2359.75 2945.7±2405.22 2951.76±2411.06 F
259.76±168.75 295.81±273.11 342.86±296.51 273.16±310.77 323.85±255.78 414.18±326.3 T

Tabela 2 - 500 gerações.
Instância AG 1 AG 2 AG 3 AG 4 AG 5 AG 6
IS_25_5 96.21±1.22 96.27±0.93 96.53±0.7 96.69±0.39 96.61±0.54 96.76±0.0 F
144.93±37.33 144.19±23.59 187.69±26.06 121.2±29.3 161.06±27.67 194.13±30.44 T
IS_25_25 104.84±8.98 105.85±9.63 105.9±9.51 106.39±9.7 106.36±9.75 106.43±9.67 F
150.55±27.74 153.46±20.06 184.34±19.49 130.19±23.15 158.33±20.54 184.15±24.36 T
IS_25_50 106.83±10.01 111.45±11.17 105.94±10.09 111.93±11.15 111.95±11.22 112.01±11.16 F
151.43±23.36 155.84±17.24 178.65±18.51 133.19±19.93 156.01±19.67 172.72±26.11 T
IS_50_5 128.64±38.77 132.18±37.21 128.26±39.63 132.73±37.3 132.8±37.39 132.8±37.27 F
204.42±94.06 208.84±93.15 256.19±135.34 176.62±77.29 221.32±114.47 258.79±150.83 T
IS_50_25 142.18±44.04 145.0±42.08 142.58±45.62 146.26±42.96 146.56±43.33 146.8±43.54 F
255.08±132.13 265.06±140.19 310.04±162.14 224.01±117.46 265.15±134.82 302.71±161.01 T
IS_50_50 149.32±43.41 153.45±42.82 149.84±44.86 154.79±43.61 155.28±44.09 155.52±44.27 F
277.07±130.35 282.36±133.82 331.05±155.36 239.0±112.42 283.37±129.67 318.84±151.62 T
IS_100_5 173.89±72.39 177.78±71.58 175.03±74.37 179.1±71.96 179.72±72.45 180.02±72.67 F
411.89±352.14 425.52±372.22 517.41±478.82 351.95±295.61 435.0±390.37 480.91±421.1 T
IS_100_25 197.21±91.62 201.09±91.08 198.38±93.05 203.08±92.51 203.99±93.37 204.42±93.76 F
542.07±476.84 563.71±505.2 669.31±601.85 463.77±405.08 558.06±489.28 603.04±509.55 T
IS_100_50 208.0±91.67 213.96±93.32 209.31±93.08 216.73±95.44 218.52±97.18 219.02±97.6 F
616.47±496.78 628.0±510.2 757.91±620.39 530.66±426.59 642.11±519.08 680.67±528.3 T
IS_250_5 257.89±173.1 263.11±172.0 259.85±175.47 266.31±174.13 268.38±175.72 268.8±175.71 F
1498.12±2692.06 1578.01±2900.86 1836.26±3291.52 995.13±1453.64 1292.43±2012.65 1367.59±2121.11 T
IS_250_25 295.17±202.85 298.9±199.28 298.77±207.71 305.14±206.52 308.79±210.71 309.55±211.36 F
2389.36±3819.12 2290.64±3577.33 2791.93±4359.09 1591.71±2342.87 1904.64±2726.5 1833.03±2501.36 T
IS_250_50 322.42±214.24 326.0±210.98 327.55±220.62 335.83±222.45 343.15±231.72 344.36±232.99 F
2889.72±4018.09 2587.39±3564.83 3374.11±4599.75 1918.86±2492.54 2302.55±2925.4 2132.08±2592.29 T
IS_500_5 377.29±280.17 380.14±276.18 384.78±290.23 396.03±298.61 404.34±307.42 405.66±308.56 F
7249.64±15635.01 7038.07±15824.39 8208.0±17336.56 3240.21±5172.27 4172.7±7063.17 3885.9±6566.49 T
IS_500_25 412.47±298.32 413.48±292.07 421.5±309.45 441.35±330.94 454.89±347.81 457.07±350.37 F
10150.79±18366.9 8718.51±16424.58 11480.61±20468.08 4783.68±7484.61 5863.78±9141.31 5218.22±7945.13 T
IS_500_50 429.21±294.99 429.07±288.2 439.15±306.19 470.03±337.39 491.61±363.07 495.57±367.91 F
11467.07±18423.27 9389.91±16067.5 12958.57±20536.84 5574.69±7816.34 7023.3±9842.92 6105.04±8363.12 T
dataset-1 4097.23±227.47 5098.1±142.71 4194.26±227.18 5275.76±47.86 5306.23±33.13 5316.96±23.84 F
399.69±30.01 404.13±28.55 480.1±25.17 382.13±25.53 465.83±28.19 488.73±34.78 T
dataset-2 4558.23±490.49 5063.25±113.28 4603.3±442.41 5167.98±113.64 5184.18±124.69 5188.58±130.06 F
273.56±128.01 275.53±130.23 321.91±159.23 251.18±132.25 305.33±161.79 320.56±170.01 T

Tabela 3 - 1000 gerações.
Instância AG 1 AG 2 AG 3 AG 4 AG 5 AG 6
IS_25_5 96.69±0.39 96.54±0.65 96.69±0.39 96.76±0.0 96.76±0.0 96.76±0.0 F
281.16±26.2 283.3±29.15 365.86±26.0 228.96±29.69 312.33±33.23 382.19±31.08 T
IS_25_25 105.76±9.14 106.19±9.66 106.05±9.39 106.42±9.66 106.45±9.68 106.46±9.7 F
298.55±26.64 309.5±40.51 362.18±19.28 249.05±29.29 307.83±24.78 363.26±29.09 T
IS_25_50 106.64±9.99 111.68±11.07 107.52±10.88 111.98±11.13 112.02±11.17 112.04±11.18 F
301.04±22.87 313.13±33.7 353.0±21.05 255.34±25.68 301.75±22.24 341.22±39.32 T
IS_50_5 128.59±38.99 132.54±37.38 129.41±39.07 132.76±37.25 132.84±37.34 132.84±37.3 F
407.7±185.85 418.74±185.28 507.59±268.45 342.98±153.48 438.8±238.32 523.52±317.95 T
IS_50_25 142.23±44.35 145.7±42.58 143.62±45.07 146.35±43.02 146.66±43.35 146.62±43.28 F
512.75±268.48 536.21±288.74 617.51±325.81 438.37±235.35 532.94±284.52 614.79±338.0 T
IS_50_50 149.42±43.72 154.08±43.16 151.22±44.62 154.95±43.73 155.42±44.16 155.43±44.16 F
558.47±265.62 569.96±274.61 665.06±315.97 468.67±225.33 571.71±273.93 641.67±314.43 T
IS_100_5 174.26±73.08 178.4±71.74 176.31±74.06 179.34±72.16 179.79±72.34 179.95±72.65 F
834.69±720.8 856.2±747.01 1040.97±966.3 693.51±589.02 874.62±784.27 978.47±874.96 T
IS_100_25 197.52±91.98 202.01±91.7 199.66±92.84 203.67±93.28 204.22±93.59 204.28±93.61 F
1112.05±996.88 1119.61±987.15 1355.08±1228.09 928.49±830.99 1122.21±983.64 1226.18±1048.66 T
IS_100_50 208.65±92.31 214.62±93.59 211.07±93.34 217.62±96.44 218.95±97.6 219.32±97.98 F
1260.94±1030.46 1248.16±999.76 1526.99±1255.96 1074.75±886.35 1296.33±1050.25 1371.76±1071.11 T
IS_250_5 259.06±174.73 264.39±173.72 261.67±175.75 267.22±174.67 268.85±176.02 269.2±176.15 F
3109.67±5644.56 3162.41±5830.77 3652.12±6490.26 2033.96±3002.4 2604.41±4050.29 2765.54±4303.1 T
IS_250_25 298.36±207.88 302.13±204.18 301.66±209.95 306.67±208.12 309.51±211.43 309.98±211.76 F
4892.76±7803.68 4595.01±7187.33 5528.23±8575.03 3345.72±5042.98 3886.56±5599.95 3721.5±5096.48 T
IS_250_50 328.02±222.06 332.2±219.52 331.87±224.62 339.55±227.18 344.4±233.2 344.81±233.37 F
5906.21±8199.93 5209.51±7178.35 6714.59±9107.79 4082.52±5412.86 4704.17±6008.67 4350.45±5307.15 T
IS_500_5 385.78±292.51 389.31±289.17 391.45±298.63 400.82±304.46 405.79±308.9 406.35±309.39 F
15317.19±33630.95 14089.79±31584.88 17018.14±36780.83 6894.11±11050.1 8563.16±14563.68 7955.6±13489.58 T
IS_500_25 425.72±316.54 427.79±311.33 433.39±325.1 450.72±344.17 456.97±350.23 458.08±351.66 F
20925.84±38264.13 17302.91±32602.49 23443.67±42370.52 10292.12±16276.94 12083.4±18928.47 10581.06±16080.7 T
IS_500_50 448.98±318.01 448.14±310.35 457.35±326.67 482.89±353.69 495.72±368.13 497.97±371.12 F
23710.3±38432.69 18501.29±31822.11 26613.04±42635.16 11961.65±16925.76 14608.3±20589.28 12373.58±16922.62 T
dataset-1 4237.23±202.0 5183.8±118.6 4299.69±202.39 5278.53±42.86 5321.03±15.35 5315.23±21.93 F
835.56±168.89 834.79±52.4 1012.93±31.09 761.06±30.47 933.16±28.58 948.89±36.51 T
dataset-2 4628.25±419.66 5106.03±119.92 4658.46±388.61 5168.76±114.9 5192.55±129.15 5189.64±126.75 F
567.31±293.7 573.54±268.91 676.61±337.05 500.75±261.24 613.56±320.28 618.21±331.73 T

Tabela 4 - Valores de Fitness do AG6 com 100 gerações, AG1 com 500 gerações e AG1 com 1000 gerações para todas as instâncias.
Instância AG6 - 100 Gerações AG1 - 500 Gerações AG1 - 1000 Gerações
IS_25_5 96.76±0.0 96.21±1.22 96.69±0.39
IS_25_25 106.43±9.67 104.84±8.98 105.76±9.14
IS_25_50 112.03±11.18 106.83±10.01 106.64±9.99
IS_50_5 132.86±37.36 128.64±38.77 128.59±38.99
IS_50_25 146.73±43.43 142.18±44.04 142.23±44.35
IS_50_50 155.45±44.19 149.32±43.41 149.42±43.72
IS_100_5 179.72±72.16 173.89±72.39 174.26±73.08
IS_100_25 203.95±93.11 197.21±91.62 197.52±91.98
IS_100_50 218.19±96.61 208.0±91.67 208.65±92.31
IS_250_5 265.45±168.84 257.89±173.1 259.06±174.73
IS_250_25 304.26±202.43 295.17±202.85 298.36±207.88
IS_250_50 336.87±221.96 322.42±214.24 328.02±222.06
IS_500_5 386.56±274.09 377.29±280.17 385.78±292.51
IS_500_25 429.62±306.41 412.47±298.32 425.72±316.54
IS_500_50 461.38±319.03 429.21±294.99 448.98±318.01
dataset-1 5301.33±39.68 4097.23±227.47 4237.23±202.0
dataset-2 5180.16±125.31 4558.23±490.49 4628.25±419.66

4 - Código Fonte

O código fonte usado no estudo empírico pode ser obtido aqui Download



Junho de 2015 (Atualizado pela última vez em Junho de 2015)