アルゴリズム

Let us study on Let us study on optimization problem

進化的アルゴリズム：進化的アルゴリズム（Evolutionary Algorithm, AE）と は、「進化的計算の一分野を意味し、人工知能の一部である。個体群ベースのメタヒューリスティックな最適化アルゴ リズムの総称である。そのメカニズムとして生殖、突然変異、遺伝子組み換え、自然淘汰、適者生存といった進化の仕組みに着想を得たアルゴリズムを用いる。 最適化問題の解の候補群が生物の個体群の役割を果たし、コスト関数によってどの解が生き残るかを決定する。それが繰り返された後、個体群の進化が行われ る」。ウィキ（日本語）には、「遺伝的アルゴリズム」「遺伝的プログラミング」「進化的戦略」「進化的プログラミング」が紹介されている。

◎実装による分類

アルゴリズム分類の1つの方法として、実装手段による 分類がある。

再帰 / 反復	再帰アルゴリズムは、ある条件が成り立つまで自身を再帰的に 呼び出すものであって、関数型言語でよく使われる。反復アルゴリズムは、ループのような反復構造と場合によってはスタックなどのデータ構造を補助的に使 い、問題を解く。一部の問題は、どちらか一方の実装が自然である。例えば、ハノイの塔は再帰的実装の方が分かりやすい。再帰アルゴリズムは全て反復アルゴ リズムでも実装可能であり、逆も同じである（ただし、複雑さは変化する）。
論理	アルゴリズムは、制御された演繹であるとも言われる。これを アルゴリズム = 論理 + 制御 と表現することもある[13]。論理部分は計算で使われる公理を表し、制御部分は公理に演繹が適用される方法を決定する。これは論理プログラミングという パラダイムの基本である。純粋な論理プログラミングでは、制御部分が固定されていて、アルゴリズムは論理部分だけで指定される。この手法の魅力は、プログ ラム意味論的なエレガントさがある点である。公理の変化は定式化されたアルゴリズムの変更を伴う。
逐次 / 並列 / 分散	アルゴリズムは通常、コンピュータが一度に1つのアルゴリズ ム内の1つの命令だけを実行するものと仮定して議論される。このようなコンピュータは、シリアル・コンピュータなどと呼ばれることもある。そういった環境 向けに設計されたアルゴリズムは逐次アルゴリズムと呼ばれ、それとは対照的な分類として並列アルゴリズムや分散アルゴリズムがある。並列アルゴリズムは、 複数のプロセッサが同時並行して同じ問題を解くのに使えるコンピュータアーキテクチャで有効である。また、分散アルゴリズムは、複数のマシンがコンピュー タネットワークで相互接続された環境で使われる。並列/分散アルゴリズムは、問題を分割して解き、その結果を集めて最終的な結果を得る。その場合、個々の プロセッサの計算時間（実行命令数）だけでなく、プロセッサ間の通信オーバーヘッドも計算資源の消費量として問題になる。例えば、ソートアルゴリズムは効 率的に並列化できるものもあるが、通信オーバーヘッドは高くつく（部分数列をソートした結果を集めるには、結局部分数列そのものをやりとりしなくてはなら ない）。反復アルゴリズムは一般に並列化可能である。並列アルゴリズムがない問題は、本質的に逐次的な問題である。
決定性 / 非決定性	決定性アルゴリズムでは解法の全ステップが常に正確に決定されるが、非決定性アルゴリズムはいわば推量や推測で問題を 解くものであり、ヒューリスティクスを使ってより正確に推測する。
正解 / 近似解	一般にアルゴリズムは正解を得るものだが、近似アルゴリズム は近似解を求め、その近似性に一定の根拠があれば、これも広義のアルゴリズムとして含めて考えることができる。近似には、決定性の戦略もあれば、乱択の戦 略もある。多くの難しい問題では、近似アルゴリズムしか実用的な解法が存在しない。近似アルゴリズムはその近似解の近似性能も評価・保証などがされる必要 がある。

◎計算パラダイムによる分類

別の分類方法として、アルゴリズムの設計方法論や パラダイムで分類する方法がある。それぞれ異なるいくつかのパラダイムが存在する。さらに、個々のパラダイムの中にも様々な異なる形式のアルゴリズムが含 まれている。以下に主なパラダイムを挙げる。

分割統治法	分割統治法は、問題を（通常再帰的に）複数または単一の同 じ種類のもっと小さい問題に還元していき、最終的に容易に解ける程度の大きさにする。分割統治の例としてはマージソートがある。ソートは入力データを分割 してそれぞれに対して行われ、統治フェーズではそれらの結果をマージする。分割統治法を単純化したものとして decrease and conquer algorithm がある。これは、問題を全く同じ複数の部分問題に分割し、その解をより大きな問題を解くのに利用する。分割統治法では一般に分割された個々の部分問題は全 く同じではないため、統治フェーズは decrease and conquer algorithm よりも複雑になる。decrease and conquer algorithm の例として二分探索がある。
動的計画法	部 分問題の最適解から全体の最適解が得られるような構造の問題や、同じ部分問題の最適解が様々な問題の解法に有効であるような問題の場合、動的計画法を使っ て既に計算済みの解を再計算するのを避けることができ、解法を効率化できる。例えば重み付けのあるグラフでの最短経路を求める場合、始点に隣接する全ての 頂点について最短経路が分かっていれば、容易に最短経路が求められる。動的計画法とメモ化は密接な関係がある。分割統治法との違いは、分割統治法では部分 問題は多少なりとも独立しているのに対して、動的計画法では部分問題が重複している。単純な再帰との違いは、再帰部分をキャッシュ化またはメモ化する点で ある。部分問題が互いに独立している場合、メモ化は何の役にも立たない。したがって、動的計画法はあらゆる複雑な問題の解法とはならない。動的計画法で は、メモ化あるいは既に解かれた部分問題の表を使うことによって、指数関数的性質をもつ問題を多項式レベルの複雑性に削減することができる。
貪欲法	貪 欲法は動的計画法に似ているが、部分問題の解を各段階では知る必要がないという点が異なる。その代わりに、各時点で最もよい選択と思われるものを選んでい く。貪欲法では、それまでの選択と現時点の局所最適解から最適と思われる解を構築していくのであって、考えられるあらゆる解を評価することはない。した がって網羅的ではなく、必ずしも正解にたどり着けるわけではない。しかし、性能は非常によい。貪欲法としてよく知られている例として、最短経路木を求める クラスカル法、プリム法、ダイクストラ法などがある。
線型計画法	線 型計画法で解ける問題では、制約条件として入力に関する線型の不等式があり、入力に関するある線型の関数を最大化（または最小化）する値の組合せを求める ものである。有向グラフに関する最大フロー問題など、多くの問題が線型計画問題として記述でき、シンプレックス法などの汎用アルゴリズムで解くことができ る。線型計画法の解空間を整数に限定したものを整数計画法と呼ぶ。
還元	この技法は、難しい問題をほぼ最適なアルゴリズムが既知の別の問題 に変換するものである。例えば、ソートされていない数列から中央値を求める選択アルゴリズムとして、まずその数列をソートし、そこから真ん中に位置する値 を取り出すという方式がある。
探索と数え上げ	ェスの手を考えるなどといった問題は、グラフ問題としてモデル化で きる。そのような問題では、比較的よく研究されているグラフ探索アルゴリズムを使うことができる。このカテゴリーには、探索アルゴリズム、分枝限定法、 バックトラッキングも含まれる。
確率的パラダイムとヒューリスティクス	ここに分類されるのは広義のアルゴリズム、ないし、遺伝的アルゴリ ズムのように（名前に反して）アルゴリズムではないものである。 乱択アルゴリズム - 選択を無作為（あるいは擬似無作為）的に行う。問題によっては、無作為性をもった解法が最も性能がよいと証明されているものもある。 遺伝的アルゴリズム - 生物の進化過程をまねた手法で解を求めるもの。無作為な突然変異を加えて、次世代の解を生成していく。自然淘汰と自己複製をエミュレートしているものと看 做す視点から「遺伝的」という命名がされた。 ヒューリスティクス - 計算資源が限られている状況での近似解を求めることを目的としている。正解を求めるのには適さない。例えば、局所探索法、タブーサーチ、焼きなまし法と いった、何らかの無作為性を導入して確率的に解を発見しようとするアルゴリズムがある。例えば焼きなまし法という名前は、冶金学の焼きなましに由来する。 加熱と冷却によって金属結晶の欠陥がなくなるように、無作為性を与えて局所的な最適解に陥るのを防ぎ、徐々に無作為性を小さくすることによって最終的に1 つの解に落ち着くという手法である。
★
研究分野による分類	科学のどんな分野にも固有の問題があり、効率的なアルゴリズムが必 要とされている。ある分野の問題はまとめて研究されることが多い。そのような分類として、探索アルゴリズム、ソートアルゴリズム、マージアルゴリズム、数 値アルゴリズム、グラフアルゴリズム、文字列アルゴリズム、計算幾何アルゴリズム、組合せアルゴリズム、機械学習、暗号理論、データ圧縮アルゴリズム、構 文解析などがある。 各分野はオーバーラップしており、ある分野でのアルゴリズムの進歩が、時には全く異なる分野での改善につながることがある。例えば、動的計画法は、本来、 産業における資源消費の最適化のために発明されたが、現在では様々な分野での各種問題に適用されている。
計算量による分類	アルゴリズムは、入力長に対する計算時間で分類される。あるアルゴ リズムは入力長に対して線形時間で完了する。また別のアルゴリズムは指数時間以上かかるし、場合によっては完了しないこともある。さらに、問題によっては 計算量の異なる複数のアルゴリズムが存在するし、効率的なアルゴリズムが全く知られていない問題もある。問題によっては、別の問題への写像が存在する。以 上のようなことから、計算量による分類は、アルゴリズムについてではなく、問題について行うのが適当とされている。つまり、問題を解く最善のアルゴリズム の計算量に基づいて、問題を分類する。
計算能力による分類	アルゴリズムは計算能力によっても分類される。一般にアルゴリズム は計算能力によって階層的に分類される。「再帰的クラス」とは、全てのチューリング計算可能関数についてのアルゴリズムを含むクラスである。このような階 層化によって、計算に必要とされる計算資源（時間とメモリ）を制限できる可能性が生じる。「部分再帰クラス」は、全てのチューリング計算可能な関数を得る ことはできない。例えば、多項式時間で実行されるアルゴリズムには多くの重要な計算が含まれるが、チューリング計算可能な関数全体を含むことはない。原始 再帰関数で実装されるアルゴリズムのクラスは、別の部分再帰的クラスの例である。 Burgin (2005, p. 24)[14] は、関数を計算するアルゴリズムは有限ステップ後に必ず出力が決定されなければならないという一般的条件を緩めたアルゴリズムの汎用的定義を行った。彼は 「超再帰的クラス」を「チューリングマシンで計算可能でない関数を計算可能なアルゴリズムのクラス」と定義した(Burgin 2005, p. 107)[14]。これはハイパーコンピュータの手法の研究と密接に関係している。

