メモ/安藤 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• メモ/安藤 へ行く。
• メモ/安藤 の差分を削除

#author("2021-04-02T07:46:53+00:00","","")
#author("2022-01-25T01:38:31+00:00","","")
-[[DELLPC>DELLPC/安藤]]


-Virtual BoxホストPC⇔ゲストPCコピペ方法~
https://onoredekaiketsu.com/copy-and-paste-with-virtualbox/

-(Linux)pythonのインストール~
https://shimi-dai.com/install-python3-on-linux/

-Mevenのインストール(linux)~
https://weblabo.oscasierra.net/install-maven-35-centos7/

-gitのインストール(linux)~
https://qiita.com/ponsuke0531/items/fe6011a1d5a7d764551c



\section{遺伝的アルゴリズムによる多目的最適化}
遺伝的アルゴリズム（Genetic Algorithm: GA）とは，1975年に，ミシガン大学のJohn Hollandが提案した，近似解を探索するためのメタヒューリスティックアルゴリズムである\cite{GA}．メタヒューリスティクスアルゴリズムとは，特定の問題だけに限らず，どんな問題に対しても汎用的に対応できるように設計された，アルゴリズムの基本的な枠組みのことである。

GAは，解の候補であるデータを遺伝子で表した「個体」を複数体用意し，適応度関数によって計算された適応度の高い個体を優先して選択し，生命の進化過程である交叉，突然変異や淘汰などの操作を繰り返し行うことで最適な解の探索をする．

GAの基本的な流れを以下に示し，各ステップの説明をする．

\begin{enumerate}
\item 　ランダムで複数の個体を生成する
\item 　各個体それぞれの適応度を計算する
\item 　「選択」，「交叉」，「突然変異」の操作により次世代の個体を生成
\item 　世代交代を行う
\item 　最終世代で一番高い適応度を持つ個体が解となる
\vspace{1mm}
\end{enumerate}

最初に一世代目の個体をランダムに生成する．このとき，個体の各遺伝子のパラメータはランダムに設定がされている．

次に，その世代のすべての個体の適応度を計算する．適応度とは，初期に生成した個体が環境にどれだけ適応できているかを評価する値である．一般にGAでは，適応度関数は最大化，または最小化の形で定義されることが多い．

\begin{description}
\item[選択]\mbox{}\\
選択とは，新しい世代を生み出す際の遺伝子操作の一つであり，適応度によって次の世代の母集団を作成する．適応度の高い個体ほど多くの子どもを生むように選択を行う．選択の方法として，ルーレット選択，トーナメント選択，ランキング選択，エリート選択があるが，どの方法も，生き残る個体を絞り込み，母集団を最適解に収束させる役割を持っている．
\begin{description}
\item[ルーレット選択]\mbox{}\\
ルーレット選択とは，個体群におけるそれぞれの個体の適応度と，それらの統計を求め，適応度の合計に対する，各個体の適応度の割合を選択確率として個体を選択するという考え方である．従って，適応度の高い個体が次世代の個体として選ばれる可能性が高くなる一方，適応度の低い個体であっても次世代の個体に選ばれる可能性もゼロではないので，個体群の多様性を保つことができ，局所的な最適解に陥ってしまうことを防止できるというメリットがある．

\item[トーナメント選択]\mbox{}\\
トーナメント選択とは，あらかじめトーナメントサイズを決めておき，個体群からランダムで個体をサイズ分取り出し，取り出した個体の中で一番高い適応度を持つ個体を選択する方法である．トーナメントサイズの設定により，どれくらい淘汰するかといった具合を調整できる．

\item[エリート保存選択]\mbox{}\\
エリート保存選択とは，個体群の中で最も適応度の高い個体を，そのまま無条件で次世代に残すという選択と，それに類似した選択方法のことである．確率のみに従って個体を選択し，交叉や突然変異のステップに進むと，非常に適応度の高い個体が現れても消滅してしまうことがあるということは，局所的な最適解に陥るのを防ぐことにも繋がるが，良い解を少ない回数で得たい場合には障害になってしまう．そのため，エリート保存選択が提案されてきた．


\end{description}

\item[交叉]\mbox{}\\
交叉とは，生物が交配によって子孫を残すことをモデル化したものである． 基本的には選択によって選ばれた個体に対して、ある交叉位置における双方の染色体の一部ずつを組み換え，新しい個体の染色体を作成する遺伝子操作である．

