遗传算法(GA)概述 |
您所在的位置:网站首页 › 遗传算法的5个基本要素是什么 › 遗传算法(GA)概述 |
注释:是学习之余整理的资料,如有不足的地方还请指教,十分感谢! 目录 1、遗传算法的基本思想 2、遗传算法的步骤 (1)初始种群的产生(编码) (2)适应度函数的确定 (3)遗传算子(选择、交叉、变异) 3、遗传算法的适应性 4、遗传算法的优缺点 (1)遗传算法的优点: (2)遗传算法的缺点: 5、算法流程图 遗传算法概述 遗传算法(Genetic Algorithm)是一种进化算法,原理是仿效生物界的“物竞天择,适者生存”的演化法则。最早由美国Michigan大学的J.Holland教授1967年提出。遗传算法主要特点就是概率化的寻优方法,可自动获取和指导优化。简单遗传算法(Simple Genetic Algorithms,GA)又称简单遗传算法或标准遗传算法),是一种最基本的遗传算法,其遗传进化操作过程简单,容易理解,是其它一些遗传算法的雏形和基础。 搜索机制:遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象,在每次迭代中都保留一组候选解,并按某种指标从解群中选取较优的个体,利用遗传算子(选择、交叉和变异)对这些个体进行组合,产生新一代的候选解群,重复此过程,直到满足某种收敛指标为止。 遗传算法的原理: 1、遗传算法的基本思想遗传算法是受生物进化过程中“优胜劣汰”的自然选择机制和遗传信息传递规律的启发,所提出的一种智能优化算法。通过程序迭代模拟自然界生物进化的过程,把要解决的问题看作环境,在一些可能的解组成的种群中,通过不断进化寻求最优解。遗传算法通过初始化种群、复制操作、交叉操作、变异操作几个步骤,模拟自然界生物进化过程中的繁殖行为与竞争行为,衍生出下一代的个体,再根据适应度的大小进行个体的优胜劣汰,提高新一代群体的质量,在经过反复多次迭代,逐步逼近复杂工程技术问题的最优解。 遗传算法的搜索策略不是盲目搜索,也不是穷举搜索,而是以目标函数为指导的搜索方式。遗传算法一般采用天然的并行结构,且借助交叉和变异产生新个体,不断产生新个体,扩大搜索范围,因此它不易于陷入局部最优点,并能以较大的概率找到全局最优点。 2、遗传算法的步骤 (1)初始种群的产生(编码)首先要初始种群,也就是进化的第一代,种群规模要根据问题的规模而定。初始种群的选择会影响算法的收敛速度和结果,多样性较好的种群有利于算法的全局搜索。初始化种群的方式一般为随机产生,产生了初始种群后要进行编码,也可以直接在产生种群的时候就是用编码的方式产生的。基因的编码方式有很多,这也取决于要解决的问题本身。 常见的编码方式有: 1、二进制编码 基因用0或1表示(常用于解决01背包问题)。 如:基因A:00100011010 (代表一个个体的染色体) 优点:编码、解码操作简单易行;交叉、变异操作便于实现;符合最小字符集编码原则;便于利用模式定理对算法进行理论分析。 缺点:存在着连续函数离散化时的映射误差。不能直接反映出所求问题的本身结构特征,不便于开发针对问题的专门知识的遗传运算算子,很难满足积木块编码原则。 2、格雷码编码 连续的两个整数所对应的编码之间仅仅只有一个码位是不同的,其余码位都相同。 3、实数(浮点数)编码 个体的每个基因值用某一范围内的某个浮点数来表示,个体的编码长度等于其决策变量的位数。 4、符号编码 5、互换编码 用于解决排序问题,如旅行商问题和调度问题。 如旅行商问题中,一串基因编码用来表示遍历的城市顺序,如:234517986,表示九个城市中,先经过城市2,再经过城市3,依此类推。 6、树形编码 用于遗传规划中的演化编程或者表示。 如,问题:给定了很多组输入和输出。请你为这些输入输出选择一个函数,使得这个函数把每个输入尽可能近地映射为输出。编码方法:基因就是树形结构中的一些函数。 7、值编码 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |