合肥工业大学系统工程导论第5章 系统优化

第5章系统优化前几章分别介绍了一些传统系统优化的方法，如线性规划、非线性规划、动态规划、图论等。本章侧重于介绍现代优化算法和大系统的分解与协调。一、现代优化算法传统优化算法与现代优化算法在系统设计与规划过程中，通常需要面临所谓的“系统优化”问题，即在一定约束条件下，选择最合理的、达到某一（或某些）目标的最优解，例如生产计划安排中的最大获利问题、投资决策问题、油管铺设中的最短路问题等。系统优化问题是一个古老的课题，早在17世纪在欧洲就有人提出了各种求最大（小）值问题。直到20世纪40年代，随着科学的发展而产生了一系列如线性规划、非线性规划、动态规划、图论等传统优化算法。这些算法在应用时，要求：Q选择表示优化因素的独立••变量；Q定义要优化的系统的性能指标和约束条件；Q写出表示各种变量之间关系的数学模型。随着20世纪80年代初期模拟退火、遗传算法和人工神经元网络算法的兴起，人们对某些复杂的优化问题及其算法进行了深入研究，从而产生了现代优化算法。这些算法是一种多学科综合性的解决问题方法，其主要应用对象是系统优化中的难解问题，即系统模型过于复杂而无法用明确的解析方程来描述的问题。启发式算法以一定的直观基础构造成的算法，称为启发式算法。启发式算法是相对于最优化算法提出的，它是在可接受的计算费用内寻求最好解（但不一定是最优解）的一种技术。在多数情况下，由于无法明确找出问题的最优解，所以也就无法表明所得解与最优解的近似程度。因此，启发式算法的特点是不考虑算法所得的最好解与最优解的偏离程度。例1（背包问题的贪婪算法）有一个容积为b的背包，现有n个体积分别为q.，价值分别为c（i=1,2,…,n）的物品待装包，试问如何使装包物品的价值达到最大？'解'对于该背包问题可构造以下贪婪算法：（1）对物品按“单位体积价值最大的优先装包”的原则，以c,/a.从大到小进行排列，不妨把排列记成｛1,2,…,n｝，并令k=1；（2）若勇1ax+ax<b，则xk=1（装包）；否则，xk=0（不装包）；iikki=1（3）k=k+1，若k=n±1时，算法停止；否则，返回（2）。故（X],x2，…,xn）为该贪婪算法的所得解。可见，这种启发式算法非常直观，且易操作。启发式算法的优点：Q数学模型简单；Q直观且简单易行；Q速度快；Q程序易于修改等。启发式算法的缺点：Q不能确保求得最优解；Q计算结果表现不稳定而造成不可信。启发式算法的分类（参见P99）：Q一步算法；Q改进的迭代算法；Q数学规划算法；••••••••Q现代优化算法。遗传算法遗传算法是根据生物进化的模型而提出的一种现代优化算法。由于最优化问题的求解过程是从众多的可行解中选出的最优解，而生物进化中的“适者生存”规律是使最有生存能力的染色体以最大的可能生存下来，这种相似性就使得遗传算法可以在优化问题中得以应用。遗传算法的生物进化特征遗传算法主要借鉴了生物进化的以下特征：.••••••••••••••••.Q生物进化实质上是发生在染色体上；Q选择：按自然选择规律确定染色体的生存或淘汰，即适者生存、优胜劣汰；Q遗传：当染色体结合时，双亲遗传基因的结合会使子代保持父代的特征；Q变异：当染色体结合后，随机的变异会造成子代与父代的特征又有所不同。遗传算法的主要步骤仿照生物遗传的概念，可以得到遗传算法的主要步骤如下：Q首先，对优化问题的解进行编码为了便于表达优化问题的解和进行遗传运算，就必须对优化问题的解进行编码，且一个解的编码称为一个染色体，组成编码的元素称为基因。Q其次，构造和应用适应函数适应函数通常是依据优化问题的目标函数来决定的。适应函数确定后，由适应函数值所决定的概率分布进而确定生存或淘汰的染色体(即解的编码)，生存下来的染色体组成一个可以繁衍下一代的群体一一种群(即一组解)。Q再次，进行编码的交叉通过编码的交叉来实现染色体的结合(即编码的组合)，从而繁衍出新的下一代(即产生新的解)。Q最后，产生变异通过基因变异(即编码的某个元素分量发生变化)使某些解的编码发生变化，从而使这些解具有更大的遍历性(适应性)。遗传算法与生物遗传概念的对应关系参见P101表5-1所示。例2用遗传算法求解maxf(x)=x2,0<x<31且x为整数。解第一步，选择解的编码，并选取初始群体以及群体中的个体数量(即群体维数)通常，表示解的简单编码是二进制编码，即0或1组成的字符串。由于变量x的最大值是31<32=25，因此可以采用5位二进制编码来表示优化问题的解，例如10000—16，11111—31，01001—9，00010—2上述编码就称为染色体。编码中的每个分量称为基因，且每个基因只有两种状态0或1。注意：若本例是对连续变量求解，如x£[0,1]且对解的误差要求是1/32=1/25,则可采用5位二进制编码，而该编码与十进制的对应关系为(参见P103例5.4)(abcde)(abcde)^|+—+—|I863JJ。模拟生物进化来构造一个初始群体，这里随机取4个染色体(即编码)组成一个群体，如x1=(00000)、x2=(11001)、x3=(01111)、x4=(01000)，且群体的个体数为4。第二步，确定适应函数一般可依据目标函数来确定适应函数，如适应函数fitness(x)=f(x)=x2,于是初始群体中各编码的适应函数值分别为fitness(x1)=0，fitness(x2)=252=625，fitness(x3)=152=225，fitness(x4)=82=64若定义第Z个个体(即编码)入选种群的概率(即生存概率)为fitness(x)「Zfitness(x)j则初始群体中各编码入选种群的概率分别为p(x1)=0,p(x2)=0.684,P(X3)=0.246,p(x4)=0.070显然，染色体个体的适应函数值越大，其生存概率也越大，则越有可能入选种群。若群体中选择4个个体成为种群，则最有可能竞争入选的个体(即编码)是x2=(11001)，x2=(11001)，x3="11)，x4=(01000)种群的选取方式通常每次都可能不同，在计算过程中无法预测哪一次的选择会获得更好的结果，因而这种选取方式在某种程度上就称为轮盘赌。第三步，使种群中染色体(即编码)进行交叉组合种群选定后，其染色体个体进行交叉组合时，首先要考虑交叉规则，如双亲遗传法、主个体副个体规则、单亲遗传规则等；其次还应考虑交叉位置的选取、交叉概率等细节问题。本例中，采用以下简单交叉的方式进行组合：X2=(11〔001)]y=(11111)X3=(01111)]y2=(01001)X2=(11*01)1y=(11I000)x=(01000)y4=(01001)用分隔符“I”表示交叉位置，即交换第二个位置以后的基因，从而得到交叉组合后的染色体y「y2、y3和y4。第四步，产生变异变异是扩大染色体选择范围的一个重要手段。通常，遗传算法实现变异的方法是赋予每个基因一个相同的相对较小的变异概率，通过随机模拟来决定在某个基因是否发生变异。本例中，若交叉后的染色体中只有y4的第一个基因发生变异，则变成y4'=(11001)。第五步，将变异后的个体组成新的群体，重复第二~四步，直至得到满足要求的解第六步，对最优解进行解码由于解码和编码是相对应的，所以可按编码规则将所得解进行解码。由此可见，在应用遗传算法解决实际问题时应注意的问题有(参见P103〜104)：.••••••••••••••••••.Q确定解的编码和解码规则；Q选取初始群体和群体维数；Q确定适应函数；Q确定种群、个体交叉和个体变异三个遗传算子。遗传算法小结(参见P102)简单的遗传算法可理解为是求解目标函数最大的优化问题。其算法描述如下：第一步，选择问题的一个编码，给出一个含有N个染色体的初始群体pop(r)，并令t=1；注意：。通常采用0-1二进制编码，且解码与编码的规则相同；Q初始群体随机选取且群体的维数为常数，该常数有时与遗传代数有关；第二步，对群体pop(t)中的每一个染色体pop.(t)，计算其相应的适应函数值f.=fitness(pop.(t))注意：通常选取适应函数与目标函数相同。第三步，若满足停止规则，则算法停止；否则，计算各染色体pop.(t)的生存概率P=.,i=1,2,,NiNZfjj=1并按生存概率分布，从pop(r)中随机选一些染色体构成一个种群newpop(r+1)={pop,(r)lj=1,2,…，N}注意：Q可重复选择pop(£)中的某个元素组成种群newpop(f+1)，如例2中选取两次X2;②按轮盘赌方法选取染色体个数与初始群体pop(t)相同的种群；第四步，以交叉概率心使种群中的各染色体交叉，得到交叉群体crosspop(r+1)；注意：通常按常规交叉法进行交叉，即一对染色体按随机位交换其后的所有基因。第五步，以较小概率p，使交叉群体中某染色体的一个基因发生变异，并形成变异群体mutpop(r+1)；注意：通常染色体中的每个基因都以同样相对较小的概率发生变异。第六步，令t=r+1，形成一个新的群体pop(r)=mutpop(r)，并返回第二步；第七步，重复第2〜6步，直到满足求解规则要求，则算法停止并进行解码。遗传算法的特点与传统优化算法相比，遗传算法的优越性体现在(参见P104)：.•••••••••.Q遗传算法适合于求解带有多参数、多变量、多目标和在多区域但连续性较差的NP-hard优化问题，是一种具有普适性的数值求解方法；Q遗传算法在求解许多组合优化问题时，不需要对问题有很深入的了解和有很强的求解技巧，如排序、路线调度、布局等；Q遗传算法与其他求解问题的启发式算法之间有较好的兼容性。二、大系统的分解与协调所谓“大系统”，通常是指系统变量、阶次及约束条件的规模都较大的系统。处理大系统优化问题的基本思路是：对大系统进行分解，即把总系统划分成若干个子系统，从而使被处理的系统降阶、降维，达到易于处理的目的。因为由大系统分解出的各子系统之间通常存在耦合关联，所以在大系统分解后必须注意在总体目标和约束条件下进行协调。由此可见，大系统优化的核心是大系统的分解/协调。其原则是：在上级系统对下级子系统的协调下，获得总体系统的最优解。大系统分解/协调•••・原理如图1所示(参见P110图5-5)。图1大系统分解/协调示意图(a.为协调变量，0，.为反馈变量)例3(生产管理问题)某总公司下属两个分公司分别生'产两种产品，设子公司1的产量为气，子公司2的产量为％，每种产品单位产量的产值均为10个单位，两个子公司的生产能力限制分别为4和3。如果原材料供应紧张，每生产1个单位％需要消耗1个单位的原材料，生产1个单位扬消耗2个单位的原材料，总原材料限制为8个单位，试问该如何安排生产计划，使全公司的产值最大？解该公司生产优化问题的数学模型为maxZ=10x+10xfx<4x2<3|x+2x<8Ix,x>0112方法1:对耦合条件进行分解/协调这种方法的思路是对耦合条件进行分解与协调。既然总资源约束是8,那么就把8分成b1和b2，并将b1、b2分别分给子公司1和子公司2,这时总系统就分解为两个“独立”的子系统，如图2所示（参见P106图5-3）。图2按耦合条件分解现在原问题就转化为如何确定各子公司资源约束b]和b2，使全公司的总产值Z—max,其实质就是资源优化分配问题。由分析可知，听、b2的可行分配方案如下：方案lb1=2,b2=6则两个子公司生产优化结果分别是x】=2，Z[=20x2=3，Z2=30可得公司总产值Z=Z1+Z2=50方案2b1=3,b2=5则两个子公司生产优化结果分别是了1=3,Z[=30x2=2,Z2=25可得公司总产值Z=Z1+Z2=55方案3b1=4,b2=4则两个子公司生产优化结果分别是x1=4,Z1=40x2=2,Z2=20可得公司总产值Z=Z1+Z2=60从上述方案中可以看出，增大b1的配额（b2的配额相应减少）会使系统总体收益提高，那么如果继续提高b1配额，其结果会如何呢？方案4b1=5,b2=3则两个子公司生产优化结果分别是

