混合整数ga最適化

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

混合整数`ga`最適化

混合整数最適化問題を解く

ga は、特定の変数が整数値である場合に問題を解決できます。整数である x 要素のベクトル intcon を指定します。

[x,fval,exitflag] = ga(fitnessfcn,nvars,A,b,[],[],...
    lb,ub,nonlcon,intcon,options)

intcon は、整数値の x コンポーネントを含む正の整数のベクトルです。たとえば、x(2) と x(10) を整数に制限する場合は、intcon を [2,10] に設定します。

surrogateopt ソルバーは整数制約も受け入れます。

メモ

ga が整数変数で解決できる問題の種類には制限があります。特に、ga は整数変数がある場合には非線形等式制約を受け入れません。詳細は、整数GAソルバーの特徴を参照してください。

ヒント

ga は、すべての x コンポーネントに下限と上限を指定すると、整数問題を最もよく解決します。

ラストリジン関数の混合整数最適化

ライブスクリプトを開く

この例では、x の最初のコンポーネントが整数になるように制限された Rastrigin 関数の最小値を見つける方法を示します。x の成分はさらに $5 π \leq x (1) \leq 20 π, - 20 π \leq x (2) \leq - 4 π$ の領域に制限されます。

問題の範囲を設定する

lb = [5*pi,-20*pi];
ub = [20*pi,-4*pi];

プロット関数を設定して、ゲームの進行状況を表示できるようにします。

opts = optimoptions('ga','PlotFcn',@gaplotbestf);

x(1)が整数値を持つGAソルバーを呼び出す

rng(1,'twister') % for reproducibility
intcon = 1;
[x,fval,exitflag] = ga(@rastriginsfcn,2,[],[],[],[],...
    lb,ub,[],intcon,opts)

Figure Genetic Algorithm contains an axes object. The axes object with title Best: 424.136 Mean: 614.506, xlabel Generation, ylabel Penalty value contains 2 objects of type scatter. These objects represent Best penalty value, Mean penalty value.

ga stopped because the average change in the penalty function value is less than options.FunctionTolerance and 
the constraint violation is less than options.ConstraintTolerance.

x = 1×2

   16.0000  -12.9325

fval = 
424.1355

exitflag = 
1

ga はすぐに解に収束します。

整数GAソルバーの特徴

整数制約を含めると、ga が解決できる問題の種類にはいくつかの制限があります。

非線形等式制約はありません。非線形制約関数は、非線形等式制約に対して [] を返す必要があります。回避策については、「非線形等式制約付き整数計画法」を参照してください。
母集団タイプは doubleVector のみです。
ハイブリッド関数はありません。ga は HybridFcn オプションの設定を上書きします。
ga は ParetoFraction、DistanceMeasureFcn、InitialPenalty、および PenaltyFactor オプションを無視します。

記載されている制限は主に自然なものであり、恣意的なものではありません。たとえば、ハイブリッド関数は整数制約をサポートしません。したがって、ga は整数制約がある場合にはハイブリッド関数を使用しません。

非線形等式制約付き整数計画法

ライブスクリプトを開く

この例では、次の制約条件のもとで、5 次元における Ackley 関数 (この例を実行すると含まれる) の最小値を見つけようとします。

x(1)、x(3)、x(5) は整数です。
norm(x) = 4.

ga ソルバーは非線形等式制約をサポートしておらず、非線形不等式制約のみをサポートしています。この例では、いくつかの問題に適用される回避策を示していますが、動作することは保証されていません。

Ackley 関数を最小化することは困難です。整数制約と等式制約を追加すると難易度が増します。

非線形等式制約を含めるには、x のノルムが 4 の tol 以内になるように小さな許容値 tol を指定します。許容差がないと、非線形等式制約は決して満たされず、ソルバーは実行可能解に到達しません。

式 norm(x) = 4 を 2 つの「ゼロより小さい」不等式として書きます。

$‖ x - 4 ‖ \leq 0$

$- ‖ x - 4 ‖ \leq 0$ .

不等式には若干の許容範囲を許容します。

$‖ x - 4 ‖ - t o l \leq 0$

$- ‖ x - 4 ‖ - t o l \leq 0$ .

これらの不等式を実装する非線形不等式制約関数 eqCon を記述します。

type eqCon

function [c, ceq] = eqCon(x)

ceq = [];
rad = 4;
tol = 1e-3;
confcnval = norm(x) - rad;
c = [confcnval - tol;-confcnval - tol];

次のオプションを設定します。

MaxStallGenerations = 50 — ソルバーがしばらく試行できるようにします。
FunctionTolerance = 1e-10 — 通常よりも厳しい停止基準を指定します。
MaxGenerations = 500 — デフォルトよりも多くの世代を許可します。
PlotFcn = @gaplotbestfun — 最適化を観察します。

opts = optimoptions('ga','MaxStallGenerations',50,'FunctionTolerance',1e-10,...
    'MaxGenerations',500,'PlotFcn',@gaplotbestfun);

ソルバーを支援するために下限と上限を設定します。

nVar = 5;
lb = -5*ones(1,nVar);
ub = 5*ones(1,nVar);

問題を解きます。

rng(0,'twister') % for reproducibility
[x,fval,exitflag] = ga(@ackleyfcn,nVar,[],[],[],[], ...
    lb,ub,@eqCon,[1 3 5],opts);

Figure Genetic Algorithm contains an axes object. The axes object with title Best Fitness: 5.96763, xlabel Generation, ylabel Penalty value contains an object of type scatter.

ga stopped because the average change in the penalty function value is less than options.FunctionTolerance and 
the constraint violation is less than options.ConstraintTolerance.

解を検証します。

x,fval,exitflag,norm(x)

x = 1×5

         0    0.9706    1.0000    3.6158   -1.0000

fval = 
5.9676

exitflag = 
1

ans = 
4.0020

奇数の x 成分は指定どおり整数です。x のノルムは 4 で、指定された相対許容誤差 1e-3 以内です。

終了フラグが肯定的であるにもかかわらず、ソリューションはグローバル最適ではありません。より大きな母集団で問題を再度実行し、解を調べます。

opts = optimoptions(opts,'Display','off','PopulationSize',400);
[x2,fval2,exitflag2] = ga(@ackleyfcn,nVar,[],[],[],[], ...
    lb,ub,@eqCon,[1 3 5],opts);

Figure Genetic Algorithm contains an axes object. The axes object with title Best Fitness: 4.23849, xlabel Generation, ylabel Penalty value contains an object of type scatter.

2 番目の解決策を調べます。

x2,fval2,exitflag2,norm(x2)

x2 = 1×5

   -1.0000    2.0082   -1.0000   -2.9954    1.0000

fval2 = 
4.2385

exitflag2 = 
1

ans = 
4.0006

2 回目の実行では、より良いソリューション (適応度関数の値が低い) が得られます。繰り返しますが、奇数の x 成分は整数であり、x2 のノルムは 4 で、指定された相対許容誤差 1e-3 以内になります。

この手順は失敗する可能性があることに注意してください。ga は整数と非線形の等式制約を同時に満たすのが困難です。

有効整数 `ga`

整数問題で ga を最も効果的に使用するには、次のガイドラインに従ってください。

各コンポーネントをできる限りしっかりと結合します。この方法により、ga の探索スペースが最小になり、ga が最も効率的に探索できるようになります。
コンポーネントを境界付けできない場合は、適切な初期範囲を指定します。デフォルトでは、ga は各コンポーネントの範囲[-1e4,1e4] を持つ初期母集団を作成します。デフォルト値が不適切な場合、初期範囲を小さくしたり大きくしたりすると、より良い結果が得られます。初期範囲を変更するには、InitialPopulationRange オプションを使用します。
変数が 10 個を超える場合は、PopulationSize オプションを使用して、デフォルトよりも大きい母集団サイズを設定します。変数が 6 個以上の場合、デフォルト値は 200 です。母集団規模が大きい場合:
- ga は収束するまでに長い時間がかかることがあります。最大世代数に達した場合 (終了フラグ 0)、MaxGenerations オプションの値を増やします。
- 突然変異率を下げます。これを行うには、CrossoverFraction オプションの値をデフォルトの 0.8 から 0.9 以上に増やします。
- EliteCount オプションの値をデフォルトの 0.05*PopulationSize から 0.1*PopulationSize 以上に増やします。

オプションの詳細については、ga options 入力引数を参照してください。

整数`ga`アルゴリズム

ga を使用した整数計画法では、基本アルゴリズムにいくつかの変更が加えられます (遺伝的アルゴリズムの仕組みを参照)。整数計画法の場合:

デフォルトでは、特殊な作成、交叉、および突然変異関数により、変数は整数になります。詳細については、Deep et al. [2] を参照してください。
デフォルト以外の作成関数、交叉関数、または突然変異関数を使用する場合、ga は各反復で線形実現可能性と整数制約に関する実現可能性を強制します。
遺伝的アルゴリズムは、適応度関数ではなく、ペナルティ関数を最小化しようとします。ペナルティ関数には実行不可能性の項が含まれます。このペナルティ関数は、デフォルトでバイナリトーナメント選択と組み合わされ、後続の世代の個体を選択します。母集団のメンバーのペナルティ関数の値は次のとおりです。
- メンバーが実行可能である場合、ペナルティ関数は適応度関数になります。
- メンバーが実行不可能な場合、ペナルティ関数は、母集団の実行可能なメンバー間の最大適応度関数と、（実行不可能な）ポイントの制約違反の合計になります。
ペナルティ関数の詳細については、Deb [1] を参照してください。

参照

[1] Deb, Kalyanmoy. An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 186(2–4), pp. 311–338, 2000.

[2] Deep, Kusum, Krishna Pratap Singh, M.L. Kansal, and C. Mohan. A real coded genetic algorithm for solving integer and mixed integer optimization problems. Applied Mathematics and Computation, 212(2), pp. 505–518, 2009.