数理解析研究所講究録 1297 巻 2002 年 28-37

28
制約付き非線形最適化手法の一提案
制約遺伝的アルゴリズム–$-\alpha$

広島修道大学商学部

阪井

節子 (Setsuko Sakai)

Faculty of Commercial Science, Hiroshima Shudo University
広島市立大学情報科学部

高濱

徹行 (Tetsuyuki Takahama)

Faculty of Information Sciences, Hiroshima City University

1

まえがき
与えられた制約のもとで目的関数を最小にするような解を求める制約付き最適化問題, 特に非線形最適化問題は, 実問題に頻繁に出現する重要な最適化問題である. 制約付き最適化問題の解法としては, 線形計
画問題の場合はシンプレックス法がよく知られており, 目的関数が非線形で微分可能な場合には, 目的関数

2 次近似式と制約式の線形近似式により得られる 2 次計画問題を逐次解く逐次 2 次計画法, 目的関数の最急降下方向やその修正方向を有効制約式の作るアフイン集合上に射影した方向に探索する射影法, 線形計の画法におけるシンプレックス法を非線形計画問題に拡張した一般縮小勾配法などの最適化手法が知られている $[1, 2]$ . L かし, 目的関数が微分可能でない場合や制約条件が非凸の場合には, これらの方法を利用することは困難である.

制約付き最適化問題を制約のない最適化問題に変換する変換法と目的関数
値のみを用いる直接探索法を組み合わせることが有効であり, 多くの応用例が存在する. 変換法 [3] には,より汎用的な方法としては,ベナルティ法, 乗数法などがあるが, 制約条件の境界付近に解が存在する場合が多いこと, パラメータが少なく単純で使用しやすいことなどからペナルテイ法を採用することが多いが, ペナルテイ係数の値が大きくなるにつれて, 変換された問題の最適化が困難になるという問題, 制約条件を完全に満足する実行可能解を探索することが困難であるという問題がある [4].
) $[5,6]$
一方, 直接探索法の一つとして, 近年多点探索を行う遺伝的アルゴリズム (Genetic Algorithm,$\mathrm{G}\mathrm{A}$が広く使用されるようになってきている.

$\mathrm{G}\mathrm{A}$は, 生物の進化過程を模倣した最適化アルゴリズムであり,強力かつ柔軟な最適化手法として注目されている. GA を利用した制約付き最適化に関する研究も盛んに行われるようになってきており [7], 既存の方法と比較しても遜色のない結果が得られるようになってき) $[6,9,10]$ を採用し,(real-codedている [8]. 特に Michmlewicz らは, 遺伝子を実数値とする実数値
すべての制約式を満足する個体の集団である参照点 (reference point) 集団と線形制約式のみを満足する探索 (search point) 集団の 2 つの集団を用いることにより制約を扱う GENOCOPIII(GEnetic algorithm for$\mathrm{G}\mathrm{A}$$\mathrm{G}\mathrm{A}$

Numerical Optimization of COnstrained Problems) を提案し, 一般に非線形制約をも取り扱えることを示した [7, 8, 11, 12, 13].
本研究では,

を提案する.

$\alpha$$\alpha$

制約法 $[14, 15]$ を遺伝的アルゴリズムと組み合わせた$\alpha$

制約遺伝的アルゴリズム$(\alpha \mathrm{G}\mathrm{A})[16]$制約法は, 制約の満足度を表現する制約満足度を導入し, 通常の大小関係の代わりに制約満

足度を優先した大小関係である$\alpha$レベル比較を定義し, 通常の比較の代わりに$\alpha$レベル比較を用いて探索

制約法の特徴は, 目的関数を
制約付きの問題を制約のない問題に変換する方法である.
変換するのではなく, 最適化アルゴリズムにおける比較を置換することにより, アルゴリズムを変換する
制約法を Powell 法 [17] と組み合わせ, 文献 [15] では, Nelder&Mead のという点である. 文献 [14] では,
Simplex 法 [18] と組み合わせることにより, 目的関数が微分不可能な制約付き最適化問題が効率よく解ける
制約法が GA にも適用可能であることを示すことも本論文の目的である.
ことを示した.

することにより,$\alpha$$\alpha$$\alpha$$\alpha$

制約法を適用した$\alpha \mathrm{G}\mathrm{A}$では, 制約を満足しない個体は制約を満足するように,制約を満足した個体

は目的関数値を最適化するように自然に進化する. 本論文では, 線形計画問題, 非線形計画問題, 非凸非線

GA による制約付き最適化手法の中で有効性がよく知られての有効性を示す.
いる GENOCOPIII を発展させた GENOCOP5 .0 $[19, 20]$ と比較することにより,形制約など様々な種類のテスト問題について,$\alpha \mathrm{G}\mathrm{A}$

36
ffl

$\mathrm{b}^{-}\mathrm{C}\hslash\not\in-:F\grave{l}\not\equiv\sigma$)$\zeta \mathrm{P}\vee \mathrm{C}^{\backslash }\backslash \mathrm{F}\acute{\nearrow}J\star \mathrm{J}’\mathrm{t}4t\backslash \backslash \backslash \ddagger$$-\pi \mathrm{b}*\iota T\triangleright\backslash$

GENOCOP5.0 &lb $\Phi To-\sim\mu$ }\d ag er ),$\mathrm{Y}$$\mathrm{Z}$$\alpha \mathrm{G}\mathrm{A}\lambda\grave{\grave{\backslash }}=\sigma$)$\hslash\dot{\{}\yen$よりもさらに優れた方法であることを示した.
$\alpha \mathrm{G}\mathrm{A}$は,制約を満足しない場合には制約満足度が最大化され, 自然に制約を満足するようになるため,

GENOCOPIII や GENOCOP50 とは異なり, 制約条件を保存しない遺伝的操作を導入することが可能である.

今後は, 実数値遺伝的アルゴリズムの研究で提案されている様々な遺伝的操作を有効に取り込むとともに, 様々な実問題に対して謝辞

本研究の一部は,$\alpha \mathrm{G}\mathrm{A}$を適用していく予定である.

日本学術振興会科学研究費補助金基盤研究 (C)(2)(課題番号 14580498) による補助のもとで行われた.

参考文献[1] 今野浩, 山下浩: 非線形計画法, 日科技連出版社 (1978).

[2] 坂和正敏: 非線形システムの最適化, 森北出版 (1986).
[3] Fiacco, A. and McComick, G.: Nonlinear programming :Sequential unconstrained minimization
techiques, Society for Industrial and Applied mathematics (1990).

[4] 坂和正敏, 矢内克裕: 非凸非線形計画問題に対する浮動小数点型遺伝的アルゴ) ズム:改良型 GENOCOPI,
電子情報通信学会論文誌, Vol. J81-A, No. 1, pp. 90-97(1998).
$|$[5] Goldberg, D.: Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley(1989).

[6] 坂和正敏, 田中雅博: 遺伝的アルゴリズム, 朝倉書店 (1995).
[7] Michalewicz, Z.: ASurvey of Constraint Handling Techniques in Evolutionary Computation Methods, Proc. of the 6th International Conference on Genetic Algorithms, Cambridge, MA, MIT Press,
pp. 135-155 (1995).
[8] Michalewicz, Z.: Genetic algorithm+data stmctures $=evolution$ programs 3rd ed., Springer-Verlag,
Berlin (1996).

[9] Tsutsui, S., Yamamura, M. and Higuchi, T.: Multi-parent Recombination with Simplex Crossoverin Real Coded Genetic Algorithms, Proc. Genetic and Evolutionary Computation Conference(GECCO’99), pp. 657-664 (1999).
[10] 小野功, 山村雅幸, 喜多一: 実数値$\mathrm{G}\mathrm{A}$とその応用, 人工知能学会誌, Vol. 15, No. 2, PP. 259-266(2000).

[11] Michalewicz, Z.: Genetic Algorithms, Numerical Optimization and Constraints, Proc. of the 6thInternational Conference on Genetic Algorithms, Pittsburgh, pp. 151-158 (1995).
[12] Michalewicz, Z., and Nazhiyath, G.: Genocop III: ACo evolutionary Algorithm for Numerical OPIEEE International Conference
timization Problems with Nonlinear Constraints, Proc. of theon Evolutionary Computation, Vol. 2, Perth, PP. 647-651 (1995).
$\ell nd$[13] Michalewicz, Z. and Schoenauer, M.: Evolutionary Algorithms for Constrained Parameter Optimization Problems, Evolutionary Computation, Vol. 4, No. 1, pp. 1-32 (1996).

29
2. で本論文の対象とする制約付き最適化問題を定義し, 3. で 制約法を説明する. 4. での性能を示す. 6. はまとめである.
を定義し, 5. で
以下,$\alpha \mathrm{G}\mathrm{A}$$\alpha$$\alpha \mathrm{G}\mathrm{A}$2

制約付き最適化問題
本論文では, 次のような不等式制約, 等式制約, 上下限制約を持つ最適化問題 (P) を考える.

目的関数

および制約条件がともに線形の場合が線形計画問題, その他の場合が非線形計画問題である.

(P)

(1)

minimize$f(x)$

subject to$g_{j}(x)\leq 0,$$j=1,$$h_{k}(x)=0,$$k=1,$$\ldots,$$\ldots,$. $\leq X:\leq u:,$ $i=1,$$l_{1}$

ここで,$x=(x_{1}, \cdots, x_{n})$$m-q$$\ldots,$$n$

は $n$ 次元決定変数ベクトル, $f(x)$ は目的関数,$g_{j}(x)\leq 0$は$q$個の不等式制約,は線形あるいは非線形の実数値関数である. ’, : はそ
) 下限値, 上限値である. さらに, 以下では実行可能領域を $F$ , 上下限制約のみを満$h_{k}(x)=0$ は $m-q$ 個の等式制約であり,れぞれ, 決定変数

$q$

$f,$

$u$

$h_{k}$$g_{j},$$x_{i}\sigma$

