《人工智能导论》课件 第5章 智能优化算法

第五章智能优化算法《人工智能导论》本章内容5.1优化算法5.2遗传算法5.3群智能算法5.4粒子群算法5.5蚁群算法1

5.1优化算法《人工智能导论》优化问题优化算法的基本概念优化算法的产生与发展优化算法的分类及应用2第5章智能优化算法学习要点信号处理

生产调度

任务分配

模式识别

图像处理

自动控制（1）优化问题3优化算法的概念

计算机科学和数学领域中的一个重要分支，是一类用于在给定约束条件下寻找最优解（或近似最优解）的方法和策略。

优化算法的产生与发展线性规划（20世纪30年代）非线性规划（20世纪50年代）组合优化（20世纪60年代）启发式算法（20世纪70-80年代）群智能算法（20世纪末）机器学习与人工智能（21世纪）

（2）优化算法（1/4）4

线性规划算法单纯形法（Simplex

Method）内点法（Interior-Point

Method）对偶单纯形法（Dual

Simplex

Method）

非线性规划算法梯度下降法（Gradient

Descent）牛顿法（Newton's

Method）

动态规划算法贝尔曼-福特算法（Bellman-Ford

Algorithm）动态规划表（Dynamic

Programming

Table）优化算法的类别5（2）优化算法（2/4）局部搜索算法爬山法（Hill

Climbing）模拟退火（Simulated

Annealing）禁忌搜索（Tabu

Search）群智能算法粒子群优化（Particle

Swarm

Optimization）蚁群优化（Ant

Colony

Optimization）人工蜂群算法（Artificial

Bee

Colony

Algorithm）

启发式算法遗传算法（Genetic

Algorithms）贪心算法（Greedy

Algorithms）

基于深度学习的优化算法随机梯度下降算法（StochasticGradientDescentAlgorithm）

动量算法（MomentumAlgorithm）优化算法的类别

优化算法的分类并不是互斥的，某些优化算法可能同时属于多个类别。6（2）优化算法（3/4）工程领域结构优化设计电路设计交通运输领域物流配送交通流量控制金融领域投资组合优化风险管理优化算法的应用7（2）优化算法（4/4）

第五章智能优化算法《人工智能》本章内容5.1优化算法5.2遗传算法5.3群智能算法5.4粒子群算法5.5蚁群算法8

5.2遗传算法《人工智能》遗传算法的基本思想遗传算法的流程遗传算法的实现过程遗传算法的应用案例遗传算法的特点与改进9第5章智能优化算法学习要点遗传算法（GeneticAlgorithm，GA）是一种通过模拟生物自然进化过程搜索最优解的智能优化算法。1975年约翰霍兰德正式提出应用领域生产调度路径规划模式识别机器学习智能控制（1）遗传算法10基本思想通过对生物遗传和进化过程中的选择、交叉和变异机理的模仿，来完成对问题最优解的自适应搜索。三个基本遗传算子：选择算子、交叉算子、变异算子。（1）遗传算法进化与遗传中的概念遗传算法的要素环境适应度函数种群随机得到的初始解集合（解的个数即群体的规模）个体可行解适应能力解的适应度函数值适者生存适应值较大的解被选中的可能性大染色体解的编码串基因解的编码中的每一分量婚配交叉：选择两个染色体交换部分分量，产生一组新的染色体的过程变异编码的某一分量发生变化的过程进化结束算法终止11Step1:初始化种群；Step2:适应度评价，计算种群中每个个体的适应度值；Step3:选择；Step4:交叉；Step5:变异；Step6:终止条件判定，若不满足，则转第2步，否则进入下一步；Step7:输出适应度值最优的染色体。否是

开始

初始化种群

适应度评价

选择

交叉

变异终止条件输出解12（2）遗传算法流程遗传算法的五要素编码机制种群初始化适应度函数遗传算子（选择、交叉、变异）控制参数13（3）遗传算法的实现过程解空间一个解的编码即：染色体编码其中的一个码和

码所在的位置，即：基因/基因位

编码机制（1/3）解的编码14

编码机制（2/3）15实数编码：直接采用实数编码，若干个实数表示一个个体。整数编码：将个体编码为整数串，每个整数表示一个基因。符号编码：将问题的解表示为符号序列的编码方式，常用于序列排序、调度问题等。除以上介绍的几种编码方式以外，遗传算法还有许多其他的编码方式。

