書店で本を購入するとき，栞を何枚かもらうのが習慣になっています。

漫画はすっかり電子書籍で読むことに慣れてしまいましたが，小説やノンフィクションはなかなか紙の本から離れられません。電子書籍で本を読むと文章に没入することができず，集中力がつづかないのです。

これにはいくつかの理由が考えられます。単純に集中力の衰えもあるでしょうし，紙とスクリーンの解像度の違い，あるいは，スマホの場合は読書以外の誘惑が多いのも理由のひとつかもしれません。

最近考えるのは「紙の本のページをめくる行為が没入感を高めているのではないか？」という仮説です。もちろん，電子書籍でもスクリーンをタッチしてページ移動できますし，中にはページめくりをアニメーションで再現するようなアプリもあります。しかし，紙のページをめくるときのざらついた音や触感も含めた豊かなフィードバックに比べると味気ない感じがするのはたしかです。

紙の本と栞の問題

とはいえ，紙の本には不便なことも多いですよね。

部屋では場所をとって荷物としてもかさばりますし，汚れも気になるところです。家に本棚を置いているような人なら誰しも経験していると思いますが，紙は放っておいても酸化や光による変色で劣化していきます（古本を買うと、ページの上の方が特に茶色くなっているのはこのせいです）。

しかし、数ある不便さの中でも，個人的に一番困るのが，最後に読んでいたページを忘れてしまうことです。

それを防ぐために紙の本では，最後に読んでいたページに栞を挟むわけですが，栞が手元にないことが多いのです。本に挟んでいた栞が紛失することもしばしばです。それで，書店では栞を余分にもらうのが習慣化してしまいました。

それでも栞の挟み忘れは発生します。そして，次に読むとき困るわけです。「あ，しまったな」と。「どこまで読んだかわからないぞ」

こういうとき，みなさんならどうしますか？

最後に読んだページを見つける

もちろん，最初のページから順番にめくっていけば，いつか必ず目的のページに辿り着きます（ページを開けば、それが目的のページだとわかるものとします）。でも，これは大変すぎますよね？

多くの人はおそらく，まずは適当なページを開いてみるのではないかと思います。いくら栞を挟み忘れたといってもだいたいの位置は覚えているはず。

では，適当に開いたページが目的のページとは違った場合はどうしましょう？　読んでいる本のページ数がたったの数ページしかないか，よほど運が良くないかぎり違うページである可能性が高いです。

そのページが読んだことのあるページであれば，目的のページはさらにその先にあるはずですから，ページを進めるでしょう。逆に，読んだことがないページであればそれより前のページに戻るはずです。

何を当たり前の話を，と思われるかもしれません。では，次にどのページを開くべきでしょうか？

ここでも適当に，という人もいるかと思いますが，実は当てずっぽうよりもう少し賢い方法があります。それは，目的のページがありそうな範囲のちょうど中間地点のページを開くことです。

この手順を箇条書きでまとめてみましょう。

1. 適当なページを開く

2. もし，そのページが前回最後に読んでいたページなら→おめでとうございます。終了です！🎉

3. もし，そのページが読んだことのあるページなら，そこに左手の人差し指を挟み，そのページから右手の人差し指（または最終ページ）までの半分の位置を開きます

4. もし，そのページが読んだことのないページなら，そこに右手の人差し指を挟み，そのページから左手の人差し指（または最初のページ）までの半分の位置を開きます

5. 2 に戻り繰り返します

ずいぶんと回りくどいことをしているように感じますよね。

ところが，一見回りくどく見える上の手順に従うと，たとえ最初のページがまったくの当てずっぽうでも，確実に目的のページが見つかります。当てずっぽうに探しつづけて，あっちこっちとページを何度も行ったり来たりするよりも確実な方法なのです。興味がある方は，実際に手近な本を手に取って上の手順を試してみてください。[1]

徐々に左右の人差し指が近くなり，目的のページに近づいていくのがわかると思います。

このような，問題解決のために解を求める一連の手続きを，数学や計算機科学ではアルゴリズムといいます。

余談ですが，ここで例に挙げた「最後に読んだページを見つけるアルゴリズム」は効率的でもあります。一見回りくどく見えるアルゴリズムですが，1,000ページの分厚い本であっても，驚くほど少ないページしか見る必要がありません。[2]

アルゴリズムとデータ構造

身近なアルゴリズムの例として，最後に読んだページを見つけるアルゴリズムを紹介しました。形式化されたステップを繰り返すことで解に近づける「アルゴリズム」は，プログラミングにおいて欠かせない道具のひとつです。

そして，アルゴリズムの他にもうひとつ重要なのがデータ構造です。

さきほどのアルゴリズムの例だと「1,000ページの書籍」というページの集まりは，アルゴリズムの処理対象となる「具体的なデータ」です。しかし，この具体的なデータを抽象化し，必要な構造を抜き出すと以下のようなデータ構造になります。[3]