足する領域を $S$ と呼ぶことにする.

3$\alpha$$\alpha$3.1

制約法

制約法について簡単に説明する.

制約付き最適化問題と制約満足度$\alpha$制約法では, 制約をどの程度満足しているかを表現するために, 制約満足度 $\mu(x)$ を導入する. 制約満

足度 $\mu(x)$ は, 以下を満足する関数である.
$\mu(x)=1$ ,$\{$if $g_{j}(x)\leq 0,$$0\leq\mu(x)<1$ , otherwise$h_{k}(x)=0$, for aU

$j,$

$k$

(2)

このような制約満足度を定義する 1 つの方法として, 各制約の満足度を定義し, それらを合成する方法があに関する区分的線形の制約満足
る. 例えば, 問題 (P) における各制約条件は, 機械的に以下のような$g_{j},$

度関数に変換できる. ただし,

1,$\mu_{g_{j}}(x)=\{$$1- \frac{g_{j}(x)}{b_{j}}$0,,$b_{j},$$h_{k}$

は適当な定数である.

$b_{k}(>0)$,

if$g_{\mathrm{j}}(x)\leq 0$if$\mathrm{O}\leq g_{j}(x)\leq b_{j}$,,$\mu_{h_{k}}(x)=\{\begin{array}{l}1-\frac{|h_{k}(x)|}{b_{k}}0\end{array}$$\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{i}\mathrm{f}|h_{k}(x)|,\leq b_{k}$(3)otherwise,

この各制約満足度から制約全体の満足度 $\mu(x)$ を求めるために, 各制約満足度を結合する. 結合演算としては, 以下のような $\min$ 演算が考えられる.
$\min$

3.2$\alpha$演算(4)$\mu(x)=\min_{j,k}\{\mu_{gj}(x), \mu_{h_{k}}(x)\}$レベル比較

以上の場合は目的関数値の大小関係
レベル比較を定義する.
を優先し, それ以外の場合は制約満足度の大小関係を優先する比較である
関数値と制約満足度の組 $(f, \mu)$ の集合上において, 制約満足度が$\alpha$$\alpha$30
点 $x,$

における関数値を$x_{2}$$,$

る関数値と制約満足度の組$\ovalbox{\tt\small REJECT},$$(\ovalbox{\tt\small REJECT}, \mu_{\ovalbox{\tt\small REJECT}})$$f_{2}$, 制約満足度を$\mu_{1},$間の大小関係であるとすると, 通常の大小関係である$\mu_{2}$$\alpha$レベル比較$\ovalbox{\tt\small REJECT}_{\alpha}(0\ovalbox{\tt\small REJECT}\alpha\ovalbox{\tt\small REJECT} \mathfrak{y}$$\ovalbox{\tt\small REJECT}$に対応す

は以下のようになる.

$f_{1}f_{1}\leq f_{2}\leq f_{2},’ \mathrm{i}\mathrm{f}\mu_{1}=\mu_{2}\mathrm{i}\mathrm{f}\mu_{1},\mu_{2}\geq\alpha$(5)$(f_{1}, \mu_{1})\leq_{\alpha}(f_{2}, \mu_{2})\Leftrightarrow\{$$\mu_{1}>\mu 2$

なお,$\leq 0$33$\leq_{1}$は制約満足度を優先する辞書式比較と一致する.

制約法の性質$\alpha$$\alpha$は関数値のみの比較と一致し,, otherwise

制約法は, 制約付き最適化問題を直接探索法で解く際に, 通常の比較の代わりにる方法である. 通常の大小比較を$\alpha$レベル比較を用いレベル比較に置き換えた最適化問題 (P\leq 。), すなわち,制約法にょる
但し,
最適化問題は以下のように定義できる.
minimize<。は \leq 。の意味での最小化である.
$\alpha$$\alpha$minimize$(\mathrm{P}\leq_{\alpha})$

ここで,問題 (P) の制約条件を $\mu(x)\geq\alpha$ に緩和した問題(6)$f(x)$$\leq_{a}$を以下のように定義する. なお,$(\mathrm{P}^{\alpha})$$(\mathrm{P}^{1})$は問題 (P) と等価である.
$(\mathrm{P}^{\alpha})$問題$(\mathrm{P}^{\alpha})$定理 1minimizesubject to

定珊 2 問題 (P) に最適解が存在するならば, 問題

最適解$\{\alpha_{n}\}$$x^{*}$(7)$\mu(x)\geq\alpha$と問題 (P\leq 。), および問題 (P) に関して以下の定理が成り立っ [14].

問題 $(P^{1})$ に最適解が存在するならば, 問題

定珊 3$f(x)$$(P\leq\alpha)$$(P_{\leq})1$の最適解は問題

任意の集積点は問題
定理 1, 2 は,$\alpha$$(P^{1})$$\alpha_{n}$の最適解である.

の最適解は, 問題 (P) の最適解である.

を強い意味で単調増加し 1 に収束する点列とする.

の存在と任意の$(P^{\chi})$に対する問題 (P\leq 。j の最適解$\hat{x}_{n}$$f(x),$ $\mu(x)$ を連続関数とし, 問題 $(P^{1})$ のの存在を仮定する. このとき, 点列$\{\hat{x}_{n}\}$のの最適解である.

レベル比較を行うことにより, 制約付き問題がそれと等価な制約のない問題に変換されることを示している.

したがって, 既存の制約のない最適化手法に$\alpha$レベル比較を導入することにょり, 制

約付きの問題を解くことが可能となる. 定理 3 は, ペナルティ法においてペナルティ係数をまで増加させて行くのと同様に,を 1 まで増加させながら最適化を行っても, 最適解が得られることを示してぃる.
$\infty$$\alpha$4$\alpha$$\alpha$

制約遺伝的アルゴリズム

制約法は,$\alpha \mathrm{G}\mathrm{A}$

目的関数値の大小関係のみに基づく最適化アルゴリズムと組み合わせることができる. 本

研究では, 適合度の大小関係のみに依存する戦略であるランキング戦略を採用することにより, 遺伝的アル
ゴリズムに

4.1

$\alpha$

制約法を適用する.

アルゴリズム$\alpha \mathrm{G}\mathrm{A}$のアルゴリズムを以下に示す.

1. 初期集団の生成 : 初期個体集団をランダムに生成する. すなわち, 各遺伝子 : を区間 $[l:, u:]$ の一様乱$x$数で生成する.

31
2. 終了判定 : 本論文では最大世代数$T$に達したとき, 実行を終了する.

レベルの決定 : 通常は $\alpha=1$ として探索すればよいが, 等式制約のように実行可能領域が非常に狭レベルを制御い場合には, 実行可能領域が狭すぎて有効な最適化が行えない. このような場合には

3.

$\alpha$$\alpha$

初期には制約条件を緩和して目的関数の最適化を優先し, 次第に制約条件を厳しくしてゆく必要

し,がある (4.2 参照).

4. 選択 : 個体の選択方法として, 適合度の大小比較のみに依存する方法であり, 頑健な方法として知られているランキング選択を採用する (4.3 参照).

5. 交叉 : 交叉確率

$P_{c}$

で親の交叉を行い, 子を生成する. なお, 交叉しない場合には親がそのまま子になったとみなす. 本論文では, 実数値$\mathrm{G}\mathrm{A}$用の交叉を採用する (4.4 参照).

6. 突然変異 : 本論文では, 正規分布にしたがった突然変異であるガウス突然変異 (Gaussian mutation)と制約付き最適化に有効であると考えられる境界突然変異 (boundary mutation) を突然変異として採用する (4.5 参照).

7. 世代交代 : 現在の集団を子に置き換え, 2. へ戻る.
$\alpha \mathrm{G}\mathrm{A}$のアルゴリズムを以下に$\mathrm{C}$

言語風に記述する.

$\alpha \mathrm{G}\mathrm{A}()$$\{$;
個体集団 $P(t)$ を生成 ;$t=0$while $(t\leq T)$;$\{$$\alpha=\alpha(t)$$\alpha$レベル比較により $P(t)$ 中の個体をランク付け ;$P’=P(t)$ からランキング選択 ;for (each $m$ 個体組
確率$P_{\mathrm{c}}$で$x^{1}$,$x^{1}$$\cdots,$,$\cdots,$$x^{m}$

for(each 遺伝子 $x$ :in

確率$P_{b}$

確率$P_{G}$

で$X$$x^{m}$

in $P’$ )

$\{$

を交叉 ;
$x^{1},$$\cdots,$$x^{m}$)$\{$: を境界突然変異 ;で $x$ : をガウス突然変異 ;

$\}$

$\}$

$t=t+1_{j}$$P(t)=P’$ ;
$\}$

$\}$

ただし,

$\alpha(t)$は世代 における$t$$\alpha$レベル,$P_{c}$

は交叉率,$P_{b}$

は境界突然変異率,$P_{G}$

はガウス突然変異率で

ある.

42

$\alpha$レベルの制御レベノレを満足す次のような制御方法を採用する.
になった後もある個体が常にある程度含まれるように, 最初は速く, 1 に近づくほどゆつくりと増加し, 1
本論文では, 等式制約を含む最適化問題に対して,$\alpha$32
る程度の最適化を行うことを目指す. そこで, 初期値$\alpha(0)$を初期集団の制約満足度の平均値と最大値の中の 2 次式に基づく制御を提案する.

間とし, 最大世代数 $T$ の半分以降は常{口となる以下のような世代

1,1$\alpha(0)=\overline{2}x_{k}1(\max\mu(x_{k})+\overline{N}1\sum\mu(x_{k}))$$\alpha(\mathrm{O})=\overline{2}x_{k}\overline{N}(\max\mu(x_{k})+2_{-}^{-}\mu(x_{k}))k=1$

$t$

,

(8)

’

$-(1- \alpha(0))(1-\frac{2t}{T})^{2}+1,0<t<\frac{T}{2}$$\alpha(t)=\{$

ただし,

43

$N$

は個体集団サイズ,

1,$t \geq\frac{T}{2}$,.

$x_{k}(k=1,2, \ldots, N)$ は各個体である.

選択

ランキング選択にはいくつかの種類があるが, 本論文では線形ランキング選択を用いる $[21, 22]$ . すな
わち, 個体集団中においてする. 個体$x_{k}$$\alpha$レベル比較によりランク付けを行い, ランクに応じた確率で選択確率を決定のランクが $r_{k}(r_{k}=1,2, \cdots, N)$ となった場合, 個体$x_{k}$の選択確率$p_{k}$

は以下のように決定される.

$p_{k}$

ただし,$\eta^{-}=2-\eta^{+},$$\eta^{+}$

$=$

(9)

$\frac{1}{N}(\eta^{+}-(\eta^{+}-\eta^{-})\frac{r_{k}-1}{N-1})$

は, 最大期待値 (maximum expected value) であり, 最良の個体が平均的個体より何倍選択されるかを指定する区間 [1.0, 2.0] の数である.

44

交叉

Michalewicz は実行可能領域が凸の場合には実行可能性が保存される交叉である, 単純交叉 (simple
crossover), 算術交叉 (arithmetic crossover), ヒューリステイック交叉 (heuristic crossover) という 3 種類の交叉を提案している. これに対して,$\alpha \mathrm{G}\mathrm{A}$では交叉によって制約が満足されなくなった場合には, 制約満

自然に制約を満足する方向に最適化される. したがって, 実行可能性の保存をそれほど重要視する必要はない. そこで, 本論文では親個体によって張られる単体 (simplex) に相似な単体内に一様分布にしたがって, 子の個体を生成することによって, 子の多様性を維持するシンプレックス交叉
足度の最大化が優先され,($\mathrm{S}\mathrm{P}\mathrm{X};\mathrm{s}\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{x}$$m$crossover) $[9,10]$ を用いる.

個の親個体

(1)

$\mathrm{f}\mathrm{f}\mathrm{l}\sigma)\ovalbox{\tt\small REJECT},\grave{\llcorner}\backslash \text{を}$(2)$y^{i},$$i=1,$$x^{1},$$\cdots,$$\cdots,$$x^{m}$が交叉するとき, 交叉後の子個体$g= \frac{1}{m}.\cdot\sum_{=1}^{m}x^{:}\text{とする}$$m$$x^{1’},$$x^{m\prime}$$\cdots,$

を以下のように定める.

.

を次式で求める : $y^{:}=g+\beta_{c}(x^{:}-g)$ で求める. ここで, ただし,$\beta_{\mathrm{c}}$は子個体が親個体の範囲からどの程度広がるかを決める正の定数である.

(3)

4.5

$y^{:},$$i=1,$$\cdots,$$m$で張られた単体$\mathcal{K}\{y^{1}, \cdots, y^{m}\}$内に一様に $m$ 個の子個体$x^{1’},$$oe^{m\prime}$$\cdots,$を生成する.

突然変異

Michalewicz は実行可能性を保存する突然変異として, 境界突然変異, 一様突然変異 (uniform mutation),
非一様突然変異 (non-uniform mutation), 全体非一様突然変異 (whole non-uniform mutation) という 4 種類の突然変異を提案している. 本論文では, これらを参考にして, 境界突然変異, ガウス突然変異の 2 種類を採用する.

以下の突然変異では, 個体 $x$ のある一つの遺伝子$x_{1}’.,$$x:+1,$$\ldots)$

を得る.

$x$

: のみを変化させ, 新しい個体 $oe’=(\ldots,$$x_{i-1}$,33
1. 境界突然変異 (boundary mutation)
境界突然変異では, ある遺伝子るときの端点を以下のように$x_{\ovalbox{\tt\small REJECT}}$$l(x\ovalbox{\tt\small REJECT}$のみを変化させたときに, 新しい個体が実行可能領域 $F$ に存在す

, r(x

箸,

$l(x_{i})=,.

$x_{\ovalbox{\tt\small REJECT}}$をどちらかに等確率で置換する.

(10)\min_{+(\ldots\prime x:-1,x_{*},x.1,\ldots)\in F}x_{i}’$$x_{i}’$$r(x_{\mathrm{i}})=$$( \ldots,oeoe’.x.\cdot\ldots)\in F\max_{:-1,.,+1\prime}$$\alpha \mathrm{G}\mathrm{A}$l(x実行可能領域中に存在する個体とそうでない個体が混在しており, 実行可能でない個体
r(x
存在しない場合もある. このため, 個体が実行可能なときには上記の突然変,実行可能でないときには実行可能領域に入れるために制約満足度 を最大化する. すなわ

では,

では,

異を行

$\mathrm{a}$$\mathrm{A}$$\mu$

ち, 境界突然変異率$P_{b}$

で以下のように$l(x:)$$x_{i}$

を$x_{i}’$に置換することになる.

or $r(x:)$$oe\in F$(11)$x_{\dot{\iota}}’=\{$$\mathrm{a}\mathrm{r}\mathrm{g}.\max_{x_{j}’\iota.\leq\leq u:}\mu(\ldots, x_{i}’, \ldots)x\not\in F$.
め探索と の最大化には, 囲い込み法と 2 分法による直接探索を用
境界突然変異は, 制約付き最適化問題の解が実行可能領域の境界付近に存在することが多いことから,
なお,$l(x_{i}),$$r(x:)$$\mathrm{A}^{\mathrm{a}}_{arrow}^{-}$$\mu$

このような解の探索に有効であると考えられる.

2. ガウス突然変異 (Gaussian mutation)
境界突然変異は比較的大域的な探索を行うため, 局所的な探索を積極的に行うガウス突然変異を併用する. 各変数 : の上下限制約の幅に比例した標準偏差を持つガウス分布に基づき, ガウス突然変異$x$率$P_{G}$

で以下のように$x$: を . に置換する.
$X_{1}’$(12)$x’.\cdot=x_{\dot{*}}+\delta$

ただし,

5

$\delta$は $N(0_{1}\beta_{G}^{2}(u:-l:)^{2})$ の乱数,$\beta G$

はガウス突然変異の分散を決める/ Д薀瓠璽燭任△.

制約付き非線形計画問題
本論文では,

5.1

Michalewicz の提案した最適化問題を対象に最適化を行, その結果について比較検討する.

テスト問題と実験条件

表 1 に Michalewicz が提案した 5 つの問題 $G_{1}\sim G_{5}[8,11]$ を示す.
形計画問題であり,る.

$\mathrm{a}$$\mathrm{A}$$G_{4}$$G_{1}$

は等式制約を含んでいる. これらの問題について,

は線形計画問題, その他は非線$\alpha \mathrm{G}\mathrm{A}$を GENOCOP50 と比較す

GENOCOP50 は全ての問題について標準設定を用いた. すなわち, 探索点集団と参照点集団サイズ

を各 70, 最大世代数 $T=5000$ , 非線形ランキング選択のパラメータ $c=0.1$ , 単純交叉, 算術交叉,
リスティック交叉, 境界突然変異, 非一様突然変異, 全体非一様突然変異の確率を 4/70 とした.

ヒュ–

制約領域が非常に狭いため標準設定では参照点を求めることができず, また参照点を与えても最適化が進まなかった. そこで, Michalewicz の提案に基づき, 等式制約の条件を緩和し, 以下の不なお,

$G_{4}$

では,等式制約に置き換えた.
$|h_{j}(x)|\leq\epsilon,$

さらに, 参照点を求めることができなかった場合には,Simplex 法を用いて等式制約関数の 2 乗和を最小化することにより参照点を求める処理を追加して実験を行った.
ようにやや緩い制約 $\epsilon=10^{-3}$ に設定した.

(13)$\epsilon>0$$\sum_{j}h\mathrm{j}(oe)^{2}$

ただし, ある程度の最適化を行える34$\ovalbox{\tt\small REJECT} 1$$G_{1}(x)= \sum_{i=1}^{4}$subject toxi–5$\sum_{*=1}^{4}.x^{2}.\cdot-\sum_{i=5}^{13}x_{i}$$2(x_{1}+x_{2})+x_{1}0+x_{11}\leq 10$$-8x_{1}+x_{1}0\leq 0$,,:Michalewicz)$\sigma$$\overline{\tau}z$}$\backslash \ovalbox{\tt\small REJECT}_{\Gamma \mathrm{J}}\ovalbox{\tt\small REJECT} \mathrm{H}$,$2(x_{1}+x\mathrm{a})+x_{10}+x_{12}\leq 10,2(x_{2}+x_{3})+x_{11}+x_{12}\leq 10$$-8x2+x_{11}\leq 0$ ,$-8x\mathrm{s}+x_{12}\leq 0$,$-2x_{4}-x_{5}+x_{1}0\leq 0$,,$-2x_{6}-x_{7}+x_{11}\leq 0$$-2x_{8}-x_{9}+x_{12}\leq 0$ ,$i=1,$$0\leq x_{i}\leq 1,$$G_{2}(x)=x_{1}+x_{2}+x_{3}$$\ldots,$$9,0\leq x_{i}\leq 100,$ $i=10,11,12,0\leq x_{13}\leq 1$

,

.

,

subject to$1-0.0025(x_{4}+xe)\geq 0$ ,$1-0.0025(x_{5}+x\tau-x_{4})\geq 0$,$x_{1}x_{6}-833.33252x_{4}-100x_{1}+83333.333\geq 0,$$x_{3}x\mathrm{s}-1250000-xsx_{5}+2500x_{5}\geq 0$$100\leq x_{1}\leq 10000$,$1-0.01(x_{8}-x_{5})\geq 0$ ,$x_{2}x_{7}-1250x\mathrm{s}-x_{2}x_{4}+1250x_{4}\geq 0$,$1000\leq X:\leq 10000$ , $i=2,3$ ,$10\leq X:\leq 1000$, $i=4,$$\cdots,$

$8$

,

.

$G_{3}(x)=(x_{1}-10)^{2}+5(x_{2}-12)^{2}+x_{3}^{4}+3(x_{4}-11)^{2}+10x_{5}^{6}+7x_{6}^{2}+x_{7}^{4}-4x_{6}x_{7}-10x_{6}-8x\tau$subject to$127-2x_{1}^{2}-3x_{2}^{4}-x_{3}-4x_{4}^{2}-5x_{5}\geq 0$,$196-23x_{1}-x_{2}^{2}-6x_{6}^{2}+8x_{7}\geq 0$$-10\leq x:\leq 10,\dot{\iota}=1,$ $\ldots,$ $7$$G_{4}(x)=\mathrm{e}^{\mathrm{r}_{1}x_{2}x_{3}x_{4}x_{5}}$

.

,

,

,
,

$282-7x_{1}-3x_{2}-10x_{3}^{2}-x_{4}+x_{5}\geq 0$$-4x_{1}^{2}-x_{2}^{2}+3x_{1}x_{2}-2x_{3}^{2}-5x_{6}+11x_{7}\geq 0$,

subject to$x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}+x_{5}^{2}=10,$$-2.3\leq x:\leq 2.3,$ $i=1,2$,$x_{2}x\mathrm{a}-5x_{4}x_{5}=0,$$-3.2\leq x\mathrm{i}\leq 3.2,$$x_{1}^{3}+x_{2}^{3}=-1$$i=3,4,5$ .

,$G_{5}(x)=x_{1}^{2}+x_{2}^{2}+x_{1}x_{2}-14x_{1}-16x_{2}+(x_{3}-10)^{2}+4(x_{4}-5)^{2}+(x_{5}-3)^{2}+2(x_{6}-1)^{2}+5x_{7}^{2}$$+7(x_{8}-11)^{2}+2(x_{9}-10)^{2}+(x_{10}-7)^{2}+45$

subject to$105-4x_{1}-5x_{2}+3x_{7}-9x_{8}\geq 0$ , $-10x_{1}+8x_{2}+17x_{7}-2x\epsilon\geq 0,8x_{1}-2x_{2}-5x_{9}+2x_{1}0+12\geq 0$ ,$-3(x_{1}-2)^{2}-4(x_{2}-3)^{2}-2x_{3}^{2}+7x_{4}+120\geq 0$$-5x_{1}^{2}-8x_{2}-(x_{3}-6)^{2}+2x_{4}+40\geq 0$ ,,$-x_{1}^{2}-2(x_{2}-2)^{2}+2x_{1}x_{2}-14x_{5}+6x_{6}\geq 0$$3x_{1}-6x_{2}-12(x_{9}-8)^{2}+7x_{1}0\geq 0$$-10\leq X:\leq 10,$ $i=1,$ $\ldots,$ $10$.

,

も全ての問題について標準設定を用いた.

,$-0.5(x_{1}-8)^{2}-2(x_{2}-4)^{2}-3x_{6}^{2}+x6+30\geq 0$ ,制約法に関するパラメータにつぃては, 制約満足度の結合演算を $\min$ 演算, 制約満足度のパラメータを $b_{i}=b_{j}=10000$ とした. 遺伝的アルゴリズムに関するパラメータについては, 個体集団サイズ $N=70$ , 最大世代数 $T=5000$ , 交叉率$\beta_{c}=1.0$ , 最大
期待値 $\eta^{+}=2.0$ , 境界突然変異率 $P_{b}=0.3/n$ , ガウス突然変異 $P_{G}=0.3/n,$ $\beta_{G}=0.01$ とした. ただし,$\alpha \mathrm{G}\mathrm{A}$$\alpha$$P_{\mathrm{c}}=0.3,$$n$は遺伝子長 (決定変数の数) であり, 問題によらず一個体あたりの確率を–定にするために, 交叉率およびに反比例させた.

各突然変異率を$n$

等式制約を含む(3) を使用し,$\alpha$$G_{4}$

については,

GENOCOP50 では式 (詔) を使用したが,$\alpha \mathrm{G}\mathrm{A}$では制約満足度に式レベルの制御を行った.

Michalewicz の研究では, 10 回の試行を行っているが, 10 回程度では偶然良い結果が連続することもあったので,より厳密な評価を行うために, 本論文では 100 回の試行を行った.

35
52

実験結果

問題 $G_{1}\sim G_{5}$ に対する実験結果を表 2 に示す. ただし, Optimal は各問題の最適値, best, average,
worst, はそれぞれ 100 回の試行における最良値, 平均値, 最悪値, 標準偏差であり, CPU ?ま実行 胸 間で$\sigma$ある.

最良値については, 全ての場合について

能最良解を得ている.

$G_{4}$

については,$\alpha \mathrm{G}\mathrm{A}$の方が, 優れており,$G_{1}\sim G_{3},$$G_{5}$

両手法とも実行可能最良解を得られなかった.

につ$\alpha \mathrm{G}\mathrm{A}$の結果では, 最良値の場合で $10^{-12}$ , 最悪値の場合で $10^{-10}$ , 平均値の場合で条件からの逸脱に止まっており,

て (ま,

実行可

$\mathrm{G}\mathrm{E}\mathrm{N}\mathrm{O}\mathrm{C}\mathrm{O}\mathrm{P}5.0$

制約条件を緩和したため, 得られた解は制約条件を $10^{-3}$ 程度逸脱しいる. それに比して,による$\mathrm{A}^{\mathrm{a}}$$\alpha$レーくノレの制御$10^{-11}$程度の卿」約

GENOCOP50 に比べて十分に実行可能解に近似した解 “得られてさらに, 平均値と最悪値ついても, 全ての問題について$\alpha \mathrm{G}\mathrm{A}$の方が優れている.

した力 って,で’ ま$\grave{\grave{\backslash }}$$\alpha \mathrm{G}\mathrm{A}$$\mathrm{A}\mathrm{a}$

る.

の方力

GENOCOP50 に比べて, 探索精度の高い最適化アルゴリズムであると考えられる.
また, 標準偏差が全ての問題について$\alpha \mathrm{G}\mathrm{A}$の方が小さいことから, 安定した探索を行う最適化$-r\mathrm{K}$

レゴ

リズムであると考えられる.
さらに, 実行時間についても全ての問題で$\alpha \mathrm{G}\mathrm{A}$の方が GENOCOP50 に比べて 3 倍以上速く, 高速な最適化アルゴリズムであると考えられる.
表 2: 実験結果

表 3 に各問題の上下限制約領域に対する実行可能領域の割合 $\rho=|F\cap S|/|S|$ を示した [11].
ると, 実行可能領域が比較的広い問題である

厳しい問題である$G_{4},$$G_{5}$

においてはについては GENOCOP50 もある程度の解を得て 4 る力\leq ,I ま実 可能領の方が圧倒的に優れている. このように,$G_{3}$$\alpha \mathrm{G}\mathrm{A}$$\alpha \mathrm{G}\mathrm{A}$

これ\sim こよ$\acute{\mathrm{f}}\overline{\mathrm{T}}$

域が厳しい場合においても精度の高い結果を得ることのできる方法である.
表 3: 実行可能領域の占有率 $\rho=|F\cap S|/|S|$6

むすひを提案した. 様々なタイプの 5 種類の制約付き最適 (ヒ力\leq 精度のを適用し, 全ての問題で最適値に近い解が得られることを実験}こより確認し,遺伝的アルゴリズムに$\alpha$

制約法を適用した$\alpha \mathrm{G}\mathrm{A}$$\alpha \mathrm{G}\mathrm{A}$

問題に$\alpha \mathrm{G}\mathrm{A}$

高い安定したアルゴリズムであることを示した.

さらに,制約付き最適化問題を遺伝的アノレゴリズムを |J37[14] 高濱徹行, 阪井節子 制約付き非線形最適化手法 制約法によるファジー制御ルールの最適化, 電子情(1999).
, No. 5,
報通信学会論文誌, Vol.
$\alpha$$\ovalbox{\tt\small REJECT}$$\mathrm{J}82-\mathrm{A}$$\mathrm{P}\mathrm{P}\cdot 658\ovalbox{\tt\small REJECT} 68$

制約 Simplex 法によるファジー制御ルールの学習, 電子情報通信学会論文誌,[15] 高濱徹行, 阪井節子:
Vol. J83-D-I, No. 7, pp. 770-779(2000).
$\alpha$[16] 高濱徹行, 阪井節子: 制約遺伝的アルゴリズムによる制約付き最適化, 第 62 回情報処理学会全国大会
講演論文集, 沙 2, pp. 111-112(2001).
$\alpha$[17] Powell, M.: An Efficient Method for Finding the Minimum of aFunction of Several Variables without
Calculating Derivatives, Computer J., Vol. 7, pp. 155-162 (1964).
[18] Nelder, J. and Mead, R.: ASimplex Method for Function Minimization, J. Computer, Vol. 7,308-313 (1965).

$\mathrm{P}\mathrm{P}$.

[19] Koziel, S. and Michalewicz, Z.: ADecoder-based Evolutionary Algorithm for Constrained Parameter
Optimization Problems, Proc. of the 5th Pamllel Pmblem Solving fvom Nature, Lecture Notes in
Computer Science, Vol. 1498, Amsterdam, PP. 231-240 (1998).
[20] Koziel, S. and Michalewicz, Z.: Evolutionary Algorithms, Homomorphous Mappings, and Constrained Parameter Optimization, Evolutionary Computation, Vol. 7, No. 1, pp. 19-44 (1999).

[21] Baker, J.: Adaptive selection methods for genetic algorithms, Proc. of the First International Conference on Genetic Algorithms and Their Applications, Hillsdale, , Lawrence Erlbaum Associates,$\mathrm{N}\mathrm{J}$PP. 101-111 (1985).

[22] Bik, T. and Hoflieister, F.: Extended selection mechanisms in genetic algorithms, Proc. of the
Fourth International Conference on Genetic Algorithms, San Mateo, Morgan Kaufinann, pp. 92-99(1991).