优化算法人工蜂群算法ABC.doc

优化算法人工蜂群算法ABC.doc

《优化算法人工蜂群算法ABC.doc》由会员分享，可在线阅读，更多相关《优化算法人工蜂群算法ABC.doc（12页珍藏版）》请在冰点文库上搜索。

优化算法——人工蜂群算法（ABC）

一、人工蜂群算法的介绍

手机微信关注公众号ID：

datadw学习数据挖掘，研究大数据，关注你想了解的，分享你需要的。

人工蜂群算法（ArtificialBeeColony,ABC）是由Karaboga于2005年提出的一种新颖的基于群智能的全局优化算法，其直观背景来源于蜂群的采蜜行为，蜜蜂根据各自的分工进行不同的活动，并实现蜂群信息的共享和交流，从而找到问题的最优解。

人工蜂群算法属于群智能算法的一种。

二、人工蜂群算法的原理

  1、原理

    标准的ABC算法通过模拟实际蜜蜂的采蜜机制将人工蜂群分为3类:

采蜜蜂、观察蜂和侦察蜂。

整个蜂群的目标是寻找花蜜量最大的蜜源。

在标准的ABC算法中，采蜜蜂利用先前的蜜源信息寻找新的蜜源并与观察蜂分享蜜源信息；观察蜂在蜂房中等待并依据采蜜蜂分享的信息寻找新的蜜源；侦查蜂的任务是寻找一个新的有价值的蜜源，它们在蜂房附近随机地寻找蜜源。

    假设问题的解空间是维的，采蜜蜂与观察蜂的个数都是，采蜜蜂的个数或观察蜂的个数与蜜源的数量相等。

则标准的ABC算法将优化问题的求解过程看成是在维搜索空间中进行搜索。

每个蜜源的位置代表问题的一个可能解，蜜源的花蜜量对应于相应的解的适应度。

一个采蜜蜂与一个蜜源是相对应的。

与第个蜜源相对应的采蜜蜂依据如下公式寻找新的蜜源：

其中，，，是区间上的随机数，。

标准的ABC算法将新生成的可能解与原来的解作比较，并采用贪婪选择策略保留较好的解。

每一个观察蜂依据概率选择一个蜜源，概率公式为

其中，是可能解的适应值。

对于被选择的蜜源，观察蜂根据上面概率公式搜寻新的可能解。

当所有的采蜜蜂和观察蜂都搜索完整个搜索空间时，如果一个蜜源的适应值在给定的步骤内（定义为控制参数“limit”）没有被提高,则丢弃该蜜源，而与该蜜源相对应的采蜜蜂变成侦查蜂，侦查蜂通过已下公式搜索新的可能解。

其中，是区间上的随机数，和是第维的下界和上界。

  2、流程

·初始化；

·重复以下过程：

o将采蜜蜂与蜜源一一对应，根据上面第一个公式更新蜜源信息，同时确定蜜源的花蜜量；

o观察蜂根据采蜜蜂所提供的信息采用一定的选择策略选择蜜源，根据第一个公式更新蜜源信息，同时确定蜜源的花蜜量；

o确定侦查蜂，并根据第三个公式寻找新的蜜源；

o记忆迄今为止最好的蜜源；

·判断终止条件是否成立；

三、人工蜂群算法用于求解函数优化问题

  对于函数

其中。

代码：

[cpp] viewplaincopy

1.#include  

2.#include  

3.#include  

4.#include  

5.#include  

6.#include  

7.using namespace std;  

8.  

9.const int NP=40;//种群的规模，采蜜蜂+观察蜂  

10.const int FoodNumber=NP/2;//食物的数量，为采蜜蜂的数量  

11.const int limit=20;//限度，超过这个限度没有更新采蜜蜂变成侦查蜂  

12.const int maxCycle=10000;//停止条件  

13.  

14./*****函数的特定参数*****/  

15.const int D=2;//函数的参数个数  

16.const double lb=-100;//函数的下界   

17.const double ub=100;//函数的上界  

18.  

19.double result[maxCycle]={0};  

20.  

21./*****种群的定义****/  

22.struct BeeGroup  

23.{  

24.    double code[D];//函数的维数  

25.    double trueFit;//记录真实的最小值  

26.    double fitness;  

27.    double rfitness;//相对适应值比例  

28.    int trail;//表示实验的次数，用于与limit作比较  

29.}Bee[FoodNumber];  

