搜索
高级检索
高级搜索
书       名 :
著       者 :
出  版  社 :
I  S  B  N:
出版时间 :
无库存
学习型智能优化算法及其应用/排序与调度丛书
0.00     定价 ¥ 99.00
泸西县图书馆
此书还可采购1本,持证读者免费借回家
  • ISBN:
    9787302514695
  • 作      者:
    邢立宁,陈英武,向尚
  • 出 版 社 :
    清华大学出版社
  • 出版日期:
    2019-07-01
收藏
荐购
编辑推荐

智能优化方法的新思路、新手段,将各种优化算法集成起来构成新的高效优化方法。

展开
作者简介

佛山科学技术学院特聘三级教授,2009在国防科学技术大学获管理学博士,主要研究方向为智能优化、资源调度及任务规划等。博士论文被评为全国优秀博士学位论文,在国内外期刊上发表80余篇论文(SCI检索30余篇),所发论文共被引用700余次,一篇论文入选ESI引用前1%论文,六篇论文入选ESI引用前10%论文。相关研究成果分别荣获湖南省自然科学二等奖(第二完成人)、吴文俊人工智能科学技术二等奖(独立署名)和武警科学技术进步二等奖(第四完成人)。入选湖湘青年科技创新创业平台培养对象和教育部“新世纪优秀人才支持计划”;获得国防科学技术大学杰出青年项目和湖南省自然科学杰出青年基金项目。出版专著4部,获得11项国家发明专利授权,主持国家自然科学基金等项目10余项,目前正在带领团队研发面向新型遥感卫星的星上自主任务规划平台。

展开
内容介绍

  《学习型智能优化算法及其应用/排序与调度丛书》在现有智能优化方法的基础上,探索学习型智能优化方法的基本框架。书中采用智能优化模型和知识模型相结合的集成建模思路,总结了精英个体知识、构件知识、算子知识和参数知识4种知识形式,构建了用于实现学习型智能优化方法的8类典型知识,以此辅助学习型智能优化方法高效地求解复杂优化问题。针对连续优化问题、离散优化问题(非对称旅行商问题、双层CARP优化问题、柔性作业车间调度问题)和实际工程问题(体系仿真优化问题、卫星地面站系统任务调度问题、多星任务规划问题),分别设计了若干种学习型智能优化算法,并对优化结果进行了分析和解释。
  《学习型智能优化算法及其应用/排序与调度丛书》主要面向在运筹学领域研究智能优化方法的企业、高校与科研院所的研究人员,帮助读者了解学习型智能优化算法的基本原理与框架流程,提高读者对学习型智能优化算法的实践与应用能力,促进学习型智能优化算法的发展与完善。

展开
精彩书摘

第1章绪论


1.1背景及意义

1.1.1背景


在工业、农业、国防、工程、交通、金融、化工、能源和通信等许多领域都存在着大量的“寻优”需求。“寻优”可简要地概括为[1]: 在满足既定约束条件下,寻找一组比较合适的参数值,使待研究系统的某些性能指标达到最大或最小。优化在资源利用、结构设计、调度管理和后勤供应等许多领域已产生了巨大的经济效益和社会效益,同时在结构力学、生命科学、材料科学、环境科学、控制论等其他领域也有着非常广泛的应用。优化方法是一种以数学为基础,用于求解各种最优化问题的应用技术,优化方法理论和技术历来受到人们的广泛重视[1]。最优化问题根据优化变量的取值类型可分为连续优化问题和离散优化问题两大类。随着科学技术的日益发展,离散优化问题与日俱增,越来越受到管理科学、运筹学、计算机科学及应用数学等诸多学科领域研究人员的高度重视。

在管理科学、计算机科学和工程学等学科及诸多应用领域中,不断涌现出许多大型复杂优化问题。面对这些问题,传统优化方法如牛顿法、共轭梯度法、模式搜索法和单纯形法等需要遍历整个搜索空间,从而产生搜索的组合爆炸,即无法在多项式时间内完成搜索。大型复杂优化问题通常都属于NP难问题。鉴于实际工程问题的复杂性、约束性、非线性和建模困难等特点,探索高效的优化算法已成为相关学科的主要研究方向之一。

自然界中许多自适应优化现象不断地启示着人类[2]: 生物体和自然生态系统通过自身演化就能比较满意地解决许多复杂问题。计算机科学家们不断地从生物系统研究中获得灵感,并通过模仿自然世界的内在机制去获取解决复杂优化问题的新方法。20世纪80年代以来,一些智能优化方法如遗传算法(源自达尔文的自然界进化理论)、蚁群算法(模拟蚂蚁的集体觅食行为)和神经网络(模拟大脑结构和思维过程)等,通过模拟某些自然现象或过程而产生、发展并不断成熟,为解决复杂工程问题提供了新思路和新手段。智能优化方法的出现极大地丰富了最优化技术,也为那些用传统优化技术难以处理的组合优化问题提供了切实可行的解决方案。

智能优化方法模拟自然界的生物系统,依赖生物体的自身本能,通过无意识的寻优行为来优化其生存状态。智能优化方法根据所使用智能体的数量可分为基于个体的智能优化方法和基于种群的智能优化方法,其中模拟退火算法等是基于个体的智能优化方法,而遗传算法、蚁群算法和粒子群优化算法等都是基于种群的智能优化方法。基于种群的智能优化方法的主要特点可概括为[2]: 

 是一类不确定的优化算法。不确定性体现了自然界生物的生理机制,并且在求解某些问题时优于确定性算法。

 是一类概率型的全局搜索算法。随着搜索过程的不断推进,找到优质解的概率大于得到劣质解的概率,能以更大概率求得全局最优解。

 在优化过程中不依赖于优化问题本身的某些数学特性。如目标函数和约束条件的精确数学描述、目标函数的连续性及可导性等。

 是一类基于多个智能体的算法。各个智能体之间通过相互协作来更好适应环境,以获取所需性能。

 具有潜在的并行性。搜索过程同时从多点出发,分布式并行模式极大提高了整个算法的运行效率、鲁棒性和反应能力。

 具有学习能力。在复杂的、不确定的、时变的环境中,能通过自我学习不断提高个体的适应性。

智能优化方法的现有研究主要集中在三个方面[1]: 对现有智能优化方法进行改进并广泛应用,对其理论进行深入研究; 开发新的智能优化工具,拓宽其应用领域,并对其寻求理论基础; 各种现有智能优化方法的混合。算法性能(精度和速度)的提高是永无止境的,提高现有智能优化方法处理各种工程问题的性能,并对其进行理论研究已成为当前智能优化领域研究的首要任务和热点问题。

1.1.2动机

根据搜索方法的发展历程(图1.1),可将现有的搜索方法分为以下三类: 古典搜索方法、启发式搜索方法和智能优化方法。

 古典搜索方法。如步长加速法、旋转方向法、单纯型调优法、方向加速法、枚举法和随机搜索方法等。古典搜索方法仅通过比较目标函数值的大小来移动迭代点,它的搜索策略像是“跟着感觉走”。

 启发式搜索方法。如共轭梯度法、牛顿型方法和变尺度法等。启发式搜索方法有一套严密的理论体系,通过比较目标函数的梯度值来移动迭代点,可看作是“梯度信息启发下的简单智能搜索”。启发式搜索方法将优化问题的梯度信息引入优化过程中,采用目标函数的梯度值来引导优化方法的寻优过程。相对于古典搜索方法,启发式搜索方法能更快地搜索到优化问题的最优解。



