禁忌搜索算法及应用

内容简介

禁忌搜索算法是一种全局逐步寻优算法，是对局部邻域搜索算法的推广，是人工智能在解决优化问题中的成功应用。《禁忌搜索算法及应用》在对禁忌搜索算法的原理做了全面阐述的基础上，结合近年来的研究工作，对其在的旅行商问题、多维背包问题、通讯中的多用户检测问题、前向神经网络训练问题、模糊神经网络设计问题、生理信号情感特征选择问题及算法的并行化等方面进行了比较广泛和深入的探讨。《禁忌搜索算法及应用》内容阐述清楚，大量实例可以加深对原理和方法的理解，能为相关研究人员提供参考和帮助。

目录

《智能科学技术著作丛书》序
前言
第1章 绪论1
1.1 关于化的问题1
1.1.1 化技术简述1
1.1.2 某些优化问题难以求解的原因1
1.2 现代启发式方法2
1.2.1 模拟退火算法3
1.2.2 进化计算3
1.2.3 人工免疫系统4
1.2.4 蚁群算法4
1.2.5 粒子群优化算法5
1.2.6 膜计算5
第2章 禁忌搜索基本原理7
2.1 禁忌搜索研究历程7
2.2 禁忌搜索示例8
2.3 禁忌搜索算法描述11
2.4 禁忌搜索的关键要素13
2.5 禁忌搜索的收敛性17
2.5.1 基于近期记忆的收敛禁忌搜索算法18
2.5.2 基于频率记忆的收敛禁忌搜索算法21
2.6 长时记忆22
2.6.1 基于频率的记忆22
2.6.2 义务执行移动22
2.7 策略性振荡22
2.8 禁忌搜索与认知心理学23
2.9 小结25
第3章 禁忌搜索在旅行商问题中的应用26
3.1 旅行商问题简介26
3.2 旅行商问题的禁忌搜索求解27
3.2.1 一种新颖的集中性与多样性的自适应搜索策略27
3.2.2 算法基本流程及仿真实验28
3.3 算法的比较33
3.4 小结34
第4章 禁忌搜索在多维背包问题中的应用35
4.1 多维背包问题简介35
4.2 基于短时-长时记忆的禁忌搜索36
4.2.1 算法基本思想36
4.2.2 算法设计36
4.3 多维背包问题优化实验38
4.4 小结44
第5章 禁忌搜索在多用户检测中的应用45
5.1 犆犇犕犃通信中多用户检测技术发展概况45
5.2 犆犇犕犃通信系统的等效数学模型47
5.3 多用户检测的性能测度49
5.3.1 误码率49
5.3.2 抗远近效应能力49
5.4 多用户检测方法50
5.5 次佳多用户检测器的分类52
5.6 基于禁忌搜索的多用户检测技术52
5.6.1 禁忌长度可变的禁忌搜索52
5.6.2 自适应禁忌搜索54
5.7 仿真实验与分析56
5.7.1 邻域构造对多用户检测问题的影响56
5.7.2 可变禁忌长度多用户检测方法的性能测度57
5.7.3 自适应禁忌搜索多用户检测方法的性能测度59
5.8 小结64
第6章 禁忌搜索在前向神经网络中的应用65
6.1 人工神经网络简介65
6.2 禁忌搜索在多层前向神经网络中的应用65
6.2.1 算法设计65
6.2.2 仿真实验66
6.3 小结71
第7章 禁忌搜索在模糊神经网络中的应用72
7.1 神经网络与模糊系统72
7.2 模糊系统与神经网络结合的方式73
7.3 犜犪犽犪犵犻-犛狌犵犲狀狅型模糊神经网络74
7.4 禁忌搜索应用于模糊神经网络的结构和参数优化77
7.4.1 犉犖犖-犎犜犛算法设计77
7.4.2 仿真实验79
7.5 禁忌搜索应用于模糊神经网络分类器设计86
7.5.1 模糊神经网络与数据挖掘87
7.5.2 犜犛-犉犖犖犆的设计88
7.5.3 犜犛-犉犖犖犆应用于犐犚犐犛数据分类91
7.6 小结93
第8章 禁忌搜索在情感计算中的应用94
8.1 情感计算与情感识别94
8.2 情感识别研究现状及问题96
8.2.1 情感识别研究现状96
8.2.2 情感识别研究中存在的问题97
8.3 犌犛犚信号的采集及特征提取99
8.3.1 犌犛犚信号99
8.3.2 犌犛犚数据采集实验100
8.3.3 犌犛犚数据的预处理105
8.3.4 犌犛犚有效特征提取106
8.4 特征选择111
8.4.1 特征选择作为组合优化问题111
8.4.2 特征选择的方法111
8.5 禁忌搜索应用于解决犌犛犚情感识别的特征选择112
8.5.1 封装式特征子集搜索思想112
8.5.2 应用于情感特征选择的禁忌搜索算法设计113
8.6 分类器设计117
8.6.1 分类器设计概述117
8.6.2 基于犌犛犚信号的情感识别分类器119
8.7 犌犛犚情感识别研究实验及分析122
8.7.1 改进的禁忌搜索算法仿真结果123
8.7.2 “一对一”情感识别研究124
8.7.3 “

