网站建设的课程设计报告,网站自建系统,网站公司深圳,wordpress付费阅读文章功能1 理论基础 在实际工程优化问题中#xff0c;多数问题是多目标优化问题。相对于单目标优化问题#xff0c;多目标优化问题的显著特点是优化各个目标使其同时达到综合的最优值。然而#xff0c;由于多目标优化问题的各个目标之间往往是相互冲突的#xff0c;在满足其中一个…1 理论基础 在实际工程优化问题中多数问题是多目标优化问题。相对于单目标优化问题多目标优化问题的显著特点是优化各个目标使其同时达到综合的最优值。然而由于多目标优化问题的各个目标之间往往是相互冲突的在满足其中一个目标最优的同时其他的目标往往可能会受其影响而变得很差。因此一般适用于单目标问题的方法难以用于多目标问题的求解。 多目标优化问题很早就引起了人们的重视现已经发展出多种求解多目标优化问题的方法。多目标优化问题求解中最重要的概念是非劣解和非劣解集两者的定义如下。 非劣解(noninferior solution):在多目标优化问题的可行域中存在一个问题解若不存在另一个可行解使得一个解中的目标全部劣于该解则该解称为多目标优化问题的非劣解。所有非劣解的集合叫做非劣解集(noninferior set)。在求解实际问题中过多的非劣解是无法直接应用的决策者只能选择其中最满意的一个非劣解作为最终解。最终解主要有三种方法第一种是求非劣解的生成法包括加权法、约束法、加权法和约束法结合的混合法以及多目标遗传算法即先求出大量的非劣解构成非劣解的一个子集然后按照决策者的意图找出最终解。第二种为交互法主要为求解线性约束多目标优化的Geoffrion法不先求出很多的非劣解而是通过分析者与决策者对话的方式逐步求出最终解。第三种是事先要求决策者提供目标之间的相对重要程度算法以此为依据将多目标问题转化为单目标问题进行求解。 利用进化算法求解多目标优化问题是近年来的研究热点1967年Rosenberg就建议采用基于进化的搜索来处理多目标优化问题但没有具体实现。1975年Holland提出了遗传算法10年后Schaffer提出了矢量评价遗传算法第一次实现了遗传算法与多目标优化问题的结合。1989年Goldberg在其著作《Genetic Algorithms for Search, Optimization, and Machine Learning》中提出了把经济学中的Pareto理论与进化算法结合来求解多目标优化问题的新思路对于后续进化多目标优化算法的研究具有重要的指导意义。目前采用多目标进化算法求解多目标问题已成为进化计算领域中的一个热门方向粒子群优化、蚁群算法、人工免疫系统、分布估计算法、协同进化算法、进化算法等一些新的进化算法陆续被用于求解多目标优化问题。本案例采用多目标粒子群算法求解多目标背包问题。 2 案例背景
2.1 问题描述 假设存在五类物品每类物品中又包含四种具体物品现要求从这五种类别物品中分别选择一种物品放入背包中使得背包内物品的总价值最大总体积最小并且背包的总质量不超过92 kg。背包问题的数学模型为 2.2 算法流程 基于粒子群算法的二维多目标搜索算法流程如图10-1所示。其中种群初始化模块随机初始化粒子的位置x和速度v,适应度值计算是指根据适应度值计算公式计算个体适应度值粒子最优更新模块根据新的粒子位置更新个体最优粒子。非劣解集更新模块根据新粒子支配关系筛选非劣解。粒子速度和位置更新模块根据个体最优粒子位置和全局粒子位置更新粒子速度和位置。 2.3 适应度计算 粒子适应度值参考式(10-1),每个个体的适应度值有两个即价值和体积同时个体须满足质量约束。 2.4 筛选非劣解集 筛选非劣解集主要分为初始筛选非劣解集和更新非劣解集。初始筛选非劣解集是指在粒子初始化后当一个粒子不受其他粒子支配(即不存在其他粒子的Px,Rx,均优于该粒子)时把粒子放入非劣解集中并且在粒子更新前从非劣解集中随机选择一个粒子作为群体最优粒子。更新非劣解集是指当新粒子不受其他粒子以及当前非劣解集中粒子的支配时把新粒子放入非劣解集中并且每次粒子更新前都从非劣解集中随机选择一个粒子作为群体最优粒子。 2.5 粒子速度和位置更新 粒子更新公式如下 2.6 粒子最优 粒子最优包括个体最优粒子和群体最优粒子其中个体最优粒子的更新方式是从当前新粒子和个体最优粒子中选择支配粒子当两个粒子都不是支配粒子时从中随机选择一个粒子作为个体最优粒子。群体最优粒子为从非劣解集中随机选择的一个粒子。 3 MATLAB程序实现 根据多目标搜索算法原理在MATLAB中实现基于粒子群算法的多目标搜索算法。 %% 该函数演示多目标perota优化问题
%清空环境
clc
clearload data%% 初始参数
objnumsize(P,1); %类中物品个数
weight92; %总重量限制%初始化程序
Dim5; %粒子维数
xSize50; %种群个数
MaxIt200; %迭代次数
c10.8; %算法参数
c20.8; %算法参数
wmax1.2; %惯性因子
wmin0.1; %惯性因子xunidrnd(4,xSize,Dim); %粒子初始化
vzeros(xSize,Dim); %速度初始化xbestx; %个体最佳值
gbestx(1,:); %粒子群最佳位置% 粒子适应度值
pxzeros(1,xSize); %粒子价值目标
rxzeros(1,xSize); %粒子体积目标
cxzeros(1,xSize); %重量约束% 最优值初始化
pxbestzeros(1,xSize); %粒子最优价值目标
rxbestzeros(1,xSize); %粒子最优体积目标
cxbestzeros(1,xSize); %记录重量以求约束% 上一次的值
pxPriorzeros(1,xSize);%粒子价值目标
rxPriorzeros(1,xSize);%粒子体积目标
cxPriorzeros(1,xSize);%记录重量以求约束%计算初始目标向量
for i1:xSizefor j1:Dim %控制类别px(i) px(i)P(x(i,j),j); %粒子价值rx(i) rx(i)R(x(i,j),j); %粒子体积cx(i) cx(i)C(x(i,j),j); %粒子重量end
end
% 粒子最优位置
pxbestpx;rxbestrx;cxbestcx;%% 初始筛选非劣解
flj[];
fljx[];
fljNum0;
%两个实数相等精度
tol1e-7;
for i1:xSizeflag0; %支配标志for j1:xSize if j~iif ((px(i)px(j)) (rx(i)rx(j))) ||((abs(px(i)-px(j))tol)... (rx(i)rx(j)))||((px(i)px(j)) (abs(rx(i)-rx(j))tol)) || (cx(i)weight) flag1;break;endendend%判断有无被支配if flag0fljNumfljNum1;% 记录非劣解flj(fljNum,1)px(i);flj(fljNum,2)rx(i);flj(fljNum,3)cx(i);% 非劣解位置fljx(fljNum,:)x(i,:); end
end%% 循环迭代
for iter1:MaxIt% 权值更新wwmax-(wmax-wmin)*iter/MaxIt;%从非劣解中选择粒子作为全局最优解ssize(fljx,1); indexrandi(s,1,1); gbestfljx(index,:);%% 群体更新for i1:xSize%速度更新v(i,:)w*v(i,:)c1*rand(1,1)*(xbest(i,:)-x(i,:))c2*rand(1,1)*(gbest-x(i,:));%位置更新x(i,:)x(i,:)v(i,:);x(i,:) rem(x(i,:),objnum)/double(objnum);index1find(x(i,:)0);if ~isempty(index1)x(i,index1)rand(size(index1));endx(i,:)ceil(4*x(i,:)); end%% 计算个体适应度pxPrior(:)0;rxPrior(:)0;cxPrior(:)0;for i1:xSizefor j1:Dim %控制类别pxPrior(i) pxPrior(i)P(x(i,j),j); %计算粒子i 价值rxPrior(i) rxPrior(i)R(x(i,j),j); %计算粒子i 体积cxPrior(i) cxPrior(i)C(x(i,j),j); %计算粒子i 重量endend%% 更新粒子历史最佳for i1:xSize%现在的支配原有的替代原有的if ((px(i)pxPrior(i)) (rx(i)rxPrior(i))) ||((abs(px(i)-pxPrior(i))tol)... (rx(i)rxPrior(i)))||((px(i)pxPrior(i)) (abs(rx(i)-rxPrior(i))tol)) || (cx(i)weight) xbest(i,:)x(i,:);%没有记录目标值pxbest(i)pxPrior(i);rxbest(i)rxPrior(i);cxbest(i)cxPrior(i);end%彼此不受支配随机决定if ~( ((px(i)pxPrior(i)) (rx(i)rxPrior(i))) ||((abs(px(i)-pxPrior(i))tol)... (rx(i)rxPrior(i)))||((px(i)pxPrior(i)) (abs(rx(i)-rxPrior(i))tol)) || (cx(i)weight) )... ~( ((pxPrior(i)px(i)) (rxPrior(i)rx(i))) ||((abs(pxPrior(i)-px(i))tol) (rxPrior(i)rx(i)))...||((pxPrior(i)px(i)) (abs(rxPrior(i)-rx(i))tol)) || (cxPrior(i)weight) )if rand(1,1)0.5xbest(i,:)x(i,:);pxbest(i)pxPrior(i);rxbest(i)rxPrior(i);cxbest(i)cxPrior(i);endendend%% 更新非劣解集合pxpxPrior;rxrxPrior;cxcxPrior;%更新升级非劣解集合ssize(flj,1);%目前非劣解集合中元素个数%先将非劣解集合和xbest合并pppxzeros(1,sxSize);rrrxzeros(1,sxSize);cccxzeros(1,sxSize);pppx(1:xSize)pxbest;pppx(xSize1:end)flj(:,1);rrrx(1:xSize)rxbest;rrrx(xSize1:end)flj(:,2);cccx(1:xSize)cxbest;cccx(xSize1:end)flj(:,3);xxbestzeros(sxSize,Dim);xxbest(1:xSize,:)xbest;xxbest(xSize1:end,:)fljx;%筛选非劣解flj[];fljx[];k0;tol1e-7;for i1:xSizesflag0;%没有被支配%判断该点是否非劣for j1:xSizes if j~iif ((pppx(i)pppx(j)) (rrrx(i)rrrx(j))) ||((abs(pppx(i)-pppx(j))tol) ... (rrrx(i)rrrx(j)))||((pppx(i)pppx(j)) (abs(rrrx(i)-rrrx(j))tol)) ...|| (cccx(i)weight) %有一次被支配flag1;break;endendend%判断有无被支配if flag0kk1;flj(k,1)pppx(i);flj(k,2)rrrx(i);flj(k,3)cccx(i);%记录非劣解fljx(k,:)xxbest(i,:);%非劣解位置endend%去掉重复粒子repflag0; %重复标志k1; %不同非劣解粒子数flj2[]; %存储不同非劣解fljx2[]; %存储不同非劣解粒子位置flj2(k,:)flj(1,:);fljx2(k,:)fljx(1,:);for j2:size(flj,1)repflag0; %重复标志for i1:size(flj2,1)result(fljx(j,:)fljx2(i,:));if length(find(result1))Dimrepflag1;%有重复endend%粒子不同存储if repflag0 kk1;flj2(k,:)flj(j,:);fljx2(k,:)fljx(j,:);endend%非劣解更新fljflj2;fljxfljx2;end%绘制非劣解分布
plot(flj(:,1),flj(:,2),o)
xlabel(P)
ylabel(R)
title(最终非劣解在目标空间分布)
disp(非劣解flj中三列依次为PRC) 3.1 仿真结果 本案例问题中每类物品的价值、体积和质量如表10-1所列。 从每类物品中选择一个物品放入背包使背包的总价值最大体积最小并且背包总质量小于92kg。粒子群算法参数为粒子个数为50,迭代次数为200,最终得到的非劣解在目标空间中的分布如图10-2所示。 由图10-2可知算法搜索到的非劣解构成了Pareto面算法搜索取得了很好的效果。 4 延伸阅读 多目标搜索算法相对于单目标算法来说更加贴近于实际问题求解结果更具有参考价值。通过多目标搜索算法最终得到的不是一个最优解而是一个非劣解集需要从非劣解集中根据实际问题的需要选择一个解作为该问题的最终解。常用的基于进化算法的多目标搜索算法除了本案例介绍的方法之外还有基于遗传算法的多目标搜索算法、基于免疫算法的多目标搜索算法等。
