首页分享【智能优化算法】基于花朵授粉算法求解多目标目优化问题附matlab代码

【智能优化算法】基于花朵授粉算法求解多目标目优化问题附matlab代码

来源：花匠小妙招时间：2024-12-23 10:03

1 简介

花朵授粉算法（ Flower Pollination Algorithm，FPA）是由英国剑桥大学学者Yang 于2012年提出的，其基本思想来源于对自然界花朵自花授粉、异花授粉的模拟，是一种新的元启发式群智能随机优化技术。

据统计，目前在自然界中被人类发现的植物大约有 37 万种，显花植物大约占有 20 万种，而其中 80% 的植物依靠生物授粉繁衍后代。花植物已经进化了大约 1． 25 亿年，在演化过程中，花朵授粉在花植物繁衍过程中承担着举足轻重的作用，对于花植物，如果没有花，很难想象植物世界是个什么样子。人类的发展和生存与跟花植物也是息息相关的，例如人们生活中吃的苹果等水果都是花朵授粉的结果。花朵授粉是通过花粉的传播来实现，而花粉的传播主要是靠昆虫及动物来完成。在实际授粉过程中，一些花朵仅仅吸引和依靠一种特定的昆虫来成功授粉，即一些花朵与传粉者之间形成了一种非常特别的花—传粉者伙伴关系。授粉形式主要有非生物和生物两种，大概 90% 的显花植物是属于生物授粉植物，即花粉主要是通过动物和昆虫来传播而实现繁衍后代。大约 10% 的显花植物是属于非生物授粉植物，不需要任何传粉者来传播花粉，而是通过自然风或者扩散途径来完成传粉，以实现子代的繁殖。在依赖生物传粉的显花植物中大约有 85% 的植物是由蜜蜂完成传粉的，蜜蜂在实际传粉中可能只对一些特定花植物进行传粉，而忽视其他种类的花植物，这样以便以最小的代价获得最大的收益。同时对于一些花植物而言，也获得更多的传粉机会，繁衍更多的后代。根据显花植物的授粉对象不同，可分为异花授粉和自花授粉两种。在一般情况下，异花授粉是两性花，一般一朵花的雌蕊接受的花粉是另一朵花的雄蕊的花粉，这就是所谓的异花授粉。自花授粉是显花植物成熟的花粉粒传到同一朵花的柱头上或同一种显花植物的不同花之间进行传粉，并能正常地受精结实的过程。由于传粉者鸟、蜜蜂等能飞行很长的距离，故异花授粉可以发生在远距离的地方，这种方式称为全局授粉。另外，鸟和蜜蜂具有 Levy 飞行的行为，跳或飞行的步长服从 Levy飞行分布。而自花授粉称为局部授粉。

花朵授粉算法是模拟自然界中显花植物花朵传粉的过程，该算法的理想条件假设如下:

a) 生物异花授粉是带花粉的传粉者通过 Levy 飞行进行的全局授粉过程。

b) 非生物自花授粉是局部授粉过程。

c) 花的常性可以被认为是繁衍概率，繁衍概率与参与的两朵花的相似性成比例关系。

d) 转换概率 p∈［0，1］控制全局授粉与局部授粉之间的转换，由于物理上的邻近性和风等其他因素的影响，局部授粉在整个授粉活动中是一个非常重要的部分 p。

然而，在现实的自然界中，每一棵显花植物可以开好多朵花，每朵花产生数百万甚至数十亿的花粉配子。但是，为了把问题简单化，假设每棵显花植物仅仅只开一朵花，且每朵花仅产生一个花粉配子。因此，问题经过简化后，意味着一朵花或一个配子就对应于优化问题中的一个解。

2 部分代码

%% The sorting of nondomninated solutions from a population of 2*npop %

%% (New solutions+old population) to form a population of npop solutions %

%% ---------------------------------------------------------------------- %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function sorted_x = solutions_sorting(x, m, ndim)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Inputs and outputs are the extended solutions x with a dimension of %

%% npop by (ndim+m+2). The objective values are already included in x. %

% More specifically, the first ndim columns are the actual solutions or

% variable values (1:ndim), followed by the m columns of objective values.

% Then, the next column (i.e.,ndim+m+1) corresponds to the ranks, whereas

% the final column (i.e., ndim+m+2) records the crowd distances.

% ----------------------------------------------------------------------- %

%% Get the parameters from the inputs such as the size of input population

npop=size(x,1); % Population size

frontRank=1; % Pareto frontRank (counter) initialization

Rcol=ndim+m+1; % Store the ranks in the column Rcol=ndim+m+1

% Define the Parato Front as a class (PF) and initilization of xSol

PF(frontRank).R=[]; xSol=[];

%% The main non-dominated sorting starts here %%%%%%%%%%%%%%%%%

for i = 1:npop,

% Set the number (initially, 0) of solutions dominating this solution

xSol(i).n=0;

% Find all the solutions (that dominated by this solution)

