使用遗传算法的自定义数据类型优化
此示例演示如何使用遗传算法来最小化使用自定义数据类型的函数。遗传算法是为解决旅行商问题而定制的。
旅行推销员问题
旅行商问题是一个优化问题，其中城市数量有限，每个城市之间的旅行成本是已知的。目标是为销售人员找到所有城市的有序集合，从而使成本最小化。为了解决旅行推销员问题，我们需要一个城市位置和每个城市之间的距离或成本的列表。
我们的推销员正在访问美国的一些城市。该文件usborder.mat变量中包含美国地图x而且y，以及变量中同一地图的几何简化版本xx而且yy．
负载(“usborder.mat”，“x”，“y”，“xx”，“yy”）;情节(x, y,“颜色”，“红色”）;持有在；
我们将生成美国境内城市的随机位置。我们可以用inpolygon以确保所有城市都在美国境内或非常接近美国边界。
城市= 40;位置= 0(城市，2);N = 1;而(n <= cities) xp = rand*1.5;Yp =兰特;如果Inpolygon (xp,yp,xx,yy) locations(n,1) = xp;位置(n,2) = yp;N = N +1;结束结束情节(位置(:1)、位置(:,2),“波”）;
蓝色圆圈表示销售人员需要旅行和交付或取货的城市位置。给定城市位置列表，我们可以计算所有城市的距离矩阵。
距离= 0(城市);为count1 = 1:城市,为Count2 =1:count1, x1 =位置(count1,1);Y1 = locations(count1,2);X2 = locations(count2,1);Y2 =位置(计数2,2);距离(count1是从=√(x1, x2)) ^ 2 + (y1 y2) ^ 2);距离(是从count1) =距离(count1,是从);结束；结束；
为自定义数据类型定制遗传算法
默认情况下，遗传算法求解器解决基于双字符串和二进制字符串数据类型的优化问题。用于创建、交叉和突变的函数假设总体是double类型的矩阵，或者在二进制字符串的情况下是逻辑矩阵。遗传算法求解器还可以处理涉及任意数据类型的优化问题。您可以对总体使用您喜欢的任何数据结构。例如，可以使用MATLAB®单元格数组指定自定义数据类型。为了使用遗传算法对于单元格数组类型的填充，您必须提供一个创建函数、交叉函数和一个突变函数，这些函数将工作于您的数据类型，例如单元格数组。
旅行商问题的必要函数
本节展示如何创建和注册三个必需的函数。对于旅行推销员问题，总体中的个体是有序集，因此总体可以很容易地用单元格数组表示。例如，旅行推销员问题的自定义创建函数将创建一个单元格数组P，其中每个元素表示一个有序的城市集合，作为一个排列向量。也就是说，业务员将按照指定的顺序出差P{我}．创建函数将返回一个大小相同的单元格数组PopulationSize．
类型create_permutations.m
function pop = create_permutations(NVARS,FitnessFcn,options) % create_permutations创建一个排列的总体。% POP = CREATE_PERMUTATION(NVARS,FITNESSFCN,OPTIONS)创建一个百分比的排列POP，每个排列的长度为NVARS。该函数的参数为% NVARS:变量数量% FITNESSFCN:适应度函数% OPTIONS: GA使用的选项结构%版权2004-2007 The MathWorks, Inc. totalPopulationSize = sum(OPTIONS . populationsize);n = NVARS;pop = cell(totalPopulationSize,1);for i = 1:totalPopulationSize pop{i} = randperm(n);结束
自定义交叉函数接受一个单元格数组，即填充，并返回一个单元格数组，即交叉产生的子单元格数组。
类型crossover_permutation.m
函数xoverKids = crosover_permutation(父母，选项，NVARS，…适应度fcn，这个分数，这个人口)% CROSSOVER_PERMUTATION旅行推销员自定义交叉功能。% xoverkids = crosover_permutation (parents, options, nvars，…% FITNESSFCN,THISSCORE,THISPOPULATION)与父母交叉，产生%的孩子多于孩子。该函数的参数为% PARENTS:选择函数选择的双亲% OPTIONS:从OPTIMOPTIONS创建的选项% NVARS:变量数量% FITNESSFCN:适应度函数% STATE:遗传算法求解器使用的状态结构% THISSCORE:当前种群的分数向量% THISPOPULATION:当前种群中的个体矩阵%版权所有2004-2015 The MathWorks, Inc. nKids = length(PARENTS)/2;xoverKids = cell(nKids,1);%通常为零(nKids,NVARS);指数= 1;for i=1:nKids %这里使用了特殊的知识，即总体是一个单元格%数组。通常，这将是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
自定义突变函数接受一个个体，即城市的有序集，并返回一个突变的有序集。
类型mutate_permutation.m
函数mutationChildren = mutate_permutation(父母，选项，NVARS，…FitnessFcn, state, thisScore,thisPopulation,mutationRate) % MUTATE_PERMUTATION旅行推销员的自定义突变函数。% mutationchildren = mutate_permutation (parents, options, nvars，…%适应度fcn，状态，这个分数，这个群体，突变率)突变父母产生突变孩子的百分比突变孩子。该函数的参数为% PARENTS:选择函数选择的双亲% OPTIONS:从OPTIMOPTIONS创建的选项% NVARS:变量数量% FITNESSFCN:适应度函数% STATE:遗传算法求解器使用的状态结构% THISSCORE:当前种群的分数向量% THISPOPULATION:当前种群中的个体矩阵% MUTATIONRATE:版权所有2004-2015 The MathWorks, Inc. %在这里我们交换置换的两个元素mutationChildren = cell(长度(父母)，1);%通常为零(长度(父母)，NVARS);for i=1:length(parents) parent = thisPopulation{parents(i)};%通常thisPopulation(parents(i)，:) p = ceil(length(parent) * rand(1,2));孩子=父母;子(p(1)) =父(p(2)); child(p(2)) = parent(p(1)); mutationChildren{i} = child; % Normally mutationChildren(i,:) end
我们还需要一个旅行推销员问题的适应度函数。个体的适合度是指在一组有序的城市中旅行的总距离。适应度函数还需要距离矩阵来计算总距离。
类型traveling_salesman_fitness.m
function scores = traveling_salesman_fitness(x,distance) % traveling_salesman_fitness TSP的自定义适应度函数。% SCORES = TRAVELING_SALESMAN_FITNESS(X, distance)计算个体的适合度%。距离(A,B)是从城市% A到城市B的距离。版权2004-2007 The MathWorks, Inc.得分=零(size(x,1)，1);对于j = 1:size(x,1) %，这里使用了填充是单元格%数组的特殊知识。通常，这将是pop(j，:);P = x{j};F =距离(p(end)，p(1));对于I = 2:长度(p) f = f +距离(p(I -1)，p(I));最终得分(j) = f;结束
遗传算法只调用一个参数的适应度函数x，但我们的适应度函数有两个参数:x，距离．我们可以使用匿名函数来获取附加参数的值，即距离矩阵。我们创建一个函数句柄FitnessFcn到接受一个输入的匿名函数x，但电话traveling_salesman_fitness与x，和距离。变量，距离有一个值时，函数句柄FitnessFcn，因此匿名函数将捕获这些值。
前面定义的距离%FitnessFcn = @(x) traveling_salesman_fitness(x，距离);
我们可以添加一个自定义绘图功能来绘制城市的位置和当前的最佳路线。红圈表示一个城市，蓝线表示两个城市之间的有效路径。
类型traveling_salesman_plot.m
function state = traveling_salesman_plot(选项，状态，标志，位置)% traveling_salesman_plot旅行推销员的自定义绘图函数。绘制城市%位置和它们之间的连接路由。这个函数是特定于旅行推销员问题的。if strcmpi(flag，'init') load('usborder.mat'，'x'，'y'，'xx'，'yy');情节(x, y,“颜色”,“红色”);轴([-0.1 1.5 -0.2 1.2]);抓住;[unused,i] = min(state.Score);基因型=州。群体{i};情节(位置(:1)、位置(:,2),“bo”); plot(locations(genotype,1),locations(genotype,2)); hold off
我们将再次使用匿名函数来创建匿名函数的函数句柄traveling_salesman_plot附加参数位置．
%前面定义的位置My_plot = @(选项，状态，标志)traveling_salesman_plot(选项，状态，标志).．.国家,国旗,位置);
遗传算法选项设置
首先，我们将创建一个选项容器来指示自定义数据类型和填充范围。
选项= optimoptions(@ga，“PopulationType”，“自定义”，“InitialPopulationRange”，.．.(1;城市));
我们选择已经创建的自定义创建、交叉、突变和绘图函数，并设置一些停止条件。
选项= optimoptions(选项，“CreationFcn”@create_permutations,.．.“CrossoverFcn”@crossover_permutation,.．.“MutationFcn”@mutate_permutation,.．.“PlotFcn”my_plot,.．.“MaxGenerations”, 500,“PopulationSize”现年60岁的.．.“MaxStallGenerations”, 200,“UseVectorized”,真正的);
最后，我们用问题信息调用遗传算法。
numberOfVariables =城市;[x, fval原因,输出]=.．.ga (FitnessFcn numberOfVariables ,[],[],[],[],[],[],[], 选项)
优化终止:超过最大代数。X = 1x1单元阵列{[14 12 36 3 5 11 40 25 38 37 7 30 28 10 23 21 27 4 1 29 26 31 9 24…]]} fval = 5.3846 reason = 0 output = struct with fields: problemtype: 'unconstrained' rngstate: [1x1 struct] generations: 500 funccount: 28563 message: '优化终止:超过最大代数。' maxconstraint: [] hybridflag: []
该图显示了蓝色圆圈中城市的位置，以及遗传算法发现的推销员将旅行的路径。推销员可以从路线的任何一端出发，最后回到起始城市回家。
相关的话题
您也可以从以下列表中选择一个网站: