メインコンテンツ

このページは機械翻訳を使用して翻訳されました。最新版の英語を参照するには、ここをクリックします。

遺伝的アルゴリズムを用いた制約付き最小化

この例では、遺伝的アルゴリズムを使用して、非線形不等式制約と境界に従う目的関数を最小化する方法を示します。

制約付き最小化問題

この問題では、最小化する目的関数は 2 次元変数 x の単純な関数です。

simple_objective(x) = (4 - 2.1*x(1)^2 + x(1)^4/3)*x(1)^2 + x(1)*x(2) + (-4 + 4*x(2)^2)*x(2)^2;

この機能は、L.C.W. Dixon と G.P. Szego [1] で説明されているように、「カム」として知られています。

さらに、この問題には非線形の制約と境界があります。

   x(1)*x(2) + x(1) - x(2) + 1.5 <= 0  (nonlinear constraint)
   10 - x(1)*x(2) <= 0                 (nonlinear constraint)
   0 <= x(1) <= 1                      (bound)
   0 <= x(2) <= 13                     (bound)

適応度関数をコード化する

次のコードを含む simple_objective.m という名前の MATLAB ファイルを作成します。

type simple_objective
function y = simple_objective(x)
%SIMPLE_OBJECTIVE Objective function for PATTERNSEARCH solver

%   Copyright 2004 The MathWorks, Inc.  

x1 = x(1);
x2 = x(2);
y = (4-2.1.*x1.^2+x1.^4./3).*x1.^2+x1.*x2+(-4+4.*x2.^2).*x2.^2;

ga などのソルバーは単一の入力 x を受け入れます。ここで、x には問題内の変数の数と同じ数の要素があります。目的関数は目的関数のスカラー値を計算し、それを単一の出力引数 y で返します。

制約関数をコーディングする

次のコードを含む simple_constraint.m という名前の MATLAB ファイルを作成します。

type simple_constraint
function [c, ceq] = simple_constraint(x)
%SIMPLE_CONSTRAINT Nonlinear inequality constraints.

%   Copyright 2005-2007 The MathWorks, Inc.

c = [1.5 + x(1)*x(2) + x(1) - x(2); 
     -x(1)*x(2) + 10];

% No nonlinear equality constraints:
ceq = [];

制約関数は、すべての不等式制約と等式制約の値を計算し、それぞれベクトル cceq を返します。c の値は、ソルバーがゼロ以下にしようとする非線形不等式制約を表します。ceq の値は、ソルバーがゼロに等しくしようとする非線形等式制約を表します。この例には非線形等式制約がないため、ceq = [] となります。詳細は、非線形制約を参照してください。

ga を使用した最小化

目的関数を関数ハンドルとして指定します。

ObjectiveFunction = @simple_objective;

問題の範囲を指定します。

lb = [0 0];   % Lower bounds
ub = [1 13];  % Upper bounds

非線形制約関数を関数ハンドルとして指定します。

ConstraintFunction = @simple_constraint;

問題変数の数を指定します。

nvars = 2;

最適点 x と最適点 fval における関数値を要求して、ソルバーを呼び出します。

rng default % For reproducibility
[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],lb,ub,ConstraintFunction)
Optimization finished: average change in the fitness value less than options.FunctionTolerance and constraint violation is less than options.ConstraintTolerance.
x = 1×2

    0.8122   12.3103

fval = 
9.1268e+04

視覚化を追加する

ソルバーの進行状況を観察するには、2 つのプロット関数を選択するオプションを指定します。プロット関数 gaplotbestf は、各反復における最適な目的関数の値をプロットし、プロット関数 gaplotmaxconstr は、各反復における最大制約違反をプロットします。これら 2 つのプロット関数をセル配列に設定します。また、Display オプションを 'iter' に設定して、コマンド ウィンドウにソルバーの進行状況に関する情報を表示します。

options = optimoptions("ga",'PlotFcn',{@gaplotbestf,@gaplotmaxconstr}, ...
    'Display','iter');

options 引数を含めてソルバーを実行します。

[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],lb,ub, ...
    ConstraintFunction,options)
Single objective optimization:
2 Variables
2 Nonlinear inequality constraints

Options:
CreationFcn:       @gacreationuniform
CrossoverFcn:      @crossoverscattered
SelectionFcn:      @selectionstochunif
MutationFcn:       @mutationadaptfeasible

                              Best       Max        Stall
Generation  Func-count        f(x)     Constraint  Generations
    1           2524       91986.8    7.796e-09      0
    2           4986       94678.2            0      0
    3          10362       96473.7            0      0
    4          16243       91270.1    0.0009897      0
Optimization finished: average change in the fitness value less than options.FunctionTolerance and constraint violation is less than options.ConstraintTolerance.

Figure Genetic Algorithm contains 2 axes objects. Axes object 1 with title Best: 91270.1 Mean: 91270.4, xlabel Generation, ylabel Fitness value contains 2 objects of type scatter. These objects represent Best fitness, Mean fitness. Axes object 2 with title Maximum Constraint Violation: 0.000989671, xlabel Generation, ylabel Constraint violation contains an object of type scatter.

x = 1×2

    0.8123   12.3104

fval = 
9.1270e+04

反復表示では、ga は問題の種類と、作成、交叉、突然変異、選択演算子に関する詳細を提供します。

非線形制約により、ga は各反復で多くのサブ問題を解決します。プロットと反復表示の両方に示されているように、解決プロセスには反復がほとんどありません。ただし、反復表示の Func-count 列には、反復ごとに多数の関数評価が表示されます。

ga ソルバーは、線形制約と境界を非線形制約とは異なる方法で処理します。最適化全体を通じて、すべての線形制約と境界が満たされます。ただし、ga は、すべての世代ですべての非線形制約を満たすとは限りません。ga が解に収束する場合、その解において非線形制約が満たされます。

ga は突然変異と交叉関数を使用して、世代ごとに新しい個体を生成します。ga が線形制約と境界制約を満たす方法は、実行可能なポイントのみを生成する突然変異と交叉関数を使用することです。たとえば、前の ga の呼び出しでは、デフォルトの突然変異関数 (制約のない問題の場合) mutationgaussian は線形制約を満たさないため、ga は代わりにデフォルトで mutationadaptfeasible 関数を使用します。カスタム突然変異関数を提供する場合、このカスタム関数は線形制約と境界制約に関して実行可能なポイントのみを生成する必要があります。ツールボックス内のすべての交叉関数は、線形制約と境界を満たすポイントを生成します。

ただし、問題に整数制約が含まれている場合、ga はすべての反復が境界と線形制約を満たすことを強制します。この実現可能性は、小さな許容範囲内で、すべての突然変異、交叉、および作成演算子に対して発生します。

開始点を指定する

ソルバーの速度を上げるには、InitialPopulationMatrix オプションで初期母集団を指定できます。ga は初期母集団を使用して最適化を開始します。各行が 1 つの開始点を表す行ベクトルまたは行列を指定します。

X0 = [0.8 12.5]; % Start point (row vector)
options.InitialPopulationMatrix = X0;
[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],lb,ub, ...
    ConstraintFunction,options)
Single objective optimization:
2 Variables
2 Nonlinear inequality constraints

Options:
CreationFcn:       @gacreationuniform
CrossoverFcn:      @crossoverscattered
SelectionFcn:      @selectionstochunif
MutationFcn:       @mutationadaptfeasible

                              Best       Max        Stall
Generation  Func-count        f(x)     Constraint  Generations
    1           2500       91769.6            0      0
    2           4962       97536.4            0      0
    3           7412       91268.4      0.00098      0
    4           9862       91268.1    0.0009893      0
    5          12312       91267.9    0.0009943      0
Optimization finished: average change in the fitness value less than options.FunctionTolerance and constraint violation is less than options.ConstraintTolerance.

Figure Genetic Algorithm contains 2 axes objects. Axes object 1 with title Best: 91267.9 Mean: 91269, xlabel Generation, ylabel Fitness value contains 2 objects of type scatter. These objects represent Best fitness, Mean fitness. Axes object 2 with title Maximum Constraint Violation: 0.000994263, xlabel Generation, ylabel Constraint violation contains an object of type scatter.

x = 1×2

    0.8122   12.3103

fval = 
9.1268e+04

この場合、開始点を指定しても、ソルバーの進行状況は大きく変わりません。

参考文献

[1] Dixon, L. C. W., and G .P. Szego (eds.).Towards Global Optimisation 2.North-Holland:Elsevier Science Ltd., Amsterdam, 1978.

参考

トピック