【组合优化】旅行商问题Traveling Salesman Problem(TSP)

2024-07-11 03:38| 来源: 网络整理| 查看: 265

遗传算法中的变量是什么？ function pop = create_permutations(NVARS,FitnessFcn,options) totalPopulationSize = sum(options.PopulationSize); n = NVARS; pop = cell(totalPopulationSize,1); for i = 1:totalPopulationSize pop{i} = randperm(n); end

根据create生成函数可得，遗传算法中的变量为全排列。也就是说，遗传算法一直在可行解的框架内进行寻优。而在精确解法中的分支定界和割平面法中，前期许多过程均在一步步排除不可行的解。

如何让解发生交叉变化？ function xoverKids = crossover_permutation(parents,options,NVARS, ... FitnessFcn,thisScore,thisPopulation) 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,:);

其中最核心的一行为：

child(p1:p2) = fliplr(child(p1:p2));

fliplr函数的作用是将一部分序列进行翻转。这个函数作用之后，仍然是一个可行解。也就是说，crossover函数是将一个可行解变成了另外一个可行解。

如何让可行解产生变异？ function mutationChildren = mutate_permutation(parents ,options,NVARS, ... FitnessFcn, state, thisScore,thisPopulation,mutationRate) % 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

其中核心的一行为：

p = ceil(length(parent) * rand(1,2));

通过随机数，让两个粒子进行交换。通过此过程，规定了变异的强度。这个函数作用之后，仍然是一个可行解。也就是说，mutation函数是将一个可行解变成了另外一个可行解。

之后的动作就是标准过程，如下所示：

options = optimoptions(@ga, 'PopulationType', 'custom','InitialPopulationRange', ... [1;nStops]); options = optimoptions(options,'CreationFcn',@create_permutations, ... 'CrossoverFcn',@crossover_permutation, ... 'MutationFcn',@mutate_permutation, ... 'MaxGenerations',5000,'PopulationSize',5000, ... 'MaxStallGenerations',200,'UseVectorized',true); numberOfVariables = nStops; [x,fval,reason,output] = ... ga(FitnessFcn,numberOfVariables,[],[],[],[],[],[],[],options)

【本文地址】

公司简介

联系我们