使用遗传算法的自定义数据类型优化
这个例子展示了如何使用遗传算法最小化使用自定义数据类型的函数。为解决旅行推销员问题，定制了遗传算法。
旅行商问题
旅行商问题是一个优化问题，其中城市数量是有限的，并且每个城市之间的旅行成本是已知的。目标是为销售人员找到一个访问所有城市的有序集合，以使成本最小化。要解决出差推销员的问题，我们需要一个城市位置和每个城市之间的距离或成本的列表。
我们的推销员正在访问美国的一些城市。该文件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)位置(n,1) = xp;位置(n, 2) = yp;n = n + 1;结束结束情节(位置(:1)、位置(:,2),“波”）;
蓝色的圆圈代表销售人员需要旅行和运送或取货的城市位置。给定城市位置列表，我们可以计算所有城市的距离矩阵。
距离= 0(城市);为count1 = 1:城市,为count =1:count, x1 = locations(count,1);日元=位置(count1, 2);x2 =位置(是从1);y2 =位置(是从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使用的选项结构% Copyright 2004-2007 The MathWorks, Inc. totalPopulationSize = sum(OPTIONS . populationsize);n =据nvar;流行=细胞(totalPopulationSize, 1);for i = 1:totalPopulationSize pop{i} = randperm(n);结束
自定义交叉函数接受一个单元格数组(填充)，并返回一个单元格数组(交叉产生的子单元格数组)。
类型crossover_permutation.m
函数xoverKids = crossover_permutation(parents,options,NVARS，…为旅行推销员定制的交叉功能。% xoverkids = crossover_permutation (parents, options, nvars，…%健康指数，这个分数，这个人口)跨越父母产生%孩子超过孩子。% %该函数的参数为% PARENTS:由选择函数选择的父母% OPTIONS:从OPTIMOPTIONS创建的选项% NVARS:变量数量% FITNESSFCN:适应度函数% STATE: GA求解器使用的状态结构% THISSCORE:当前种群的分数向量% THISPOPULATION:当前种群中的个体矩阵% Copyright 2004-2015 The MathWorks, Inc. nKids = length(PARENTS)/2;xoverKids =细胞(nKids, 1);通常% 0 (nKids,据nvar);指数= 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(parents,options,NVARS，…为旅行推销员定制的突变函数。% mutationchildren = mutate_permutation (parents, options, nvars，…变异父母产生变异的孩子。% %该函数的参数为% PARENTS:由选择函数选择的父母% OPTIONS:从OPTIMOPTIONS创建的选项% NVARS:变量数量% FITNESSFCN:适应度函数% STATE: GA求解器使用的状态结构% THISSCORE:当前种群的分数向量% THISPOPULATION:当前种群中的个体矩阵% MUTATIONRATE:这里我们交换排列突变的两个元素children = cell(length(parents)，1);%正常为零(length(parents)，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
traveling_salesman_fitness(x，距离)% traveling_salesman_fitness为TSP自定义适应度函数。% SCORES = TRAVELING_SALESMAN_FITNESS(X, distance)计算个人的适合度百分比。适应度是x中一个%有序的城市集合的总旅行距离。distance (A,B)是从城市% A到城市B的距离。对于j = 1:size(x,1) %，这里使用的是特殊知识，即总体是一个单元格%数组。通常，这应该是pop(j，:);p = x {j};f =距离(p(结束)、p (1));对于I = 2:长度(p) f = f +距离(p(I -1)，p(I));结束分数(j) = f;结束
遗传算法只调用一个参数的适应度函数x，但我们的适应度函数有两个参数:x，距离．我们可以使用匿名函数来获取附加参数的值，即距离矩阵。我们创建一个函数句柄FitnessFcn到接受一个输入的匿名函数x电话,但traveling_salesman_fitness与x,距离。变量distance在函数句柄时有一个值FitnessFcn，因此匿名函数将捕获这些值。
%前面定义的距离FitnessFcn = @(x) traveling_salesman_fitness(x，距离);
我们可以添加一个自定义plot功能来绘制城市的位置和当前的最佳路线。红圈代表一个城市，蓝线代表两个城市之间的有效路径。
类型traveling_salesman_plot.m
traveling_salesman_plot为旅行推销员定制的plot函数。绘制城市%位置和它们之间的连接路由。这个函数是专门针对旅行推销员的问题。%版权所有2004-2006 The MathWorks, Inc. persistent x y xx yy if strcmpi(flag，'init') load('usborder.mat'，'x'，'y'，'xx'，'yy');情节(x, y,“颜色”,“红色”);轴([-0.1 1.5 -0.2 1.2]);抓住;(未使用,我)= min (state.Score);基因型= state.Population {};情节(位置(: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 cell array{[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: []
图中蓝色圆圈显示的是城市的位置，以及由遗传算法发现的推销员将旅行的路径。销售人员可以从路线的任何一端开始，并在结束时返回起始城市返回家。
相关的话题
您也可以从以下列表中选择网站: