嵌套分割算法及其应用研究

VIP免费

3.0 高德中 2024-11-19 8 4 4.64MB 49 页 15积分

侵权投诉

嵌套分割算法及其应用研究

摘要

最优化方法应用十分广泛，几乎存在于每个科学研究领域、各级政府的管理、

决策、规划部门，也可以渗透到每一个数学分支，是现代科学技术，特别是工程优

化中不可缺少的理论依据、手段和方法。近些年来，现代系统的规模增大，约束条

件增多，非线性严重，使得传统的数学优化方法显得无能为力。伴随着人工智能、

仿生学的兴起，人们从不同的角度出发对生物系统及其行为特征进行了模拟，设计

出了一系列通用性较强的智能优化方法和模式，典型的有：遗传算法、模拟退火算

法、禁忌搜索算法、蚁群算法、粒子群算法、人工神经网络、DNA算法、和声算法

等，在广泛的科学和工程技术领域内显示了其独特的能力和应用效果。

本文的研究立足于Shi和ólafsson等于1997年提出的一种新型的全局优化算法

—嵌套分割算法(Nested Partitions Method, NPM) ，该算法虽然早在上世纪90

年代就已经提出，但是进展缓慢。具体说来，本文的工作主要包括：

(1) 概述了计算复杂性、几类典型的组合优化问题，及求解NP-难题常用的几

种智能优化算法及其研究现状。

(2) 分析了NPM的基本思想及其实施过程，同时探讨了算法的全局收敛性及其

优化效率。

(3) 针对函数优化问题，将禁忌搜索的思想引入嵌套分割算法的抽样算子中,

提出了基于禁忌搜索的复合嵌套分割算法（TSNP），从理论上探索算法的可行性和

科学性，并从实验角度验证算法的有效性。

(4) 针对背包问题，为蚁群优化算法引入回溯算子，加强算法的局部搜索能力

设计了基于回溯策略的蚁群优化算法（BACO），并通过实例验证混合算法的有效性

本文的研究成果进一步延伸了嵌套分割算法及其混合算法的应用范围，不仅具

有很好的理论意义，并且还有很大的应用价值。通过大量的实验证明，该算法是一

种可行且有效的智能算法，为复杂优化问题的求解提供了具有竞争力的方法，随着

研究的不断深入，其使用的范围将越来越广。

关键词：嵌套分割算法禁忌搜索蚁群算法函数优化背包问题

ABSTRACT

The optimization method have been widely applied to almost every research areas,

a l l l e v e l s o f g o v e r n m e n t s m a n a g e m e n t , d e c i s i o n - m a k i n g a n d p l a n n i n g

d e p a r t m e n t s ,w h i c h c a n a l s o p e n e t r a t e i n t o e v e r y b r a n c h o f

mathematics.It is modern science and technology, especially indispensable basis, means

a nd meth od s t o t he e n g i ne e r i n g o p t im i z a t i o n t he o r y. In r e c e n t ye a r s, as t h e s c a l e o f

object problem becomes larger and constraint conditions are increasing,additionly, high

n o n l i n e a r i t y a r e basic characteristics o f t h e s e c o m p l e x s y s t e m s, t r a d i t i o n a l

mat h ema t ica l o pti m iz at io n me tho ds l oo k po we rl es s. With th e e merg en c e o f a r ti f ic i a l

i n t e l l i g e n c e a n d b i o n i c s , p e o p l e h a v e s i m u l a t e d t h e m f r o m di f f e r e n t p e r s p e c t i v e

based on the characteristics of biological systems and their behavior, designed a series

of strong universal intelligent optimization methods and models. Typical methods are

genetic algorithms, simulated annealing, tabu search, ant colony optimization, particle

s w a r m o p t i m i z a t i o n , a r t i f i c i a l n e u r a l n e t w o r k s , D N A a l g o r i t h m , h a r m o n y s e a r c h

algorithm and so on. In the broad field of science and engineering has demonstrated its

unique capabilities and application results.

This paper introduced the main ideas and implementation process of nested partitions

met hod( NPM) whi ch is a n ew g lo b al o pt imi zat ion algo ri t hm ba sed on w hat Shi and

ólafsson proposed in 1997. It was first proposed in the early 90s of the last century, and

developed slowly. The contents of the thesis include:

1. G e n e r a l l y i n t r o d u c e s c o m p u t a t i o n a l c o m p l e x i t y a n d s u r v e y s

several types of traditional combinatorial optimization problems, some main ideas of

e v o l u t i o n a r y a l g o r i t h m s w h i c h c a n s o l v e N P - h a r d p r o b l e m s a n d t h e i r d e v e l o p m e n t

history.

2. This paper discusses the global convergence of nested partitions method and

optimize efficiency.

3. T h i s p a p e r i n t r o d u c ed t h e t a b u s e a r c h ( T S ) a l g o r i t h m a n d