摘要与插图

第1章 绪 论
1.1 关于化的问题
1.1.1 化技术简述
化技术是应用数学的一个重要分支,是解决化问题的一门新兴学科,主要研究在众多的解决方案中什么样的方案是的,或者怎样找出方案?例如,工程设计中怎样选择设计参数,使得设计方案既满足要求又能降低成本;资源分配中,怎样分配有限资源,使得分配方案既能满足各方面的基本要求又能获得好的经济效益;生产计划安排中,选择怎样的计划方案才能提高产值和利润;原料配比问题中,怎样确定各种成分的比例,才能提高质量,降低成本;城建规划中,怎样安排工厂?学校?机关?商店?医院?住宅小区和其他单位的合理布局,才能方便群众,有利于城市各行各业的发展?在人类活动的各个领域中,诸如此类的化问题,不胜枚举?
由于生产生活中的化问题比比皆是,并且无法回避,因此,几个世纪以来,人们孜孜以求,形成了一系列相关的化理论和算法?早在17世纪,英国伟大的科学家Newton发明微积分的时代就已经出现了极值问题,后来又出现
Lagrangian乘数法?1847年法国数学家Cauchy研究了函数值沿什么方向下降的问题,提出下降法?1939年,苏联数学家Kantorovich提出了解决下料问题和运输问题这两种线性规划问题的求解方法?
自20世纪40年代以来,由于科学研究的迅猛发展,是电子计算机的广泛应用,求解化问题有了强有力的计算工具,其相关的研究得到了飞速发展?至今,已出现线性规划?整数规划?非线性规划?几何规划?动态规划?随机规划等许多算法,化理论和算法在实际应用中正在发挥越来越大的作用?
1.1.2 某些优化问题难以求解的原因
现实世界中的许多工程问题或管理问题都可以归结为带约束的化问题,其种类与性质繁多?化问题可分为函数优化问题和组合优化问题两大类,其中,函数优化的对象是一定区间内的连续变量,而组合优化的对象则是解空间中的离散状态?无论工程中的许多问题,如天然气管网的运行优化?通信网络的结构优化等,还是计算机科学中的许多问题,如旅行商问题(rtaveling salesman problem,TSP)?作业车间调度问题(job shop scheduling problem,JSSP)?0-1背包问题(0-1knapsack problem,0-1KP)?装箱问题(bin packing problem,BPP)?图着色问题(graph colouring problem,GCP)?聚类问题(clustering problem problem,CPP)?度生成树问题(minimum degree spanning tree problem,MDSTP)和集合覆盖问题(set cover problem,SCP)等,都可以归结为组合优化问题?因此,对组合优化问题的研究一直受到人们的广泛重视?人们已经认识到,组合优化问题的计算复杂度很高,属于非确定性多项式困难问题(non-determinis-tic polynomial-time hardproblem,NP-hard),除了枚举一部分解空间以外(枚举将是一个天文数字),没有更好的解法?当问题的规模较小时,可以用运筹学的经典方法,如线性规划?整数规划?动态规划?分支定界等方法进行求解?当问题的规模增大时,由于解空间呈指数级或阶乘级增长,欲求准确的解实际上已不可能?
实际的优化问题之所以难于求解,归纳起来有以下一些原因[1]:
(1)搜索空间(或解空间)中可能解的数目太多以至于无法采用穷举搜索法去找到解;
(2)问题是如此复杂以至于为了得到任何解答,不得不采用问题的简化模型,而实际上所得的结果是无用的;
(3)描述可能解质量的评估函数或者有噪声或者随时间而变化,因此需要的不仅仅是一个解而是一系列解的解集;
(4)可能解都被严格约束以至于构造哪怕一个可行解都是困难的,更不用说找到解了;
(5)求解问题的人没有作好充分的准备或存在某种心理障碍使得他们难以找到答案?
当然,可能还有其他一些原因,但上面所列的已经足够了?每一个