量子竞争决策算法及其应用研究

VIP免费

3.0 牛悦 2024-11-19 4 4 766.09KB 56 页 15积分

侵权投诉

摘要

最优化在工程技术、科学研究和经济管理等诸多领域中有着广泛的应用，最

优化技术是用于求解各种问题最优解或满意解的应用技术。随着目标问题的规模

越来越大，约束条件增多，不连续、不可微、不确定、高度非线性已成为这些复

杂系统的基本特征，或者问题本身是困难的组合优化问题。这些特点使传统的最

优化方法在应用于复杂、困难的优化问题时有较大的局限性。因此对高效的优化

技术的需求日益迫切，探寻适合复杂计算且具有智能特征的算法已成为研究热点

和重要研究方向。

本文在竞争决策算法和进化博弈论及量子进化算法的基础上提出了一种新型

优化算法――量子竞争决策算法。从理论和实验两方面对算法进行了研究，本文

的创新与改进之处体现在以下几点：

（1）竞争决策算法在优化过程中竞争者缺少学习和自进化能力，影响算法的

性能，本文将进化博弈论引入到算法中，使竞争者具有自调整和自寻优能力；

（2）竞争决策等方法解决了进化博弈中往往得到次优解和量子进化中的退化

问题，使得算法具有更强的全局优化能力；

（3）将量子进化计算中量子比特、叠加态等理论与竞争者结合，缩小竞争者

群体规模，加快算法收敛速度；

（4）竞争决策算法在求解离散优化问题已初见成效，但没有讨论过其收敛性，

有关量子进化算法的收敛性的研究也较少，本文利用马尔可夫链从理论上证明了

量子竞争决策算法具有全局收敛性；

（5）将量子竞争决策算法分别用于求解非线性0-1规划问题、大规模旅行商

问题和复杂函数优化问题，给出了算法的数学描述，设计了相应的求解策略，通

过大量实验和与现有算法的比较，均获得了理想的结果；

（6）竞争决策算法目前仅用于求解离散组合优化问题，量子竞争决策算法可

用一般连续和离散空间优化问题；量子进化算法已成功用于求解线性 0-1 背包问题

和小规模旅行商问题等，但不能有效求解复杂优化问题，量子竞争决策算法在求

解非线性 0-1 规划问题、大规模旅行商问题和复杂函数优化问题时表现出良好的

性能；进化博弈论在生物、经济、政治等方面应用较多，但在优化问题上应用很

少，量子竞争决策算法拓宽了进化博弈论的应用领域。

总之，本文从理论上提出了求解优化难题的新型算法并给出了收敛性的分析，

在应用上为求解复杂困难的优化问题提供了新的有效的方法。

关键词：优化竞争决策进化博弈量子进化收敛

ABSTRACT

The optimization techniques have been applied to a wide range of engineering

technology, scientific research,economic management and so on, which are used to

obtain optimal solution or satisfactory solution of various problems. As the scale of

object problem becomes larger and constraint conditions are increasing, discontinuity,

non-differentiation, uncertainty and high nonlinearity are basic characteristics of these

complex systems, or these problems are NP-hard combinatorial optimization problems.

The traditional optimization methods have great limitation to solve complex and

difficult optimization problems because of these features. So the require for high

efficiency intelligent optimization techniques is becoming more and more necessary,

and exploring algorithms with intelligent characteristics for complicated calculation is

research focus and important research direction.

This dissertation proposes a novel optimization algorithm-quantum competitive

decision algorithm, which is based on competitive decision algorithm, evolutionary

game theory and quantum evolutionary algorithm. The algorithm is analyzed from the

experiment and theory aspects. The main innovations and improvements lie below:

1 The performance of competitive decision algorithm is influenced because of lack

of the capacity of learning and self-evolution for competitors in the optimization

process. The introduction of evolutionary game theory makes competitors possess the

ability of self-adjusting and self-optimizing.

2 The decision-making method and other methods solve the suboptimal solution in

evolutionary game theory and the degenerate problem in quantum evolutionary

algorithm, and these make the algorithm have stronger global optimization ability.

3 The combination of quantum bit, superposition state and other concepts in

quantum evolutionary algorithm and competitors can reduce the number of competitors

and speed up the convergence of the algorithm.

4 Competitive decision algorithm has won initial success in solving discrete

optimization problems, but there is no discussion of its convergence. There is also less

research on the convergence of quantum evolutionary algorithm. This dissertation gives

convergence analysis by Markov chain in theory.

5 The algorithm is applied to solve nonlinear 0-1 programming, large-scale TSP

and complex function optimization. This dissertation gives their mathematical

descriptions and develops a series of strategies for solving these different optimization

problems. A large number of experiments and comparisons with existing algorithms are

done. All show that the algorithm is robust and efficient.

6 Competitive decision algorithm at present is only used in discrete combinatorial

optimization problems. quantum competitive decision algorithm can be effectively used

in function and discrete optimization problems. Quantum evolutionary algorithm has

been applied successfully to linear 0-1 knapsack problem, small-scale TSP and so on,

but it can not effectively solve the complex optimization problems. Experiments on

solving nonlinear 0-1 programming, large-scale TSP and complex function optimization

indicate that quantum competitive decision algorithm has the good performance.

Evolutionary game theory is applied extensively in biological, economic, political and

so on, but it is less used in optimization problems. quantum competitive decision

algorithm widens its application range.

In a word, this dissertation theoretically presents a new method for optimization

problems and gives the convergence proof of the algorithm. Practically, the dissertation

puts forward a novel and effective algorithm for solving difficult and complex

optimization problems.

Keywords: Optimization, Competition and Decision, Evolutionary

Game, Quantum Evolutionary, Convergence

摘要

ABSTRACT

第一章绪论.....................................................................................................................1

§ 1.1 研究背景 .................................................................................................................1

§ 1.2 计算复杂性及 NP 难题 ......................................................................................... 2

§ 1.2.1 计算复杂性.......................................................................................................2

§ 1.2.2 NP 难题 ............................................................................................................ 3

§ 1.3 经典优化算法 .........................................................................................................5

§ 1.4 智能优化算法 .........................................................................................................5

§ 1.4.1 遗传算法...........................................................................................................6

§ 1.4.2 模拟退火算法...................................................................................................6

§ 1.4.3 禁忌搜索算法...................................................................................................7

§ 1.4.4 人工神经网络...................................................................................................7

§ 1.4.5 蚁群算法...........................................................................................................8

§ 1.4.6 微粒群算法.......................................................................................................8

§ 1.4.7 DNA 算法.........................................................................................................9

§ 1.4.8 植物生长算法.................................................................................................10

§ 1.5 研究内容 ...............................................................................................................10

§ 1.6 小结 .......................................................................................................................12

第二章竞争决策算法和进化博弈论及量子进化算法...............................................13

§ 2.1 引言 .......................................................................................................................13

§ 2.2 主要方法和技术 ...................................................................................................13

§ 2.2.1 竞争决策算法.................................................................................................13

§ 2.2.2 进化博弈论.....................................................................................................15

§ 2.2.3 量子进化算法.................................................................................................16

§ 2.3 量子竞争决策算法 ...............................................................................................17

§ 2.4 小结 .......................................................................................................................18

第三章非线性 0-1 规划问题的量子竞争决策算法 ................................................... 19

§ 3.1 引言 .......................................................................................................................19

§ 3.2 算法设计................................................................................................................19

§ 3.2.1 基本概念.........................................................................................................19

§ 3.2.2 算法流程 ........................................................................................................22

§ 3.3 实例测试................................................................................................................22

§ 3.4 小结 .......................................................................................................................26

第四章大规模旅行商问题的量子竞争决策算法.......................................................27

§ 4.1 问题描述 ...............................................................................................................27

§ 4.2 算法原理 ...............................................................................................................28

§ 4.2.1 基本符号及含义 ............................................................................................28

§ 4.2.2 基本概念 ........................................................................................................29

§ 4.3 实例验证 ...............................................................................................................31

