基于免疫多目标优化的否定选择算法.pdf

As t he devel opment of human i mmune syst em(HIS)，an i ncreasi ng at t ent i on has

been pai d t o some amazi ng characters，such as hi ghl y evol ved，paral l el ，di stri buted and

adapt i ve．In order

t he probl em i nvol ved i n

engi neeri ng

appl i cati ons，arti fi ci al i mmune syst em( AIS) has

been proposed

i nspi red by the

i nformat i on processi ng

abi l i ti es of HIS．Among many of the mechani sms

comput at i on provi des

approach for

i mprovi ng the performi ng of

i ntrusi on detecti on，al l of whi ch mechani sms are i nvol ved i n the most di scussed areas．

Parti cul arl y，a NewSphere- domi nance based Preference Immune Al gori t hm(SPIAII)

i s proposed at

fi rst i n thi s paper．And a negat i ve sel ecti on algorithmwi t h opti onal

proposed for i ntrusi on detecti on subsequent l y．Fi nal l y, we

successful l y

propose t he i mpl ement i ng

st rat egy about

usi ng const rai ned mul ti obj ecti ve immune

al gori thm(CMIA)for V- det ect or negat i ve sel ecti on．

In chapt er t wo，we mai nl y propose an i mproved sphere—domi nance rel at i onshi p

combi ned wi tl l the concept of soft

const rai nt ．Thi s domi nance rel ati onshi p Can beaer

eval uat e t he preference i nformati onof Deci si on Maker(DM)，and ensure t he stabi l i ty of

convergi ng t o the PF wi t hi n t he preference area．Based on thi s newdomi nance，a New

Sphem—domi nance based Preference Immune Al gori thm(SPIAII)i s proposed．Thi s

al gori t hmCan effecti vel y i mprove the di versi ty of ant i bodi es，accordi ng t o whi ch t he

stabi l i ty of convergence wi l l be enhanced．

In chapt er t hree，V—det ect or negat i ve sel ecti on al gori t hm，whi ch i s one of t he most

i mport ant algorithms i n the area of i ntrusi on detecti on，wi l l be mai nl y di scussed．As we

known，t hi s al gori t hmi ncl udes several mechani sms，such as two di fferent representati ve

i nterpretati ons of sel f sampl e and two met hods of esti mati ng detector

coverage．In

addi ti on，al l

of t hem hol d

t here own meri ts and

demeri t s．For

detecti ng

compl i cat ed i ntrusi on dat a，a negat i ve sel ect i on al gori t hmwi t h opt i onal modul es wi l l be

proposed．Thi s approach Can wel l i nt egrat e al l t hese mechani sms i nt o some modul es for

handl i ng di fferent t est dat a fl exi bl y．

In chapt er four, the mai n cont ri but i on i s t he successful appl i cat i on about i mprovi ng

the negat i ve sel ect i on algorithmfNSA) wi t h const rai ned mul ti obj ecti ve opt i mi zat i on

met hod．It

i s means t hat a novel conswmned mul ti obj ecti ve i mmune al gori thm(CMIA)

for V- det ect or negat i ve sel ecti on i s proposed．CMIA Can produce a seri es of det ect ors

wi t h an opt i mal

di stri buti on，and better sat i sfi ed the common engi neeri ng goal s i n

vari ous NSAs．111e new al gori t hmi ncreases t he effecti veness of si gl e detector；SO a

l arger dangerous

can be covered by fewer

det ect ors wi t h a more reasonabl e

di stri buti on．111at means the detecti on rat e wi l l be effecti vel y enhanced wi t h fi xed scal e

of detector set．

support ed by

Nat i onal

Hi 曲Technol ogy

Research and

Devel opment Program( 863 Program)of Chi na(Grant No．2009AA1 2221 0)，the

Nat i onal

Foundat i on of Chi na(Grant

Nos．60703 1 07)，the Key

Sci emi fi c

and Technol ogi cal

Innovat i on Speci al

of Shaanxi (Grant

2008ZDKG- 37)，the Programfor NewCent ury Excel l ent Tal ent s i n Uni versi ty(Grant

No．NCET- 08- 081 1)，the Program for New Sci enti fi c and

Technol ogi cal

Shaanxi Provi nce(Grant No．20 1 0KJXX一03)，and the Fundamental Research Funds for

the Central Uni versi ti es(Grant No．K505 1 002000 1)．

Keywords：Art i fi ci al i mmune system，Mul ti - obj ecti ve opti mi zati on，Intrusi on det ect i on

