摘要：为解决多目标规划问题中快速有效的任务分配和调度问题，基于遗传算法进化过程中每代种群均生成大量可行解,提出一种基于目标序列的排序矩阵评价个体适应度的多目标遗传算法,并对遗传算法进行了改进。优化的算法通过可行解之间相互比较，有效控制了非劣解集的替换选取过程,使得算法可以求得非劣解集。最后将该方法应用于发电厂的多目标调度中,验证了其可行性。

　　关键词：多目标规划 遗传算法 优化技术 分配和调度

　　1 前言

　　多目标优化问题，实质上是在多个标准的约束下，寻求解决问题的最佳方案。多目标最优化的理论和方法在经济规划、计划管理、金融决策、能源开发、工程设计、农业种植、卫生保健以及军事科学等领域都有大量应用。但是在多目标优化中，由于同时考虑多个目标，要其同时最优一般是不可能的，于是转为讨论如何寻求一个最优解，即非劣最优解。近年来，遗传算法GA(Genetic Algorithm)已广泛应用于多目标优化非劣解的求解，但是如何评价非劣解质量的好坏还没有满意的结论。因为多目标问题中非劣解往往是一个解集，每一个非劣解都具有在不同程度上满足多个目标的优越性，而实际应用中只需要一个解。因此，多目标优化的求解需要解决两个问题：

　　(1) 如何求得非劣解;

　　(2) 非劣解的优性如何鉴别。

　　对于(1)，传统的多目标优化方法是将各子目标聚合为一带权系数的单目标函数，求解此单目标函数以获得非劣解。现代采用遗传算法获得Pareto非劣

　　解集。而问题(2)目前多采用基于偏好的方法，由决策者根据目标之间的相对偏好关系，给出一组权系数，但这种方法使非劣解对偏好非常敏感，而且给出客观权系数也是困难的。

　　再者，分布式系统提供了巨大的处理能力，然而，为了实现和充分利用这种能力，需要优良的任务分配和调度方案。快速有效的任务分配和调度是分布式系统中一个关键的问题，其实质是将任务合理和透明地在处理机之间进行分配，并重新排列任务的执行顺序，以符合任务依赖关系的要求，使整个系统的任务能在最短的时间内完成，从而达到系统的综合性能最优，为问题的解决提供了新的思路。

　　为此，本文根据遗传算法中每一代都有大量的可行解产生这一特点,我们考虑对该算法进行优化，即通过可行解之间相互比较，淘汰劣解的办法来达到对非劣解集的逼近。最后产生一条解决问题的最优的路径。并进行实际应用。主要工作或创新如下：

　　(1)提出一种基于目标序列的排序矩阵评价个体适应度的多目标遗传算法。

　　(2)将模糊优选理论应用于并列选择遗传算法。

　　2 算法原理

　　(1)遗传算法简介

　　遗传算法是一种全局随机优化算法，具有在复杂空间求解问题近似最优解的能力。其基本思想就是模拟生物界自然进化和遗传过程。通过一定的编码技术将问题的解进行编码，再利用选择、杂交、变异三种基本操作模拟由这些串组成群体的进化过程。标准遗传算法(SGA)是由Holland提出的，遗传算法的流程图，如图 1 所示：

　　图 1 遗传算法的流程图

　　传统的遗传算法的缺点是只以单个目标函数值作为选择的标准，而没有体现目标之间的关系，这样往往陷入单个目标函数的局部最优解。而基于相对隶属度的多准则模糊优选模型可以给出有限个方案的相对隶属度，把相对隶属度作为适应度函数在总群体中进行选择，将有效的改善以上缺点，从而满足了整体最优性，又尽可能的使各子目标最优。

　　(2)基于目标序列的排序矩阵评价个体适应度的多目标遗传算法

　　考虑一个n维的多目标规划问题,且均为目标函数最大化,其劣解可以定义为：

　　f (x*) f (x) (i=1,2,…,n) (1)

　　且式(1)至少对一个i取 “ < ” 即至少劣于一个可行解的x*，必为劣解。优解的选择替换，必须使得解集的分布具有一定程度的均匀性，所以在多目标遗传算法中要对交叉和变异概率依据种群和进化代数进行自适应调整,并控制种群个体并行向非劣解集前沿面逼近。即采用基于目标序列的排序矩阵评价个体适应度的多目标遗传算法。

　　(3)算法步骤 ：

　　Step 1. 适应度确定 ：

　　个体适应度是通过个体间的相互比较得到,使综合表现优良的个体获得较大适应度。算法中个体采用实数编码,只需知道各目标函数的优劣衡量标准(越大越优,越小越优或中心最优)即可将个体对目标表现优劣排序"将种群所有个体对各目标表现排序就能得到(表1)列出的表现矩阵：

　　表1 基于目标函数的表现距阵

　　目 标

　　排 序

　　表现

　　序列

　　1

　　2

　　…….

　　N

　　Obj (1)

　　X

　　X

　　……..

　　X

　　Obj (2)

　　X

　　X

　　……..

　　X

　　……..

　　……

　　………

　　…….

　　……….

　　………

　　Obj (n)

　　X

　　X

　　………

　　X

　　表中，Obj(i)(i=1,,,n)为目标函数，n为目标个数;N为个体总数，即可行解的数量。针对每一个目标i，所有个体都会依据对该目标的函数值优劣生成一个可行解的排序序列Xi，对每个目标都排序后，可以得到个体对全部目标函数的总体表现。根据个体的排序计算其适应度，即：

　　(i = 1, 2，……，n) (2)

　　( j=1,2，……，N; )(3)

　　式中, X为种群的第j个个体;R为其在种群所有个体中对目标i的优劣排序后所得的序号; ()表示对目标i所得的适应度, E ()为对全部目标所得的综合适应度;k为(1,2)区间的常数,用于加大个体的函数值表现最优时的适应度。由上式可以看出,对于总体表现较优的个体能得到更大的适应度,获得更多的参与进化的机会。

　　Step 2. 和的自适应计算

　　选择,交叉,变异均按一般遗传算法方式进行,交叉概率和变异概率以自适应的方式选定,即通过个体本身适应度大小和种群整体性能的比较确定其交叉和变异的概率，其计算公式如下:

　　(4)

　　(5)

　　式中: f 为群体中最大的适应度值; f 为群体的平均适应度值; f 为可能进行交叉的2个个体中较大的适应度值; f为进行变异的个体的适应度值; 其中k1,k2,k3,k4 [0,1] 。

　　通过该公式实际上反映了同一代种群中不同个体的和与其适应度的线性函数关系。个体适应度小于种群平均值时,其和分别取固定值， 一般计算中取= K，= K.当其大于平均值而小于个体适应度越大则, 越小,得到保存的机会也越大,反之则相反。当适应度低于平均适应度时,说明该个体是表现较差的个体,对它就采用较大的交叉率和变异率;如果适应度高于平均适应度,说明该个体性能优良,对它就根据其适应度值取相应的交叉率和变异率。而交叉概率和变异概率的取值的上限为k1,k3,这样进化的稳定性也得到了保证。这种自适应调整是针对计算中同一代种群中不同个体对和取值的自适应选取。

 1/3    1 2 3 下一页 尾页