轮盘赌随机选择算法

2023-11-09 11:20
文章标签 算法 选择 随机 轮盘

本文主要是介绍轮盘赌随机选择算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文转载自 https://my.oschina.net/u/1412321/blog/192454

一、遗传算法的应用

函数优化(遗传算法的经典应用领域);
组合优化(实践证明,遗传算法对于组合优化中的NP完全问题,如0-1背包问题,TSP等,非常有效);
自动控制;

机器人智能控制;

组合图像处理和模式识别;

人工生命;

遗传程序设计;



二、遗传学基本概念与术语

基因型(genotype):性状染色体的内部表现;

表现型(phenotype):染色体决定性状的外部表现,或者说,根据基因型形成的个体;

进化(evolution):逐渐适应生存环境,品质不断得到改良。生物的进化是以种群的形式进行的。

适应度(fitness):度量某个物种对于生存环境的适应程度。

选择(selection):以一定的概率从种群中选择若干个个体。一般,选择过程是一种基于适应度的优胜劣汰的过程。

复制(reproduction):细胞分裂时,遗传物质DNA通过复制而转移到新产生的细胞中,新细胞就继承了旧细胞的基因。

交叉(crossover):两个染色体的某一相同位置处DNA被切断,前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交;

变异(mutation):复制时可能(很小的概率)产生某些复制差错,变异产生新的染色体,表现出新的性状。

编码(coding):DNA中遗传信息在一个长链上按一定的模式排列。

          遗传编码可看作从表现型到基因型的映射。

解码(decoding):基因型到表现型的映射。

个体(individual):指染色体带有特征的实体;
种群(population):个体的集合,该集合内个体数称为种群的大小;



三、遗传算法的基本思路


在开始介绍一个实例之前,有必要了解一下轮盘赌选择法,因为基本遗传算法就是用的这个选择策略。

轮盘赌选择
又称比例选择方法.其基本思想是:各个个体被选中的概率与其适应度大小成正比.

具体操作如下:
(1)计算出群体中每个个体的适应度f(i=1,2,…,M),M为群体大小;
(2)计算出每个个体被遗传到下一代群体中的概率;

       

(3)计算出每个个体的累积概率;

       (q[i]称为染色体x[i] (i=1, 2, …, n)的积累概率)

     

(4)在[0,1]区间内产生一个均匀分布的伪随机数r;
(5)若r<q[1],则选择个体1,否则,选择个体k,使得:q[k-1]<r≤q[k] 成立;
(6)重复(4)、(5)共M次



四、一个简单的实例

1. 产生初始种群

s1= 13 (01101)

s2= 24 (11000) 

s3= 8   (01000)

s4= 19 (10011)


2. 计算适应度

假定适应度为f(s)=s^2 ,则

f (s1) = f(13) = 13^2 = 169

f (s2) = f(24) = 24^2 = 576

f (s3) = f(8) = 8^2 = 64

f (s4) = f(19) = 19^2 = 361

3. 选择

染色体的选择概率为:

染色体的累计概率为:

根据上面的式子,可得到:

例如设从区间[0, 1]中产生4个随机数: 

   r1 = 0.450126,    r2 = 0.110347 

   r3 = 0.572496,    r4 = 0.98503 

4. 交叉

基本遗传算法(SGA)中交叉算子采用单点交叉算子。

单点交叉运算

5. 变异

6. 至下一代,适应度计算→选择→交叉→变异,直至满足终止条件


五、遗传算法应用

这里使用具体的应用例子:函数优化

  • 问题的提出

     一元函数求最大值:

用微分法求取f(x)的最大值:

可求得最大值点:f(1.85)=3.85

0. 编码

     表现型:x
     基因型:二进制编码(串长取决于求解精度)
     串长与精度之间的关系:
     若要求求解精度到6位小数,区间长度为2-(-1)=3,即需将区间分为3/0.000001=3&times;106等份。
          所以编码的二进制串长应为22位。

1. 产生初始种群

     产生的方式:随机
     产生的结果:长度为22的二进制串
     产生的数量:种群的大小(规模),如30,50,…
          1111010011100001011000
          1100110011101010101110
          1010100011110010000100
          1011110010011100111001  
          0001100101001100000011    
          0000011010010000000000

