2023.07.31

总结：复习学过的三种算法 1.粒子群算法：核心是速度更新公式和位置更新公式。（1）速度更新公式由三部分组成，惯性部分（由惯性权重和粒子自身速度构成，表示粒子对先前自身状态的信任）、认知部分（表示粒子本身的思考，即粒子自身经验的部分，粒子当前位置与自身历史最优位置之间的距离和方向）、社会部分（表示粒子之间的信息共享与合作，即粒子当前位置与群体历史位置之间的距离和方向）。（2）位置更新公式由当前位置和下一次迭代的速度组成。（3）适应值为因变量，即目标函数；粒子位置为自变量。（4）粒子群优化算法流程图 。（5）将粒子群算法应用与风机布局问题，假设有10台风机，以年发电量最大为目标，优化风机坐标（x,y）和轮毂高度h。每个粒子代表了一种布局方案，一个粒子的位置由30个变量组成(（x1,y1,h1）, （x2,y2,h2）,......,（x10,y10,h10）) ，将年发电量作为适应度函数，评价粒子的位置是否最优。

2.一种自适应粒子群优化算法：APSO的主要思想是根据群体的收敛情况动态调整算法的参数。APSO的核心算法与PSO类似，由粒子的速度和位置更新规则组成。每个粒子通过与局部最优解和全局最优解比较来更新自己的位置和速度。该种APSO通过开发一个系统参数自适应方案和一个精英学习策略（ELS）来实现。（1）设计一个进化状态估计（ESE）技术。在PSO过程中，种群分布特征随代数和进化状态变化，如早期阶段粒子分散在各个区域，因此种群分布是分散的，后期粒子会聚集到一起并收敛到一个局部或全局最优区域。本文通过进化因子f=(dg-dmin)/(dmax-dmin)判断当前粒子所处的状态，di为每个粒子i与所有其他粒子的平均距离，dg为全局最佳粒子与其他所有粒子的平均距离，比较所有di确定dmax、dmin。在探索阶段f较大，在开发阶段f减小，收敛阶段f趋近于0，随后当搜索目标发生转移时，PSO跳出局部最优，产生f的最大值，随后再进行探索和开发，直到出现另一次收敛。将f分为四组，代表四个状态——探索S1、开发S2、收敛S3、跳出S4，采用模糊分类法对齐进行分类。(2).惯性权重w的调整。w随进化状态发生变化，是f的函数w(f)=1/(1+1.5e(-2.6f)). f、w较大时有利于全局搜索，f较小时，是开发或收敛状态，w减小有利于局部搜索。（3）根据粒子所处的状态控制加速因子c1、c2，并规定两代粒子之间的最大增幅与减幅限制。（4）本文设计了一个基于高斯扰动的ELS并将其应用于全局最佳粒子，以便在确定搜索为收敛状态时帮助跳出局部最优。 3.禁忌搜索算法。它是一个用来跳出局部最优的搜寻方法，从一个初始可行解出发，选择一系列的特定搜索方向作为试探，选择让特定的目标函数值变化最多的方向移动。（1）流程：禁忌搜索算法在初始化的时候，在搜索空间随机生成一个初始解 i，禁忌表H置空，当前解i记为历史最优解 s，然后进入迭代的搜索过程。在每一次迭代中，都从当前的解出发，在当前禁忌表H的限制下，构造出解i的邻域A，然后从A中选出适应值最好的解j来替换解i ，同时更新禁忌表H。在解j替换解i之后，如果解i的质量得到改善，那么历史最优的解 s 将被解i替换:否则，s 保持不变，即使解i虽然暂时变差了，但是由于扩大了搜索空间，仍有利于跳出局部最优。得到了新的当前解i之后，算法返回迭代的开始继续进行，直到找到最优解或者运行了一定的迭代次数等终止条件的时候结束算法。(2)产生邻域解和候选解：候选解是在邻域解里面选取适应度较好的几个作为候选解。邻域解可通过随机法、交换法、单个法、阈值法等方法生成。交换法是在两个不同的集群中分别选取两个不同的对象，然后将它们交换。单个法是每次将一个对象从一个集群移动到另一个集群中。阈值法是一种概率阈值方法，常用于在基于聚类算法的禁忌搜索中建立邻域（测试）解。概率阈值越高，允许的干扰就越少，因此，测试解会与当前解更接近，反之亦然。（3）首先对候选解按照适应度排序，1号候选解优于2号候选解，依次类推。然后根据藐视准则更新禁忌表，更新禁忌表分为两类，①第一类是候选解的最佳适应度大于初始解的适应度值（如序号为1的候选解的适应度值为9大于S0的适应度值8.5），此时将适应度值最大的候选解作为下一次迭代的S0，同时更新禁忌表。更新禁忌表（禁忌矩阵）时判断矩阵中的每个值是否为0，禁忌表中不为0的值全部减1。同时将更新后的禁忌表序号1对应的值设置为禁忌最大长度，如10。②第二类是候选解的最佳适应度不大于初始解的适应度值。此时1号候选解的最佳适应度为8小于初始解S0的适应度值8.5，需要对候选解在禁忌表中的值逐一判断。判断1号候选解在禁忌表（禁忌矩阵）中的值是否为0，若为0则将1号候选解作为下一次迭代的S0，且禁忌表中所有不为0的值全部减1（和第一类的操作相同），并令禁忌表（禁忌矩阵）中1号候选解对应的值为10（禁忌最大长度）。若不为0，则对2号候选解进行判断​。（禁忌表和禁忌长度的作用是为了使搜索在一定的迭代次数内不重复​。）（4）详细步骤：（Ab、At、Ac表示最好的解、邻域解和当前解，Zb、Zt、Ac表示他们对应的目标函数）①初始化：设A为采用随机初始化得到的初始解，Z为目标函数的值，然后令Ab=Ac=A，且Zb=Zc=Z。设置以下参数的值：method(邻域方法：随机、交换、单个、阈值)、MTLS（禁忌表的最大尺寸）、P（概率阈值）、NTS（邻域解的数量）、ITMAX是作为终止条件固定的最大迭代次数，令TLL（禁忌表长度）=0，执行步骤2。②选择生成邻域解的方法，选择“method”为“随机”（random）的，如果“method”为禁忌的，重复步骤2，否则进入步骤3。③使用Ac生成多个邻域解，At1、At2、......、AtNTS，并评估其对应的目标函数Zt1、Zt2、......、ZtNTS。④将解Zt1、Zt2、......、ZtNTS按升序排列：如果Zt1不是禁忌的，或是禁忌的但Zt1＞Zb（Zt1比Zb更好），则Ac=At1，Zc=Zt1,进入步骤5；否则，Ac=Atl，Zc=Ztl，Atl是邻域解中非禁忌的解，进入步骤5。如果所有邻域解都是禁忌的，返回步骤3。⑤在第二个禁忌表(保存已经访问的解)的末尾插入Ac，TLL=TLL+1（如果TLL=MTLS+1，则删除列表中的第一个元素，TLL=TLL-1）。如果Zc＞Zb（Zc优于Zb），则Ab=Ac，Zb=Zc。如果经过一定次数的迭代后，解没有改善，则将当前的method插入到第一个禁忌表中，并返回步骤2。⑥检查终止条件。如果满足终止条件，Ab将作为最佳解、Zb作为对应的最佳目标函数被输出；否则返回步骤2。