JP2006155449A

JP2006155449A - 分散遺伝的アルゴリズムを用いた最適化処理方法

Info

Publication number: JP2006155449A
Application number: JP2004348086A
Authority: JP
Inventors: Rei Wang; レイワン
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 2004-12-01
Filing date: 2004-12-01
Publication date: 2006-06-15
Also published as: KR20070085607A; CN101103367A; US7908229B2; WO2006059788A2; US20090271341A1; CN101103367B; WO2006059788A3; WO2006059788A9; WO2006059788B1; EP1836656A2

Abstract

【課題】遺伝的アルゴリズムによる最適化処理方法において、局所解に留まることを避けるために容易に最適解に到達しない場合があった。
【解決手段】複数の個体を有する島を複数形成し、これら複数の島それぞれに遺伝的アルゴリズムを適用して所望の条件をクリアするまで前記個体の交叉、突然変異、評価、選択を繰り返し、最適解を得る最適化処理方法であり、個体を別の島に移住させて最適解を得るようにした最適化処理方法である。
【選択図】図１

Description

本発明は複雑な種々の組合せの中から最適解を選び出す分散遺伝的アルゴリズムに関するものである。

従来の遺伝的アルゴリズムとしては、特許文献１に記載されたものが知られている。この遺伝的アルゴリズムを図７のフローチャートを用いて簡単に説明する。

図７において、パターンの要素数、パターン集団内のパターン数、適応度の目標値等々各設定値の初期値を入力する工程Ｓ１と、互いに異なる複数のパターンからなるパターン集団を生成するするパターン生成集団工程Ｓ２と、パターン集団の中から所定数のパターンを抽出し、それらパターンの構成要素を操作して操作パターンを生成する操作工程Ｓ３と、抽出パターンおよび操作パターンの群から、それらパターンから得られる特性をもとに、互いの異なる特性を有するパターンを抽出パターンと同数選択する選択工程Ｓ４と、抽出したパターンに代えて選択工程にて選択した所定数のパターンをパターン集団に加える置換工程Ｓ５と、操作工程、選択工程、置換工程からなる一連のアルゴリズム工程を、アルゴリズム工程にて得た直前のパターン集団内の最良の特性値が所望の値の範囲内になるまで繰り返す工程Ｓ６からなる。
特開２００１−１９５３８０号公報

このような遺伝的アルゴリズムを用いた最適化方法ではフローチャートで示される演算を繰り返すが、すべてのパターンが同じパターン集団内に属するため局所解に陥る可能性があり、これを避けて最適値を見出すために数多くの計算を繰り返す必要があった。言い換えると最適化の要求レベルを上げると最適値を見出すまでの時間がかかるという課題を有していた。

本発明は、遺伝的アルゴリズムを用いた最適化方法において、より少ない繰り返し回数にて最適な解を見出すことを目的としたものである。

この課題を解決するため、本発明の分散遺伝的アルゴリズムは複数の個体を有する島を複数形成し、これら複数の島それぞれに遺伝的アルゴリズムを適用して所望の条件をクリアするまで前記個体の交叉、突然変異、評価、選択を繰り返し、最適解を得る最適化処理方法で、個体を別の島に移住させて最適解を得るようにした最適化処理方法であり、各島の個体が別の島に一世代ごとに移住するようにしたことを特徴としている。かかる方法によれば各島における個体のいくつかが別の島に移住し、一世代ごとに評価の低い個体と入れ替わることによりその島に存在する個体の評価の平均値が上がり、何世代か経過することにより最適解に到達する。

個体は複製されて移住するので、別の島に移住したのち評価の低い個体が選択、排除されても島内の総個体数は変化せず、個体の多様性が保たれる結果、局所解に留まることが少なくなる。

また、島から別の島へ移住する個体はランダムに選択されて移住するので島内の個体の多様性が保たれ、遺伝的アルゴリズムに起こりがちな局所解に陥ることが少なくなる。

また、個体を評価する評価関数を複数有することにより、すべての島で同一の評価関数を使用せず異なった評価関数を用いることにより、局所解に陥ることを避けることができる。

さらに、遺伝的アルゴリズムによって得られたある世代での最適の個体に対し、一つのパラメータについて局所探索を行うことにより効率的に最適解に到達できる。

