Thesis or Dissertation 実行不可能解を活用する進化型制約付き多目的最適化

宮川, みなみ  ,  ミヤカワ, ミナミ  ,  Miyakawa, Minami

pp.1 - 123 , 2016-03-25 , The University of Electro-Communications
Description
本研究では,進化計算による制約付き多目的最適化において,従来法では単に排除される制約条件を満たさない実行不可能解を解探索に有効活用する方法について探求し,その有効性を計算機実験によって検証することを目的とする.この目的を達成するために,まず,本研究の基礎となる二段階の非支配ソートと指向性交配を用いるTNSDM (Two-stage Non-dominated Sorting and Directed Mating) アルゴリズムを提案する.二段階の非支配ソートでは,制約違反量に基づいて解集団をいくつかのグループに分類した後,各グループを目的関数値に基づいて再分類することによって解をランキングする.指向性交配では,実行可能解を第一の親とし,それより目的関数値が良い実行不可能解集合を選出する.その中から,二段階の非支配ソートで求めた解のランキングに従って第二の親を選択し,子を生成する.制約条件を満たさない実行不可能解の中には,解集団中の実行可能解より良い目的関数値(評価値) を示す場合があるため,それを解探索の手掛かりに活用する.まず,(1) 基礎となるTNSDM の指向性交配において,実行可能解より高い目的関数値を持つ解を解探索に活用することによって最適化性能が改善されることを示す.次に,(2)指向性交配による解探索効果が問題の性質に依存することを解決するために,有用な実行不可能解の選出領域を制御するTNSDM-CS (TNSDM with Controlling Selection area) を提案する.これにより,解探索中に生じる実行不可能解が少ない問題では,選出領域を拡大して指向性交配を実行しやすく,多い問題では縮小して良い親を選べるようになる.また,(3) 指向性交配で活用する実行可能解は,良い目的関数値を持つが実行不可能であるがゆえ,世代ごとに解集団から消失される.この問題を解決するため,有用な実行不可能解を解集団中にアーカイブし,解探索の手掛かりとして繰り返し活用するTNSDM-A(TNSDM with Archive) を提案する.さらに,(4) TNSDM-CS とTNSDM-A を組み合わせたTNSDM-CSA (TNSDM with Controlling Selection area and Archive) を提案する.TNSDM-CS において,有用な実行不可能解の選出領域を縮小すると,解探索の指向性が高まるため解探索性能が改善される利点があるが,同時に,選出領域に解が存在せずに指向性交配を実行できないケースが生じる欠点がある.この問題に対して,有用な実行不可能解のアーカイブを導入すると,選出領域を縮小しても選出領域に解が得られやすくなり,選出領域を縮小する欠点を補える.また,(5) 指向性交配で選択する有用な実行不可能解から子に複写される遺伝子(変数) の量を操作するTNSDM-CG (TNSDM with Controlling crossed Genes) を提案する.実行不可能解から子に複写される遺伝子量を減少させると,子は実行可能解になりやすいが有用な遺伝子情報を得にくい.逆に増加させると,子は実行不能解になりやすいが有用な遺伝子情報を得やすくなる.このバランスを操作することによって,指向性交配の解探索効果を高める.最後に,(6)TNSDM-CS とTNSDM-A,TNSDM-CG それぞれの指向性交配の効果を高める手法を組み合わせたTNSDM-CSACG(TNSDM with Controlling Selection area, Archive and Controlling crossed Genes) を提案し,その効果を検証する.提案法の効果を検証するため,離散問題のm 目的k ナップザック問題,連続問題のSRN,OSY,TNK,mCDTLZ,実問題の3 段式ハイブリッドロケットの概念設計最適化問題を用いる.また,比較アルゴリズムとして,代表的なCNSGA-II とRTS アルゴリズムを用いる.実験の結果,本研究で提案するいずれのアルゴリズムも,従来法より高い解探索性能を示すことが明らかになった.その詳細について順に述べると,まず,(1)TNSDM が従来法より高い解探索性能を示すことがわかった.これより,目的関数値の高い実行不可能解を活用する指向性交配によって,制約条件を有する多目的最適化問題における進化計算の解探索性能が改善されることが明らかになった.次に,(2) TNSDM-CSにおいて有用な実行不可能解の選出領域を制御することによって,指向性交配による解探索効果がさらに高まることが明らかになった.選出領域が拡大されると指向性交配の実行回数が増加する効果があり,縮小されると解探索の指向性が高まる効果があるため,解探索性能が改善される.また,(3) TNSDM-A において有用な実行不可能解を解集団中にアーカイブすることによっても,指向性交配による解探索効果がさらに高まることが明らかになった.これは,TNSDM では世代ごとに消失してしまう有用な実行不可能解を繰り返し指向性交配に活用できるためである.さらに,(4) TNSDM-CSA において有用な実行不可能解の選出領域制御法にアーカイブ法を組み合わせると,指向性交配を実行できないケースが減るため,より選出領域を縮小して解探索の指向性を高めた場合に,TNSDM-CS とTNSDM-A より高い解探索性能を達成できることが明らかになった.また,(5) TNSDM-CG において有用な実行不可能解から子へ複写される遺伝子(変数) 量を操作することによって,子の実行可能解へのなりやすさと,子に複写される解探索に有用な遺伝子情報の量を操作できるようになり,指向性交配の効果が高まることが明らかになった.最後に,(6)TNSDM-CSACG において,有用な実行不可能解の選出領域制御法とアーカイブ法,交叉量操作法を組み合わせると,上記(1)~(5) のアルゴリズムと比べ,最も高い解探索性能を示すことが明らかになった.(4) において示される有用な実行不可能解の選出領域制御法にアーカイブ法の組み合わせによる効果に加え,交叉量操作により親として選択された実行不可能解から子に複写する遺伝子量を制御することによって解探索性能が高まる.
Full-Text

http://ir.lib.uec.ac.jp/infolib/user_contents/9000000832/9000000832.pdf

Number of accesses :  

Other information