图1.1搜索方法的发展历程



 智能优化方法。如模拟退火算法、遗传算法、禁忌搜索、进化规划、进化策略和蚁群算法等。智能优化方法在优化流程上均是一种“邻域搜索”结构。智能优化方法在一定程度上把优化问题的领域知识隐含地加入到算法中。如在遗传算法中,通过选择、交叉和变异操作,将优化问题的较优个体的一些部件特征(component characteristic)逐步地保留下来; 在蚁群算法中,通过信息素将优化问题较优个体的一些部件特征逐步地保留下来。与启发式搜索方法相比,智能优化方法能较好地解决大规模复杂系统中出现的组合爆炸问题,不仅具有通用、稳健、简单、便于并行处理等优点,而且有望成为数值计算与语义表达、形象思维等高级智能行为之间相互联系的桥梁。智能优化方法的研究在一些采用传统方法难以解决或无法解决的应用领域中取得了重大突破。

在现有智能优化方法中,还没有大量直接地挖掘、存储和应用待求解问题的相关领域知识,还不能最有效地得到最优解。在现实生活中,实际系统的规模越来越大,约束条件越来越多,系统结构越来越复杂,多准则、非线性、不可微、不确定已成为这些复杂系统的基本特征。探寻适合大规模计算且具有智能特征的问题求解方法已成为相关学科的研究热点和重要研究方向。

本书认为在求解复杂优化问题时,可从优化过程中直接挖掘一些待求解问题的相关知识,然后应用知识来指导后续优化过程。本文更多地关注一些显性知识,即能明确表达的知识。显性知识可采用计算机语言来表示和存储,其他模型可通过给定方式对这些知识进行更新和应用。鉴于此,本书提出一类学习型智能优化方法: 采用知识模型和智能优化模型相结合的集成建模思路,以智能优化模型为基础,同时突出知识模型的作用,将智能优化模型和知识模型进行优化组合、优势互补,以提高学习型智能优化方法的效率。

学习型智能优化方法研究的难点主要表现在以下方面: 

 学习型智能优化方法的基本框架。构建一种比较通用的优化框架,将智能优化方法和知识模型进行优化组合、优势互补,以提高学习型智能优化方法的效率。

 知识的定义。构建用于实现学习型智能优化方法的若干典型知识,这些典型知识可辅助学习型智能优化方法高效地求解复杂优化问题。

 设计并实现若干种比较典型的学习型智能优化方法。针对一些连续优化问题、 组合优化问题或实际工程问题,设计并实现若干种比较典型的学习型智能优化方法,这些方法稍加修改就可推广到其他复杂优化问题的求解中。

1.2智能优化方法

智能优化方法的主要思想来源于人类对物理、生物和社会等自然现象的长期观察和深刻理解。智能优化方法的特点就是仿自然,如仿人类思维(神经网络、禁忌搜索等)、仿生物行为(粒子群优化、蚁群优化等)和仿物理原理(模拟退火、微正则退火等)。这些方法从随机的可行初始解出发,采用优胜劣汰策略,在可接受的计算成本内去搜寻满意解。虽然不能保证最终一定能求得最优解,但智能优化方法能在搜索精度和算法复杂度之间达到某种平衡。智能优化方法已成为解决优化问题特别是NP难问题的一种有力工具,在优化领域得到了非常广泛的应用。

常用的智能优化方法有以下几种: 

(1) 模拟退火(simulate anneal)。模拟退火是基于Monte Carlo迭代求解策略的随机寻优算法,其出发点是固体物质退火过程与组合优化问题的相似性; 从某一初温开始,随着温度的降低,结合概率突跳特性在解空间中搜索最优解,即在局部解时能概率性地跳出并最终趋于全局最优。

(2) 遗传算法(genetic algorithm)。遗传算法是一种通过模拟自然进化过程搜索最优解的方法。它将问题求解表示成染色体适者生存过程,通过染色体的逐步迭代,最终收敛到最适应环境的个体(优化问题的最优解或满意解)。

(3) 禁忌搜索(tabu search)。禁忌搜索是一种全局逐步优化算法,它模拟人类的智力过程,通过引入一种灵活的存储结构和相应的禁忌规则来避免迂回搜索,并通过藐视原则来赦免一些被禁忌的优良状态,以实现全局优化。

