2013神经网络、模糊控制及专家系统第五章.ppt

当C2＝0时，则粒子之间没有社会信息，模型变为只有认知(cognition-only)模型： 被称为局部PSO算法。由于个体之间没有信息的交流，整个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。 3. 粒子群优化算法PSO 局部和全局最优算法 参数分析 参数有： 群体规模m ：一般取20～40，对较难或特定类别的问题可以取到100～200。 最大速度 决定当前位置与最好位置之间的区域的分辨率(或精度)。如果太快，则粒子有可能越过极小点;如果太慢，则粒子不能在局部极小点之外进行足够的探索，会陷入到局部极值区域内。这种限制可以达到防止计算溢出、决定问题空间搜索的粒度的目的。 3. 粒子群优化算法PSO 机理与构造 免疫算子的机理 免疫算子是由接种疫苗和免疫选择两部分操作构成的。其中，疫苗指的是依据人们对待求问题所具备的先验知识而从中提取出的一种基本的特征信息，抗体是指根据这种特征信息而得出的一类解。前者可看作是对待求的最佳个体所能匹配模式的一种估计，后者是对这种模式进行匹配而形成的样本。免疫算子中接种疫苗作用的发挥与选取疫苗的优劣、生成抗体的好坏直接相关；免疫遗传算法的收敛性靠免疫算子中的免疫选择来保证。 3. 免疫遗传算法 在免疫选择作用下，若疫苗使抗体适值得到提高，且高于当前群体的平均适值，则疫苗所对应的模式将在群体中呈指数级扩散；否则；它将被遏制或呈指数级衰减。 可见，免疫选择在加强接种疫苗方面具有积极作用，在消除其负面影响方面具有鲁棒性。 3. 免疫遗传算法 免疫算子的执行算法 为表述方便，令 为第k代第i个个体 接种疫苗后所得到的抗体，Pi为个体接种疫苗的概率，PV为更新疫苗的概率， 表示按模式hj修改个体 上基因的接种疫苗操作，n和m分别为群体和疫苗的规模。 至此，在针对某一待求问题而构造和应用免疫算子时所进行的过程可表示如下： 3. 免疫遗传算法 ⑴ 抽取疫苗： ① 分析待求问题； ② 依据特征信息估计特定基因位上的模式 H={hj；j=1, 2， …, m} ⑵ 令k=0, j=0 ⑶ while(conditions = True) ① 若{PI}=True，则j=j+1； ② i=0 ③ for (i≤n) { 接种疫苗： 免疫检验：若 ，则 ；否则 ； i=i+1； 退火选择：Ak+1=S(Ak)，k=k+1； } 3. 免疫遗传算法 其中：停机条件可以采用最大迭代次数或统计个体最佳适值连续不变的最大次数。这里模拟退火算法是基于迭代求解策略的一种随机寻优算法。 3. 免疫遗传算法 免疫疫苗的选取示例 在此结合TSP问题具体讨论免疫疫苗选取的具体过程与步骤。 ⑴ 搜索特征信息 假设在某一时刻，从一城市出发欲前往下一个目标城市，一般首先考虑距离当地路程最近的城市；若它已被访问过，则剔除该城，然后选择该城之外的距离最小的城市；并以此类推。尽管这种贪婪策略不能保证全局最优，但在仅包含几个城市的一个很小范围内，往往不失为一个较好的策略。当然，能否作为最终的解决方案，还需要进一步的判断。 3. 免疫遗传算法 ⑵ 制作免疫疫苗 就TSP问题的特点而言，在最终的最佳路径解决方案中，必然包括且尽可能包括相邻城市间距离最短的路径。显然，这种特点可作为求解问题时提供参考的一种特征信息或知识，这也是从问题中抽取疫苗的一种信息途径。因此，在具体实施过程中，只需使用一般的循环迭代方法找出所有城市的邻近城市即可（当然，某一城市可能是两个或多个城市的邻近城市，也可能都不是）。需强调的是，疫苗不是一个个体，故不能作为问题的解，它仅仅具备个体在某些基因位上的特征。 ⑶ 接种免疫疫苗 为不失一般性，设TSP问题中所有与城市Ai距离最近的城市为Aj，且二者并非直接连接而是处于某一路径的两段： Ai-1——Ai——Ai+1 ① 段 Aj-1——Aj——Aj+1 ② 段 3. 免疫遗传算法 如图中实线所示。当前的遍历路径为，其对应的路径长度为： 在免疫概率Pi发生条件下，对城市Ai而言，免疫算子将把其邻近城市Aj排列为其下一个城市，而使原先的遍历路径调整为： 相应的路径长度变化为： 3. 免疫遗传算法 3. 免疫遗传算法 比较两路径长度，因为Aj是所有城市中（即全局