Matlab实现遗传算法无向图结点分成两类使得两类间边数最少数学建模作业-Toy模板网

这篇具有很好参考价值的文章主要介绍了Matlab实现遗传算法无向图结点分成两类使得两类间边数最少数学建模作业。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

输入：一个图的邻接矩阵G，n1,n2 （举例n1=16,n2=1）

输出：节点的分类id（第一类为0，第二类为1，0的个数为n1个， 1的个数为n2个）

目标：使得两类之间的边数最少

算法：遗传算法

步骤1：初始化种群，种群个数，随机生成初始种群

步骤2：交叉算子

步骤3：突变算子

步骤4：计算适应度，进行种群的优化选择

步骤5：将代码组合起来

步骤6：画图

给出如下邻接矩阵

0    1    0    0    0    0    0    0    0    0    0    1    0    0
0    1    0    0    0    0    0    0    0    0    1    0    0    0
0    0    0    0    0    0    0    1    1    0    0    0    1    0
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    1    0    1    1
0    0    0    0    0    0    0    0    0    0    0    0    0    1
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    0    1
0    0    0    0    0    0    0    0    0    0    0    0    1    1
0    0    0    0    0    0    0    0    0    0    0    0    1    1
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    1    1
0    0    0    0    0    0    0    0    0    0    0    0    0    1
0    0    0    0    0    0    0    0    0    0    0    0    1    1
0    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    1    1
0    0    0    0    0    1    0    1    0    1    0    0    1    1
0    0    0    0    0    1    0    1    0    0    0    1    0    0
0    0    0    1    1    0    0    0    0    0    0    1    0    0
0    0    0    0    0    0    0    0    0    1    0    0    0    1
0    0    0    1    1    0    0    0    0    0    0    0    0    1
0    0    0    0    0    0    0    0    0    0    0    1    0    1
0    0    0    1    0    0    1    0    0    0    0    0    1    1
0    0    0    0    0    0    0    0    0    0    0    0    1    1
0    0    0    0    1    1    0    0    1    0    0    0    1    1
1    0    1    1    0    0    0    0    0    1    1    1    0    1
1    0    1    1    0    0    1    1    1    1    1    1    1    0

步骤1：初始化种群，种群个数，随机生成初始种群

population = cell(1,100);
k=1;
 %随机选取100个种群
for i = 1:100
    a = randperm(34);
    a(find(a <= n1)) = 1;
    a(find(a > n1)) = 0;
    population(i) = {a};
end

randperm（）:此 MATLAB 函数返回行向量，其中包含从 1 到 n 没有重复元素的整数随机排列。找到1~16在数组a的位置，将此位置的数值置1,同理，17~34置0。

这样就得到了一个值全是0或1的数组，0和1各表示一个分类，将34个点分为两类。重复100次，形成一个元胞数组，即为100个将结点分为两类的种群。

更详细的一般编码步骤可以在其他文章搜到，但本题不涉及故不提及。

步骤2：交叉算子

 %交叉
    g = 1;
    count = 1;
    %总交叉次数小于500或得到40对交叉后存活的新个体
    while g <= 500 && count <= 40    
    e = sort(randperm(34,2));
    f = randperm(20,2);
    ransetia = cell2mat(population(f(1)));
    ransetib = cell2mat(population(f(2)));
    %存活条件为交叉前后两组点的数量不变
    if sum(ransetia(e(1):e(2))) == sum(ransetib(e(1):e(2)))
        lingshi = ransetia(e(1):e(2));
        ransetia(e(1):e(2)) = ransetib(e(1):e(2));
        ransetib(e(1):e(2)) = lingshi;
        population(19+2*count) = {ransetia};
        population(20+2*count) = {ransetib};
        count = count+1;
    end
    g = g+1;
    end

让我们先设定词义 种群=染色体

编码的交叉类比染色体交叉，交叉的编码段位置及长度由randperm随机出来，在此题中要满足分出的两类数量为16和18，故交叉出的染色体也要满足条件，ransetia、ransetib中1的数量仍然保持为16，不满足的则直接被淘汰，满足的加入种群。

