基于GA算法的TSP问题源码程序 - matlab算法设计

下载频道> 资源分类> matlab源码> 算法设计> 基于GA算法的TSP问题源码程序

标题：基于GA算法的TSP问题源码程序
分享到：

所属分类: 算法设计资源类型：文件大小: 3.44 KB 上传时间: 2016-01-24 22:26:36 下载次数: 8 资源积分：1分提供者: matlab源码基于GA算法的TSP问题源码程序

内容：
基于GA算法的TSP问题源码程序，程序员在编程的过程中可以参考学习使用，希望对IT程序员有用，此源码程序简单易懂、方便阅读，有很好的学习价值！

部分代码如下：

%TSPO_GA Open Traveling Salesman Problem (TSP) Genetic Algorithm (GA)

% Finds a (near) optimal solution to a variation of the TSP by setting up

% a GA to search for the shortest route (least distance for the salesman

% to travel to each city exactly once without returning to the starting city)

% Summary:

% 1. A single salesman travels to each of the cities but does not close

% the loop by returning to the city he started from

% 2. Each city is visited by the salesman exactly once

% Input:

% USERCONFIG (structure) with zero or more of the following fields:

% - XY (float) is an Nx2 matrix of city locations, where N is the number of cities

% - DMAT (float) is an NxN matrix of point to point distances/costs

% - POPSIZE (scalar integer) is the size of the population (should be divisible by 4)

% - NUMITER (scalar integer) is the number of desired iterations for the algorithm to run

% - SHOWPROG (scalar logical) shows the GA progress if true

% - SHOWRESULT (scalar logical) shows the GA results if true

% - SHOWWAITBAR (scalar logical) shows a waitbar if true

% Input Notes:

% 1. Rather than passing in a structure containing these fields, any/all of

% these inputs can be passed in as parameter/value pairs in any order instead.

% 2. Field/parameter names are case insensitive but must match exactly otherwise.

% Output:

% RESULTSTRUCT (structure) with the following fields:

% (in addition to a record of the algorithm configuration)

% - OPTROUTE (integer array) is the best route found by the algorithm

% - MINDIST (scalar float) is the cost of the best route

% Usage:

% tspo_ga

% -or-

% tspo_ga(userConfig)

% -or-

% resultStruct = tspo_ga;

% -or-

% resultStruct = tspo_ga(userConfig);

% -or-

% [...] = tspo_ga('Param1',Value1,'Param2',Value2, ...);

% Example:

% % Let the function create an example problem to solve

% tspo_ga;

% Example:

% % Request the output structure from the solver

% resultStruct = tspo_ga;

% Example:

% % Pass a random set of user-defined XY points to the solver

% userConfig = struct('xy',10*rand(50,2));

% resultStruct = tspo_ga(userConfig);

% Example:

% % Pass a more interesting set of XY points to the solver

% n = 50;

% phi = (sqrt(5)-1)/2;

% theta = 2*pi*phi*(0:n-1);

% rho = (1:n).^phi;

% [x,y] = pol2cart(theta(:),rho(:));

% xy = 10*([x y]-min([x;y]))/(max([x;y])-min([x;y]));

% userConfig = struct('xy',xy);

% resultStruct = tspo_ga(userConfig);

% Example:

% % Pass a random set of 3D (XYZ) points to the solver

% xyz = 10*rand(50,3);

% userConfig = struct('xy',xyz);

% resultStruct = tspo_ga(userConfig);

% Example:

% % Change the defaults for GA population size and number of iterations

% userConfig = struct('popSize',200,'numIter',1e4);

% resultStruct = tspo_ga(userConfig);

% Example:

% % Turn off the plots but show a waitbar

% userConfig = struct('showProg',false,'showResult',false,'showWaitbar',true);

% resultStruct = tspo_ga(userConfig);

% See also: tsp_ga, tsp_nn, tspof_ga, tspofs_ga, distmat

% Author: Joseph Kirk

% Email: jdkirk630@gmail.com

% Release: 2.0

% Release Date: 05/01/2014

function varargout = tspo_ga(varargin)

% Initialize default configuration

defaultConfig.xy = 10*rand(50,2);

defaultConfig.dmat = [];

defaultConfig.popSize = 100;

defaultConfig.numIter = 1e4;

defaultConfig.showProg = true;

defaultConfig.showResult = true;

defaultConfig.showWaitbar = false;

% Interpret user configuration inputs

if ~nargin

userConfig = struct();

elseif isstruct(varargin{1})

userConfig = varargin{1};

else

try

userConfig = struct(varargin{:});

catch

error('Expected inputs are either a structure or parameter/value pairs');

end

% Override default configuration with user inputs

configStruct = get_config(defaultConfig,userConfig);

% Extract configuration

xy = configStruct.xy;

dmat = configStruct.dmat;

popSize = configStruct.popSize;

numIter = configStruct.numIter;

showProg = configStruct.showProg;

showResult = configStruct.showResult;

showWaitbar = configStruct.showWaitbar;

if isempty(dmat)

nPoints = size(xy,1);

a = meshgrid(1:nPoints);

dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),nPoints,nPoints);

end

% Verify Inputs

[N,dims] = size(xy);

[nr,nc] = size(dmat);

if N ~= nr || N ~= nc

error('Invalid XY or DMAT inputs!')

end

n = N;

% Sanity Checks

popSize = 4*ceil(popSize/4);

numIter = max(1,round(real(numIter(1))));

showProg = logical(showProg(1));

showResult = logical(showResult(1));