§ 4.4 小结 .......................................................................................................................33

第五章函数优化的量子竞争决策算法.......................................................................35

§ 5.1 引言 .......................................................................................................................35

§ 5.2 算法描述................................................................................................................35

§ 5.2.1 连续优化问题的模型 ....................................................................................35

§ 5.2.2 算法分析 ........................................................................................................35

§ 5.3 计算实验 ...............................................................................................................36

§ 5.4 小结........................................................................................................................42

第六章量子竞争决策算法的收敛性...........................................................................43

§ 6.1 概述 .......................................................................................................................43

§ 6.2 理论基础 ...............................................................................................................43

§ 6.3 收敛性分析 ...........................................................................................................44

§ 6.4 小结 .......................................................................................................................46

第七章全文总结和展望...............................................................................................47

§ 7.1 全文总结 ...............................................................................................................47

§ 7.2 进一步的工作 .......................................................................................................47

参考文献.........................................................................................................................49

在读期间公开发表的论文和承担科研项目及取得成果.............................................53

致谢...............................................................................................................................55

第一章绪论

§ 1.1 研究背景

随着时代的不断进步和发展，如今的科学技术正处在多学科相互交叉和渗透

的时代，尤其是计算机科学与技术的迅速发展，从根本上改变了人类的生产与生

活，并渗透到各个研究领域，已成为生产、生活、研究中的一个重要且不可缺少

的工具。同时，随着人类生存空间的扩大及认识与改造世界范围的拓宽，人们对

科学技术提出了新的和更高的要求，其中对高效的优化技术和智能计算的要求日

益迫切。优化技术的目标是寻求最优的方法来完成各种任务，最优的方法是指用

最短的时间，最少的人力、物力和设备来完成我们的工作。作为一个重要的科学

分支，它一直受到人们的广泛重视，并在诸多工程领域得到迅速推广和应用，如

运筹学、系统工程、系统控制、人工智能、模式识别、生产调度、VLSI 技术和计

算机工程等。

进入 21 世纪，尽管人们已经可以让计算机完成一些过去无法想象的任务，但

仍然有许多复杂的实际问题得不到很好的解决，如组合优化问题中存在很多目前

还无法处理的 NP 难题，其中，有著名的旅行商问题、车辆路径问题、背包问题等，

这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主

要原因是当问题规模较大时，会出现所谓的“组合爆炸”，导致计算机无法在现

有的存储空间和有效的时间内求得问题的最佳答案，经典算法对此无能为力。正

是这些问题的代表性和复杂性激起了人们对优化理论与算法的研究兴趣。智能算

法是目前解决该类问题的现实有效方法，如遗传算法、神经网络、模拟退火法、

禁忌搜索法、蚁群算法、免疫算法、微粒群算法等。但随着问题规模的日益庞大

和复杂性的增加，这些问题也暴露出本身固有的一些缺点。

本文在竞争决策算法基础上，结合进化博弈论和量子进化算法，针对优化问

题，提出一种全新的优化算法——量子竞争决策算法。从理论角度探索算法的收

敛性，为算法奠定理论基础，并从实验角度验证算法的有效性。

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要最优化在工程技术、科学研究和经济管理等诸多领域中有着广泛的应用，最优化技术是用于求解各种问题最优解或满意解的应用技术。随着目标问题的规模越来越大，约束条件增多，不连续、不可微、不确定、高度非线性已成为这些复杂系统的基本特征，或者问题本身是困难的组合优化问题。这些特点使传统的最优化方法在应用于复杂、困难的优化问题时有较大的局限性。因此对高效的优化技术的需求日益迫切，探寻适合复杂计算且具有智能特征的算法已成为研究热点和重要研究方向。本文在竞争决策算法和进化博弈论及量子进化算法的基础上提出了一种新型优化算法――量子竞争决策算法。从理论和实验两方面对算法进行了研究，本文的创新与改进之处体现在以下几...

展开>> 收起<<

量子竞争决策算法及其应用研究.pdf

共56页,预览6页

还剩页未读，继续阅读

量子竞争决策算法及其应用研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: