AI情報
AIの分野で活用されている手法の一つに「遺伝的アルゴリズム」があります。
データを遺伝子と考え、生物のように進化を繰り返すことで最適解を導き出す手法です。
この、「遺伝的アルゴリズム」がどのようなものなのか、またどのような分野で活用されているか、事例についても紹介をしていきます。
遺伝的アルゴリズムについて理解を深めることで、AIを活用したアイデアの幅が広がるかもしれません。
本業でシステムエンジニアをしています。 分かりやすい記事を心がけています。
AIの一つ遺伝的アルゴリズムとは？
遺伝的アルゴリズムとは、「進化論の考え方に基づいたアルゴリズム」のことです。
データを遺伝子のように変形、選択、交叉、突然変異などを繰り返すことで最適解を探索するアルゴリズムです。
遺伝的アルゴリズムは、生物の進化の過程で起こる、環境への適応や強い個体が生き残り、弱い個体は淘汰される現象からヒントを得て誕生したアルゴリズムです。
AIにおける遺伝的アルゴリズムでは、さまざまな個体のグループから最も適していると思われる個体を選び出し、組み合わせたり、変形させたりすることによって新しい個体を作り出します。
この手法を繰り返すことで、最適解に近づけていくのです。
遺伝的アルゴリズムの歴史
遺伝的アルゴリズムの概念は、ジョン・ホランドによって1960年代にはじめて提案されました。
生物学の進化論にインスパイアされ、集団内での遺伝子の進化的な操作をコンピュータ上でシミュレートすることを考えました。
ホランドは、1975年に「遺伝的アルゴリズムと適応システム」という本を出版し、遺伝的アルゴリズムの基本概念を広め、遺伝的アルゴリズムの発展に大きな影響を与えました。
1980年代になると、遺伝的アルゴリズムはAIの分野で広く使われるようになりました。
遺伝的アルゴリズムの３つの概念
遺伝的あるがリズムには３つの概念が存在します。
遺伝的アルゴリズムの基本である下記の３つの概念についてご紹介します。
- 選択
- 交叉
- 突然変異
それでは、一つずつ見ていきましょう。
選択
選択は、集団内の個体から次世代の個体を選び出すプロセスです。
適応度と呼ばれる評価基準に基づいて、優れた個体を選択することで、次世代に適応度の高い個体を残します。
選択の方法には、ルーレット選択、トーナメント選択などがあります。
ルーレット選択は適応度の高さに応じてルーレットの面の大きさが決まり、個体数に応じてルーレットが回され選択される仕組みです。
トーナメント選択は「全体からランダムで特定の個数を選ぶ」、「適応度の高いものを選択する」という方法を繰り返し行うことで適応度の高いものを選択します。
選択の目的は、良い個体を選び出し、その遺伝子情報を次世代に伝えることです。
交叉
交叉は、選択された個体同士の遺伝子情報を組み合わせる操作です。
交叉によって、新たな個体（子孫）が生み出されます。
一般的には、2つの親個体から一部の遺伝子情報を交換することで、新たな解を生成します。
交叉は探索空間を多様化させる役割を果たし、解の多様性を維持することが重要です。
交叉には「一点交叉法」と「二点交叉法」が存在します。
一点交叉法
一点交叉法は遺伝子に切れ目を入れ、切れ目から後を入れ替えていく方法です。
具体的には親１、親２の文字列上で切れ目をランダムに１カ所選び、切れ目の右側の２つの親の文字列をそのまま変換して、子１、子２を生成します。
二点交叉法
遺伝子の切れ目が二つあるものが二点交叉法です。
具体的には、切れ目の間で交互に２つの親の文字列をそのまま変換して、子１、子２を生成します。
突然変異
突然変異は、個体の遺伝子情報をランダムに変化させる操作です。
集団内の多様性を保つために重要であり、探索空間内の新たな領域を探索するという効果があります。
また、突然変異率として事前に設定ができるため、ある程度コントロールをすることができます。
突然変異は、選択や交叉によって生じる解の局所最適解への収束を防ぐ役割もあります。
遺伝的アルゴリズムの4つのメリット
遺伝的アルゴリズムにはいくつかのメリットがあります。
ここでは、代表的な下記4つのメリットについてご紹介をします。
- 最適解をみつけられる
- 活用できる範囲が広い
- 適度にランダム性がある
- 理屈がシンプルで使いやすい
それでは、一つずつ見ていきましょう。
最適解をみつけられる
遺伝的アルゴリズムは、解の候補を集団として表現し、その集団を進化させることで最適解を見つける能力があります。
選択、交叉、突然変異といった操作によって、探索空間を広くカバーしながら最適解に収束していきます。
特に多数の局所最適解が存在する問題や複雑な問題に対して、効果的に解の探索を行うことができます。
活用できる範囲が広い
遺伝的アルゴリズムは、さまざまな分野や問題に適用できる汎用性があります。
最適化問題、機械学習、スケジューリング、ロボット工学、ゲーム戦略など、さまざまな領域で適用されています。
また、問題の特性に合わせて適切に調整することで、効率的な解の探索が可能になります。
適度にランダム性がある
遺伝的アルゴリズムは、選択や突然変異によってランダム性を持っています。
このランダム性によって、局所最適解に陥るリスクを減らし、解の多様性を維持しながら探索空間を広げることができます。
ランダム性があるため、幅広い可能性の中で吟味していくことが可能です。
理屈がシンプルで使いやすい
遺伝的アルゴリズムの基本的なメカニズムは直感的で使いやすいという特徴があります。
集団内の個体を遺伝子情報で表現し、適応度に基づいて進化させるというアプローチはシンプルでありながらも効果的です。
複雑な問題を複雑なまま扱うことができるため、「単純化思考」では不可能であった新たな発見をする可能性もあります。
また、遺伝的アルゴリズムのパラメータ調整も比較的直感的であり、実際の問題に適用しやすいという特性があります。
遺伝的アルゴリズムの3つのデメリット
遺伝的アルゴリズムにはメリットだけではなく、デメリットも存在するため注意が必要です。
ここからは下記の3つのデメリットについてご紹介します。
- 計算時間がかかる
- 最適解を保証できない
- パラメータの設定が難しい
それでは、一つずつ見ていきましょう。
計算時間がかかる
遺伝的アルゴリズムは、多くの個体を評価し、選択・交叉・突然変異を繰り返すことで解の探索を行います。
特に問題のサイズや解の空間が大きい場合、十分な探索を行うために多くの計算時間が必要になります。
最適解の保証ができない
遺伝的アルゴリズムは確率的な最適化手法であり、実行ごとに異なる解が得られる可能性があります。
また、局所最適解に収束する場合や十分な解に収束しない場合もあります。問題によっては、最適解が見つからないこともあります。
パラメータの設定が難しい
遺伝的アルゴリズムには選択、交叉率、突然変異率などのパラメータがあります。
これらのパラメータの設定は問題に依存し、最適化の効果に大きく影響します。
適切なパラメータ設定を行うためには、経験や試行錯誤が必要であり、問題ごとに最適なパラメータを見つけることが難しい場合もあります。
遺伝的アルゴリズムの3つの活用事例
遺伝的アルゴリズムのメリットやデメリットについて紹介をしてきましたが、実際にはどのような分野で活用されているのでしょうか。
下記の３つの活用事例についてご紹介します。
- 新幹線の先頭車両の形状
- 金融取引
- 配送ルートの最適化
それでは、一つずつ見ていきましょう。
新幹線の先頭車両の形状
2007年に登場した東海道新幹線のN700系の先頭車両の形状は、遺伝的アルゴリズムによって膨大なデザインの中から絞り込んで決められています。
N700系の先頭部分は「エアロ・ダルウィング」と呼ばれ、特徴的な曲線によって騒音の抑制を実現しています。
「エアロ・ダブルウィング」は、5000にも及ぶシミュレーションを繰り返し作られました。
性能面での評価はもちろん、デザイン的にも高い評価を集めています。
金融取引
金融取引の活用事例としては、株式の自動売買の際に遺伝的アルゴリズムを活用するケースが挙げられます。
金融取引においては、終了条件が膨大にあるため、遺伝的アルゴリズムを活用し細かく条件を定めてコントロールすることで成果が出やすく効果的であると言われています。
配送ルートの最適化
物流業界では複数の配送先を効率的に回る最短ルートを探索することで輸送コストの削減と配送時間の短縮ができます。
最短ルートの最適解を導き出す際の手段として遺伝子アルゴリズムが活用され、配送ルート最適化を実施しています。
遺伝的アルゴリズムをPythonで実装
ここからはPythonで実際に遺伝的アルゴリズムを実装する際のステップについてご紹介します。
- ライブラリのインストール
- ランダムに個体（遺伝子）を生成
- 適応度の算出
- 次世代の生成（選択・交叉・突然変異）
- 解の決定
- 遺伝的アルゴリズムの実行
上記ステップを１から順番に詳しく見ていきましょう。
１．ライブラリのインストール
まず、必要なライブラリをインストールします。
今回は、例としてDEAPをインストールします。
２．ランダムに個体（遺伝子）を生成
DEAPを使用して遺伝的アルゴリズムを実装する場合、下図のコードを参考に遺伝子を表す個体をランダムに生成しましょう。
まず初めに、「適応度クラス」、「個体クラス」を定義し、初期遺伝子及び初期個体の生成を行います。
３．適応度の算出
個体の適応度を算出する関数を定義します。
下図のコードは要素の合計を適応度とする目的関数です。
４．次世代の生成（選択・交叉・突然変異）
遺伝的アルゴリズムの進化操作を定義します。
下図では初めに「交叉方法」、「突然変異方法」、「選択方法」を指定し、その後にアルゴリズムの進化についての処理が記述されています。
５．解の決定
繰り返し上記の処理を行うことで、最良の個体（解）を導き出すことができます。
６．遺伝的アルゴリズムの実行
上記のステップでは、evolve関数を呼び出して遺伝的アルゴリズムを実行します。
populationは初期個体群、ngenは世代数、cxpbは交叉確率、mutpbは突然変異確率となります。
上記ステップを繰り返すことで、個体群の全体の適応度が向上し、最適解に近づいていきます。
まとめ：遺伝的アルゴリズムの効率的な学習方法を学ぼう
本記事では、遺伝的アルゴリズムの概要から、メリット、デメリット、Pythonでの実装方法までをご紹介しました。
遺伝的アルゴリズムでは、選択、交叉、突然変異を繰り返し行うことで、最適解を導き出すことができます。
また、遺伝的アルゴリズムは歴史のある手法ですが、さまざまな問題や分野に応用できる手法であることがおわかりいただけたかと思います。
Jiteraでは、要件定義を書くだけでAIがアプリ・システムを開発できるプラットフォームがあります。
遺伝的アルゴリズムの手法を利用したAIの活用を検討されている方は、AIの分野を得意としているJiteraへ是非ご相談ください。
