使用遗传算法优化自定义数据类型
此示例说明如何使用遗传算法来最小化使用自定义数据类型的函数。遗传算法是针对旅行商问题专门定制的。
旅行商问题
旅行商问题是一个优化问题,其中城市数量有限,并且每个城市之间的旅行费用是已知的。目标是找到销售员要访问的所有城市的有序集合,以使成本最小化。为了解决旅行商问题,我们需要一个城市位置列表以及每个城市之间的距离或费用。
我们的销售员正在美国各个城市访问。文件 usborder.mat
在变量 x
和 y
中包含美国地图,在变量 xx
和 yy
中包含同一张地图的几何简化版本。
load('usborder.mat','x','y','xx','yy'); plot(x,y,'Color','red'); hold on;
我们将生成美国边境内城市的随机位置。我们可以使用 inpolygon
函数来确保所有城市都位于美国边界内或非常靠近美国边界。
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; end end plot(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); end; end;
为自定义数据类型定制遗传算法
默认情况下,遗传算法求解器基于双精度和二进制字符串数据类型解决优化问题。创建、交叉和变异函数假设种群是双精度类型的矩阵,或者在二进制字符串的情况下是逻辑类型的。遗传算法求解器还可以解决涉及任意数据类型的优化问题。您可以为您的种群使用任何您喜欢的数据结构。例如,可以使用 MATLAB® 元胞数组指定自定义数据类型。为了将 ga
与单元格元胞数组类型的种群一起使用,您必须提供一个创建函数、一个交叉函数和一个可对您的数据类型(例如元胞数组)起作用的变异函数。
旅行商问题所需的函数
本节介绍如何创建和注册三个所需的函数。旅行商问题种群中的一个个体是有序集,因此可以很容易地用元胞数组来表示种群。旅行商问题的自定义创建函数将创建一个元胞数组,例如 P
,其中每个元素以排列向量的形式表示一组有序的城市。也就是说,销售员会按照 P{i}
指定的顺序出行。创建函数将返回大小为 PopulationSize
的元胞数组。
type create_permutations.m
function pop = create_permutations(NVARS,FitnessFcn,options) %CREATE_PERMUTATIONS Creates a population of permutations. % POP = CREATE_PERMUTATION(NVARS,FITNESSFCN,OPTIONS) creates a population % of permutations POP each with a length of NVARS. % % The arguments to the function are % NVARS: Number of variables % FITNESSFCN: Fitness function % OPTIONS: Options structure used by the GA % Copyright 2004-2007 The MathWorks, Inc. totalPopulationSize = sum(options.PopulationSize); n = NVARS; pop = cell(totalPopulationSize,1); for i = 1:totalPopulationSize pop{i} = randperm(n); end
自定义交叉函数采用元胞数组(种群)并返回元胞数组(交叉产生的子项)。
type crossover_permutation.m
function xoverKids = crossover_permutation(parents,options,NVARS, ... FitnessFcn,thisScore,thisPopulation) % CROSSOVER_PERMUTATION Custom crossover function for traveling salesman. % XOVERKIDS = CROSSOVER_PERMUTATION(PARENTS,OPTIONS,NVARS, ... % FITNESSFCN,THISSCORE,THISPOPULATION) crossovers PARENTS to produce % the children XOVERKIDS. % % The arguments to the function are % PARENTS: Parents chosen by the selection function % OPTIONS: Options created from OPTIMOPTIONS % NVARS: Number of variables % FITNESSFCN: Fitness function % STATE: State structure used by the GA solver % THISSCORE: Vector of scores of the current population % THISPOPULATION: Matrix of individuals in the current population % Copyright 2004-2015 The MathWorks, Inc. nKids = length(parents)/2; xoverKids = cell(nKids,1); % Normally zeros(nKids,NVARS); index = 1; for i=1:nKids % here is where the special knowledge that the population is a cell % array is used. Normally, this would be thisPopulation(parents(index),:); parent = thisPopulation{parents(index)}; index = index + 2; % Flip a section of parent1. p1 = ceil((length(parent) -1) * rand); p2 = p1 + ceil((length(parent) - p1- 1) * rand); child = parent; child(p1:p2) = fliplr(child(p1:p2)); xoverKids{i} = child; % Normally, xoverKids(i,:); end
自定义变异函数接受一个个体,即城市的有序集合,并返回一个变异的有序集。
type mutate_permutation.m
function mutationChildren = mutate_permutation(parents ,options,NVARS, ... FitnessFcn, state, thisScore,thisPopulation,mutationRate) % MUTATE_PERMUTATION Custom mutation function for traveling salesman. % MUTATIONCHILDREN = MUTATE_PERMUTATION(PARENTS,OPTIONS,NVARS, ... % FITNESSFCN,STATE,THISSCORE,THISPOPULATION,MUTATIONRATE) mutate the % PARENTS to produce mutated children MUTATIONCHILDREN. % % The arguments to the function are % PARENTS: Parents chosen by the selection function % OPTIONS: Options created from OPTIMOPTIONS % NVARS: Number of variables % FITNESSFCN: Fitness function % STATE: State structure used by the GA solver % THISSCORE: Vector of scores of the current population % THISPOPULATION: Matrix of individuals in the current population % MUTATIONRATE: Rate of mutation % Copyright 2004-2015 The MathWorks, Inc. % Here we swap two elements of the permutation mutationChildren = cell(length(parents),1);% Normally zeros(length(parents),NVARS); for i=1:length(parents) parent = thisPopulation{parents(i)}; % Normally thisPopulation(parents(i),:) p = ceil(length(parent) * rand(1,2)); child = parent; child(p(1)) = parent(p(2)); child(p(2)) = parent(p(1)); mutationChildren{i} = child; % Normally mutationChildren(i,:) end
我们还需要一个解决旅行商问题的适应度函数。个体的适应度是一组有序城市的总行进距离。适应度函数还需要距离矩阵来计算总距离。
type traveling_salesman_fitness.m
function scores = traveling_salesman_fitness(x,distances) %TRAVELING_SALESMAN_FITNESS Custom fitness function for TSP. % SCORES = TRAVELING_SALESMAN_FITNESS(X,DISTANCES) Calculate the fitness % of an individual. The fitness is the total distance traveled for an % ordered set of cities in X. DISTANCE(A,B) is the distance from the city % A to the city B. % Copyright 2004-2007 The MathWorks, Inc. scores = zeros(size(x,1),1); for j = 1:size(x,1) % here is where the special knowledge that the population is a cell % array is used. Normally, this would be pop(j,:); p = x{j}; f = distances(p(end),p(1)); for i = 2:length(p) f = f + distances(p(i-1),p(i)); end scores(j) = f; end
ga
将仅使用一个参量 x
调用我们的适应度函数,但我们的适应度函数有两个参量:x
、distances
。我们可以使用匿名函数来捕获附加参量即距离矩阵的值。我们创建一个函数句柄 FitnessFcn
到一个匿名函数,该函数接受一个输入 x
,但使用 x
调用 traveling_salesman_fitness
和距离。当函数句柄 FitnessFcn
被创建时,变量 distances 就有一个值,因此这些值被匿名函数捕获。
%distances defined earlier
FitnessFcn = @(x) traveling_salesman_fitness(x,distances);
我们可以添加自定义绘图函数来绘制城市的位置和当前最佳路线。红色圆圈代表一座城市,蓝线代表两座城市之间的有效路径。
type traveling_salesman_plot.m
function state = traveling_salesman_plot(options,state,flag,locations) % TRAVELING_SALESMAN_PLOT Custom plot function for traveling salesman. % STATE = TRAVELING_SALESMAN_PLOT(OPTIONS,STATE,FLAG,LOCATIONS) Plot city % LOCATIONS and connecting route between them. This function is specific % to the traveling salesman problem. % Copyright 2004-2006 The MathWorks, Inc. persistent x y xx yy if strcmpi(flag,'init') load('usborder.mat','x','y','xx','yy'); end plot(x,y,'Color','red'); axis([-0.1 1.5 -0.2 1.2]); hold on; [unused,i] = min(state.Score); genotype = state.Population{i}; plot(locations(:,1),locations(:,2),'bo'); plot(locations(genotype,1),locations(genotype,2)); hold off
我们将再次使用匿名函数来创建一个匿名函数的函数句柄,该函数使用附加参量 locations
调用 traveling_salesman_plot
。
%locations defined earlier 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)
ga stopped because it exceeded options.MaxGenerations. x = 1x1 cell array {[14 12 36 3 5 11 40 25 38 37 7 30 28 10 23 21 27 4 1 ... ] (1x40 double)} fval = 5.3846 reason = 0 output = struct with fields: problemtype: 'unconstrained' rngstate: [1x1 struct] generations: 500 funccount: 28563 message: 'ga stopped because it exceeded options.MaxGenerations.' maxconstraint: [] hybridflag: []
该图用蓝色圆圈显示了城市的位置以及销售员通过遗传算法找到的行进路径。销售员可以从路线的任意一端出发,最后返回出发城市回家。