system，Negati ve sel ecti on al gori t hm

第一章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．1

1．1生物免疫系统与人工免疫系统⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．2

1．2多目标优化问题及多目标优化算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．3

1．2．1多目标优化问题及相关定义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．3

1．2．2动态多目优化问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．5

1．2．3多目优化算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．6

1．3免疫在多目标优化算法中的体现⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．6

1．4入侵检测的基本概念及框架模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．8

1．4．1入侵检测的概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯8

1．4．2入侵检测系统的分类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．8

1．4．3入侵检测系统的框架模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．9

1．5本文的主要工作安排⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．10

第二章基于偏好思想的免疫多目标优化算法⋯⋯⋯⋯⋯⋯⋯⋯⋯．．1l

2．1引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11

2．2相关背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．12

2．2．1非支配邻域免疫算法(NNIA)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．12

2．2．2球支配(Sphere—domi nance)偏好方法及原理⋯⋯⋯⋯⋯．．15

2．2．3基于不同支配偏好方法的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯．．16

2．3新型基于球支配的偏好免疫算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯18

2．3．1基于软约束球支配的偏好思想⋯⋯⋯⋯⋯⋯⋯⋯⋯．．18

2．3．2偏好多目标优化算法中的统计变异方式⋯⋯⋯⋯⋯⋯⋯19

2．3．3一种新型的基于球支配的偏好免疫算法(SPIA—II)流程⋯⋯．．20

2．4实验结果及分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．23

2．4．1多目标测试问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．23

2．4．2静态多目标问题试验对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯25

2．4．3动态多目标问题试验对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯31

2．5本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．35

第三章可选择模块式否定选择算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．37

3．1引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯37

3．2相关背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．37

3．2．1否定选择算法的背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．37

3．2．2否定选择算法的免疫模型及特点⋯⋯⋯⋯⋯⋯⋯⋯⋯38

3．2．3否定选择算法的流程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．39

3．3可选择模块式否定选择算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．42

3．3．1否定选择算法的自己样本表现型⋯⋯⋯⋯⋯⋯⋯⋯⋯42

3．3．2否定选择算法的覆盖率估计方法⋯⋯⋯⋯⋯⋯⋯⋯⋯44

3．3．3模块设置方式及存在必要性说明⋯⋯⋯⋯⋯⋯⋯⋯⋯45

3．4实验结果及分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．48

3．4．1测试问题说明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．48

3．4．2不同自己样本表现型的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．48

3．4．3不同覆盖率估计方法的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯52

3．5本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．54

第四章基于约束多目标免疫算法的否定选择⋯⋯⋯⋯⋯⋯⋯⋯⋯．．55

4．1引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯55

4．2相关背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．56

4．2．1多目标约束优化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．56

4．2．2超球体的相关计算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯57

4．3约束多目标免疫算法与否定选择⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯57

4．3．1目标函数的设置及其约束⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯58

4．3．2基于约束多目标免疫算法否定选择的流程⋯⋯⋯⋯⋯⋯．．59

4．3．3基于约束多目标免疫算法否定选择的重要策略⋯⋯⋯⋯⋯．63

4．4实验结果及分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．64

4．4．1二维数据测试比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯64

4．4．2多维数据测试比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯70

4．5本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．71

第五章总结与展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯73

5．1总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯73

5．2展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯74

致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．75

参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯77

研究成果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯83

随着科学技术的不断发展和深入，以及各个学科对更深层的理论的发掘，许

多的研究课题已经不能靠单一领域的理论和方法来解决。如今世界上各种科学技

术之间相互交叉、渗透的情况层出不穷，从而诞生了许多的边缘学科。与此同时，

人们面临着越来越复杂的研究问题，传统方法的局限性也促使人们不断寻求新的

方法和手段，信息科学等领域的不断扩展就证明了这一点。包括人类在内的生物

体系和生物环境本身就蕴含着无数的未解之谜，对此的研究有助于人类更好的理

解自然界。正因如此，生物逐渐成为了许多科学家发明创造的灵感源泉，他们模

仿生物界不同的机能体系，创立了许多新颖的技术和方法。20世纪60年代以来，

模拟某一自然现象、过程或生物系统特性的理论和技术不断涌现和发展，如人工

神经网络，进化算法，免疫算法，模拟退火算法，模糊系统等，对促进人工智能、

计算机技术及其相关领域的应用和发展起到了巨大的推动作用【l J。生物系统中的信

