BETA

アントコロニー最適化のPython現最良リポジトリを紹介する

投稿日:2019-12-11
最終更新:2019-12-10

本記事は群知能と最適化 Advent Calendar 2019の11日目です。

この記事は,自分の理解が目的のため,質が悪いです.
申し訳ありません.

本記事を簡潔に

  • acopyっていうリポジトリが便利だよ!
  • ドキュメントもきちんと書かれてるよ!
  • 設計も綺麗だよ!
  • Pythonの面白い文法がいっぱいだよ!
  • プルリクしているけど返事がないので悲しいよ!

アントコロニー最適化とは?

アントコロニー最適化とは、蟻の群れの生態から着想を得た
離散的な組み合わせ問題を解くメタヒューリスティクスなアルゴリズムです。

アントコロニー最適化(ACO)を救いたいで解説しているため、ご覧下さい。

アントコロニー最適化の設計の難しさ

アントコロニー最適化では、多くの概念が出てきます。
例えば

  • グラフ
  • アリ
  • アリが構築したパス
  • Solver

などです。

これらを実装するとき、シングルファイルに実装するのが一番ラクですが
やはり、コードのメンテナンスという面ではシングルファイルは駄目です。

また、どのクラスにどの機能を持たせるか?はなかなか分けづらくなっています。
アリ自体が、構築したパスを持つのか、フェロモンはグラフに持たせるのか
Solverはパスもアリも持つのか?

など多くの考えなければいけない設計ポイントが多いです。

そこで、acopyというリポジトリを参考にして、アントコロニー最適化の良い設計について考えてみようと思います。

acopy

acopyは、rhgrant10というアメリカの方が作ったリポジトリです。

ドキュメントも存在し、Sphinxドキュメントで作成されています。

設計がキレイなため、ソースコードを全部まとめて写経して勉強させていただきました。
自分が写経させていただいてできたリポジトリはreacoです。

acopyの設計

acopyの設計は以下のようなクラスに分割されています。

  • Solver
  • Solution
  • Colony
  • Ant
  • SolverPlugin
  • State
  • utils(モジュール)
  • グラフ(NetworkX)

Solver

Solverクラスは、AntColonyOptimization全体を管理するクラスです。

NetworkXで作成されたグラフと、Colonyインスタンスを受け取ってACOを実行します。
規定回数だけ実際に解を構築し、その解を評価してStateインスタンスに格納します。

プラグインの管理もするのもSolverクラスです。

Solution

Solutionクラスは、アリが生成する解自体を表すクラスです。
アリが通ったパスや頂点を保存し、パス同士を比較できるようになっています。これは、__eq____lt__などが定義されているためです。

Colony

Colonyクラスは、蟻を$N$体生成するだけのクラスです。
蟻が移動するフェロモンとヒューリスティックの基準である${\alpha}, {\beta}$のみ定義します。

Ant

Antクラスは、実際にNetworkXで作成されたグラフ上を移動して解を構築します。
このとき、解はSolutionクラスのインスタンスを生成してそこに格納し、SolutionインスタンスをSolverに返します。

  • パス移動

によるパスの構築のみを行い、蒸発などはSolverに任せます。

SolverPlugin

Solverクラスが持つことができる、SolverPluginクラスです。
このクラスを継承することで、SolverインスタンスがSolverPluginに「全情報を格納しているStateインスタンス」を渡します。
よって、SolverPlugin側からプラグインとして、Solverの拡張を行うことができます。

https://qiita.com/ganariya/items/3b8861788ec30238a8a9

上記の記事でプラグインの仕組みを説明しています。

Stateクラス

Solverインスタンス内で生成されるStateクラスです。

  • NetworkXのグラフ
  • 構築されたパス情報
  • パラメータ

などすべての情報をStateクラスに格納します(参照させます)。

これによって、このStateクラスを前述のSolverPluginインスタンスに渡し、ユーザが作成したクラスからSolverの内部情報にアクセスできるようになります。

このStateを利用して、分かりやすい図などを作成できます。

utilsモジュール

utilsモジュールでは、色々と使う共通メソッドを準備しています。

ACOに直接関係ない関数や処理はutilsとして作成すると良さそうです。

グラフ(NetworkX)

ACOはグラフに帰結した最適化問題のため、グラフを使用する必要があり、acopyではNetworkXを利用しています。

自前のグラフクラスを作るよりも多くのメソッドや省略記法などの恩恵を受けることができます。

TSP問題のベンチマークに使用される多くのベンチマークグラフが、他のライブラリでNetworkXに変換できるため、嬉しい設計になっています。

acopyから学んだプラクティス

acopyをすべて写経して、多く学んだことがありました。

グラフはNetworkXを使用する

これまでは、自分でグラフクラスを作っていましたが
PythonでACOをやるならNetworkXを使用すると良さそうです。

多くの属性をエッジに簡単に追加できるためNetworkXを使うと設計がよりシンプルになります。

Stateにすべての情報を集めて、プラグインで参照させる

Solverインスタンスに、Stateインスタンスをメンバとして持たせて
すべての情報をStateインスタンスにもたせておきます。

これによって、プラグインですべての情報を参照し、他の処理を行うことができます。

Solverの機能を制限する

Solverにやらせることを少なくすると設計が綺麗になります。
具体的には

  • 全体としてのパラメータのみ定義する
  • グラフのみ受け取り、Stateインスタンスにすべての情報をもたせる
  • 規定回数optimizeで、蟻インスタンスに解を作らせ、その解を用いてグラフ情報をアップデートする
  • プラグインを実行する

のみになっています。

アリと解を分離する

acopyではアリと解を分離しています。

Solutionクラスでは

  • 情報の格納
  • Solutionインスタンス同士の比較
  • エッジ、ノードの追加の便利メソッド

のみの定義を行っています。

そして、Antクラスでは

  • 解インスタンスを作って、Solverに返す
  • そのために、受け取ったグラフ上で、実際にパスを構築する

をしています。

SolutionとAntを分離させることで、解自体をSolverに渡しやすくなり、Antのみがグラフ情報にアクセスするようになります。

PSO, ABCアルゴリズムでも分離すると良いかもしれません。

ここで、現Antクラスはインスタンスにしなくても良いような設計になっていますが、応用研究では感度の悪いアリなどアリ自体に工夫をすることが多いため、インスタンスにしたほうが良いと考えます。

依存度を可能な限り小さくする

acopyでは、可能な限り親と子の参照しかありません。
依存度が小さいため、見やすい設計になっています。

便利文法が多い

acopyはかなり珍しい文法・イディオムが使用されています。(自分がPython初心者なのでそう感じているだけかもしれませんが><)

acopyから学んだ文法は【Python中級者への道】記事リンクまとめにまとめています。

まとめ

PythonでACOをする場合は是非acopyを参考にしてみてください。
きれいな文法・設計を見ることができます。
僕は非常に勉強になりました。

ぜひみなさんも自分の好きなリポジトリを探して、写経をしたりプルリクしてみてください。
残念ながらプルリクしていますが反応がありません。現場からは以上です。

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

競プロなどをします。

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう