论文部分内容阅读
摘要：演化算法因其内在的并行行，在求解多目标优化问题时具有独特的优势。本文介绍多目标演化算法的基本原理，并详细讨论基于Pareto最优概念的多目标演化算法。
关键词：多目标优化；Pareto最优解；演化算法
中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)20-30262-02
Evolutiaon Algorithm for Multi-Objective Optimization Problems
MO Hai-fang
(Computer and Experiment Center, South-Center University For Nationality, Wuhan 430074, China)
Abstract: Evolut ionary algorithm is especially suitable to solve multi-object ive optimization problems. The basic principle of multi-object ive evolution algorithm is introduced, and the Pareto optimial-based evolutionary approach is discussed.
Key words: multi-objective optimization; Pareto optimal solutions; evolution algorithm
1 引言
多目标问题的求解是近年来优化计算的一个热点问题。与单目标问题不同，多目标问题的解不是单一的解，而是一组相互之间不可比较，甚至是相互冲突的解。因此求解多目标问题比求解单目标问题要困难得多。
求解多目标问题的传统方法主要有加权法、层次优化法、目标规划法等，这些方法的主要思想是对多目标进行权重分配，转化为单目标问题，然后运用单目标优化技术进行求解。这类方法需要较多的先验知识，而且计算效率低。
演化算法（EA）是一类模拟自然界生物进化的全局性概率优化搜索方法，因为其内在的并行性，特别适合于求解复杂的多目标优化问题。
基于向量评估的VEGA算法是Schaffer于1985年提出的，这是第一个多目标演化算法。该算法的主要思想是在每一代中根据各目标函数，用适应度比例法产生一定数目的子种群，然后把它们合并成新的一代，继续执行交叉和变异等遗传操作。VEGA算法在本质上仍然是加权和的方法。随后有许多成功的多目标演化算法被提出。1993年，Fonseca和Fleming提出MOGA算法，Horn和Nafploitis提出NPGA算法，Srinivas和Deb提出NSGA算法。其中MOGA最著名，这是基于Pareto最优概念的算法，它统计出群体中优于某个体的个体数量，并依此计算该个体的适应值。同时采用自适应的小生境技术和受限杂交技术来提高种群多样性。1999年，Zitzler和Thiele提出了SPEA算法，该算法采用精英保留策略来提高多目标进化算法的性能。这些算法都能成功求解多目标问题，它们的实现基于以下基本的策略：Pareto最优策略和保持种群多样性的策略。
2 多目标优化问题中的一些概念
一般地，一个多目标优化问题可以归结为多个目标的极小化模型：
定义1：多目标优化问题
v-min f(x)=[(f1(x), f2(x), …,fm(x))]T
subject to x ∈X
X?哿Rm
其中的v-min表示向量极小化，即向量目标函数f(x)=[(f1(x),f2(x),…,fm(x))]T中的各子目标函数都尽可能地极小化。
然而在很多情况下，多目标优化问题中的各个子目标是相互冲突的，一个子目标性能的改善可能会引起另一个子目标性能的降低，也就是说，一个能够同时使所有目标函数达到最优的解很可能是不存在的，只能在它们之间进行协调和折衷处理，使各个子目标函数都尽可能地达到最优。为了对多目标问题的解进行比较, 先给出Pareto最优解的定义。
定义2：Pareto占优
任何两个决策向量a∈X和b∈X，如果f(a) 定义3：Pareto最优解
如果不存在y∈X，使fi(y)≤fi(x), i=1,2,…,m，且至少有一个严格不等式成立，则称x∈X是多目标优化问题的Pareto最优解，或称为非劣解。
通常的多目标问题的Pareto最优解都有很多，把Pareto最优解的集合称为Pareto前沿。由定义3可知，Pareto最优解集中的解是彼此不可比较的，解集中的解数量越多，分布越广泛, 决策者的选择空间越大，越能对实际多目标问题进行合理求解。
3 多目标演化算法
多目标演化算法的大致流程如下：
1) 初始化：产生初始群体P(0)；
2) 计算个体的适应值；
3) 在群体P(t)中执行选择、交叉和变异等进化操作产生下一代种群P(t+1)；
4) 若满足结束条件则将退出，否则转到步骤3)。
3.1 基于Pareto非劣概念的排名
用Pareto非劣解的概念计算个体适应值的方法首先是由Goldberg于1989年提出的。他提出排序方法（Ranking）和基于序的适应度函数形式。先将多目标函数值组成一个向量代表一个个体，假设个体xi在t代群体中有n个个体优于它，则它在群体中的序为：rank(xi)=1+n。如图1所示，当前群体中所有非劣最优解的序都为1。
图1 群体中个体的Pareto序
排序仅仅体现了各个个体之间的优越次序，没有体现各个个体的分散程度，所以容易导致最终得到很多个相似的Pareto最优解，而难于获得分布均匀的Pareto最优解。
3.2 群体多样性
为了逼近Pareto最优解集，就要得到多个不同的解，因此，群体多样性极其重要。为了提高群体多样性，多目标演化算法已经提出了多种小生境与共享技术，以求获得均匀分布得Pareto最优解集。已有的保持群体多样性的方法有：适应值共享、受限杂交、孤岛模型、重新初始化、拥挤机制等。比较适合多目标演化算法的是适应值共享。
适应值共享的思路是：同一个小生境中（Niche）的个体必须共享资源。一个个体有越多的邻居（neighborhood），那么该个体的适应值越小。
两个个体之间的空间距离小于某个伐值（Niche radius）时，就成为邻居（neighborhood），一个个体的邻居数量称为小生境数（Niche Count）。某個个体的适应值除以它的小生境数就得到它调整后的适应值，从而使有多个相似的个体降低了适应值，减少了它们遗传到下一代群体的机会。
3.3 精英策略
SPEA算法采用精英保留策略来提高多目标进化算法的性能。精英是指一代群体中适应值较高的个体。在多目标演化算法中，在每一代群体中都有多个精英，把这些精英保存到一个精英集合中，然后按照概率从这个集合中再选择优秀个体进入下一代群体，从而加快了算法的收敛速度，提高算法的性能。
4 测试函数
minimize T(x)=(f1(x1),f2(x2)
subject to f2(x)=g(x2,…, xm)h(f1(x1),g(x2,…,xm))
where x=(x1,x2,…,xm)
测试函数1：
f1(x1)=x1
(m=30并且xi∈[0,1]。当达到Pareto前沿时g(x)=1)
5 结束语
多目标演化算法具有广泛的应用前景，目前已经被成功应用到自动控制、机械设计、航空航天、网络通信、作业调度、图像处理、生命科学等多个领域。随着多目标演化算法在理论上的深入探索，必将在更多领域得到应用。
多目标演化算法的研究在近年来取得了许多成果，进一步值得研究的问题包括：加强多目标演化算法的基础理论研究，从理论上证明算法的收敛性，设计能反映多目标演化算法基本特征的测试函数；对于高维多目标优化问题，研究新的非基于Pareto 最优概念的群体排序方法；结合领域知识，设计专门的多目标演化算法。
参考文献：
[1] 谢涛, 陈火旺, 康立山. 多目标优化的演化算法[J]. 计算机学报, 2003,26(8):997-1007.
[2] 马清亮, 胡昌华. 多目标进化算法及其在控制领域中的应用综述[J].控制与决策, 2006,21(5):481-486.
[3] 祁荣宾, 钱锋, 杜文莉, 等. 基于精英选择和个体迁移的多目标遗传算法[J]. 控制与决策, 2007,22(2):164-168.
[4] 陈柳, 周伟, 张国平. 一种基于树结构排序的多目标优化演化算法[J]. 计算机工程与应用. 2005,(2):90-93.
[5] 陈国良, 王熙法, 庄镇泉, 等. 遗传算法及其应用[M]. 北京：人民邮电出版社，2001.
[6] 王小平, 曹立明. 遗传算法理论、应用与软件实现[M]. 西安：西安交通大学出版社，2002.
关键词：多目标优化；Pareto最优解；演化算法
中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)20-30262-02
Evolutiaon Algorithm for Multi-Objective Optimization Problems
MO Hai-fang
(Computer and Experiment Center, South-Center University For Nationality, Wuhan 430074, China)
Abstract: Evolut ionary algorithm is especially suitable to solve multi-object ive optimization problems. The basic principle of multi-object ive evolution algorithm is introduced, and the Pareto optimial-based evolutionary approach is discussed.
Key words: multi-objective optimization; Pareto optimal solutions; evolution algorithm
1 引言
多目标问题的求解是近年来优化计算的一个热点问题。与单目标问题不同，多目标问题的解不是单一的解，而是一组相互之间不可比较，甚至是相互冲突的解。因此求解多目标问题比求解单目标问题要困难得多。
求解多目标问题的传统方法主要有加权法、层次优化法、目标规划法等，这些方法的主要思想是对多目标进行权重分配，转化为单目标问题，然后运用单目标优化技术进行求解。这类方法需要较多的先验知识，而且计算效率低。
演化算法（EA）是一类模拟自然界生物进化的全局性概率优化搜索方法，因为其内在的并行性，特别适合于求解复杂的多目标优化问题。
基于向量评估的VEGA算法是Schaffer于1985年提出的，这是第一个多目标演化算法。该算法的主要思想是在每一代中根据各目标函数，用适应度比例法产生一定数目的子种群，然后把它们合并成新的一代，继续执行交叉和变异等遗传操作。VEGA算法在本质上仍然是加权和的方法。随后有许多成功的多目标演化算法被提出。1993年，Fonseca和Fleming提出MOGA算法，Horn和Nafploitis提出NPGA算法，Srinivas和Deb提出NSGA算法。其中MOGA最著名，这是基于Pareto最优概念的算法，它统计出群体中优于某个体的个体数量，并依此计算该个体的适应值。同时采用自适应的小生境技术和受限杂交技术来提高种群多样性。1999年，Zitzler和Thiele提出了SPEA算法，该算法采用精英保留策略来提高多目标进化算法的性能。这些算法都能成功求解多目标问题，它们的实现基于以下基本的策略：Pareto最优策略和保持种群多样性的策略。
2 多目标优化问题中的一些概念
一般地，一个多目标优化问题可以归结为多个目标的极小化模型：
定义1：多目标优化问题
v-min f(x)=[(f1(x), f2(x), …,fm(x))]T
subject to x ∈X
X?哿Rm
其中的v-min表示向量极小化，即向量目标函数f(x)=[(f1(x),f2(x),…,fm(x))]T中的各子目标函数都尽可能地极小化。
然而在很多情况下，多目标优化问题中的各个子目标是相互冲突的，一个子目标性能的改善可能会引起另一个子目标性能的降低，也就是说，一个能够同时使所有目标函数达到最优的解很可能是不存在的，只能在它们之间进行协调和折衷处理，使各个子目标函数都尽可能地达到最优。为了对多目标问题的解进行比较, 先给出Pareto最优解的定义。
定义2：Pareto占优
任何两个决策向量a∈X和b∈X，如果f(a)
如果不存在y∈X，使fi(y)≤fi(x), i=1,2,…,m，且至少有一个严格不等式成立，则称x∈X是多目标优化问题的Pareto最优解，或称为非劣解。
通常的多目标问题的Pareto最优解都有很多，把Pareto最优解的集合称为Pareto前沿。由定义3可知，Pareto最优解集中的解是彼此不可比较的，解集中的解数量越多，分布越广泛, 决策者的选择空间越大，越能对实际多目标问题进行合理求解。
3 多目标演化算法
多目标演化算法的大致流程如下：
1) 初始化：产生初始群体P(0)；
2) 计算个体的适应值；
3) 在群体P(t)中执行选择、交叉和变异等进化操作产生下一代种群P(t+1)；
4) 若满足结束条件则将退出，否则转到步骤3)。
3.1 基于Pareto非劣概念的排名
用Pareto非劣解的概念计算个体适应值的方法首先是由Goldberg于1989年提出的。他提出排序方法（Ranking）和基于序的适应度函数形式。先将多目标函数值组成一个向量代表一个个体，假设个体xi在t代群体中有n个个体优于它，则它在群体中的序为：rank(xi)=1+n。如图1所示，当前群体中所有非劣最优解的序都为1。
图1 群体中个体的Pareto序
排序仅仅体现了各个个体之间的优越次序，没有体现各个个体的分散程度，所以容易导致最终得到很多个相似的Pareto最优解，而难于获得分布均匀的Pareto最优解。
3.2 群体多样性
为了逼近Pareto最优解集，就要得到多个不同的解，因此，群体多样性极其重要。为了提高群体多样性，多目标演化算法已经提出了多种小生境与共享技术，以求获得均匀分布得Pareto最优解集。已有的保持群体多样性的方法有：适应值共享、受限杂交、孤岛模型、重新初始化、拥挤机制等。比较适合多目标演化算法的是适应值共享。
适应值共享的思路是：同一个小生境中（Niche）的个体必须共享资源。一个个体有越多的邻居（neighborhood），那么该个体的适应值越小。
两个个体之间的空间距离小于某个伐值（Niche radius）时，就成为邻居（neighborhood），一个个体的邻居数量称为小生境数（Niche Count）。某個个体的适应值除以它的小生境数就得到它调整后的适应值，从而使有多个相似的个体降低了适应值，减少了它们遗传到下一代群体的机会。
3.3 精英策略
SPEA算法采用精英保留策略来提高多目标进化算法的性能。精英是指一代群体中适应值较高的个体。在多目标演化算法中，在每一代群体中都有多个精英，把这些精英保存到一个精英集合中，然后按照概率从这个集合中再选择优秀个体进入下一代群体，从而加快了算法的收敛速度，提高算法的性能。
4 测试函数
minimize T(x)=(f1(x1),f2(x2)
subject to f2(x)=g(x2,…, xm)h(f1(x1),g(x2,…,xm))
where x=(x1,x2,…,xm)
测试函数1：
f1(x1)=x1
(m=30并且xi∈[0,1]。当达到Pareto前沿时g(x)=1)
5 结束语
多目标演化算法具有广泛的应用前景，目前已经被成功应用到自动控制、机械设计、航空航天、网络通信、作业调度、图像处理、生命科学等多个领域。随着多目标演化算法在理论上的深入探索，必将在更多领域得到应用。
多目标演化算法的研究在近年来取得了许多成果，进一步值得研究的问题包括：加强多目标演化算法的基础理论研究，从理论上证明算法的收敛性，设计能反映多目标演化算法基本特征的测试函数；对于高维多目标优化问题，研究新的非基于Pareto 最优概念的群体排序方法；结合领域知识，设计专门的多目标演化算法。
参考文献：
[1] 谢涛, 陈火旺, 康立山. 多目标优化的演化算法[J]. 计算机学报, 2003,26(8):997-1007.
[2] 马清亮, 胡昌华. 多目标进化算法及其在控制领域中的应用综述[J].控制与决策, 2006,21(5):481-486.
[3] 祁荣宾, 钱锋, 杜文莉, 等. 基于精英选择和个体迁移的多目标遗传算法[J]. 控制与决策, 2007,22(2):164-168.
[4] 陈柳, 周伟, 张国平. 一种基于树结构排序的多目标优化演化算法[J]. 计算机工程与应用. 2005,(2):90-93.
[5] 陈国良, 王熙法, 庄镇泉, 等. 遗传算法及其应用[M]. 北京：人民邮电出版社，2001.
[6] 王小平, 曹立明. 遗传算法理论、应用与软件实现[M]. 西安：西安交通大学出版社，2002.