各种智能优化算法比较与实现（matlab版）_1

1.1算法基本思想

免疫算法是受生物免疫系统的启发而推出的一种新型的智能搜索算法。它是一种确定性和随机性选择相结合并具有“勘探”与“开采”能力的启发式随机搜索算法。免疫算法将优化问题中待优化的问题对应免疫应答中的抗原，可行解对应抗体（B细胞），可行解质量对应免疫细胞与抗原的亲和度。如此则可以将优化问题的寻优过程与生物免疫系统识别抗原并实现抗体进化的过程对应起来，将生物免疫应答中的进化过程抽象成数学上的进化寻优过程，形成一种智能优化算法。它具有一般免疫系统的特征，采用群体搜索策略，通过迭代计算，最终以较大的概率得到问题的最优解。相对于其他算法，免疫算法利用自身产生多样性和维持机制的特点，保证了种群的多样性，克服了一般寻优过程（特别是多峰值的寻优过程）的不可避免的“早熟”问题，可以求得全局最优解。免疫算法具有自适应性、随机性、并行性、全局收敛性、种群多样性等优点。
1.2 算法操作步骤
（1）首先进行抗原识别，即理解待优化的问题，对问题进行可行性分析，提取先验知识，构造出合适的亲和度函数，并制定各种约束条件。
（2）然后初始化抗体群，通过编码把问题的可行解表示成解空间中的抗体，在解的空间内随机产生一个初始种群。
（3）对种群中的每一个可行解进行亲和度评价。（记忆单元的更新：将与抗原亲和性高的抗体加入到记忆单元，并用新加入的抗体取代与其亲和性最高的原有抗体（抗体和抗体的亲和性计算））
（4）判断是否满足算法终止条件；如果满足条件则终止算法寻优过程，输出计算结果；否则继续寻优运算。
（5）计算抗体浓度和激励度。（促进和抑制抗体的产生：计算每个抗体的期望值，抑制期望值低于阈值的抗体；可以知道与抗原间具有的亲和力越高，该抗体的克隆数目越高，其变异率也越低）
（6）进行免疫处理，包括免疫选择、克隆、变异和克隆抑制。
免疫选择：根据种群中抗体的亲和度和浓度计算结果选择优质抗体，使其活化；
克隆：对活化的抗体进行克隆复制，得到若干副本；
变异：对克隆得到的副本进行变异操作，使其发生亲和度突变；
克隆抑制：对变异结果进行再选择，抑制亲和度低的抗体，保留亲和度高的变异结果。
（7）种群刷新，以随机生成的新抗体替代种群中激励度较低的抗体，形成新一代抗体，转步骤（3）。
免疫算法运算流程图

1.3 代码实现

结果为

2.1算法基本思想
蚁群算法是一种源于大自然生物世界的新的仿生进化算法，通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式搜索算法。蚂蚁在运动过程中，能够在它所经过的路径上留下信息素进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此来指导自己的运动方向。初始阶段，环境中没有信息素的遗留，蚂蚁寻找事物完全是随机选择路径，随后寻找该事物源的过程中就会受到先前蚂蚁所残留的信息素的影响，其表现为蚂蚁在选择路径时趋向于选择信息素浓度高的路径。同时，信息素是一种挥发性化学物，会随着时间的推移而慢慢地消逝。如果每只蚂蚁在单位距离留下的信息素相同，那对于较短路径上残留的信息素就相对较高，这被后来的蚂蚁选择的概率就将大，从而导致这条短路径上走的蚂蚁就越多。而经过的蚂蚁越多，该路径上残留的信息素就将更多，这样使得整个蚂蚁的集体行为构成了信息素的正反馈过程，最终整个蚁群会找出最优路径。
2.2 基本蚁群算法操作步骤
（1）初始化参数：开始时每条边的信息素量都相等
（2）将各蚂蚁放置各顶点，禁忌表为对应的顶点。
（3）蚂蚁个体根据状态转移概率计算转移概率选择下一个顶点，更新禁忌表，再计算概率，再选择顶点，再更新禁忌表，直至遍历所有顶点1次。
（4）计算该只蚂蚁留在各边的信息素量，该蚂蚁死去。
（5）重复（3）～（4），直至所有蚂蚁都周游完毕。
（6）计算各边的信息素增量和信息素量。
（7）记录本次迭代的路径，更新当前的最优路径，清空禁忌表。
（8）判断是否达到预定的迭代步数，或者是否出现停滞现象。若是，算法结束，输出当前最优路径；否则，转（2），进行下一次迭代。

