(转载)基于量子遗传算法的函数寻优算法(matlab实现)

news/2024/4/21 0:24:48/

8.1 理论基础

8.1.1 量子遗传算法概述

        量子遗传算法(quantum genetic algorithm,QGA)是量子计算与遗传算法相结合的产物,是一种新发展起来的概率进化算法。遗传算法是处理复杂优化问题的一种方法,其基本思想是模拟生物进化的优胜劣汰规则与染色体的交换机制,通过选择、交叉、变异三种基本操作寻找最优个体。由于GA不受问题性质、优化准则形式等因素的限制,仅用目标函数在概率引导下进行全局自适应搜索,能够处理传统优化方法难以解决的复杂问题,具有极高鲁棒性和广泛适用性,因而得到了广泛应用并成为跨学科研究的热点。但是,若选择、交叉、变异的方式不当,GA会表现出迭代次数多、收敛速度慢、易陷入局部极值的现象。
        量子计算中采用量子态作为基本的信息单元,利用量子态的叠加、纠缠和干涉等特性,通过量子并行计算可以解决经典计算中的NP问题。1994年Shor提出第一个量子算法,求解了大数质因子分解的经典计算难题,该算法可用于公开密钥系统RSA;1996年Grover提出随机数据库搜索的量子算法,在量子计算机上可实现对未加整理的数据库√N量级的加速搜索,量子计算正以其独特的计算性能迅速成为研究的热点。
        量子遗传算法就是基于量子计算原理的一种遗传算法。将量子的态矢量表达引入遗传编码,利用量子逻辑门实现染色体的演化,实现了比常规遗传算法更好的效果。量子遗传算法建立在量子的态矢量表示的基础之上,将量子比特的几率幅表示应用于染色体的编码,使得一条染色体可以表达多个态的叠加,并利用量子逻辑门实现染色体的更新操作,从而实现了目标的优化求解。

8.1.2 量子比特编码

        在量子计算机中,充当信息存储单元的物理介质是一个双态量子系统,称为量子比特。量子比特与经典位不同就在于它可以同时处在两个量子态的叠加态中,比如:
        在量子遗传算法中,采用量子比特存储和表达一个基因。该基因可以为“0”态或“1”态,或它们的任意叠加态。即该基因所表达的不再是某一确定的信息,而是包含所有可能的信息,对该基因的任一操作也会同时作用于所有可能的信息。
        采用量子比特编码使得一个染色体可以同时表达多个态的叠加,使得量子遗传算法比经典遗传算法拥有更好的多样性特征。采用量子比特编码也可以获得较好的收敛性,随着|α|²或|β|²趋于0或1,量子比特编码的染色体将收敛到一个单一态。

8.1.3 量子门更新

        量子门作为演化操作的执行机构,可根据具体问题进行选择,目前已有的量子门有很多种,根据量子遗传算法的计算特点,选择量子旋转门较为合适。量子旋转门的调整操作为

 

8.2 案例背景

8.2.1 问题描述

        复杂二元函数求最值

 

 matlab代码及该函数的图形如下。

x = linspace(0, 12.1, 200);
y = linspace(4.1, 5.8, 200);
[x, y] = meshgrid(x,y);
f = 21.5+x.*sin(4*pi*x)+y.*sin(20*pi*y);figure;
surf(x,y,f);
colormap(gca, 'jet')
xlabel('x');
ylabel('y');
zlabel('f(x,y)');
title('函数图像')

        从图8-1中可以看出,该非线性函数在给定范围内分布着许多局部极值,通常的寻优算法极易陷入局部极值或在各局部极值间振荡,比较适用于验证量子遗传算法的性能。

8.2.2 解题思路及步骤

        1.量子遗传算法流程
        量子遗传算法的算法流程如下:
        (1)初始化种群Q(t0),随机生成n个以量子比特为编码的染色体;
        (2)对初始种群Q(t0)中的每个个体进行一次测量,得到对应的确定解P(t0);
        (3)对各确定解进行适应度评估;
        (4)记录最优个体和对应的适应度;
        (5)判断计算过程是否可以结束,若满足结束条件则退出,否则继续计算;
        (6)对种群Q(t)中的每个个体实施一次测量,得到相应的确定解;
        (7)对各确定解进行适应度评估;
        (8)利用量子旋转门U(t)对个体实施调整,得到新的种群Q(t+1);
        (9)记录最优个体和对应的适应度;
        (10)将迭代次数t加1,返回步骤(5)。
        对应的流程图如图8-2所示。

 

        随后,算法进入循环迭代阶段,随着迭代的进行,种群的解逐渐向最优解收敛。在每一次迭代中,首先对种群进行测量,以获得一组确定解P(t),然后计算每个解的适应度值,再根据当前的演化目标和事先确定的调整策略,利用量子旋转门对种群中的个体进行调整,获得更新后的种群,记录下当前的最优解,并与当前的目标值进行比较,如果大于当前目标值,则以新的最优解作为下一次迭代的目标值,否则保持当前的目标值不变。
2.量子遗传算法实现
(1)量子比特编码
        采用遗传算法中的二进制编码,对存在多态的问题进行量子比特编码,如两态用一个量子比特进行编码,四态用两个量子比特进行编码。该方法的优点是通用性好,且实现简单。采用多量子比特编码m个参数的基因如下:
(2)量子旋转门
        量子遗传算法中,旋转门是最终实现演化操作的执行机构。这里使用一种通用的、与问题无关的调整策略,如表8-1所列。

8.3 MATLAB程序实现

8.3.1 种群初始化

        种群初始化函数InitPop,得到初始种群的量子比特编码矩阵chrom。
function chrom=InitPop(M,N)
%% 初始化种群-量子比特编码
% M:为种群大小×2,(α和β)
% N:为量子比特编码长度
for i=1:Mfor j=1:Nchrom(i,j)=1/sqrt(2);end
end

8.3.2 测量函数

        对种群实施一次测量,得到二进制编码,函数名为collapse。
function binary=collapse(chrom)
%% 对种群实施一次测量 得到二进制编码
% 输入chrom :为量子比特编码
% 输出binary:二进制编码
[M,N]=size(chrom);  %得到种群大小 和编码长度
M=M/2;  % 种群大小
binary=zeros(M,N);  %二进制编码大小初始化
for i=1:Mfor j=1:Npick=rand;  %产生【0,1】随机数if pick>(chrom(2.*i-1,j)^2)    % 随机数大于α的平方binary(i,j)=1;elsebinary(i,j)=0;endend
end

8.3.3 量子旋转门函数

        旋转门是最终实现演化操作的执行机构,量子旋转门函数为Qgate。
function chrom=Qgate(chrom,fitness,best,binary)
%% 量子旋转门调整策略
% 输入  chrom:更新前的量子比特编码
%     fitness:适应度值
%        best:当前种群中最优个体
%      binary:二进制编码
% 输出  chrom:更新后的量子比特编码
sizepop=size(chrom,1)/2;
lenchrom=size(binary,2);
for i=1:sizepopfor j=1:lenchromA=chrom(2*i-1,j);   % αB=chrom(2*i,j);     % βx=binary(i,j);b=best.binary(j);if ((x==0)&(b==0))||((x==1)&(b==1))delta=0;                  % delta为旋转角的大小s=0;                        % s为旋转角的符号,即旋转方向elseif (x==0)&(b==1)&(fitness(i)<best.fitness)delta=0.01*pi;if A*B>0s=1;elseif A*B<0s=-1;elseif A==0s=0;elseif B==0s=sign(randn);endelseif (x==0)&(b==1)&(fitness(i)>=best.fitness)delta=0.01*pi;if A*B>0s=-1;elseif A*B<0s=1;elseif A==0s=sign(randn);elseif B==0s=0;endelseif (x==1)&(b==0)&(fitness(i)<best.fitness)delta=0.01*pi;if A*B>0s=-1;elseif A*B<0s=1;elseif A==0s=sign(randn);elseif B==0s=0;endelseif (x==1)&(b==0)&(fitness(i)>=best.fitness)delta=0.01*pi;if A*B>0s=1;elseif A*B<0s=-1;elseif A==0s=0;elseif B==0s=sign(randn);endende=s*delta;       % e为旋转角U=[cos(e) -sin(e);sin(e) cos(e)];      % 量子旋转门y=U*[A B]';        % y为更新后的量子位chrom(2*i-1,j)=y(1);chrom(2*i,j)=y(2);end
end

