遗传算法解决旅行商问题(TSP)一:初始化和适应值

旅行商问题（Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

设有n个城市，城市i和城市j之间的距离是 。设

image

那么TSP问题使下面的目标最小：

image

设置参数

首先，设置一下参数：

CITYSIZE            = 10;       % 城市个数
POPSIZE             = 50;       % 种群个数
PC                  = 0.4;      % 交叉概率
PM                  = 0.05;     % 变异概率
MAXGEN              = 150;      % 迭代次数

LEAVING             = 5;        % 父代保留数量

生成距离矩阵

这里假设有10个城市，其坐标定义于pos变量，第一行是各个城市的x坐标，第二行是各个城市的y坐标，比如第一个城市的坐标为(1,1)，第三个城市的坐标为(2,2)。之后计算处各个城市之间的距离。

pos = [1 2 2 3 1 4 5 5 6 4; 1 1 2 2 3 4 4 5 5 6];       % 城市坐标
D = distancematrix(pos);                                % 城市距离矩阵

function D = distancematrix(pos)
% 根据城市坐标位置生成各地距离矩阵
% pos       input  城市坐标
% D         output 距离矩阵
N = size(pos, 2);
D = zeros(N, N);
for i = 1:N
    for j = i+1:N
        dis = (pos(1,i) - pos(1,j)).^2 + (pos(2,i) - pos(2,j)).^2;
        D(i,j) = dis^(0.5);
        D(j,i) = D(i,j);
    end
end
end

初始化

种群中每个个体，都表示着一个访问城市的路径，这意味着每个个体都要覆盖所有城市，但是只能经过一个城市一次。

function pop = initpop(popsize, chromlength)
% 生成初始种群
% popsize       input  种群规模
% chromlength   input  染色体长度
% pop           output 种群
pop = zeros(popsize, chromlength);
for i = 1:popsize
    pop(i,:) = randperm(chromlength);
end
end

计算适应度值

根据种群中每个个体中城市的顺序，可以求出这个个体所代表的距离，距离越大，适应度越小，因此用距离的倒数作为个体的适应度值。

function len = callength(D, pop)
% 计算种群中每个个体所对应的路线距离
% D             input  距离矩阵
% pop           input  种群
% len           output 距离
n = size(pop,1);
len = zeros(n, 1);
for i = 1:n
    for j = 1:(size(pop,2)-1)
        len(i,1) = len(i,1) + D(pop(i, j), pop(i, j+1));
    end
    len(i,1) = len(i,1) + D(pop(i,1), pop(i,end));
end
end

function fitness = calfitness(objval)
% 求适应度值
% objval        input  目标函数值
% fitness       output 适应度值
fitness = 1 ./ objval;
end