多目标优化的蚁群遗传算法.doc

多目标优化的蚁群遗传算法 伍爱华，李智勇 （湖南大学 计算机与通信学院，湖南 长沙 410082） 摘要Pareto最优决策。 关键词多目标蚁群遗传算法1　引言 GA具有快速性、随机性、全局收敛性等优点，但是运行到一定程度后，由于没有有效利用系统中的反馈信息而作大量无谓的冗余迭代，所以其实用性差、解的精度不高、算法复杂度高、不能保证求得最优解[4]。而ACA具有并行性、正反馈机制以及求解效率高等特性，但其全局搜索能力较差，容易陷入局部解[5,6]。 遗传算法与蚂蚁算法的融合[7]（GAAA）是当前一种较新的思路，它基于遗传算法的快速全局搜索能力和蚂蚁算法的正反馈收敛机制，初期采用遗传算法过程生成信息素分布，后期利用蚂蚁算法正反馈求精确解，力求优势互补。但实质上GAAA只是先后运用简单地了两种算法，并不是实质的融合，尽管在一定程度上提高了求解的精度，但是算法效率降低了。 针对GAAA的不足，近年来，又有些学者提出了基于信息量留存的蚁群遗传算法[8]和蚁群遗传混合算法[9]，在单目标优化中取得了较为明显的效果。本文基于GA和ACA的特性提出多目标蚁群遗传算法（MOAGA），用于解决连续空间多目标优化问题，在遗传搜索中引入ACA的信息反馈更新机制，信息素指导遗传搜索，而遗传搜索结果引导信息素的更新，力求将两种算法优势互补，达到二者的始终融合，同时在算法中引入了决策集，期望在提高求决策精度、扩大决策范围的同时降低算法复杂度。 2　多目标优化问题 其中：为决策向量，为多目标优化函数向量，（表示）为约束条件，为边界条件，且，，决策分量满足。在多目标优化问题中，各个目标通常是相互制约的关系，对其中一个目标进行优化往往以其他目标的性能降低为代价，且其最优决策不是唯一的，而是存在一组Pareto最优决策。 3　MOAGA算法MOGA和ACA的MOAGA算法，其基本思想是汲取两种算法的优点，克服各自的缺陷，优势互补，其基本思路是算法主体过程采用MOGA，充分利用MOGA的快速性、随机性、全局收敛性，一方面ACA中信息素指导MOGA的遗传选择，另一方面MOGA的结果引起信息素的更新，并用于指导下一次遗传选择，充分利用了ACA的并行性、正反馈机制以及求解效率高等特性。使二者优势互补，从而达到提高解的精度、求解效率。在具体的运算过程中，引入决策集的概念，并随机抽取部分优秀决策参与遗传选择，维持了决策的多样性，扩大了决策的分布范围。 3.1 输入参数及初始化 输入参数： 定义域分解规模，信息量调节系数，决策集的规模和决策复制次数上限，将选取的优秀决策个数，子区域信息量的相对重要程度，决策目标函数的相对重要程度，信息挥发系数，最大迭代次数，终止时连续迭代次数。 初始化：将决策向量空间均匀分解为个子空间（）。然后在每个子空间中随机产生一个决策形成第1代----初始决策。 对初始决策用约束条件判断，剔除非可行决策得可行决策集。 若存在可行决策，该子空间初始信息量为： ， 当时； ， 当时。 若不存在可行决策，则： 且，其中正常数，，为信息量强度权重调节系数。 3.2 决策集更新 第代进化并剔除非可行决策结束后，把新旧决策进行合并，去掉重复决策得到第代可行决策集，决策个数为（有）。在计算出中各决策的个目标函数值之后, 用递归方法对进行Pareto分级产生与规模一样的第代决策集。起初中决策数为， 。具体为： Step1: 根据Pareto最优定义得的Pareto最优决策集（设有个决策）； Step2: 若，将并入，并令，，转Step1； Step3: 若，则将按严格不等式成立个数降序排列，选出前个决策并入，此即为第代决策集。 再将与进行比较，剔除中的较劣决策，并将较优决策包含进来，完成更新操作。 3.3 遗传选择 第代可行决策集（）被选中的概率为： ， 其中表示第个决策所处的子空间坐标。然后依照轮盘赌的方式，选取决策组成第代可行决策集，同时从中随机选取个决策（此即优秀决策），其对应复制次数加1，剔除重复和复制次数超过限制的决策后继续从中随机选取优秀决策，直到规模为，此即下一次交叉操作可行父决策。这样使得与其它决策集实时交换，能加快决策的收敛。 3.4 信息素更新 各子空间的信息量更新过程如下：由前面我们确定了第代中各子空间的信息量，因此有第代子空间上的第个目标函数信息量为： ， 其中为第代子空间上加入的第个目标函数信息量。不妨设在子空间上，第代的Pareto最优决策集为。 若，则 ， 当时； ， 当时。 若，则；其中。 3.5 算法步骤 MOAGA首先将决策空间均匀地分解为若干个子空间，分别从每个子空间中随机产生一个决策，去掉非可行决策后形成初始可行决策集，依据各子空间中决策的目标函数值用信息素标定空间，并对初始可行