澶氬�︾�戣�捐�′紭鍖?( MDO ) 鏈虹數姣曚笟璁捐��(璁烘枃) - 鐧惧害鏂囧簱

山东科技大学学士学位论文

1）数学模型：由解空间、目标函数和初始解三部分组成。

解空间：对所有可能解均为可行解的问题定义为可能解的集合，对存在不可行解的问题，或限定解空间为所有可行解的集合，或允许包含不可行解但在目标函数中用罚函数(Penalty Function)惩罚以致最终完全排除不可行解；目标函数：对优化目标的量化描述，是解空间到某个数集的一个映射，通常表为若干优化目标的一个和式，应正确体现问题的整体优化要求且较易计算，当解空间包含不可行解时还应包括罚函数项：初始解：是算法迭代的起点，试验表明，模拟退火算法是健壮的(Robust)，即最终解的求得不十分依赖初始解的选取，从而可任意选取一个初始解。

2）新解的产生和接受机制：由四个步骤构成一轮试验。

首先，按某种随机机制由当前解产生一个新解，通常通过简单变换(如对部分元素的置换、互换或反演等)产生，可能产生的新解构成当前解的邻域；其次，计算新解伴随的目标函数差，一般由变换的改变部分直接求得；第三，由接受准则，即新解更优，或恶化但满足Metropolis准则，判断是否接受新解，对有不可行解而限定解空间仅包含可行解时，还需先判断其可行性；最后，满足接受准则时进行当前解和目标函数值的迭代，否则舍弃新解。

3）冷却进度表：即(t，△t，L，s)。应使得t充分大且衰减得充分慢、L足够大，S通常选为解在连续M个Mapkob链中无任何改变时终止算法。

3.3 智能算法特点

前面已经提到，MDO中涉及的常用智能算法有以下几种： 1) 模拟退火算法( adaptive simulated annealing，ASA )； 2) 遗传算法( genetic algorithms，G A)

而在MDO环境下的常用软件中涉及的与遗传算法有关的算法主要有以下几种：

1) 多岛遗传算法（mlti-island genetic algorithm，MIGA）；

21

山东科技大学学士学位论文

2) 领域培植遗传算法（neighborhood cultivation genetic algorithm，NCGA）；

3) 非配解排序遗传算法（non-domianted sorting genetic algorithm，NSGA-Ⅱ）。

特点 ASA MIGA NCGA NSGA-Ⅱ 只有实数变量 1 1 1 1 变量可为实数、离散型 1 1 1 1 高度非线性优化问题 设计变量大于20个 1 1 1 1 约束条件大于1000个 代码运行时间长 用户可以提供梯度方向 不需要目标函数连续 1 1 1 1 可解决不等式约束 1 1 1 1 可以解决等式约束 1 1 1 1 基于K-T条件 从很多设计中寻找最优解 1 1 1 不需要变量相互独立 1 1 不需要有限可微 1 1 1 1 表3.1智能算法的特点 其中：“1” 表示该算法具有这种特征。从表 1可以看出，这几种智能算法的特点非常类似：普遍对多约束、高度非线性问题不适应；不适合解决大规模的复杂优化问题，对问题的约束条件要求较松；对数值算法要求严格的 K- T条件没有限制；对变量类型没有特殊要求。若要选择具体的算法，该表格明显不能提供足够的依据，还需要一些具体指标来对算法的性能加以评判。

3.4

3.4.1 算法比较指标的确定

算法选择模型

算法的比较是相对的。没有一种方法对解决所有问题来说都是最好的，对于一个特定的问题或某一类问题可以有针对此类问题相对较好的解决途

22

山东科技大学学士学位论文

径。鉴于算法比较的这些特点，本文提出了以下几个方面的比较指标，以期对算法选择有一定的指导意义。

1）短时寻优能力 鉴于工程实践中的问题比较复杂、 运行时间十分漫长，许多工程实际问题所关心的焦点往往是在短时间内得到满意的解区间，而不是耗费大量时间求得问题的最终收敛最优解。

智能算法涉及的参数较多，方法不同、参数不同。因此需要首先定位一个基准，起到为其他算法参数调整提供参照物的作用。为此，本文使用了AS A作为标准算法来尝试参数的设置。因为 ASA的基本设置中仅需要改动最大生成设计个数即可对算法结果产生影响，易于控制。本文使用的具体参数设置步骤如下：

a) 使用 ASA作为优化器，根据每个案例优化运行周期长短将最大生成设计个数设为 200～500的数值，其他参数可以适当微调。运行案例得到优化后的结果。

b) 将运行结果与案例文档提供的结果进行比较。如果结果满意 (优于或至少相差不多，如 10% )则保留设置，跳转到d)；否则转到 c)继续执行。

c) 调整 ASA参数，主要是增加最大运行次数，运行优化过程得到结果并转到 b)。

d) 根据 ASA的最大运行次数设置，分别调整其他三种算法的参数设置，使其最大运行次数与 AS A大致相仿。

e) 将算法结果与案例文档提供的结果比较。如果能得到可行解且不相差过大 (数量级差距 )则保留设置，记录结果；否则转回 d)。

2）时间

算法在进行优化时所需要的时间。为了避免了同一算法解决

不同案例的时间无法比较的问题，研究中采用相对运行时间。即：关注的仅仅是对于某一案例，该算法的解决速度与其它算法速度的比较，而并不在意绝对数值。并且，同一算法不同案例的时间绝对值的比较是没有意义的。相对运行时间定义如下：

23

山东科技大学学士学位论文

tij?Tij?Ti?1n （3-1）

ijn其中， tij——算法i在案例j的相对运算时间

Tij——算法i在案例j的实际运算时间

?Ti?1nijn——各种算法运行案例j的平均时间

3）解决问题的个数 指一种算法在所有的案例中，随着时间的累积可

以解决的问题的数量。通常，工程应用中希望算法可以在尽可能短的时间内解决较多的问题。为了反映这一需求，将相对时间分段，而ni 表示的就是对某种算法在相对时间小于i的前提下解决问题的个数。这样，就建立了相对运行时间和解决问题个数的关系。

4）精度

对同一个算法而言，要求的精度越高，在配置相同的计算机

上运行的时间也就越长。因此，抛开精度不谈，单纯的考虑运行时间是没有很大意义的。目前，常用两种精度选取标准：目标函数的相对精度和设计变量的相对精度。由于目标函数的相对精度表示了设计的优劣，而工程界关注的是最终的设计成果，因此选用目标函数的相对精度作为研究的精度。定义见公式（3-2）和（3-3）：

当 f(x*)?0时， ?f?f(x) （3-2）

f(x)?f(x*)当f(x)?0 时， ?f? （3-3）

f(x*)*其中，f(x*) 是目标函数的理想值，f(x) 是某个算法得到的目标函数值。 3.4.2 算法比较模型

在三维算法比较方法的基础上，建立算法比较三维模型。即：在算法的

24