【優化覆寫】改進的雜草算法求解無線傳感器覆寫優化問題【Matlab 046期】

一、雜草算法簡介（附課題報告）

1 IWO定義

IWO是2006年由A. R. Mehrabian等提出的一種從自然界雜草進化原理演化而來的随機搜尋算法，模仿雜草入侵的種子空間擴散、生長、繁殖和競争性消亡的基本過程，具有很強的魯棒性和自适應性。

IWO算法是一種高效的随機智能優化算法，以群體中優秀個體來指導種群的進化，以正态分布動态改變标準差的方式将由優秀個體産生的子代個體疊加在父代個體周圍，再經過個體之間的競争，得到最優個體。算法兼顧了群體的多樣性和選擇力度。

2 IWO搜尋與性能

IWO相比其他的進化算法擁有更大的搜尋空間和更好的性能。

與GA相比，IWO算法簡單，易于實作，不需要遺傳操作算子，能簡單有效地收斂問題的最優解，是一種強有力的智能優化工具。

3 IWO算法實作步驟

3.1 初始化種群

一定資料的雜草初始分布在搜尋空間中，位置随機，個數根據實際情況調整；

3.2子代繁殖

分布在整個搜尋空間的父代，根據父代的适應值産生下一代種子，種子的個數由适應度值決定，适應值高的産生的種子多，低的個體産生種子數少。

3.3 空間擴散

子代個體按照一定規律分布在父代個體周圍，分布位置規律滿足正态分布（父代為軸線（均值），标準差随着代數不斷變化）。

3.4 競争淘汰

當一次繁殖的個體數超過種群數量的上限時，将子代和父代一起排序，适應值低的個體将被清除。

二、部分源代碼

% IWO
% CPSO
% IIWO
%% 清空環境變量
clear
clc

%% 網絡參數
L = 20;                         % 區域邊長
V = 24;                         % 節點個數
Rs = 2.5;                           % 感覺半徑
Rc = 5;                        % 通信半徑
Re = 0.05;                     % 感覺誤差
data = 1;                      % 離散粒度
%% 基本參數
N = 30;                    % 種群規模
dim = 2*V;               % 維數
maxgen = 300;         % 最大疊代次數
ub = L;
lb = 0;

%% 初始化種群位置
X = rand(N, dim).*(ub-lb)+lb;
for i = 1:N
    fitness(i) = fun(X(i, :), L, Rs, Re, data);
end

%% 傳入函數變量
[bestvalue_IWO, gbest_IWO, Curve_IWO] = IWO(N, maxgen, Rs, Re, L, data, X, fitness, lb, ub, dim);
[bestvalue_CPSO, gbest_CPSO, Curve_CPSO] = CPSO(N, maxgen, Rs, Re, L, data, X, fitness, lb, ub, dim);
[bestvalue_IIWO, gbest_IIWO, Curve_IIWO] = IIWO(N, maxgen, Rs, Re, L, data, X, fitness, lb, ub, dim);

%% 繪圖比較
figure;
t = 1:maxgen;
plot(t, Curve_IWO, 'ro-', t, Curve_CPSO, 'kx-', t, Curve_IIWO, 'bp-',...
    'linewidth', 2, 'linewidth', 1.5, 'MarkerSize',7, 'MarkerIndices', 1:20:maxgen);
legend('IWO', 'CPSO', 'IIWO');
xlabel '疊代次數';
ylabel '覆寫率';
function Rcov = fun(Position, L, Rs, Re, data)
%% 适應度函數：WSN的覆寫率
x = Position(1:2:end);      % 擷取x軸的坐标
y = Position(2:2:end);      % 擷取y軸的坐标
lamda1 = 0.1;                           % 感覺衰減系數
lamda2 = 0.1;
epsilon1 = 2;
epsilon2 = 2;
N = length(x);                          % 節點總個數
% 離散化區域内的點
m = 0:data:L;
n = 0:data:L;
k = 1;
for i = 1:numel(m)
    for j = 1:numel(n)
        p(k, :) = [m(i), n(j)];
        k = k+1;
    end
end
Total = size(p, 1);
% 計算覆寫率
for j = 1:size(p, 1)
    C = zeros(N, 1);
    for i = 1:N
        dij = sqrt((p(j, 1)-x(i))^2+(p(j, 2)-y(i))^2);
        if Rs-Re >= dij
            C(i) = 1;                                          % 改變覆寫狀态
        elseif Rs+Re > dij
            C(i) = exp(-lamda1*(dij-(Rs-Re))^epsilon1/((Rs+Re-dij)^epsilon2+lamda2));
        end
    end
    P(j) = 1-prod(1-C);
    % 判斷門檻值
    if P(j) < 0.75
        P(j) = 0;
    end
end
% 計算覆寫比例
Rcov = sum(P(1:end))/Total;                     
function [fitnessgbest, gbest, yy] = CPSO(N, maxgen, Rs, Re, L, data, X, fitness, lb, ub, dim)

