离散型问题是建模竞赛中的主流题型,如果判断所研究的问题是组合优化问题, 那么就大概率需要全局优化算法了。历年赛题中, 比较经典的这类问题有灾情巡视、公交车调度、彩票问题、露天矿卡车调度、交巡警服务平台、太阳影子定位等等。可见全局优化问题的求解算法在数学建模中的重要性,这一讲重要就介绍 MATLAB 全局优化技术及相关实例。

MATLAB 中有个全局优化工具箱 ( Global Optimization Toolbox ) ,该工具箱集成了几个主流的全局优化算法,包含全局搜索、多初始点、模式搜索、遗传算法、多目标遗传算法、模拟退火求解器和粒子群求解器, 如图 1 所示。对于目标函数或约束函数连续、不连续、随机、导数不存在以及包含仿真或黑箱函数的优化问题,都可使用这些求解器来求解。

图 1 MATLAB 全局优化工具箱包含的求解器

另外,还可通过设置选项和自定义创建、更新函数来改进求解器效率。可以使用自定义数据类型,配合遗传算法和模拟退火求解器,来描绘采用标准数据类型不容易表达的问题。利用混合函数选项,可在第一个求解器之后应用第二个求解器来改进解算。

遗传算法可以说是典型的通过变化解的结构以得到更优解的算法,适应能力比较强,现已经典的旅行商问题(TSP)为例, 来看看如何使用 MATLAB 来实现遗传算法。

旅行商问题的数据

load('usborder.mat','x','y','xx','yy');plot(x,y,'Color','red'); hold on;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;    endendplot(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);    endend

定义目标函数

FitnessFcn = @(x) traveling_salesman_fitness(x,distances);

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);

用模拟退火(SA)算法求解Peaks问题

clc, clear, close all

定义优化问题

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))

用一般最优算法求解

[x,f] = fmincon(problem)

-1.3474    0.2045f =   -3.0498

用 SA 算法寻找全局最小值

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)

x =    0.2280   -1.5229f =  -13.0244

MATLAB 全局优化算法的各求解器如下表所示。 在建模比赛中, 建议大家先了解各算法的原理, 这样当遇到具体问题的时候, 就可以根据问题的特征判断哪个或哪几个算法比较合适, 如果不好判断, 不妨全部尝试一下, 做个算法比较也是比较常见的事情, 这样得到的结果更酷, 摘要也更有内容啦。

转自:数模乐园

关注杭电数学建模协会