• 大小関係のあるデータが順番に並んでいる……書籍のページは小さい数字から大きい数字に並んでいます。

• 任意の位置のデータにアクセス可能……書籍の好きなページを開くことができます（実際のところ，狙ったページを一発で開くのは難しいのですが，そこは無視することにします）。

ここで面白いのは，同じデータ構造に対しては，同じアルゴリズムが適用できることです。

つまり，上の構造に当てはまるのであれば，データは「書籍」である必要はなく，たとえば，「身長順に並んだ生徒の一覧」でもいいわけです。そして，この一覧の中から「身長 163 cm の生徒を見つける」ときにも，同じアルゴリズムが使えます。

アルゴリズムを探して

プログラムにとっては，効率的なアルゴリズム，従来の方法ではうまく解けない問題を解くことができるアルゴリズムが重要です。そのため，プログラマーは世の中の「アルゴリズム的なもの」「データ構造的なもの」に敏感になります。

たとえば，オフィスビルや商業施設でエレベーターを待っているとき，長時間待たされて苛々した経験はないでしょうか？

こういうときのエレベーターは，待たされている側のことはお構いなしに，理不尽な動きをしているように思えるものです。こちらとしては，適当に時間潰しをしながら待つしかないわけですが，同時に頭の片隅で「このエレベーターがどのようなアルゴリズムで動いているのか？」と興味が湧くわけです。

同じように，『カンデル神経科学』の第 3 章「遺伝子と行動」を読んでいるときも同様に，このアルゴリズム的なものセンサーがピピッと反応しました。
本書の中でも，この章で扱う遺伝子は特に，アルゴリズムやデータ構造と相性が良さそうです。遺伝子の構造（コード領域と非コード領域），RNAへの転写からタンパク質への翻訳，などを読むとアルゴリズムの本を読んでいるような錯覚に陥ります。

実際，計算機科学の世界では，遺伝的アルゴリズムというアルゴリズムが広く使われています。このアルゴリズムでは，自然界での適者生存という考え方をアルゴリズムに取り入れており，そこで用いられるデータ構造は遺伝子を模倣したものです。[4][5]

試しに，遺伝的アルゴリズムの実際の動きを，簡単な例をとって説明してみましょう。

この試験で，できるだけ高得点を取るにはどうしたらよいでしょうか？

もちろん，すべての問題の○×の組み合わせを試すことができれば，いつかは満点を取ることができます。しかし，組み合わせの数は膨大であり，途方もない時間がかかりそうです。[6]

では，遺伝的アルゴリズムを使って，満点ではなくても高得点に近い解答を取る方法を紹介しましょう。以下のような流れになります。

1. 第1問から第100問までの解答として，「○」と「×」をランダムに並べた「遺伝子」をたくさん作ります。「○××○×○……」「×○○○××……」……（その他多数）といった感じです。これが初期世代になります

2. すべての遺伝子の成績（合計得点）を算出します

3. 成績優秀な遺伝子を選択します

4. 生き延びた遺伝子同士を交わらせて（交差），次の世代を作ります [7]

5. 2 に戻り繰り返します

以上の手順を繰り返し世代交代を重ねていくと，そのうち合計得点が伸びなくなっていくはずです。この時点でアルゴリズムは収束しており，高得点に近い解答が求められるようになっています。[8]

どうでしょう？　遺伝的アルゴリズムが自然選択や遺伝子の仕組みに影響を受けていることがよくわかるかと思います。[9]

自然と模倣のアルゴリズム

今回の記事では，身近な例からアルゴリズムとは何かについて説明し，自然界からアイデアを得たアルゴリズムとして遺伝的アルゴリズムを紹介しました。

前回の記事で紹介したニューラルネットワークもまた，自然界（生物の神経回路網）からヒントを得たアルゴリズム（とデータ構造）です。計算機科学の世界では，このようにして発明されたアルゴリズムが他にもたくさんあります。[10]

驚くべきは，自然界からヒントを得て作られたアルゴリズムが，自然がまったく意図しない形で利用され，実際に成果を出していることです。自然選択と進化の過程で効率的な戦略を生み出す自然のシステムにも，それをうまく利用する人間の創造力にも頭が下がるばかりです。

※この連載の記事の内容は筆者個人の見解に基づくものであり，所属組織を代表するものではありません。

脚注

[1] 最後に読んだページを探す手順 具体例で考えてみます。1,000ページの本を読んでいるとして，最後に読んだページを忘れてしまった。しかも悪いことに，だいたいどのあたりかの見当もまったくつかないとします（積読したままだいぶ時間が経ってしまったのでしょう）。

しょうがないのでまずは適当なページを開いてみます。843 ページでした。これは最後に読んだページではなく，読んだ記憶もないページです。ということは，目的のページは 843 ページよりも前にあるはずです。

