[第六章]智能计算及其应用

进化算法

进化算法是基于自然选择和遗传等生物进化机制的一种搜索算法

基本遗传算法

编码

位串编码

参数编码为一堆排列染色体的方法，一维染色体编码方法

二进制编码

若干个二进制表示一个个体，将解空间映射到串空间

Gray编码

二进制编码变换得到

实数编码

若干实数表示一个个体，在实数空间进行遗传操作

多参数级联编码

把每个参数进行二进制编码得到字串，再把字串连成完整的染色体

群体设定

初始种群的产生

种群规模的确定

群体中个体的数量成为种群规模

适应度函数

将目标函数映射成适应度函数的方法

若目标函数为最大化问题，Fit[f(x)] = f(x)

若目标函数为最大化问题，Fit[f(x)] = 1/f(x)

适应度函数的尺寸变换

将所有妨碍适应度值高的个体产生，从而影响算法正常工作的问题称为欺骗问题

适应度函数的尺寸变换：适应度函数值域的某种映射变换

线性变换

非线性变换

选择

复制，从当前群体中按照一定概率选出优良个体，是他们有机会作为父代繁殖下一代

个体选择概论分配方法

适应度比例方法
排序方法

选择个体方法

轮盘赌选择
锦标赛选择方法
最佳个体保存方法

交叉

配对或复制时，染色体互相混合，产生新的染色体

基本的交叉算子

修正的交叉方法

变异

个体编码的一些位进行随机变化

遗传算法的一般步骤

特点

改进算法

双倍体遗传算法

采用显性和隐性两个染色体同时进行进化

设计

双种群遗传算法

多种群同时进化，交换种群间优秀的个体所携带的遗传信息，打破种内平衡有利于跳出局部最优解

设计

自适应遗传算法

交叉概率P和变异概率P能够随适应度变化自动改变

步骤

概率

应用

流水车间调度问题

设计

群智能

产生背景：受动物群体智能启发的算法

简单个体组成的群落与环境及个体间的互动行为

粒子群优化

原理

流程

参数

位置更新方程

参数设置

应用

车辆路径问题

蚁群算法

算法模型

由信息素和局部启发信息（信息素）共同决定，也称随机比例规则

t时刻蚂蚁k选择从x城市到y城市的概率

allowed(x) = {1，…，n} - tabu(x)表示蚂蚁下一步可以选择的城市

tabu(x)记录蚂蚁走过的城市

=0为多起点随机贪婪算法

=0为正反馈启发式算法

如果考虑信息素随时间的挥发，设表示信息挥发速度，为0~1的常数

拆分成t时刻每只蚂蚁的信息素

产生三种模型

整个路径上k蚂蚁选择的影响

下一条路径上k蚂蚁选择的影响

常量

参数选择

应用

[第五章]搜索求解策略

[第七章]专家系统与机器学习