【优化覆盖】基于matlab果蝇算法求解无线传感器覆盖优化问题【含Matlab源码 2215期】

一、⛄果蝇算法

果蝇优化算法(Fruit Fly Optimization Algorithm, FOA) 是台湾学者潘文超经过研究发现, 并于2011年提出的一种新型智能优化算法, 它具有很好的全局优化性能, 能够解决很多的优化求解问题.果蝇有着优于其它生物的感官知觉, 特别是视觉与嗅觉, 依靠灵敏的嗅觉, 果蝇可以很好的感知到空气中的各种气味分子, 甚至可以嗅到几十公里以外的食物.同时利用敏锐的视觉与其它果蝇聚集, 并向该方向移动.果蝇算法就是模仿果蝇的觅食过程而提出一种新型的群智能优化算法.

1 基本果蝇算法:
果蝇拥有优于其它物种的感官, 它可以收集空气中的气味分子搜寻远处的食物, 然后聚集同伴朝食物方向并拢.FOA算法就是模拟果蝇群体的觅食过程而衍生的优化算法, 其步骤可以归纳为:

(1) 初始化种群大小Sizepop, 最大迭代次数Maxgen, 随机初始化果蝇群体位置X_axis, Y_axis.
(2) 果蝇个体随机向各个方向的位置进行搜寻.
(3) 计算果蝇个体与原点距离d, 再将距离的倒数做为果蝇个体的味道浓度判定值
(4) 将味道浓度判定值Si代入适应度函数 (Fitness function) , 求出果蝇个体的味道浓度.
(5) 找出果蝇群体中最佳的果蝇
(6) 记录并保留最佳味道浓度值与X, Y坐标.
(7) 开始迭代, 重复执行 (2) ~ (5) , 并判断最佳味道浓度是否优于前一次迭代得到的味道浓度, 并且当前迭代次数小于最大迭代数Maxgen, 则执行 (6) , 否则, 算法结束.

将CS-FOA应用于解决WSN问题的算法步骤如下:
(1) 初始化无线传感器网络相关参数, 包括区域长a, 宽b, 节点的额定有效覆盖半径R, 该区域布置传感器节点个数N;
(2) 初始化CS-FOA的相关参数, 包括果蝇种群大小Sizepop, 最大迭代次数Maxgen, 单位周期迭代次数T, 搜索区间长度L;
(3) 随机初始Sizepop个果蝇的位置Wt, 根据式 (2) , 第t个果蝇的传感器节点表示为, 其中t∈[1, Sizepop], i∈[1, N];
(4) 根据式 (3) ~ (6) 计算出GW, 将GW最大的果蝇标记为最佳果蝇, 记录此果蝇的GW以及位置W:
(5) 进入迭代寻优计算, 果蝇个体根据式 (7) 确定搜索步长, 随机向各个方向搜寻.
(6) 执行步骤 (4) , 找出其中覆盖率最大的果蝇个体, 记录此果蝇的位置和覆盖率, 并将此果蝇的覆盖率与上一代最佳果蝇的覆盖率比较, 如果此果蝇覆盖率大于上一代覆盖率, 那么将此果蝇标记为最佳果蝇.最佳果蝇的位置设为节点位置, 也是下一次搜索的果蝇初始位置, 所有果蝇向此果蝇聚拢.
(7) 循环执行步骤 (5) (6) , 直至迭代次数达到Maxgen, 记录最终的结果.此时得到无线传感器网络最大的覆盖率best G和对应节点位置G_axis.

⛄二、部分源代码

%% 清空环境变量
clc;
clear;

%% 网络参数
L = 60; % 区域边长
n = 40; % 节点个数
rs = 6; % 感知半径
data = 0.4; % 离散粒度

%% FOA参数
maxgen = 500; % 迭代次数
sizepop = 25; % 种群规模
s = 0.3; % 步长

%% 随机初始化果蝇群体位置
X_axis = Lrand(1, n); % X = rand(sz1,…,szN)返回由随机数组成的 sz1×…×szN 数组
Y_axis = Lrand(1, n); % 使用公式 r = a + (b-a).*rand(N,1) 生成区间 (a,b) 内的 N 个随机数

%% 个体和浓度最大和最小值
for i = 1:sizepop
% 随机位置（第i行的全部列）
X(i, 😃 = X_axis + 2srand(1, n)-s; % 冒号：就是全部的意思，可以创建向量，为数组加下标，以及指定 for 迭代
Y(i, 😃 = Y_axis + 2srand(1, n)-s;
% 味道浓度函数(覆盖率)
Smell(i) = computeCover(X(i, 😃, Y(i, 😃, L, rs, data);
end
% 找出此果蝇群体中味道浓度最高的果蝇(求极大值)
[bestSmell, bestindex]=max(Smell); % index：返回表格或数组中的元素值，此元素由行号和列号的索引值给定
% 最佳气味浓度、果蝇位置、适应度最优位置
X_axis = X(bestindex, 😃;
Y_axis = Y(bestindex, 😃;
Smellbest = bestSmell;

%% 初始结果显示
gbest = [X_axis; Y_axis]';
disp(‘初始位置：’ ); % disp输出字符串
disp([num2str(gbest)]); % num2str把数值转换成字符串， 转换后可以使用fprintf或disp函数进行输出
disp([‘初始覆盖率：’, num2str(Smellbest)]);
% 初始覆盖图
figure;
for i = 1:n
axis([0 L 0 L]); % 限制坐标范围，axis([xmin xmax ymin ymax])，xmin和xmax分别表示在绘图时x、y轴的上下限
x = gbest(:, 1); % axis函数通常在绘图中用于设置坐标值范围
y = gbest(:, 2);
sita = 0:pi/100:2pi; % 角度[0, 2pi]，sita：角度
hold on;
p2 = fill(x(i)+rscos(sita), y(i)+rssin(sita), ‘y’); % 填充区域颜色
end
p1 = plot(gbest(:, 1), gbest(:, 2), ‘r*’);
legend([p1, p2], {‘WSN节点’, ‘覆盖区域’});
title ‘FOA-WSN初始结果’;

%% 果蝇迭代寻优
for gen = 1:maxgen
% 粒子位置和速度更新

% 根据气味浓度值寻找极值
[bestSmell, bestindex]=max(Smell);
% 保留最佳值位置
if bestSmell > Smellbest
    X_axis = X(bestindex, :);
    Y_axis = Y(bestindex, :);
    Smellbest = bestSmell;
end
% 每代最优Smell值记录到yy数组中，并记录最优迭代坐标
yy(gen) = Smellbest;
Xbest(gen, :) = X_axis;
Ybest(gen, :) = Y_axis;
% 显示迭代信息
display(['FOA: At iteration ', num2str(gen), ' the best fitness is ', num2str(yy(gen))]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14

end

%% 结果显示
gbest = [ Xbest(end, 😃; Ybest(end, 😃]';
disp(‘最优位置：’);
disp([num2str(gbest)]);
disp([‘最优覆盖率：’, num2str(yy(end))]);

⛄三、运行结果

⛄四、matlab版本及参考文献

1 matlab版本
2014a

2 参考文献
[1]尹向兵,吴良超.基于周期果蝇算法的无线传感网覆盖优化[J].赤峰学院学报(自然科学版). 2017,33(16)

3 备注
简介此部分摘自互联网，仅供参考，若侵权，联系删除