遗传算法Github初学

遗传算法的理论是根据达尔文进化论而设计出来的算法:人类是朝着好的方向(最优解)进化,进化过程中,会自动选择优良基因,淘汰劣等基因

遗传算法(genetic algorithm——GA)是计算数学中用于解决最佳化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择、杂交等。

搜索算法的共同特征为:

  1. 首先组成一组候选解
  2. 依据某些适应性条件测算这些候选解的适应度(指个体在种群生存的优势程度度量)
  3. 根据适应度保留某些候选解,放弃其他候选解
  4. 对保留的候选解进行某些操作,生成新的候选解

遗传算法的一般步骤:

  1. my_fitness函数评估每条染色体所对应个体的适应度
  2. 升序排列适应度评估值,选出前parent_number个 个体作为待选parent种群(适应度函数的值越小越好)
  3. 待选parent种群中随机选择2个个体作为父方和母方
  4. 抽取父母双方的染色体,进行交叉,产生2个子代。(交叉概率)
  5. 对子代(parent + 生成的 child)的染色体进行变异(变异概率)
  6. 重复3,4,5步骤,直到新种群(parent_number + child_number)的产生

循环以上步骤直至找到满意的解

交叉概率:两个个体进行交配的概率。例如,交配概率为0.8,则80%的“夫妻”会生育后代。

变异概率:所有的基因中发生变异的占总体的比例。

适应度函数

        适应度函数由解决的问题决定。举一个平方和的例子。

求函数的最小值,其中每个变量的取值区间都是[-1, 1]。问题的最优解:每个x_i 都等于0。

function y = my_fitness(population)
% population是随机数[0,1]矩阵,下面的操作改变范围为[-1,1]
population = 2 * (population - 0.5); 
y = sum(population.^2, 2); % 行的平方和

 适应度函数 my_fitness 的目的是计算一个给定种群(population)中每个个体(individual)的适应度度值,适应度函数是根据个体的特性(在这个案例中是个体的各个维度值)来评估个体在问题域中表现的好坏。

改变范围是为了让个体的特征值落在特定的区间内,这样可以使得不同个体之间比较更加公平,并且有助于算法收敛。行的平方和即每个个体的特征值平方和,适应度值越小说明这个个体越接近于问题的解。

GA函数
function [best_fitness, elite, generation, last_generation] = my_ga( ...number_of_variables, ...    % 求解问题的参数个数 也就是每个个体有多少个特征值fitness_function, ...       % 自定义适应度函数名population_size, ...        % 种群规模(每一代个体数目)parent_number, ...          % 每一代中保持不变的数目(除了变异)mutation_rate, ...          % 变异概率maximal_generation, ...     % 最大演化代数 即算法运行的最大迭代次数minimal_cost ...            % 最小目标值(函数值越小,则适应度越高)% 当某一代中的最佳适应度值小于或等于这个值时,算法提前终止 
)% 累加概率
% 假设 parent_number = 10
% 分子 parent_number:-1:1 用于生成一个数列
% 分母 sum(parent_number:-1:1) 是一个求和结果(一个数)
%
% 分子 10     9     8     7     6     5     4     3     2     1
% 分母 55
% 相除 0.1818    0.1636    0.1455    0.1273    0.1091    0.0909    0.0727    0.0545    0.0364    0.0182
% 累加 0.1818    0.3455    0.4909    0.6182    0.7273    0.8182    0.8909    0.9455    0.9818    1.0000
%
% 运算结果可以看出
% 累加概率函数是一个从0到1增长得越来越慢的函数
% 因为后面加的概率越来越小(数列是降虚排列的)
cumulative_probabilities = cumsum((parent_number:-1:1) / sum(parent_number:-1:1)); % 1个长度为parent_number的数列% 最佳适应度
% 每一代的最佳适应度都先初始化为1
best_fitness = ones(maximal_generation, 1);% 精英
% 每一代的精英的参数值都先初始化为0
elite = zeros(maximal_generation, number_of_variables);% 子女数量
% 种群数量 - 父母数量(父母即每一代中不发生改变的个体)
child_number = population_size - parent_number; % 每一代子女的数目% 初始化种群
% population_size 对应矩阵的行,每一行表示1个个体,行数=个体数(种群数量)
% number_of_variables 对应矩阵的列,列数=参数个数(个体特征由这些参数表示)
population = rand(population_size, number_of_variables);last_generation = 0; % 记录跳出循环时的代数% 后面的代码都在for循环中
for generation = 1 : maximal_generation % 演化循环开始% feval把数据带入到一个定义好的函数句柄中计算% 把population矩阵带入fitness_function函数计算cost = feval(fitness_function, population); % 计算所有个体的适应度(population_size*1的矩阵)% index记录排序后每个值原来的行数[cost, index] = sort(cost); % 将适应度函数值从小到大排序% index(1:parent_number) % 前parent_number个cost较小的个体在种群population中的行数% 选出这部分(parent_number个)个体作为父母,其实parent_number对应交叉概率population = population(index(1:parent_number), :); % 先保留一部分较优的个体% 可以看出population矩阵是不断变化的% cost在经过前面的sort排序后,矩阵已经改变为升序的% cost(1)即为本代的最佳适应度best_fitness(generation) = cost(1); % 记录本代的最佳适应度% population矩阵第一行为本代的精英个体elite(generation, :) = population(1, :); % 记录本代的最优解(精英)% 若本代的最优解已足够好,则停止演化if best_fitness(generation) < minimal_cost; last_generation = generation;break; end% 交叉变异产生新的种群% 染色体交叉开始for child = 1:2:child_number % 步长为2是因为每一次交叉会产生2个孩子% cumulative_probabilities长度为parent_number% 从中随机选择2个父母出来  (child+parent_number)%parent_numbermother = find(cumulative_probabilities > rand, 1); % 选择一个较优秀的母亲father = find(cumulative_probabilities > rand, 1); % 选择一个较优秀的父亲% ceil(天花板)向上取整% rand 生成一个随机数% 即随机选择了一列,这一列的值交换crossover_point = ceil(rand*number_of_variables); % 随机地确定一个染色体交叉点% 假如crossover_point=3, number_of_variables=5% mask1 = 1     1     1     0     0% mask2 = 0     0     0     1     1mask1 = [ones(1, crossover_point), zeros(1, number_of_variables - crossover_point)];mask2 = not(mask1);% 获取分开的4段染色体% 注意是 .*mother_1 = mask1 .* population(mother, :); % 母亲染色体的前部分mother_2 = mask2 .* population(mother, :); % 母亲染色体的后部分father_1 = mask1 .* population(father, :); % 父亲染色体的前部分father_2 = mask2 .* population(father, :); % 父亲染色体的后部分% 得到下一代population(parent_number + child, :) = mother_1 + father_2; % 一个孩子population(parent_number+child+1, :) = mother_2 + father_1; % 另一个孩子end % 染色体交叉结束% 染色体变异开始% 变异种群mutation_population = population(2:population_size, :); % 精英不参与变异,所以从2开始number_of_elements = (population_size - 1) * number_of_variables; % 全部基因数目number_of_mutations = ceil(number_of_elements * mutation_rate); % 变异的基因数目(基因总数*变异率)% rand(1, number_of_mutations) 生成number_of_mutations个随机数(范围0-1)组成的矩阵(1*number_of_mutations)% 数乘后,矩阵每个元素表示发生改变的基因的位置(元素在矩阵中的一维坐标)mutation_points = ceil(number_of_elements * rand(1, number_of_mutations)); % 确定要变异的基因% 被选中的基因都被一个随机数替代,完成变异mutation_population(mutation_points) = rand(1, number_of_mutations); % 对选中的基因进行变异操作population(2:population_size, :) = mutation_population; % 发生变异之后的种群% 染色体变异结束end % 演化循环结束

cumulative_probabilities = cumsum((parent_number:-1:1) / sum(parent_number:-1:1));

这段代码是用来计算累加概率分布的。

1.生成递减序列,parent_number:-1:1生成一个从parent_number到1的递减序列。

2.计算总和,sum(parent_number:-1:1)

3.计算概率,(parent_number:-1:1) / sum(parent_number:-1:1) 将序列[10 9 8 7 6 5 4 3 2 1]中的每个元素除以序列的总和55 得到一个新的序列,其中每个元素代表一个概率。例如,对于 parent_number为 10 的情况,新的序列将是

[0.1818 0.1636 0.1455 0.1273 0.1091 0.0909 0.0727 0.0545 0.0364 0.0182]

