検索ベースのソフトウェアエンジニアリング
メタヒューリスティック探索技術のソフトウェア工学への応用

探索型ソフトウェア工学（SBSE）は、遺伝的アルゴリズム、シミュレーテッドアニーリング、タブーサーチといったメタヒューリスティック探索技術をソフトウェア工学の問題に適用します。ソフトウェア工学における多くの活動は、最適化問題として捉えることができます。線形計画法や動的計画法といったオペレーションズ・リサーチの最適化技術は、計算量や問題構造に関する仮定のために、大規模なソフトウェア工学の問題には実用的ではないことがよくあります。研究者や実務家は、問題構造に関する仮定をほとんど課さないメタヒューリスティック探索技術を用いて、最適解に近い、あるいは「十分に良い」解を見つけます。[1]

SBSE の問題は 2 つのタイプに分けられます。

  • ブラックボックス最適化問題、たとえば、タスクに人を割り当てる問題 (典型的な組み合わせ最適化問題)。
  • ソースコードに対する操作を考慮する必要があるホワイトボックス問題。[2]

意味

SBSEは、ソフトウェア工学の問題を、メタヒューリスティックを用いて解くことができる計算探索問題に変換します。これには、探索空間、つまり可能な解の集合を定義することが含まれます。この空間は通常、網羅的に探索するには大きすぎるため、メタヒューリスティックなアプローチが提案されます。そして、メトリック[3]（適応度関数、コスト関数、目的関数、品質尺度とも呼ばれる）を用いて、潜在的な解の品質を測定します。多くのソフトウェア工学の問題は、計算探索問題として再定式化できます。[4]

対照的に、「検索ベースのアプリケーション」という用語は、別の産業用アプリケーションで、検索技術ではなく検索エンジン技術を使用することを指します。

簡単な歴史

ソフトウェア工学の問題に最適化を適用する最も初期の試みの一つは、 1976年にWebb MillerとDavid Spoonerによってソフトウェアテストの分野で報告されました。[5] 1992年には、S. Xanthakisと彼の同僚が初めてソフトウェア工学の問題に検索手法を適用しました。 [6] SBSEという用語は、2001年にHarmanとJonesによって初めて使用されました。[7]研究コミュニティは2013年までに800人以上の著者を含むまでに成長し、40か国の約270の機関にまたがっています。[8]

応用分野

探索型ソフトウェア工学は、ソフトウェア開発プロセスのほぼすべての段階に適用できます。ソフトウェアテストは主要な適用例の一つです。[9]探索技術は、要件分析、[10] [11]設計、[12] [13]リファクタリング、[14]開発、[15]保守など、他のソフトウェア工学活動にも適用されています。[16]

要件エンジニアリング

要件エンジニアリングとは、ソフトウェアのユーザーと環境のニーズを特定し、管理するプロセスです。限られたリソースや要件間の相互依存性といった制約の中で、ユーザーの要求を満たす最適な要件のサブセットを見つけることを目的とした、要件の選択と最適化には、探索ベースの手法が用いられてきました。この問題は、多くの場合、多基準意思決定問題として扱われ、一般的には、コストとユーザー満足度、そして要件リスクの間の適切な妥協点を提示することを伴います。[17] [18] [19] [20]

デバッグとメンテナンス

ソフトウェアのバグ（またはコードの臭い）を特定し、デバッグ（またはリファクタリング）する作業は、ツールによってサポートされているとはいえ、大部分が手作業で労力を要する作業です。SBSEの目的の一つは、バグを自動的に特定し修正することです（例えば、ミューテーションテストなど）。

遺伝的プログラミングは、生物学に着想を得た手法で、交叉と突然変異を用いてプログラムを進化させ、ソースコードの数行を変更することでプログラムの修復箇所を探すために用いられてきました。GenProg Evolutionary Program Repairソフトウェアは、あるテストで105個のバグのうち55個を1個あたり約8ドルで修復しました。[21]

共進化は「捕食者と獲物」の比喩を採用しており、一連のプログラムと一連のユニットテストが一緒に進化し、互いに影響を与えます。[22]

テスト

探索型ソフトウェア工学は、テストケース（テストデータ）の自動生成、テストケースの最小化、テストケースの優先順位付けなど、ソフトウェアテストに適用されてきました。[23] 回帰テストも注目を集めています。

ソフトウェアの最適化

SBSEをプログラムの最適化、つまりソフトウェアの一部を修正して速度とリソースの使用効率を高める研究は、成功を収めてきました。[24]ある例では、50,000行のプログラムが遺伝的に改良され、平均で70倍高速化されたプログラムが生まれました。[25] Basiosらによる最近の研究では、データ構造を最適化することで、Google Guavaの実行時間が9%、メモリ消費量が13%、CPU使用率がそれぞれ4%改善されたことが示されています。[26]

プロジェクト管理

プロジェクトのスケジュール設定など、通常はプロジェクトマネージャーが行う多くの決定は、自動的に行うことができます。[27]

ツール

SBSEで利用できるツールには、OpenPAT、[28] EvoSuite、[29] Pythonのコードカバレッジ測定ツールであるCoverageなどがあります。[30]

方法と技術

次のようなさまざまな方法とテクニックが利用可能です。

業界の受け入れ

SBSE は比較的新しい研究分野であるため、まだ業界で広く受け入れられていません。

SBSEの産業界における成功事例は、主にソフトウェアテスト分野に見られます。大規模なバグ発見のためのランダムテスト入力を自動生成する機能は、企業にとって魅力的です。2017年、Facebookは検索ベースのバグ発見アプリ「Sapienz」を開発したソフトウェアスタートアップ企業Majicke Limitedを買収しました。[32]

他の応用シナリオでは、ソフトウェアエンジニアは、制御がほとんどできないツールや、人間が生成するものとは異なるソリューションを生成するツールの導入に消極的になる場合があります。[33]プログラムの修正や改善におけるSBSEの活用においては、開発者は、自動的に生成された変更がシステム要件やテスト環境の範囲外で予期せぬ動作を生成しないことを確信する必要があります。完全な自動プログラミングはまだ実現されていないことを考慮すると、このような変更の望ましい特性は、保守作業を支援するために人間が容易に理解できることです。[34]

もう一つの懸念は、SBSEによってソフトウェアエンジニアが不要になるのではないかという点です。支持者は、SBSEの目的はエンジニアとプログラムの関係を強化することだと主張しています。[35]

参照