(4) 进化规划(evolution programming)。进化规划过程可理解为从所有可能的计算机程序中,搜索具有高适应度的计算机程序个体。进化规划最初由随机产生的计算机程序群体开始,计算机程序由适合问题空间领域的函数组成,函数可以是算术运算函数、编程操作、逻辑函数或领域函数。群体中每个计算机程序个体都是用适应度来评价的,该适应度的取值与特定问题领域有关。

(5) 进化策略(evolution strategy)。进化策略通过模仿自然进化原理来求解参数优化问题。进化策略和遗传算法的区别包括: 表示个体的方式不同,进化策略在浮点矢量上运行,而遗传算法一般运行在二进制矢量上; 选择过程不同; 复制参数不同,遗传算法的复制参数(交叉和变异的可能性)在进化过程中保持恒定,而进化策略动态地改变它们。随着技术的发展,进化策略和遗传算法的差别越来越不明显。

(6) 蚁群算法(ant colony optimization)。蚁群算法是受自然界中蚂蚁搜索食物行为的启发而提出的一种随机优化算法。蚂蚁间借助于信息素这种化学物质进行信息的交流和传递,并表现出正反馈现象: 某段路径上经过的蚂蚁越多,该路径被重复选择的概率就越高。正反馈机制和通信机制是蚁群算法的两个重要基础。

(7) 人工神经网络(neural network)。人工神经网络是一种模仿动物神经网络行为特征,进行分布式并行信息处理的数学模型。人工神经网络具有自学习和自适应能力,可通过预先提供的相互对应的输入数据和输出数据,分析掌握两者之间的潜在规律,最终根据这些规律,用新输入数据来推算输出结果。

1.3知识导向的智能优化算法

智能优化算法是当前研究的热点问题,其主要缺点是容易出现早熟收敛和收敛速度慢。导致这些缺点的一个重要原因就是智能优化算法中缺乏明确的导向因子。国内外学者一方面通过传统人工智能手段和特定知识模型来实现对智能优化算法的进化引导,同时也采用具有双层进化机制的文化算法对智能优化算法进行引导。

1.3.1传统人工智能引导的智能优化算法

采用传统人工智能手段对智能优化算法进行引导,如采用禁忌搜索[3]、文化算法[4]和机器学习[5]来控制进化等[6]。在具体实施时,必须首先抽取一些进化过程中尽可能一般和重要的规则,利用禁忌搜索、文化算法和机器学习等算法进行学习,然后根据学习得到的规则控制个体进化。这些工作的缺点在于很难找到尽可能一般和重要的规则,而且这些规则缺乏全局性,没有考虑到随着个体的进化,个体所处的环境也在不断变化,因而相应的规则也应该变化[6]。

为了平衡进化过程中选择操作正向作用和交叉(变异)操作破坏性影响,范磊等采用归纳学习方法来引导进化过程[7]: 采用归纳学习方法从进化历史进程中抽取出能反映过去进化的错误和成功的规则,进而用它们来引导后续进化过程,保证在避免重复错误的同时加速进化。基于函数优化和布局求解的实验验证了其有效性。

曹先彬等借鉴个体进化的生命周期性,提出了一种基于生命期引导的生态进化模型[8]。基于此模型的算法在个体生命期的各个阶段设置了相应的引导算子,使个体在整个生命期都基于其生态特征而被引导进化。实验结果验证了其优越性。

为了提高粒子群算法中粒子搜索全局最优解的准确度,岑宇森等提出了基于知识空间的分组式粒子群算法[9]。该算法使用kmeans算法对粒子群进行分组,利用较小的最大飞行速度加强粒子在组内的局部搜索能力,并将“知识空间”的概念引入到分组中,由知识空间中的粒子来引导群中粒子前往更好的解空间搜索。