编码机制（3/3）16

种群初始化是算法开始执行的第一步，它决定了算法搜索解空间的起点。通常采用随机的方法在解空间中生成一组解作为初始群体。

种群初始化17

适应度函数用来评估个体在问题求解中的优劣程度。

运用适应度函数为每个个体计算一个适应度值，适应度值越高，表明个体越接近问题的最优解。

适应度函数18

选择

也称为复制操作，是指从当前群体中按照一定的概率选出优良的个体，用来产生下一代。轮盘赌锦标赛排序遗传算子（1/3）19

交叉

交叉通常基于一定的交叉概率pc，对选中的两个父代个体交换某些基因位，形成新的子代个体的过程，也称为重组，是产生新个体的主要手段。单点交叉两点交叉均匀交叉遗传算子（2/3）单点交叉示意图20

遗传算子（3/3）变异

变异操作通常以一个较小的变异概率pm发生，是一种对个体染色体上的基因进行随机改变的操作。21

控制参数种群规模（N）：种群规模影响算法的搜索能力和运行效率。编码长度（L）：编码长度会影响算法的计算量和交叉、变异操作的效果。L的设置跟优化问题密切相关。交叉概率（Pc）：决定了进化过程中参加交配的染色体数目，一般为0.5~1。变异概率（Pm）：决定了进化过程中个体发生变异的数量，增加群体进化的多样性。一般为0.001~0.1之间。22

（4）遗传算法的应用案例（1/7）1.编码机制：二进制编码2.种群初始化：随机初始3.适应度函数：目标函数本身4.匹配选择：轮盘赌选择5.交叉：单点交叉6.变异：单点变异7.环境选择：精英保留策略8.终止规则：最大进化代数23步骤1：根据问题定义适应度函数

import

randomdef

objective_function(x):

return

3

*

x

**

2

-

6

*

x

+

2def

fitness_function(x):

return

-objective_function(x)

#

因为是求最小值，所以取负值作为适应度步骤

2：设置遗传算法参数POPULATION_SIZE

=

50

#

种群大小GENE_LENGTH

=

8

#

基因长度，用于编码

x

的值CROSSOVER_RATE

=

0.8

#

交叉概率MUTATION_RATE

=

0.05

#

变异概率NUM_GENERATIONS

=

100

#

迭代次数24（4）遗传算法的应用案例（2/7）步骤

4：解码个体基因为实数def

decode_individual(individual):

decimal_value

=

0

for

bit

in

individual:

decimal_value

=

(decimal_value

<<

1)

|

bit

min_value

=

-5

#

函数定义域下限

max_value

=

5

#

函数定义域上限

scaled_value

=

min_value

+

decimal_value

*

(max_value

-

min_value)

/

(2

**

GENE_LENGTH

-

1)

return

scaled_value

步骤

3：初始化种群def

initialize_population():population

=

[]

for

_

in

range(POPULATION_SIZE):

individual

=

[random.randint(0,

1)

for

_

in

range(GENE_LENGTH)]

population.append(individual)

return

population25（4）遗传算法的应用案例（3/7）步骤

5：选择操作def

selection(population):

fitness_values

=

[fitness_function(decode_individual(individual))

for

individual

in

population]

total_fitness

=

sum(fitness_values)

probabilities

=

[fitness

/

total_fitness

for

fitness

in

fitness_values]

selected_indices

=

random.choices(range(POPULATION_SIZE),

weights=probabilities,

k=POPULATION_SIZE)

selected_population

=

[population[i]

for

i

in

selected_indices]

return

selected_population

根据个体的适应度计算选择概率，然后通过随机选择生成新的种群。适应度高的个体有更大的概率被选中。

26（4）遗传算法的应用案例（4/7）步骤

6：交叉操作

def

crossover(parent1,

parent2):

if

random.random()

<

CROSSOVER_RATE:

crossover_point

=

random.randint(1,

GENE_LENGTH

-

1)

child1

=

parent1[:crossover_point]

+

parent2[crossover_point:]

child2

=

parent2[:crossover_point]

+

parent1[crossover_point:]

return

child1,

child2

else:

return

parent1,

parent227（4）遗传算法的应用案例（5/7）步骤

7：变异操作

：以较小的概率对个体的基因进行变异。def

mutation(individual):

for

i

in

range(GENE_LENGTH):

if

random.random()

<

