matlab全局优化与局部优化

在实际的工作和生活过程中,优化问题无处不在,比如资源如何分配效益最高,拟合问题,最小最大值问题等等。优化问题一般分为局部最优和全局最优,局部最优,就是在函数值空间的一个有限区域内寻找最小值;而全局最优,是在函数值空间整个区域寻找最小值问题。

  • 函数局部最小点是那种它的函数值小于或等于附近点的点。但是有可能大于较远距离的点。
  • 全局最小点是那种它的函数值小于或等于所有的可行点。

MATLAB—什么是全局优化 - foundy - 李会先博客

matlab中的提供的传统优化工具箱(Optimization Tool),能实现局部最优,但要得全局最优,则要用全局最优化算法(Global Optimization Tool),主要包括:
  1. GlobalSearch) 全局搜索和(MultiStart)多起点方法产生若干起始点,然后它们用局部求解器去找到起始点吸引盆处的最优点。
  2. ga  遗传算法用一组起始点(称为种群),通过迭代从种群中产生更好的点,只要初始种群覆盖几个盆,GA就能检查几个盆。
  3. simulannealbnd)模拟退火完成一个随机搜索,通常,模拟退火算法接受一个点,只要这个点比前面那个好,它也偶而接受一个比较糟的点,目的是转向不同的盆。
  4.  (patternsearch )模式搜索算法在接受一个点之前要看看其附近的一组点。假如附近的某些点属于不同的盆,模式搜索算法本质上时同时搜索若干个盆
下面我就一些具体例子,来说明各种优化方法:
(1)先看一个求最小值的普通优化问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
%%目标函数
f = @(x) x.*sin(x) + x.*cos(2.*x); 
%% 的取值范围
lb = 0;
ub = 10;
%% 寻找最小值和绘图
x0 = [0 1 3 6 8 10];
hf = figure;
for i=1:6
    x(i) = fmincon(f,x0(i),[],[],[],[],lb,ub,[],...
                   optimset('Algorithm','SQP','Disp','none'));
    subplot(2,3,i)
    ezplot(f,[lb ub]);
    hold on
    plot(x0(i),f(x0(i)),'k+')
    plot(x(i),f(x(i)),'ro')
    hold off
    title(['Starting at ',num2str(x0(i))])
    if i == 1 || i == 4
        ylabel('x sin(x) + x cos(2 x)')
    end
end


可以看出,初值x0不同,得到的结果截然不同,这说明这种求解器,能寻找局部最优,但不一定是全局最优,在起点为8时,取得全局最优。
 
我们换一种求解器:fminbound,这种求解器不需要给点初值。

1
2
3
4
5
6
7
8
x2 = fminbnd(f,lb,ub);
figure
ezplot(f,[lb ub]);
hold on
plot(x2,f(x2),'ro')
hold off
ylabel('x sin(x) + x cos(2 x)')
title({'Solution using fminbnd.','Required no starting point!'})

现在我们尝试全局最优的方法:GlobalSearch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
% Leason Learned: Use the appropriate solver for your problem type!
%% But what if |fmincon| was the only choice?
% Use globalSearch or MultiStart
problem = createOptimProblem('fmincon','objective',f,'x0',x0(1),'lb',lb,...
             'ub',ub,'options',optimset('Algorithm','SQP','Disp','none'));
gs = GlobalSearch;
xgs = run(gs,problem);
figure
ezplot(f,[lb ub]);
hold on
plot(xgs,f(xgs),'ro')
hold off
ylabel('x sin(x) + x cos(2 x)')
title('Solution using globalSearch.')

因此全局最优的方法能够获取全局最优。

(2)再看一个线性拟合的问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
close all, clear all, clc
%% Pharmacokinetic Data
t = [ 3.92,  7.93, 11.89, 23.90, 47.87, 71.91, 93.85, 117.84 ]              %#ok<*NOPTS>
c = [0.163, 0.679, 0.679, 0.388, 0.183, 0.125, 0.086, 0.0624 ]
plot(t,c,'o'), xlabel('t'), ylabel('c')
%% 3 Compartment Model
model = @(b,t) b(1)*exp(-b(4)*t) + b(2)*exp(-b(5)*t) + b(3)*exp(-b(6)*t)
%% Define Optimization Problem
problem = createOptimProblem('lsqcurvefit', ...
                             'objective', model, ...
                             'xdata', t, 'ydata', c, ...
                             'x0',ones(1,6),...
                             'lb', [-10 -10 -10  0   0   0 ],...
                             'ub', [ 10  10  10 0.5 0.5 0.5], ...
                             'options',optimset('OutputFcn',...
                             @curvefittingPlotIterates))
