遗传算法Github初学

2024-09-04 22:44
文章标签 初学 github 遗传算法

本文主要是介绍遗传算法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);

这篇关于遗传算法Github初学的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

Github连接方式

打开Linux中git的配置文件: /home/username/git/MyRepository/.git/config [core]repositoryformatversion = 0filemode = truebare = falselogallrefupdates = true[remote "origin"]fetch = +refs/heads/*:refs/remot

GitHub每周最火火火项目(9.2-9.8)

项目名称:polarsource / polar 项目介绍:polar 是一个开源项目,它是 Lemon Squeezy 的替代方案,并且具有更具优势的价格。该项目的目标是为开发者提供一种更好的选择,让他们能够在追求自己的热情和兴趣的同时,通过编码获得相应的报酬。通过使用 polar,开发者可以享受到更实惠的价格,同时也能够更自由地发挥自己的创造力和技能。 项目地址:https://github.

Node.js和vue3实现GitHub OAuth第三方登录

Node.js和vue3实现GitHub OAuth第三方登录 前言 第三方登入太常见了,微信,微博,QQ…总有一个你用过。 在开发中,我们希望用户可以通过GitHub账号登录我们的网站,这样用户就不需要注册账号,直接通过GitHub账号登录即可。 效果演示 注册配置 GitHub 应用 1.首先登录你的GitHub然后点击右上角的头像->点击进入Settings页面 2.在

将你的github仓库设置为web代理

将你的github仓库设置为web代理 废话不多说,直接上步骤 废话不多说,直接上步骤 创建一个仓库,上传静态web。 2. 设置仓库的 page 1)点击 “Settings” 如图设置

GitHub每日最火火火项目(9.7)

项目名称:polarsource / polar 项目介绍:polar 是一个开源的项目,它是 Lemon Squeezy 的替代方案,具有更优惠的价格。该项目旨在让开发者能够凭借自己的热情进行编码并获得报酬。通过使用 polar,开发者可以更轻松地实现自己的创意和项目,并从中获得收益。 项目地址:https://github.com/polarsource/polar项目名称:psf / bla

git如何灵活切换本地账号对应远程github的两个账号

git如何灵活切换本地账号对应远程github的两个账号 问题: 有时候我们会同时维护两个github的账号里面的仓库内容,这时候本地git需要频繁的切换ssh,以方便灵活的与两个账号的仓库可以通信。这篇日记将阐述我是怎么解决这个问题的。1. 第一个账户 生成本地SSH2. 注意 我们要设置第二个账户的 本地 SSH 时3. 两个账号来回切换 问题: 有时候我们会同时维护两个git

ubuntu16.04 caffe(github源码cpu)+python3.5+opencv3.4.5安装编译

https://www.cnblogs.com/hanjianjian90/p/10604926.html

Understanding the GitHub Flow

这里看下Github的入门介绍    --链接 GitHub Flow is a lightweight, branch-based workflow that supports teams and projects where deployments are made regularly. This guide explains how and why GitHub Flow works

GIT-macOS配置推送代码到GitHub

文章目录 前言1. **设置 HTTP/HTTPS**临时设置(仅对当前会话有效)永久设置(写入配置文件) 2. **设置 SOCKS **3. **取消设置**4. **验证配置**5. **测试推送** 总结 前言 macOS配置推送代码到GitHub 1. 设置 HTTP/HTTPS 临时设置(仅对当前会话有效) git config --global ht