2. 计算适应度

     不同的问题有不同的适应度计算方法
     本例:直接用目标函数作为适应度函数
     ①将某个体转化为[-1,2]区间的实数:
        s=<1000101110110101000111> → x=0.637197
     ②计算x的函数值(适应度):
        f(x)=xsin(10πx)+2.0=2.586345

     (0000000000000000000000)→-1
     (1111111111111111111111)→2

     上面的①其实就是二进制与十进制之间的转换:
     第一步,将一个二进制串(b21b20…b0)转化为10进制数:
        

      第二步,x’对应的区间[-1,2]内的实数:

     

3. 遗传操作

    选择:轮盘赌选择法;
    交叉:单点交叉;
    变异:小概率变异

  • 模拟结果

     设置的参数:
     种群大小50;交叉概率0.75;变异概率0.05;最大代数200。
     得到的最佳个体:
     smax=<1111001100111011111100>;
     xmax=1.8506;
     f(xmax)=3.8503;

  • 运行结果



六、总结

编码原则
完备性(completeness):问题空间的所有解都能表示为所设计的基因型;
健全性(soundness):任何一个基因型都对应于一个可能解;
非冗余性(non-redundancy):问题空间和表达空间一一对应。

适应度函数的重要性
     适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。
     一般而言,适应度函数是由目标函数变换而成的,对目标函数值域的某种映射变换称为适应度的尺度变换(fitness scaling)。

适应度函数设计不当有可能出现欺骗问题:
(1)进化初期,个别超常个体控制选择过程;
(2)进化末期,个体差异太小导致陷入局部极值。

欺骗问题举例:

可以想象一下,假设地球像类似灾难电影《后天》一样,出现有毒的雾霾,喜马拉雅山脉下有100只猴子(种群大小),只有爬上珠穆朗玛峰顶端的猴子才能生存下来,

因为喜马拉雅山脉有很多山峰,我们以高度作为适应度,case(1):如果不在珠峰的猴子若比在珠峰半山腰的猴子要高,因为种群大小不变,在珠峰的猴子可能就会被淘汰;

case(2):100只猴子都不在珠峰;

1. 选择的作用:优胜劣汰,适者生存;

2. 交叉的作用:保证种群的稳定性,朝着最优解的方向进化;

3. 变异的作用:保证种群的多样性,避免交叉可能产生的局部收敛;

下图很好地表现了遗传算法的精髓。

遗传算法的特点

  • 自组织、自适应和自学习性
    在编码方案、适应度函数及遗传算子确定后,算法将利用进化过程中获得的信息自行组织搜索。

  • 本质并行性
    内在并行性与内含并行性

  • 不需求导
    只需目标函数和适应度函数

  • 概率转换规则
    强调概率转换规则,而不是确定的转换规则


七、补充

因为遗传算法的每个操作对不同的应用选择的策略各有优劣,所以具体情况,具体分析,在此附上:

1. 选择

适应度计算:
按比例的适应度函数(proportional fitness assignment)
基于排序的适应度计算(Rank-based fitness assignment)

选择算法:
轮盘赌选择(roulette wheel selection)

随机遍历抽样(stochastic universal selection)
局部选择(local selection)
截断选择(truncation selection)
锦标赛选择(tournament selection)

2. 交叉

因为编码分二进制和浮点数编码,所以交叉和变异都有两类;

实值重组(real valued recombination):

离散重组(discrete recombination)

中间重组(intermediate recombination)

线性重组(linear recombination)

扩展线性重组(extended linear recombination)

二进制交叉(binary valued crossover):

单点交叉(single-point crossover)

多点交叉(multiple-point crossover)

均匀交叉(uniform crossover)

洗牌交叉(shuffle crossover)

缩小代理交叉(crossover with reduced surrogate)

3. 变异

实值变异
二进制变异

另外,遗传算法背后的理论支撑——模式定理,可以在对遗传算法有深入研究和优化的时候再详看。

这篇关于轮盘赌随机选择算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、

前端知识点之Javascript选择输入框confirm用法

《前端知识点之Javascript选择输入框confirm用法》:本文主要介绍JavaScript中的confirm方法的基本用法、功能特点、注意事项及常见用途,文中通过代码介绍的非常详细,对大家... 目录1. 基本用法2. 功能特点①阻塞行为:confirm 对话框会阻塞脚本的执行,直到用户作出选择。②

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Python 中 requests 与 aiohttp 在实际项目中的选择策略详解

《Python中requests与aiohttp在实际项目中的选择策略详解》本文主要介绍了Python爬虫开发中常用的两个库requests和aiohttp的使用方法及其区别,通过实际项目案... 目录一、requests 库二、aiohttp 库三、requests 和 aiohttp 的比较四、requ