MUTATION_RATE:

individual[i]

=

1

-

individual[i]

return

individual28（4）遗传算法的应用案例（6/7）步骤

8：运行遗传算法def

genetic_algorithm():

population

=

initialize_population()

for

generation

in

range(NUM_GENERATIONS):

selected_population

=

selection(population)

new_population

=

[]

for

i

in

range(0,

POPULATION_SIZE,

2):

parent1

=

selected_population[i]

parent2

=

selected_population[i

+

1]

child1,

child2

=

crossover(parent1,

parent2)

child1

=

mutation(child1)

child2

=

mutation(child2)

new_population.append(child1)

new_population.append(child2)

population

=

new_population

best_individual

=

max(population,

key=lambda

x:

fitness_function(decode_individual(x)))

best_value

=

decode_individual(best_individual)步骤9：输出结果

print("Best

solution:

x

=",

best_value,

"Function

value:",

objective_function(best_value))genetic_algorithm()29（4）遗传算法的应用案例（7/7）全局搜索能力隐含的并行性

鲁棒性易实现自适应性（5）遗传算法的特点与改进（1/3）30遗传算法的特点参数选择的敏感性可能过早收敛计算复杂度和时间成本较高局部搜索能力较弱适应度评估的依赖性遗传算法的局限性31（5）遗传算法的特点与改进（2/3）自适应遗传算法

在算法的不同阶段，根据种群特性和个体适应度等因素动态调整Pc和Pm的值。双种群遗传算法将种群分为两个子群体。各自采用不同的进化策略或参数。双倍体遗传算法自然界中大多数生物都采用双倍体遗传，每个基因型由显性和隐性一对染色体组成。双倍体遗传算法中的每个个体具有两条染色体，即双倍体结构。双倍体遗传算法采用显性遗传。遗传算法的改进32（5）遗传算法的特点与改进(3/3)

第五章智能优化算法《人工智能》本章内容5.1优化算法5.2遗传算法5.3群智能算法5.4粒子群算法5.5蚁群算法33

5.3群智能算法《人工智能》群智能算法背景常见的群智能算法34第5章智能优化算法学习要点（1）群智能算法产生的背景群智能算法一类源于对自然界中生物群体智能行为的观察

和模拟的启发式算法。自然界中动物的群体行为蚂蚁搬家鸟群觅食蜜蜂筑巢……群体智能由简单个体组成的群落与环境以及个体之间的互动行为。35（2）常见的群智能算法36粒子群优化蚁群算法人工蜂群算法人工鱼群算法布谷鸟搜索算法狼群算法萤火虫算法……

第五章智能优化算法《人工智能》本章内容5.1优化算法5.2遗传算法5.3群智能算法5.4粒子群算法5.5蚁群算法37

5.4粒子群优化算法《人工智能》粒子群优化算法思想粒子群优化算法流程和实现过程粒子群算法的应用案例粒子群算法的改进38第5章智能优化算法学习要点（1）粒子群优化算法思想算法思想：模拟鸟群觅食行为，将每个潜在的解类比为搜索空间中的一只鸟，称之为“粒子”，每个粒子都有自己的位置和速度，位置代表问题的一个可能解。每个粒子设定一个初始位置和速度向量，根据目标函数计算当前位置的适应度值，每个粒子根据自身的历史最优位置和整个粒子群的全局最优位置不断调整自己的速度和位置，逐渐向最优解靠近。39否是

开始

初始化粒子种群

设置算法参数

评估粒子适应度

获取个体历史最优位置

获取种群最优位置

更新每个粒子的速度和位置终止条件输出当前全局最优解算法结束（2）粒子群优化算法基本流程Step1：初始化粒子群并设置算法相关参数；Step2：计算每个粒子位置的适应度值，更新自身的的历史最优位置Pbest；Step3：根据各个粒子的历史最优位置Pi，更新群体历史最优位置GbestStep4：更新每个粒子的速度，并将其限制在vmax内，更新当前的位置。Step5：判断是否满足终止条件。若满足，输出当前历史最优位置，否则返回Step2。40

（3）粒子群算法实现过程（1/3）41适应度评估

根据问题的目标函数计算每个粒子的适应度值。更新个体最优解和全局最优解

个体最优解：每个粒子将其当前适应度值与自身历史最优适应度值进行比较，如果当前的适应度值更优，则更新个体最优位置为当前位置。

