Diese Seite wurde mithilfe maschineller Übersetzung übersetzt. Klicken Sie hier, um die neueste Version auf Englisch zu sehen.

Kodierung und Minimierung einer Fitnessfunktion mit dem genetischen Algorithmus

Live Script öffnen

Dieses Beispiel zeigt, wie Sie mithilfe von drei Techniken eine Fitnessfunktion für den genetischen Algorithmus-Solver ga erstellen und minimieren:

  • Basic

  • Einbeziehung zusätzlicher Parameter

  • Vektorisiert für Geschwindigkeit

Grundlegende Fitnessfunktion

Die grundlegende Fitnessfunktion ist die Rosenbrock-Funktion, eine gängige Testfunktion für Optimierer. Die Funktion ist eine Summe von Quadraten:

f(x)=100(x12-x2)2+(1-x1)2.

Die Funktion hat am Punkt [1,1] einen Minimalwert von Null. Da die Rosenbrock-Funktion ziemlich steil ist, zeichnen Sie den Logarithmus von eins plus der Funktion.

fsurf(@(x,y)log(1 + 100*(x.^2 - y).^2 + (1 - x).^2),[0,2])
title('log(1 + 100*(x(1)^2 - x(2))^2 + (1 - x(1))^2)')
view(-13,78)
hold on
h1 = plot3(1,1,0.1,'r*','MarkerSize',12);
legend(h1,'Minimum','Location','best');
hold off

Fitness-Funktionscode

Die Funktionsdatei simple_fitness implementiert die Funktion von Rosenbrock.

type simple_fitness
function y = simple_fitness(x)
%SIMPLE_FITNESS fitness function for GA

%   Copyright 2004 The MathWorks, Inc. 

  y = 100 * (x(1)^2 - x(2)) ^2 + (1 - x(1))^2;

Eine Fitnessfunktion muss einen Input x annehmen, wobei x ein Zeilenvektor mit so vielen Elementen ist wie die Anzahl der Variablen im Problem. Die Fitnessfunktion berechnet den Wert der Funktion und gibt diesen Skalarwert in ihrem einzigen Rückgabeargument y zurück.

Minimieren mit ga

Um die Fitnessfunktion mit ga zu minimieren, übergeben Sie der Fitnessfunktion einen Funktionshandle sowie die Anzahl der Variablen im Problem. Damit ga die relevante Region untersucht, schließen Sie die Grenzen -3 <= x(i) <= 3 ein. Übergeben Sie die Grenzen als fünftes und sechstes Argument nach numberOfVariables. Einzelheiten zur ga-Syntax finden Sie unter ga.

ga ist ein Zufallsalgorithmus. Legen Sie zur Reproduzierbarkeit den Zufallszahlenstrom fest.

rng default % For reproducibility
FitnessFunction = @simple_fitness;
numberOfVariables = 2;
lb = [-3,-3];
ub = [3,3];
[x,fval] = ga(FitnessFunction,numberOfVariables,[],[],[],[],lb,ub)
Optimization terminated: maximum number of generations exceeded.

x = 1×2

    1.5083    2.2781


fval = 0.2594

Der vom Solver zurückgegebene x ist der beste Punkt in der von ga berechneten endgültigen Population. fval ist der Wert der Funktion simple_fitness, ausgewertet am Punkt x. ga hat keine besonders gute Lösung gefunden. Möglichkeiten zur Verbesserung der Lösung finden Sie unter Auswirkungen genetischer Algorithmusoptionen.

Fitnessfunktion mit zusätzlichen Parametern

Manchmal verfügt Ihre Fitnessfunktion über zusätzliche Parameter, die während der Optimierung als Konstanten fungieren. Beispielsweise kann eine verallgemeinerte Rosenbrock-Funktion zusätzliche Parameter haben, die die Konstanten 100 und 1 darstellen:

f(x,a,b)=a(x12-x2)2+(b-x1)2.

a und b sind Parameter der Fitnessfunktion, die während der Optimierung als Konstanten fungieren (sie werden im Rahmen der Minimierung nicht variiert). Die parameterized_fitness.m-Datei implementiert diese parametrisierte Fitnessfunktion.

type parameterized_fitness
function y = parameterized_fitness(x,p1,p2)
%PARAMETERIZED_FITNESS fitness function for GA

%   Copyright 2004 The MathWorks, Inc.        
 
