一种改进的关键工序算法
刘智勇 徐昕
江苏科技大学经济管理学院，江苏 镇江 212003
摘要：针对max ///n m p F 问题，改进了关键工序法法，该算法同时注重关键工件与关键工序，通过对关键工件与非关键工件在关键工序前后的加工时间计算、比较来获得各工件加工的先后顺序，缩短最长流程时间。并将该启发式算法与关键工序法进行了对比分析，最后利用仿真的方法来验证所提出的方法的可行性。
关键词：Flow-shop 关键工件 关键工序 启发式算法 最长流程时间 0引言
Flow-shop 调度问题（flow shop scheduling problem,FSP ）是许多实际流水线生产调度问题的简化模型，它无论是在离散制造工业还是在流程工业中都具有广泛的应用，因此其研究具有重要的理论意义和工程价值。n/m/p/F max 问题是Flow-shop
调度问题中的一种特殊情况，即所有工件在各台机器上的加工顺序都相同，也称流水作业排列排序问题或同顺序排序问题。其求解方法有精确方法
[1]（分支定界法、穷举法等）、智能搜索法
[2,3,4]（神经网络法、遗传算法、蚁群算法等）、启发式算法[4,5,6,7]（Palmer 算法、C-D-S 法、关键工序法、最小排序系数法等）等等。由于Flow-shop 调度问题一般都属于NP 难题(nondeterministic polynomial)。精确方法只能求解小规模问题，对于大规模问题几乎被认为是无效算法，智能搜索法在求解上虽比启发式算法更接近最有解，但由于设计针对具体问题的智能搜索法对于许多人来说比较困难，特别是对于实际工程人员更是如此。所以启发式算法仍是用的很多的方法。主要的启发式算法有Palmer 算法、关键工序法和最小排序系数法等。其中，关键工序法贯穿着当前先进的管理思想，能够很好的对现实情况进行解释和分析。然而关键工序法所求的可行解很可能与最优解相差甚远，鉴于此，本文对其进行了改进。
1 max ///n m p F 问题描述
max
///n m p F 问题可以描述为：有n 个工件在m 台机器上加工，各工件有完全相
同的工艺路线，每一台机器上加工工件的先后顺序也完全相同；一个工件不能同时在不同的机器上加工；每台机器同时只能加工一个工件；各工件在加工完后立即送下一道工序；工件在机器上开始加工，必须一直进行到该工序完工，中途不允许停下来插入其它工件；所有工件在0时刻已准备就绪，机器调整时间包括在加工时间内；
允许工件在工序之间等待，允许机器在任务未到达时闲置；优化目标是求出这n 个任务的一个全排列，使其最长流程时间（也称加工周期）max F 最短，则max F 的计算方法如下：
,00,,11,1,1,,11,,max
,00max(,)(1,2,,1,2,,i j i i i i j
i j i j i j n m C C C C t C C C t F C i n j m ---==??=+??=+??==???=????；其中；） 上式中,i j C 代表工件i 在机器j 上的完工时间，
,i j t 代表工件i 在机器j 上的加工时间。
2改进的关键工序法
改进的关键工序法要求抓住关键工序和关键工件，定义关键工序为各道工序上加工各个工件总时间最长的工序；定义关键工件为各个工件在各道工序加工总时间最长的工件。若关键工件都多个，则按照各关键工件首道工序加工时间与尾道工序加工时间的大小分组，首道工序加工时间小于尾道的工件为第一组，首道工序加工时间等于尾道的工件第二组，首道工序加工时间大于尾道的工件为第三组，优先顺序为{第一组，第二组，第三组}，对于第一组中的各关键工件之间的排序则按关键工序前各道工序总加工时间从小到大排序，对于第三组的各关键工件之间的排序则按关键工序后各道工序总加工时间从大到小排序，第二组的各关键工件的排序时需先比较第一组与第三组内的工件个数，当第一组的工件个数少于或等于第三组时，第二组内工件按第一组规则排，否则按第三组的规则排。
对关键工件以外的所有工件同样比较首道工序加工时间与尾道工序加工时间，按小于、等于、大于分为三组，其组内排序规则与关键工件个组内排序规则相同。最后按{非关键工件第一组，非关键工件第二组，关键工件第一组，关键工件第二组，关键工件第三组，非关键共建第三组}的顺序进行总排序，即可获得满意的max F 。对于关键工序为首道工序的情形，就把次关键工序看成是上述的关键工序，排序步骤不变。
用数学语言表示如下：
Step1: 对i ?，计算,*,1m i i j j t t ==∑，对j ?，计算*,,1n
j i j i t t ==∑，
定义{}",*1,*2,*,*|max(,,,)i n i A i t t t t ∈==???为关键工件，
定义{}"*,*,1*,2*,|max(,,,)j m j B j t t t t ∈==??? 为关键工序。
Step2:：若()1Card A >（其中()Card 表示括号中集合包含元素的个数）， 则⑴{}"""1,1,|i i m A i t t =<≠?，则计算""1,1
j i j j t -=∑的值，按该值从小到大排列获得"i 一
４２２０１０．４６（６）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 博弈树置换表启发式算法研究 焦尚彬，刘丁 ＪＩＡＯＳｈａｎｇ－ｂｉｎ，ＬＩＵＤｉｎｇ 西安理工大学信息与控制工程研究中心，西安７１００４８ Ｘｉ’ａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｘｉ’ａｎ７１００４８，Ｃｈｉｎａ Ｅ－ｍａｉｌ：ｊｉａｏｓｈａｎｇｂｉｎ＠ｘａｕｔ．ｅｄｕ．ｃａ ＪＩＡＯＳｈａｎｇ－ｂｉｎ。ＬＩＵＤｉｎｇ．Ｒｅｓｅａｒｃｈｏｎｔｒａｎｓｌａｔｉｏｎｔａｂｌｅｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２０１０．４６（６）：４２－４５． Ａｂｓｔｒａｃｔ：Ｓｅａｒｃｈｉｎｇｉｓｅｓｓｅｎｔｉａｌｆｏｒｃｏｍｐｕｔｅｒ－ｇａｍｅｏｆｂｏａｒｄｇａｍｅｓ．Ａｎｄｅｘｃｅｌｌｅｎｔｓｅａｒｃｈａｌｇｏｒｉｔｈｍｍａｙｏｂｔａｉｎｔｈｅｏｐｔｉｍａｌｐａｔｈ ｂｙｓｅａｒｃｈｉｎｇｆｅｗｎｏｄｅｓ，ａｎｄｉｍｐｒｏｖｅｔｈｅｃｏｍｐｅｔｉｔｉｖｅｌｅｖｅｌｏｆｃｏｍｐｕｔｅｒｇａｍｅ．ＴｈｉｓｐａｐｅｒｓｅｔｓＣｈｉｎｅｓｅｃｈｅｓｓｃｏｍｐｕｔｅｒｇａｍｅａｓｂａｃｋｇｒｏｕｎｄ，ａｎｄｏｎｔｈｅｂａｓｉｓｏｆａｌｐｈａ－ｂｅｔａａｌｇｏｒｉｔｈｍ，ｉｔｍａｋｅｓａｄｅｔａｉｌｅｄｄｅｓｃｒｉｐｔｉｏｎａｂｏｕｔｔｈｅｐｒｉｎｃｉｐｌｅｏｆｔｒａｎｓｌａｔｉｏｎｔａｂｌｅｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍａｎｄｈａｓｈｃｏｌｌｉｓｉｏｎ，ａｎｄｔｈｅｒｅｐｌａｃｅｍｅｎｔｓｃｈｅｍｅｓｏｆｔｗｏ－ｌｅｖｅｌｔｒａｎｓｐｏｓｉｔｉｏｎｔａｂｌｅｉｓｐｒｏｐｏｓｅｄ，ｅｎｈａｎｃｉｎｇｔｈｅｅｆ－ｆｉｃｉｅｎｅｙｏｆｓｅａｒｉｎｇｅｎｇｉｎｅ．Ａｔｌａｓｔ，ｔｈｅｅｘｐｅｒｉｍｅｎｔｒｅｓｕｌｔｓｖｅｒｉｆｙｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅｍｅｔｈｏｄｓ． Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｕｔｅｒｇａｍｅ；ｓｅａｒｃｈｉｎｇｔｒｅｅ；ｔｒａｎｓｌａｔｉｏｎｔａｂｌｅｈｅｕｒｉｓｔｉｃ；ａｋ＇ｈａ－ｂｅｔａａｌｇｏｒｉｔｈｍ 摘要：博弈树搜索对于计算机博弈至关重要。优秀的搜索算法通过搜索较少的节点就可以获得最佳路径，从而提高计算机的博弈水平。论文以中国象棋计算机博弈作为背景，在ａｌｐｈａ－ｂｅｔａ基本搜索算法上，详细阐述了置换表启发算法的原理和哈希冲突，引进了双层置换表的概念及其替换策略，增强了引擎的搜索效率。实验结果表明了该算法的有效性。 关键词：计算机博弈；博弈树；置换表岩［；ａｌｐｈａ—ｂｅｔａ算法 ＤＯＩ：１０．３７７８０．ｉｓｓｎ．１００２—８３３１．２０１０．０６．０１２文章编譬：１００２—８３３１（２０１０）０６－００４２－－０４文献标识码：Ａ中图分类号：，ＩＰｌ８ １引言 汁算机博弈的核心是搜索，一盘完整的棋局需要考虑约４５９０一１０啪种局面，因而就目前的电脑硬件水平无法实现“象棋不败算法”ｆｌｌ。１９５０年香侬教授（ＣｌａｕｄｅＳｈａｎｎｏｎ）首先提出了“极大一极小算法”，奠定了计算机人机博弈的理沦基础１２－３１。Ｂｒｕｎｏ在１９６３年提出了ａｌｐｈａ—ｂｅｔａ算法１４１，１９７５年Ｋｎｕｔｈ和Ｍｏｏｒｅ给出了其数学正确性证明嘲。ａｌｐｈａ－ｂｅｔａ是所有剪枝算法的基础，但其效率与子树节点搜索的先后顺序密切相关，因此启发算法的目的就是尽可能首先找出最佳着法。其中，历史启发ｆ日和杀手启发算ｉ去Ｉ，嘟是针对多次搜索的节点排序，具有较高的效率，但没有根据象棋里经常会有重复局面出现的特征来很好利用前面搜索的结果；吃子启发算法㈣根据当前吃对方棋子所能取得的好处排序，符合象棋的特征，但一般局面的吃子着法极少，并且吃子也并不一定就是最佳着法，甚至有可能贪吃一子导致满盘皆输；置换表启发１９１充分利用了象棋里重复局面多次出现的特征，弥补了上述启发算法的不足。 目前，对于单置换表策略主要有深度优先（ＤｅｅｐｅｒＰｒｉｏｒｉ—ｔｙ）和随时替换（ＡｌｗａｙｓＲｅｐｌａｃｅ）两种。深度优先策略主要基于深度的考虑，忽略了棋局不断演变产生的新棋局信息对以后局势的影响，无法保证棋局信息的实时性，从而降低了置换表的效率，有时甚至引发非法剪枝。而随时替换策略虽然充分考虑了棋局新信息，具有较好的实时性，但却丢掉了拥有较深层数的棋局数据，浪费了资源并增加了搜索时间，效率不如深度优先策略（下文验证实验结果证明了这一结论）。基于以上考虑，利用上述两种置换策略的优点，引入双置换表（Ｔｗｏ－ｌｅｖｅｌＴｒａａｓ— ｐｏｓｉｔｉｏｎＴａｂｌｅ（Ｔｗｏ—ｌｅｖｅｌＴＹ））策略，并且应用Ｚｏｂｆｉｓｔ哈希技术解决了置换表的存取速度慢及存储窄间庞大等问题，分析了 置换冲突并给出了风险降低措施。将该策略与ａｌｐｈａ－ｂｅｔａ搜索算法相结合，实验结果表明，既具有较高的实时性又对已有数据有较好的利用率。 ２ａｌｐｈａ—ｂｅｔａ基奉原理 对于程序而言，考虑对弈双方的每一种着法，就形成了博弈树。一棵深度为３的博弈树如图１所示。 黑 圈１深度为３的博奔树结构图 ＤｅｐｔｈＯ Ｄｅｐｔｈｌ Ｄｅｐｔｈ２ Ｄｅｐｔｈ３ 作者简介：焦尚彬（１９７４一），男，博士，副教授．主要研究领域为智能控制、状态检测；刘丁（１９５７一），男，博士，博士生导师，长期从事工业自动化、智能控制理论与应用等方面的研究。 收稿日期：２００８—０９—１９修１＂１日期：２００８—１２—１０ 万方数据
启发式搜索 1. 介绍 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 使用启发式搜索算法求解8数码问题。 1) A ，A 星算法采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2) 宽度搜索采用f(i)为i 的深度，深度搜索采用f(i)为i 的深度的倒数。 3. 算法流程 ① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ； ② 如果OPEN 是空表，则失败退出，无解； ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； ④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； ⑤ 如果i 是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： 计算)(j f ；如果j 既不在OPEN 表中，又不在CLOCED 表中，则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在OPEN 表或CLOSED 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，则 (I)以此新值取代旧值。 (II)从j 指向i ，而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中，则把它移回OPEN 表中。 ⑦ 转向②，即GOTO ②。
基于仿真的优化方法综述 作者：东汪定伟 1 引言 人们对复杂事物和复杂系统建立数学模型并进行求解的能力是有限的，目标函数和约束条件往往不能以明确的函数关系表达，或因函数带有随机参、变量，导致基于数学模型的优化方法在应用于实际生产时，有其局限性甚至不适用。基于仿真的优化(Simulation Based Optimization，SBO)方是在这样的背景下发展起来的。 随着优化问题越来越复杂，对优化对象的评价只能通过仿真获得的统计指标来实现。这时，SBO是复杂优化问题的惟一选择。近年来，SBO已成为国际上最热的研究方向。 虽然SBO已经在很多领域得到了应用，但是当前对于SBO的理论研究并不完善，算法仍在不断探索和改进中，新的研究成果不断出现。 2 SBO的研究概况及分类 综观最优化的发展过程，大约经过了以下几个阶段： ①1940～1970年数学规划阶段一目标和约束是解析函数。②1970-2000年智能优化阶段一目标和约束放宽为含有判断逻辑的计算机程序。③2000年一未来基于仿真的优化(SBO)阶段一用大量仿真的统计数据来进行性能评价。 有些学者对SBO做了一些综述工作。Andradottir从连续事件和离散事件两个方面，对SBO 技术作了总结；Azadivar从单目标优化和多目标优化的角度对SBO方法作了论述；在国，湘龙等认为SBO是非枚举地从可能值中找到最佳输入变量值，使得输出结果为最优或满意解的过程。王凌等按照优化方法的不同，对SBO及其改进和应用作了综述。 随着对SBO方法研究的深入，SBO在复杂工程系统的设计优化、供应链和物流系统、制造系统及社会经济系统等领域得到了应用。总结当前的研究和应用情况，可以看出，基于仿真的优化是仿真方法和优化方法的结合，是借助仿真手段实现系统的优化的一种优化方法。
粒子群优化算法综述 摘要：本文围绕粒子群优化算法的原理、特点、改进与应用等方面进行全面综述。侧重于粒子群的改进算法，简短介绍了粒子群算法在典型理论问题和实际工业对象中的应用，并给出了粒子群算三个重要的网址，最后对粒子群算做了进一步展望。 关键词；粒子群算法；应用；电子资源；综述 0.引言 粒子群优化算法]1[(Particle Swarm Optimization ，PSO)是由美国的Kenned 和Eberhar 于1995年提出的一种优化算法,该算法通过模拟鸟群觅食行为的规律和过程，建立了一种基于群智能方法的演化计算技术。由于此算法在多维空间函数寻优、动态目标寻优时有实现容易，鲁棒性好，收敛快等优点在科学和工程领域已取得很好的研究成果。 1. 基本粒子群算法]41[- 假设在一个D 维目标搜索空间中，有m 个粒子组成一个群落，其中地i 个粒子组成一个D 维向量，),,,(21iD i i i x x x x =，m i ,2,1=，即第i 个粒子在D 维目标搜索空间中的位置是i x 。换言之，每个粒子 的位置就是一个潜在的解。将i x 带入一个目标函数就可以计算出其适 应值，根据适应值得大小衡量i x 的优劣。第i 个粒子的飞翔速度也是一个D 维向量，记为),,,(21iD i i i v v v v =。记第i 个粒子迄今为止搜索到的最优位置为),,,(21iD i i i p p p p =，整个粒子群迄今为止搜索到的最优位置为),,,(21gD gi g g p p p p =。 粒子群优化算法一般采用下面的公式对粒子进行操作
)()(22111t id t gd t id t id t id t id x p r c x p r c v v -+-+=+ω (1) 11+++=t id t id t id v x x (2) 式中，m i ,,2,1 =；D d ,,2,1 =；ω是惯性权重， 1c 和2c 是非负常数， 称为学习因子， 1r 和2r 是介于]1,0[间的随机数；],[max max v v v id -∈，max v 是常数，由用户设定。 2. 粒子群算法的改进 与其它优化算法一样PSO 也存在早熟收敛问题。随着人们对算 法搜索速度和精度的不断追求，大量的学者对该算法进行了改进，大致可分为以下两类：一类是提高算法的收敛速度；一类是增加种群多样性以防止算法陷入局部最优。以下是对最新的这两类改进的总结。 2.1.1 改进收敛速度 量子粒子群优化算法]5[:在量子系统中，粒子能够以某一确定的 概率出现在可行解空间中的任意位置，因此，有更大的搜索范围，与传统PSO 法相比，更有可能避免粒子陷入局部最优。虽然量子有更大的搜索空间，但是在粒子进化过程中，缺乏很好的方向指导。针对这个缺陷，对进化过程中的粒子进行有效疫苗接种，使它们朝着更好的进化方向发展，从而提高量子粒子群的收敛速度和寻优能力。 文化粒子群算法]6[:自适应指导文化PSO 由种群空间和信念空间 两部分组成。前者是基于PSO 的进化，而后者是基于信念文化的进化。两个空间通过一组由接受函数和影响函数组成的通信协议联系在一起，接受函数用来收集群体空间中优秀个体的经验知识；影响函数利用解决问题的知识指导种群空间进化；更新函数用于更新信念空间；
实验名称:启发式搜索算法 1、实验环境 Visual C++ 6.0 2、实验目的和要求 （复述问题）使用启发式算法求解8数码问题 （1）编制程序实现求解8数码问题A*算法，采用估价函数 f(n)=d(n)+p（n） 其中：d(n)是搜索树中结点n的深度；w(n)为节点n的数据库中错放的旗子个数； p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。 （2）分析上述（1）中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界h(n)的定义，并测试该估价函数是否使算法失去可采纳性。 实验目的：熟练掌握启发式搜索A*算法及其可采纳性。 3、解题思路、代码 3.1解题思路 八数码问题的求解算法 （1）盲目搜索 宽度优先搜索算法、深度优先搜索算法 （2）启发式搜索 启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。 先定义下面几个函数的含义： f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。 评价函数的形式可定义如(2)式所示： f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。 利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法针对八数码问题启发函数设计如下： F(n)=d(n)+p(n) (4)
·论文· 车辆路径调度问题的启发式算法综述1 杨燕旋1，宋士吉1 (1.清华大学自动化系，北京 100084) 摘要：车辆路径调度问题是一类具有重大研究意义及广泛应用价值的NP难优化问题。本文给出了该问题的定义和基本描述，并将目前为止被应用于求解VRP问题的启发式算法分为构造型启发式算法、改进型启发式算法和人工智能算法这三大类，接着介绍了各类中比较典型的算法，并对算法的应用和研究情况进行了分析和总结，最后对进一步的研究做出了展望。 关键词：物流；车辆路径问题；调度；启发式算法 中图分类号：F252 A Survey on the Heuristic Algorithms for the Vehicle Routing Problem YANG Yan-Xuan,1 SONG Shi-Ji,1 (1.Department of Automation, Tsinghua University, Beijing 100084, China) Abstract：Vehicle Routing Problem is an NP-hard problem with great research and application significance. In this research, we first present the definition of the problem and give a classification to the existed heuristic algorithms for the problem. Then typical algorithms are introduced and research on the algorithms are investigated and summarized. Finally, further research directions are given. Key words：Logistics; Vehicle Routing Problem; Scheduling; Heuristic Algorithm 1959年，Dantzig等人首先从旅行商问题（Traveling Salesman Problem，简称TSP问题，）得到启发，提出了车辆分配问题TDP（Truck Dispatching Problem）。这是一类具有重要研究价值的问题。一方面，它代表了一类典型的组合优化问题，具有深远的理论意义；另一方面，它是一类重要的物流运输问题，直接影响着相关企业的运转效率，具有广泛的实践意义。半个世纪以来，许多的专家学者对该问题进行了广泛而深入的研究，并将这类问题统称为车辆路径调度问题（Vehicle Routing Problem，简称为VRP问题）。他们从基本问题出发，根据 1基金项目：自然科学基金（编号：60574077）、国家“八六三”高技术项目（编号：2007AA04Z102） 作者简介：杨燕旋（1983-），女，汉族，广东，清华大学硕士研究生，从事车辆路径调度方向的研究，E-mail: yyx02@https://www.doczj.com/doc/8d2134528.html,. 宋士吉（1965-），男，汉族，黑龙江，清华大学教授，博导，从事供应链管理等方向的研究，E-mail: shijis@https://www.doczj.com/doc/8d2134528.html,
实验一启发式搜索算法 学号：2220103430 班级：计科二班 姓名：刘俊峰
一、实验内容： 使用启发式搜索算法求解8数码问题。 1、编制程序实现求解8数码问题A *算法，采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2、 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界 的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。 二、实验目的： 熟练掌握启发式搜索A * 算法及其可采纳性。 三、实验原理： （一）问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 启发式搜索:由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个
启发式优化算法
Heuristic Optimization Algorithm
理论与应用 Theory & Application
内容纲要
? ?
优化问题与优化算法 常用的启发式优化算法
模拟退火算法 ? 遗传算法 ? 粒子群优化算法 ? 混合策略优化算法
?
?
讨论
优化问题
?
组合式优化问题
? ? ? ?
七桥问题 最短路径问题 公路连接问题 旅行商问题 无约束函数优化问题 有约束函数优化问题 函数优化+组合优化
?
函数优化问题
? ?
?
混合优化问题
?
七桥问题
?
Euler在1736年访问Konigsberg时，他发现Konigsberg城中有 一条名叫Pregel的河流，河上建有七座桥如图所示: 市民有 趣的消遣活动是星期六作一次走过所有七座桥的散步，每 座桥只能经过一次而且起点与终点必须是同一地点。
Impossible Task!
最短路径问题 SPP－shortest path problem
?
?
?
货柜车司机奉命在最短的时间内将一车货 物从甲地运往乙地。 从甲地到乙地的公路网纵横交错，因此有 多种行车路线，这名司机应选择哪条线路 呢？ 假设货柜车的运行速度是恒定的，那么这 一问题相当于需要找到一条从甲地到乙地 的最短路。
公路连接问题
?
?
某一地区有若干个主要城市，现准备修建 高速公路把这些城市连接起来，使得从其 中任何一个城市都可以经高速公路直接或 间接到达另一个城市。 假定已经知道了任意两个城市之间修建高 速公路成本，那么应如何决定在哪些城市 间修建高速公路，使得总成本最小？
粒子群算法综述 【摘要】：粒子群算法(pso)是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已得到广泛研究和应用。为了进一步推广应用粒子群算法并为深入研究该算法提供相关资料，本文对目前国内外研究现状进行了全面分析，在论述粒子群算法基本思想的基础上，围绕pso的运算过程、特点、改进方式与应用等方面进行了全面综述，并给出了未来的研究方向展望。 【关键词】：粒子群算法优化综述 优化理论的研究一直是一个非常活跃的研究领域。它所研究的问题是在多方案中寻求最优方案。人们关于优化问题的研究工作，随着历史的发展不断深入，对人类的发展起到了重要的推动作用。但是，任何科学的进步都受到历史条件的限制，直到二十世纪中期，由于高速数字计算机日益广泛应用，使优化技术不仅成为迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。这些优化技术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、生产调度等。随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，常规优化法如牛顿法、车辆梯度法、模式搜索法、单纯形法等已经无法处理人们所面的复杂问题，因此高效的
优化算法成为科学工作者的研究目标之一。 1.粒子群算法的背景 粒子群算法(particle swarm optimization，pso)是一种新兴的演化算法。该算法是由j.kennedy和r.c.eberhart于1995年提出的一种基于群智能的随机优化算法。这类算法的仿生基点是：群集动物(如蚂蚁、鸟、鱼等)通过群聚而有效的觅食和逃避追捕。在这类群体的动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。如在蚁群中，当每个个体发现食物之后，它将通过接触或化学信号来招募同伴，使整个群落找到食源；在鸟群的飞行中，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，但随着时间推移，这些初始处于随机状态的鸟通过相互学习(相互跟踪)组织的聚集成一个个小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集在同一位置──食源。这些群集动物所表现的智能常称为“群体智能”，它可表述为：一组相互之间可以进行直接通讯或间接通讯(通过改变局部环境)的主体，能够通过合作对问题进行分布求解。换言之，一组无智能的主体通过合作表现出智能行为特征。粒子群算法就是以模拟鸟的群集智能为特征，以求解连续变量优化问题为背景的一种优化算法。因其概念简单、参数较少、易于实现等特点，自提出以来已经受到国内外研究者的高度重视并被广泛应用于许多领域。
启发式算法研究小结 0.探究启发式算法的缘由 在选《管理优化决策》这门课的时候，我抱着很强的好奇心和巨大的求知欲，试图尝试在这门课上学到我感兴趣的知识点以及确定我今后极有可能的研究领域和大方向。很幸运的是，我找到了。为什么这么说呢？就在我选择博士专业内选修课和专业外选修课的同时我发现了管理优化决策这门课和计算机学院那边开的选修课——《启发式优化》（由吕志鹏教授讲授），有很多是相通的，发现管理界尤其是在管理科学与工程方向和计算机技术应用领域所探究的问题出奇的一致，已经很难分清，哪个是管理方面的问题，哪个是计算机技术应用的范围了。正如各位都知道的是，由于选修课最终确定前一个月是可以去试听的，然而我并没有因为两者看上去内容有些相似就匆忙退选。通过对这两门课的内容进行比较，它给了我很大的触动，也带给我巨大的好奇，到底是管理方面的研究越来越偏向运用计算机等其他学科的知识和工具，还是计算机应用研究的方面越来越偏向实际的管理优化问题了呢？亦或者两个学科的边界正在走向模糊？我想学科交叉和融合的这一说法对于我来说可能并不是很新鲜，但这的确是我亲身经历的一种美妙体验和发现。它带给我新奇的同时也无疑给了我值得我深思几点的启示： 首先，众所周知，管理学科作为一门交叉的新兴学科，它的方法和工具都是依托和借助其他领域和学科而来的，它本身并没有或者几乎没有一个完完整整的只属于管理学科的方法和工具，几乎是其它学科的知识演变而来的，这就是我们所知道的学科交叉和学科融合；然而管理领域和传统计算机研究等领域的视角并不完全一样，其中对于计算机领域的研究者们而言，他们不但在乎启发式算法是否能够解决问题、效率是否大幅提高（而管理领域的专家们更在乎这点，能用第一，好用第二，或者说管理专家们更在乎第一点——问题能够得到的解决，至于第二点就不是那么迫切。而对计算机领域的向专家们而言，可以说两者都非常重要、要求非常苛刻），更在乎它所表现出来的优越特性（就时间、空间复杂度以及算法求解过程中保持一定的集中性和分散性而言的）。然而当管理领域的学者们求解类似问题，一般来说都是和我们生活中的管理者经常遇到且直接和的决策相关的问题，因为由于管理者的决策质量好坏会往往直接导致企业和团体的效率和绩效和高低，进而导致企业和组织的竞争力强弱，所以一般企业或者个人都是基于一定的价值诉求来解决管理问题，进而提高工作效率。由于管理者们非常了解生活中并不存在完完全全的理性人和完全信息，因此他们很难也极少去尝试寻找最优解，找到满意解就可以了，这一点和启发式算法的设计思想不谋而合（由于
1、程序源代码 #include
第25卷第4期 青岛大学学报(工程技术版) Vol.25No.4 2010年12月JOURNAL OF QING DAO UNIVERSIT Y (E &T) Dec.2010 文章编号:1006-9798(2010)04-0057-04 集装箱码头泊位调度问题的启发式算法研究 张海滨,张纪会,宣金钊 (青岛大学复杂性科学研究所,山东青岛266071) 摘要:为优化集装箱码头泊位的分配,提高泊位的利用率,把码头泊位的调度问题转化为带有约束条件的特殊二维装箱问题。通过建立连续泊位调度的非线性规划模型,提出了一种求解集装箱码头连续泊位分配问题启发式算法。仿真算例结果表明该算法能在实际的集装箱码头泊位调度中有效的提高泊位的利用率。关键词:泊位分配;装箱问题;启发式算法中图分类号:U692.4 文献标识码:A 收稿日期:2010-09-11 基金项目:国家自然科学基金项目(70671057);山东省自然科学基金项目(ZR2010GM006)作者简介:张海滨(1982-),男,硕士研究生,主要从事集装箱码头泊位调度的研究。 泊位作为港口运输中一种重要的资源,是影响港口发展的关键因素之一。随着港口之间的竞争越来越激烈,如何最大限度提高泊位的利用率、加快船舶的装卸速度,提高港口作业效率和服务水平,是增强港口竞争力的关键因素之一。因此,泊位调度问题成为港口运输中研究的一项重点内容之一。泊位分配问题根据泊位的特点分为离散泊位分配和连续泊位分配,根据作业特点分为静态泊位分配和动态泊位分配。泊位分配问题作为N P 难问题,可以视为指派问题或者划分问题[1];Lai 等[2]提出了以先到先服务为准则的动态泊位调度的启发式算法;Imai [3-5]提出了一种离散泊位下静态和动态泊位分配的启发式算法;Cordeau 等[6]利用禁忌搜索方法对动态泊位分配问题进行了求解;K im 等[7]建立了惩罚策略下的最小费用泊位动态分配模型,并利用模拟退火算法进行了求解;Monaco 等[8]通过考虑船舶总的在港时间,建立了一种连续泊位动态分配模型并进行求解;Hansen 等[9]基于在港时间和在港费用综合考虑建立了相应的模型,并进行了仿真求解。本文仅考虑泊位一种因素,建立了连续的动态泊位分配优化模型,提出了一种启发式算法可以求得模型的近似最优解。 1 以利用率最高为目标的泊位调度模型 泊位调度问题实际是如何安排船舶靠泊的时间和靠泊位置,使某一时间内港口泊位的利用率最高。实际上泊位的划分主要是逻辑划分而非物理划分。目前国际上的集装箱运输都是采用班轮运输方式,因此,为建立模型作如下假设:模型中的泊位是连续的,进入待泊区域的集装箱船舶都可以进入泊位作业区域进行作业;根据集装箱采取班轮运输的特点,假设船舶的作业时间由所在目的港装卸箱子的数量决定,与船舶的靠泊位置无关;假设船舶都能按照预计时间到达目的港,可以根据船舶的预计到达时间对船舶进行分配靠泊位置。 建立x -y 直角坐标系,x 轴表示作业时间,y 轴表示离散泊位长度。则连续泊位调度的模型可以描述为: 1) 某一时间段内通过合理安排船舶靠泊作业顺序和作业位置使泊位的利用率最大,其模型为 max F = ∑ j ∈V l j t nj /S (1) 式中,l j 表示船舶j 安全作业需要的泊位长度(其中包括船舶的长度和船舶安全作业之间的距离);t nj 表示船
摘要 在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，由于其几乎不存在对问题的约束，因此，粒子群优化算法在各种优化问题中得到广泛应用。 本文首先描述了基本粒子群优化算法及其改进算法的基本原理,对比分析粒子群优化算法与其他优化算法的优缺点，并对基本粒子群优化算法参数进行了简要分析。根据分析结果,研究了一种基于量子的粒子群优化算法。在标准测试函数的优化上粒子群优化算法与改进算法进行了比较,实验结果表明改进的算法在优化性能明显要优于其它算法。本文算法应用于支持向量机参数选择的优化问题上也获得了较好的性能。最后,对本文进行了简单的总结和展望。 关键词：粒子群优化算法最小二乘支持向量机参数优化适应度
目录 摘要...................................................................... I 目录....................................................................... II 1.概述. (1) 1.1引言 (1) 1.2研究背景 (1) 1.2.1人工生命计算 (1) 1.2.2 群集智能理论 (2) 1.3算法比较 (2) 1.3.1粒子群算法与遗传算法(GA)比较 (2) 1.3.2粒子群算法与蚁群算法(ACO)比较 (3) 1.4粒子群优化算法的研究现状 (4) 1.4.1理论研究现状 (4) 1.4.2应用研究现状 (5) 1.5粒子群优化算法的应用 (5) 1.5.1神经网络训练 (6) 1.5.2函数优化 (6) 1.5.3其他应用 (6) 1.5.4粒子群优化算法的工程应用概述 (6) 2.粒子群优化算法 (8) 2.1基本粒子群优化算法 (8) 2.1.1基本理论 (8) 2.1.2算法流程 (9) 2.2标准粒子群优化算法 (10) 2.2.1惯性权重 (10) 2.2.2压缩因子 (11) 2.3算法分析 (12) 2.3.1参数分析 (12) 2.3.2粒子群优化算法的特点 (14) 3.粒子群优化算法的改进 (15) 3.1粒子群优化算法存在的问题 (15) 3.2粒子群优化算法的改进分析 (15) 3.3基于量子粒子群优化(QPSO)算法 (17) 3.3.1 QPSO算法的优点 (17) 3.3.2 基于MATLAB的仿真 (18) 3.4 PSO仿真 (19) 3.4.1 标准测试函数 (19) 3.4.2 试验参数设置 (20) 3.5试验结果与分析 (21) 4.粒子群优化算法在支持向量机的参数优化中的应用 (22) 4.1支持向量机 (22) 4.2最小二乘支持向量机原理 (22)
编号 南京航空航天大学毕业论文 题目启发式搜索算法在N数码问 题中的应用 学生姓名 学号 学院 专业 班级 指导教师 二〇一三年六月
南京航空航天大学 本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：启发式搜索算法在N数码问题中的应用）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。 作者签名：年月日 （学号）：
启发式搜索算法在N数码问题中的应用 摘要 N数码问题是人工智能领域中的经典问题，N数码可以有效的判断一个搜索算法的优劣。在低阶数码问题中，使用简单的宽搜或深搜就可以解决问题，但在高阶数码中，由于其巨大的搜索规模，我们必须采用更加智能的算法才能解决问题。与传统搜索相比，启发式搜索当前搜索过程中的信息，选择最为可行的状态进行拓展，从而大大提高了搜索的质量和效率。 本文通过建立N数码问题的存储机制和移动规则，使得N数码问题转化为了一个标准的搜索问题。并着重分析了A*算法和遗传算法在N数码中的应用，在A*算法中使用了两种不同的估价函数，目的是比较不同估价函数在N数码问题中的表现。在最后，本文进行了大量实验，综合分析了A*算法和遗传算法在不同规模数据下的优劣。 关键词：启发式搜索，数码问题，A*算法，遗传算法
The Application of Heuristic Search Algorithm on N-Puzzle Problem Abstract N-puzzle problem is a classic problem in artificial intelligence. N-puzzle problem can effectively judge the merits of a search algorithm. In the low order puzzle problem, using a Depth-First-Search or Breadth-First-Search can solve the problem, but in the higher order digital, because of the huge search space area,we must adopt a more intelligent https://www.doczj.com/doc/8d2134528.html,pared with the traditional search method, heuristic search uses the information in the search process, and it will choose the most feasible state, thus greatly improves the search quality and efficiency. This paper designs the storage mechanism and movement rules of N-puzzle problem, making the N-puzzle problem transforms to a standard search problem. This paper focuses on the application of A* algorithm and genetic algorithm in N-puzzle problem, and two different evaluation function used in A* algorithm. The objective is to compare the performance of different valuation function in N digital problem. In the end, this paper carries out a large number of experiments, a comprehensive analysis of the A* algorithm and genetic algorithm in different scale of data. Key Words：Heuristic Search;N-puzzle Problem;A* algorithm; Genetic algorithm
华中科技大学硕士学位论文 目录 摘要 ...................................................................................................................... I Abstract................................................................................................................. II 1绪论 1.1课题背景及意义 (1) 1.2问题数学描述 (1) 1.3国内外研究现状 (2) 1.4本文主要研究内容 (4) 2相关理论基础 2.1启发式算法概述 (5) 2.2局部搜索 (5) 2.3TSP问题概述 (6) 2.4问题数学建模 (9) 2.5本章小结 (12) 3多阶段优化启发式算法 3.1算法主框架 (14) 3.2和TSP问题相互转化 (16) 3.3求解TSP问题 (19) 3.4候选路搜索 (23) 3.5节点属性提升 (27) 3.6本章小结 (28) 4实验结果分析 4.1算例集介绍 (29) 4.2求解结果比较 (30) 4.3本章小结 (38) 5算法分析与讨论 5.1复杂度分析 (39) 5.2增量评估技术 (39) 5.3多策略组合 (41) 5.4本章小结 (42)
华中科技大学硕士学位论文 6总结与展望 6.1论文工作总结 (43) 6.2未来工作展望 (43) 致谢 (45) 参考文献 (46) 附录一：测试数据 (49)
现代智能优化算法课程群智能优化算法综述学生姓名: 学号: 班级: 2014年6月22日
摘要 工程技术与科学研究中的最优化求解问题十分普遍,在求解过程中,人们创造与发现了许多优秀实用的算法。群智能算法就是一种新兴的演化计算技术,已成为越来越多研究者的关注焦点,智能优化算法具有很多优点,如操作简单、收敛速度快、全局收敛性好等。群智能优化就是智能优化的一个重要分支,它与人工生命,特别就是进化策略以及遗传算法有着极为特殊的联系。群智能优化通过模拟社会性昆虫的各种群体行为,利用群体中个体之间的信息交互与合作实现寻优。本文综述群智能优化算法的原理、主要群智能算法介绍、应用研究及其发展前景。 关键词:群智能;最优化;算法
目录 摘要 0 1 概述 (2) 2 定义及原理 (2) 2、1 定义 (2) 2、2 群集智能算法原理 (3) 3 主要群智能算法 (3) 3、1 蚁群算法 (3) 3、2 粒子群算法 (4) 3、3 其她算法 (5) 4 应用研究 (6) 5 发展前景 (6) 6 总结 (7) 参考文献 (8)
1 概述 优化就是人们长久以来不断研究与探讨的一个充满活力与挑战的领域。很多实际优化问题往往存 在着难解性,传统的优化方法如牛顿法、共扼梯度法、模式搜索法、单纯形法等己难以满足人们需求。 因此设计高效的优化算法成为众多科研工作者的研究目标。随着人类对生物启发式计算的研究, 一些社会性动物( 如蚁群、蜂群、鸟群) 的自组织行为引起了科学家的广泛关注。这些社会性动物在漫长的进化过程中形成了一个共同的特点: 个体的行为都很简单, 但当它们一起协同工作时, 却能够“突现”出非常复杂的行为特征。基于此,人们设计了许多优化算法,例如蚁群算法、粒子群优化算法、混合蛙跳算法、人工鱼群算法,并在诸多领域得到了成功应用。目前, 群智能理论研究领域主要有两种算法: 蚁群算法(Ant Colony Optimization, ACO) 与粒子群优化算法(ParticleSwarm Optimization, PSO)。 2 定义及原理 2、1 定义 群集智能优化算法源于对自然界的生物进化过程或觅食行为的模拟。它将搜索与优化过程模拟成个体的进化或觅食过程,用搜索空间中的点模拟自然界中的个体;将求解问题的目标函数度量成个体对环境的适应能力;将个体的优胜劣汰过程或觅食过程类比为搜索与优化过程中用好的可行解取代较差可行解的迭代过程。从而,形成了一种以“生成+检验”特征的迭代搜索算法,就是一种求解极值问题的自适应人工智能技术。各类优化算法实质上都就是建立问题的目标函数,求目标函数的最优解,因而实际工程优化问题均可转化为函数优化问题。其表达形式如下: 求: ,,2,1,0)(..), (min , ,,2,1,),,,(21Lm j X g t s X f n L i x L x x X i T n i =≤== 。Ω∈X 其中,i X 为设计变量;)(X f 为被优化的目标函数;0)(≤X g j 为约束函数;Ω为设计变量的可行