Loading article…
コンピュータサイエンスにおいて、経験的アルゴリズム（または実験的アルゴリズム）とは、経験的手法を用いてアルゴリズムの挙動を研究する手法である。この手法は、アルゴリズムの開発と実験を組み合わせたものであり、アルゴリズムは設計されるだけでなく、さまざまな状況で実装およびテストされる。このプロセスでは、アルゴリズムの初期設計が分析され、アルゴリズムが段階的に開発されるようになる。[ 1 ]
経験的アルゴリズムの手法は、アルゴリズムの分析のための理論的手法を補完する。[ 2 ]特に統計学からの経験的手法を原理的に適用することで、理論的分析では（現状では）アクセスできない困難な組み合わせ問題に対する高性能ヒューリスティックアルゴリズムなどのアルゴリズムの挙動に関する洞察を得られることが多い。[ 3 ]また、経験的手法は、アルゴリズムの効率を大幅に向上させるためにも使用できる。[ 4 ]
アメリカのコンピュータ科学者キャサリン・マクジオックは、経験的アルゴリズム学の主な分野を 2 つ挙げています。1 つ目 (経験的分析として知られています) はアルゴリズムの動作の分析と特性評価を扱い、2 つ目 (アルゴリズム設計またはアルゴリズム工学として知られています) はアルゴリズムのパフォーマンスを向上させるための経験的方法に焦点を当てています。[ 5 ]前者は統計学の技術とツールに依存することが多く、後者は統計学、機械学習、最適化のアプローチに基づいています。さまざまなコンテキストで使用するさまざまなタイプのアルゴリズムの選択と改良に経験的方法を適用する場合、通常はパフォーマンス プロファイラなどの動的分析ツールがよく使用されます。[ 6 ] [ 7 ] [ 8 ]
経験的アルゴリズムの研究は、ACM Journal on Experimental Algorithmics (JEA) やJournal of Artificial Intelligence Research (JAIR) など、いくつかのジャーナルに掲載されています。キャサリン・マクジオックの他に、経験的アルゴリズムの著名な研究者には、ベルナール・モレ、ジュゼッペ・F・イタリアーノ、ホルガー・H・フース、デイビッド・S・ジョンソン、ロベルト・バッティティなどがいます。[ 9 ]
経験的アルゴリズムがない場合、アルゴリズムの複雑さを分析するには、アルゴリズムが使用されるさまざまな状況に適用できるさまざまな理論的方法が必要になることがあります。[ 10 ]メモリとキャッシュの考慮事項は、特定の目的のために複雑なアルゴリズムを理論的に選択したり、その最適化のアプローチを検討したりする際に考慮すべき重要な要素となることがよくあります。[ 11 ] [ 12 ]パフォーマンスプロファイリングは、通常、アプリケーション全体のコード内のボトルネックを見つけて分析したり[ 13 ] [ 14 ] [ 15 ]、アプリケーション全体を分析してパフォーマンスの低いコードを特定したりするために使用される動的プログラム分析手法です。[ 16 ]プロファイラは、アプリケーションのパフォーマンスの問題に最も関連のあるコードを明らかにすることができます。[ 17 ]
プロファイラは、特定の状況でどのアルゴリズムを選択するかを判断するのに役立つ場合があります。[ 18 ]複雑性分析と同様に、個々のアルゴリズムをプロファイリングする場合、メモリとキャッシュの考慮事項は、命令数やクロックサイクルよりも重要になることがよくあります。ただし、プロファイラの結果は、アルゴリズムが使用する命令の数ではなく、アルゴリズムがデータにアクセスする方法に照らして検討することができます。[ 19 ]
プロファイリングは、パフォーマンスの結果を視覚的に表現することで、アルゴリズムの動作に対する直感的な洞察を提供する可能性があります[ 20 ] 。 [ 21 ]パフォーマンス プロファイリングは、たとえば、ワイルドカードのマッチングアルゴリズムの開発中に適用されています。Rich Salzのwildmatアルゴリズム[ 22 ]など、ワイルドカードのマッチングのための初期のアルゴリズムは、通常、パフォーマンスの観点から批判された手法である再帰に依存していました[ 23 ] 。Krauss のマッチングワイルドカード アルゴリズムは、テスト ケースを使用して非再帰的な代替案を定式化しようとする試みに基づいて開発され[ 24 ]、その後、パフォーマンス プロファイリングによって提案された最適化[ 25 ]が行われ、プロファイリングとその他の考慮事項を考慮して考案された新しいアルゴリズム戦略が生まれました。[ 26 ]基本ブロックのレベルでデータを収集するプロファイラ[ 27 ]またはハードウェア支援に依存するプロファイラ[ 28 ]は、特定のコンピュータや状況に合わせてアルゴリズムを最適化する際にソフトウェア開発者を支援するのに十分な精度の結果を提供します。[ 29 ]パフォーマンス プロファイリングは、任意のテストベースの問題に適用される共進化アルゴリズムなど、複雑な状況で適用される複雑なアルゴリズムの特性を開発者が理解するのに役立ち、設計の改善につながる可能性があります。[ 30 ]