30.  

31.BeeGroup NectarSource[FoodNumber];//蜜源，注意：

一切的修改都是针对蜜源而言的  

32.BeeGroup EmployedBee[FoodNumber];//采蜜蜂  

33.BeeGroup OnLooker[FoodNumber];//观察蜂  

34.BeeGroup BestSource;//记录最好蜜源  

35.  

36./*****函数的声明*****/  

37.double random（double, double）;//产生区间上的随机数  

38.void initilize（）;//初始化参数  

39.double calculationTruefit（BeeGroup）;//计算真实的函数值  

40.double calculationFitness（double）;//计算适应值  

41.void CalculateProbabilities（）;//计算轮盘赌的概率  

42.void evalueSource（）;//评价蜜源  

43.void sendEmployedBees（）;  

44.void sendOnlookerBees（）;  

45.void sendScoutBees（）;  

46.void MemorizeBestSource（）;  

47.  

48.  

49./*******主函数*******/  

50.int main（）  

51.{  

52.    ofstream output;  

53.    output.open（"dataABC.txt"）;  

54.  

55.    srand（（unsigned）time（NULL））;  

56.    initilize（）;//初始化  

57.    MemorizeBestSource（）;//保存最好的蜜源  

58.          

59.    //主要的循环  

60.    int gen=0;  

61.    while（gen

62.    {  

63.        sendEmployedBees（）;  

64.              

65.        CalculateProbabilities（）;  

66.              

67.        sendOnlookerBees（）;  

68.              

69.        MemorizeBestSource（）;  

70.              

71.        sendScoutBees（）;  

72.              

73.        MemorizeBestSource（）;  

74.  

75.        output<

76.              

77.        gen++;  

78.    }  

79.      

80.    output.close（）;  

81.    cout<<"运行结束!

!

"<

82.    return 0;  

83.}  

84.  

85./*****函数的实现****/  

86.double random（double start, double end）//随机产生区间内的随机数  

87.{     

88.    return start+（end-start）*rand（）/（RAND_MAX + 1.0）;  

89.}  

90.  

91.void initilize（）//初始化参数  

92.{  

93.    int i,j;  

94.    for （i=0;i

95.    {  

96.        for （j=0;j

97.        {  

98.            NectarSource[i].code[j]=random（lb,ub）;  

99.            EmployedBee[i].code[j]=NectarSource[i].code[j];  

100.            OnLooker[i].code[j]=NectarSource[i].code[j];  

101.            BestSource.code[j]=NectarSource[0].code[j];  

102.        }  

103.        /****蜜源的初始化*****/  

104.        NectarSource[i].trueFit=calculationTruefit（NectarSource[i]）;  

105.        NectarSource[i].fitness=calculationFitness（NectarSource[i].trueFit）;  

106.        NectarSource[i].rfitness=0;  

107.        NectarSource[i].trail=0;  

108.        /****采蜜蜂的初始化*****/  

109.        EmployedBee[i].trueFit=NectarSource[i].trueFit;  

110.        EmployedBee[i].fitness=NectarSource[i].fitness;  

111.        EmployedBee[i].rfitness=NectarSource[i].rfitness;  

112.        EmployedBee[i].trail=NectarSource[i].trail;  

113.        /****观察蜂的初始化****/  

114.        OnLooker[i].trueFit=NectarSource[i].trueFit;  

115.        OnLooker[i].fitness=NectarSource[i].fitness;  

116.        OnLooker[i].rfitness=NectarSource[i].rfitness;  

117.        OnLooker[i].trail=NectarSource[i].trail;  

118.    }  

119.    /*****最优蜜源的初始化*****/  

120.    BestSource.trueFit=NectarSource[0].trueFit;  

121.    BestSource.fitness=NectarSource[0].fitness;  

122.    BestSource.rfitness=NectarSource[0].rfitness;  

123.    BestSource.trail=NectarSource[0].trail;  

124.}  

125.  

126.double calculationTruefit（BeeGroup bee）//计算真实的函数值  

127.{  

128.    double truefit=0;  

129.    /******测试函数1******/  

130.    truefit=0.5+（sin（sqrt（bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]））*sin（sqrt（bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]））-0.5）  

131.        /（（1+0.001*（bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]））*（1+0.001*（bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]）））;  

132.  

133.    return truefit;  

134.}  

135.  

136.double calculationFitness（double truefit）//计算适应值  

