多目标优化的遗传算法及其实现
- 格式：pdf
- 大小：1.36 MB
- 文档页数：4
定义 3 设 X 是多目标优化模型的约束集, f (X ) 是多目标优 化时的向量目标函数, 若有解 x 1 X, 并且不存在比 x1 更优越的解 x, 则称 x1 是 多目标优化模型的 Pareto最优解 [ 5, 6 ] . 2. 2 多目标优化和遗传算法的融合、发展状况 及分类
由于遗传算法是对一个种群并行地进行运 算操作, 它运行一次能找到多目标优化问题的多 个 P are to最优解, 因而它是求解多目标优化问题 的 P are to最优解集合的一个有效手段. 求解多目 标优化问题的遗传算法主要有以下几种: 2. 2. 1 权重系数变换法
,
X
* n
]T
来优化目 标
F (X )
=
[ f1 (X ), f 2 (X ), , fk (X ) ] T. 一个多目标优化问
题通常包含 k个目标和 (m + p + q ) 个限制条件,
定义 x 为 变 量 的 函 数 为: M in /M ax f (x ) =
( f1 (X ), f 2 (X ), , fk (X ) ) Y. 限制条件为: gi (x ) 0, 对 i = 1, 2, , m;
多目标优化的遗传算法及其实现
胡贵强
( 西南大学 计算机与信息科学学院, 重庆 400715)
[ 摘 要 ]遗传算法是一种通过模拟自然进化过程搜索最优解的方法, 在优化方法中具有独特 的优越性, 有着非常重要的理论意义和广泛的应用领域. 多目标优化问题求解已成为遗传算法 的一个重要研究方向, 而基于 Pareto 最优概念的多目标遗传算法则是当前遗传算法的研究热 点. 本文对遗传算法的理论基础进行分析, 包括模式定理等, 讨论用遗传算法来解决多目标优 化问题的方法并给出其实现, 介绍遗传算法的各种改进措施, 并指出遗传算法的发展动向. [ 关键词 ]遗传算法; 多目标优化; Pareto最优 [ 中图分类号 ] TP301. 6 [文献标识码 ] A [ 文章编号 ] 1673- 8012( 2008) 05- 0012- 04
reto首先在经 济平衡的研究中提出了多目标规
划问题, 引进了所谓 P areto 最优解的概念. 此外, 1927 年数学家 F. H ausdorff 对关于展提供 了理论工
具. 1947年, J. Von N eum an 和 O. M o rgenstern 在
f (X ) 是 多 目 标 优 化 时 的 向 量 目 标 函 数, 若 fk (x 1 ) fk ( x2 ), 任取 k = 1, 2, , n, 且 f j (x1 ) < f j ( x2 ), 存在 j = 1, 2, , n, 则称解 x1 比 x2 优越.
定义 2 设 X 是多目标优化模型的约束集, f (X ) 是多目标优 化时的向量目标函数. 若有解 x 1 X, 并且 x1 比 X 中所有其他解都优越, 则称 解 x 1 是多目标优化模型的最优解 [ 3] .
极大极小法的基本思想是: 先生成初始的种 群, 然后对每个子目标函数均计算种群适应度的 和的值. 对每代染色体选择, 使它们的适应度值 的和最劣的函数作为目标函数. 2. 2. 5 混合法
混合法的基本思想是: 选择算子的主体使用并 列选择法, 然后通过引入保留最佳个体和共享函数 的思想来弥补只使用并列选择法的不足之处. 2. 3 多目标优化算法设计及 MATLAB实现 2. 3. 1 算法设计
排列选择法的基本思想是: 基于 Pareto 最 优个体 的概念对种群中的所有个体进行排序,
所有属于同一层次的 Pareto 最优解赋以同样的 繁殖概率, 依据此概率进行选择, 从而使得排在 前面的 P areto 最优个体有更多的机会遗传给下 一代种群. 如此这样, 经过一定代数的循环之后, 最终可求出多目标优化问题的 P areto 最优解. 2. 2. 4 极大极小法
* [收稿日期 ] 2008- 08 - 28 [ 作者简介 ] 胡贵强 ( 1983 - ), 男, 重庆永川人, 西南大学硕士研究生.
12
hj (x ) = 0, 对 j = 1, 2, , p. 下面介绍多 目标优化中最优解和 Pareto 最
优解的定义. 定义 1 设 X 是多目标优化模型的约束集,
13
( 4) 函数 rank ing. 基于排序的适应 度分配. ranking按照个体的目 标值 ObjV 由小到大的顺 序对它们进行排序.
( 5) 函数 selec.t 从群中选择个体. ( 6) 函数 recomb in. 重组个体, xovsp 为单 点交叉的意思. ( 7) 函数 mu.t 离散变异算子, 用来变异操作. 初始化程序的源码如下: N IND = 100; % 个体数目 ( Number of in d ividu als) MAXGEN = 50; % 最大遗传代数 ( M ax i m un num ber of generat ions) NVAR = 2; % 变量个数 ( Num ber o f vari ab les) PRECI = 20; % 变量的二进制位数 ( P re cision o f variab les) GGA P = 0. 9; % 代沟 ( Generation gap) trace1 = [ ] ; trace2 = [ ]; trace3 = [ ] ; % 性能跟踪 ( T race the perform ance of GA ) F ie ldD = [ rep ( [ PREC I] , [ 1, NVAR ] ); [ 1, 1; 4, 2] ; rep ( [ 1; 0; 1; 1], [ 1, NVAR ] ) ]; % 建立区域描述器 ( Build field descriptor) Chrom = crtbp ( N IND, NVAR* PRECI ); % 初始种群 ( In itialize the chromosom e popu la t ion) v = bs2rv ( Chrom, F ieldD ); % 初始种群 十进制转换 ( B inary to dec im al) 后面所有方法均采用此初始化程序. 所有的 程序以 m 文件的格式附后. 3 实验结果与分析 采用上述描述的多目标的遗传算法实现上 述 2个目标优化的问题. 总共采用了上述 5种方 法实现问题, 下面给出 5种方法的表现结果. 3. 1 多目标遗传算法的实现一
并列选择法的基本思想是, 先将配对库的全 部个体按子目标函数的数目均等地划分为一些
子配对库, 对每个子 配对库分 配一个子 目标函 数, 配对库 i 的个体是根据第 i 个目标函数从当 前种群中随机选择的个体组成的; 然后将所有这 些子配对库合并为一个完整的中间群, 再在这个 中间种群中进行杂交和变异运算, 从而生成下一 代种群. 如此这样不断地循环, 最终可求出多目 标优化问题的 Pareto 最优解. 2. 2. 3 排列选择法
算法设计上, 还是在基础理论上, 均取得了长足 的发展, 应用也非常广泛. 本文通过对基本遗传 算法的研究, 以及对其在多目标优化问题上的实 现, 在遗传算法领域进行探讨, 并通过程序来验 证. 在多目标优化问题的研究中, 所采用的一些 方法在一些算例中获得了比较好的 Pareto解集.
遗传算法是生命科学与工程科学互相交叉、 互相渗透的产物, 是一种求解问题的高度并行性 全局搜索算法. 近年来, 遗传算法已成为信息科 学、计算机科学、运筹学和应用数学等诸多学科 共同关注的热点研究领域.
在科学与工程实践中, 很多现实设计与决策 问题都是多目标问题, 而且各个目标之间很可能 是互相竞争的, 即无 法使各个 目标同时 达到最 优. 一般的多目标优化问题解决方法是将多目标 优化问题转化为优化方法比较成熟的单目标优 化问题, 但这样就很难客观评价所得多目标问题 的解的优劣性. 多目标优化问题与单目标优化问 题的本质不同在于: 多目标优化问题的最优解是 一个集合, 而不是一个全局最优解. 我们称这个 解集为 P areto最优解集.
3. 2 多目标遗传算法的实现二
图 2 并列选择法表现图
3. 3 多目标遗传算法的实现三
图 3 极大极小法表现图
3. 4 多目标遗传算法的实现四
图 4 排列选择法表现图
3. 5 多目标遗传算法的实现五
图 1 权重系数变换法 1 1 的表现图
14
图 5 混合法表现图
4 结语 经过近 10余年的努力, GA 不论是在应用、
下面是一个含有 2个目标的多目标优化问 题.
m in f1 = x (: , 1). * x (: , 1) / 4 + x (: , 2).
* x (: , 2) /4;
m in f 2 = x (: , 1). * ( 1 - x (: , 2) ) + 10; s. .t 1 x1 4, 1 x2 2. 可以采用最优解保存策略来求解. 第 1代进 化产生的最好的 n 个解 ( n 为非劣解集个数 ) 作 为现有非劣解集保存, 其个数由多目标问题的特 性和需要的非劣解数量要求确定, 一般取为种群 个体总数的 5% ~ 15% . 以后对于每一代进化所 产生的最好的一系列解与原有的非劣解集依据 式进行比较, 用所产生的更好的解代替原有的劣 解. 这样, 计算结束时所得到的就是算法中产生 的最好的非劣解, 从而构成非劣解集 [ 5] . 2. 3. 2 MATLAB遗传算法工具箱函数介绍 本文对多目标优化遗传算法用 MATLAB 加 以实现. 为了明确算法本身而不是程序设计, 我们 采用 MATLAB遗传算法工具箱来提高编程效率. 本文采用英国设菲尔德大学开发的遗传算法工具 箱. 下面仅对本次程序设计所用到的函数作介绍: ( 1) 函数 rep. rep是一个低级复 制函数, 通 常不直接使用, 它可被 GA 工具箱中许多函数调 用. ( 2) 函数 crtbp. 创建 初始种群. 遗传算法的 第 1步是 创建由任 意染色体 组成的原 始种群. crtbp创建一元素为随机数的矩阵 Chrom. ( 3) 函数 bs2rv. 二进制串到实值的转换函数.
由于遗传算法是对一个种群并行地进行运 算操作, 它运行一次能找到多目标优化问题的多 个 P are to最优解, 因而它是求解多目标优化问题 的 P are to最优解集合的一个有效手段. 求解多目 标优化问题的遗传算法主要有以下几种: 2. 2. 1 权重系数变换法
,
X
* n
]T
来优化目 标
F (X )
=
[ f1 (X ), f 2 (X ), , fk (X ) ] T. 一个多目标优化问
题通常包含 k个目标和 (m + p + q ) 个限制条件,
定义 x 为 变 量 的 函 数 为: M in /M ax f (x ) =
( f1 (X ), f 2 (X ), , fk (X ) ) Y. 限制条件为: gi (x ) 0, 对 i = 1, 2, , m;
多目标优化的遗传算法及其实现
胡贵强
( 西南大学 计算机与信息科学学院, 重庆 400715)
[ 摘 要 ]遗传算法是一种通过模拟自然进化过程搜索最优解的方法, 在优化方法中具有独特 的优越性, 有着非常重要的理论意义和广泛的应用领域. 多目标优化问题求解已成为遗传算法 的一个重要研究方向, 而基于 Pareto 最优概念的多目标遗传算法则是当前遗传算法的研究热 点. 本文对遗传算法的理论基础进行分析, 包括模式定理等, 讨论用遗传算法来解决多目标优 化问题的方法并给出其实现, 介绍遗传算法的各种改进措施, 并指出遗传算法的发展动向. [ 关键词 ]遗传算法; 多目标优化; Pareto最优 [ 中图分类号 ] TP301. 6 [文献标识码 ] A [ 文章编号 ] 1673- 8012( 2008) 05- 0012- 04
reto首先在经 济平衡的研究中提出了多目标规
划问题, 引进了所谓 P areto 最优解的概念. 此外, 1927 年数学家 F. H ausdorff 对关于展提供 了理论工
具. 1947年, J. Von N eum an 和 O. M o rgenstern 在
f (X ) 是 多 目 标 优 化 时 的 向 量 目 标 函 数, 若 fk (x 1 ) fk ( x2 ), 任取 k = 1, 2, , n, 且 f j (x1 ) < f j ( x2 ), 存在 j = 1, 2, , n, 则称解 x1 比 x2 优越.
定义 2 设 X 是多目标优化模型的约束集, f (X ) 是多目标优 化时的向量目标函数. 若有解 x 1 X, 并且 x1 比 X 中所有其他解都优越, 则称 解 x 1 是多目标优化模型的最优解 [ 3] .
极大极小法的基本思想是: 先生成初始的种 群, 然后对每个子目标函数均计算种群适应度的 和的值. 对每代染色体选择, 使它们的适应度值 的和最劣的函数作为目标函数. 2. 2. 5 混合法
混合法的基本思想是: 选择算子的主体使用并 列选择法, 然后通过引入保留最佳个体和共享函数 的思想来弥补只使用并列选择法的不足之处. 2. 3 多目标优化算法设计及 MATLAB实现 2. 3. 1 算法设计
排列选择法的基本思想是: 基于 Pareto 最 优个体 的概念对种群中的所有个体进行排序,
所有属于同一层次的 Pareto 最优解赋以同样的 繁殖概率, 依据此概率进行选择, 从而使得排在 前面的 P areto 最优个体有更多的机会遗传给下 一代种群. 如此这样, 经过一定代数的循环之后, 最终可求出多目标优化问题的 P areto 最优解. 2. 2. 4 极大极小法
* [收稿日期 ] 2008- 08 - 28 [ 作者简介 ] 胡贵强 ( 1983 - ), 男, 重庆永川人, 西南大学硕士研究生.
12
hj (x ) = 0, 对 j = 1, 2, , p. 下面介绍多 目标优化中最优解和 Pareto 最
优解的定义. 定义 1 设 X 是多目标优化模型的约束集,
13
( 4) 函数 rank ing. 基于排序的适应 度分配. ranking按照个体的目 标值 ObjV 由小到大的顺 序对它们进行排序.
( 5) 函数 selec.t 从群中选择个体. ( 6) 函数 recomb in. 重组个体, xovsp 为单 点交叉的意思. ( 7) 函数 mu.t 离散变异算子, 用来变异操作. 初始化程序的源码如下: N IND = 100; % 个体数目 ( Number of in d ividu als) MAXGEN = 50; % 最大遗传代数 ( M ax i m un num ber of generat ions) NVAR = 2; % 变量个数 ( Num ber o f vari ab les) PRECI = 20; % 变量的二进制位数 ( P re cision o f variab les) GGA P = 0. 9; % 代沟 ( Generation gap) trace1 = [ ] ; trace2 = [ ]; trace3 = [ ] ; % 性能跟踪 ( T race the perform ance of GA ) F ie ldD = [ rep ( [ PREC I] , [ 1, NVAR ] ); [ 1, 1; 4, 2] ; rep ( [ 1; 0; 1; 1], [ 1, NVAR ] ) ]; % 建立区域描述器 ( Build field descriptor) Chrom = crtbp ( N IND, NVAR* PRECI ); % 初始种群 ( In itialize the chromosom e popu la t ion) v = bs2rv ( Chrom, F ieldD ); % 初始种群 十进制转换 ( B inary to dec im al) 后面所有方法均采用此初始化程序. 所有的 程序以 m 文件的格式附后. 3 实验结果与分析 采用上述描述的多目标的遗传算法实现上 述 2个目标优化的问题. 总共采用了上述 5种方 法实现问题, 下面给出 5种方法的表现结果. 3. 1 多目标遗传算法的实现一
并列选择法的基本思想是, 先将配对库的全 部个体按子目标函数的数目均等地划分为一些
子配对库, 对每个子 配对库分 配一个子 目标函 数, 配对库 i 的个体是根据第 i 个目标函数从当 前种群中随机选择的个体组成的; 然后将所有这 些子配对库合并为一个完整的中间群, 再在这个 中间种群中进行杂交和变异运算, 从而生成下一 代种群. 如此这样不断地循环, 最终可求出多目 标优化问题的 Pareto 最优解. 2. 2. 3 排列选择法
算法设计上, 还是在基础理论上, 均取得了长足 的发展, 应用也非常广泛. 本文通过对基本遗传 算法的研究, 以及对其在多目标优化问题上的实 现, 在遗传算法领域进行探讨, 并通过程序来验 证. 在多目标优化问题的研究中, 所采用的一些 方法在一些算例中获得了比较好的 Pareto解集.
遗传算法是生命科学与工程科学互相交叉、 互相渗透的产物, 是一种求解问题的高度并行性 全局搜索算法. 近年来, 遗传算法已成为信息科 学、计算机科学、运筹学和应用数学等诸多学科 共同关注的热点研究领域.
在科学与工程实践中, 很多现实设计与决策 问题都是多目标问题, 而且各个目标之间很可能 是互相竞争的, 即无 法使各个 目标同时 达到最 优. 一般的多目标优化问题解决方法是将多目标 优化问题转化为优化方法比较成熟的单目标优 化问题, 但这样就很难客观评价所得多目标问题 的解的优劣性. 多目标优化问题与单目标优化问 题的本质不同在于: 多目标优化问题的最优解是 一个集合, 而不是一个全局最优解. 我们称这个 解集为 P areto最优解集.
3. 2 多目标遗传算法的实现二
图 2 并列选择法表现图
3. 3 多目标遗传算法的实现三
图 3 极大极小法表现图
3. 4 多目标遗传算法的实现四
图 4 排列选择法表现图
3. 5 多目标遗传算法的实现五
图 1 权重系数变换法 1 1 的表现图
14
图 5 混合法表现图
4 结语 经过近 10余年的努力, GA 不论是在应用、
下面是一个含有 2个目标的多目标优化问 题.
m in f1 = x (: , 1). * x (: , 1) / 4 + x (: , 2).
* x (: , 2) /4;
m in f 2 = x (: , 1). * ( 1 - x (: , 2) ) + 10; s. .t 1 x1 4, 1 x2 2. 可以采用最优解保存策略来求解. 第 1代进 化产生的最好的 n 个解 ( n 为非劣解集个数 ) 作 为现有非劣解集保存, 其个数由多目标问题的特 性和需要的非劣解数量要求确定, 一般取为种群 个体总数的 5% ~ 15% . 以后对于每一代进化所 产生的最好的一系列解与原有的非劣解集依据 式进行比较, 用所产生的更好的解代替原有的劣 解. 这样, 计算结束时所得到的就是算法中产生 的最好的非劣解, 从而构成非劣解集 [ 5] . 2. 3. 2 MATLAB遗传算法工具箱函数介绍 本文对多目标优化遗传算法用 MATLAB 加 以实现. 为了明确算法本身而不是程序设计, 我们 采用 MATLAB遗传算法工具箱来提高编程效率. 本文采用英国设菲尔德大学开发的遗传算法工具 箱. 下面仅对本次程序设计所用到的函数作介绍: ( 1) 函数 rep. rep是一个低级复 制函数, 通 常不直接使用, 它可被 GA 工具箱中许多函数调 用. ( 2) 函数 crtbp. 创建 初始种群. 遗传算法的 第 1步是 创建由任 意染色体 组成的原 始种群. crtbp创建一元素为随机数的矩阵 Chrom. ( 3) 函数 bs2rv. 二进制串到实值的转换函数.
