Main Content

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

遺伝的アルゴリズムを使用したカスタム データ型の最適化

この例では、遺伝的アルゴリズムを使用してカスタム データ型を使用する関数を最小化する方法を示します。遺伝的アルゴリズムは巡回セールスマン問題を解決するためにカスタマイズされています。

巡回セールスマン問題

巡回セールスマン問題とは、都市の数が有限で、各都市間の移動コストがわかっている場合の最適化問題です。目標は、コストが最小になるようにセールスマンが訪問するすべての都市の順序付きセットを見つけることです。巡回セールスマン問題を解決するには、都市の位置と各都市間の距離またはコストのリストが必要です。

私たちの営業マンはアメリカの都市を訪問しています。ファイル usborder.mat には、変数 xy に米国の地図が含まれており、変数 xxyy には同じ地図の幾何学的に簡略化されたバージョンが含まれています。

load('usborder.mat','x','y','xx','yy');
plot(x,y,'Color','red'); hold on;

アメリカ合衆国の国境内にある都市の位置をランダムに生成します。inpolygon 関数を使用すると、すべての都市が米国の境界内にあるか、または境界に非常に近いことを確認できます。

cities = 40;
locations = zeros(cities,2);
n = 1;
while (n <= cities)
    xp = rand*1.5;
    yp = rand;
    if inpolygon(xp,yp,xx,yy)
        locations(n,1) = xp;
        locations(n,2) = yp;
        n = n+1;
    end
end
plot(locations(:,1),locations(:,2),'bo');

青い円は、営業担当者が商品を配達または受け取るために出向く必要がある都市の位置を表しています。都市の場所のリストが与えられれば、すべての都市の距離行列を計算できます。

distances = zeros(cities);
for count1=1:cities,
    for count2=1:count1,
        x1 = locations(count1,1);
        y1 = locations(count1,2);
        x2 = locations(count2,1);
        y2 = locations(count2,2);
        distances(count1,count2)=sqrt((x1-x2)^2+(y1-y2)^2);
        distances(count2,count1)=distances(count1,count2);
    end;
end;

カスタム データ型の遺伝的アルゴリズムのカスタマイズ

デフォルトでは、遺伝的アルゴリズム ソルバーは、double およびバイナリ文字列データ型に基づいて最適化問題を解決します。作成、交差、突然変異の関数では、集団が double 型の行列、またはバイナリ文字列の場合は論理型の行列であると想定されます。遺伝的アルゴリズム ソルバーは、任意のデータ型を含む最適化問題にも適用できます。母集団には任意のデータ構造を使用できます。たとえば、カスタム データ型は MATLAB® セル配列を使用して指定できます。ga をセル配列型の集団で使用するには、セル配列などのデータ型で機能する作成関数、交差関数、および突然変異関数を提供する必要があります。

巡回セールスマン問題に必要な関数

このセクションでは、必要な 3 つの関数を作成して登録する方法を示します。巡回セールスマン問題の母集団内の個体は順序付けられた集合であるため、母集団はセル配列を使用して簡単に表現できます。巡回セールスマン問題のカスタム作成関数は、P などのセル配列を作成します。各要素は、順列ベクトルとして順序付けられた都市のセットを表します。つまり、セールスマンは P{i} で指定された順序で移動することになります。作成関数は、サイズ PopulationSize のセル配列を返します。

type create_permutations.m
function pop = create_permutations(NVARS,FitnessFcn,options)
%CREATE_PERMUTATIONS Creates a population of permutations.
%   POP = CREATE_PERMUTATION(NVARS,FITNESSFCN,OPTIONS) creates a population
%  of permutations POP each with a length of NVARS. 
%
%   The arguments to the function are 
%     NVARS: Number of variables 
%     FITNESSFCN: Fitness function 
%     OPTIONS: Options structure used by the GA

%   Copyright 2004-2007 The MathWorks, Inc.

totalPopulationSize = sum(options.PopulationSize);
n = NVARS;
pop = cell(totalPopulationSize,1);
for i = 1:totalPopulationSize
    pop{i} = randperm(n); 
end

カスタム交差関数は、セル配列 (母集団) を受け取り、交差の結果生じた子であるセル配列を返します。

type crossover_permutation.m
function xoverKids  = crossover_permutation(parents,options,NVARS, ...
    FitnessFcn,thisScore,thisPopulation)
%   CROSSOVER_PERMUTATION Custom crossover function for traveling salesman.
%   XOVERKIDS = CROSSOVER_PERMUTATION(PARENTS,OPTIONS,NVARS, ...
%   FITNESSFCN,THISSCORE,THISPOPULATION) crossovers PARENTS to produce
%   the children XOVERKIDS.
%
%   The arguments to the function are 
%     PARENTS: Parents chosen by the selection function
%     OPTIONS: Options created from OPTIMOPTIONS
%     NVARS: Number of variables 
%     FITNESSFCN: Fitness function 
%     STATE: State structure used by the GA solver 
%     THISSCORE: Vector of scores of the current population 
%     THISPOPULATION: Matrix of individuals in the current population

%   Copyright 2004-2015 The MathWorks, Inc. 

nKids = length(parents)/2;
xoverKids = cell(nKids,1); % Normally zeros(nKids,NVARS);
index = 1;

for i=1:nKids
    % here is where the special knowledge that the population is a cell
    % array is used. Normally, this would be thisPopulation(parents(index),:);
    parent = thisPopulation{parents(index)};
    index = index + 2;

    % Flip a section of parent1.
    p1 = ceil((length(parent) -1) * rand);
    p2 = p1 + ceil((length(parent) - p1- 1) * rand);
    child = parent;
    child(p1:p2) = fliplr(child(p1:p2));
    xoverKids{i} = child; % Normally, xoverKids(i,:);
end

カスタム変異関数は、都市の順序付けられたセットである個体を受け取り、変異された順序付けられたセットを返します。

type mutate_permutation.m
function mutationChildren = mutate_permutation(parents ,options,NVARS, ...
    FitnessFcn, state, thisScore,thisPopulation,mutationRate)
%   MUTATE_PERMUTATION Custom mutation function for traveling salesman.
%   MUTATIONCHILDREN = MUTATE_PERMUTATION(PARENTS,OPTIONS,NVARS, ...
%   FITNESSFCN,STATE,THISSCORE,THISPOPULATION,MUTATIONRATE) mutate the
%   PARENTS to produce mutated children MUTATIONCHILDREN.
%
%   The arguments to the function are 
%     PARENTS: Parents chosen by the selection function
%     OPTIONS: Options created from OPTIMOPTIONS
%     NVARS: Number of variables 
%     FITNESSFCN: Fitness function 
%     STATE: State structure used by the GA solver 
%     THISSCORE: Vector of scores of the current population 
%     THISPOPULATION: Matrix of individuals in the current population
%     MUTATIONRATE: Rate of mutation

%   Copyright 2004-2015 The MathWorks, Inc.

% Here we swap two elements of the permutation
mutationChildren = cell(length(parents),1);% Normally zeros(length(parents),NVARS);
for i=1:length(parents)
    parent = thisPopulation{parents(i)}; % Normally thisPopulation(parents(i),:)
    p = ceil(length(parent) * rand(1,2));
    child = parent;
    child(p(1)) = parent(p(2));
    child(p(2)) = parent(p(1));
    mutationChildren{i} = child; % Normally mutationChildren(i,:)
end

巡回セールスマン問題にも適合関数が必要です。個体の適応度は、順序付けられた都市の集合における移動距離の合計です。適合関数では、合計距離を計算するために距離行列も必要です。

type traveling_salesman_fitness.m
function scores = traveling_salesman_fitness(x,distances)
%TRAVELING_SALESMAN_FITNESS  Custom fitness function for TSP. 
%   SCORES = TRAVELING_SALESMAN_FITNESS(X,DISTANCES) Calculate the fitness 
%   of an individual. The fitness is the total distance traveled for an
%   ordered set of cities in X. DISTANCE(A,B) is the distance from the city
%   A to the city B.

%   Copyright 2004-2007 The MathWorks, Inc.