\item[突然変異]\mbox{}\\
突然変異とは，ある一定の確率で，個体の染色体上の遺伝子を別の遺伝子に置き換える操作である．交叉によって生成される個体は，その親遺伝子に依存した限られた範囲の個体であるため，突然変異は個体群の多様性を維持する役割を担っているといえる．

\end{description}

突然変異の操作の後，適応度関数によって各個体の適応度を求め，上記の選択，交叉，突然変異の過程を繰り返すことで，世代を交代しながら最適な解を探索する．世代交代の過程で最適解が得られたと判断された場合や，世代交代数を設定しておき，最終世代数に達したときに生き残っていた個体集団の中で，もっとも高い適応度の個体を最適解と見なす場合にＧＡは終了する．

次に，本研究で扱う手法である，非優越ソートGA(Non-dominated Sorting Genetic Algorithm: NSGA-I\hspace{-.1em}I）について説明する．
NSGA-I\hspace{-.1em}Iとは，Debらによって2002年に提案された\cite{NSGA2}，GAを多目的最適化問題に拡張したものである．

NSGAは，Goldberg により提案された非優越ランキングソート\cite{非優越ソート}とシェアリングを組み合わせた個体の評価方法を用いており，パレート的アプローチに基づく手法の一つである．NSGA-IIでは，NSGAと比較して次の 3 点において改良，変更が行われている．

\begin{quote}
 \begin{itemize}
  \item エリート主義の導入
  \item 混雑距離の導入
  \item 高速ソートの実現
 \end{itemize}
\end{quote}

上記におけるエリート主義とは，探索中に得られる多目的におけるパレート個体の保存を
意味している．NSGA-II では，パレート保存する個体数は常に一定であり，保存したパレート個体を選択に反映させる方法を用いている．また，混雑距離とは従来までのシェアリングに代わる個体のばらつき度合いを評価する方法であり，解の両隣にある2つの解の平均距離である．

ここで，
$i$番目の解$x^{(i)}$の混雑距離は,
$x^{(i)}$に関数値が最も近接する$i-1$番目と$i+1$番目の解$x^{(i-1)}$と$x^{(:+1)}$
，$\overline{f}_{j}(\cdot)$は，$i$番目の目的関数$f_{j}(\cdot)$をその値域幅で正規化した目的関数とすると，次のように定義される．

\begin{eqnarray}
CD(x^{(i)}) = \frac{1}{k} \sum\limits_{j=1}^{k} | \tilde{f_{j}}(x^{i+1}) - \tilde{f_{j}}(x^{i-1}) |
\end{eqnarray}

隣接する個体間の距離を適合度とする為，シェアリングと異なりパラメータフリーという特徴を持っている．また，NSGA-IIは NSGA同様，Goldberg の非優越ソートを用いている．

NSGA-IIにおける一連のアルゴリズムについて各Stepごとに以下示す．

\begin{enumerate}
\item 　初期化: $N$ 個の個体をランダムに生成する (パ
レート保存個体群 $P1$ 生成)．世代 $t = 1$ とする．
\item 　遺伝的操作: 個体群 $P_{t}$ を用いて選択，交叉，
突然変異といった遺伝的操作を行い次世代子個体群$Q_{t}+1$を作成する．
\item 　個体群の統合: 母集団 $P_{t}$ と $Q_{t}$ を組み合わせ
る．$R_{t} = P_{t} \cup Q_{t}+1$
\item 　パレート個体保存選択: 母集団 Rt に対して
高速非優越ソートおよび混雑度の計算を行い，
各個体の適合度割り当てを行う．適合度の上
位から順に $N$ 個体を選択しパレート
保存個体群 $P_{t}=1$ を作成する．
\item 　終了判定: 世代を $t = t + 1$ とし，終了判定
を行う．終了条件を満たしている場合は，パ
レート保存個体群 $P_{t}=1$ を最終解 $A$ として出
力．終了条件を満たしていなければ Step2 へ
戻る．
\vspace{1mm}
\end{enumerate}

ここで重要となるのが，Step2 におけるバイナリトーナメント選択の際の判断基準の，適合度割り当てについてである．NSGA-II ではこの選択において，ニッチ比較操作に基づく選択を行っており，より多様性を重視した選択を行っている．