8.3.4 适应度函数

        这里以求解最大值问题为例进行说明,如果是求解最小值问题,可以转变成求最大值问题(加个负号即可),目标值越大的个体,其适应度值也应该越大,所以可以直接将所优化的目标 函数作为适应度函数。适应度主函数FitnessFunction的代码:
function [fitness,X]=FitnessFunction(binary,lenchrom)
%% 适应度函数
% 输入  binary:二进制编码
%     lenchrom:各变量的二进制位数
% 输出 fitness:适应度
%            X:十进制数(待优化参数)
sizepop=size(binary,1);
fitness=zeros(1,sizepop);
num=size(lenchrom,2);
X=zeros(sizepop,num);
for i=1:sizepop[fitness(i),X(i,:)]=Objfunction(binary(i,:),lenchrom);         % 使用目标函数计算适应度
end
        其中,函数Objfunction是待优化的目标函数,这里以8.2.1节中的函数为例进行说明。函数Objfunction的代码:
function [Y,X]=Objfunction(x,lenchrom)
%% 目标函数
% 输入     x:二进制编码
%   lenchrom:各变量的二进制位数
% 输出     Y:目标值
%          X:十进制数
bound=[-3.0 12.1;4.1 5.8];   % 函数自变量的范围
%% 将binary数组转化成十进制数组
X=bin2decFun(x,lenchrom,bound);
%% 计算适应度-函数值
Y=sin(4*pi*X(1))*X(1)+sin(20*pi*X(2))*X(2);
        其中,函数bin2decFun是将二进制编码转换成十进制数,其代码如下:
function X=bin2decFun(x,lenchrom,bound)
%% 二进制转化成十进制
% 输入      x:二进制编码
%    lenchrom:各变量的二进制位数
%       bound:各变量的范围
% 输出      X:十进制数
M=length(lenchrom);
n=1;
X=zeros(1,M);
for i=1:Mfor j=lenchrom(i)-1:-1:0X(i)=X(i)+x(n).*2.^j;n=n+1;end
end
X=bound(:,1)'+X./(2.^lenchrom-1).*(bound(:,2)-bound(:,1))'; 

8.3.5 量子遗传算法主函数

        量子遗传算法主函数代码如下:
clc;
clear all;
close all;
%----------------参数设置-----------------------
MAXGEN=200;                        % 最大遗传代数
sizepop=40;                        % 种群大小
lenchrom=[20 20];          % 每个变量的二进制长度
trace=zeros(1,MAXGEN);
%--------------------------------------------------------------------------      
best=struct('fitness',0,'X',[],'binary',[],'chrom',[]);   % 最佳个体 记录其适应度值、十进制值、二进制编码、量子比特编码
%% 初始化种群
chrom=InitPop(sizepop*2,sum(lenchrom));
%% 对种群实施一次测量 得到二进制编码
binary=collapse(chrom); 
%% 求种群个体的适应度值,和对应的十进制值
[fitness,X]=FitnessFunction(binary,lenchrom);         % 使用目标函数计算适应度
%% 记录最佳个体到best
[best.fitness bestindex]=max(fitness);     % 找出最大值
best.binary=binary(bestindex,:);
best.chrom=chrom([2*bestindex-1:2*bestindex],:);
best.X=X(bestindex,:);
trace(1)=best.fitness;
fprintf('%d\n',1)
%% 进化
for gen=2:MAXGENfprintf('%d\n',gen)  %提示进化代数%% 对种群实施一次测量binary=collapse(chrom);%% 计算适应度[fitness,X]=FitnessFunction(binary,lenchrom);%% 量子旋转门chrom=Qgate(chrom,fitness,best,binary);[newbestfitness,newbestindex]=max(fitness);    % 找到最佳值% 记录最佳个体到bestif newbestfitness>best.fitnessbest.fitness=newbestfitness;best.binary=binary(newbestindex,:);best.chrom=chrom([2*newbestindex-1:2*newbestindex],:);best.X=X(newbestindex,:);endtrace(gen)=best.fitness;
end%% 画进化曲线
plot(1:MAXGEN,trace);
title('进化过程');
xlabel('进化代数');
ylabel('每代的最佳适应度');%% 显示优化结果
disp(['最优解X:',num2str(best.X)])
disp(['最大值Y:',num2str(best.fitness)]);