息处理部分可分为脑神经系统，遗传．进化系统，免疫系统和内分泌系统四种类型，

而前三种类型可以分别对应人工神经网络(Arti fi ci al Neural Net work- - ANN) ，进

化算法(Evol uti onary Al gori thms- - Eas)，和人工免疫系统(Arti fi ci al Immune Syst em

--AIS)的原型21。而本文的主要工作则基于人工免疫系统。

在脑神经系统和遗传进化系统的早期研究中，人们逐渐发现了诸如复杂度与

泛化能力之间的矛盾等问题。因此在人工智能不断向生物智能学习的过程中，人

们意识到生物免疫能力的重要性。免疫系统的复杂功能堪与大脑相比较，是复杂

的自适应系统，能够有效的使用多种机制防御外部病原体。其具体作用是识别所

有身体内的细胞，并将其分类为自体和非自体。1974年，美国诺贝尔奖获得者，

生物学家、医学家、免疫学家Jeme提出了免疫网络的理论【3】，使得免疫系统引起

广泛的关注。继此之后，Farmer、Perel son，Bersi ni 、Varel a等理论免疫学者分别

在1986年，1989年和1990年发表了相关的论文，其中Farmer的关于免疫系统与

机器学习的研究是具有创造性和开拓性的工作，他们的工作有效的为基于免疫原

理的计算系统和智能系统的发展开辟了道路【4‘7J。“人工免疫系统”的概念于1996

年12月在日本举行的基于免疫系统的国际专题讨论会上正式提出。紧接其后，在

1997年和1998年的IEEE Syst ems，Man and Cyberneti cs国际会议上组织了相关的

专题讨论，并成立了“人工免疫系统及其应用分会"。如今，已有许多人工智能领

域的著名国际会议开辟了人工免疫系统的国际会议，比如IEEE Conference

Evol ut i onary

Computati on(CEC)，

Evol ut i onary

Comput at i on

Conference(GECCO)，Int emat i onal Joi nt Conference on Arti fi ci al Intel l i gence(IJCAI)，

Internati onal Joi nt Confefence on Neural Networks(IJCNN)．

基于免疫多目标优化的否定选择算法

1．1生物免疫系统与人工免疫系统

人工免疫系统是在生物免疫学的理论基础上发展起来的，它离不开对生物免疫

系统的理解和研究，同样与免疫学的发展密不可分。

生物免疫系统是一个高度复杂的自适应系统，可以保护生物体免受外部病原体

的侵害，并能够把体内所有的细胞或分子分成属于自己的种类(自体细胞)和属

于外部来源的非自体分子两类。此外，生物免疫系统的运行不依靠任何控制中心，

具有分布式的任务处理能力，它不仅有在局部采取行动的能力，也能通过化学信

息的交流构成网络，进而形成全局防御系统。因此生物免疫系统充分展示了可以

融进人工智能系统的特性：分布性，多样性，动态性，鲁棒性，自适应，自治性，

自我检测，错误耐受等【8J。而这些特性正是生物免疫系所固有的特性，也正是大多

数人工系统中缺乏的特性。如今基于免疫系统原理发展起来的计算技术已然成为

了自然计算中的新领域，它模仿生物免疫系统的各种机能，创造出许多新型的计

生物免疫系统能够以多种智能的方法对其输入进行应答，能够被激发并产生准

确的目标特异性应答，随后通过交叉变异来进行进化学习，以此适应新环境【9】o此

外它对重复出现的刺激环境能够更快的应答，是高度分布式的、高度并行的。这

种分布式处理和并行处理等信息处理机制是由免疫系统内部构造形成的，能够满

足人们对计算应用的需要，为人工免疫系统提供理论支持。

早在1990年，日本学者Ishi da就利用免疫系统成功解决了传感器网络故障诊

断问题，这也是免疫系统在工程应用领域可查到的最早的研究成果【l 们。随后，美

国学者Forrest在1994年首次将免疫系统的手段应用于计算机安全和病毒检测【l l 】。

而这一应用的提出则主要基于生物免疫系统中的免疫反馈机理和动态维持系统稳

定的能力。生物免疫系统可以建立有效的反馈控制系统，如利用T细胞的免疫反

馈规律可以设计出自调节免疫反馈控制器。而且生物免疫系统也可以被比拟为工

程应用中的自组织存储器，它可以记忆已使用信息且很少遗忘，具有优化学习机

理和学习外界物质的自然防御机理，因此可以动态的维持系统的状态。此外从工

程应用的角度来看，生物免疫系统抗体多样性的遗传机理可以被借鉴用于搜索优

化算法。在具体的进化过程中，可以通过生成不同抗原的抗体来达到全局优化的

人工免疫系统是模拟生物免疫系统功能、原理和模型的一种自适应系统。目前，

其研究成果已经涉及了诸多领域，如机器学习、自动控制、模式识别、计算机安

全、图像处理、搜索和优化、数据分析等。它已然成为了继神经网络、模糊逻辑

和进化计算后人工智能的又一研究热点。但是不论是对免疫机理的认识、免疫算

法的构造，还是其应用都将要经历长时间的发展才能最终走向成熟。

1．2多目标优化问题及多目标优化算法

众所周知，无论是在科学研究还是在工程应用上，目标优化都是非常重要的课

题。而这些优化问题往往是多属性、多目标的，甚至是多个目标相互冲突的，如

何获取这些问题的最优解，一直都是学术界和工程界关注的焦点问题。例如

在企业管理中产品的生产质量与生产成本这两个目标之间就是相互矛盾的。与单

目标优化不同，在多目标优化问题(Mul ti ．obj ecti ve Opt i mi zat i on Probl em，MOP)

中某一个目标的改善就可能引起其他目标性能的降低，因此多目标优化的本

质就是在各个目标之间进行协调和折中的处理，使所有目标尽可能同时达到

最优。针对多目标的优化问题，各种多目标优化算法(Mul ti —obj ecti ve Opt i mi zat i on

Al gori t hm，MOOal gori thm)被提出，近年来发展迅速。

1．2．1多目标优化问题及相关定义

为了更好的了解多目标优化算法的过程和实质，我们必须首先了解多目标优化

问题并掌握一些重要的基本概念。

在解决多目标优化问题中，如何选择最优解，如何构造最优解集，如何评价最

优解的优劣等都是决策者应该考虑的问题。为了解决此类问题，我们首先要了解

多目标优化问题的一般描述【12‘13】。

若给定决策向量X=b．，x：，x，，⋯，矗)，它满足如下约束条件：

g，【X)≥0(f=l，2，⋯，k)

O=1，2，⋯，k)

设有，．个相互冲突的优化目标，则优化目标可表示为：

f(x)=“(x)，五(x)，⋯，Z(x”

此时需要寻求一个x‘=b：，x：9· t· 9x：)，使f【X+)在满足两个约束条件的同时达

在多目标优化中，不同的子目标函数有不同优化目标，但不外乎以下三种情

况：1)、最小化所有子目标；2)、最大化所有子目标；3)、最小化一部分子目标，

而最大化另一部分子目标。为了处理方便，我们通常会把子目标函数同时转化为

最大化或最小化。例如把最大化转化为最小化的方法为：

mi nf,(X)：一max(-f，(X))

同时其约束条件式(1．1)贝JJ需要变为：

一g。(X)≥0(f=1,2，⋯，k)

如此一来，多目标优化问题都可以转化或统一的表达形式，以最小化多目标

基于免疫多目标优化的否定选择算法

优化为例，多目标优化问题可表示为：

{minf(X)=(石(x)，五(x)，⋯，z(x))1(1-6)

【subj ectto gi(X)≥0，红(X)=0(f=l，2，⋯，k)

其中X=X。，x：，x，，⋯，X。)通常被称为决策向量，属于一个连续的可行的搜索空间，

称为决策空间Q。决策空间Q可被理解为满足式(1．1)与式(1．2)的可行解集，即有：

Q={x∈R”Ig，(x)≥o，曩(x)=0；(f=1,2，⋯，七；，=1,2，⋯，，)}

而向量函数f(x)可将Q三R”映射到集合兀￡R7上，兀是El 标函数空间。此外，．代

表了子目标函数的个数，k代表了约束函数的个数。

以多目标优化问题MOP的定义为基础，如式(1．6)所示，在这里我们还需要

关注一些重要的定义。如支配关系，Pareto最优解，Pareto最优解集，Pareto最优

边界等【12-131。

支配关系(domi nate rel at i on)是存在于多目标个体之间的一种非常重要的

定义1．2．1：设x。∈Q和X占∈Q是进化群体中的任意两个不同的个体，X。

支配X占，表示为X一>- XB，当且仅当：

^≥耋器量参譬悬怠；(1-8X

^影∈{1，2，⋯，，．j ，Z(4)<，【口)

其中“>- ’’即为支配关系。

此外，在多目标个体之间的支配关系上还会存在程度上的差异，具体可

分为弱非支配关系和强非支配关系。

所谓弱非支配(weak non．domi nance)可定义为：若仅存在X∈Q，满足

五(x‘)≤五(X)(k=l，2，⋯，，)，但不满足五(X+)<石(x)(k=l，2，⋯，，-)，则称X’∈Q为弱

所谓强非支配(st rong non—domi nance) 可定义为：若存在X∈Q，使

五(x‘)≤五(x)(七=1，2，⋯，，．)成立，且至少存在一个f∈{1，2，⋯，，．}，使z(F)

称X’∈Q为强非支配解。从定义可以看出，如果X’是强非支配解，则X‘必为弱

非支配解，反之则不然。

对于多目标问题中的非支配解，即Pareto最优解，有如下定义：

定义1．2．2：给定一个多目标优化问题mi nf(X)，不存在任何X∈Q使得

x>-x。，x+∈Q，则称x’是mi nf(X)的非支配解，即Pareto最优解。Q为满足式

(1．1)与式(1．2)的可行解集。

在多目标优化问题中Pareto最优解通常不止一个，则所有Pareto最优解的集合

可被称为Pareto最优解集(Pareto Set，PS)，定义为：

定义1．2．3：针对一个多目标优化问题mi nf(X)，Pareto最优解集为

P’={X’)={X∈QI、了叉∈Q，x>-x}。

本文涉及的最后一个重要定义就是Paret o最优边界(Paret o Front，PF)。

定义1．2．4：若己知一个多目标优化问题minf(x)及其Pareto最优解集{X‘}，其

Paret。最优边界为：阡’=If(X)=∽(X)，厶(X)，⋯，，(X))l X∈{X’珏。简言之，

Pareto最优边界即为Pareto最优解集在目标空间兀的投影。

1．2．2动态多目优化问题

如今在许多的科学研究和工程应用中，多目标优化问题不只包含多个相互矛

盾、相互制约的目标函数，而且这些目标函数或者其相关参数时常与时间因素有

关。如系统优化过程中考虑的动态调度问题，不同时间间隔需要各异的运行状态

的问题等。将现实中具有多个目标，且与时间因素相关的问题抽象成数学模型，

就得到动态多目标优化问题(Dynami c Mul ti —obj ecti ve Opt i mi zat i on Probl em，DMOP)

【15】，此外由时间带来的约束被称为动态约束。

几乎所有的动态多目标优化控制问题都能被如下非线性参数化多目标优

化问题所表示l "。16J：

定义1．2．5：设V0，vF和W分别为n。维，刀F维和M维离散或连续的向量空

间，g与h分别为不等式和等式约束，f是从V| 0×vF映射到w上的一个函数，则

此时M个目标的参数化多目标优化问题可表示为：

玳f 2{石(V0' vF)，⋯，厶(V。，VF)}

s1．g(vo，VF)≤o，h(vo，VF)=0

在式(1—9)中，vo是对优化起作用的变量，而变量VF是独立于变量vo的，且与优

化无关。目标函数和约束条件均要受到参数的约束，且大多为非线性。

如果只考虑时间，作为单一的参数，式(1．9)可被转化为：

定义1．2．6：设f为时间变量，V和W分别为胛维和M维离散或连续的向量空

间，g与h分别为不等式和等式约束，f是从V×t 映射到w上的一个函数，则M个

目标的参数化动态多目标优化问题可表示为：

m删inf_{石(V，f)，．一，厶(V，‘))

s．t．g(v，t)≤o，h(V，，)=0

为了更好的定义上述动态多目标优化问题，我们还需了解两个重要的解集。

定义1．2．7：f时刻的Pareto最优解集POS(S。(f))即为决策变量空间；t时刻的

Pareto最优边界上的最优目标集合尸卯fC(，))即为目标空间的Pareto最优解集。

在本文中，我们所考虑到的动态多目标优化问题DMOP可具体表示为：

基于免疫多目标优化的否定选择算法

j mi nF(x, t)2(彳(彬)，五(彬)⋯，厶(叫)。(1-1 1)

【subject t o

其中x=(五，⋯，xt)。∈R7为有效的决策变量，XcR7为决策空间，R肼为目标空

间。F-(x，，)寸R肘由M个实值的目标函数Z(x，，)f：1，2，⋯，M组成，每一个函数

动态多目标问题DMOP对于决策空间和目标空间有以下4种随时间变换的方

式：1)、Pareto最优解集(最优决策变量)S。随时间变化，而Pareto最优边界(最优

目标值)C不随时间变化；2)、Pareto最优解集(最优决策变量)s。和Pareto最优

边界(最优目标值)C都随时间变化；3)、Pareto最优解集(最优决策变量)s，不随

