多目标遗传算法研究

第四章 多目标遗传算法研究

§4.1 多目标优化算法简介

常见的工程优化问题大多属于多目标范畴，并且这些对象往往因相互制约而产生挑战。该领域从古代起就受到了人们的高度重视，并且经过长期的研究与发展已经形成了一套较为完善的解决方法体系。以下将重点阐述多目标优化的基础知识及其相关的非劣解概念

定义1： 当 （设 为多目标优化问题的可行域）时，在没有任何其他可行点 能满足上述条件的情况下（其中 个目标），如果至少有一个不等式严格成立，则称这样的点 是该优化问题的一个非支配解（Nondominated Point）。而将所有这些点组成的集合称为非支配集合（Nondominated Set）。

在多目标优化问题中,若存在非劣解,则通常会形成一个无限大的非劣解集合.由于实际问题中可能存在大量的非劣解候选方案,因此仅凭这些方案无法直接得出结论.决策者需要从这些候选方案中选择一个最满意的作为最终解决方案.确定最终解决方案的方法主要包括三种类型:一种是通过生成大量候选方案来构建部分最优集合;另一种则是通过逐步迭代的方式,在每一步仅生成少量候选方案;第三种则要求决策者预先给出各目标之间的相对重要性权重.这一策略也可被视为第一种主要策略的一种辅助手段.本章将提出一种基于模糊逻辑的方法,这种算法能够较好地反映出决策者的权重信息,并将其应用于多目标优化问题求解.

在生成技术中，主要的方法包括加权型策略、限制型策略以及混合型方法等；其中较为先进的技术还包括多目标遗传算法。而在交互式决策过程中，主要的技术包括基于线性约束条件下的多目标优化问题中采用Geoffrion方法；而对于仅涉及线性目标函数的问题，则应用了逐步探索技术（STEM）；此外还包括Zionts-Wallenius方法以及基于替代价值评估的选择交换策略。

从整体来看，在吸引 Decision-Maker（DM）的角度而言

生成法中，常用的加权法有其固有的缺点，对于非劣解集的某些区域不可能求出。如图4.1就是一个两个目标的例子，箭头所指非劣解曲线凹的部分无法用加权法求出，出现该现象的原因是，加权法实际上是优化各个目标函数正线性组合而成的单个目标。即采用正加权系数计算的单目标最优必然是非劣解，而某些非劣解可能找不到一组正加权系数来进行求解。采用约束法可以避免该现象，但是计算代价过大，且过程很繁杂，应用前景也不乐观。利用多目标遗传算法求解非劣解集是最近几年新出现的一种求解思路，目前还处在研究

图4.1 加权法无法求出全部非劣解的例子

在前期阶段, 虽然计算结果显示具有显著潜力, 作为本章的重点研究方向, 则集中于多目标非劣解集算法的研究

§4.2基于模糊逻辑的多目标遗传算法

§4.2.1 模糊逻辑简介

模糊逻辑（Fuzzy Logic）是一种新兴的分类技术（集合论的核心概念之一）。它模仿人类智慧的特点，在处理从完全肯定到完全否定之间过渡的情况时表现出独特的能力。不同于传统集合论中的明确分类方式，在模糊逻辑中通过为每个元素分配一个介于0到1之间的数值来描述其属于某个集合的程度。这种量化的方法使得我们可以更精细地刻画事物之间的连续性变化关系。具体的理论框架和应用案例可参考文献【116

§4.2.2 基于模糊逻辑的多目标遗传算法的思路和具体实现

通过前面介绍的知识可知, 模糊逻辑作为一种有效的工具, 具有良好的效果, 它能够很好地体现决策者的主观意愿[1]。利用模糊逻辑的方法能够体现决策者对各个目标之间重要性的"权衡"信息[2]。众所周知, 遗传算法是基于个体适应度来进行运算, 即适应度就是决策者对个体综合评价的结果, 因此可以通过模糊逻辑的方法直接构造出决策者对遗传体适应度的具体取值, 即从决策者的角度出发进行个体综合评价[3]。这种数值结果可作为遗传进化的基础依据和动力来源[4]。下面将详细阐述这一过程的具体步骤

（1）分别求出各单目标的最优解；

（2）以（1）中的单目标的最优解和决策者协商，给出各个目标满意度的隶属函数；

（3）利用模糊逻辑理论来体现决策者的观点，并建立起各目标满意度与个体适应度之间的关联。

（4）以（3）定义的适应度为基础采用遗传算法进行求解；

为了先分别解决每个单一目标的最佳方案, 以便使决策者对单独优化每个目标的可能性有一个明确的认识, 即如果单独优化某个目标可能得到其最佳结果。有了这一认识, 决策者就能更加自信地绘制出关于各项目标满意度的隶属曲线。当单独优化某个目标的问题过于困难难以精确找到最佳结果时, 我们也可以估算出该方案的大致范围。

