多目的最適解探索支援装置、及び多目的最適解探索支援プログラム
【課題】遺伝的アルゴリズムを対象とし、パラメータ（遺伝子）と評価値（固体の適応度）を可視化する技術を提供する。
【解決手段】遺伝的アルゴリズムを利用した多目的最適化問題に対応する多目的最適解探索支援装置であって、表示手段を備え、複数種類の正規化方法を用いた結果について、前記表示手段に、正規化方法を切り替えて、正規化結果を表示させる切替手段を備える。
【解決手段】遺伝的アルゴリズムを利用した多目的最適化問題に対応する多目的最適解探索支援装置であって、表示手段を備え、複数種類の正規化方法を用いた結果について、前記表示手段に、正規化方法を切り替えて、正規化結果を表示させる切替手段を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多目的最適解探索支援装置、及び多目的最適解探索支援プログラムに関し、特に遺伝的アルゴリズムを適用した得られた最適解の探索を支援する多目的最適解探索支援装置、及び多目的最適解探索支援プログラムに関する。
【背景技術】
【０００２】
多目的最適化の問題では、パレート最適解が示すように多数の最適解候補がある。その中から最終的に一つの最適解と言う。その中から一つの最適解を選択することは容易ではない
【０００３】
また、評価関数は設計者の経験的・実験的検証により決定されるか、もしくは関連研究論文などから引用されることが少なくない。そして、最終的な結果（評価値）によって、その有効性が議論されている。もし、パレート最適解におけるパラメータと評価値が一目で容易に把握可能となれば、それらの関連性を確認することが可能になり、設計者が意図している最適解が探索されているか否かの判断が容易になる。
【０００４】
多目的最適化においては、遺伝的アルゴリズムが利用されることが多い。遺伝的アルゴリズムの可視化に関する先行研究として、非特許文献１から非特許文献３に例示するものがある。情報の「可視化」とは、情報を色や形状などで表現する技術である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】W.B.Shineand C.F.Erick、「Visualization the evolution of genetic algorithm search processes」、Proceedings of 1997 IEEEInternational Conference on Evolutionary Computation、pp.367-372, 1997
【０００６】
【非特許文献２】E.Hartand P.Ross、「Gavel-ANew Tool for Genetic Algorithm Visualization」、 IEEE Transaction on EvolutionaryComputation、Vol.5,No.4, pp.335-348, 2001
【０００７】
【非特許文献３】T.D.Collins、「Applying software visualizationtechnology to support the use of evolutionary algorithm」、Journal of VisualLanguages and Computing、14, pp.123-150, 2003
【発明の概要】
【発明が解決しようとする課題】
【０００８】
遺伝的アルゴリズムに関する先行研究は、直接可視化型と間接可視化型とに大別される。直接可視化型では、遺伝子の値、評価値・適応度、探索空間をそれぞれ可視化し、探索過程および結果を目視により確認するものである。しかしながら、遺伝子の値、適応度、探索空間が個別に表示されるため、直感的にその相互関係を把握することが艱難となる。そのため、設計者が意図している解探索が実行されているか否かの判断も容易ではない、という問題点がある。また、最適解候補（準最適解）を意味する個体数が増加するに従って設計者の負担（確認作業）が増加することになる。さらに、可視化する探索空間は２または３次元で表現されるが、その空間を構成する軸の決定は容易ではなく、特に多目的最適化においては困難である。
【０００９】
一方、間接可視化型では、探索空間の軸を情報圧縮技術により決定するものと、染色体（遺伝子の場合）と評価値・適応度の相互関係を統計的処理により定量化することで可視化するものとがある。多数存在する情報圧縮技術の中において、自己組織化マップを応用した可視化技術は、その有用性が実験的に検証されている。これには、評価関数の出力をそのまま自己組織化マップに入力し、２次元空間にマッピングする手法と、定量化された染色体間の相互関係を自己組織化マップの入力とし、２または３次元空間にマッピングする手法が提案されている。しかしながら、間接可視化型では、遺伝子の値がどのように解探索および適応度に関与しているかを一目で容易に把握・確認することはできない。
【課題を解決するための手段】
【００１０】
本発明は、上記の如き問題点に鑑み、遺伝的アルゴリズムを対象とし、パラメータ（遺伝子）と評価値（固体の適応度）を可視化する技術を提供することを目的とする。
係る問題点を解決するため、本発明に係る多目的最適解探索支援装置は、遺伝的アルゴリズムを利用した多目的最適化問題に対応する多目的最適解探索支援装置であって、表示手段と、複数種類の正規化方法を用いた結果について、前記表示手段に、正規化方法を切り替えて、正規化結果を表示させる切替手段を備えることを特徴とする。
【００１１】
また、本発明に係る多目的最適解探索支援プログラムは、上記本発明に係る多目的最適解探索支援の機能をコンピュータに実現させることを特徴とする。
【発明の効果】
【００１２】
本発明に係る多目的最適解探索支援装置等によると、遺伝的アルゴリズムを適用した多目的最適解探索において、一つ一つの固体に対する、その遺伝子の値を確認する作業が容易に行える、という効果がある。
【図面の簡単な説明】
【００１３】
【図１】擬似カラー表示法により、個体の遺伝子と関連付ける画素に色を割り当てる様子について説明するための図である。
【図２】多目的最適化問題（ＫＵＲ：Kursawe test function、ＺＤＴ６：Zitzler, Deb, and Thiele test function）とＲＧＡの設定パラメータをそれぞれ示す図である。
【図３】ＫＵＲを用いて得られた、各テスト関数のパレート面とパレート最適解の可視化結果を示す図である。
【図４】ＺＤＴ６を用いて得られた、各テスト関数のパレート面とパレート最適解の可視化結果を示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について、図面等を参照しながら説明する。
本実施の形態では、擬似カラー表示法により、個体の遺伝子と関連付ける画素に色を割り当てる。図１は、その様子について説明するための図である。
【００１５】
このように擬似カラーで表現するために、遺伝子の値は正規化[０，１]される。正規化方法は、（１）パレート最適解とみなされた全個体の全遺伝子の最小値で減算した後に最大値で除算する方法（ＮＡＧ：Normalization on All Genes）と、（２）全個体の各遺伝子の最小値で減算した後に最大値で除算する方法（ＮＥＧ：Normalization on Each Gene）の２種類とする。
【００１６】
（１）は、パレート最適解全体のうち、特異的な値を持つ遺伝子を把握するためであり、（２）は、各遺伝子の値の詳細な違いを把握するためである。また、評価値も遺伝子の値を同様に正規化し、グレースケールで表現する。
【００１７】
以下、計算機シミュレーションについて説明する。図２は、多目的最適化問題（ＫＵＲ：Kursawe test function、ＺＤＴ６：Zitzler, Deb, and Thiele test function）とＲＧＡの設定パラメータをそれぞれ示す図である。テスト関数ＫＵＲは、非連続で、かつ非凸関数であり、多峰性の特性を持つ。テスト関数ＺＤＴ６は、単峰性の特性を持つ。
【００１８】
図３、図４は、本実施の形態において、得られた、各テスト関数のパレート面とパレート最適解の可視化結果を示す図である。図３中の（ａ）は、ＫＵＲ、図４中の（ａ）はＺＤＴ６のテスト関数のパレート面である。図３、図４の（ｂ）は、パレート最適解の全個体の全遺伝子の最大値と最小値によりＮＡＧを用いて正規化した結果を示す。図３、図４の（ｃ）は、各遺伝子における、その値の最大値と最小値とを用いて、ＮＥＧにより正規化した結果を示す。なお、本実施の形態において、パレート最適解探索には、ＭＡＴＬＢ Global Optimization Toolbox を使用した。本実施の形態では、例えばマウス等の入力手段を用い、簡単に、例えばＫＵＲ、ＺＤＴ６の各々についてＮＡＧとＮＥＧ、といった異なる正規化方法による結果の表示を切り替えることができる。
【００１９】
より具体的には、図３（ｂ）と図３（ｃ）との間の表示を切り替えたり、図４（ｂ）と図４（ｃ）との間の表示を切り替えたりすることが容易にできる。
【００２０】
テスト関数ＫＵＲの結果において、第一目的関数（ｙ１）は、変数２（ｘ２）」の値の増加に伴って、おおよそ減少する傾向にあることが伺える。ＫＵＲの第一目的関数の出力は隣り合った変数の２乗和の値に左右されるため、変数の数が３つの場合、変数２の影響を強く受けると推測されるが、本実施の形態の手法により遺伝子の値をカラー表示しているため、容易に把握することが可能となっている（図３（ｂ）（ｃ）参照）。
【００２１】
もっとも、今回の事例では、ＮＡＧとＮＥＧとの結果に大きな差は見られなかった。これは、各変数（遺伝子）にＮＡＧとＮＥＧとで使用する最大値・最小値が含まれていたためである、と推測される。
【００２２】
テスト関数ＺＤＴ６において、ＺＤＴ６の第一目的関数の変数が変数１のみであるため、変数１（ｘ１）と第一目的関数（ｙ１）との間に偏りが存在する。このことは、パレート面からは確認できないが、図３（ｂ）におけるカラーバー（提出物件参照）に表示されている値を参照することにより容易に確認できる。しかしながら、ＺＤＴ６は、ｘ１＝[０．０，０．２]における範囲でしか、ｙ１＝[０．３２６，０．７]を得ることができないように設計されている。ｘ１＝[０．０，０．２]は、変数１が極めて濃い青色で表示されることを意味するが、図４（ｂ）では、濃い青色で表現された変数１を確認するには至らなかった（提出物件参照）。
【００２３】
これは、Multi-Objective Genetic Algorithm（ＭＯＧＡ）を使用しているため、真のパレート最適解に到達していないことが原因であると推測される。また、ＮＡＧの結果では、変数２〜１０（ｘ２〜１０）の値の差を確認できなかった。これは、変数２〜１０が、極めて０．０に近い値を持っているためだと考えられる。
【００２４】
一方、ＮＥＧの結果では、各遺伝子の詳細な違いを確認することができた。しかしながら、その解釈および十分に考察するまでには至らなかった。これは、変数２〜１０が個別の意味を持つ変数ではないためである。さらに、ＮＡＧとＮＥＧとの結果を比較すると、正規化方法の違いによっては、把握可能な情報が異なることが解る。
【００２５】
パレート最適解から一つの最適解を選択する場合、パレート最適解と判断されたすべての個体の遺伝子の値を確認する必要がある。一つ一つの個体に対する、その遺伝子の値の確認には、個別に対応するための操作が必要となり、最適解候補数の増加に伴って、その作業コストは高くなる。以上に説明した本実施の形態の手法を適用することで、一つ一つの個体に対する、その遺伝子の値を確認する作業が容易に行える、と推測される。
【産業上の利用可能性】
【００２６】
本発明は、例えば、遺伝的アルゴリズムを利用した多目的最適化に適用することができる。
【技術分野】
【０００１】
本発明は、多目的最適解探索支援装置、及び多目的最適解探索支援プログラムに関し、特に遺伝的アルゴリズムを適用した得られた最適解の探索を支援する多目的最適解探索支援装置、及び多目的最適解探索支援プログラムに関する。
【背景技術】
【０００２】
多目的最適化の問題では、パレート最適解が示すように多数の最適解候補がある。その中から最終的に一つの最適解と言う。その中から一つの最適解を選択することは容易ではない
【０００３】
また、評価関数は設計者の経験的・実験的検証により決定されるか、もしくは関連研究論文などから引用されることが少なくない。そして、最終的な結果（評価値）によって、その有効性が議論されている。もし、パレート最適解におけるパラメータと評価値が一目で容易に把握可能となれば、それらの関連性を確認することが可能になり、設計者が意図している最適解が探索されているか否かの判断が容易になる。
【０００４】
多目的最適化においては、遺伝的アルゴリズムが利用されることが多い。遺伝的アルゴリズムの可視化に関する先行研究として、非特許文献１から非特許文献３に例示するものがある。情報の「可視化」とは、情報を色や形状などで表現する技術である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】W.B.Shineand C.F.Erick、「Visualization the evolution of genetic algorithm search processes」、Proceedings of 1997 IEEEInternational Conference on Evolutionary Computation、pp.367-372, 1997
【０００６】
【非特許文献２】E.Hartand P.Ross、「Gavel-ANew Tool for Genetic Algorithm Visualization」、 IEEE Transaction on EvolutionaryComputation、Vol.5,No.4, pp.335-348, 2001
【０００７】
【非特許文献３】T.D.Collins、「Applying software visualizationtechnology to support the use of evolutionary algorithm」、Journal of VisualLanguages and Computing、14, pp.123-150, 2003
【発明の概要】
【発明が解決しようとする課題】
【０００８】
遺伝的アルゴリズムに関する先行研究は、直接可視化型と間接可視化型とに大別される。直接可視化型では、遺伝子の値、評価値・適応度、探索空間をそれぞれ可視化し、探索過程および結果を目視により確認するものである。しかしながら、遺伝子の値、適応度、探索空間が個別に表示されるため、直感的にその相互関係を把握することが艱難となる。そのため、設計者が意図している解探索が実行されているか否かの判断も容易ではない、という問題点がある。また、最適解候補（準最適解）を意味する個体数が増加するに従って設計者の負担（確認作業）が増加することになる。さらに、可視化する探索空間は２または３次元で表現されるが、その空間を構成する軸の決定は容易ではなく、特に多目的最適化においては困難である。
【０００９】
一方、間接可視化型では、探索空間の軸を情報圧縮技術により決定するものと、染色体（遺伝子の場合）と評価値・適応度の相互関係を統計的処理により定量化することで可視化するものとがある。多数存在する情報圧縮技術の中において、自己組織化マップを応用した可視化技術は、その有用性が実験的に検証されている。これには、評価関数の出力をそのまま自己組織化マップに入力し、２次元空間にマッピングする手法と、定量化された染色体間の相互関係を自己組織化マップの入力とし、２または３次元空間にマッピングする手法が提案されている。しかしながら、間接可視化型では、遺伝子の値がどのように解探索および適応度に関与しているかを一目で容易に把握・確認することはできない。
【課題を解決するための手段】
【００１０】
本発明は、上記の如き問題点に鑑み、遺伝的アルゴリズムを対象とし、パラメータ（遺伝子）と評価値（固体の適応度）を可視化する技術を提供することを目的とする。
係る問題点を解決するため、本発明に係る多目的最適解探索支援装置は、遺伝的アルゴリズムを利用した多目的最適化問題に対応する多目的最適解探索支援装置であって、表示手段と、複数種類の正規化方法を用いた結果について、前記表示手段に、正規化方法を切り替えて、正規化結果を表示させる切替手段を備えることを特徴とする。
【００１１】
また、本発明に係る多目的最適解探索支援プログラムは、上記本発明に係る多目的最適解探索支援の機能をコンピュータに実現させることを特徴とする。
【発明の効果】
【００１２】
本発明に係る多目的最適解探索支援装置等によると、遺伝的アルゴリズムを適用した多目的最適解探索において、一つ一つの固体に対する、その遺伝子の値を確認する作業が容易に行える、という効果がある。
【図面の簡単な説明】
【００１３】
【図１】擬似カラー表示法により、個体の遺伝子と関連付ける画素に色を割り当てる様子について説明するための図である。
【図２】多目的最適化問題（ＫＵＲ：Kursawe test function、ＺＤＴ６：Zitzler, Deb, and Thiele test function）とＲＧＡの設定パラメータをそれぞれ示す図である。
【図３】ＫＵＲを用いて得られた、各テスト関数のパレート面とパレート最適解の可視化結果を示す図である。
【図４】ＺＤＴ６を用いて得られた、各テスト関数のパレート面とパレート最適解の可視化結果を示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について、図面等を参照しながら説明する。
本実施の形態では、擬似カラー表示法により、個体の遺伝子と関連付ける画素に色を割り当てる。図１は、その様子について説明するための図である。
【００１５】
このように擬似カラーで表現するために、遺伝子の値は正規化[０，１]される。正規化方法は、（１）パレート最適解とみなされた全個体の全遺伝子の最小値で減算した後に最大値で除算する方法（ＮＡＧ：Normalization on All Genes）と、（２）全個体の各遺伝子の最小値で減算した後に最大値で除算する方法（ＮＥＧ：Normalization on Each Gene）の２種類とする。
【００１６】
（１）は、パレート最適解全体のうち、特異的な値を持つ遺伝子を把握するためであり、（２）は、各遺伝子の値の詳細な違いを把握するためである。また、評価値も遺伝子の値を同様に正規化し、グレースケールで表現する。
【００１７】
以下、計算機シミュレーションについて説明する。図２は、多目的最適化問題（ＫＵＲ：Kursawe test function、ＺＤＴ６：Zitzler, Deb, and Thiele test function）とＲＧＡの設定パラメータをそれぞれ示す図である。テスト関数ＫＵＲは、非連続で、かつ非凸関数であり、多峰性の特性を持つ。テスト関数ＺＤＴ６は、単峰性の特性を持つ。
【００１８】
図３、図４は、本実施の形態において、得られた、各テスト関数のパレート面とパレート最適解の可視化結果を示す図である。図３中の（ａ）は、ＫＵＲ、図４中の（ａ）はＺＤＴ６のテスト関数のパレート面である。図３、図４の（ｂ）は、パレート最適解の全個体の全遺伝子の最大値と最小値によりＮＡＧを用いて正規化した結果を示す。図３、図４の（ｃ）は、各遺伝子における、その値の最大値と最小値とを用いて、ＮＥＧにより正規化した結果を示す。なお、本実施の形態において、パレート最適解探索には、ＭＡＴＬＢ Global Optimization Toolbox を使用した。本実施の形態では、例えばマウス等の入力手段を用い、簡単に、例えばＫＵＲ、ＺＤＴ６の各々についてＮＡＧとＮＥＧ、といった異なる正規化方法による結果の表示を切り替えることができる。
【００１９】
より具体的には、図３（ｂ）と図３（ｃ）との間の表示を切り替えたり、図４（ｂ）と図４（ｃ）との間の表示を切り替えたりすることが容易にできる。
【００２０】
テスト関数ＫＵＲの結果において、第一目的関数（ｙ１）は、変数２（ｘ２）」の値の増加に伴って、おおよそ減少する傾向にあることが伺える。ＫＵＲの第一目的関数の出力は隣り合った変数の２乗和の値に左右されるため、変数の数が３つの場合、変数２の影響を強く受けると推測されるが、本実施の形態の手法により遺伝子の値をカラー表示しているため、容易に把握することが可能となっている（図３（ｂ）（ｃ）参照）。
【００２１】
もっとも、今回の事例では、ＮＡＧとＮＥＧとの結果に大きな差は見られなかった。これは、各変数（遺伝子）にＮＡＧとＮＥＧとで使用する最大値・最小値が含まれていたためである、と推測される。
【００２２】
テスト関数ＺＤＴ６において、ＺＤＴ６の第一目的関数の変数が変数１のみであるため、変数１（ｘ１）と第一目的関数（ｙ１）との間に偏りが存在する。このことは、パレート面からは確認できないが、図３（ｂ）におけるカラーバー（提出物件参照）に表示されている値を参照することにより容易に確認できる。しかしながら、ＺＤＴ６は、ｘ１＝[０．０，０．２]における範囲でしか、ｙ１＝[０．３２６，０．７]を得ることができないように設計されている。ｘ１＝[０．０，０．２]は、変数１が極めて濃い青色で表示されることを意味するが、図４（ｂ）では、濃い青色で表現された変数１を確認するには至らなかった（提出物件参照）。
【００２３】
これは、Multi-Objective Genetic Algorithm（ＭＯＧＡ）を使用しているため、真のパレート最適解に到達していないことが原因であると推測される。また、ＮＡＧの結果では、変数２〜１０（ｘ２〜１０）の値の差を確認できなかった。これは、変数２〜１０が、極めて０．０に近い値を持っているためだと考えられる。
【００２４】
一方、ＮＥＧの結果では、各遺伝子の詳細な違いを確認することができた。しかしながら、その解釈および十分に考察するまでには至らなかった。これは、変数２〜１０が個別の意味を持つ変数ではないためである。さらに、ＮＡＧとＮＥＧとの結果を比較すると、正規化方法の違いによっては、把握可能な情報が異なることが解る。
【００２５】
パレート最適解から一つの最適解を選択する場合、パレート最適解と判断されたすべての個体の遺伝子の値を確認する必要がある。一つ一つの個体に対する、その遺伝子の値の確認には、個別に対応するための操作が必要となり、最適解候補数の増加に伴って、その作業コストは高くなる。以上に説明した本実施の形態の手法を適用することで、一つ一つの個体に対する、その遺伝子の値を確認する作業が容易に行える、と推測される。
【産業上の利用可能性】
【００２６】
本発明は、例えば、遺伝的アルゴリズムを利用した多目的最適化に適用することができる。
【特許請求の範囲】
【請求項１】
遺伝的アルゴリズムを利用した多目的最適化問題に対応する多目的最適解探索支援装置であって、
表示手段と、
複数種類の正規化方法を用いた結果について、前記表示手段に、正規化方法を切り替えて、正規化結果を表示させる切替手段を備える
ことを特徴とする多目的最適解探索支援装置。
【請求項２】
コンピュータに、請求項１に記載の機能を実現させる多目的最適解探索支援プログラム。
【請求項１】
遺伝的アルゴリズムを利用した多目的最適化問題に対応する多目的最適解探索支援装置であって、
表示手段と、
複数種類の正規化方法を用いた結果について、前記表示手段に、正規化方法を切り替えて、正規化結果を表示させる切替手段を備える
ことを特徴とする多目的最適解探索支援装置。
【請求項２】
コンピュータに、請求項１に記載の機能を実現させる多目的最適解探索支援プログラム。
【図２】
【図１】
【図３】
【図４】
【図１】
【図３】
【図４】
【公開番号】特開２０１２−２４２９１６（Ｐ２０１２−２４２９１６Ａ）
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願番号】特願２０１１−１０９９５０（Ｐ２０１１−１０９９５０）
【出願日】平成２３年５月１６日（２０１１．５．１６）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 「動的画像処理実利用化ワークショップ２０１１ 講演概要集」、社団法人 精密工学会、平成２３年３月３日、第１１９、１２０ページ
【出願人】（３０４０２０２９２）国立大学法人徳島大学 (307)
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願日】平成２３年５月１６日（２０１１．５．１６）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 「動的画像処理実利用化ワークショップ２０１１ 講演概要集」、社団法人 精密工学会、平成２３年３月３日、第１１９、１２０ページ
【出願人】（３０４０２０２９２）国立大学法人徳島大学 (307)
[ Back to top ]