第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求解问题的人没有作好充分的准备或存在某种心理障碍使得他们难以找到答案?
当然,可能还有其他一些原因,但上面所列的已经足够了?每一个问题都有其存在的原因,重要的是如何解决它?因此,现代启发式方法应运而生?
1.2 现代启发式方法
如前所述,许多优化问题难于求解?但从满足实际应用的角度出发,能够得到满意解的近似算法或以一定的概率保证解的质量的随机算法是可以接受的,也越来越受到重视?
近几十年来,研究者开始从不同的角度出发向自然界的生物系统?人类自身及其行为特征或智力过程等寻求灵感?自然界的生物系统具有趋向于非集中控制性?自适应性和环境意识,这使得它们具有适应环境的能力,具有很强的可测量性和灵活性,这些属性远远优于现有的最好的人机系统?探讨如何从生物学中包括人类自身的安全性?适应环境和优化过程获取的灵感用于计算任务,对人工智能的新原理?新方法及相关学科的发展具有极大的推动作用?
在自然界灵感的启发下,自20世纪80年代以来,出现了一些新颖的优化算法,如人工神经网络?混沌?进化计算?模拟退火?禁忌搜索?模糊系统?人工免疫系统?群智能?量子计算?膜计算等,这些算法的思想和内容涉及数学?物理学?生物进化?人工智能?神经科学?统计力学等方面,为解决复杂问题提供了新的思路和手段?这些算法独特的优点和机制,引起了国内外学者的广泛重视并掀起了研究热潮,且在诸多领域得到了成功应用?鉴于这些算法构造的直观性和自然机理,通常称其为现代启发式modern heuristics,MH方法或计算智能computational intelligence,CI或自然计算nature inspired computation,NIC?下面就一些主要的启发式方法予以简介?
1.2.1 模拟退火算法
模拟退火simulated annealing,SA算法的思想最早是由METROPOLIS等在1953年提出的[2],1983年,Kirkpatrick等将其应用于组合优化[3]?模拟退火算法是基于Monte Carlo迭代求解的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性?模拟退火算法在某一初温下,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解时能概率性地跳出并最终趋于全局最优?模拟退火算法是一种通用的优化算法,目前已在工程中得到了广泛应用,如VLSI?生产调度?控制工程?机器学习?图像处理等领域[4-7]?
1.2.2 进化计算
进化计算evolutionary computation,EC的研究始于20世纪50年代,在20世纪六七十年代并未受到普遍的重视?其主要原因为:一是这些方法本身还不够成熟;二是这些方法需要较大的计算量,而当时的计算机还不够普及且速度较慢,这样便限制了它们的应用;三是当时基于符号处理的人工智能方法正处于其顶峰时期,使得人们难以认识到其他方法的有效性及适应性?到了20世纪80年代,人工智能方法的局限性越来越突出,并且随着计算机速度的提高和并行计算机的普及,已使得进化计算对机器速度的要求不再是制约其发展的因素?进化计算的不断发展及其在一些应用领域内取得的成功,已表现出了良好的应用前景?由于进化计算在机器学习?过程控制?经济预测?工程优化等领域取得的成功,引起了各领域科学家的极大兴趣?自20世纪80年代中期以来,世界上许多国家都掀起了进化计算的研究热潮?目前,有数种以进化计算为主题的国际会议在世界各地定期召开,并已出版了两种以上专门关于进化计算的权威期刊?进化计算的主要特
点是群体搜索策略和群体之间的信息交换?目前,遗传算法genetic algorithm,GA?进化规划evolutionary programming,EP?进化策略evolutionary strategies,ES三者一起构成了进化计算的主要框架[8-10]?近年来,进化计算在解决连续变量的函数最优化问题和离散变量的组合优化问题时所表现出的鲁棒性?全局性?隐并行性和自适应性,使其成为一类应用日益广泛的智能优化算法[11-14]?
1.2.3 人工免疫系统
人工免疫系统artificial immune system,AIS是模仿自然免疫系统功能的一种智能方法,它体现了一种受生物系统启发,通过学习外界物质的自然防御机理的学习技术,提供了噪声忍耐?无教师学习?自组织?记忆等进化学习机理,结合了分类器?神经网络和机器推理等系统的一些优点,因此提供了新颖的解决问题的方法和途径,成为继神经网络?模糊系统?进化计算后人工智能的又一研究热点[15,16]?
Farmer等率先基于免疫网络的相关学说给出了免疫系统的动态模型,并探讨了免疫系统与其他人工智能方法的联系,开始了人工免疫系统的研究[17]?在我国,靳蕃等在1990年前后就已经指出“免疫系统所具有的信息处理和肌体防卫功能,从工程角度来看,具有非常深远的意义”[18]?但是,这之后的研究成果较为少见?
直到1996年12月,在日本首次举行了基于免疫系统的国际专题讨论会,首次提出了“人工免疫系统”的概念?随后,人工免疫系统的研究进入了兴盛发展期,Dasgupta等认为人工免疫系统已经成为人工智能领域的理论和应用研究热点[15,19,20],相关论文和研究成果正在逐年增加?在国内,西安电子科技大学焦李成及其团队较早地开展了人工免疫系统的研究,取得了令人瞩目的成就[21-34]?在国外,美国新墨西哥大学较早地开展了基于人工免疫系统的信息安全方面的研究,提出了计算免疫学的概念,致力于构建计算机免疫系统,其相关成果已经在IBM?Intel等公司的信息安全软件中得到了应用?英国Kent大学的Timmis等对基于人工免疫系统的机器学习和数据挖掘技术进行了系统的理论研究,并开展了基于人工免疫系统的大规模数据挖掘的应用[35,36]?人工免疫系统的研究主要集中在人工免疫系统模型?人工免疫系统算法和人工免疫系统方法的应用等方面[17]?
1.2.4 蚁群算法
蚂蚁被称为社会性昆虫,因为它具备组成社会的三个要素:除了有组织?有分工,还有相互通信和信息的传递?生物学家和仿生学家发现,蚁群有着奇妙的信息系统?寻找食物时,蚂蚁倾向于跟随信息素浓度高的轨迹?这些轨迹是由觅食的蚂蚁个体在行进过程中留下的,以指导其他个体朝相同食物源方向前进?被访问得越多的地方,其信息素的浓度就越高?由于蚂蚁在寻找食物源和返回巢穴时的访问,邻近巢穴的道路上聚焦了浓度更高的信息素[37]
从蚂蚁群体寻找最短路径的觅食行为中受到启发,意大利学者Dorigo等
1991年提出了一种模拟自然界蚂群行为的优化算法———蚁群优化ant colony optimization,ACO算法以下简称蚁群算法?蚁群算法使用人工信息素轨迹作为群体中简单Agent之间的通信方式?信息素轨迹作为蚂蚁使用的分布式的数值信息,以概率构造问题的解?模拟蚂蚁的搜索经验,问题的潜在解依照信息素更新规则和概率转换规则被不断修改[38]?
蚁群算法具有分布计算?信息正反馈和启发式搜索的特征,最初用于求解旅行商问题,此后在多种组合优化问题中获得了广泛的成功应用[39,40]?
1.2.5 粒子群优化算法
粒子群优化particle swarm optimization,PSO算法是Kennedy和Eberhart受人工生命研究结果的启发?通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法[41]?1995年,IEEE国际神经网络学术会议发表了题为Particle swarm optimization的论文,标志着粒子群优化算法的诞生?它与其他进化算法一样,也是基于“种群”和“进化”的概念,通过个体间的协作与竞争,实现复杂空间最优解的搜索;同时,粒子群优化算法又不像其他进化算法那样对个体进行交叉?变异?选择等进化算子操作,而是将群体swarm中的个体看做在犇维搜索空间中没有质量和体积的粒子particle,每个粒子以
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
