一种约束多目标优化问题的改进蚁群遗传算法

1、本栏目责任编辑 :贾薇薇 计算机工程应用技术 Knowledge And Technology 电脑知识与技术 2008年第 4卷第 9期 (总第 36期 一种约束多目标优化问题的改进蚁群遗传算法伍爱华(长沙民政职业技术学院 , 湖南 长沙 410004摘要 :该文针对多目标蚁群遗传算法 (MOAGA 解集边界分布不均的问题 , 提出改进算法 , 解决了连续空间中带约束条件多目标优 化问题 。 改进算法在基本 MOAGA 算法的基础上 , 在选择中引入一定比例的边界决策 、 单目标最优决策 , 并提高边界决策的交叉率 。 实验证明 , 改进算法解决了基本算法解集分布边界疏中间密的问题 , 并且

2、能更快的获得散布性较好的 Pareto 最优解集 。关键词 :约束多目标优化问题 , 改进蚁群遗传算法 , 散布性 , Pareto 前沿中图分类号 :TP18文献标识码 :A 文章编号 :1009-3044(200836-2830-03An Improved Multi-Objective Ant-Genetic Algorithm In Constrained ProblemWU Ai-hua(ChangshaSocial Work College,Changsha 410004,ChinaAbstract:An improved Multi-Objective Ant-Genetic A

3、lgorithm is presented in this paper, it can be used to solve Constrained Multi-Objective Optimization Problem on continuous space. Go farther than the basic MOAGA, we introduce some scale of boundary-decision and single-objective excellent-decision in choosing, and enhance ratio of intercrossing of

4、boundary-decision. In the end, an example was listed to prove that the improved algorithm can solve the problem of the solution-set distributing uneven on the boundary in basic one, and can obtain the Pareto optimality set faster and better.Key words:Constrained Multi-Objective Optimization Problem;

5、 Improved Multi-Objective Ant-Genetic Algorithms; diffusion perfor -mance; Pareto front1引言在实际问题中 , 许多控制和决策问题需同时考虑多个目标优化 , 即约束多目标优化问题 。 不失一般性 , 以最小化问题为例 , 约束 多目标优化问题可定义如下 :(1但对多目标优化问题的求解至今还是一个难点 , 通常很难求出其最优解 , 只能求出 Pareto 解 。 近年来 , 出现了一系列用来解决 此问题的算法 , 如遗传算法 (GA、 粒子群优化 (PSO 、 蚁群算法 (ACA 等 , 这些算法虽然在过程控制

6、 、 工程优化等方面取得了成功 , 但 在求解多目标函数优化问题时存在一些困难 。 就目前来说 , 由于蚁群算法具有并行性 、 正反馈机制以及求解效率高等特性 , 但其全 局搜索能力较差 , 容易陷入局部解 1。 而遗传算法尽管具有快速性 、 随机性 、 全局收敛性等优点 , 但是运行到一定程度后 , 由于没有有 效利用系统中的反馈信息而作大量无谓的冗余迭代 , 另外该算法对所选参数比较敏感 , 其收敛速率还得不到非常有效的保证 , 有时 会出现收敛停滞现象 2。 考虑到蚁群算法和遗传算法的特性 , 因此有学者考虑研究蚁群算法与遗传算法的融合 3(GAAA , 但该算法 只是简单地先后运用两种

7、算法进行求解 , 并不是实质的融合 , 尽管在一定程度上提高了求解的精度 , 但是算法效率降低了 。 多目标 蚁群遗传算法 (MOAGA 很好的解决了这一问题 , 但是由于该算法采用是线性交叉算子 , 解集的分布是中间密 , 靠近边界的部分比 较稀疏 。 因此为了解决解分布的均匀散布性 , 本文提出基于 MOAGA 的改进算法 , 在选择过程中时 , 按一定比例加入边界决策 (特别 是边界最优决策 , 同时使得部分单目标最优决策直接成为父代 ; 在交叉过程中 , 提高边界决策的繁殖能力 。 这样 , 就能更快地获得 散布性较好的解集 。2改进的多目标蚁群遗传算法2.1信息素操作首先将决策向量空

8、间均匀分解为 M=M1×M 2× ×M n 个子空间 E j 1j 2 j i (j i =1,2, ,M i 。 然后在每个子空间中随机产生一个决策形成 第 1代 初始决策集 A(1* 。 对初始决策用约束条件判断 , 剔除非可行决策得可行决策集 A(1。则第 k 代编号为 j 1j 2 j n 的子空间上第 i 个目标函数对应的信息量 Ph i,j 1j 2 j i(k为 :(2其中 Ph i,j 1j 2 j i (k=0, 且 Ph' i,j 1j 2 j i(k为第 k 代子空间 j 1j 2 j n 上由于新决策引入所产生的信息量增量 , 为挥

9、发系数 。具体计算过程为 :不妨设在子空间 j 1j 2 j n 上 , 第 k 代的 Pareto 最优决策集为 Pp1,p 2, ,p k 。 收稿日期 :2008-10-22作者简介 :伍爱华 (1972-, 女 , 湖南邵阳人 , 长沙民政职业技术学院电子系讲师 , 主要研究方向为智能计算理论及其应用 。计算机工程应用技术 本栏目责任编辑 :贾薇薇 若 P ,则 若 P=, 则 Ph i,j 1j 2 j i(k=0; 其中 i=1,2, ,m 。 2.2优秀决策集更新第 代进化结束得到第 代初始决策集 A(k* , 根据一个定义的相似度对 A(k* 去掉相似决策 (以提高决策的散布范

10、围 , 并用约束 条件处理后得到第 代可行决策集 A(k。 接着对 A(k进行 Pareto 分级 , 取 A(k* 的第 1级 Pareto 决策集与优秀决策集 D (对于第一 代 , 令 D= 取并 , 得到决策集 B , 再对 B 又一次进行 Pareto 分级 , 则 B 的第 1级 Pareto 决策集即更新后的 D 。2.3遗传操作选择 :为了保证决策的多样性及不缩小散布范围 , 把以下几种决策直接作为父代参与遗传交叉 :部分边界决策 、 少量父代决策中 的 Pareto 优秀决策 、 少量单目标最优决策 、 少量优秀决策集 D 中的决策 。 注意 :以上决策总个数不能超过父代决策

11、的 20%(经验值 , 一 般建议 5%15%, 否则将会很快收敛于局部最优 。 接着按概率进行选择 , 第 代可行决策集 A j (k* (j=1,2, ,kM 被选中的概率为: (5其中 j' 表示第 j 个决策所处的子空间坐标 。 然后依照轮盘赌的方式 , 选取决策直到 A(k规模为 M , 得到第 k 代可行决策集 A(k。 1 交叉一般来说 , 大量的约束多目标优化问题都是基于实数空间的 , 因此本文采用线性交叉算子 。 由于实数线性交叉的特点 , 在数次 交叉后 , 不可避免后代不断趋近于空间的中心 , 从而形成空间中心较密 、 边界稀疏甚至没有的情况 。 前面进行父代选择

12、时进行了一 定的处理 , 但是为了保证解集的散布性 , 在主体交叉完毕后进行边界强制性交叉 。 边界强制性交叉的特点是 , 在两个父代个体中 , 随 机确定其中一个为边界决策 , 另一个在其余决策中随机选择 。2 变异变异操作是产生新个体的辅助方法 , 同时也决定了蚁群遗传算法的局部搜索能力 。 每个个体的每个变量都有均等的变异机会 , 先选定一个个体的一个变量 , 然后产生一个随机数 , 如果该数大于变异概率 , 则不执行变异操作 ; 否则在该个体相应变量的定义域 范围进行变异操作 。 本文选择的变异方法是决策突变 , 即若某决策被选定执行变异 , 则在其定义域范围内进行突变 。3收敛性验证

13、3.1间距评估间距评估是由 Shott 于 1995年提出的 4, 通过计算相邻解之间的相对距离 , 来对解的多样性进行评估 。 若设 Pareto 最优决策的 个数为 , 则分布性能可用最近解欧氏距离的标准差来表示:(6 其中 d i =minj (m k =1|fk (Ai -f k (Aj (i,j=1,2, ,N 为决策 i 到所有决策的最短距离 。 为最短距离的期望 , 即 1N i =1d i 。 从 s 的表达式可以看出 , s 值越小表示分布越均匀 。3.2最大散布范围这种评价方式是由 Zitzle and Kalyanmony Deb 于 1999年提出的 5, 用来计算解集

14、中的所有极值解构成的多面体的周长 , 具体定 义如下:(7 的值越大表示解的散布范围越广 。3.3收敛速度这里我们用一级 Pareto 最优决策集的改变百分比序列来反应收敛速度:(8 其中 X 为本次迭代的一级 Pareto 最优决策最优集 , X' 为上次迭代的一级 Pareto 最优决策最优集 ,“ -軌 ” 为近似减法 (表示把集合 X 中与 X' 相同或相似的决策去掉 。 从表达是可以看出 , 若随着迭代的进行 , M i 序列迅速稳定趋向于 0(实际是一个很小的数 , 则表 示算法收敛较快 。3.4数值实验为说明 MOAGA 在解决连续空间中带约束多目标优化问题的优越

15、性 , 本文以两变量约束问题 BNH 问题为例来测试算法的性能 。 (3(4伍爱华 :一种约束多目标优化问题的改进蚁群遗传算法 2831本栏目责任编辑 :贾薇薇 计算机工程应用技术 Computer Knowledge And Technology 电脑知识 与技术 2008年第 4卷第 9期 (总第 36期 (上接第 2827页 坑到平地的这类下降和上升边缘存储为 0。 依据数据的写入方式大致来讲分三类 , 一类是直接压制的 , 如 CD 唱片 , 先灌录好一张高 质量的母盘而后交由制作部门 , 制作相应的模板 , 而后对 CD 盘面进行压制即可得到与母盘一样的信息 。 第二类是 CD-R

16、, 即 CD-Recordable , 一次性写入 CD , 这类事在盘面上有一层可记录数据的数据染料层 , 通过激光对这层打 ” 坑 ” 也就存储了 0或 1。 第三类是 CD-RW , 可多次写 CD 。 主要原理是选用可逆的染料材质作为数据层 , 利用材料的特性来完成数据的多次读写 。 读取是通过激光的 打到盘道的不同的位置的不同反射情况来获取 0或 1。2.6其他各类新存储介质IBM 在 2007年推出了单原子存储技术 , 也是利用了原子内部的磁性原理 , 并且在实验室成功的在一个原子上存储比特的信 息 , 而当今即使是最高密度的硬盘 , 存储一个信息至少需要 100万个磁性原子 。

17、效率的提高可想而知 。3结论到此 , 文章开头的问题似乎已不重要了 , 了解几类主要介质及其原理应该更为重要 。 存储介质的发展史也是计算机的发展史 , 每次存储介质的改进 , 计算机及其相关设备的改进也就随之产生 , 这对我们的生活起到了很大的推动作用 。可以预见的是 , 随着材料科学等学科的不断发展 , 新的存储技术也可能将随之而来 , 我们期待人类无穷的智慧 。参考文献 :1曹岳辉 , 李力 , 李梦晖编著 . 计算机硬件技术基础 M.北京 :清华大学出版社 ,2006.31-32.2美 施敏著 , 赵鹤鸣 , 钱敏等译 . 半导体器件与工艺 M.(第 2版 . 苏州 :苏州大学出版社

18、,2002.2-7.3蒋本珊 编著 . 计算机组成原理 M.北京 :清华大学出版社 ,2004.228-229,245-250.BNH问题(9BNH 问题是一个两变量约束问题 , 它的 Pareto 前沿是连通的 , 便于求解 。 由下表可以看出 , 改进算法比 MOAGA 算法搜索到的 解的数量更多 , 分布也更加均匀 , 而且解散布的范围更广 。表 1三种算法在间距及最大散布范围上的比较4结束语本文提出了一种基于蚁群算法和遗传算法的改进多目标蚁群遗传算法 6, 用来求解约束多目标优化问题 。 本算法先将解空间分 解成子区域 , 信息素对遗传搜索进行指导 , 在搜索中更新信息素 , 同时采用了最优决策集的更新策略和搜索收敛退出机制 , 从而提 高求解效率 , 降低算法复杂度 。 实验证明 , 与以往算法相比 , 此算法解决了解集分布边界疏的问题 , 并且能更快更精确地逼近 Pareto 前沿 。参考文献 :1T.Stutzle, M.Dorigo. A Short Convergence Proof for a class of Ant Colony Optimization Algorithm.