主要内容

Custom Data Type Optimization Using the Genetic Algorithm

打开脚本

此示例显示了如何使用遗传算法使用自定义数据类型最小化函数。定制遗传算法以解决旅行推销员问题。

旅行推销员问题

旅行推销员问题是一个优化问题，有限的城市数量，并且每个城市之间的旅行成本是已知的。目的是找到一套有序的城市，让推销员参观，以使成本最小化。为了解决旅行推销员问题，我们需要每个城市的位置和距离或成本清单。

我们的推销员正在美国访问美国的城市。文件usborder.matcontains a map of the United States in the variablesX和y，以及变量中同一地图的几何简化版本XX和yy。

加载（'usborder.mat'，，，，'x'，，，，'y'，，，，'xx'，，，，'YY'); plot(x,y,'颜色'，，，，'红色的'); hold上;

我们将在美国边界内建立城市的随机位置。我们可以使用inpolygon功能以确保所有城市都在内部或非常接近美国边界。

城市= 40;位置=零（城市，2）;n = 1;while(n <= cities) xp = rand*1.5; yp = rand;ifInpolygon（XP，YP，XX，YY）位置（n，1）= XP;位置（n，2）= yp;n = n+1;结尾结尾绘图（位置（：1），位置（：，2），'bo');

蓝色圈子代表了推销员需要旅行和交付或取货商品的城市的位置。鉴于城市位置列表，我们可以计算所有城市的距离矩阵。

距离= zeros(cities);为了count1 = 1：城市，为了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);结尾;结尾;

Customizing the Genetic Algorithm for a Custom Data Type

默认情况下，遗传算法求解器基于双重和二进制字符串数据类型解决了优化问题。创建，交叉和突变的功能假设种群是双重型的矩阵，或者在二进制字符串的情况下是逻辑的。遗传算法求解器还可以处理涉及任意数据类型的优化问题。您可以将您喜欢的任何数据结构用于人群。例如，可以使用MATLAB®单元格数组指定自定义数据类型。为了使用gawith a population of type cell array you must provide a creation function, a crossover function, and a mutation function that will work on your data type, e.g., a cell array.

旅行推销员问题所需的功能

本节显示了如何创建和注册三个必需功能。旅行推销员问题的人口中的个人是有序的集合，因此可以使用单元格数量轻松地表示人口。旅行推销员问题的自定义创建功能将创建一个单元格数组，例如p，其中每个元素代表有序的城市作为排列向量。也就是说，推销员将按照指定的顺序旅行p {i}。创建功能将返回一个大小的单元格数组人口化。

typecreate_permutations.m
函数流行= create_permutations(据nvar 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

自定义交叉功能采用单元阵列，人群，并返回一个单元格数组，这是由交叉造成的孩子。

typecrossover_permunt.m
函数Xoverkids = Crossover_permunt（父母，选项，NVARS，... FITNESSFCN，THISCORE，THISPOPULATION）％Crossover_PerMunt_Permunt for Traveling Salesman的自定义交叉功能。％Xoverkids = Crossover_permunt（父母，期权，NVARS，...％Fitnessfcn，ThisScore，ThisProution）跨越父母产生％的孩子Xoverkids。％％对该功能的参数为％父母：选择功能的父母选择％选项：从Optimottions％NVARS创建的选项：变量数量％Fitnessfcn：Fitness函数％状态：GA Solver％使用的状态结构THISCORE使用的状态结构：当前人口百分比本人群的评分：当前人口中个体的矩阵2004-2015 The Mathworks，Inc。nkids =长度（父母）/2;Xoverkids = Cell（Nkids，1）;百分比为零（NKIDS，NVARS）；索引= 1;对于i = 1：nkids％，这是使用人口为单元％阵列的特殊知识。通常，这将是这个人群（父母（索引），:);parent = thisPopulation {父母（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

自定义突变函数采用一个个人，这是一组有序的城市，并返回一个突变的有序集。

typemutate_permunt.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

我们还需要用于旅行推销员问题的健身功能。个人的适应性是一组有序城市的总距离。健身函数还需要距离矩阵来计算总距离。

typetravely_salesman_fitness.m
功能分数= travely_salesman_fitness（x，distances）％travely_salesman_fitness for TSP的自定义健身功能。％分数= travely_salesman_fitness（x，距离）计算个人的健身％。健身是X中的一个％订购城市的总距离。大小（x，1），1）;对于j = 1：大小（x，1）％，这是使用人口为单元％阵列的特殊知识。通常，这将是流行的（j，:);p = x {j};f =距离（p（end），p（1））;对于i = 2：长度（p）f = f +距离（p（i-1），p（i））;结束分数（j）= f;结尾

ga只需一个论点就将我们的健身功能称为X，，，，but our fitness function has two arguments:X，，，，距离。We can use an anonymous function to capture the values of the additional argument, the distances matrix. We create a function handleFitnessfcn到一个匿名函数，该功能接受一个输入X，但是打电话travely_salesman_fitnesswithX和距离。变量，距离有一个值Fitnessfcn创建，因此这些值由匿名函数捕获。

之前定义的％距离fitnessfcn = @（x）travely_salesman_fitness（x，distances）;

We can add a custom plot function to plot the location of the cities and the current best route. A red circle represents a city and the blue lines represent a valid path between two cities.

typetravely_salesman_plot.m
函数状态= travely_salesman_plot（选项，状态，标志，位置）％travely_salesman_plot for旅行推销员自定义绘图功能。％state = travely_salesman_plot（选项，状态，标志，位置）绘制城市％位置以及它们之间的连接路线。此功能特定于旅行推销员问题。％版权2004-2006 MathWorks，Inc。持续X y XX yy，如果strcmpi（flag，'init'）load（'usborder.mat'，'x'，x'，'y'，''，xx'，yy'）;结束图（x，y，'颜色'，'red'）;轴（[ -  0.1 1.5 -0.2 1.2]）;坚持，稍等;[未使用，i] = min（state.score）;基因型= state.Population {i};绘图（位置（：1），位置（：，2），'bo'）; plot(locations(genotype,1),locations(genotype,2)); hold off

再次，我们将使用匿名函数来创建一个匿名函数的函数句柄，该函数调用travely_salesman_plot与其他论点位置。

之前定义的％位置my_plot = @（选项，状态，标志）travely_salesman_plot（选项，...state,flag,locations);

遗传算法选项设置

首先，我们将创建一个选项容器，以指示自定义数据类型和人口范围。

选项= Optimoptions（@GA，“人口类型”，，，，'风俗'，，，，'InitialPopulationRange'，，，，...[1;城市]）;

我们选择我们创建的自定义创建，交叉，突变和情节功能，以及设置一些停止条件。

选项= optimoptions（选项，'creationfcn'，，，，@create_permutations,...“跨界”，@crossover_permunt，...'MutationFcn'，@mutate_permunt，...'PlotFcn'，my_plot，...“最大化”，500，“人口化”，，，，60,...'MaxStallGenerations'，200，“使用矢量”，真的）;

最后，我们将问题信息称为遗传算法。

数字=城市；[x，fval，原因，输出] =...ga(FitnessFcn,numberOfVariables,[],[],[],[],[],[],[],options)
优化终止：超过几代人数。x = 1x1单元格数组{[[14 12 36 3 5 11 40 25 37 7 30 28 10 23 21 27 4 1 29 26 31 9 24 ...]} fval = 5.3846原因= 0 output = 0 output = struct with fields：alsisionType：“无约束” rngstate：[1x1 struct]世代：500 funccount：28563消息：“优化终止：超过世代的最大数量。”MaxConstraint：[] Hybridflag：[]

The plot shows the location of the cities in blue circles as well as the path found by the genetic algorithm that the salesman will travel. The salesman can start at either end of the route and at the end, return to the starting city to get back home.

相关话题