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

混合整数 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\pi \le x(1)\le 20\pi ,-20\pi \le x(2)\le -4\pi$$ の領域内に制限されます。

問題の範囲を設定する

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)

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 つの「ゼロ未満」の不等式として書きます。

$$\Vert x-4\Vert \le 0$$

$$-\Vert x-4\Vert \le 0$$.

不等式には小さな許容範囲を許容します。

$$\Vert x-4\Vert -tol\le 0$$

$$-\Vert x-4\Vert -tol\le 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);

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);

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.

関連するトピック

• 遺伝的アルゴリズムを使用して混合整数エンジニアリング設計問題を解く
• 混合整数代理最適化
• 整数および非線形制約を持つ非線形問題を解く