AI基础 L9 Local Search II 局部搜索
Local Beam search
对于当前的所有k个状态，生成它们的所有可能后继状态。
检查生成的后继状态中是否有任何状态是解决方案。
如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。
当达到预设的迭代次数或满足某个终止条件时，算法停止。
— Choose k successors randomly, biased towards good ones
— Close analogy to natural selection
Genetic Algorithms
遗传算法的一些关键特征：
-
随机局部光束搜索：
- 定义：遗传算法通过随机局部光束搜索来生成解决方案。
- 作用：这有助于算法探索状态空间，并找到更好的解决方案。
-
从状态对生成后继状态：
- 定义：遗传算法通过交叉操作，从两个父代状态生成新的子代状态。
- 作用：这有助于算法在种群中传播有用的信息，并产生新的解决方案。
-
状态表示：
- 定义：每个状态应该是一个字符串，其中字符串的子串应该有意义。
- 作用：这有助于算法有效地表示和操作解决方案。
-
应用示例：
- 定义：n-皇后问题是一个典型的遗传算法应用示例。
- 作用：在这个问题中，每个状态用一个字符串表示，其中第i个字符表示第i个皇后所在的行。
• Population of individuals 一组可能的解决方案
• Mutation — local search N (x) 变异是指对种群中的个体进行小的随机改变。
• cross over — population holds information 交叉是指将两个父代个体的部分基因组合在一起，形成新的子代个体。
• generations — iterations of improvement 代是指遗传算法中迭代的过程。
GA Terminology
• Gene - characters in the string representing the state
• Chromosome - blocks of genes in the string in a state
• Population - neighbours in the search
• Selection, crossover, mutation
1-point crossover
随机选择切点 交换切割后的尾部
Create children by exchanging tails (typically with 0.6 < PC < 0.9)
n-point crossover
随机选择n个切点 交替交换切割后的尾部
• Glue parts, alternating between parents
• Generalisation of 1 point (still some positional bias)
指的是多点交叉相对于单点交叉的推广。虽然多点交叉通过选择多个交叉点来减少位置偏见，但仍然存在一定的位置偏见，因为交叉点的位置会影响子代个体的基因组合。这意味着，尽管多点交叉减少了位置偏见，但仍然不能完全消除位置对交叉结果的影响。
uninform crossover
• Assign ‘heads‘ to one parent, ‘tails‘ to the other
• Flip a coin for each gene of the first child
• Make an inverse copy of the gene for the second child
• Inheritance is independent of position 遗传与位置无关
按照50%概率为每个个体分配切割后的头部和尾部 切割成最小不可分单位
mutation
• Alter each gene independently with a probability Pm
• Pm is called the mutation rate
• Typically between 1/pop_size and 1/chromosome_length
每一个最小不可分部分按突变率发生变化
Selection
• Main idea: better individuals get higher chance
• Chances proportional to fitness
• Implementation: roulette wheel technique
— Assign to each individual a part of the roulette wheel
— Spin the wheel n times to select n individuals
加权选择
Crossover VS. mutation
• Exploration: Discovering promising areas in the search space, i.e. gaining information
on the problem 通常用于探索新的解决方案
• Exploitation: Optimising within a promising area, i.e. using information 用于在当前解决方案的基础上进行微调
• There is co-operation and competition between them
— Crossover is explorative, it makes a big jump to an area somewhere “in between“ two
(parent) areas
— Mutation is exploitative, it creates random small diversions, thereby staying near (in the
area of) the parent
• Only crossover can combine information from two parents crossover合并父级信息
• Only mutation can introduce new information (alleles) mutation 产生新信息
• Crossover does not change the allele frequencies of the population crossover不会改变信息频率
• To hit the optimum you often need a ‘lucky‘ mutation mutation达到最佳需要运气
Continuous state spaces
适用于那些需要找到全局最优解或近似最优解的问题。它的主要优点是能够找到全局最优解或近似最优解，但它的主要缺点是可能需要大量的迭代次数。