y = p1 * (x(1)^2 - x(2)) ^2 + (p2 - x(1))^2;

Minimieren durch zusätzliche Parameter

Verwenden Sie eine anonyme Funktion, um die Werte der zusätzlichen Argumente zu erfassen, nämlich die Konstanten a und b. Erstellen Sie einen Funktionshandle FitnessFunction für eine anonyme Funktion, die eine Eingabe x entgegennimmt und parameterized_fitness mit x, a und b aufruft. Die anonyme Funktion enthält die Werte von a und b, die beim Erstellen des Funktionshandles vorhanden sind.

a = 100;
b = 1; % define constant values
FitnessFunction = @(x) parameterized_fitness(x,a,b);
[x,fval] = ga(FitnessFunction,numberOfVariables,[],[],[],[],lb,ub)
Optimization terminated: maximum number of generations exceeded.

x = 1×2

    1.3198    1.7434


fval = 0.1025

Siehe Passing Extra Parameters.

Vektorisierte Fitnessfunktion

Um an Geschwindigkeit zu gewinnen, vektorisieren Sie Ihre Fitnessfunktion. Eine vektorisierte Fitnessfunktion berechnet die Fitness einer Sammlung von Punkten auf einmal, was im Allgemeinen Zeit spart, im Vergleich zur individuellen Auswertung dieser Punkte. Um eine vektorisierte Fitnessfunktion zu schreiben, lassen Sie Ihre Funktion eine Matrix akzeptieren, in der jede Matrixzeile einen Punkt darstellt, und lassen Sie die Fitnessfunktion einen Spaltenvektor mit Fitnessfunktionswerten zurückgeben.

So ändern Sie die Funktionsdatei parameterized_fitness in eine vektorisierte Form:

  • Ändern Sie jede Variable x(i) in x(:,i), also den Spaltenvektor der Variablen, der x(i) entspricht.

  • Ändern Sie jede Vektormultiplikation * in .* und jede Potenzierung ^ in .^, um anzuzeigen, dass die Operationen elementweise erfolgen. In diesem Code gibt es keine Vektormultiplikationen, ändern Sie also einfach die Exponenten.

type vectorized_fitness
function y = vectorized_fitness(x,p1,p2)
%VECTORIZED_FITNESS fitness function for GA

%   Copyright 2004-2010 The MathWorks, Inc.  

y = p1 * (x(:,1).^2 - x(:,2)).^2 + (p2 - x(:,1)).^2;

Diese vektorisierte Version der Fitnessfunktion nimmt eine Matrix x mit einer beliebigen Anzahl von Punkten, d. h. und einer beliebigen Anzahl von Zeilen, und gibt einen Spaltenvektor y mit der gleichen Anzahl von Zeilen wie x zurück.

Sagen Sie dem Solver, dass die Fitnessfunktion in der Option 'UseVectorized' vektorisiert ist.

options = optimoptions(@ga,'UseVectorized',true);

Fügen Sie Optionen als letztes Argument für ga ein.

VFitnessFunction = @(x) vectorized_fitness(x,100,1);
[x,fval] = ga(VFitnessFunction,numberOfVariables,[],[],[],[],lb,ub,[],options)
Optimization terminated: maximum number of generations exceeded.

x = 1×2

    1.6219    2.6334


fval = 0.3876

Was ist der Geschwindigkeitsunterschied? Bestimmen Sie die Zeit der Optimierung mit und ohne Vektorisierung.

tic
[x,fval] = ga(VFitnessFunction,numberOfVariables,[],[],[],[],lb,ub,[],options);
Optimization terminated: maximum number of generations exceeded.

v = toc;
tic
[x,fval] = ga(FitnessFunction,numberOfVariables,[],[],[],[],lb,ub);
Optimization terminated: maximum number of generations exceeded.

nv = toc;
fprintf('Using vectorization took %f seconds. No vectorization took %f seconds.\n',v,nv)
Using vectorization took 0.153337 seconds. No vectorization took 0.212880 seconds.

In diesem Fall war die Verbesserung durch die Vektorisierung nicht groß, da die Berechnung der Fitnessfunktion nur sehr wenig Zeit in Anspruch nimmt. Für zeitaufwändigere Fitnessfunktionen kann die Vektorisierung jedoch hilfreich sein. Siehe Vectorize the Fitness Function.

Siehe auch

Themen