【ご注意】このページ は数学とは一生無縁だと思 いこんでいる学生のための啓蒙ページですので、その筋の専門家が見たら冷 笑に付される類のものかもしれません。専門家の皆さん、どうか暖かい眼で見守ってくださいませ。

【動機と課題】

潜水艦を探索する方法として、ラグランジュ乗数法が使われると いう話を聞いた（出典：荒川泓「最適化」『日本大百科全書』電子版、 1999年）。

これについて、インターネット上において 「ラグランジュ乗数法」と「潜 水艦」で日本語検索をかけてみたところ言及している文献（ウェブ ページ）は見つからなかった。

これを素人にもわかりやすく解説するには どうしたらよいか？

→これに関しては現役の自衛隊の教官の執筆になるＯＲの入門書で発見！　この場合の 敵の潜水艦はディーゼル駆動で、洋上で充電している際に、航空機等により発見され、さらに現場で深度調整をできない爆雷を投下して撃滅する最適な方法は何 かということのようだった。

齋藤芳正、2002『はじめてのＯＲ』（ブルーバックス）、Pp.18-21、講談 社.



映画『Uボート』艦長のモデルとなった、ハインリヒ・レーマン=ヴィレンブロック大尉（写真中央）。1940年から1942年まで U96(Type-7/U-96)の艦長に就任、エース級の戦果を出した者のみに与えられる騎士鉄十字章を叙勲している＿＿ウィキより