2.3 代码实现
这里用蚁群算法解决旅行商问题

结果显示

3.1算法基本思想
粒子群算法（Particle Swarm Optimization，PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景：一群鸟在区域中随机搜寻食物，在这个区域里只有一块食物，所有的鸟知道自己当前位置离食物多远，那么搜索的最简单有效的策略就是搜索目前离食物最近的鸟的周围区域。粒子群算法利用这种模型得到启示并应用于解决优化问题。在粒子群算法中，-用一种粒子来模拟上述的鸟类个体，每个粒子可视为N维搜索空间中的一个搜索个体，粒子的当前位置即为对应优化问题的一个候选解，粒子的飞行过程即为该个体的搜索过程.粒子的飞行速度可根据粒子历史最优位置和种群历史最优位置进行动态调整.粒子仅具有两个属性：速度和位置，速度代表移动的快慢，位置代表移动的方向。每个粒子单独搜寻的最优解叫做个体极值，粒子群中最优的个体极值作为当前全局最优解。不断迭代，更新速度和位置。最终得到满足终止条件的最优解。
3.2算法基本操作步骤
（1）初始化粒子群，包括群体规模N，每个粒子的位置xi和速度vi。
（2）计算每个粒子的适应度fit[i]。
（3）对每个粒子，用它的适应度值fit[i]和个体极值pbest(i)比较。如果fit[i]小于pbest(i)，则用fit[i]替换掉pbest(i)。
（4）对每个粒子，用它的适应度值fit[i]和全局极值gbest(i)比较。如果fit[i]小于gbest(i)，则用fit[i]替换掉gbest(i)。
（5）迭代更新粒子的位置xi和速度vi。
（6）进行边界条件处理
（7）判断算法终止条件是否满足：若是，则结束算法并输出优化结果；否则返回（2）
粒子群算法运算流程图

3.3 代码实现

本次实验选取下面的5个测试函数，分别用以上智能算法进行结果分析比较。首先使用蚁群算法、免疫算法和粒子群算法以第一个基准函数为例，画出适应度图像并据此分析每个函数的特点。本文用到的环境是Windows10系统，软件是MATLAB R2017a.
（1）函数f1(x,y)=3cos(xy)+x+y2的最小值，其中x的取值范围为[-4,4],y的取值范围为[-4,-4]。这是一个有多个局部极值的函数，其函数图像如图所示：

（2）函数f2(x,y)=5sin(xy)+x2+y2的最小值，其中x的取值范围为[-4,4],y的取值范围为[-4,-4]。这是一个有多个局部极值的函数，其函数图像如图所示：

（3）函数f3(x,y)=6sin(4x)+9cos(5y)+y2的最小值，其中x的取值范围为[-4,4],y的取值范围为[-4,-4]。这是一个有多个局部极值的函数，其函数图像如图所示：

（4）函数f4(x,y)=3cos6y+x2+y2的最小值，其中x的取值范围为[-4,4],y的取值范围为[-4,-4]。其函数图像如图所示：

（5）函数f5(x,y)=sin(x2+y)+cos(5x)+x+y的最小值，其中x的取值范围为[-4,4],y的取值范围为[-4,-4]。这是一个有多个局部极值的函数，其函数图像如图所示：

仿真过程如下设置：
第一步：初始化免疫个体维数为D=2，免疫种群个体数为NP=50，最大免疫代数为G=200，变异概率为Pm=0.7，激励度系数为alfa=2，belta=1，相似度阈值为detas=0.2，克隆个数为Nc1=5;
第二步：随机产生初始种群，计算个体亲和度、抗体浓度和激励度，并按激励度排序。
第三步：取激励度前NP/2个个体进行克隆、变异、克隆抑制的免疫操作；免疫后的种群进行激励度计算。
第四步：随机生成NP/2个个体的新种群，并计算个体亲和度、抗体浓度和激励度；免疫种群和随机种群合并，并按激励度排序，进行免疫迭代。
第五步：判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。
优化结束后，其适应度进化曲线如下图2.1所示。

图2.1免疫算法适应度
分析：
优化后的结果为：在免疫代数为200，即x=-4,y=0.7539时，函数取得最小值-6.4078.免疫算法不强调算法参数设置和初始解的质量，利用其启发式的智能搜索机制，即使起步于劣质解种群，最终也可以搜索到问题的全局最优解，对问题和初始解的依赖性不强，具有很强的适应性和鲁棒性。故在上图，种群20代以后基本处于最优解。

