Eingeschränkte Minimierung mit dem genetischen Algorithmus
Dieses Beispiel zeigt, wie mit dem genetischen Algorithmus eine Zielfunktion minimiert werden kann, die nichtlinearen Ungleichheitsbeschränkungen und -grenzen unterliegt.
Problem der eingeschränkten Minimierung
Für dieses Problem ist die zu minimierende Zielfunktion eine einfache Funktion einer 2-D-Variablen 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;
Diese Funktion wird als „Cam“ bezeichnet und in L.C.W. Dixon und G.P. Szego [1] beschrieben.
Darüber hinaus weist das Problem nichtlineare Einschränkungen und Grenzen auf.
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)
Codieren Sie die Fitnessfunktion
Erstellen Sie eine MATLAB-Datei mit dem Namen simple_objective.m, die den folgenden Code enthält:
type simple_objectivefunction 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;
Solver wie ga akzeptieren eine einzelne Eingabe x, wobei x so viele Elemente hat wie die Anzahl der Variablen im Problem. Die Zielfunktion berechnet den Skalarwert der Zielfunktion und gibt ihn in ihrem einzigen Ausgabeargument y zurück.
Code der Einschränkungsfunktion
Erstellen Sie eine MATLAB-Datei mit dem Namen simple_constraint.m, die den folgenden Code enthält:
type simple_constraintfunction [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 = [];
Die Einschränkungsfunktion berechnet die Werte aller Ungleichheits- und Gleichheitseinschränkungen und gibt die Vektoren c bzw. ceq zurück. Der Wert von c stellt nichtlineare Ungleichheitsbeschränkungen dar, die der Solver kleiner oder gleich Null zu machen versucht. Der Wert von ceq stellt nichtlineare Gleichheitsbeschränkungen dar, die der Solver versucht, auf Null zu setzen. Dieses Beispiel hat keine nichtlinearen Gleichheitsbeschränkungen, also ceq = []. Einzelheiten finden Sie unter Nonlinear Constraints.
Minimieren mit ga
Geben Sie die Zielfunktion als Funktionshandle an.
ObjectiveFunction = @simple_objective;
Geben Sie die Problemgrenzen an.
lb = [0 0]; % Lower bounds ub = [1 13]; % Upper bounds
Geben Sie die nichtlineare Einschränkungsfunktion als Funktionshandle an.
ConstraintFunction = @simple_constraint;
Geben Sie die Anzahl der Problemvariablen an.
nvars = 2;
Rufen Sie den Solver auf und fordern Sie den optimalen Punkt x und den Funktionswert am optimalen Punkt fval an.
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
Visualisierung hinzufügen
Um den Fortschritt des Lösers zu beobachten, geben Sie Optionen an, die zwei Plotfunktionen auswählen. Die Plotfunktion gaplotbestf stellt bei jeder Iteration den besten Zielfunktionswert dar und die Plotfunktion gaplotmaxconstr stellt bei jeder Iteration die maximale Einschränkungsverletzung dar. Legen Sie diese beiden Plotfunktionen in einem Zellenarray fest. Zeigen Sie außerdem Informationen zum Fortschritt des Solvers im Befehlsfenster an, indem Sie die Option Display auf 'iter' setzen.
options = optimoptions("ga",'PlotFcn',{@gaplotbestf,@gaplotmaxconstr}, ... 'Display','iter');
Führen Sie den Solver aus, einschließlich des Arguments 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 0Optimization finished: average change in the fitness value less than options.FunctionTolerance and constraint violation is less than options.ConstraintTolerance.
x = 1×2
0.8123 12.3104
fval = 9.1270e+04
Mit der iterativen Anzeige liefert dieses ga Details zum Problemtyp und den Erstellungs-, Crossover-, Mutations- und Auswahloperatoren.
Nichtlineare Einschränkungen führen dazu, dass ga bei jeder Iteration viele Teilprobleme löst. Wie sowohl in den Diagrammen als auch in der iterativen Anzeige gezeigt, umfasst der Lösungsprozess nur wenige Iterationen. Allerdings zeigt die Spalte Func-count in der iterativen Anzeige viele Funktionsauswertungen pro Iteration.
Der ga-Solver behandelt lineare Einschränkungen und Grenzen anders als nichtlineare Einschränkungen. Während der gesamten Optimierung werden alle linearen Einschränkungen und Grenzen eingehalten. Allerdings erfüllt ga möglicherweise nicht alle nichtlinearen Einschränkungen in jeder Generation. Wenn ga zu einer Lösung konvergiert, werden die nichtlinearen Einschränkungen bei dieser Lösung erfüllt.
ga verwendet die Mutations- und Crossover-Funktionen, um in jeder Generation neue Individuen zu erzeugen. Die Art und Weise, wie ga die linearen und gebundenen Einschränkungen erfüllt, besteht darin, Mutations- und Crossover-Funktionen zu verwenden, die nur mögliche Punkte generieren. Beispielsweise erfüllte im vorherigen Aufruf von ga die Standardmutationsfunktion (für uneingeschränkte Probleme) mutationgaussian die linearen Einschränkungen nicht, weshalb ga stattdessen standardmäßig die Funktion mutationadaptfeasible verwendet. Wenn Sie eine benutzerdefinierte Mutationsfunktion bereitstellen, darf diese benutzerdefinierte Funktion nur Punkte generieren, die im Hinblick auf die linearen und gebundenen Einschränkungen durchführbar sind. Alle Crossover-Funktionen in der Toolbox generieren Punkte, die die linearen Einschränkungen und Grenzen erfüllen.
Wenn Ihr Problem jedoch ganzzahlige Einschränkungen enthält, erzwingt ga, dass alle Iterationen Grenzen und lineare Einschränkungen erfüllen. Diese Machbarkeit besteht für alle Mutations-, Crossover- und Erstellungsoperatoren innerhalb einer kleinen Toleranz.
Geben Sie einen Startpunkt an
Um den Solver zu beschleunigen, können Sie in der Option InitialPopulationMatrix eine Anfangspopulation angeben. ga verwendet die Anfangspopulation, um seine Optimierung zu starten. Geben Sie einen Zeilenvektor oder eine Matrix an, in der jede Zeile einen Startpunkt darstellt.
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.
x = 1×2
0.8122 12.3103
fval = 9.1268e+04
In diesem Fall ändert die Angabe eines Startpunkts den Löserfortschritt nicht wesentlich.
Verweise
[1] Dixon, L. C. W., und G. P. Szego (Hrsg.). Auf dem Weg zur globalen Optimierung 2. Nordholland: Elsevier Science Ltd., Amsterdam, 1978.