showWaitbar = logical(showWaitbar(1));

% Initialize the Population

pop = zeros(popSize,n);

pop(1,:) = (1:n);

for k = 2:popSize

pop(k,:) = randperm(n);

end

% Run the GA

globalMin = Inf;

totalDist = zeros(1,popSize);

distHistory = zeros(1,numIter);

tmpPop = zeros(4,n);

newPop = zeros(popSize,n);

if showProg

figure('Name','TSPO_GA | Current Best Solution','Numbertitle','off');

hAx = gca;

end

if showWaitbar

hWait = waitbar(0,'Searching for near-optimal solution ...');

end

for iter = 1:numIter

% Evaluate Each Population Member (Calculate Total Distance)

for p = 1:popSize

d = 0; % Open Path

for k = 2:n

d = d + dmat(pop(p,k-1),pop(p,k));

end

totalDist(p) = d;

end

% Find the Best Route in the Population

[minDist,index] = min(totalDist);

distHistory(iter) = minDist;

if minDist < globalMin

globalMin = minDist;

optRoute = pop(index,:);

if showProg

% Plot the Best Route

if dims > 2, plot3(hAx,xy(optRoute,1),xy(optRoute,2),xy(optRoute,3),'r.-');

else plot(hAx,xy(optRoute,1),xy(optRoute,2),'r.-'); end

title(hAx,sprintf('Total Distance = %1.4f, Iteration = %d',minDist,iter));

drawnow;

end

% Genetic Algorithm Operators

randomOrder = randperm(popSize);

for p = 4:4:popSize

rtes = pop(randomOrder(p-3:p),:);

dists = totalDist(randomOrder(p-3:p));

[ignore,idx] = min(dists); %#ok

bestOf4Route = rtes(idx,:);

routeInsertionPoints = sort(ceil(n*rand(1,2)));

I = routeInsertionPoints(1);

J = routeInsertionPoints(2);

for k = 1:4 % Mutate the Best to get Three New Routes

tmpPop(k,:) = bestOf4Route;

switch k

case 2 % Flip

tmpPop(k,I:J) = tmpPop(k,J:-1:I);

case 3 % Swap

tmpPop(k,[I J]) = tmpPop(k,[J I]);

case 4 % Slide

tmpPop(k,I:J) = tmpPop(k,[I+1:J I]);

otherwise % Do Nothing

end

newPop(p-3:p,:) = tmpPop;

end

pop = newPop;

% Update the waitbar

if showWaitbar && ~mod(iter,ceil(numIter/325))

waitbar(iter/numIter,hWait);

end

if showWaitbar

close(hWait);

end

if showResult

% Plots the GA Results

figure('Name','TSPO_GA | Results','Numbertitle','off');

subplot(2,2,1);

pclr = ~get(0,'DefaultAxesColor');

if dims > 2, plot3(xy(:,1),xy(:,2),xy(:,3),'.','Color',pclr);

else plot(xy(:,1),xy(:,2),'.','Color',pclr); end

title('City Locations');

subplot(2,2,2);

imagesc(dmat(optRoute,optRoute));

title('Distance Matrix');

subplot(2,2,3);

if dims > 2, plot3(xy(optRoute,1),xy(optRoute,2),xy(optRoute,3),'r.-');

else plot(xy(optRoute,1),xy(optRoute,2),'r.-'); end

title(sprintf('Total Distance = %1.4f',minDist));

subplot(2,2,4);

plot(distHistory,'b','LineWidth',2);

title('Best Solution History');

set(gca,'XLim',[0 numIter+1],'YLim',[0 1.1*max([1 distHistory])]);

end

% Return Output

if nargout

resultStruct = struct( ...

'xy', xy, ...

'dmat', dmat, ...

'popSize', popSize, ...

'numIter', numIter, ...

'showProg', showProg, ...

'showResult', showResult, ...

'showWaitbar', showWaitbar, ...

'optRoute', optRoute, ...

'minDist', minDist);

varargout = {resultStruct};

end

% Subfunction to override the default configuration with user inputs

function config = get_config(defaultConfig,userConfig)

% Initialize the configuration structure as the default

config = defaultConfig;

% Extract the field names of the default configuration structure

defaultFields = fieldnames(defaultConfig);

% Extract the field names of the user configuration structure

userFields = fieldnames(userConfig);

nUserFields = length(userFields);

% Override any default configuration fields with user values

for i = 1:nUserFields

userField = userFields{i};

isField = strcmpi(defaultFields,userField);

if nnz(isField) == 1

thisField = defaultFields{isField};

config.(thisField) = userConfig.(userField);

end

文件列表（点击上边下载按钮，如果是垃圾文件请在下面评价差评或者投诉）:

基于GA算法的TSP问题源码程序/
基于GA算法的TSP问题源码程序/tspo_ga.m

关键词：算法 源码 程序

matlab源码下载排行

回到顶部

友情链接

matlab源码网站源码编程语言网络编程手机通讯编程 KUNAG 官网 KUNAG 电商更多

: 联系方式| 版权声明| 招聘信息| 广告服务| 银行汇款| 法律顾问| 兼职技术| 付款方式| 关于我们|; 网站客服程序员兼职招聘 411241577@qq.com; 沪ICP备19040327号-3; 公安备案号：沪公网安备 31011802003874号; 库纳格流体控制系统（上海）有限公司版权所有; Copyright © 1999-2014, GUSUCODE.COM, All Rights Reserved

关键词： 算法 源码 程序

相关推荐

matlab源码下载排行

友情链接

关键词：算法源码程序