scores = zeros(size(x,1),1);
for j = 1:size(x,1)
    % here is where the special knowledge that the population is a cell
    % array is used. Normally, this would be pop(j,:);
    p = x{j}; 
    f = distances(p(end),p(1));
    for i = 2:length(p)
        f = f + distances(p(i-1),p(i));
    end
    scores(j) = f;
end

ga は、引数 x のみを使用してフィットネス関数を呼び出しますが、フィットネス関数には xdistances という 2 つの引数があります。匿名関数を使用して、追加の引数である距離行列の値を取得できます。1 つの入力 x を受け取り、x と距離を使用して traveling_salesman_fitness を呼び出す匿名関数への関数ハンドル FitnessFcn を作成します。関数ハンドル FitnessFcn が作成されると、変数 distances に値が設定され、これらの値は匿名関数によってキャプチャされます。

%distances defined earlier
FitnessFcn = @(x) traveling_salesman_fitness(x,distances);

都市の位置と現在の最適ルートをプロットするカスタム プロット関数を追加できます。赤い円は都市を表し、青い線は 2 つの都市間の有効な経路を表します。

type traveling_salesman_plot.m
function state = traveling_salesman_plot(options,state,flag,locations)
%   TRAVELING_SALESMAN_PLOT Custom plot function for traveling salesman.
%   STATE = TRAVELING_SALESMAN_PLOT(OPTIONS,STATE,FLAG,LOCATIONS) Plot city
%   LOCATIONS and connecting route between them. This function is specific
%   to the traveling salesman problem.

%   Copyright 2004-2006 The MathWorks, Inc.
persistent x y xx yy
if strcmpi(flag,'init')
  load('usborder.mat','x','y','xx','yy');
end
plot(x,y,'Color','red');
axis([-0.1 1.5 -0.2 1.2]);

hold on;
[unused,i] = min(state.Score);
genotype = state.Population{i};

plot(locations(:,1),locations(:,2),'bo');
plot(locations(genotype,1),locations(genotype,2));
hold off

ここでも、匿名関数を使用して、追加の引数 locations を指定して traveling_salesman_plot を呼び出す匿名関数への関数ハンドルを作成します。

%locations defined earlier
my_plot = @(options,state,flag) traveling_salesman_plot(options, ...
    state,flag,locations);

遺伝的アルゴリズムのオプション設定

まず、カスタム データ タイプと人口範囲を示すオプション コンテナーを作成します。

options = optimoptions(@ga, 'PopulationType', 'custom','InitialPopulationRange', ...
                            [1;cities]);

作成したカスタム作成、クロスオーバー、突然変異、プロット関数を選択し、いくつかの停止条件を設定します。

options = optimoptions(options,'CreationFcn',@create_permutations, ...
                        'CrossoverFcn',@crossover_permutation, ...
                        'MutationFcn',@mutate_permutation, ...
                        'PlotFcn', my_plot, ...
                        'MaxGenerations',500,'PopulationSize',60, ...
                        'MaxStallGenerations',200,'UseVectorized',true);

最後に、問題情報を使用して遺伝的アルゴリズムを呼び出します。

numberOfVariables = cities;
[x,fval,reason,output] = ...
    ga(FitnessFcn,numberOfVariables,[],[],[],[],[],[],[],options)
ga stopped because it exceeded options.MaxGenerations.

x =

  1x1 cell array

    {[14 12 36 3 5 11 40 25 38 37 7 30 28 10 23 21 27 4 1 ... ] (1x40 double)}


fval =

    5.3846


reason =

     0


output = 

  struct with fields:

      problemtype: 'unconstrained'
         rngstate: [1x1 struct]
      generations: 500
        funccount: 28563
          message: 'ga stopped because it exceeded options.MaxGenerations.'
    maxconstraint: []
       hybridflag: []

この図には、青い円で囲まれた都市の位置と、遺伝的アルゴリズムによって発見されたセールスマンが移動する経路が表示されます。セールスマンはルートのどちらの端からでも出発することができ、最後に出発都市に戻って帰宅することができます。

関連するトピック