李亚男等在遗传算法中采用专家知识辅助寻优,并将该改进遗传算法应用到无功规划优化中[10]。依据专家知识对少数被选中的个体动态形成本厂、站的就地无功/电压控制的有效变量集进行人工调整,可改善遗传算法的局部寻优能力。对某实际系统的计算表明,结合专家知识的遗传算法能够更有效地找到全局最优。

柴啸龙将领域知识通过禁忌连接集的形式加入蚁群规划算法中[11],相邻动作层的很多互斥信息通过禁忌连接集只需计算一次,不进入主循环计算中,这样可以较好地提升算法的执行效率。实例分析表明这一策略是有效的。

1.3.2特定知识模型引导的智能优化算法

采用特定知识模型对智能优化算法进行引导时,在智能优化算法运行之初就已确定了知识的基本形式,  相关知识按照固定规则随着算法演化而不断调整,然后采用已获得知识来指导后续个体的进化。采用特定知识模型对智能优化算法进行引导也可理解为演化与学习之间的交互(interaction between evolution and learning)[1217]。

根据现有文献,研究人员一般通过以下两种途径来实现演化和学习之间的交互[18]: 学习已获得个体的一些优良特征,采用这些优良特征来改进后续产生的个体; 学习已获得个体的一些不良特征,采取措施防止这些不良特征出现在后续个体中。现有研究表明: 演化和学习之间的交互是可能的,可采用多种途径来实现演化和学习之间的交互,例如版本空间(version space)[19]、基于案例的记忆单元[20]、Q学习系统(Qlearning system)[21,22]和AQ学习系统(AQlearning system)[23]等。通过演化和学习之间的交互可有效提高智能优化方法的优化效率[18]。

1.3.2.1采用记忆单元对智能优化算法进行引导

很多学者尝试采用记忆单元(memory cell)来实现演化和学习之间的交互。Chung和Reynolds将个体优良特征看作是信念(beliefs),将这些信念保存到记忆单元中,采用这些信念来改进后续个体[24]。Branke将一些已获得的较优个体保存到记忆单元中,采用这些较优个体来改进后续个体[25]。

Gantovnik等采用记忆单元在遗传算法中实现演化和学习之间的交互[26,27],并使用这种改进遗传算法来解决混合变量优化设计问题。Louis和Li采用带有记忆单元的遗传算法来求解旅行商问题[28]。Yang采用基于记忆单元的移民方式在遗传算法中实现演化和学习之间的交互[29,30],并使用这种改进遗传算法求解动态优化问题。

苏淼等采用免疫记忆方式在蚁群算法中实现演化和学习之间的交互[31],并使用这种改进蚁群算法来求解武器目标分配问题。Acan使用外部记忆单元(external memory)在蚁群算法中实现演化和学习之间的交互[32]。在此基础上,Acan在外部存储器中加入了局部置换(partial permutations)功能[33],进一步提高了改进蚁群算法的效率。Shamsipur使用外部记忆单元在蚁群算法中实现演化和学习之间的交互[34]。

1.3.2.2基于案例对智能优化算法进行引导

很多学者也采用案例(case)在智能优化方法中实现演化和学习之间的交互[20,35,36]。Louis和McDonnell采用案例推理(casebased reasoning)方法从案例记忆单元(casebased memory cell)中选择特征来改进后续个体[20]。Louis和Li在遗传算法中采用案例注入方式来实现演化和学习之间的交互[35],并使用这种改进遗传算法来求解旅行商问题。Rasheed和Hirsh采用案例学习方式在遗传算法中实现演化和学习之间的交互[36]。BabbarSebens和Minsker提出了一种基于案例的宏观交互式遗传算法(casebased  micro  interactive  genetic  algorithm)[37],主要通过案例记忆单元和案例推理来实现演化和学习之间的交互。

1.3.2.3采用学习演化模型对智能优化算法进行引导

