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

系统优化 前几章分别介绍了一些传统系统优化的方法，如线性规划、非线性规划、动态规划、图论等。本章侧重于介绍现代优化算法和大系统的分解与协调。 现代优化算法 传统优化算法与现代优化算法 在系统设计与规划过程中，通常需要面临所谓的“系统优化”问题，即在一定约束条件下，选择最合理的、达到某一（或某些）目标的最优解，例如生产计划安排中的最大获利问题、投资决策问题、油管铺设中的最短路问题等。 系统优化问题是一个古老的课题，早在17世纪在欧洲就有人提出了各种求最大（小）值问题。直到20世纪40年代，随着科学的发展而产生了一系列如线性规划、非线性规划、动态规划、图论等传统优化算法。这些算法在应用时，要求： 选择表示优化因素的独立变量； 定义要优化的系统的性能指标和约束条件； 写出表示各种变量之间关系的数学模型。随着20世纪80年代初期模拟退火、遗传算法和人工神经元网络算法的兴起，人们对某些复杂的优化问题及其算法进行了深入研究，从而产生了现代优化算法。这些算法是一种多学科综合性的解决问题方法，其主要应用对象是系统优化中的难解问题，即系统模型过于复杂而无法用明确的解析方程来描述的问题。 启发式算法 以一定的直观基础构造成的算法，称为启发式算法。启发式算法是相对于最优化算法提出的，它是在可接受的计算费用内寻求最好解（但不一定是最优解）的一种技术。 在多数情况下，由于无法明确找出问题的最优解，所以也就无法表明所得解与最优解的近似程度。因此，启发式算法的特点是不考虑算法所得的最好解与最优解的偏离程度。 例1（背包问题的贪婪算法） 有一个容积为b的背包，现有n个体积分别为ai，价值分别为ci（i =1, 2, …, n）的物品待装包，试问如何使装包物品的价值达到最大? 解 对于该背包问题可构造以下贪婪算法： （1）对物品按“单位体积价值最大的优先装包”的原则，以ci / ai从大到小进行排列，不妨把排列记成{1, 2, …, n}，并令k = 1； （2）若，则xk = 1（装包）；否则，xk = 0（不装包）； （3）k = k + 1，若k = n±1时，算法停止；否则，返回（2）。 故（x1, x2, …, xn）为该贪婪算法的所得解。可见，这种启发式算法非常直观，且易操作。 启发式算法的优点： 数学模型简单； 直观且简单易行； 速度快； 程序易于修改等。 启发式算法的缺点： 不能确保求得最优解； 计算结果表现不稳定而造成不可信。 启发式算法的分类（参见P99）： 一步算法； 改进的迭代算法； 数学规划算法； 现代优化算法。 遗传算法 遗传算法是根据生物进化的模型而提出的一种现代优化算法。由于最优化问题的求解过程是从众多的可行解中选出的最优解，而生物进化中的“适者生存”规律是使最有生存能力的染色体以最大的可能生存下来，这种相似性就使得遗传算法可以在优化问题中得以应用。 （1）遗传算法的生物进化特征 遗传算法主要借鉴了生物进化的以下特征： 生物进化实质上是发生在染色体上； 选择：按自然选择规律确定染色体的生存或淘汰，即适者生存、优胜劣汰； 遗传：当染色体结合时，双亲遗传基因的结合会使子代保持父代的特征； 变异：当染色体结合后，随机的变异会造成子代与父代的特征又有所不同。 （2）遗传算法的主要步骤 仿照生物遗传的概念，可以得到遗传算法的主要步骤如下： 首先，对优化问题的解进行编码 为了便于表达优化问题的解和进行遗传运算，就必须对优化问题的解进行编码，且一个解的编码称为一个染色体，组成编码的元素称为基因。 其次，构造和应用适应函数 适应函数通常是依据优化问题的目标函数来决定的。适应函数确定后，由适应函数值所决定的概率分布进而确定生存或淘汰的染色体（即解的编码），生存下来的染色体组成一个可以繁衍下一代的群体——种群（即一组解）。 再次，进行编码的交叉 通过编码的交叉来实现染色体的结合（即编码的组合），从而繁衍出新的下一代（即产生新的解）。 最后，产生变异 通过基因变异（即编码的某个元素分量发生变化）使某些解的编码发生变化，从而使这些解具有更大的遍历性（适应性）。 遗传算法与生物遗传概念的对应关系参见P101表5-1所示。 例2 用遗传算法求解max f (x) = x2，且x为整数。 解 第一步，选择解的编码，并选取初始群体以及群体中的个体数量（即群体维数） 通常，表示解的简单编码是二进制编码，即0或1组成的字符串。由于变量x的最大值是3132 = 25，因此可以采用5位二进制编码来表示优化问题的解，例如 10000→16，11111→31，01001→9，00010→2 上述编码就称为染色体。编码中的每个分量称为基因，且每个基因只有两种状态0或1。 注意：若本例是对连续变量求解，如x∈[0, 1]且对解的误差