Loading article…
貪欲ランダム化適応探索手順( GRASPとも呼ばれる) は、組み合わせ最適化問題に一般的に適用されるメタヒューリスティックアルゴリズムです。GRASP は通常、貪欲ランダム化ソリューションの連続的な構築と、それに続く局所探索による反復的な改善からなる反復で構成されます。[1]貪欲ランダム化ソリューションは、達成されるソリューションの品質に応じて貪欲関数によってランク付けされた要素のリストから問題のソリューションセットに要素を追加することによって生成されます。貪欲ソリューションの候補セットに多様性を持たせるために、ランク付けされた候補要素は多くの場合、制限付き候補リスト(RCL) に配置され、ソリューションの構築時にランダムに選択されます。この種の貪欲ランダム化構築方法は、半貪欲ヒューリスティックとも呼ばれ、Hart と Shogan (1987) で初めて説明されました。[2]
GRASPはFeoとResende（1989）で初めて導入されました。[3] GRASPに関する調査論文にはFeoとResende（1995）、[1]とResendeとRibeiro（2003）があります。[4]
古典的なアルゴリズムには、Reactive GRASPなどのバリエーションがあります。このバリエーションでは、構築フェーズでのRCLの制限を定義する基本パラメータは、以前に見つかったソリューションの品質に応じて自動的に調整されます。[5] また、コスト摂動、バイアス関数、記憶と学習、部分的に構築されたソリューションのローカルサーチなど、検索を高速化するテクニックもあります。[4]
参照
参考文献
- ^ ab Feo, Thomas A.; Resende, Mauricio GC (1995). 「貪欲ランダム化適応探索手順」. Journal of Global Optimization . 6 (2): 109–133. doi :10.1007/BF01096763. S2CID 2110014.
- ^ Hart, JP; Shogan, AW (1987年7月). 「半貪欲ヒューリスティックス: 実証的研究」.オペレーションズ・リサーチ・レターズ. 6 (3): 107–114. doi :10.1016/0167-6377(87)90021-6.
- ^ Feo, Thomas A.; Resende, Mauricio GC (1989年4月). 「計算困難な集合被覆問題に対する確率的ヒューリスティック」.オペレーションズ・リサーチ・レターズ. 8 (2): 67–71. doi :10.1016/0167-6377(89)90002-3.
- ^ ab Resende, Mauricio GC; Ribeiro, Celso C. (2003). 「貪欲ランダム化適応探索手順」メタヒューリスティックハンドブック. Springer. pp. 219–249. ISBN 978-0-306-48056-0。
- ^ Prais, Marcelo; Ribeiro, Celso C. (2000). 「Reactive GRASP: TDMA トラフィック割り当てにおける行列分解問題への応用」INFORMS Journal on Computing . 12 (3): 164–176. doi :10.1287/ijoc.12.3.164.12639.