全局最优解：在所有粒子的个体最优位置中找出适应度值最好的位置作为全局最优位置。

（3）粒子群算法实现过程（2/3）42

（3）粒子群算法实现过程（3/3）43

（4）粒子群算法的应用案例（1/4）定义目标函数import

randomdef

objective_function(x):return

x

**

2

-

5

*

x

+

6设置算法相关参数num_particles

=

50

#

粒子数量max_iterations

=

100

#

最大迭代次数w

=

0.5

#

惯性权重c

1=

1.5

#

学习因子1c

2=

1.5

#

学习因子244

初始化粒子群#

初始化粒子的位置和速度particles_position

=

[random.uniform(-10,

10)

for

_

in

range(num_particles)]particles_velocity

=

[random.uniform(-1,

1)

for

_

in

range(num_particles)]#

初始化个体最优位置、全局最优位置、全局最优适应度personal_best_position

=

particles_position.copy()global_best_position

=

particles_position[0]global_best_fitness

=

objective_function(global_best_position)45（4）粒子群算法的应用案例（2/4）

更新粒子速度和位置

for

iteration

in

range(max_iterations):

for

i

in

range(num_particles):

#

更新粒子的速度

r1

=

random.random()

r2

=

random.random()

particles_velocity[i]

=

(w

*

particles_velocity[i]

+

c1

*

r1

*

(personal_best_position[i]

–

particles_position[i])

+c2

*

r2

*

(global_best_position

-

particles_position[i]))

#

更新粒子的位置

particles_position[i]

+=

particles_velocity[i]

46（4）粒子群算法的应用案例（3/4）

计算机适应度并更新个体和全局最优位置

#

计算当前粒子的适应度

current_fitness

=

objective_function(particles_position[i])

#

更新个体最优位置

if

current_fitness

<

objective_function(personal_best_position[i]):

personal_best_position[i]

=

particles_position[i]

#

更新全局最优位置

if

current_fitness

<

global_best_fitness:

global_best_fitness

=

current_fitness

global_best_position

=

particles_position[i]输出全局最优解print("全局最优解：",

global_best_position)

print("全局最优适应度值：",

global_best_fitness)47（4）粒子群算法的应用案例（4/4）（5）粒子群算法的改进

粒子群优化算法在解决需要高精度的问题可能无法取得令人满意的结果。同时，算法具有较强的参数依赖性。

惯性权重的动态调整

算法运行过程中动态调整惯性权重。

学习因子的自适应调整根据迭代次数或粒子的性能进行自适应调整。

引入变异操作对粒子的位置或速度进行随机变异，以增加种群的多样性。

多种群策略将粒子群划分为多个子群，每个子群独立进化。48

第五章智能优化算法《人工智能》本章内容5.1优化算法5.2遗传算法5.3群智能算法5.4粒子群算法5.5蚁群算法49

5.5蚁群算法《人工智能》蚁群算法的基本思想蚁群算法的流程和实现过程蚁群算法的应用实例蚁群算法的改进50第5章智能优化算法学习要点（1）蚁群算法的提出

蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的概率型算法，由M.Dorigo等人受自然界蚂蚁觅食行为的启发于1992年提出，最早被应用于解旅行商问题（Traveling

Salesman

Problem，TSP）。51（2）蚁群算法基本思想（1/2）

蚂蚁之间通过它们分泌的信息素进行交流。当蚂蚁随机移动时能检测到其他同伴所释放的信息素，并沿着该路线移动，同时又释放自身的信息素，从而增强了该路径的信息素数量。随着时间推移，距离较近的道路信息素浓度越来越大，越来越多的蚂蚁选择这条道路。在这种反馈机制下，“最短”的道路最终会被找到，即最佳路径。52蚁群算法与蚂蚁觅食类比蚁群觅食蚁群算法蚂蚁从蚁巢到食物的行走路径可行解蚁巢到食物的最短路径最优解蚁巢到食物的所有路径解空间某路径上信息素浓度信息素矩阵根据信息素选择路径根据概率路径选择53（2）蚁群算法基本思想（2/2）（3）蚁群算法的流程与实现过程（1/2）Step1:

初始化设置参数：蚂蚁数量（m）；信息素挥发系数（ρ）；信息素重要度（α）及启发式信息重要度（β）；最大迭代次数；初始化地图：构建问题的地图表示；初始化信息素矩阵：设置所有