AI基础 L9 Local Search II 局部搜索

2024-09-09 08:04

本文主要是介绍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

遗传算法的一些关键特征:

  1. 随机局部光束搜索

    • 定义:遗传算法通过随机局部光束搜索来生成解决方案。
    • 作用:这有助于算法探索状态空间,并找到更好的解决方案。
  2. 从状态对生成后继状态

    • 定义:遗传算法通过交叉操作,从两个父代状态生成新的子代状态。
    • 作用:这有助于算法在种群中传播有用的信息,并产生新的解决方案。
  3. 状态表示

    • 定义:每个状态应该是一个字符串,其中字符串的子串应该有意义。
    • 作用:这有助于算法有效地表示和操作解决方案。
  4. 应用示例

    • 定义: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

适用于那些需要找到全局最优解或近似最优解的问题。它的主要优点是能够找到全局最优解或近似最优解,但它的主要缺点是可能需要大量的迭代次数。

这篇关于AI基础 L9 Local Search II 局部搜索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1150605

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

AI绘图怎么变现?想做点副业的小白必看!

在科技飞速发展的今天,AI绘图作为一种新兴技术,不仅改变了艺术创作的方式,也为创作者提供了多种变现途径。本文将详细探讨几种常见的AI绘图变现方式,帮助创作者更好地利用这一技术实现经济收益。 更多实操教程和AI绘画工具,可以扫描下方,免费获取 定制服务:个性化的创意商机 个性化定制 AI绘图技术能够根据用户需求生成个性化的头像、壁纸、插画等作品。例如,姓氏头像在电商平台上非常受欢迎,

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

Andrej Karpathy最新采访:认知核心模型10亿参数就够了,AI会打破教育不公的僵局

夕小瑶科技说 原创  作者 | 海野 AI圈子的红人,AI大神Andrej Karpathy,曾是OpenAI联合创始人之一,特斯拉AI总监。上一次的动态是官宣创办一家名为 Eureka Labs 的人工智能+教育公司 ,宣布将长期致力于AI原生教育。 近日,Andrej Karpathy接受了No Priors(投资博客)的采访,与硅谷知名投资人 Sara Guo 和 Elad G

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

AI hospital 论文Idea

一、Benchmarking Large Language Models on Communicative Medical Coaching: A Dataset and a Novel System论文地址含代码 大多数现有模型和工具主要迎合以患者为中心的服务。这项工作深入探讨了LLMs在提高医疗专业人员的沟通能力。目标是构建一个模拟实践环境,人类医生(即医学学习者)可以在其中与患者代理进行医学

AI行业应用(不定期更新)

ChatPDF 可以让你上传一个 PDF 文件,然后针对这个 PDF 进行小结和提问。你可以把各种各样你要研究的分析报告交给它,快速获取到想要知道的信息。https://www.chatpdf.com/