本文提出了利用遗传算法求解多目标优化问题的一种有效方法——基于存档策略的多目标数值优化遗传算法，并讨论了算法的收敛性。通过在算法中嵌入一个多目标线搜索算子，加强了算法的搜索能力，提高了收敛速度。 本文所要求解的多目标优化问题的数学模型为： (MP)minf(x)=(f1(x)，f2(x)，…fq(x))Ts.tx=(x1，x2，…，xn)T∈Rnai≤xi≤bi，i=1，2，…，n。多目标遗传算法的有关概念定义1(支配关系)设X、Y为种群(→X)(t)中的个体，如果满足：fi(x)≤fi(y)，对任意i∈{1，2，…，n}fj(x)＜fj(y)，至少有一个j∈{1，2，…，n}则称个体X支配个体Y，或称个体Y被个体X支配。 定义2(非支配个体)如果在种群(→X)(t)中不存在个体Y，使个体Y支配个体X，则称X为种群(→X)(t)中的非支配个体。 定义3(Pareto秩)设在种群(→X)(t)中，有p(t)i个个体支配Xi，则定义个体Xi的秩为rank(Xi，t)=1+p(t)i，非支配个体的秩为1。 定义4(档案)我们称一个独立于进化过程的集合(→A)(t)为档案，用于保存到当前代为止非支配个体E(t)及相应的多目标函数值f((→E)(t))，即(→A)(t)=(→E)(t)∪f((→E)(t))。同时称{(→A)(t)}∞t=1为档案序列。 本文采取Pareto秩的方法确定个体的适应度并由此划分赌轮；其中采用了完全算术交叉算子、边界变异算子和初始化变异算子相结合的混合变异算子。这些算子都是我们在已有遗传算子的基础上加以改进形成的，改进的指导思想是充分利用多目标数值优化的特点所提供的信息。 存档算子，本算法采取一种主要策略，基本思想是：在进化过程之外设有一个集合称之为档案，记为(→A)(t)，用于保存每一代中的非支配个体。具体方法如下： (1)通过支配关系选择出当前代种群(→X)(t)中的非支配个体X*。 (2)将X*与档案(→A)(t)中的个体放在一起进行比较：若X*被档案(→A)(t)中的个体所支配，则X*直接被剔除；若X*与档案(→A)(t)中的个体无支配关系，则X*进入档案(→A)(t)；若X*支配档案(→A)(t)中的某些个体，则X*进入档案(→A)(T)，并剔除那些被支配个体。档案(→A)(t)中的个体在进化过程中保持非支配地位。 (3)当算法终止时，档案(→A)(t)中的解集即为所要求的Pareto最优集B*的近似集。 在交叉过程中嵌入多目标线搜索算子在本算法中起着关键性的作用。方法叙述如下： 任选一不被支配个体xi作为基点，随机地选一个被xi支配的个体xj，确定搜索方向(→d)=xi-xj。以xi为基点在方向(→d)上寻找最优个体x*=x1+λ*(→d)，其中，λ*=argPartoMinf(xi+λ(→d))用x*代替xi。确定λ*的具体做法如下：λ∈[0,λmax](1)初始化首先确定λ的上界λmax，以保证xi+λ(→d)在可行域内。设xi=(xi1，xi2，…，xi,)T，x*=(x*1，x*2，…，x*n)T，(→d)=(d1，d2，…，dn)T。由x*=xi+λ*(→d)，ak≤x*k≤bk。由得：当dk=0时，λ不受第κ坐标方向限制； 当dk＞0时，设λ1=min(bk-xik)/dk；当dk＜0时，设λ2=min(ak-xik)/dk。其中k=1，2，…，n。则取λmax=min(λ1，λ2)，置xb=xi+λmax(→d)。 (2)多目标线搜索 在线段[xi，xb]上搜索非支配点x*，即确定最优步长λ*，使x*=xi+λ*(→d)。为此我们设计基于Pareto支配关系的二分法多目标线搜索： 算法描述如下： 步1：置λ←λmax，xl←xi，xr←xi+λ(→d)；如果fk(xl)≥fk(xr)，k=1，2，…，q，算法停止，输出x*=xr，否则，转步2。 步2：置λ←1/2λ。 步3：如果fk(x1)≥fk(xr)，k=1，2，…，q，置xl←xi+λ(→d)；否则，置xr←xi+λ(→d)。 步4：若满足终止准则λ＜ε(事先给定的正数)，则取x*=xl+xr/2，否则，转步2。 算法之后，通过算例检验了算法的有效性。 最后，从理论上证明本算法的收敛性。主要概念与结论如下： 定义5设S为n维空间Rn中的有限离散点集，记为S={A1，A2，…，Am}，，其中Ai(xi1，xi2，…，xin)，(i=1，2，…，m)，设xij≥0，(i=1，2，…，m；j=1，2，…，n)。则点Ai与区域Di={(x1，x2，…，xn)|0≤xl≤xij，j=1，2，…，n}(i=1，2，…，m)相对应，点集S与区域m∪i=1Di相对应，定义区域m∪i=1Di的Lebesque测度为点集的S的测度，记为Ωs。 定义6对档案序列{(→d)(t)}∞t=1的任意两个解集合(→E)(i)，(→E)(j)，设Si=f((→E)(i))，Sj=f((→E)(j))，则Si，Sj均为判据空间Rq中的有限离散点集，定义点集Si与Sj之间的距离为d(Si，Sj)|ΩSi-ΩSj|。 其中ΩSi，ΩSj分别为点集Si，Sj的测度。 设档案(→A)(t)与Pareto最优面B*之间的距离为dt，则dt=|Ω(→A(t)-ΩB*|。设Dt表示取值为dt的随机变量，则{Dt}为时间序列。 时间序列{Dt}有以下性质： (1)P{Dt≥0}=1； (2)当Dt=d时，有Dl+1≤d，当然有P{Dt+l≤dt|Dt=dt}=1，即dt为Dt+1的上界； (3)当dt≠0(dt＞0)时，存在0＜δ≤1使P{Dt+1＜dt|Dt=dt}≥δ＞0。 定理1若时间序列{Dt}满足P{Dt+1＜dt|Dt=dt}≥δ＞0则时间序列几乎必然收敛到0，即有P{limt→∞Dt=0}=1。定理2时间序列{Dt}几乎必然收敛到0，当且仅当档案序列{(→A)(t)}几乎必然收敛到Pareto最优面B*。定理4.2说明当t→∞时，档案序列{(→A)(t))}以概率1收敛到Pareto最优面B*。