时间变化，而Pareto最优边界(最优目标值)只随时间变化；4)、优化问题虽时间

变化，但Pareto最优解集(最优决策变量)s，和Pareto最优边界(最优目标值)C都

1．2．3多目优化算法

目前，用于多目标优化问题的系统优化模型大体可分为数学规划模型和非数学

规划模型两大类。其中数学规划的方法是最早被广泛应用的系统优化方法，如线

性规划、非线性规划、动态规划和整数规划等。而智能优化算法则是非数学规划

模型的代表。它是一类通过模拟某一自然现象或过程而建立起来的优化方法，

具有高度并行、自组织、自学习与自适应等特征。这类算法包括进化算法(EA)、

粒子群算法(PSO)、禁忌搜索(TS)、分散搜索(SS)、模拟退火(SA)、人工免疫

系统(AIS)和蚁群算法(ACO)等114】。

与传统的数学规划方法相比，智能优化算法更适合用于求解多目标优化问题。

首先，智能优化算法在每一次运行中，能够获得多个有效解，即可以同时处理一

组解。其次，智能优化算法对最优解集的连续性和前端形状不敏感，因此普适性

更高，能更好的逼近非凸和不连续的最优解集。如今，智能优化算法被广泛应用

于多目标优化领域，并出现了一些热门的方向，进化多目标优化算法，免疫多目

标优化算法等。其中的被人们广泛采纳的具体算法有NSGA．II[ 17】、SPEA2[ 18】、PAES

f191、NNIA[20】、AMOSA[21】等。

1．3免疫在多目标优化算法中的体现

现代免疫的概念指的是机体免疫系统识别排除抗原性异物的功能，即识别自己

(sel f)和非己(nonsel D并排除非己的功能。通常能够诱导机体免疫响应并与机体发生

特异性反应的物质被称为抗原，而B细胞、T细胞以及抗原特异性淋巴细胞通常

被称为抗体。也就是说在人工免疫系统中，优化问题和约束即为抗原，而抗体则

是决策变量的编码。为了更好的展示免疫在多目标优化算法的应用，我们需要将

免疫系统中的术语与多目标优化算法进行统一。下面以式(1．6)所示的多目标优化

问题为例，具体说明。

抗原甲：抗原甲通常被定义为目标值向量f(x1。

抗体以及抗体种群：抗体b=(包，62，⋯，岛)则是决策变量x的编码，表示为

b=e(X)，反过来决策变量x被称为抗体b的解码，表示为x=P。1(b)。此时抗体

种群可表示为一个n维的抗体b的集合，即：

B={bl 92j 2，⋯，玩}，6f∈R。，1≤f≤n

此时种群大小可视为刀。

Ab．Ag亲和度关系a：通常Ab—Ag亲和度关系是在单一抗体b=e(x)和抗原

甲之间衡量的。具体可以定义为a(b，甲1：

a(b，甲)=F(e。(6))

=(石(e_1(6))，石(P-1(6))，⋯，，(P-1(6)))2

Ab．Abs亲和度关系丫：通常Ab．Ab亲和度关系是在两个抗体之间衡量的，因

此被衡量抗体与抗体种群中其它的抗体之间的联系将被忽略。因此在本文中将应

用一种新的Ab．Abs亲和度关系。如计算抗体6，∈B，J=(1，2，⋯，刀)的Ab-Abs亲和

T(o，B)=、／∑一(屯，B)(1- 14)

其中每一个丫j (6，，B)可以简化表示成L。将抗体种群B中的所有抗体按第f个目标

函数值降序排序，则可得到：

　　1／8

为了保证分母不为零，设万为一个无限小的数。

非支配抗体：针对于式(1—6)所示的抗原甲，我们称抗体匆为抗体种群

B={岛，62，⋯，玩}的非支配抗体，当且仅当抗体种群B中不存在抗体

吃(J=1，2，⋯，n^j ≠f)使得

(V，∈”· ，M}，彳(P。1(乞))≤石(P‘1(匆)))

^3l∈”· ，M)，石(e-I(包))<石(P_(6J)))

这样，抗体种群B中所有的非支配抗体组成了Pareto最优解集。