%---------------------------------------------------------------------- %修士論文用スタイルファイルの使用例 % 知的システムデザイン研究室 % 畠中一幸 % 2000/01/05 %---------------------------------------------------------------------- %---------------------------------------------------------------------- %プリアンブルの指定です. %11ptでjreportクラスを使用しています. %ですから,一番大きな見出しがchapterになります. %注意してください. %---------------------------------------------------------------------- \documentclass[a4paper,11pt]{jreport} \usepackage{masterthesis} \pagestyle{plain} \begin{document} %---------------------------------------------------------------------- %abstractです. %終了すると強制的に改ページを行います. %---------------------------------------------------------------------- \begin{abstract} In this paper \ldots \end{abstract} %---------------------------------------------------------------------- %目次です. %ここではギリシャ数字でページ番号を書きます. %目次が終わると改ページを行い,以降をアラビア数字で振り直します. %特に何かを追加する必要はありません. %---------------------------------------------------------------------- \pagenumbering{roman} \tableofcontents \newpage \pagenumbering{arabic} %---------------------------------------------------------------------- %ここより下が本文です. %例として,わたし(畠中)の卒論の出だしを載せておきます. %---------------------------------------------------------------------- \chapter{序論} \section{最適化問題} 一般的に最適化問題とは,ある制約条件下において,与えられた状態空間で定義された関数(目的関数)の最大値(または,最小値)を与える状態空間の要素を求めることを言う. 最適化理論に基づくさまざまな最適化手法は,システムの設計,計画,制御,評価ならびに各信号処理,意思決定論などの広範囲な問題を取り扱うのに必要な基本指針である.これらは問題解決の手段として有効であり,利用されている.最適化に関する研究は1940年代から始まる歴史を持ち,現在のオペレーションズリサーチ(OR)の中核をなしている.したがって,単純な組織・システムであれば,従来の線形的な最適化法はきわめて有効に働く.しかし問題の規模が広がり,多様性を有するようになると,従来の最適化法では計算が困難となる.組み合わせ問題などでは,変数の数が増えすぎると組み合わせ爆発が起こり,最適解を見つけるのは実質的に不可能になる. 現実にはそのような問題が多く存在しており,厳密な最適解を得るのではなく,計算可能な準最適解を求めるための方法が求められているのが現状である. \section{準最適化法} 準最適解を得るための方法は大きく分けて,ヒューリスティック法とランダム法の2種類に分かれる. \subsection{ヒューリスティック法} 適応する事象システムの機構や問題の性質を熟知している人,またはその人の知識を用いて,事象システム固有の性質を十分に知った人によって作成されたアルゴリズムのことを言う. この手法では実行可能な解が得られるが,その解の最適性を保証するものはない.しかしながら,対象とする問題の構造をうまく利用することが可能であれば,比較的良好な解が得られるとされている. \subsection{ランダム法} ヒューリスティック方途は対照的に,問題の性質をまったく考慮しない完全な確率的手法である.記述した最適化の事象システムに関して,定義域から無作為に解の候補を選択し,その中で目的関数が最大(最小)となるものを解とする方法である.この方法では論理的には探索回数を無限大に増やせば,最適解を選ることが可能である.しかし,問題空間の解の候補を全て調べ上げると言うのは,あまりにも非現実的である.本実験で使用する遺伝的アルゴリズムは両手法の中間に位置する方法である. \subsection{遺伝的アルゴリズム} 遺伝的アルゴリズム(以下,必要に応じてGAと略記する)は生物の進化を模倣した,確率的なアルゴリズムである.このアルゴリズムは以下のような特徴を持っている. \begin{enumerate} \item パラメータをコード化したものを直接使用する. \item 一点探索ではなく多点探索である. \item サンプリングによる探索で,ブラインドサーチである. \item 決定論的規則ではなく,確率的オペレータを用いる探索である. \end{enumerate} これらの特徴からGAは,従来の古典的手法に無い特徴を備えた最適化法として注目を集めた.そしてスケジューリング問題や,ニューラルネットワーク最適化問題など従来の方法では難解な問題に適用され,その有効性が立証された.今日ではバス仕業ダイヤ作成,鉄道車両運用表作成などに使用されている.しかしながらGAの研究が盛んになるにつれ,以下のような問題が指摘されるようになった. \begin{enumerate} \item コンピュータ資源の浪費. \item 早熟収束による,局所解への収束. \item パラメータ設定の複雑さ. \end{enumerate} これらの問題が解決されれば,GAの有効性は飛躍的に向上するものと思われる.本論文ではこれら遺伝的アルゴリズムの諸問題の解決法として,島モデルによる並列化を用いている. 以下,2章,3章でGAの概論及びその並列化法について述べ,4章,5章ででGAを適用したトラス構造物最適化問題とGAへの適用法を述べる.6章ではSGAと並列GAの比較,及び島モデル特有のパラメータ(移住率と移住間隔)についての実験結果を述べる. 2 遺伝的アルゴリズム概説及び予備実験 ここでは遺伝的アルゴリズムの構成要素及び,アルゴリズムについて述べる. %---------------------------------------------------------------------- %謝辞です %今のところ,次のように書いてください. %あとで謝辞用の環境を作るかもしれません. %---------------------------------------------------------------------- \newpage \chapter*{謝辞} ここに謝辞を書きます. %---------------------------------------------------------------------- %参考文献の記入欄です. %こちらもnewpageで強制的に改ページしています. %---------------------------------------------------------------------- \newpage \begin{thebibliography}{9} \bibitem{hata_Holland} J.H.Holland:"Adaptation In Natural and Artificial Systems",University of Michigan Press,1975. \bibitem{hata_Tanse} Reiko Tanse :"Distributed Genetic Algorithms ", Proc. $3^{rd}$ International Conference. Genetic Algorithms. Morgan Kaufmann. pp434〜439,1989. \bibitem{hata_Miki} 三木,畠中:"並列分散GAによる計算時間の短縮と解の高品質化",第3回最適化シンポジウム講演論文集,pp59,1998 \bibitem{hata_Hiroyasu} 廣安,金子,畠中,三木:"分散遺伝的アルゴリズムにおける遺伝子郡の特異な進化",第11回計算力学講演会講演論文集,1998. \bibitem{hata_Whitley} Whitley,D., Mathias,K., Rana, S.and Dzubera,J.:"Building Better Test Function",Proc 6th Int. Conf. on Genetic Algorithms,Morgarn Kaufmann,pp.239-246,1995 \end{thebibliography} %---------------------------------------------------------------------- %以下,図表のためのページです. %再びページ番号を振り直しています. %論文が完成すると,本文と図表の間に色紙を挟みます. %---------------------------------------------------------------------- \newpage \appendix \pagenumbering{arabic} %---------------------------------------------------------------------- %図の張り込み例です. %---------------------------------------------------------------------- \begin{figure} \begin{center} \includegraphics{figure.eps} \caption{図の張り込み例} \end{center} \label{ring} \end{figure} %---------------------------------------------------------------------- %数式の例です. %---------------------------------------------------------------------- \begin{eqnarray} P_G &=& W_d \times d^2 \hspace{2em} if(d>d^2) \\ & & 0 \hspace{1em} else \nonumber \\ P_L &=& \sum_{k=1}^{N} P_k \\ P_k &=& 1 \hspace{1em} if((\sigma_n > \sigma_0)or(L_k > L_k^*)) \\ & & 0 \hspace{1em} else \nonumber \end{eqnarray} %---------------------------------------------------------------------- %表の例です. %少し番号表示がおかしいので,すぐにでも修正します. %---------------------------------------------------------------------- \begin{table}[htbp] \begin{center} \tbcaption{Parameter Setting} \label{hata_table1} \begin{tabular}{c|c} \hline {Parameter} & {Value} \\ \hline \hline Sub Poputaion Size & 10,50,100,200 \\ \hline Migration Rate & 0.1, 0.3, 0.5 \\ \hline Migration Interval & 1,5,10,50,100, $\infty$ \\ \hline \end{tabular} \end{center} \end{table} \end{document}