总交叉次数500可以自己视情况设定，count达到40停止，意思是生成40*2=80个新种群，更新元胞数组21~100位置的种群，前20个是上一次迭代保留的优秀种群，下文会提到。

步骤3：突变算子

任选一个种群，选出两个结点，如果一个是0一个是1，将其突变为1和0，即在交换所属于不同类两个结点的位置。突变次数counter设置为80次，可以视情况改变。

%变异
    counter = 1;
    while counter <= 80
        c = randperm(34,2);
        r = cell2mat(population(randperm(100,1)));
        if sum(r(c)) == 1
            r(c) = r(c)*(-1)+1;
            population(20+counter) = {r};
            counter = counter+1;
        end
    end

步骤4：计算适应度，进行种群的优化选择

适应度的测度：1/(两类结点之间连接的边数+1）分母加一是以防分成互相之间没有边连通的两类时导致分母变为0出错。

 %适应度
    fitness = [];
    %计算适应度
    for i = 1:100
        x = cell2mat(population(i));
        b = Adjacency_matrix-x ;
        fitness(i) = 1/(length(find(b(find(x == 1),:)==1))+1);
    end

    [fitness,Index] = sort(fitness,"descend");
    %将每次迭代的最大适应度保存，便于后续画图
    maxfit(k) = fitness(1);
    %保存该次迭代的总体适应度水平
    general_fit(k) = mean(fitness);
    %淘汰80个种群
    population(Index(21:100)) = [];

精英数量直接设置成了最优的前20个，并没有根据优劣程度排序进行轮盘赌选择，也没有根据迭代次数设置精英个数的递增保留。（因为这题这样已经够用了，可以去设置一下，不难）

步骤5：将代码组合起来

function finalans=GA(Adjacency_matrix,n1,n2)

% Adjacency_matrix= w
% n1 = 16,n2 = 18

if (n1+n2)~=size(Adjacency_matrix,1) ||...
    size(Adjacency_matrix,1)~=size(Adjacency_matrix,2)||...
    n1<1 || n2<1
    error('参数格式不合法')
end

population = cell(1,100);
k=1;
 %随机选取100个种群
for i = 1:100
    a = randperm(34);
    a(find(a <= n1)) = 1;
    a(find(a > n1)) = 0;
    population(i) = {a};
end

while k <= 100
    %交叉
    g = 1;
    count = 1;
    %总交叉次数小于500或得到40对交叉后存活的新个体
    while g <= 500 && count <= 40    
    e = sort(randperm(34,2));
    f = randperm(20,2);
    ransetia = cell2mat(population(f(1)));
    ransetib = cell2mat(population(f(2)));
    %存活条件为交叉前后两组点的数量不变
    if sum(ransetia(e(1):e(2))) == sum(ransetib(e(1):e(2)))
        lingshi = ransetia(e(1):e(2));
        ransetia(e(1):e(2)) = ransetib(e(1):e(2));
        ransetib(e(1):e(2)) = lingshi;
        population(19+2*count) = {ransetia};
        population(20+2*count) = {ransetib};
        count = count+1;
    end
    g = g+1;
    end


    %变异
    counter = 1;
    while counter <= 80
        c = randperm(34,2);
        r = cell2mat(population(randperm(100,1)));
        if sum(r(c)) == 1
            r(c) = r(c)*(-1)+1;
            population(20+counter) = {r};
            counter = counter+1;
        end
    end   
    %适应度
    fitness = [];
    %计算适应度
    for i = 1:100
        x = cell2mat(population(i));
        b = Adjacency_matrix-x ;
        fitness(i) = 1/(length(find(b(find(x == 1),:)==1))+1);
    end

    [fitness,Index] = sort(fitness,"descend");
    %将每次迭代的最大适应度保存
    maxfit(k) = fitness(1);
    %保存该次迭代的总体适应度水平
    general_fit(k) = mean(fitness);
    %淘汰80个种群
    population(Index(21:100)) = [];      
    k = k+1;
end