さらに局所探索を行う個体はランダムに選択され多様な個体について局所探索が行われる結果、局所探索の効率が向上する。

さらに、一つのパラメータについてある幅で局所探索を行い、より良い解が得られなかった場合、そのパラメータの局所を記憶しておき、次の世代で同じパラメータについて局所探索する場合は前記局所では行わず別の場所で探索するので効率的に最適解を得ることができる。

また、薄膜を多層に形成した光フィルタにおいて、薄膜各層の屈折率、膜厚の最適設計値を本最適化処理方法により容易に求めることができる。

本発明の分散遺伝的アルゴリズムを用いた最適化処理方法は各島において遺伝的アルゴリズムを適用し、世代ごとに個体をランダムに選択して各島間に移住させて、最適解を求めるものであり、各島のベストの個体を移住させた場合に見られるように同質の個体が各島に集まることがないので、局所解に留まることなく最適解に到達することができる。さらに各島の遺伝的アルゴリズムの計算を別個の電子計算機を用いて行うことが可能であり、より短時間での計算が可能となる。

以下、本発明の実施の形態につき図面を参照しながら説明する。

（実施の形態１）
図１は本発明の分散遺伝的アルゴリズムの概念を表した図であり、島１には個体１０１,１０２，１０３等、島２には個体２０１，２０２，２０３等、島３には個体３０１，３０２，３０３等が存在する。島１では個体１０１、島２では個体２０３、島３では個体３０２がランダムに選択されて、個体１０１は島２へ、個体２０３は島３へ、個体３０２は島１にそれぞれ移住した後、各島においてすべての個体が評価、淘汰され、最適値に到達するまでこの流れを繰り返す。

本実施の形態では、多層薄膜から構成される光フィルタの最適膜厚と最適層数を求めるために分散遺伝的アルゴリズムを用いたのでこの膜厚と層数の求め方について説明する。

多層薄膜の光フィルタは図２に示すようにガラス基板１０の上に、二酸化ケイ素よりなる第１層１１、次に五酸化タンタルよりなる第２層１２、次に二酸化ケイ素よりなる第３層１３、その次には五酸化タンタルよりなる第４層１４というふうに二酸化ケイ素と五酸化タンタルの薄膜を交互に形成したもので、これら二酸化ケイ素と五酸化タンタルの各層の膜厚を変えて形成することにより光フィルタとして所望の透過率特性（波長と透過率）を得ることができる。所望の透過率特性を有する光フィルタの各層膜厚の最適値を求める方法についてさらに詳細に説明する。

図３は島に存在する各個体と多層薄膜の膜厚の関係を表すもので、個体Ａには遺伝子Ａ１，Ａ２，Ａ３，Ａ４・・・Ａｎがあり、これら遺伝子Ａ１が１層目、Ａ２が２層目、Ａ３が３層目、Ａ４が４層目、Ａｎがｎ層目の膜厚に相当する。個体はＡからＸまでこの島に存在し、別の島には別の遺伝子からなる個体が複数存在している。

図４において島１では所定数の初期個体を発生し、次に他の島へ移住する個体をランダムに選択する。その個体は複製され島２へ移住し、島２において各個体は交叉や突然変異を受ける。

その後、島にいるすべての個体について評価値を計算する。評価値は、所望の透過率と計算による透過率の差をＥｒｒとして島ごとに以下の２種類の式により算出される。奇数番号の島については（式１）を、偶数番号の島については（式２）を用いた。

次に、各々の個体の評価値を計算した後、ランダムに選択された個体について局所探索を行う。局所探索とは上記遺伝的アルゴリズムを行って得られた結果につき、ある個体のあるパラメータについてそのパラメータを少し変化させてさらに良いものがないかを探索することである。なおここで言うパラメータとは各層の膜厚のことで、層数は最大１００層とした。

