遗传算法原理与应用

遗传算法原理与应用

遗传算法原理与应用唐 慧 丰

2006 年 5 月

遗传算法原理与应用

报告提纲一、遗传算法概述

二、遗传算法原理 三、遗传算法的应用

遗传算法原理与应用

一、遗传算法概述1、智能优化算法 2、基本遗传算法 3、遗传算法的特点

遗传算法原理与应用

1、智能优化算法智能优化算法又称为现代启发式算 法，是一种具有全局优化性能、通用性 强、且适合于并行处理的算法。这种算 法一般具有严密的理论依据，而不是单 纯凭借专家经验，理论上可以在一定的 时间内找到最优解或近似最优解。

遗传算法原理与应用

常用的智能优化算法(1)遗传算法 (Genetic Algorithm, 简称GA)

(2)模拟退火算法(Simulated Annealing, 简称SA)

(3)禁忌搜索算法(Tabu Search, 简称TS)

……

遗传算法原理与应用

智能优化算法的特点它们的共同特点：都是从任一解出发， 按照某种机制，以一定的概率在整个求解 空间中探索最优解。由于它们可以把搜索 空间扩展到整个问题空间，因而具有全局 优化性能。

遗传算法原理与应用

遗传算法起源遗传算法是由美国的J. Holland教授于 1975年在他的专著《自然界和人工系统的 适应性》中首先提出的，它是一类借鉴生 物界自然选择和自然遗传机制的随机化搜 索算法 。

遗传算法原理与应用

遗传算法的搜索机制遗传算法模拟自然选择和自然遗传过 程中发生的繁殖、交叉和基因突变现象，在

每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子

(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到

满足某种收敛指标为止。

遗传算法原理与应用

2、基本遗传算法基本遗传算法(Simple Genetic Algorithms,简称SGA,又称简单遗传算法 或标准遗传算法),是由Goldberg总结出 的一种最基本的遗传算法，其遗传进化操 作过程简单，容易理解，是其它一些遗传 算法的雏形和基础。

遗传算法原理与应用

基本遗传算法的组成(1)编码(产生初始种群) (2)适应度函数 (3)遗传算子(选择、交叉、变异) (4)运行参数

遗传算法原理与应用

编码GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的

串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。

SGA使用二进制串进行编码。

遗传算法原理与应用

函数优化示例求下列一元函数的最大值：

f ( x) x sin(10 x) 2.0x∈[-1,2] ,求解结果精确到6位小数。

遗传算法原理与应用

SGA对于本例的编码由于区间长度为3,求解结果精确到6位小 数，因此可将自变量定义区间划分为3×106等 份。又因为221 < 3×106 < 222 ,所以本例的二 进制编码长度至少需要22位，本例的编码过程 实质上是将区间[-1,2]内对应的实数值转化为

一个二进制串(b21b20…b0)。

遗传算法原理与应用

几个术语

个体(染色体)

基因型：1000101110110101000111基因

解码

编码

表现型：0.637197

遗传算法原理与应用

初始种群SGA采用随机方法生成若干个 个体的集合，该集合称为初始种群。 初始种群中个体的数量称为种群规 模。

遗传算法原理与应用

适应度函数遗传算法对一个个体(解)的好坏 用适应度函数值来评价，适应度函数值越 大，解的质量越好。适应度函数是遗传算 法进化过程的驱动力，也是进行自然选择 的唯一标准，它的设计应结合求解问题本

身的要求而定。

遗传算法原理与应用

选择算子遗传算法使用选择运算来实现对群体中的个 体进行优胜劣汰操作：适应度高的个体被遗传到

下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就 是按某种方法从父代群体中选取一些个体，遗传 到下一代群体。SGA中选择算子采用轮盘赌选择 方法。

遗传算法原理与应用

轮盘赌选择方法轮盘赌选择又称比例选择算子，它的基本思想 是：各个个体被选中的概率与其适应度函数值大小 成正比。设群体大小为n ,个体i 的适应度为 Fi,则 个体i 被选中遗传到下一代群体的概率为：

P Fi / Fi ii 1

n

遗传算法原理与应用

轮盘赌选择方法的实现步骤(1) 计算群体中所有个体的适应度函数值(需要 解码);

(2) 利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；

(3) 采用模拟赌盘操作(即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配) 来确定各个个体是否遗传到下一代群体中。

遗传算法原理与应用

交叉算子所谓交叉运算，是指对两个相互配对的染色

体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算

法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。 SGA中交叉算子采用单点交叉算子。

遗传算法原理与应用

单点交叉运算交叉前： 00000|01110000000010000 11100|00000111111000101 交叉后： 00000|00000111111000101 11100|01110000000010000 交叉点

本文来源：https://www.bwwdw.com/article/vyc1.html