参考文献

  1. ^ Mohan, M.; Greer, D. (2019年8月1日). 「多目的アプローチを用いた自動リファクタリングの調査」 .情報ソフトウェア技術. 112 : 83–101 . doi :10.1016/j.infsof.2019.04.009. ISSN  0950-5849.
  2. ^ Harman, Mark (2010). 「なぜソースコード分析と操作は常に重要なのか」.第10回IEEEソースコード分析と操作に関するワーキングカンファレンス (SCAM 2010) . 第10回IEEEソースコード分析と操作に関するワーキングカンファレンス (SCAM 2010). pp.  7– 19. doi :10.1109/SCAM.2010.28.
  3. ^ Harman, Mark; John A. Clark (2004). 「メトリクスも適応度関数である」.第10回国際ソフトウェアメトリクスシンポジウム議事録, 2004.第10回国際ソフトウェアメトリクスシンポジウム, 2004. pp.  58– 69. doi :10.1109/METRIC.2004.1357891.
  4. ^ Clark, John A.; Dolado, José Javier; Harman, Mark; Hierons, Robert M.; Jones, Bryan F.; Lumkin, M.; Mitchell, Brian S.; Mancoridis, Spiros; Rees, K.; Roper, Marc; Shepperd, Martin J. (2003). 「ソフトウェア工学を探索問題として再定式化する」. IEE Proceedings - Software . 150 (3): 161– 175. CiteSeerX 10.1.1.144.3059 . doi :10.1049/ip-sen:20030559 (2025年7月12日非アクティブ). ISSN  1462-5970. {{cite journal}}: CS1 maint: DOIは2025年7月時点で非アクティブです（リンク）
  5. ^ ミラー, ウェッブ; スプーナー, デイビッド L. (1976). 「浮動小数点テストデータの自動生成」. IEEE Transactions on Software Engineering . SE-2 (3): 223– 226. Bibcode :1976ITSEn...2..223M. doi :10.1109/TSE.1976.233818. ISSN  0098-5589. S2CID  18875300.
  6. ^ S. Xanthakis、C. Ellis、C. Skourlas、A. Le Gall、S. Katsikas、K. Karapoulios、「遺伝的アルゴリズムのソフトウェアテストへの応用」、第5回国際ソフトウェア工学応用会議論文集、フランス、トゥールーズ、1992年、625～636ページ
  7. ^ Harman, Mark; Jones, Bryan F. (2001年12月15日). 「検索ベースソフトウェアエンジニアリング」. Information and Software Technology . 43 (14): 833– 839. CiteSeerX 10.1.1.143.9716 . doi :10.1016/S0950-5849(01)00189-6. ISSN  0950-5849.  
  8. ^ Harman, Mark; Mansouri, S. Afshin; Zhang, Yuanyuan (2012年11月1日). 「検索ベースソフトウェアエンジニアリング：トレンド、テクニック、そしてアプリケーション」 . ACM Computing Surveys . 45 (1): 1– 61. doi :10.1145/2379776.2379787. S2CID  207198163.
  9. ^ McMinn, Phil (2004). 「検索ベースのソフトウェアテストデータ生成：サーベイ」.ソフトウェアテスト、検証、信頼性. 14 (2): 105– 156. CiteSeerX 10.1.1.122.33 . doi :10.1002/stvr.294. ISSN  1099-1689. S2CID  17408871.  
  10. ^ Greer, Des; Ruhe, Guenther (2004年3月15日). 「ソフトウェアリリース計画：進化的かつ反復的なアプローチ」. Information and Software Technology . 46 (4): 243– 253. CiteSeerX 10.1.1.195.321 . doi :10.1016/j.infsof.2003.07.002. ISSN  0950-5849. S2CID  710923.  
  11. ^ コラレス、フェリペ;ソウザ、ジャーフェソン。カルモ、ラファエロ。パドヴァ、クラリンド;マテウス、ジェラルド R. (2009)。 「ソフトウェア リリース計画への新しいアプローチ」。ソフトウェアエンジニアリングに関する XXIII ブラジルシンポジウム、2009 年。SBES '09。ソフトウェアエンジニアリングに関する XXIII ブラジルシンポジウム、2009 年。SBES '09。 pp.  207–215。土井:10.1109/SBES.2009.23。
  12. ^ Clark, John A.; Jacob, Jeremy L. (2001年12月15日). 「プロトコルもプログラムである：セキュリティプロトコルのメタヒューリスティック探索」. Information and Software Technology . 43 (14): 891– 904. CiteSeerX 10.1.1.102.6016 . doi :10.1016/S0950-5849(01)00195-1. ISSN  0950-5849.  
  13. ^ Räihä, Outi (2010年11月1日). 「検索ベースのソフトウェア設計に関する調査」(PDF) .コンピュータサイエンスレビュー. 4 (4): 203– 249. CiteSeerX 10.1.1.188.9036 . doi :10.1016/j.cosrev.2010.06.001. ISSN  1574-0137. 
  14. ^ Mariani, Thainá; Vergilio, Silvia Regina (2017年3月1日). 「検索ベースリファクタリングに関する体系的レビュー」. Information and Software Technology . 83 : 14–34 . doi :10.1016/j.infsof.2016.11.009. ISSN  0950-5849.
  15. ^ Alba, Enrique; Chicano, J. Francisco (2007年6月1日). 「GAを用いたソフトウェアプロジェクト管理」. Information Sciences . 177 (11): 2380– 2401. doi :10.1016/j.ins.2006.12.020. hdl : 10630/8145 . ISSN  0020-0255.
  16. ^ Antoniol, Giuliano; Di Penta, Massimiliano; Harman, Mark (2005). 「大規模保守プロジェクトにおけるプロジェクト計画の最適化に適用される探索ベース手法」. Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05 . Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05. pp.  240– 249. CiteSeerX 10.1.1.63.8069 . doi :10.1109/ICSM.2005.79.  
  17. ^ Zhang, Yuanyuan (2010年2月). 多目的探索に基づく要件選択と最適化 (PhD). ストランド、ロンドン、英国: ロンドン大学.
  18. ^ Y. Zhang、M. Harman、S. L. Lim、「要件相互作用管理の検索ベース最適化」、ユニバーシティ・カレッジ・ロンドン、コンピュータサイエンス学部、研究ノート RN/11/12、2011 年。
  19. ^ Li, Lingbo; Harman, Mark; Letier, Emmanuel; Zhang, Yuanyuan (2014). 「ロバストな次リリース問題」. 2014年遺伝的・進化的計算年次会議論文集. Gecco '14. pp.  1247– 1254. doi :10.1145/2576768.2598334. ISBN 9781450326629. S2CID  8423690。
  20. ^ Li, L.; Harman, M.; Wu, F.; Zhang, Y. (2017). 「要件選定における厳密な分析の価値」(PDF) . IEEE Transactions on Software Engineering . 43 (6): 580– 596. Bibcode :2017ITSEn..43..580L. doi :10.1109/TSE.2016.2615100. ISSN  0098-5589. S2CID  8398275.
  21. ^ Le Goues, Claire ; Dewey-Vogt, Michael ; Forrest, Stephanie ; Weimer, Westley (2012). 「自動プログラム修復に関する体系的研究：105個のバグのうち55個を8ドルで修正」2012年 第34回国際ソフトウェア工学会議 (ICSE) . 2012年 第34回国際ソフトウェア工学会議 (ICSE). pp.  3– 13. doi :10.1109/ICSE.2012.6227211.
  22. ^ Arcuri, Andrea; Yao, Xin (2008). 「ソフトウェアバグ自動修正への新たな共進化的アプローチ」. IEEE Con​​gress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence) . IEEE Con​​gress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). pp.  162– 168. CiteSeerX 10.1.1.159.7991 . doi :10.1109/CEC.2008.4630793. 
  23. ^ Harman, Mark; Jia, Yue; Zhang, Yuanyuan (2015年4月). 「検索型ソフトウェアテストの成果、未解決の問題、そして課題」. 2015 IEEE 第8回国際ソフトウェアテスト・検証・妥当性確認会議 (ICST) . グラーツ, オーストリア: IEEE. pp.  1– 12. CiteSeerX 10.1.1.686.7418 . doi :10.1109/ICST.2015.7102580. ISBN  978-1-4799-7125-1. S2CID  15272060。
  24. ^ Memeti, Suejb; Pllana, Sabri; Binotto, Alecio; Kolodziej, Joanna; Brandic, Ivona (2018). 「並列コンピューティングシステムのソフトウェア最適化におけるメタヒューリスティックスと機械学習の活用：体系的な文献レビュー」. Computing . 101 (8): 893– 936. arXiv : 1801.09444 . Bibcode :2018arXiv180109444M. doi :10.1007/s00607-018-0614-9. S2CID  13868111.
  25. ^ Langdon, William B.; Harman, Mark. 「遺伝的プログラミングによる既存ソフトウェアの最適化」( PDF) IEEE Transactions on Evolutionary Computation .
  26. ^ Basios, Michail; Li, Lingbo; Wu, Fan; Kanthan, Leslie; Barr, Earl T. (2017年9月9日). 「Google Guavaにおけるダーウィン的データ構造の最適化」. 検索ベースソフトウェアエンジニアリング(PDF) . コンピュータサイエンス講義ノート. 第10452巻. pp.  161– 167. doi :10.1007/978-3-319-66299-2_14. ISBN 978-3-319-66298-5。
  27. ^ Minku, Leandro L.; Sudholt, Dirk; Yao, Xin (2012). 「プロジェクトスケジューリング問題のための進化的アルゴリズム：実行時間分析と改良設計」.第14回遺伝的・進化的計算国際会議議事録. GECCO '12. ニューヨーク、ニューヨーク州、米国: ACM. pp.  1221– 1228. doi :10.1145/2330163.2330332. ISBN  978-1-4503-1177-9。
  28. ^ Mayo, M.; Spacey, S. (2013). 「遺伝的アルゴリズムを用いた動的性能分析メトリクスに基づく回帰テストの失敗予測」(PDF) .探索型ソフトウェア工学. コンピュータサイエンス講義ノート. 第8084巻. pp.  158– 171. doi :10.1007/978-3-642-39742-4_13. hdl : 10289/7763 . ISBN  978-3-642-39741-7。
  29. ^ 「ホーム」. evosuite.org .
  30. ^ その他、Ned Batchelderと100、「カバレッジ：Pythonのコードカバレッジ測定」、2020年7月28日のオリジナルからアーカイブ、2018年3月14日取得{{citation}}: CS1 maint: 数値名: 著者リスト (リンク)
  31. ^ 「Java のオープンソースプロファイラー」。
  32. ^ 「Sapienz：Facebookによるソフトウェアテストの自動化推進」VentureBeat、2018年12月30日。 2020年9月29日閲覧。
  33. ^ Jones, Derek (2013年10月18日). 「遺伝的アルゴリズムを用いたプログラミング：それは人間が既にやっていることではないでしょうか ;-)」. The Shape of Code . 2013年10月31日閲覧。
  34. ^ Le Goues, Claire ; Forrest, Stephanie ; Weimer, Westley (2013年9月1日). 「自動ソフトウェア修復における現在の課題」. Software Quality Journal . 21 (3): 421– 443. CiteSeerX 10.1.1.371.5784 . doi :10.1007/s11219-013-9208-0. ISSN  1573-1367. S2CID  16435531.  
  35. ^ Simons, Christopher L. (2013年5月). SBSEにおけるソフトウェアエンジニアの行く末は？. モデリングと検索ベースソフトウェアエンジニアリングの統合に関する第一回国際ワークショップ, モデリングと検索ベースソフトウェアエンジニアリングの統合に関する第一回国際ワークショップ. サンフランシスコ, 米国: IEEE Press. pp.  49– 50. 2013年10月31日閲覧。
  • SBSEの出版物のリポジトリ 2012年5月2日アーカイブWayback Machine
  • メタヒューリスティクスとソフトウェアエンジニアリング 2011年9月23日アーカイブWayback Machine
  • ソフトウェア成果物インフラストラクチャリポジトリ
  • 国際ソフトウェア工学会議
  • 遺伝的および進化的計算（GECCO）
  • 検索ベースのソフトウェアエンジニアリングに関するGoogle Scholarページ
「https://en.wikipedia.org/w/index.php?title=Search-based_software_engineering&oldid=1326085378」より取得