光フィルタの最適膜厚を求める場合の局所探索について図を用いて説明する。図５のマトリクスは模式的にある個体の遺伝子すなわち各層の膜厚を表したもので、層数は１２、膜厚は９水準とし、各層番号を横軸に、層の膜厚を縦軸にとっている。各層の黒く塗りつぶされたところが各層の膜厚である。この状態で局所探索を行うにはある遺伝子の、ここではランダムに選択された第３層の膜厚についてさらに良い値がないかどうか探索する。第３層の黒く塗りつぶされたマスから上下２マス離れた縦線で表されたマスにつき評価を行い、上下どちらかのマスの膜厚の値がもとの黒く塗りつぶされたマスの膜厚より良ければ、良い方の膜厚が第３層の膜厚として残る。また上下どちらかのマスの膜厚よりも黒く塗りつぶされたマスの値の方が良ければ、黒く塗りつぶされたマスの膜厚が残り、この世代における局所探索は終了する。

各島にて世代ごとに局所探索が行われ、探索される遺伝子すなわち層はランダムに選択されるのであるが、何世代かの後この第３層が再度選択された場合、以前局所探索を行った結果残らなかった二つのマスを除いた残りのマスにつき局所探索を行う。すなわち第３層の縦線で示されたマスの局所探索を行い、これら縦線のマスの評価が良くなくて残らなかった場合、以降の第３層での局所探索は斜線で示されたマスの中から２つを選択して探索する。

図５において、局所探索が終了するとそれぞれの島において評価値の悪い個体が選択、排除されて分散遺伝的アルゴリズムの一世代が完了する。この時評価値が設定した値をクリアしているかどうかを判定し、もし終了と判定されない場合は、もとのランダム選択のところに戻り同じ処理を繰り返す。そして個体の評価値が設定した値をクリアしたと判定すれば、最適化されたと判断し終了する。この一連のループは各島ごとに行われ、個体の移住は各島にまたがって行われる。

多層薄膜の光フィルタは第１層が二酸化ケイ素とし、その屈折率は１．４５１５３１、第２層は五酸化タンタルであり、その屈折率は２．０５９３５８である。光フィルタはこれらの層が交互に形成されるので奇数層はすべて二酸化ケイ素、偶数層はすべて五酸化タンタルである。本最適化処理方法においては、島を５、島内の個体数を２００、すなわち一世代で１０００個体を評価する最適化処理を行った。最適化処理により得られた特性と目標特性とを図６に示す。また（表１）に本最適化処理方法にて得られた多層薄膜の各膜厚を示す。

以上のように本最適化処理方法により目標とする特性に極めて近い特性を有する多層薄膜の光フィルタの設計値を容易に得ることができる。

本発明の分散遺伝的アルゴリズムを用いた最適化処理方法は、電子計算機を用いて最適化問題等を解く最適化手法として有用である。

本発明の分散遺伝的アルゴリズムの概念を表す図光フィルタの構造を表す断面図個体の遺伝子と膜厚の関係を示す説明図本発明の分散遺伝的アルゴリズムを表すフローチャート本発明の分散遺伝的アルゴリズムにおける局所探索の説明図本発明の実施の形態において得られた多層薄膜の光フィルタのゲイン特性の計算値と目標値を比較した図従来の遺伝的アルゴリズムを説明するフローチャート

符号の説明

１０ガラス基板
１１第１層
１２第２層
１３第３層
１４第４層
１０１，１０２，１０３島１の個体
２０１，２０２，２０３島２の個体
３０１，３０２，３０３島３の個体

Claims

複数の個体を有する島を複数形成し、これら複数の島それぞれに遺伝的アルゴリズムを適用して所望の条件をクリアするまで前記個体の交叉、突然変異、評価、選択を繰り返し、最適解を得る最適化処理方法であり、個体を別の島に移住させて最適解を得るようにした最適化処理方法。
複製された個体が移住する請求項１に記載の最適化方法。
島内においてランダムに選択された個体が複製される請求項２に記載の最適化処理方法。
個体の評価を行う評価関数の定義を少なくとも２種類以上持つ請求項１に記載の最適化処理方法。
遺伝的アルゴリズムのフローにおいて個体の一つのパラメータについてあるステップの局所探索を行うという工程を有する請求項１に記載の最適化処理方法。
局所探索を行う個体の選択はランダムに行う請求項５に記載の最適化処理方法。
個体の一つのパラメータについてあるステップで局所探索を行い、より良い解が得られなかった場合そのステップを記憶しておき、次の世代で同じパラメータについて局所探索する場合は前記ステップ以外のステップで探索する請求項５に記載の最適化処理方法。
請求項１から請求項７に記載の最適化処理方法を用いた多層膜の光フィルタの製造方法。