仿真过程如下设置：
第一步：初始化蚂蚁个数m=20，最大迭代次数G=200，信息素蒸发系数Rh0=0.9，转移概率常数P0=0.2，局部搜索步长step=0.1
第二步：随机产生蚂蚁初始位置，计算适应度函数值，设为初始信息素，计算状态转移概率。
第三步：进行位置更新：当状态转移概率小于转移概率常数时，进行局部搜索；当状态转移概率大于转移概率常数时，进行全局搜索，产生新的蚂蚁位置，并用边界吸收方式进行 边界条件处理，将蚂蚁位置界定在取值范围内。
第四步：计算新的蚂蚁位置的适应度值，判断蚂蚁是否移动，更新信息素。
第五步：判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。
优化结束后，其适应度进化曲线如下图2.2所示。

图2.2 蚁群算法适应度
分析：
优化后的结果为：在200轮迭代，即x=-4,y=-0.7539时，函数取得最小值-6.4079.蚁群算法一般需要较长的搜索时间和容易出现停滞现象等不足，故在上图中，容易看到，在100代后，才基本找到最优解。

仿真过程如下设置：
第一步：初始化群体例子个数为N=100，粒子维数为D=2，最大迭代次数为T=200，学习因子c1=c2=1.5，惯性权重最大值为Wmax=0.8,惯性权重最小值为Wmin=0.4，位置最大值为Xmax=4，位置最小值为Xmin=-4，速度最大值为Vmax=1，速度最小值为Vmin=-1.
第二步：初始化种群粒子位置x和速度v，粒子个体最优位置p和最优值pbest，
粒子群全局最优位置g和最优值gbest。
第三步：计算动态惯性权重值w，更新位置x和速度值v，并进行边界条件处理，判断是否替换粒子个体最优位置p和最优值pbest，以及粒子群全局最优位置g和最优值gbest。
第四步：判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。
优化结束后，其适应度进化曲线如下图2.3所示。

图2.3 粒子群适应度
分析：
优化后的结果为：在200轮迭代，即x=-4，y=-0.7588时，函数取得最小值-6.4072。粒子群算法本质是一种随机搜索算法，它是一种新型的智能优化技术。该算法能以较大概率收敛于全局最优解。如上图所示，算法在40次迭代，基本找到全局最优解。实践证明，粒子群算法适合在动态、多目标优化环境中寻优，与传统优化算法相比，具有较快的计算速度和更好地全局搜索能力。所以，与其他算法相比，粒子群算法是一种高效的并行搜索算法。

蚁群算法和免疫算法分别在5个基准函数上进行实验，同时在每个基准函数实验20次，并求出20次实验蚁群算法和免疫算法求得全局最优解的平均迭代次数及其标准差。平均迭代次数来反映算法的性能，标准差来反映算法的稳定性。如下表2-1
表2-1

分析：
由表2-1所示，免疫算法在平均10次迭代，基本找到全局最优解，而蚁群算法最好的是在平均29次迭代，才基本找到全局最优解。从这个例子上看，免疫算法在效率上是蚁群算法的3倍左右。从标准差上看，免疫算法更稳定。免疫算法和蚁群算法这两种算法，对问题和初始解的依赖性不强，具有很强的适应性和鲁棒性。免疫算法不需要集中控制，可实现并行处理。而且免疫算法的优化进程是一种多进程的并行优化，在探求问题最优解的同时可以得到问题的多个次优解，即除找到问题的最佳方案外，还会得到若干个较好的备选方案，尤其适合于多模态的优化问题。蚁群算法的参数较少，设置简单，因而该算法易于应用到组合优化问题的求解。
2.5 蚁群算法和粒子群算法比较
蚁群算法和粒子群算法分别在5个基准函数上进行实验，同时在每个基准函数实验20次，并求出20次实验蚁群算法和免疫算法求得全局最优解的平均迭代次数及其标准差。平均迭代次数来反映算法的性能，标准差来反映算法的稳定性。如下表2-2
表2-2