%% solve
b = lsqcurvefit(problem)  
结果:最小二乘拟合结果误差较大

现在我们尝试全局最优方法:MultiStart

1
2
3
4
5
6
7
8
9
10
%% Multistart
ms = MultiStart                                                             
[b,fval,exitflag,output,solutions] = run(ms, problem, 50)                   %#ok<*NASGU,*ASGLU>
%%
curvefittingPlotIterates(solutions)
%%
problem.options.OutputFcn = {};
tic, [b,fval,exitflag,output,solutions] = run(ms, problem, 100), toc  %计算算法的时间

可以看出全局优化结果较好,误差较小。

这种算法的运行时间:Elapsed time is 6.139324 seconds.
现在我使用并行计算的方式解决:
1
2
3
4
5
%% Parallel Version
matlabpool open 2 %开启两个matlab并行计算
ms.UseParallel = 'always' %开启并行计算
tic, [bp,fvalp,exitflagp,outputp,solutionsp] = run(ms, problem, 100); toc
matlabpool close
结果:14 out of 100 local solver runs converged with a positive local solver exit flag.

Elapsed time is 4.358762 seconds.
Sending a stop signal to all the labs … stopped.

可以看出,运行时间减少,提高了效率。
(3)再看一个寻找最小值的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
%% Objective Function
% We wish find the minimum of the |peaks| function
clear all, close all, clc
peaks
%% Nonlinear Constraint Function
% Subject to a nonlinear constraint defined by a circular region of radius
% three around the origin
type circularConstraint
%% Define Optimization Problem
problem = createOptimProblem('fmincon',...
                             'objective',@(x) peaks(x(1),x(2)), ...
                             'nonlcon',@circularConstraint,...
                             'x0',[-1 -1],...
                             'lb',[-3 -3],...
                             'ub',[3 3],...
                             'options',optimset('OutputFcn',...
                                                @peaksPlotIterates))
                             
%% Run the solver |fmincon| from the inital point
% We can see the solution is not the global minimum
[x,f] = fmincon(problem)    

这种方法只能寻找局部最优。

现在用全局优化算法:

1
2
3
4
5
6
7
%% Use |MultiStart| to Find the Global Minimum
% Define the multistart solver
close all
ms = MultiStart %这里可以换成GlobalSearch
%% Run |Multistart|
% Well use 5 starting points
[x,f,exitflag,output,solutions] = run(ms, problem, 5)
 
 

(4)再举一个模拟退火即模式搜索的算法 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
%% Objective Function
% We wish find the minimum of the |peaks| function
clear all, close all, clc
peaks
%% Nonlinear Constraint Function
% Subject to a nonlinear constraint defined by a circular region of radius
% three around the origin
type circularConstraint
%% Define Optimization Problem
problem = createOptimProblem('fmincon',...
                             'objective',@(x) peaks(x(1),x(2)), ...
                             'nonlcon',@circularConstraint,...
                             'x0',[-1 -1],...
                             'lb',[-3 -3],...
                             'ub',[3 3],...
                             'options',optimset('OutputFcn',...
                                                @peaksPlotIterates))
                             
%% Run the solver |fmincon| from the inital point
% We can see the solution is not the global minimum
[x,f] = fmincon(problem)                                                    
%% Use Simmulated Annealing to Find the Global Minimum
% Solve the problem using simmulated annealing.  Note that simmulated
% annealing does not support nonlinear so we need to account for this in
% the objective function.
problem.solver  = 'simulannealbnd';
problem.objective = @(x) peaks(x(1),x(2)) + (x(1)^2 + x(2)^2 - 9);
problem.options = saoptimset('OutputFcn',@peaksPlotIterates,...
                             'Display','iter',...
                             'InitialTemperature',10,...
                             'MaxIter',300)
[x,f] = simulannealbnd(problem) 
f = peaks(x(1),x(2))   

 
 
  Use Pattern Search to Find the Global Minimum
1
2
3
4
5
6
7
8
%% Use Pattern Search to Find the Global Minimum
% Solve the problem using pattern search.
problem.solver  = 'patternsearch';
problem.options = psoptimset('OutputFcn',@peaksPlotIterates,...
                             'Display','iter',...
                             'SearchMethod',{@searchlhs})
[x,f] = patternsearch(problem)
 

2 thoughts on “matlab全局优化与局部优化

Leave a Reply

Your email address will not be published. Required fields are marked *