该系统中的计算方式在具体实施上与模糊控制的方法具有高度一致性。其主要包含三个关键环节：首先是基于输入信号的模糊化（Fuzzification），随后通过建立合理的推理机制实现系统的动态响应（Fuzzy-Inference），最后结合优化算法完成精确解算（Defuzzification）。在运算机制中，在推理阶段采用最大最小合成法，在去模糊化过程中则采用了更为精确的面积重心积分法以提高系统的响应精度。

下面以十杆桁架双目标优化为例详细叙述算法过程。

参考图3.4，在节点1、2、3、4中，位移目标是指它们的某个方向偏移量达到最小的最大值。这里所说的最大偏移量指的是这些偏移量的绝对值最大的那个。

我们已经设定了两个目标；既分别最小化位移与重量；从而构建较为简单的模糊逻辑如下

（1）如果重量轻并且位移小那么设计的适应度高；

很明显上式同时针对两个目标提出了要求。若仅关注重量，则可构建如下的模糊逻辑模型：

（2）如果重量轻不管位移大或小设计的适应度都应高；

我们可以将模糊逻辑表示得更加精细，更符合决策者实际的想法：

（3-1）如果重量轻而且位移小那么设计的适应度很高；

（3-2）如果重量轻而且位移中等那么设计的适应度高；

（3-3）如果重量轻而且位移大那么设计的适应度一般；

（3-4）如果重量中等而且位移小那么设计的适应度高；

（3-5）如果重量中等而且位移中等那么设计的适应度中等；

（3-6）如果重量中等而且位移大那么设计的适应度低；

（3-7）如果重量大而且位移小那么设计的适应度中等；

（3-8）如果重量大而且位移中等那么设计的适应度低；

（3-9）如果重量大而且位移大那么设计的适应度很低；

我们可以建立相应的表格表示以上逻辑：

重量	位移	→	设计适应度
Good	Good	→****	Very High
Good	Normal	→****	High
Good	Bad	→****	Normal
Normal	Good	→****	High
Normal	Normal	→****	Normal
Normal	Bad	→****	Low
Bad	Good	→****	Normal
Bad	Normal	→****	Low
Bad	Bad	→****	Very Low

表4.1 模糊逻辑表

运用模糊逻辑理论将目标函数映射至决策者的效用函数上，在实际应用中对决策者效用函数进行精确刻画往往面临诸多挑战。鉴于此，在多目标优化问题研究领域中寻求一种合理构建决策者效用函数的方法具有重要意义。然而，在要求决策者以带有模糊性的语言表述自身偏好时显得相对容易。运用模糊逻辑理论的另一个显著优势在于能够直观展现决策者在调整模糊性参数后对最终决策的影响过程；即通过计算所得结果始终能够较好地反映决策者的真实想法。当非劣解集范围较大时，在实际操作中应用模糊逻辑可能是最有效的途径。

§4.2.3 算例

通过上一章的计算分析，在十杆问题中找到了最小重量为1598.93lb的结果；同时我们也能获得对应的最小位移值7.171639以及对应的最小重量值15349.4496。接下来将对比分析这两种设计方案的特点和性能表现

位移最小设计（ ）	最轻设计（ ）
杆1	40.0000	7.9396
杆2	40.0000	0.1
杆3	40.0000	8.0956
杆4	40.0000	3.9613
杆5	0.1	0.1
杆6	40.0000	0.1
杆7	40.0000	5.7554
杆8	40.0000	5.5994
杆9	40.0000	5.5994
杆10	40.0000	0.1
重量（ ）	15349.4496	1598.93
位移（ ）	0.977492	7.171639

表4.2

从上表可以很明显地看出，位移和重量是两个互相冲突的目标。

基于已知单目标极值的情况，在这种情况下我们采用一种简便的模糊逻辑来计算个体的适应度。如果所测得的重量较低并且位移较小，则表明个体具有较高的适应度。

为简单起见，假定重量轻的隶属函数为线性的，如图4.2所示。

1

1598.93

15349.4496

重量

图4.2 重量轻的隶属函数

假定位移小的隶属函数也为线性，如图4.4所示。

个体适应度被定义为[0,1]区间内，并且假设当适应度较高时其隶属函数将呈现线性关系（如图4-3所示）。

群体数量设定为100，在代数设置为500的情况下展开运算，在复制操作的概率下定位于2%，变异操作的概率则定位于1%。在经过十次独立运行后获得实验结果

随机运行十次得结果如下：

重量（ ）	位移（ ）
4567.742671	2.288459
4645.949119	2.349095
4688.605046	2.378970
4714.601695	2.381532
4887.722703	2.460164