分析：
由表2-2所示，蚁群算法最差结果在平均101次迭代，找到全局最优解，而粒子群算法最差结果在22次迭代左右，就找到了全局最优解。从这个例子上看，粒子群算法效率是蚁群算法的5倍左右。从标准差上来比较，粒子群算法算法更稳定。蚁群算法的参数较少，设置简单，因而该算法易于应用到组合优化问题的求解。粒子群算法是基于群智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化算法。与其他算法相比，粒子群算法是一种高效的并行搜索算法。实践证明，它适合在动态、多目标优化环境中寻优，与传统优化算法相比，具有较快的计算速度和更好地全局搜索能力。

粒子群算法和免疫算法分别在5个基准函数上进行实验，同时在每个基准函数实验20次，并求出20次实验蚁群算法和免疫算法求得全局最优解的平均迭代次数及其标准差。平均迭代次数来反映算法的性能，标准差来反映算法的稳定性。如下表2-3

分析：
由表2-3所示，免疫算法最好的结果是在平均8次迭代，基本找到全局最优解，粒子群算法则最好的结果是在平均6次迭代左右，更快地找到全局最优解。从这点看，粒子群算法略微快些，即使从最坏结果看，免疫算法最坏平均在14次，而粒子群算法，则是11次，这点看，依然是粒子群算法更好点。在从标准差方面看，免疫算法和粒子群算法算法稳定性一样。从这个例子上看，粒子群算法在效率上和免疫算法的几乎相同。整体上来看的话，与免疫算法相比，粒子群算法具有较快的计算速度和更好地全局搜索能力，是一种高效的并行搜索算法。

蚁群算法、粒子群算法和免疫算法分别在5个基准函数上进行实验，同时在每个基准函数实验20次，并求出20次实验蚁群算法和免疫算法求得全局最优解的平均迭代次数及其标准差。平均迭代次数来反映算法的性能，标准差来反映算法的稳定性。如下表2-4

分析：
由表2-4所示，免疫算法和粒子群算法平均在10次迭代左右，基本找到了全局最优解，蚁群算法则最好结果在平均29次迭代，才基本找到全局最优解，从这点看，免疫算法和粒子群算法在效率上是蚁群算法的3倍左右，而免疫算法和粒子群算法在效率上几乎持平。

免疫算法和蚁群算法不强调算法参数设置和初始解的质量，利用其启发式的智能搜索机制，即使起步于劣质解种群，最终也可以搜索到问题的全局最优解，对问题和初始解的依赖性不强，具有很强的适应性和鲁棒性。免疫算法不需要集中控制，可实现并行处理。而且免疫算法的优化进程是一种多进程的并行优化，在探求问题最优解的同时可以得到问题的多个次优解，即除找到问题的最佳方案外，还会得到若干个较好的备选方案，尤其适合于多模态的优化问题。蚁群算法的参数较少，设置简单，因而该算法易于应用到组合优化问题的求解。粒子群算法是基于群智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化算法。与其他算法相比，粒子群算法是一种高效的并行搜索算法。实践证明，它适合在动态、多目标优化环境中寻优，与传统优化算法相比，具有较快的计算速度和更好地全局搜索能力。

[1] 蔡自兴，王勇. 智能系统原理、算法与应用[M].北京：机械工业出版社，2014
[2] 李爱国，覃征，鲍复民，等.粒子群优化算法[J].计算机工程与应用，2002
[3] 包子阳，余继周，杨杉编著，智能优化算法及其MATLAB实例（第2版）[M].北京：电子工业出版社，2018.
[4] 刘冰.人工免疫算法及其应用研究[D].重庆：重庆大学，2004.
[5] 黄友锐.智能优化算法及其应用[M].北京：国防工业出版社，2008.
[6] 高海昌，冯博琴.智能优化算法求解TSP问题[J].控制与决策，2006
[7] 段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.
[8]《群体智能优化算法》专题导语[J].郑州大学学报(工学版),2018.
[9] 王凤娟,姜淑凤,单永瑞,张鹏飞,冉东.群智能优化算法的研究与分析[J].信息通信,2018.
[10] 费腾, 张立毅.现代智能优化算法研究[J].信息技术, 2015.
[11] 李智.智能优化算法研究及应用展望.武汉轻工大学学报, 2016.
[12] 楚东来, 赵伟辰, 林春城.群智能算法的研究现状和发展趋势[J].信息通信, 2015,
[13] https://blog.csdn.net/wangqiuyun/article/details/12838903
[14] https://blog.csdn.net/taonull/article/details/45972393
[15] https://blog.csdn.net/greedystar/article/details/80343841
[16] https://blog.csdn.net/v_JULY_v/article/details/6132775