137.{  

138.    double fitnessResult=0;  

139.    if （truefit>=0）  

140.    {  

141.        fitnessResult=1/（truefit+1）;  

142.    }else  

143.    {  

144.        fitnessResult=1+abs（truefit）;  

145.    }  

146.    return fitnessResult;  

147.}  

148.  

149.void sendEmployedBees（）//修改采蜜蜂的函数  

150.{  

151.    int i,j,k;  

152.    int param2change;//需要改变的维数  

153.    double Rij;//[-1,1]之间的随机数  

154.    for （i=0;i

155.    {  

156.          

157.        param2change=（int）random（0,D）;//随机选取需要改变的维数  

158.  

159.        /******选取不等于i的k********/  

160.        while 

（1）  

161.        {  

162.            k=（int）random（0,FoodNumber）;  

163.            if （k!

=i）  

164.            {  

165.                break;  

166.            }  

167.        }  

168.  

169.        for （j=0;j

170.        {  

171.            EmployedBee[i].code[j]=NectarSource[i].code[j];  

172.        }  

173.  

174.        /*******采蜜蜂去更新信息*******/  

175.        Rij=random（-1,1）;  

176.        EmployedBee[i].code[param2change]=NectarSource[i].code[param2change]+Rij*（NectarSource[i].code[param2change]-NectarSource[k].code[param2change]）;  

177.        /*******判断是否越界********/  

178.        if （EmployedBee[i].code[param2change]>ub）  

179.        {  

180.            EmployedBee[i].code[param2change]=ub;  

181.        }  

182.        if （EmployedBee[i].code[param2change]

183.        {  

184.            EmployedBee[i].code[param2change]=lb;  

185.        }  

186.        EmployedBee[i].trueFit=calculationTruefit（EmployedBee[i]）;  

187.        EmployedBee[i].fitness=calculationFitness（EmployedBee[i].trueFit）;  

188.  

189.        /******贪婪选择策略*******/  

190.        if （EmployedBee[i].trueFit

191.        {  

192.            for （j=0;j

193.            {  

194.                NectarSource[i].code[j]=EmployedBee[i].code[j];  

195.            }  

196.            NectarSource[i].trail=0;  

197.            NectarSource[i].trueFit=EmployedBee[i].trueFit;  

198.            NectarSource[i].fitness=EmployedBee[i].fitness;  

199.        }else  

200.        {  

201.            NectarSource[i].trail++;  

202.        }  

203.    }  

204.}  

205.  

206.void CalculateProbabilities（）//计算轮盘赌的选择概率  

207.{  

208.    int i;  

209.    double maxfit;  

210.    maxfit=NectarSource[0].fitness;  

211.    for （i=1;i

212.    {  

213.        if （NectarSource[i].fitness>maxfit）  

214.            maxfit=NectarSource[i].fitness;  

215.    }  

216.      

217.    for （i=0;i

218.    {  

219.        NectarSource[i].rfitness=（0.9*（NectarSource[i].fitness/maxfit））+0.1;  

220.    }  

221.}  

222.  

223.void sendOnlookerBees（）//采蜜蜂与观察蜂交流信息，观察蜂更改信息  

224.{  

225.    int i,j,t,k;  

226.    double R_choosed;//被选中的概率  

227.    int param2change;//需要被改变的维数  

228.    double Rij;//[-1,1]之间的随机数  

229.    i=0;  

230.    t=0;  

231.    while（t

232.    {  

233.          

234.        R_choosed=random（0,1）;  

235.        if（R_choosed

236.        {          

237.            t++;  

238.            param2change=（int）random（0,D）;  

239.              

240.            /******选取不等于i的k********/  

241.            while 

（1）  

242.            {  

243.                k=（int）random（0,FoodNumber）;  

244.                if （k!

=i）  

245.                {  

246.                    break;  

247.                }  

248.            }  

249.  

250.            for（j=0;j

251.            {  

252.                OnLooker[i].code[j]=NectarSource[i].code[j];  

253.            }  

254.              

255.            /****更新******/  

256.            Rij=random（-1,1）;  

257.            OnLooker[i].code[param2change]=NectarSource[i].code[param2change]+Rij*（NectarSource[i].code[param2change]-NectarSource[k].code[param2change]）;  

258.              

259.            /*******判断是否越界*******/  

260.            if （OnLooker[i].code[param2change]

261.            {  

262.                OnLooker[i].code[param2change]=lb;  

263