【現時点でわかっている知識】

上掲の荒川の解説によれば、オペレーションズ・リサーチはもと もと軍事作戦研究にはじまる。

1950年代後半のコンピュータの実用化 はその研究に拍車をかける。そのなかで注目されたのが、探索労力の最適配分問題 （optimal allocation of serach effort）［→データマイニングという発想に繋がるで はないか！］であったという。

これは、複雑な部品からなる機械の故障を 発見することであり、これを一般化すると、「探索すべき目標が多数の箱のどれか １つに入って」おり、それを最小限の努力で発見するには、ど〜すればよいのかということになる。

さらに、これを数学問題として定式 化すると、「それぞれの箱に投入する探索労力の総和がある値に制限されるという条件下 で発見確立を最大にするために、個々の箱に対する探索労力配分をどのようにするか」ということになるらしい。

しかし、数多あるラグランジュ乗数法につ いての説明は、いきなりpdfファイルで、数式ガンガンという説明が多く、ここで、無知な私の 頭は思考停止（始皇帝死？）

アルゴリズムってなんでしょ か（国立情報学研究所）︎▶蟻コロニー最適化（ウィキペディア）▶Ant colony optimization algorithms︎︎▶︎公費（運営費 交付金）等による図書購入に関するアルゴリズム▶種の連続性／ 非連続性 と進化に関する方法論︎︎▶人文社会系ゼミで学ぶ高校生のためのライフデザイン ︎▶︎︎ビッグデータだけに依存すると予測を誤る▶︎利他行動の進化論的 解決を「老人殺し」に適応できるか？▶線型計画法︎︎▶︎▶︎

最適化問題（Optimization problem）という分野を理解するミニ用語集

ア ルゴリズム：アルゴリズ ム

コンピュータによる計算方法（＝コンピュータプログラムの設計図）

最 適化：

目的に対してもっとも適切な計画をたて、それを実行すること。

デー タマイニング：Data mining

データの集積の中から、法則となりうるような知識を抽出すること。

【謝辞と資料】

今回のお師匠さま、宇野 毅明先生に感謝！（追伸：メールもいただきました！02030）

宇野 毅明のページ、http://research.nii.ac.jp/‾uno/index-j.htm（2002 年3月7日〜2017年12月24日）

お師匠差さまの研究テーマは、アルゴリズムの高速化である

最適化とアルゴリズムの中の、列挙アルゴリズム、木構造アルゴリズム、近似解法高 速化を研究している（らしい）。

リンク

• 進化的アルゴリズム︎▶公費（運営費交付金）等による図書購入に関するアルゴリズム▶大学生のためのライフデザイン︎︎▶ビッグデータだけに依存すると予測を誤る︎▶︎︎線型計画法▶ロジスティクス︎▶︎︎戦略の２つの意味▶︎兵 站▶︎︎▶︎▶︎
  

文献

• 荒川泓「最適化」『日本大百科全書』電子版、1999年

その他の情報