はじめに
こちらは「群知能と最適化2019 Advent Calender」
です！
12/2日の記事として、ganariyaが担当します！
卒論が迫っていて、だいぶ内容が荒いです！絶対に適宜修正していきます！申し訳ないです！
この記事で扱うこと
- はじめに
- 最適化とは？
- 群知能とは？
はじめに
みなさんは「群知能」を知っていますか？
群知能とは、「生物の群れ」から知能を得た最適化や心理学の一般的な学問を差します。
最適化のように、コンピュータサイエンスの視点のみならず、当然ながら生物学、人間としての心理学など、多くの細分化された学問です。
今回のAdventCalenderでは、これらのうち「最適化」「群知能」何でもありのごった煮Calenderです！
是非 気軽に書いていきましょう！
最適化とは？
唐突ですが、「最適化」と呼ばれると何を思い浮かべますか？
これは、おそらくその人の経験や背景によって変わると思います。
人によってはアルバイトのシフト、先生ならテストの効率的な採点、社長なら社員の効率的な採用・利用方法など人それぞれです。
コンピュータサイエンスにおける「最適化」とは、基本的に「最適化問題」を差します。
Wikipediaから引用させていただくと
最適化問題（さいてきかもんだい、英: optimization problem）とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最小（もしくは最大）となる状態を解析する問題である[1]。こうした問題は総称して数理計画問題（すうりけいかくもんだい、英: mathematical programming problem, mathematical program）、数理計画とも呼ばれる[1]。最適化問題は、自然科学、工学、社会科学などの多種多様な分野で発生する基本的な問題の一つであり、その歴史は18世紀の変分問題に遡る[2]。1940年代に線型計画法が登場して以来、理論的な研究や数値解法の研究が非常に活発に行われ、その応用範囲はいろいろな分野に拡大されていった[1]。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。物理学やコンピュータビジョンにおける最適化問題は、考えている関数をモデル化された系のエネルギーを表すものと見なすことによって、エネルギー最小化問題と呼ばれることもある。
のようになります。
つまり、「最適化したい現実問題を、何かしらコンピュータの仕組みとアルゴリズム・数学でなんとかする」のが、「最適化問題」になります。
この最適化問題は、基本的にNP困難と呼ばれる難しい問題を差します。
「$y=x^2$で$x=4$のときの$y$の値がわからないよぁ〜」みたいなものは最適化とは呼びません。
人間的に・コンピュータ的に、普通に考えたらむちゃくちゃ難しいものが「最適化問題」になります。
最適化問題の典型例「巡回セールスマン問題」
最適化問題で、最も良く挙げられるNP困難な問題といえば、「巡回セールスマン問題」です。
おそらく聞いた人も多いと思います。
巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
以上のような概要です。
例えば、$N=20$の都市があったとしましょう。
これの重み付きハミルトンパスの最小化問題が、巡回セールスマン問題になります。
これの全探索の場合の計算量は$O(N!)$です。
また、ビット全探索をしても$O(N2^N)$です。
「なんだ、N!の計算でできんじゃないか？」となる人もいるかもしれません。
これはとてつもなく、計算量の概念では厄介な部類に入ります。
例えば、$N=30$の時点で、$2.6{\times}10^{32}$回の計算です。
もっともはやいC++でも$10^8$回の計算に約$1$秒かかるため、これは一生かかっても終わらない計算、ということになります。
現実の問題なら、$N=1000$などザラにあります。
これでは、普通に解くことは絶対にできません。
このように、現実の問題は、必ずしも「最適解」は求まりません。
計算量の問題やメモリリソースなど多くの問題が存在します。
そのため、「最良解」と呼ばれる、一番良い解ではないが、許容できる解を探す、というのが「最適化問題」の大事な目的になります。
最適化手法
「最適化問題」を解く手法には多くの種類が存在し、かなり国柄を表しています（体感です）
それぞれ、特色やメリット・デメリットが存在します。
数理最適化
日本など、システム系に強い国が多く扱っている題材です。
最適化の中で、問題を「数理的なモデル」で捉えて、基本的には「最適解」を求めます。
他手法と比べて異なる点として
- 基本的に同じ解が求まる
- ヒューリスティック的に、高速に近似解を求めるものもあるようです
- 静的手法のため、問題定義の変化にあまり強くない
- 数学が辛い（僕には無理です）
ヒューリスティック・メタヒューリスティクス手法
アメリカなどの海外でよく使用されている手法のようです。
問題を「プログラミングでシミュレーション」して、近似解を求めます。
数学的背景よりも、基本的には「動いてなんぼや！」の精神に近く、僕がすきなジャンルです（数学ができないので）
群知能による最適化は、このメタヒューリスティクス手法に入ります。
他にも多くの手法が存在するようです（もっと細かく区分されます）
僕はものすごく浅いので、理解が足りません（勉強していきます）。
群知能とは？
最適化についてこれまで見てきました。
この「最適化」の手法の一つに、生物の動きに着目した「群知能」が存在します。
群知能については、自分の記事群知能を救いたい
で扱っています。
こちらを参考にすると、群知能の内容がよりわかりやすいと思います。
最後に
群知能は、「生物」という生き物の動き・性質を利用した学問です。
そのため、シミュレーションを実際に自分で書いてみると、生命の神秘を感じます。
（本当に単純なルールのみで、最適化が行われます。）
群知能はコンピュータサイエンスのみならず
- 人間心理学
- 行動学
- ロボット行動学
など多くの学問で扱われています。
面白い本としては、群れのルール 群衆の叡智を賢く活用する方法
があり、「人間心理学」に近い内容が乗っています。
中古もかなりお安いので、ぜひ読んでみてください！
ただ、実際に群知能による最適化はやってみるほうが早いです。
自分で実装すると、より直感的に身につきます。
ぜひ触ってみてください。