论文部分内容阅读
[摘 要]针对多目标蚁群遗传算法（MOAGA）解集边界分布不均的问题，提出改进算法，解决连续空间中带约束条件多目标优化问题。改进算法在基本MOAGA算法的基础上，在选择中引入一定比例的边界决策、单目标最优决策，并提高边界决策的交叉率。实验证明，改进算法解决了基本算法解集分布边界疏中间密的问题，并且能更快的获得散布性较好的Pareto最优解集。
[关键词]约束多目标优化问题 改进蚁群遗传算法 散布性 Pareto前沿
中图分类号：TP3 文献标识码：A 文章编号：1671－7597(2008)0510053－02
一、引言
约束多目标优化问题在社会经济、管理、军事和人文等领域应用的非常广泛。不失一般性，以最小化问题为例，约束多目标优化问题(Constrained Mutli-Objective Optimization Problem， CMOP)可定义如下:
其中为目标函数， ，称为约束条件，
称为维决策向量。将满足所有约束条件的解空间称为(1)的可行域。对于等式约束可通过容许误差（也称容忍度）将它转化为两个不等式约束：
故在以后讨论问题时，仅考虑带不等式约束的优化问题。在搜索空间中，满足约束条件的决策变量称为可行解，否则称为不可行解。
就目前来说，在智能算法中，虽然蚁群算法具有并行性、正反馈机制以及求解效率高等特性，但其全局搜索能力较差，容易陷入局部解[1]。而遗传算法虽具有快速性、随机性、全局收敛性等优点，但其收敛速率还得不到非常有效的保证，有时会出现收敛停滞现象[2]。考虑到蚁群算法和遗传算法的特性，有学者考虑研究蚁群算法与遗传算法的融合[3]（GAAA），但该算法只是简单地先后运用两种算法进行求解，并不是实质的融合，尽管在一定程度上提高了求解的精度，但算法效率降低了。多目标蚁群遗传算法（MOAGA）很好的解决了这一问题，但由于该算法采用线性交叉算子，解集的分布是中间密，边界部分比较稀疏。因此为了解决解分布的均匀散布性，本文提出基于MOAGA的改进算法，在选择过程中，按一定比例加入边界决策（特别是边界最优决策），同时使得部分单目标最优决策直接成为父代；在交叉过程中，提高边界决策的繁殖能力。这样，更快地获得了散布性较好的解集。
二、改进的多目标蚁群遗传算法
（一）信息素操作
首先将决策空间均匀分解为若干子空间（ ），对每个子空间（ ）为该子空间在第维上的顺序号，
为该子空间编号），随机生成一个决策 ，形成初始决策集
，即第一代决策集，然后对 进行约束条件处理，得到第一代初始可行决策集。
则第代编号为 的子空间上第个目标函数对应的信息量
（二）优秀决策集更新
第代进化结束得到第代初始决策集 ，根据一个定义的相似度对 去掉相似决策（以提高决策的散布范围），并用约束条件处理后得到第代可行决策集 。接着对进行Pareto分级，取的第1级Pareto决策集与优秀决策集（对于第一代，令）取并，得到决策集，再对又一次进行Pareto分级，则的第1级Pareto决策集即更新后的。
（三）遗传操作
1.选择
父代的主要来源：考虑到个目标函数的量纲可能不一致，从而导致各目标函数对应的信息量量纲也不一致，因此必须对各量纲进行归一化处理，然后根据归一化的信息量来求出各决策的概率。根据这个思想，设第
代可行决策集的决策数为，则中第个决策
被选中的概率为：
计算出 的概率后，扰乱 的顺序，然后依照轮盘赌的方式，选取决策， 组成第代的初始父决策集，
其中 小于父代规模。
父代的其它来源：对实数问题的约束多目标优化来说，最好的交叉算子是线性交叉算子，该算子通过产生0到1之间的均匀随机数实现线性运算交叉过程，相当于在两点之间按照均匀分布产生随机点，这样尽管在每一次具体的交叉中是随机均匀的，但是在一个内部有很多端点的空间来说，经过数次交叉后，不可避免的是交叉结果分布趋近于空间中心，在一定程度上影响了最优解集的均匀散布性，使得在整个求解空间上，解集的分布是中间较密，靠近边界的部分比较稀疏。为了保证决策的多样性及不缩小散布范围，按一定的规则和比例把以下几种决策直接作为父代参与遗传交叉：部分边界决策、少量 中的Pareto优秀决策、少量单目标最优决策、少量优秀决策集中的决策，且以上决策总个数不能超过父代决策集总数的20%（经验值，一般建议5%－15%），否则将会很快收敛于局部。同时若从中随机选取了某个优秀决策，判断其复制次数是否超过复制次数充许值，若未超过，把该决策加入，且其对应复制次数加1，否则跳过从中继续寻找下一个优秀决策，且寻找次数不能超过寻找次数的充许值。
通过以上两部分的选择，得到第代的父决策集 。
2.交叉
主体交叉：一般来说，大量的约束多目标优化问题都是基于实数空间的，因此本文采用线性交叉交叉算子。过程如下：
Step1：随机选择两个父代个体
Step2：产生一个0－1之间的随机数，如果大于交叉概率，则转Step1；
Step3：执行线性交叉。产生两个0－1之间的随机数和，设交叉后生成两个子个体，分别为，。
其中 ， 。
边界强制性交叉：根据前面分析，由于实数线性交叉的特点，在数次交叉后，不可避免后代不断趋近于空间的中心，从而形成空间中心较密、边界稀疏甚至没有的情况。虽然前面进行父代选择时进行了一定的处理，但是为了保证解集的散布性，在主体交叉完毕后，还有必要进行边界强制性交叉。边界强制性交叉就是在两个父代个体中，随机确定其中一个为边界决策，另一个在其余决策中随机选择。
3.变异
变异操作是产生新个体的辅助方法，同时也决定了蚁群遗传算法的局部搜索能力。每个个体的每个变量都有均等的变异机会，先选定一个个体的一个变量，然后产生一个随机数，如果该数大于变异概率，则不执行变异操作；否则在该个体相应变量的定义域范围进行变异操作。本文选择的变异方法是决策突变，即若某决策被选定执行变异，则在其定义域范围内进行突变。
三、收敛性验证
（一）间距评估
间距评估是由Shott于1995年提出的[4]，通过计算相邻解之间的相对距离，来对解的多样性进行评估。若设Pareto最优决策的个数为，则分布性能可用最近解欧氏距离的标准差来表示：
的最短距离。为最短距离的期望，即。从的表达式可以看出，值越小表示分布越均匀。
（二）最大散布范围
这种评价方式是由Zitzle and Kalyanmony Deb于1999年提出的[5]，用来计算解集中的所有极值解构成的多面体的周长，具体定义如下：
的值越大表示解的散布范围越广。
（三）收敛速度
这里我们用一级Pareto最优决策集的改变百分比序列来反应收敛速度：
。 （9）
其中为本次迭代的一级Pareto最优决策最优集，为上次迭代的一级Pareto最优决策最优集，为近似减法（表示把集合中与 相同或相似的决策去掉）。从表达是可以看出，若随着迭代的进行， 序列迅速稳定趋向于0（实际是一个很小的数），则表示算法收敛较快。
（四）数值实验
为说明MOAGA在解决连续空间中带约束多目标优化问题的优越性，本文以两变量约束问题TNK为例来测试算法的性能[6]。TNK问题：
TNK问题的求解难度在于它的Pareto前沿是由多段不连通的Pareto曲线构成，且其曲线是非凸的。MOAGA算法需要167步得到154个最优解，而改进算法则只需要84次迭代收敛得到168个最优解。算法性能如表3.1所示，从表3.1可知，改进算法迭代全局收敛更快，更够求出更多的一级Pareto最优解，且解的散布性能更好。
表3.1两种算法在间距及最大散布范围上的比较
四、结束语
本文提出了一种基于蚁群算法和遗传算法的改进多目标蚁群遗传算法，用来求解约束多目标优化问题。本算法先将解空间分解成子区域，再用信息素标定这些子区域，并将信息量指导遗传搜索、优秀决策引入、边界决策引入、单目标最优决策引入、便捷决策强制交叉、决策集更新、改变算法终止条件等方式相结合，从而提高求解效率，降低算法复杂度。实验证明，改进算法解决了解集分布边界疏的问题，并且能更快更好地获得散布性较好的Pareto最优解集。
参考文献：
[1]T.Stutzle， M.Dorigo. A Short Convergence Proof for a class of Ant Colony Optimization Algorithm. IEEE Transaction on Evolutionary Computation.2002， 6(4):358~365.
[2]B.Roy. Problems and Methods with Multiple Objective function. Mathematical Programming.1971，1(2):239~201.
[3]S.Christine. Ants Can Solve Constrain Satisfaction Problem. IEEE Transactions on Evolutionary Computation.2002，6(4):347-357.
[4]Deb K. Multi-objective Optimization Using Evolutionary Algorithms， New York: JohnWiley&sons，2001.
[5]Van Veldhuizen D.A.，Lamont GB. On Measuring Multiobjective Evolutionary Algorithm Performance. In Proceeding sof the 2000 Congress on Evolutionary Computation. 2000: 204- 211.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
[关键词]约束多目标优化问题 改进蚁群遗传算法 散布性 Pareto前沿
中图分类号：TP3 文献标识码：A 文章编号：1671－7597(2008)0510053－02
一、引言
约束多目标优化问题在社会经济、管理、军事和人文等领域应用的非常广泛。不失一般性，以最小化问题为例，约束多目标优化问题(Constrained Mutli-Objective Optimization Problem， CMOP)可定义如下:
其中为目标函数， ，称为约束条件，
称为维决策向量。将满足所有约束条件的解空间称为(1)的可行域。对于等式约束可通过容许误差（也称容忍度）将它转化为两个不等式约束：
故在以后讨论问题时，仅考虑带不等式约束的优化问题。在搜索空间中，满足约束条件的决策变量称为可行解，否则称为不可行解。
就目前来说，在智能算法中，虽然蚁群算法具有并行性、正反馈机制以及求解效率高等特性，但其全局搜索能力较差，容易陷入局部解[1]。而遗传算法虽具有快速性、随机性、全局收敛性等优点，但其收敛速率还得不到非常有效的保证，有时会出现收敛停滞现象[2]。考虑到蚁群算法和遗传算法的特性，有学者考虑研究蚁群算法与遗传算法的融合[3]（GAAA），但该算法只是简单地先后运用两种算法进行求解，并不是实质的融合，尽管在一定程度上提高了求解的精度，但算法效率降低了。多目标蚁群遗传算法（MOAGA）很好的解决了这一问题，但由于该算法采用线性交叉算子，解集的分布是中间密，边界部分比较稀疏。因此为了解决解分布的均匀散布性，本文提出基于MOAGA的改进算法，在选择过程中，按一定比例加入边界决策（特别是边界最优决策），同时使得部分单目标最优决策直接成为父代；在交叉过程中，提高边界决策的繁殖能力。这样，更快地获得了散布性较好的解集。
二、改进的多目标蚁群遗传算法
（一）信息素操作
首先将决策空间均匀分解为若干子空间（ ），对每个子空间（ ）为该子空间在第维上的顺序号，
为该子空间编号），随机生成一个决策 ，形成初始决策集
，即第一代决策集，然后对 进行约束条件处理，得到第一代初始可行决策集。
则第代编号为 的子空间上第个目标函数对应的信息量
（二）优秀决策集更新
第代进化结束得到第代初始决策集 ，根据一个定义的相似度对 去掉相似决策（以提高决策的散布范围），并用约束条件处理后得到第代可行决策集 。接着对进行Pareto分级，取的第1级Pareto决策集与优秀决策集（对于第一代，令）取并，得到决策集，再对又一次进行Pareto分级，则的第1级Pareto决策集即更新后的。
（三）遗传操作
1.选择
父代的主要来源：考虑到个目标函数的量纲可能不一致，从而导致各目标函数对应的信息量量纲也不一致，因此必须对各量纲进行归一化处理，然后根据归一化的信息量来求出各决策的概率。根据这个思想，设第
代可行决策集的决策数为，则中第个决策
被选中的概率为：
计算出 的概率后，扰乱 的顺序，然后依照轮盘赌的方式，选取决策， 组成第代的初始父决策集，
其中 小于父代规模。
父代的其它来源：对实数问题的约束多目标优化来说，最好的交叉算子是线性交叉算子，该算子通过产生0到1之间的均匀随机数实现线性运算交叉过程，相当于在两点之间按照均匀分布产生随机点，这样尽管在每一次具体的交叉中是随机均匀的，但是在一个内部有很多端点的空间来说，经过数次交叉后，不可避免的是交叉结果分布趋近于空间中心，在一定程度上影响了最优解集的均匀散布性，使得在整个求解空间上，解集的分布是中间较密，靠近边界的部分比较稀疏。为了保证决策的多样性及不缩小散布范围，按一定的规则和比例把以下几种决策直接作为父代参与遗传交叉：部分边界决策、少量 中的Pareto优秀决策、少量单目标最优决策、少量优秀决策集中的决策，且以上决策总个数不能超过父代决策集总数的20%（经验值，一般建议5%－15%），否则将会很快收敛于局部。同时若从中随机选取了某个优秀决策，判断其复制次数是否超过复制次数充许值，若未超过，把该决策加入，且其对应复制次数加1，否则跳过从中继续寻找下一个优秀决策，且寻找次数不能超过寻找次数的充许值。
通过以上两部分的选择，得到第代的父决策集 。
2.交叉
主体交叉：一般来说，大量的约束多目标优化问题都是基于实数空间的，因此本文采用线性交叉交叉算子。过程如下：
Step1：随机选择两个父代个体
Step2：产生一个0－1之间的随机数，如果大于交叉概率，则转Step1；
Step3：执行线性交叉。产生两个0－1之间的随机数和，设交叉后生成两个子个体，分别为，。
其中 ， 。
边界强制性交叉：根据前面分析，由于实数线性交叉的特点，在数次交叉后，不可避免后代不断趋近于空间的中心，从而形成空间中心较密、边界稀疏甚至没有的情况。虽然前面进行父代选择时进行了一定的处理，但是为了保证解集的散布性，在主体交叉完毕后，还有必要进行边界强制性交叉。边界强制性交叉就是在两个父代个体中，随机确定其中一个为边界决策，另一个在其余决策中随机选择。
3.变异
变异操作是产生新个体的辅助方法，同时也决定了蚁群遗传算法的局部搜索能力。每个个体的每个变量都有均等的变异机会，先选定一个个体的一个变量，然后产生一个随机数，如果该数大于变异概率，则不执行变异操作；否则在该个体相应变量的定义域范围进行变异操作。本文选择的变异方法是决策突变，即若某决策被选定执行变异，则在其定义域范围内进行突变。
三、收敛性验证
（一）间距评估
间距评估是由Shott于1995年提出的[4]，通过计算相邻解之间的相对距离，来对解的多样性进行评估。若设Pareto最优决策的个数为，则分布性能可用最近解欧氏距离的标准差来表示：
的最短距离。为最短距离的期望，即。从的表达式可以看出，值越小表示分布越均匀。
（二）最大散布范围
这种评价方式是由Zitzle and Kalyanmony Deb于1999年提出的[5]，用来计算解集中的所有极值解构成的多面体的周长，具体定义如下：
的值越大表示解的散布范围越广。
（三）收敛速度
这里我们用一级Pareto最优决策集的改变百分比序列来反应收敛速度：
。 （9）
其中为本次迭代的一级Pareto最优决策最优集，为上次迭代的一级Pareto最优决策最优集，为近似减法（表示把集合中与 相同或相似的决策去掉）。从表达是可以看出，若随着迭代的进行， 序列迅速稳定趋向于0（实际是一个很小的数），则表示算法收敛较快。
（四）数值实验
为说明MOAGA在解决连续空间中带约束多目标优化问题的优越性，本文以两变量约束问题TNK为例来测试算法的性能[6]。TNK问题：
TNK问题的求解难度在于它的Pareto前沿是由多段不连通的Pareto曲线构成，且其曲线是非凸的。MOAGA算法需要167步得到154个最优解，而改进算法则只需要84次迭代收敛得到168个最优解。算法性能如表3.1所示，从表3.1可知，改进算法迭代全局收敛更快，更够求出更多的一级Pareto最优解，且解的散布性能更好。
表3.1两种算法在间距及最大散布范围上的比较
四、结束语
本文提出了一种基于蚁群算法和遗传算法的改进多目标蚁群遗传算法，用来求解约束多目标优化问题。本算法先将解空间分解成子区域，再用信息素标定这些子区域，并将信息量指导遗传搜索、优秀决策引入、边界决策引入、单目标最优决策引入、便捷决策强制交叉、决策集更新、改变算法终止条件等方式相结合，从而提高求解效率，降低算法复杂度。实验证明，改进算法解决了解集分布边界疏的问题，并且能更快更好地获得散布性较好的Pareto最优解集。
参考文献：
[1]T.Stutzle， M.Dorigo. A Short Convergence Proof for a class of Ant Colony Optimization Algorithm. IEEE Transaction on Evolutionary Computation.2002， 6(4):358~365.
[2]B.Roy. Problems and Methods with Multiple Objective function. Mathematical Programming.1971，1(2):239~201.
[3]S.Christine. Ants Can Solve Constrain Satisfaction Problem. IEEE Transactions on Evolutionary Computation.2002，6(4):347-357.
[4]Deb K. Multi-objective Optimization Using Evolutionary Algorithms， New York: JohnWiley&sons，2001.
[5]Van Veldhuizen D.A.，Lamont GB. On Measuring Multiobjective Evolutionary Algorithm Performance. In Proceeding sof the 2000 Congress on Evolutionary Computation. 2000: 204- 211.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”