xSol(i).q=[];

% Sorting into 3 categories: better (minimization), equal & otherwise

for j=1:npop,

% Definte 3 counters for 3 categories

ns_categ_1=0; ns_categ_2=0; ns_categ_3=0;

for k=1:m, % for all m objectives

% Update the counters for 3 different categories

if (x(i,ndim+k) < x(j,ndim+k)), % better/non-dominated

ns_categ_1=ns_categ_1+1;

elseif (x(i,ndim+k)==x(j,ndim+k)), % equal

ns_categ_2=ns_categ_2+1;

else % dominated

ns_categ_3=ns_categ_3+1;

end

end % end of k

% Update the solutions in their class

if ns_categ_1==0 && ns_categ_2 ~= m

xSol(i).n=xSol(i).n+1;

elseif ns_categ_3 == 0 && ns_categ_2 ~= m

xSol(i).q=[xSol(i).q j];

end

end % end of j

%% Record/Udpate the Pareto Front

if xSol(i).n==0,

x(i,Rcol)=1; % Update the Rank #1 (i.e., the Pareto Front)

PF(frontRank).R = [PF(frontRank).R i];

end

end % end of i=1:npop (The first round full rank-sorting process)

% Update the rest frontRanks (close, but not on the Pareto Front)

while ~isempty(PF(frontRank).R),

nonPF=[]; % Intialization the set

N=length(PF(frontRank).R);

for i=1 :N,

% Get the solution/list

Sol_tmp_q=xSol(PF(frontRank).R(i)).q;

% If not empty, update

if ~isempty(xSol(Sol_tmp_q))

for j = 1:length(Sol_tmp_q),

% Get the solutions dominated by the current solution

Sol_tmp_qj=xSol(PF(frontRank).R(i)).q(j);

xSol(Sol_tmp_qj).n=xSol(Sol_tmp_qj).n-1;

if xSol(Sol_tmp_qj).n==0

x(Sol_tmp_qj, Rcol)=frontRank + 1;

nonPF = [nonPF Sol_tmp_qj];

end

end % end of j

end

end % end of i

frontRank=frontRank+1;

PF(frontRank).R=nonPF;

end % end of PF(frontRank)

% Now carry out the sorting of ranks and then update

[~,frontRanks_Index]=sort(x(:, Rcol));

Sorted_frontRank=x(frontRanks_Index,:);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Evaluate the crowding distances for each solution for each frontRank %

% That is, all the non-domonated solutions on the Pareto Front. %%%%%%%%%%

Qi=0; % Initialize a counter

for frontRank=1:(length(PF)-1),

% Define/initialize a generalized distance matrix

dc = []; past_Q=Qi+1;

for i=1:length(PF(frontRank).R),

dc(i,:)=Sorted_frontRank(Qi+i,:);

end

Qi=Qi+i;

% Solutions are sorted according to their fitness/objective values

fobj_sorted=[];

for i=1:m,

[~, f_Rank]=sort(dc(:,ndim+i));

fobj_sorted=dc(f_Rank,:);

% Find the max and min of the fobj values

fobj_max=fobj_sorted(length(f_Rank), ndim+i);

fobj_min=fobj_sorted(1, ndim+i);

% Calculate the range of the fobj

f_range=fobj_max-fobj_min;

% If the solution is at the end/edge, set its distance as infinity

dc(f_Rank(length(f_Rank)), Rcol+i)=Inf;

dc(f_Rank(1), Rcol+i) = Inf;

for j=2:length(f_Rank)-1,

fobj2=fobj_sorted(j+1,ndim + i);

fobj1=fobj_sorted(j-1,ndim + i);

% Check the range or special cases

if (f_range==0),

dc(f_Rank(j), Rcol+i)=Inf;

else

% Scale the range for distance normalization

dc(f_Rank(j),Rcol+i)=(fobj2-fobj1)/f_range;

end

end % end of j

end % end of i

% Calculate and update the crowding distances on the Pareto Front

dist = []; dist(:,1)=zeros(length(PF(frontRank).R),1);

for i=1:m,

dist(:,1)=dist(:,1)+dc(:, Rcol+i);

end

% Store the crowding distrance (dc) in the column of Rcol+1=ndim+m+2

dc(:, Rcol+1)=dist; dc=dc(:,1:Rcol+1);

% Update for the output

xy(past_Q:Qi,:)=dc;

end % end of all ranks search/update

sorted_x=xy(); % Output the sorted solutions

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% end of non-dominated sorting %%%%%%%%%%%%%%

3 仿真结果

4 参考文献

[1]张迷, 贺兴时. 多目标优化问题的花授粉算法改进[J]. 西安工程大学学报, 2016, 30(3):7.

博主简介：擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真，相关matlab代码问题可私信交流。

部分理论引用网络文献，若有侵权联系博主删除。

【智能优化算法】基于花朵授粉算法求解多目标目优化问题附matlab代码