Minimizzazione vincolata utilizzando l'algoritmo genetico
Questo esempio mostra come minimizzare una funzione obiettivo soggetta a vincoli e limiti di disuguaglianza non lineare utilizzando l'algoritmo genetico.
Problema di minimizzazione vincolata
Per questo problema, la funzione obiettivo da minimizzare è una semplice funzione di una variabile 2-D 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;
Questa funzione è nota come "camma", come descritto in L.C.W. Dixon e G.P. Szego [1].
Inoltre, il problema presenta vincoli e limiti non lineari.
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)
Codifica la funzione di fitness
Creare un file MATLAB denominato simple_objective.m contenente il seguente codice:
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;
Risolutori come ga accettano un singolo input x, dove x ha tanti elementi quante sono le variabili nel problema. La funzione obiettivo calcola il valore scalare della funzione obiettivo e lo restituisce nel suo singolo argomento di output y .
Codifica la funzione di vincolo
Creare un file MATLAB denominato simple_constraint.m contenente il seguente codice:
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 = [];
La funzione di vincolo calcola i valori di tutti i vincoli di disuguaglianza e di uguaglianza e restituisce rispettivamente i vettori c e ceq. Il valore di c rappresenta i vincoli di disuguaglianza non lineare che il risolutore tenta di rendere minori o uguali a zero. Il valore di ceq rappresenta i vincoli di uguaglianza non lineare che il risolutore tenta di rendere uguali a zero. Questo esempio non ha vincoli di uguaglianza non lineare, quindi ceq = [] . Per i dettagli, vedere Nonlinear Constraints .
Ridurre al minimo utilizzando ga
Specificare la funzione obiettivo come funzione handle.
ObjectiveFunction = @simple_objective;
Specificare i limiti del problema.
lb = [0 0]; % Lower bounds ub = [1 13]; % Upper bounds
Specificare la funzione di vincolo non lineare come funzione handle.
ConstraintFunction = @simple_constraint;
Specificare il numero di variabili del problema.
nvars = 2;
Chiama il risolutore, richiedendo il punto ottimale x e il valore della funzione nel punto ottimale fval.
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
Aggiungi visualizzazione
Per osservare i progressi del risolutore, specificare le opzioni che selezionano due funzioni di grafico. La funzione di grafico gaplotbestf traccia il miglior valore della funzione obiettivo a ogni iterazione, mentre la funzione di grafico gaplotmaxconstr traccia la massima violazione del vincolo a ogni iterazione. Imposta queste due funzioni di grafico in una matrice di celle. Inoltre, è possibile visualizzare informazioni sullo stato di avanzamento del risolutore nella finestra di comando impostando l'opzione Display su 'iter'.
options = optimoptions("ga",'PlotFcn',{@gaplotbestf,@gaplotmaxconstr}, ... 'Display','iter');
Eseguire il risolutore, incluso l'argomento 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
Grazie alla visualizzazione iterativa, ga fornisce dettagli sul tipo di problema e sugli operatori di creazione, crossover, mutation e selezione.
I vincoli non lineari fanno sì che ga risolva molti sottoproblemi a ogni iterazione. Come mostrato sia nei grafici che nella visualizzazione iterativa, il processo di soluzione prevede poche iterazioni. Tuttavia, la colonna Func-count nella visualizzazione iterativa mostra molte valutazioni di funzioni per iterazione.
Il risolutore ga gestisce i vincoli e i limiti lineari in modo diverso rispetto ai vincoli non lineari. Tutti i vincoli e i limiti lineari sono soddisfatti durante l'ottimizzazione. Tuttavia, ga potrebbe non soddisfare tutti i vincoli non lineari a ogni generazione. Se ga converge a una soluzione, i vincoli non lineari saranno soddisfatti in quella soluzione.
ga utilizza le funzioni di mutation e crossover per produrre nuovi individui a ogni generazione. Il modo in cui ga soddisfa i vincoli lineari e vincolati è quello di utilizzare funzioni di mutation e crossover che generano solo punti fattibili. Ad esempio, nella precedente chiamata a ga, la funzione di mutation predefinita (per problemi non vincolati) mutationgaussian non soddisfa i vincoli lineari e quindi ga utilizza invece la funzione mutationadaptfeasible per impostazione predefinita. Se si fornisce una funzione di mutation personalizzata, questa funzione personalizzata deve generare solo punti realizzabili rispetto ai vincoli lineari e ai vincoli di limitazione. Tutte le funzioni di crossover nella casella degli strumenti generano punti che soddisfano i vincoli e i limiti lineari.
Tuttavia, quando il problema contiene vincoli interi, ga impone che tutte le iterazioni soddisfino i limiti e i vincoli lineari. Questa fattibilità si verifica per tutti gli operatori di mutation, crossover e creation, entro una piccola tolleranza.
Fornire un punto di partenza
Per velocizzare il risolutore, è possibile fornire una popolazione iniziale nell'opzione InitialPopulationMatrix. ga utilizza la popolazione iniziale per avviare la sua ottimizzazione. Specificare un vettore riga o una matrice in cui ogni riga rappresenta un punto iniziale.
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 questo caso, fornire un punto di partenza non modifica sostanzialmente l'avanzamento del risolutore.
Riferimenti
[1] Dixon, L. C. W., e G .P. Szego (a cura di). Verso l'ottimizzazione globale 2. Olanda Settentrionale: Elsevier Science Ltd., Amsterdam, 1978.
