📄 traveling_salesman_demo.html
字号:
<html xmlns:mwsh="http://www.mathworks.com/namespace/mcode/v1/syntaxhighlight.dtd"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <!--This HTML is auto-generated from an M-file.To make changes, update the M-file and republish this document. --> <title>Custom Data Type Optimization Using the Genetic Algorithm</title> <meta name="generator" content="MATLAB 7.0.0.4032 (R14) Prerelease"> <meta name="date" content="2004-03-23"> <meta name="m-file" content="traveling_salesman_demo"> <meta name="title" content="Custom Data Type Optimization Using the Genetic Algorithm"> <meta name="description" content="This is a demonstration of how to use the genetic algorithm to minimize a function using a custom data type. The genetic algorithm is customized to solve the traveling salesman problem."><style>body { background-color: white;}h1 { color: #990000; font-size: x-large;}h2 { color: #990000; font-size: medium;}p.footer { text-align: right; font-size: xx-small; font-weight: lighter; font-style: italic; color: gray;}pre.codeinput { margin-left: 30px;}span.keyword {color: #0000FF}span.comment {color: #228B22}span.string {color: #A020F0}span.untermstring {color: #B20000}span.syscmd {color: #B28C00}pre.showbuttons { margin-left: 30px; border: solid black 2px; padding: 4px; background: #EBEFF3;}pre.codeoutput { color: gray; font-style: italic;}pre.error { color: red;} </style></head> <body> <h1>Custom Data Type Optimization Using the Genetic Algorithm</h1> <p>This is a demonstration of how to use the genetic algorithm to minimize a function using a custom data type. The genetic algorithm is customized to solve the traveling salesman problem. </p> <h2>Contents</h2> <ul> <li><a href="#1">Traveling salesman problem</a></li> <li><a href="#5">Customizing the genetic algorithm for a custom data type</a></li> <li><a href="#6">Required functions for the traveling salesman problem</a></li> <li><a href="#13">Genetic Algorithm options setup</a></li> </ul> <h2>Traveling salesman problem<a name="1"></a></h2> <p>The traveling salesman problem is an optimization problem where there is a finite number of cities, and the cost of travel between each city is known. The goal is to find an ordered set of all the cities for the salesman to visit such that the cost is minimized. To solve the traveling salesman problem, we need a list of city locations and distances, or cost, between each of them. </p> <p>Our salesman is visiting cities in the United States. The file usborder.mat contains a map of the United States in the variables x and y, and a geometrically simplified version of the same map in the variables xx and yy. </p><pre class="codeinput">load(<span class="string">'usborder.mat'</span>,<span class="string">'x'</span>,<span class="string">'y'</span>,<span class="string">'xx'</span>,<span class="string">'yy'</span>);plot(x,y,<span class="string">'Color'</span>,<span class="string">'red'</span>); hold <span class="string">on</span>;</pre><img vspace="5" hspace="5" src="traveling_salesman_demo_01.png"><p>We will generate random locations of cities inside the border of the United States. We can use the INSIDE function to make sure that all the cities are inside or very close to the US boundary. The INSIDE function requires the input to be of complex data type, hence we will form the US border in imaginary coordinates. </p><pre class="codeinput">cities = 40;complex_coord = xx+i*yy;X_coord = [];Y_coord = [];n=0;<span class="keyword">while</span> n<cities, a=rand*1.5+i*rand; <span class="keyword">if</span> inside(a,complex_coord), X_coord=[X_coord; real(a)]; Y_coord=[Y_coord; imag(a)]; n=n+1; <span class="keyword">end</span>;<span class="keyword">end</span>;locations=[X_coord Y_coord];plot(locations(:,1),locations(:,2),<span class="string">'bo'</span>);</pre><img vspace="5" hspace="5" src="traveling_salesman_demo_02.png"><p>Blue circles represent the locations of the cities where the salesman needs to travel and deliver or pickup goods. Given the list of city locations, we can calculate the distance matrix for all the cities. </p><pre class="codeinput">distances = zeros(cities);<span class="keyword">for</span> count1=1:cities, <span class="keyword">for</span> 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); <span class="keyword">end</span>;<span class="keyword">end</span>;</pre><h2>Customizing the genetic algorithm for a custom data type<a name="5"></a></h2> <p>By default, the genetic algorithm solver solves optimization problems based on double and binary string data types. The functions for creation, crossover, and mutation assume the population is a matrix of type double, or logical in the case of binary strings. The genetic algorithm solver can also work on optimization problems involving arbitrary data types. You can use any data structure you like for your population. For example, a custom data type can be specified using a MATLAB cell array. In order to use GA with 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> <h2>Required functions for the traveling salesman problem<a name="6"></a></h2> <p>This section demonstrates how to create and register the three required functions. An individual in the population for the traveling salesman problem is an ordered set, and so the population can easily be represented using a cell array. The custom creation function for the traveling salesman problem will create a cell array, say P, where each element represents an ordered set of cities as a permutation vector. That is, the salesman will travel in the order specified in P{i}. The creation function will return a cell array of size PopulationSize. </p><pre class="codeinput">type <span class="string">create_permutations.m</span></pre><pre class="codeoutput">function pop = create_permutations(NVARS,FitnessFcn,options)% This function 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 The MathWorks, Inc.% $Revision: 1.1.4.1 $ $Date: 2004/03/26 13:26:06 $totalPopulationSize = sum(options.PopulationSize);n = NVARS;pop = cell(totalPopulationSize,1);for i = 1:totalPopulationSize pop{i} = randperm(n); end</pre><p>The custom crossover function takes a cell array, the population, and returns a cell array, the children that result from the crossover. </p><pre class="codeinput">type <span class="string">crossover_permutation.m</span></pre><pre class="codeoutput">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 structure created from GAOPTIMSET% 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 The MathWorks, Inc. % $Revision: 1.1.4.1 $ $Date: 2004/03/26 13:26:06 $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</pre><p>The custom mutation function takes an individual, which is an ordered set of cities, and returns a mutated ordered set.</p><pre class="codeinput">type <span class="string">mutate_permutation.m</span></pre><pre class="codeoutput">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 structure created from GAOPTIMSET% 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 The MathWorks, Inc.% $Revision: 1.1.4.1 $ $Date: 2004/03/26 13:26:06 $% Here we swap two elements of the permutationmutationChildren = 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</pre><p>We also need a fitness function for the traveling salesman problem. The fitness of an individual is the total distance traveled for an ordered set of cities. The fitness function also needs the distance matrix to calculate the total distance. </p><pre class="codeinput">type <span class="string">traveling_salesman_fitness.m</span></pre><pre class="codeoutput">function scores = traveling_salesman_fitness(x,distances)% A custom fitness function. % 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 The MathWorks, Inc.% $Revision: 1.1.4.1 $ $Date: 2004/03/26 13:26:06 $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⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -