\documentclass[twocolumn]{jarticle} \usepackage{jsaiac} \usepackage[dvips]{graphicx} \title{確率モデル遺伝的アルゴリズムEHBSAにおける戦略、\\パラメータの調査 \\ {\small　Study on the Strategies and Parameters for the Probabilistic Model-Building Genetic Algorithm EHBSA}} %%英文は以下を使用 %\title{Style file for manuscripts of JSAI 20XX} \jaddress{酒井大輔、京都大学大学院情報学研究科知能情報学専攻、sakai@kuicr.kyoto-u.ac.jp} \author{% \jname{酒井大輔\first} \ename{Daisuke Sakai} \and \jname{上田和紀\second} \ename{Kazunori Ueda} } \affiliate{ \jname{\first{}京都大学大学院情報学研究科} \ename{Graduate School of Informatics, Kyoto University} \and \jname{\second{}早稲田大学理工学部} \ename{Science and Engineering, Waseda University} } %% \Vol{19} %% <-- 19th（変更しないでください） \session{2F1-02}%% <-- 講演ID（必須） \begin{abstract} We studied strategies and parameters for the TSP solutions of EHBSA (edge histogram based sampling algorithm), which is one of the probabilistic-model genetic algorithms, mainly from the perspective of accuracy. % 30 word As the result of systematic experiments, we found some facts. For example, in the stage of population selection and parallelization, the elite strategy performed best. %26 For the implementation language, we chose a strongly-typed functional language OCaml, because of richness of libraries and efficiency of programming, and implemented EHBSAWO (EHBSA without template) and ENBSAWT (EHBSA with template) for a single processor and multiple processors,respectively. % 41 word For multiprocessors, we used ocamlmpi, which is an interface module to the MPI message-passing library. By the parallelization, the accuracy (reciprocal of traversal distance) improved by 1.3 to 1.6 times than that of the single-processor version. %49 word \end{abstract} %\setcounter{page}{1} \def\Style{``jsaiac.sty''} \def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em% T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}} \def\JBibTeX{\leavevmode\lower .6ex\hbox{J}\kern-0.15em\BibTeX} \def\LaTeXe{\LaTeX\kern.15em2$_{\textstyle\varepsilon}$} \begin{document} \maketitle \section{背景と動機}\label{section:pmbga} 従来の遺伝的アルゴリズム(GA)の欠点を補い、その上で生物のアルゴリズムの高い探索能力を コンピュータ上に実現する新たな手法として確率モデルGAと呼ばれるものが注目されている。 確率モデルGAとは、従来のGAのように交叉オペレータにより子個体を生成せず、 集団の個体分布を確率モデルで近似し、そのモデルに基づいて子個体を生成する 手法である。 確率モデルGAとしては、PBIL, compactGA, ECGA (extended compact GA) (参考文献\cite{ECGA}\cite{cGA})などがあるが、 その適用はほとんどtoy problemに限られ、従来のGAの代表的な応用であるスケジューリング問題 や巡回セールスマン問題 (TSP）についての応用はほとんど見られない。 そのような中、確率モデルGAに基づいたTSPについての数少ない応用としてはEHBSA (参考文献\cite{EHBSA1}) があり、従来のGAを超える高いポテンシャルが期待できる。しかし、このアルゴリズムにおける 最適な戦略、パラメータはまだ充分には研究されていない。 確率モデルGAは従来のGAと同じように、 集団数などの多くのパラメータや様々な戦略が存在し、 これらの組み合わせによってその性能が大きく変化することを考えると、 EHBSAを利用したTSP解法における効果的な戦略、パラメータを調査することの 意義は十分にあると考え、本研究を行なった。 \section{EHBSA}\label{section:ehbsa} EHBSAは確率モデル遺伝的アルゴリズムの一種であり、巡回セールスマン問題などの順序問題 に対する解を探索するのに用いる。 確率モデル遺伝的アルゴリズムは集団の個体分布を確率モデルで 近似するが、EHBSAではこれをedge histogram matrix (EHM)という行列 で行なう。つまり、世代$t$の集団があったとき、これから$EHM^t$をつくりこれを用いてsampling することで、世代$t+1$の集団をつくる。この繰り返しにより、より良い解を探索する。 EHBSAのアルゴリズムの簡単な流れは次のようになる。 \begin{enumerate} \item 個体をランダムに生成する \item 選択オペレータを用い、有望集団をつくる \item 有望集団からEHMを作成する \item EHMを基に子個体をsamplingする \item 終了条件が満たされるまで、ステップ２から４をくり返す。 \end{enumerate} \section{EHBSAWO, EHBSAWT} EHBSAにはEHBSAWO(EHBSA without template)とEHBSAWT (EHBSA with template)という ２種類の手法がある。EHBSAWOは第\ref{section:ehbsa}節で述べたほぼそのままのアルゴリズム だが、EHBSAWTは集団の中からtemplateとしてひとつの要素を取りだしそれらをいくつかの cutによって分け、その中の１つのsegmentだけをsamplingし他のsegmentはそのままコピーされる。 これによって優秀なブロックが次世代にも遺伝すること、世代交代にかかる 計算量が短縮されるなどの効果が望める。 \begin{figure} \centerline{ \includegraphics[width=7cm,height=5cm]{soturon-ohp1.eps} } \caption{全体の流れ} \label{flow} \end{figure} \section{実装したシステムと戦略} \subsection{実装したシステム} EHBSAWO, EHBSAWTのアルゴリズムを用い、TSPの解法を探索する プログラムをそれぞれ逐次版と並列版の２種類ずつ作成した。 その他に上記のアルゴリズムの計測と分析を効率良く行なうために、パラメータファイルを書き、それの直積を計算し それらすべてを実行するユーティリティと、同様のパラメータファイルを受け取り 結果を自動的にグラフにするユーティリティを実装した。 具体的には次のようなパラメータファイルを手作業で用意する。 \begin{verbatim} pop_num;20,30,40 city_num;50 max_generation;30,40 population_select;no_population_select make_ehm_strategy;make_ehm_weight:0.04 use_twoopt;use_twoopt,non_use_twoopt \end{verbatim} このファイル名をmakeparameterとする。これを使い、例えばEHBSAWOで計測したいときには 次のように打ち込む。 \begin{verbatim} ocaml str.cma unix.cma execute_ehbsawo.ml makeparameter \end{verbatim} このようにすると各行の要素の直積集合の数だけ、自動的に実行し結果をファイルに格納する。 上のパラメータファイルでは$3 \times 1 \times 2 \times 1 \times 1 \times 2 = 12$回計測する事になる。 また、計測が終わっているとしてその結果が見たいときは次のように打つと実験結果を 自動的にグラフ化する。 \begin{verbatim} ocaml str.cma unix.cma read_ehbsawo.ml graph makeparameter \end{verbatim} 本研究では初期集団の選択、templateの選択、sampling nodeの選択、EHMの戦略、 局所的改善手法の有無、送受信の戦略に分けて戦略を実装した (この内、template, sampling nodeの選択はEHBSAWTのみであり、送受信の戦略は並列版のみの実装である）。 図\ref{flow}にその全体の流れの図がある。 丸い枠に囲まれているのが各フェーズを表し、右上に 書いてあるものがパラメータ、左下に書いてあるのが実装した戦略の数になる。 \begin{enumerate} \item 初期集団を選択し有望集団を作る。 \item EHBSAWTの場合はtemplate, sampling nodeを選択する。 \item 有望集団からEHMを作成し、samplingする。 \item もし戦略に組み込まれていれば、2opt法で局所的改善を行う。 \item 並列版の場合は各CPUから他のCPUへと集団の要素を送信する。 \end{enumerate} \subsection{実装した戦略} \renewcommand{\thesubsubsection}{\thesubsection .\arabic{subsubsection}} \subsubsection 初期集団の選択のフェーズに置いては以下の４つの戦略を実装した。 \vspace{-0.2cm} \begin{itemize} \item no\_population\_select : 全く選択を行わない \vspace{-0.2cm} \item population\_select\_half : 優れた上位半分を使う (つまり同じ内容のものが２つず作られる) \vspace{-0.2cm} \item population\_select\_roulette : 適応度の割合に応じて子孫を残す \vspace{-0.2cm} \item population\_select\_tournament : ランダムに２つ選び、そのうちの優れた方が受け継がれ、それを集団の数だけ繰り返す \vspace{-0.2cm} \end{itemize} \subsubsection templateを選択するフェーズでは以下の３つの戦略を実装した。 \vspace{-0.2cm} \begin{itemize} \item choose\_template\_randomly : ランダムにtemplateを選ぶ \vspace{-0.2cm} \item choose\_template\_roulette : 適応度に応じて選択する \vspace{-0.2cm} \item choose\_template\_elite : 最も良いものをtemplateとして選択する \vspace{-0.2cm} \end{itemize} \subsubsection sampling nodeを選択するフェーズでは以下の２つの戦略を実装した。 \vspace{-0.2cm} \begin{itemize} \item choose\_node\_randomly : ランダムにsampling nodeを選ぶ \vspace{-0.2cm} \item choose\_node\_roulette : 適応度に応じて選択する \vspace{-0.2cm} \end{itemize} \subsubsection EHMを作成するフェーズでは以下の２つの戦略を実装した。実験した中ではこれが最も効果の大きいファクター だった。 \vspace{-0.2cm} \begin{itemize} \item make\_ehm\_delta : EHBSAの論文に基づいたデルタ関数を使う \vspace{-0.2cm} \item make\_ehm\_weight : 独自の重みづけを行なうEHMを作成する \vspace{-0.2cm} \end{itemize} \subsubsection 局所的改善手法として2opt法という従来のGAに使われているヒューリスティックスを使うか使わないかの２種類の 戦略を実装した。 \vspace{-0.2cm} \begin{itemize} \item use\_twoopt : 2opt法を使う \vspace{-0.2cm} \item non\_use\_twoopt : 2opt法を使わない \vspace{-0.2cm} \end{itemize} \subsubsection 送受信の戦略としては送信、受信に以下の４種類ずつ計８個を実装した。 \vspace{-0.2cm} \begin{itemize} \item send\_randomly, receive\_randomly : ランダムに送受信する \vspace{-0.2cm} \item send\_roulette, receive\_roulette : 適応度に応じて送受信するのを選ぶ \vspace{-0.2cm} \item send\_elite : 最も適応度の高いもの決められた数だけ送信する \vspace{-0.2cm} \item recive\_elite : 適応度の最も低いものを受信したものと取り替える \vspace{-0.2cm} \item send\_tournament　: ランダムに２つ選びそのうち適応度の高いものを送信する。 \vspace{-0.2cm} \item receive\_torunament : ランダムに一つ選び、それと受信したものを比較し、優れているときのみ交換する。 \vspace{-0.2cm} \end{itemize} \subsection{ocamlmpi} 本節ではocamlmpiについて簡単に紹介する(参考文献\cite{ocaml1}\cite{ocaml2}\cite{ocaml3})。 ocamlmpiはOCamlのMPIインターフェースであり、 OCamlのプログラム上でMPIを利用した並列プログラミングを行える。ocamlmpiを用いることにより 従来ほとんどC, C++, Fortranなどに限られていた並列プログラムを、OCamlを用いて行えるようになり スクリプト言語の手軽さで並列化された実行コードを得ることが出来る。 ocamlmpiの最も大きな特徴はsendとreceiveで任意の型が送受信 出来るという事だ。 例えば、floatとintをプロセス０から１まで送りたいとき、Ｃなどでは面倒なプログラムが 必要になるが、ocamlmpiでは \begin{verbatim} if myrank=0 then ( let a = 1 and b = 2.0 in send (a,b) 1 0 comm_world ) else ( let a,b = (receive 0 0 comm_world) in Printf.printf "int:%d, float:%f\n" a b ) \end{verbatim} などと簡単に出来る。また次のように、受信するときに型を指定してプログラムを読みやすくする事も出来る。 \begin{verbatim} let x : int * float = (receive 0 0 comm_world) in let a,b = x in \end{verbatim} \section{実験結果と考察} \begin{table*}[t] \caption{cut数と計測時間、および解の精度}\label{tab:cut1} \begin{center} \begin{tabular}{|c|c|c|} \hline & 集団数/最小距離/時間(s) & 集団数/最小距離/時間(s) \\ \hline EHBSAWO & 150/8823.9/16.6 & 150/8823.9/16.6 \\ \hline EHBSAWT/1 & 150/9792.9/16.7 & 150/9792.9/16.7 \\ \hline EHBSAWT/2 & 150 /11824.8/7.63 & 300/12462.9/15.4 \\ \hline EHBSAWT/3 & 150/13729.6/5.35 & 450/14720.0/16.0 \\ \hline EHBSAWT/4 & 150/14436.0/4.43 & 600/17208.3 /17.9 \\ \hline EHBSAWT/5 & 150/15950.1 /4.17 & 750/19280.9/21.3 \\ \hline \end{tabular} \end{center} \end{table*} \begin{table*}[t] \caption{並列版EHBSAWOの実験結果１}\label{tab:mpiehbsawo2} \begin{center} \begin{tabular}{|c|c|c|c|c|c|} \hline 都市数 & ＣＰＵ数 & 送受信数 & 並列版の解 & 逐次版の解 & 逐次版/並列版 \\ \hline 200 & 7 & 5 & 4864.1 & 7657.1 & 1.57 \\ \hline 400 & 8 & 10 & 8273.5 & 13525.5 & 1.63 \\ \hline 600 & 6 & 10 & 15428.0 & 19317.1 & 1.25 \\ \hline 800 & 8 & 10 & 17800.1 & 24701.0 & 1.38 \\ \hline 1000 & 6 & 20 & 23639.5 & 30812.7 & 1.30 \\ \hline \end{tabular} \end{center} \end{table*} \begin{figure} \begin{center} \includegraphics[width=7cm,height=5cm]{ehbsawo_graph1.eps} \end{center} \caption{EHBSAWOにおける初期集団の選択}\label{fig:pop_select_ehbsawo} \end{figure} 実験の結果、実行速度以外はEHBSAWOのほうがEHBSAWTよりも優れていた。これを示しているのが表\ref{tab:cut1} で、これを見ると解の精度という点ではEHBSAWOがEHBSAWTを上回っている事、cut数を増やすと実行時間は 短くなるがその分解の精度が悪化すること。また与えられた都市数に対して集団数が大きすぎると解の精度 がかえって悪化する事などが見て取れる。 このうち、cut数の増加に伴い解の精度が悪化する問題についてはtemplateをランダムに選ぶせいで、質の良くないものを templateにしてしまっている可能性が高いことに原因が有ると思われた。そこで、最も適応度の高いもの をtemplateにして実行すれば、解の精度の向上が望めるか、と考え実行したが、ほとんど結果は 変わらなかった。結局これはcutすることで、EHMの重みづけの効果が少なくなってしまうことに大きな原因が あると考えられる。よってEHBSAWTの改善にはcut数を可変にするなど他の手法が必要になる。 今回の研究では、解の精度に焦点を絞っているので以下ではEHBSAWOのみを取り上げる。 有望集団を作成する手法としては、エリート戦略、トーナメント戦略が適当であることが分かった (図\ref{fig:pop_select_ehbsawo})。また当初の予想を裏切り、これは他の戦略にほとんど依存しなかった。 つまり他の戦略、パラメータがどのようなものであれ、初期集団の選択においてはエリート戦略、 トーナメント戦略が良い性能を示した。 EHMの作成のフェーズにおいてはデルタ関数を用いたものよりも、都市間の距離を考えた 重み付けをおこないEHMを作成する戦略の方が良い性能を示した(図\ref{ehm})。このEHMの作成における 戦略が実装した戦略の中では、解の精度に対して最も大きな影響を持っていた。 \begin{figure} \centerline{ \includegraphics[width=7cm,height=5cm]{soturon-ohp2.eps} } \caption{EHMによる比較} \label{ehm} \end{figure} \begin{figure} \centerline{ \includegraphics[width=7cm,height=5cm]{mpiehbsawo_graph1.eps} } \caption{並列版EHBSAWOにおける送受信戦略} \label{mpiehbsawo-strategy} \end{figure} MPIを用いた並列化では送受信における戦略には各プロセスが自分の集団の中で 最も適応度の高いものを他のプロセスに送り、受け取る側はそれを自分の集団の中で 最も適応度の低い要素と入れ替えるというエリート戦略が最も有効だった (図\ref{mpiehbsawo-strategy})。 また、送受信する数は都市数などに比べ比較的少量の場合のほうが解の精度は 良く、逐次版に比べて1.3倍から1.6倍程度の向上が見られた(表\ref{tab:mpiehbsawo2})。 しかし、本研究で実装した並列EHBSAのアルゴリズムは安定性に今一つ難が見られた (表\ref{tab:mpiehbsawo3})。優れた安定性を持つ並列アルゴリズムはこれからの 課題である。 なお、計測はSGI Altix 350 (Itanium2 $\times$ 8 , memory:40GB)上で行ない、 処理系にOCaml-3.08、拡張モジュールとしてocamlmpi-1.01を 用い、コンパイルはocamloptコマンドを使い行なった。また、計測は１回のみである。 \begin{table}[htbp] \caption{並列版EHBSAWOの実験結果２}\label{tab:mpiehbsawo3} \begin{center} \begin{tabular}{|c|c|c|c|} \hline 都市数 & プロセス数 & 送受信数 & 並列版の解 \\ \hline 200 & 6 & 5 & 8284.6 \\ \hline 200 & 7 & 5 & 4864.1 \\ \hline 200 & 8 & 5 & 5562.4 \\ \hline 400 & 6 & 10 & 14291.7 \\ \hline 400 & 7 & 10 & 10221.9 \\ \hline 400 & 8 & 10 & 8273.5 \\ \hline 600 & 6 & 10 & 15428.0 \\ \hline 600 & 7 & 10 & 15757.1 \\ \hline 600 & 8 & 10 & 18500.4 \\ \hline 800 & 6 & 10 & 18160.2 \\ \hline 800 & 7 & 10 & 18956.0 \\ \hline 800 & 8 & 10 & 17800.1 \\ \hline 1000 & 6 & 20 & 23639.5 \\ \hline 1000 & 7 & 20 & 30047.3 \\ \hline 1000 & 8 & 20 & 28848.7 \\ \hline \end{tabular} \end{center} \end{table} \section{今後の課題} 今後の課題としてはアルゴリズムの改良がある。EHBSAは世代交代にかかる時間は通常のGAよりも短いが、 解の精度自体は通常のGAに劣る。これは戦略にエリート戦略を用いEHMを重みづけするというかなり 強引に探索領域をせばめる戦略のため、解が局所解に陥る可能性が高いせいである。 この点を改善するには探索空間を大きく取れるような戦略、パラメータを増やす必要がある。 また並列化したときに解の精度が大幅に向上することがあるのは確認できたが、これは 全く異なるかたちの集団の要素を取り入れることで探索空間が拡大することが理由として 考えられる。しかし、本研究で実装した並列EHBSAのアルゴリズムは最適なパラメータを 与えられた条件(都市数など）から導くのが難しく、精度の良い解を見つけるのに適切な 計算ノードの数にも規則性は見つけられなかった。この点の改善は今後の研究課題になる。 \begin{thebibliography}{9} \bibitem{ocaml1} Xavier Leroy : OCamlMPI: interface with the MPI message-passing interface \\ http://cristal.inria.fr/~xleroy/software.html\#ocamlmpi \bibitem{ocaml2} 酒井大輔 : ocaml備忘録 \\ http://www.ueda.info.waseda.ac.jp/ \\ \hspace{1cm} \~{}sakai/ocaml/ocamlmemo.html \bibitem{ocaml3} Xavier Leroy : The Objecttive Caml system release 3.08 Documentation and user's manual, 2004 \\ http://caml.inria.fr/pub/docs/ \\ \hspace{1cm} manual-ocaml/index.html %\bibitem{ocaml1} 酒井大輔 : ocaml備忘録 \\ % \hbox{\tt http://www.ueda.info.waseda.ac.jp/\~{}sakai/ocaml/ocamlmemo.html} \bibitem{EHBSA1} Shigeyoshi Tsutsui : Probabilistic Model-Building Genetic Algorithms in Permutation Representation Domain Using Edge Histogram, Proc. of the 7th Parallel Problem Solving from Nature - PPSN VII, pp.224-233, 2002. \bibitem{ECGA} Georges Harik : Linkage Learning via Probabilistic Modeling in the ECGA, Technical report, IIIiGAL Technical Report, No. 99010, 1999. \bibitem{cGA} Georges R. Harik, G.Lobo, David E. Goldberg : The Compact Genetic Algorithm, Proceeding of the 1998 IEEE Conference on Evolutionary Computation, pp. 523-528, 1998 \end{thebibliography} \end{document}