8.4 结果分析

       优化结果如下所示:

  

        本例是针对8.2.1节中的案例进行编写的,用户可以根据自己的实际问题修改函数Objfunction(待优化的问题也并不局限在函数优化,可以是一个复杂的运算过程),再简单修改下
主函数中的相应变量设置即可。

8.5 延伸阅读

        前面使用的是未改进的量子遗传算法,该算法可以做些改进:


http://www.ppmy.cn/news/107540.html

相关文章

Unity | HDRP高清渲染管线学习笔记:基本操作

目录 一、场景整体环境光强度 1.HDRI Sky 2.Shadows 二、屏幕后处理效果(Post Processing) 1.Exposure 2.Post-processing/Tonemapping 三、抗锯齿 四、添加光源 1.Light Explorer窗口 2.光照探针组 3.反射探针 4.烘焙光照贴图 本文主要是了解HDRP基本操作&#xf…

ARM实验5-流水灯仿真实验

一、实验名称&#xff1a;流水灯仿真实验 二、实验目的&#xff1a; 掌握ARM处理器的输入输出接口。掌握通过MDK提供的仿真功能&#xff0c;实现系统的仿真运行。通过该编程实验&#xff0c;进一步巩固和强化学生ARM汇编编程的能&#xff0c;ARM应用程序框架&#xff0c;培养…

发明专利公开 -- 一种基于 JSON 文件 + Http Header 的支持多项目、多分支、多人协同的 Api Mock/代理 工具

现阶段主流的前后端分离的开发模式下&#xff1a;前后端采用并行开发方式&#xff0c;在前端开发过程中通常需要依附于共同约定的接口格式及数据。 该过程是一个并行过程&#xff0c;因此 Api Mock 模拟接口的返回变成了必要。同时&#xff0c;联调过程中&#xff0c;修改后端…

6.2 exec函数族

目录 进程-exec函数族 进程-execl/execlp 进程创建-execl(p)-示例 进程-execv/execvp 进程创建-execv(p)-示例 进程-system 笔记 进程-exec函数族 进程调用exec函数族执行某个程序 进程当前内容被指定的程序替换 实现让父子进程执行不同的程序 父进程创建子进程 子进…

【斯歌X捷普】优秀体验官活动:全民开发的样板企业是这样炼成的

3月22日&#xff0c;上海斯歌与捷普共同举办了一场别出心裁的活动——“产品优秀体验官”颁奖典礼&#xff0c;以表彰对业务流程开发做出突出贡献的捷普员工。值得注意的是&#xff0c;获奖的14名流程开发人员中&#xff0c;有7人并非是专业的IT人员&#xff0c;而是来自业务岗…

GB28181 对接海康平台,解决音视频卡顿问题

GB28181 对接海康平台,解决音视频卡顿问题 一、概述二、问题分析1、设备对比分析2、抓包对比分析3、验证分析结果三、总结四、讨论一、概述 设备使用GB28181协议对接海康平台时,发现音频和视频存在卡顿现象,不是一直卡顿,有时候卡有时候不卡,但是卡顿的时候音视频一起卡顿…

自动化测试中的失败截图和存log

如果我们在执行自动化测试的时候&#xff0c;希望能在失败的时候保存现场&#xff0c;方便事后分析。 对于UI自动化&#xff0c;我们希望截图在测试报告中。 对于api自动化&#xff0c;我们希望截取出错的log在测试报告中。 我开始自己蛮干&#xff0c;写了两个出错截图的方法。…

【windows脚本】使用diskpart命令管理未分配磁盘

环境 系统&#xff1a;win10 x64 概述 使用windows脚本管理未分配磁盘&#xff0c;手动操作需要做以下几步&#xff1a; 1、初始化磁盘GPT形式&#xff1b; 2、新建简单卷&#xff0c;设置大小和驱动器号。 3、格式化。 diskpart命令 使用diskpart工具&#xff0c;命令如…

【Linux】进程间通信详解

环境&#xff1a;centos7.6&#xff0c;腾讯云服务器Linux文章都放在了专栏&#xff1a;【Linux】欢迎支持订阅 进程间通信介绍 什么是进程间通信&#xff1f; 进程间通信&#xff08;Interprocess communication&#xff0c;简称IPC&#xff09;就是让程序员能够协调不同的进…

淘宝商品销量接口分享:获取淘宝商品总销量月销量

item_search_sales 获得淘宝商品总销量月销通过商品详情接口item_get&#xff0c;返回参数sales代表详情页上的月销 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;secretString是调用密钥api_nameString是API接口名称&#…

证件照制作教程:如何使用在线工具制作高质量的证件照

证件照制作&#xff1a;让你的形象更加完美 介绍 证件照是人们在日常生活、工作和学习中必不可少的一项证明身份的重要文件。而证件照的质量好坏不仅会直接影响到证件审核的效率&#xff0c;还会影响到自己形象的好坏。为了让自己的形象更加完美&#xff0c;我们需要制作高质…

关于ROS常用的cmake语句

关于ROS常用的CMake语句 1. find_package(catkin) ROS提供了ROS功能包的查找功能&#xff0c;并提供了catkin_INCLUDE_DIRS与catkin_LIBRARIES变量。 find_package(catkin REQUIRED COMPONENTS my_package)比如&#xff0c;以上cmake语句查找了my_package功能包&#xff0c…

研发工程师玩转Kubernetes——定时任务

定时任务是指可以制定周期的任务&#xff0c;比如每周二0点1分执行一次。在《研发工程师玩转Kubernetes——非定时任务》中&#xff0c;我们介绍了单次执行的任务。现在我们只要对其清单稍作修改&#xff0c;就可以实现定时任务。 apiVersion: batch/v1 kind: CronJob metadat…

MSDS报告是什么?

MSDS报告是什么&#xff1f;MSDS&#xff08;欧洲国家也有SDS&#xff0c;但内容与MSDS大同小异&#xff09;&#xff0c;MSDS就是化学品安全技术说明书&#xff0c;里面会包含物质的理化特性以及对使用者健康可能产生危害的一份文件。不管是对工艺设计、设备材质选型、还是对实…

Nginx 安装及部署项目

1. 下载nginx安装包 首先从官网下载 nginx,大家可以自己在百度搜索 nginx&#xff0c;进入官 网&#xff0c;或者在浏览中直接输入 nginx 的官方网址: http://nginx.org/ &#xff0c;在此我直接提供 nginx 的下载链接&#xff0c;大家点进去之后可以按照 自己的需求下载自己所…

微信支付链接二维码生成

1、进入composer官方网站&#xff0c;搜索phpqrcode安装包 composer命令安装 composer require aferrandini/phpqrcode 生成二维码图片的公共方法&#xff1a; // 公用二维码生成 static function setQrcode($url){//二维码图片保存路径$path advert/qrcode/.date("Ymd&q…

C++进阶 —— map

目录 一&#xff0c;map介绍 类pair 函数模板make_pair 二&#xff0c;map使用 一&#xff0c;map介绍 map是关联容器&#xff0c;按照特定的次序存储元素&#xff08;由键key和值value组合而成的&#xff09;&#xff1b;键key通常用于排序及唯一标识元素&#xff0c;而值…

企业如何进行等保自测和自评定级?

企业如何进行等保自测和自评定级&#xff1f;等保自测和自评定级是企业加强信息安全保障的重要手段。随着信息技术的不断发展&#xff0c;网络安全威胁不断增加&#xff0c;企业需要加强信息安全保障&#xff0c;保障企业信息的安全性、完整性和可用性。本文将介绍企业如何进行…

高完整性系统:Hoare Logic

目录 1. 霍尔逻辑&#xff08;Proving Programs Correct&#xff09; 1.1 警告&#xff08;Caveats&#xff09; 1.2 误解&#xff08;Misconception&#xff09; 1.3 编程语言&#xff08;Programming Language&#xff09; 1.4 程序&#xff08;Programs&#xff09; 1…

Ubuntu中which和whereis的区别

Ubuntu中which和whereis的区别 which和whereis是Linux系统中常用的命令&#xff0c;用于查找特定命令或文件的位置。在Ubuntu中&#xff0c;这两个命令的使用方法如下&#xff1a; which命令 which命令用于查找可执行文件在PATH路径中的位置。 示例&#xff1a; which ls输…