遗传算法简单介绍与MATLAB实现(三)

时间:2022-04-01 09:52:40

遗传算法简单介绍与MATLAB实现(三)

新的题目

我们先来看一下可能会遇到的比较常见的问题:找一堆点的中心。

假如我们现在有十个点:

序号 x y
1 1.4 3.6
2 2.7 0.1
3 1.5 6.9
4 4.6 3.6
5 5.2 1.2
6 5.6 2.7
7 8.2 3.5
8 3.8 2.1
9 4.6 2.9
10 8.7 3.3

我们现在想要找出一个点,这个点距离其他所有点的距离之和最短。


以上就是题目,所以我们可以先用公式来形容一下,我们需要找一个点 (x0,y0) ,令该点到其他十个点的距离之和为 d ,则有

d=i=110(x0xi)2+(y0yi)2

所以我们现在面对的就是求

mind

现在看起来应该比较清楚了,但是有一个问题,就是上一章中,我们讲的是求最大值,即令最优解是最大值。如果我们想要改成求最小值的话,那么程序中要有很多地方需要改,如果一个不慎,很有可能哪里没有改过来就导致程序的结果出现了bug,因此我们稍微变换一下,把我们想求的变成最大值就好

max1d

这样子就能够适应我们之前讲的程序了。

模型与遗传算法连接处

那么要怎么用遗传算法解决呢?上一章中我在CalFitness这个函数说明了它很重要,就是因为它是被解决模型和遗传算法的连接部分。

我们曾经说过,某个个体的适应度其实就是被求模型的解,也就是说每个个体我们都要把他的染色体带入到模型中求一下解,得出来的解就是适应度。而CalFitness这个函数就是用来求解种群中每个个体的适应度的。

我们再看一下上一章中这一段程序

function fitness = CalFitness(chrom, N, N_chrom)
fitness = zeros(N, 1);
%开始计算适应度
for i = 1:N
x = chrom(i, 1);
y = chrom(i, 2);
fitness(i) = sin(x)+cos(y)+0.1*x+0.1*y;
end

首先我利用zeros函数给fitness预分配了空间,接下来用了一个for循环对种群中所有个体进行循环内部的操作。这个操作就是我们上一章出的那个求解最大值的问题。

所以到这里应该很明白了,我们把模型的程序写在CalFitness里面就好。

模型的代码

因此我们依旧令染色体节点数为2,第一个节点是 x 坐标,第二个节点是 y 坐标,修改两个变量的范围都是 [0,10] 。这是基础参数需要变化的。

把最后输出的适应度全部都被一除一下,这是代码需要修改的。

所以可以很容易写出这个模型的代码为

function fitness = CalFitness(chrom, N, N_chrom)
fitness = zeros(N, 1);
point = [1.4 2.7 1.5 4.6 5.2 5.6 8.2 3.8 4.6 8.7;
3.6 0.1 6.9 3.6 1.2 2.7 3.5 2.1 2.9 3.3]
;
for i = 1:N
x = chrom(i, 1);
y = chrom(i, 2);
xy = [x; y]*ones(1, 10);
d = sum(sqrt((xy(1,:)-point(1,:)).^2+(xy(2,:)-point(2,:)).^2));
fitness(i) = 1/d;
end

顺便再画出图,修改一下PlotModel函数

function y = PlotModel(chrom)
point = [1.4 2.7 1.5 4.6 5.2 5.6 8.2 3.8 4.6 8.7;
3.6 0.1 6.9 3.6 1.2 2.7 3.5 2.1 2.9 3.3]
;
figure(2)
scatter(point(1,:), point(2,:), 'ko')
hold on
scatter(chrom(1), chrom(2), 'bo', 'filled')
for i = 1:10
plot([point(1, i) chrom(1)], [point(2, i) chrom(2)], 'y')
end

模型的结果

因此可以得到结果最优的坐标点为 (4.6,2.9) ,此时距离其他十个点的距离之和为 24.1432

遗传算法适应度迭代图为

遗传算法简单介绍与MATLAB实现(三)

下图是做出来的坐标点的位置

遗传算法简单介绍与MATLAB实现(三)

简单的总结

以上就是遗传算法的简单应用与MATLAB实现。希望我的内容可以给诸位看的人一点帮助。

曾经我在学习Python的时候也写了一个遗传算法,所以我下一次会把Python版的代码放出来。当初写时是想要熟悉Python的类以及列表的使用等,所以并没有使用numpy来仿MATLAB写,所以诸位有相同意向的在我下一篇博客里可以一起讨论一下。

以上。