%% 參數初始化
c1 = 2;                           % 社會認知參數
c2 = 2;                           % 自我認知參數
Vmax = 2;                      % 最大速度
Vmin = -2;                      % 最小速度
u = 4;                          % 混沌系數
W = 0.8;                % 慣性權重

% 初始化速度
V = rand(N, dim).*(Vmax-Vmin)+Vmin;
%% 個體極值和群體極值
[bestfitness, bestindex] = max(fitness);
gbest = X(bestindex, :);        % 全局最佳
zbest = X;                            % 個體最佳
fitnessgbest = bestfitness;    % 全局最佳适應度值
fitnesszbest = fitness;           % 個體最佳适應度值

%% 初始結果顯示
x = gbest(1:2:end);
y = gbest(2:2:end);
disp('初始位置：' );
for i = 1:dim/2
    disp([num2str(x(i)), '     ', num2str(y(i))]);
end
disp(['初始覆寫率：', num2str(fitnessgbest)]);
% 初始覆寫圖
figure;
for i = 1:dim/2
    axis([0 L 0 L]);            % 限制坐标範圍
    sita = 0:pi/100:2*pi;   % 角度[0, 2*pi]
    hold on;
    fill(x(i)+Rs*cos(sita), y(i)+Rs*sin(sita), 'b');
    plot(x(i)+Rs*cos(sita), y(i)+Rs*sin(sita), 'b');
end
plot(x, y, 'r+');
title '初始部署';

%% 疊代尋優
for i = 1:maxgen
    
    for j=1:N
        % 速度更新
        V(j, :) = W*V(j, :) + c1*rand*(zbest(j, :)-X(j, :)) + c2*rand*(gbest-X(j, :));
        V(j, V(j, :) > Vmax) = Vmax;
        V(j, V(j, :) < Vmin) = Vmin;
        % 位置更新
        X(j, :) = X(j, :)+V(j, :);
        X(j, X(j, :) > ub) = ub;
        X(j, X(j, :) < lb) = lb;
        % 計算适應度值
        fitness(j)=fun(X(j, :), L, Rs, Re, data);
    end
    
    for j = 1:N
        % 個體最優更新
        if fitness(j) > fitnesszbest(j)
            zbest(j, :) = X(j, :);
            fitnesszbest(j) = fitness(j);
        end
        % 群體最優更新
        if fitness(j) > fitnessgbest
            gbest = X(j, :);
            fitnessgbest = fitness(j);
        end
    end
    %% 對粒子群最優位置進行混沌優化
    Y(1, :) = (gbest-lb)/(ub-lb);           
    % logistic
    for t = 1:N-1 
        for e = 1:dim
            Y(t+1, e) = u*Y(t, e)*(1-Y(t, e));
        end
    end
    Y = Y.*(ub-lb)+lb;
    for j = 1:N
        fit(j) = fun(Y(j, :), L, Rs, Re, data);
    end
    % 尋找最優混沌可行解矢量
    [ybestfitness, ybestindex] = max(fit);
    ran = 1+fix(rand()*N);              % 産生一随機數1~N之間
    X(ran, :) = Y(ybestindex, :);
    fitness(ran) = ybestfitness;
    % 每代最優解存入yy數組
    yy(i) = fitnessgbest;
    
    disp(['At iteration ', num2str(i), ', the best fitness is ', num2str(yy(i))]);
end


%% 結果顯示
x = gbest(1:2:end);
y = gbest(2:2:end);
disp('最優位置：' );
for i = 1:dim/2
    disp([num2str(x(i)), '     ', num2str(y(i))]);
end
disp(['最優覆寫率：', num2str(yy(end))]);
%% 繪圖
figure;
plot(yy, 'r', 'lineWidth', 2);          %  畫出疊代圖
title('算法訓練過程', 'fontsize', 12);
xlabel('疊代次數', 'fontsize', 12);
ylabel('網絡覆寫率', 'fontsize', 12);
figure
for i = 1:dim/2
    axis([0 L 0 L]);            % 限制坐标範圍
    sita = 0:pi/100:2*pi;   % 角度[0, 2*pi]
    hold on;
    fill(x(i)+Rs*cos(sita), y(i)+Rs*sin(sita), 'k');
end
plot(x, y, 'r+');
title 'CPSO優化覆寫';

           

三、運作結果

四、matlab版本及參考文獻

1 matlab版本

2014a

2 參考文獻

[1] 包子陽,餘繼周,楊杉.智能優化算法及其MATLAB執行個體（第2版）[M].電子工業出版社，2016.

[2]張岩,吳水根.MATLAB優化算法源代碼[M].清華大學出版社，2017.

[3]周品.MATLAB 神經網絡設計與應用[M].清華大學出版社，2013.

[4]陳明.MATLAB神經網絡原理與執行個體精解[M].清華大學出版社，2013.

[5]方清城.MATLAB R2016a神經網絡設計與應用28個案例分析[M].清華大學出版社，2018.