さて，次に開くページですが，目的のページは 843 ページよりも前にあるはずなので，843 を半分にした 421 ページにしましょう（端数は切り捨てることにしました）。残念ながら，421 ページも目的のページではなく読んだ記憶もありません。ということは…そう，421 ページよりも前にあるはずなので，421 を半分にした 210 ページを開きます。このとき，すでに確認した 421 ページよりも後に目的のページはないはずなので，目印として右手の人差し指を挟んでおきましょう。

210 ページを開くと，そこも目的のページではありませんでしたが，今度は読んだことのあるページでした。つまり，最後に読んだページは，210 ページよりも後ろにある，ということです。

210 ページよりも後ろにあることがわかったので，ここも指を挟んでおきましょう。左手の人差し指を挟みます。そうです。いまページに挟んでいる二本の指は，目的のページがありそうな範囲を表しています。次に開くページは，目的のページがありそうな範囲のちょうど中間地点のページなので，315 ページを開きます。これを繰り返します。

[2] 驚くほど少ないページしか見る必要がありません　1,000 ページの本の場合，たかだか 10 回ページを見れば，最後に読んだページを見つけることができます。10,000 ページでも，たかだか 14 回です。

[3] 書籍のデータ構造　ここでは話を簡単にするため，データが有限個であること，データに重複がないこと，には触れていません。同じデータが重複している場合，このアルゴリズムだとそのうちのいずれかひとつを見つけて終了します。

[4] 遺伝的アルゴリズム　遺伝的アルゴリズム （genetic algorithm = “GA”） は，生物の進化過程をモデルとした手法で，進化論的計算手法や進化計算と呼ばれる手法のひとつです。また，最適化の分野においては，メタヒューリスティクス（発見的知識に基づく最適化アルゴリズムの枠組み）の一手法と見なすこともできます。

古典的な GA および，GA の発展と活用事例については，以下の文献を参考にしました。

Katoch, S., Chauhan, S.S. & Kumar, V. A review on genetic algorithm: past, present, and future. Multimed Tools Appl 80, 8091–8126 (2021). https://doi.org/10.1007/s11042-020-10139-6

[5] 最適化　すこし前に取り上げたエレベーターの運行制御もまた，最適化問題のひとつです。乗客の待ち時間と乗車時間が最小化されるように，あるいは，あまりに多くの乗客が乗り合わせてエレベーターが混雑しないように，など複数の制約条件を満たす必要があります。

[6] 100問の解答組み合わせ数　100 問の解答の組み合わせの数は，2 の 100 乗 = 1,267,650,600,228,229,401,496,703,205,376 通りです。

実際に，ありうる解答の組み合わせを順番に試していく簡単なプログラムを組んでみたところ，30 問の組み合わせを試行するのに 400 秒ほどかかりました。10 問増えるごとに組み合わせの数が 1,024 倍になるため，単純計算で 100 問の組み合わせを試行するのに 14,974,525,884,289,846 年かかることになります。

[7] 生き延びた遺伝子同士を交わらせて（交差），次の世代を作ります 遺伝的アルゴリズムでは，世代交代を重ねて最適解へと収束させることが目的です。選択によって成績優秀な遺伝子（解候補）の特徴を次世代へ継承しつつ，交差によって現世代とは異なる解を探索することができるわけです。

しかし，成績優秀な解候補の特徴のみを残す，ということは逆に，全体の多様性が少ない，ということでもあります。世代を重ねることによる解の変化が少ない，ということであり，最適解に辿り着くよりも早く収束してしまう可能性が高くなります（局所最適解に陥ってしまう，とも言います）。

そのため，遺伝的アルゴリズムでは，稀に突然変異を起こすなど，多様性を維持するための試みがさまざまに行われています。

[8] この時点でアルゴリズムは収束 今回のように単純な問題であれば，簡単な遺伝的アルゴリズムでも割とすぐに高得点を獲得することができます。また，最適解（満点を獲得すること）も分かっているので，最適解に到達するまで世代を重ねてみることができます。

手元で試してみたところ，第 400 世代くらいで 90 点を超え，第 800 世代くらいで 100 点に収束しました。処理にかかった時間は 1 分程度です。

[9] 遺伝子の仕組みに影響を受けている 他の類似アルゴリズムにも言えることですが，自然界をそのまま模倣するのではなく，あくまで参考にしている，という点に注意が必要です。たとえば，DNA の二重らせん構造は，ここで紹介している遺伝的アルゴリズムでは現れません。

[10] 自然界からヒントを得たアルゴリズム ミツバチの採餌行動をモデルにした人工蜂コロニーアルゴリズム，クジラの捕食行動をモデルにしたアルゴリズム，などなど。紹介しきれないほど多くの例があります。

2022.8.8　石川 尊教（@takanori_is）