%=4,Z]=40x2=3/2,Z2=15可得公司总产值Z=Z]+Z2=55从上述方案分析可知，若在方案3的基础上进一步提高b]的配额(即同时使b2降低)，则系统总体收益反而会降低。因此可得出结论：方案3的资源分配方案就是最优的方案，即「资源分配方案：b]=4,b2=4生产安排：x]=4,x2=2|分公司产值：Z]=40,Z2=20[总公司产值：Z=Z]+Z2=60方法2:对目标函数进行分解/协调这种方法是根据耦合关系，对目标函数进行分解/协调。其思路是：将耦合约束条件乘以待定系数k心0)，再合并到目标函数中，即耦合约束条件移项，得乘以待定系数k乘以待定系数k(k^0)，得合并到目标函数中，得由于8k是常数，则上式合并为k(8-x-2x)>0maxZ=10x]+10x2+8k-kx「2kx2maxZ=(10x]-kx〔)+(10x2-2kx2)通过上述方法将耦合约束条件合并到目标函数中，其实就是将约束条件中耦合约束条件去掉，以便分解子系统。这样原问题就转换为：在满足总的资源条件下，选择待定系数k，使子系统达到最优，此时子系统的解就是总体系统的最优解，如图3所示(参见P]07图5-4)。图3按目标函数分解由图可见，形式上分解为两个“独立”的子系统，关键是参数k的确定。由分析可知，确定参数k的可行方案如下：方案1k=4对于第一个子系统，有maxZ=]0x-4x=6xfx<4ix]>0可得，解％=4对于第二个子系统，有maxZ=10x-8x=2xfx<3S'IX220可得，解x2=3检查：x1+2x2=4+2X3=10>8结论：当选定k=4时，不能满足约束条件，即资源不够。方案