不同于基于达尔文进化论的演化计算方法,学习演化模型(learnable  evolution  model,LEM)主要采用机器学习方法来指导整个演化进程。Coletti对学习演化模型进行了初步研究[38],Wojtusiak研究了学习演化模型中的约束优化问题[39],Kaufman和Michalski采用学习演化模型来解决热交换器设计问题[40],Jourdan等使用学习演化模型来解决多目标水系统设计问题[41],Domanski等采用学习演化模型来求解优化设计问题[42]。目前,学习演化模型的最新版本为LEM3。Wojtusiak和Michalski应用LEM3来解决复杂函数优化问题[43]。

近年来,越来越多的学者开始使用学习演化模型在智能优化方法中实现演化和学习之间的交互[18,23]。Michalski等在总结学习演化模型最新进展[44]的基础上,在智能优化方法中采用学习模型来实现演化和学习之间的交互[45]。在Michalski构建的学习演化模型中,主要采用机器学习方法来实现演化和学习之间的交互[23]。Ho等采用学习型遗传框架(learnable genetic architecture,LEGA)来实现演化和学习之间的交互[18]。Wojtusiak设计了一种可用于多种智能优化方法的LEM3系统[46]。


展开
目录

第1章 绪论
1.1 背景及意义
1.1.1 背景
1.1.2 动机
1.2 智能优化方法
1.3 知识导向的智能优化算法
1.3.1 传统人工智能引导的智能优化算法
1.3.2 特定知识模型引导的智能优化算法
1.3.3 具有双层进化机制的文化算法
1.4 章节结构

第2章 学习型智能优化方法
2.1 学习型智能优化相关理论
2.1.1 知识
2.1.2 知识模型
2.1.3 遗传算法
2.1.4 蚁群算法
2.1.5 学习型智能优化的基本框架
2.1.6 学习型智能优化的运行机制
2.2 学习型智能优化中的知识
2.2.1 精英个体知识
2.2.2 构件知识
2.2.3 算子知识
2.2.4 参数知识
2.3 学习型智能优化算法的框架与流程
2.3.1 求解函数优化问题的学习型遗传算法框架与流程
2.3.2 求解非对称旅行商问题的学习型遗传算法框架与流程
2.3.3 求解双层CARP优化问题的学习型遗传算法框架与流程
2.3.4 求解双层CARP优化问题的学习型蚁群算法框架与流程
2.3.5 求解柔性作业车间调度问题的学习型蚁群算法框架与流程
2.3.6 求解柔性作业车间调度问题的学习型协同进化算法框架与流程
2.3.7 求解体系仿真优化问题的学习型遗传算法框架与流程
2.3.8 求解卫星地面站系统任务调度的学习型蚁群算法框架与流程
2.3.9 求解多星任务规划问题的学习型蚁群算法框架与流程
2.4 本章小结

第3章 求解函数优化问题的学习型遗传算法
3.1 问题描述及特点分析
3.2 求解过程
3.2.1 种群初始化
3.2.2 选择操作
3.2.3 交叉操作
3.2.4 变异操作
3.2.5 灾变操作
3.2.6 终止条件
3.3 实验结果及分析
3.3.1 参数设置
3.3.2 几种典型的函数优化方法
3.3.3 普通测试函数的实验结果
3.3.4 组合测试函数的实验结果
3.4 本章小结

第4章 求解非对称旅行商问题的学习型遗传算法
4.1 问题描述及特点分析
4.1.1 旅行商问题描述
4.1.2 旅行商问题的分类
……
第5章 求解双层CARP优化问题的学习型遗传算法和学习型蚁群算法
第6章 求解柔性作业车间调度问题的学习型蚁群算法和学习型协同进化算法
第7章 求解体系仿真优化问题的学习型遗传算法
第8章 求解卫星地面站系统任务调度的学习型蚁群算法
第9章 求解多星任务规划问题的学习型蚁群算法
第10章 总结与展望
参考文献
索引
附录

展开
加入书架成功!
收藏图书成功!
我知道了(3)
发表书评
读者登录

温馨提示:请使用泸西县图书馆的读者帐号和密码进行登录

点击获取验证码
登录