4.累加概率,((parent_number:-1:1) / sum(parent_number:-1:1))对于上面的概率序列,累加和的结果 每个元素是前面所有元素的概率之和

 [0.1818 0.3455 0.4909 0.6182 0.7273 0.8182 0.8909 0.9455 0.9818 1.0000]

应用场景

        在遗传算法中,累加概率分布通常用于比例选择方法中。这种方法基于个体适应度值的比例来选择父母个体,适应度高的个体有更大的机会被选中吗,成为下一代的父母。

选择过程
  1. 计算适应度:为种群中的每个个体计算适应度值
  2. 归一化适应度:将适应度值转换为概率值。适应度值越大,被选择的概率越高
  3. 累加概率:计算累加概率分布
  4. 随机选择:适应累加概率分布来随机选择父母        

具体来说,当需要从种群中选择一个个体作为父母是,会生成一个介于0到1之间的随机数,然后查找累加概率向量中第一个大于或等于这个随机数的元素的索引。这个索引对应的个体就被选中了。

例如,如果随机生成的数是0.75,那么在累加概率向量[0.1818 0.3455 0.4909 0.6182 0.7273 0.8182 0.8909 0.9455 0.9818 1.0000]中,第一个大于或等于0.75的元素是0.7273,其索引为5,那么第5个个体会被选中。

这种方法确保了适应度较高的个体有更大的机会被选中,从而增加了优秀个体传递给下一代的机会。

        交叉和变异是遗传算法中的两个核心操作,它们模仿了自然界中生物进化的过程,用于在搜索过程中生成新的候选解。

交叉

        交叉操作(也称为杂交)是指在遗传算法中选择两个或多个个体(通常称为父母)并将它们的一部分遗传信息进行交换,以生成新的个体(称为后代或子代)这种操作的目的是探索解空间,通过组合现有个体的有点来创造潜在的更好解。

常见的交叉方法:

  • 单点交叉:选择一个交叉点,然后交换该点之后的基因片段
  • 多点交叉:选择多个交叉点,交替交换交叉点之间的基因片段
  • 均匀交叉:每个基因位点独立决定是否从父母之一继承基因

示例

假设我们有两个二进制编码的个体P1和P2:

P1 = [1 0 1 0 1 1]

P2 = [0 1 0 1 0 0]

使用单点交叉,在第三位交叉,生成的新个体为:

P1 = [1 0 1 1 0 0]

P2 = [0 1 0 0 1 1]

变异

        变异操作是指以一定的概率随机改变个体中的某些基因,以引入新的遗传信息。这种操作的目的是为了维持种群的多样性,防止算法过早二等收敛到局部最优解。

方法

        变异通常是在个体的基因位点上随机地改变其值。例如,对于二进制编码的个体,变异可能是简单地翻转某个位的值。

示例

假设我们有一个二进制编码的个体 Individual = [1 0 1 0 1 1],并在第二位进行变异:

变异前:[1 0 1 0 1 1]

变异后:[1 1 1 0 1 1]

 通过累加概率分布来选择父母

mother = find(cumulative_probabilities > rand, 1);

cumulative_probabilities 是一个长度为parent_number的向量,表示每个父母个体被选中的累加概率。

为了选择一个父母个体,我们生成一个介于0和1 之间的随机数(rand)使用 find函数来找cumulative_probabilities中第一个大于或等于这个随机数的元素的索引。这个索引对应的个体就是被选中的父母个体

mask1 = [ones(1, crossover_point), zeros(1, number_of_variables - crossover_point)];

mask1和mask2是两个掩码向量,用于在交叉操作中区分交叉点之前和之后的基因片段

mask2 = not(mask1);

对mask1中的每个元素进行逻辑取反

mother_1 = mask1 .* population(mother, :); % 母亲染色体的前部分
mother_2 = mask2 .* population(mother, :); % 母亲染色体的后部分

mother_1会保留 mask1中为 1 的位置上的基因值,其余位置上的基因值为 0。

mother_2会保留 mask2 中为 2 的位置上的基因值,其余位置上的基因值为 0。

测试test
clear; 
close all;% 调用 my_ga 进行计算
% 求解问题的参数个数         10
% 自定义适应度函数名         my_fitness
% 种群规模                  100
% 每一代中保持不变的数目     50 (即交叉率0.5)
% 变异概率                  0.1 (1/10的个体发生变异)
% 最大演化代数              10000 10000代
% 最小目标值                1.0e-6 个体适应度函数值 < 0.000001结束
[best_fitness, elite, generation, last_generation] = my_ga(10, 'my_fitness', 100, 50, 0.1, 10000, 1.0e-6);% 输出后10行
% disp(best_fitness(9990:10000,:));
% disp(elite(9990:10000,:))
% 这样是不合适的,因为GA常常在中间就跳出循环了% 这样才是合适的输出
disp(last_generation); 
i_begin = last_generation - 9;
disp(best_fitness(i_begin:last_generation,:));
% 将elite值转化为问题范围内
my_elite = elite(i_begin:last_generation,:);
my_elite = 2 * (my_elite - 0.5);
disp(my_elite);% 最佳适应度的演化情况
figure
loglog(1:generation, best_fitness(1:generation), 'linewidth',2)
xlabel('Generation','fontsize',15);
ylabel('Best Fitness','fontsize',15);
set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);% 最优解的演化情况
figure
semilogx(1 : generation, 2 * elite(1 : generation, :) - 1)
xlabel('Generation','fontsize',15);
ylabel('Best Solution','fontsize',15);
set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/416508.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

记一次Linux安装Maven、Git并拉取SpringBoot代码打包

记一次Linux安装Maven、Git并拉取SpringBoot代码打包 前言一、现在我用的方案二、安装Git三、安装maven四、脚本编写五、idea中运行六、总结 前言 在Java后端开发中&#xff0c;我相信基本上都在用springboot开发&#xff0c;因为它的约定优于配置&#xff0c;自动配置&#x…

五,Spring Boot中的 Spring initializr 的使用

五&#xff0c;Spring Boot中的 Spring initializr 的使用 文章目录 五&#xff0c;Spring Boot中的 Spring initializr 的使用1. 方式1&#xff1a;IDEA创建2. 方式2&#xff1a;start.spring.io 创建3. 注意事项和细节4. 最后&#xff1a; 需要&#xff1a;使用 Spring initi…

html+css网页设计 合十文化2个页面

htmlcss网页设计 合十文化2个页面 ui还原度90% 网页作品代码简单&#xff0c;可使用任意HTML编辑软件&#xff08;如&#xff1a;Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等操作&#xff09;。 获取源码 …

学习使用双指针

​ ​ &#x1f525;个人主页&#xff1a;guoguoqiang. &#x1f525;专栏&#xff1a;leetcode刷题 双指针&#xff0c;有时候是快慢指针的方式来进行题目&#xff0c; 有时候是同向双指针来完成题目&#xff08;这个也叫滑动窗口&#xff09;&#xff0c; 有时候是通过两个…

STM32(F103ZET6)第十九课:FreeRtos的移植和使用

目录 需求一、FreeRtos简介二、移植FreeRtos1.复制代码2.内存空间分配和内核相关接口3.FreeRtosConfig4.添加到工程中三、任务块操作1.任务四种状态2.创建任务过程 需求 1.将FreeRtos&#xff08;嵌入式实时操作系统&#xff09;移植到STM32中。 2.在该系统中实现任务的创建、…

智能优化特征选择|基于鲸鱼WOA优化算法实现的特征选择研究Matlab程序(KNN分类器)

智能优化特征选择|基于鲸鱼WOA优化算法实现的特征选择研究Matlab程序&#xff08;KNN分类器&#xff09; 文章目录 一、基本原理原理流程举个例子总结 二、实验结果三、核心代码四、代码获取五、总结 智能优化特征选择|基于鲸鱼WOA优化算法实现的特征选择研究Matlab程序&#x…

macos MacPort 包管理工具安装和使用

在macos v10.15版本中, xz, python等软件无法使用brew安装, 原因是brew对于旧版本的macos不再支持, 但是我们可以使用另外一个macos下的包管理工具来安装brew无法安装的软件, macport 是一个和brew类似的macos下的一个非常优秀的软件包安装管理工具. MacPort安装前提条件 安…

【qt踩坑】路径含中文导致的报错,以及 OpenGL的链接报错

​ 背景 本来是准备采用VSQt插件的方式来开发Qt的&#xff0c;但是学习过程中发现&#xff0c;这种模式还是没有直接用Qt Creator 开发来的方便&#xff0c;插件这种模式坑多&#xff0c;功能不完善。 不过在直接使用Qt Creator的时候也踩坑了&#xff1a; (最后发现&#x…

SprinBoot+Vue健康管管理微信小程序的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue3.6 uniapp代码 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍&#xff1a;CSDN认证博客专家&#xff0c;CSDN平…

qt报错 error: undefined reference to `vtable for RelayDevice 解决方法

在 Qt 编程中&#xff0c;当出现错误 undefined reference to ‘vtable for RelayDevice’ 时&#xff0c;通常是因为类的虚函数没有实现&#xff0c;或者未正确实现虚析构函数。以下是一些可能的解决方法&#xff1a; 确保实现所有虚函数&#xff1a; 检查 RelayDevice 类中声…

git clone 别人的项目上传到自己的Gitee或者github仓库

git clone别人的项目 git clone https://github.com/wohuweixiya/yft-design.git 进入该项目内&#xff0c;删除原有的.git信息 rm -r .git 初始化.git git init 将本地代码添加到仓库 git add . git commit -m "提交仓库说明" Github上新建一个和这个clone下来…

Rust多线程编程概述

【图书介绍】《Rust编程与项目实战》-CSDN博客 《Rust编程与项目实战》(朱文伟&#xff0c;李建英)【摘要 书评 试读】- 京东图书 (jd.com) Rust到底值不值得学&#xff0c;之一 -CSDN博客 Rust到底值不值得学&#xff0c;之二-CSDN博客 12.2 多线程编程概述 12.2.1 线程…

基于51单片机的电动机控制系统的设计

文章目录 前言资料获取设计介绍功能介绍程序代码部分参考 设计清单具体实现截图参考文献设计获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师&#xff0c;一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP…

LLM大模型学习:AI时代,敏感词过滤,如何精准且高效,方法+代码实现

前言 自从我开始搞大模型应用&#xff0c;就一直有一个头疼的问题困扰着我的团队&#xff0c;那就是避免敏感信息。 传统的做法是通过一些匹配算法&#xff0c;过滤掉敏感词&#xff0c;这个后面我们再讲。 但大模型的对话中&#xff0c;想要防止他做一些不合法的事情&#…

论文速读|重新审视奖励设计与评估:用于强健人型机器人站立与行走控制的方法

论文地址&#xff1a;https://arxiv.org/pdf/2404.19173 这篇论文为类人机器人站立和行走&#xff08;SaW&#xff09;控制器的持续可衡量改进奠定了基础。通过引入一套定量实际基准测试方法&#xff0c;作者展示了现有控制器的优缺点&#xff0c;并通过基准测试指导新控制器的…

Linux malloc内存分配实现原理

目录 一、用户进程虚拟内存空间布局 二、malloc工作原理 2.1 malloc实现流程 2.1.1 brk方式申请内存 2.1.2 mmap方式分配内存 2.2 核心代码 2.3 malloc分配物理内存的时机 2.4 malloc分配的实际内存大小 三、虚拟内存与物理内存 3.1 如何建立映射 3.2 分配物理内存 …

大数据采集与分析实训室解决方案

随着信息技术的飞速发展&#xff0c;大数据已成为推动产业升级、社会进步的重要力量。为了培养适应未来社会需求的大数据专业人才&#xff0c;构建一套科学、先进的大数据采集与分析实训室解决方案显得尤为重要。为此&#xff0c;唯众特推出全面升级的大数据采集与分析实训室解…

使用实例:xxl-job应用在spring cloud微服务下

1、首先下载&#xff0c;从github上下载&#xff0c;选择zip然后直接解压 https://github.com/xuxueli/xxl-job/releases 2、解压完后用idea启动。 启动这个启动类&#xff0c;然后按照路径访问 http://localhost:8080/xxl-job-admin/ 3、在你的项目里编写一个单独的微服务&a…

mac的使用

mac使用python的问题 对于python的虚拟环境&#xff0c;其实是基于已经安装到本地的python来安装不同的包。&#xff08;之前我的mac上只安装了python3.9.6 &#xff0c;安装的位置为/usr/bin/python3&#xff09;然后我在vscode里怎么找都找不到如何弄一个python3.7.6 的版本…

Nginx部署前端vue项目操作步骤和方法~小皮

部署前端Vue.js项目到Nginx上&#xff0c;是开发流程中至关重要的一步&#xff0c;它意味着将静态文件托管在Web服务器上&#xff0c;使应用程序能够被用户访问和交互。下面将详细介绍如何使用Nginx部署前端Vue项目的操作步骤和方法&#xff1a; 准备构建Vue项目 安装Node.js和…