改进的蛙跳算法在多目标优化问题中的应用
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
改进的蛙跳算法在多目标优化问题中的应用
王晓笛１，肖伟１，何灿２
ＷＡＮＧＸｉａｏｄｉｌ．ＸＩＡ０Ｗｄｌ．ＨＥＣａｎ２
１．湖南师范大学，长沙４１００８１
２．湖南星辰在线网络传播有限公司，长沙４１００ｔ６
１．ＨｕｎａｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１００８１．Ｃｈｉｎａ
２．ＨｕｎａｎＣＳＯＮＬＩＮＥＩｎｔｅｒｎｅｔＴｒａｎｓｍｉｓｓｉｏｎＣｏ．，Ｌｔｄ，Ｃｈａｎｇｓｈａ４１００１６，Ｃｈｉｎａ
ＷＡＮＧＸｉａｏｄｉ，ＸＩＡＯ、ｖｅｉ，ＨＥＣａｎ．ＡｐｐｌｉｃａｔｉｏｎｏｆｉｍｐｒｏｖｅｄＳｈｕｆｆｌｅＦｒｏｇＬｅａｐｉｎｇＡｌｇｏｒｉｔｈｍｔｏｒｅｓｏｌｖｅｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２０１２，４８（３０）：２３３—２３８．
、
Ａｂｓｔｒａｃｔ：ＴｈｉｓｐａｐｅｒｄｒａｗｓｇｅｎｅｔｉｃｏｐｅｒａｔｏｒｓｏｆＧＡａｎｄｉｍｐｒｏｖｅｓｔｈｅｍｅｔｈｏｄｏｆＳＦＬＡｇｒｏｕｐｄｉｖｉｄｉｎｇｂａｓｅｄｏｎｉｎ—
ｔｒｏｄｕｃｉｎｇＳＦＬＡ，ｐｕｔｓｆｏｒｗａｒｄａｎｉｍｐｒｏｖｅｄＳＦＬＡｔｏｒｅｓｏｌｖｅｐｒｏｂｌｅｍｏｆｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎ．Ｔｈｅｉｍｐｒｏｖｅｄｍｅｔｈｏｄｔａｋｅｓｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅＯ—ｌｋｎａｐｓａｃｋａＳａｎｅｘａｍｐｌｅｆｏｒｓｉｍｕｌａｔｅｄｅｘｐｅｒｉｍｅｎｔ，ｗｈｉｃｈｂｅａｒｓＯＵｔｔｈａｔ．ｃｏｍｐａｒｅｄｗｉｔｈｏｒｉｇｉｎａｌＳＦＬＡ，ｔｈｅｉｍｐｒｏｖｅｄＳＦＬＡｈａｓｂｅＲｅｒｐｅｒｆｏｒｍａｎｃｅｏｎｒｅｓｏｌｖｉｎｇｉｍｐｒｏｖｅｄＳＦＬＡｐｒｏｂｌｅｍ．
Ｋｅｙｗｏｒｄｓ：ＳｈｕｆｆｌｅＦｒｏｇＬｅａｐｉｎｇＡｌｇｏｒｉｔｈｍ（ＳＦＬＡ）；ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎ；ｇｅｎｅｔｉｃｏｐｅｒａｔｏｒｓ；ｇｒｏｕｐｉｎｇｍｅｔｈｏｄ；ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ０－１ｋｎａｐｓａｃｋｐｒｏｂｌｅｍ
摘要：在介绍原始混洗蛙跳算ｊ去的基础上，引入遗传算法中的遗传算子，改进原始蛙跳算法的分组方法，提出一种改进的混洗蛙跳算法用于求解多目标优化问题。改进的算法以多目标。一１背包问题为例进行模拟实验，其实验结果表示，与原始的混洗蛙跳算法相比较，改进的蛙跳算法在求解多目标优化问题上具有更好的性能。关键词：混洗蛙跳算法；多目标优化问题；遗传算子；分组方法：多目标０—１背包问题
文章编号：１００２—８３３ｌ（２０１２）３０—０２３３．０６文献标识码：Ａ中图分类号：ＴＰ３９１
ｌ弓Ｉ言
群体智能优化算法是一种基于群体智能的进化算法，源于对自然界生物进化过程或觅食行为的模拟。这种算法不需要问题的梯度信息，具有较强的鲁棒性，并且每个个体遵循的规则非常简单，群体智能的实现简单、方便，加上系统用于通信的开销少，易于扩充，篚通过简单个体的交瓦表现出高度的智能，使原来一些复杂的、难于用常规的优化算法进行处理的问题可以得到解决，因此大大增强了人们解决和处理优化问题的能力。
２０００年，ＭｕｚａｆｆａｒＥｕｓｕｆｆ和ＫｅｖｉｎＬａｎｓｅｙ模拟青蛙觅食过程，提出混洗蛙跳算法（ＳｈｕｆｆｌｅＦｒｏｇＬｅａｐ—ｉｎｇＡｌｇｏｒｉｔｈｍ．ＳＦＬＡ）”１，该算法模拟青蛙群体在寻觅食物时，分成不同的族群进行思想传递的过程，将全局信息交换与局部搜索结合【２，，实现局部搜索使局部的个体问信息传递，混合策略使局部问的思想得到交换的舀的。混洗蛙跳算法概念简单，需要调整的参数少，计算速度快，全局搜索能力强，易于实现”，，所以主要应用于解决多目标优化问题。
通过与遗传算法、蚁群算法和粒子群算法的比较发现，混洗蛙跳算法在解决优化问题时搜索速度是最快的Ｈ－。，这样的一个优势引起了很多研究者的注意，近年来，出现了一些对蛙跳算法的改进，例如在原始混洗蛙跳算法中引进一个加速搜索范围参数”，；将粒子群算法的惯性移动与混洗蛙跳算法的子群相结合形成新的模因算法ｍ，；引进代表青蛙个体思想的
基金项日：湖南省教育厅资助科研项目（Ｎｏ．０９Ｃ６４８）。
作者箝介：王晓笛，硕士研究生，研究方向为算法理论；肖伟，吾日教授，研究方向为汁算数学的教学和研究；何灿．工程师，研究方向为算法研究及ｗｅｂ开发。
收稿日期：２０１１－０４—２９修回日期：２０１１－０７．２６ＣＮＫＩ出版日期：２０１１－０９．２９
ＤＯＩ：１０．３７７８／ｊｉｓｓｎ．１００２—８３３１。２０１２，３０．０４９ｈｔｔｐ：／／ｗｖ，，＇ｗ，ｃｎｋｉ，ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｔｔｌｌ２１２７，ＴＰ２Ｑｌ、凹２９，１０３５．｛３１６，ｈ｛ｍｌ
万方数据