i n c o r p o r a t ed t h e i d e a s o f T S i n t o t w o o f t h e a r i t h m e t i c o p e r a t o r s o f

N PM t o f o r m t h e c o m b i n e d T S N P a l g o r i t h m t h a t s o l v e d f u n c t i o n o p t i m i z a t i o n . A n d

this algorithm is theoretically feasible and scientific exploration, and the angle from the

experimental verification algorithm.

4. T h i s p a p e r a d o p te d t h e c o n c e p t o f b a c k t r a c k i n g f r o m t h e N e s t e d P a r t i t i o n

m e t h o d ( N PM) a n d a p p l y i t t o t h e A n t C o l o n y O p t i m i z a t i o n ( A C O ) f o r

strengthening the Ant Colony algorithm of local search ability to solve the Knapsack

Problem. Numerical tests on typical instances show the efficiency and advantage of the

algorithm.

The research result of the thesis develops and extends the applications of the Nested

Par t iti ons Alg o rith m an d it s hy bri d a lgor it h m. It n ot o nly pos se s ses goo d t h eo reti cal

significance, but also has great application value. Many tests show that it is a kind of

intelligent algorithm with feasibility and availability, and it provides a new competitive

method for solving complex and hard optimization problems in application.

With the further research, its applied range will be wider.

Ke y w o r d s : N e s t e d P a r t i t i o n s Me t h o d, T a b u S e a r c h , A n t C o l o n y

Algorithm, Function Optimization, knapsack problem

目 录
中文摘要
ABSTRACT
第一章 绪 论.......................................................1
§1.1  研究背景..................................................1
§1.2  研究内容..................................................2
第二章 智能优化算法概述............................................4
§2.1  引言......................................................4
§2.2  计算复杂性及NP难题........................................4
§2.2.1 计算复杂性.............................................4
§2.2.2 NP难题.................................................6
§2.3  智能优化算法..............................................9
§2.3.1 遗传算法..............................................10
§2.3.2 禁忌搜索..............................................11
§2.3.3 模拟退火算法..........................................11
§2.3.4 粒子群算法............................................12
§2.3.5 人工神经网络..........................................12
§2.3.6 蚁群算法..............................................13
§2.3.7 DNA算法...............................................13
§2.3.8 和声算法..............................................14
§2.4  小结.....................................................15
第三章 嵌套分割算法...............................................16
§3.1  引言.....................................................16
§3.2  嵌套分割算法(NPM)的思想和方法............................16
§3.2.1 NPM的概念.............................................16
§3.2.2 NPM的基本思想.........................................17
§3.2.3 NPM描述...............................................18
§3.2.4 NPM的求解示例.........................................19
§3.3  嵌套分割算法的全局收敛性.................................20
§3.4  NPM的优化效率分析........................................21
§3.4.1 分割策略对NPM的意义...................................21
§3.4.2 抽样样本大小对NPM的意义...............................22
§3.4.3 回溯次数对NPM的意义...................................22
§3.4.4 NPM的寻优概率分析.....................................22
§3.5  小结.....................................................24
第四章 嵌套分割算法应用...........................................25
§4.1  引言.....................................................25
§4.2  函数优化问题的嵌套分割算法及其改进.......................25
§4.2.1 函数优化问题的数学描述................................25
§4.2.2 NPM实施步骤...........................................26
§4.2.3 嵌套分割算法的改进—TSNP算法..........................28
Ⅰ

§4.2.4 TSNP算法的可行性分析..................................31
§4.2.5 TSNP算法的科学性分析..................................32
§4.2.6 函数优化仿真实验......................................32
§4.3  背包问题的嵌套分割算法及其改进...........................37
§4.3.1 背包问题的数学描述....................................37
§4.3.2 求解背包问题的算法描述................................38
§4.3.3 算例测试..............................................40
§4.4  小结.....................................................42
第五章 结论与展望.................................................43
§5.1  全文总结.................................................43
§5.2  后续工作.................................................43
参考文献..........................................................45
Ⅱ

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

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

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

嵌套分割算法及其应用研究摘要最优化方法应用十分广泛，几乎存在于每个科学研究领域、各级政府的管理、决策、规划部门，也可以渗透到每一个数学分支，是现代科学技术，特别是工程优化中不可缺少的理论依据、手段和方法。近些年来，现代系统的规模增大，约束条件增多，非线性严重，使得传统的数学优化方法显得无能为力。伴随着人工智能、仿生学的兴起，人们从不同的角度出发对生物系统及其行为特征进行了模拟，设计出了一系列通用性较强的智能优化方法和模式，典型的有：遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法、粒子群算法、人工神经网络、DNA算法、和声算法等，在广泛的科学和工程技术领域内显示了其独特的能力和应用效果。本文的研...

展开>> 收起<<

嵌套分割算法及其应用研究.doc

共49页,预览5页

还剩页未读，继续阅读

嵌套分割算法及其应用研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: