港口泊位调度问题的粒子群优化研究_刘志雄
2010年第32卷第8期总第194期物流工程与管理
LOGISTICS ENGINEERING AND MANAGEMENT
物流技术
doi ：10．3969/j．issn．1674－4993．2010．08．037
港口泊位调度问题的粒子群优化研究
*
?刘志雄1，
2
（1．武汉科技大学机械自动化学院，湖北武汉430081；2．天津港（集团）有限公司博士后科研工作站，天津300461）
【收稿日期】2010－07－08
*基金项目：中国博士后科研基金资助项目（NO．20090450769）【作者简介】刘志雄－），男，武汉科技大学副教授博士，博士后，研究方向：生产调度及其智能优化方法。
【摘
要】泊位计划与调度直接影响着港口船舶的进港靠泊，采用粒子群算法对港口泊位调度问题进行优化。建立
港口泊位调度问题的数学模型，针对泊位调度的特点，提出一种基于船舶和粒子位置取整的二维粒子编码方法。为了保证所生成的泊位调度解的可行性，提出了一种针对粒子编码的修正方法。针对港口船舶作业实际数据，采用粒子群算法进行了计算，
并与实际泊位调度结果进行了比较。计算结果说明粒子群算法能够有效地优化港口泊位调度问题。【关键词】港口；泊位调度；建模；粒子群算法；粒子编码【中图分类号】TP39；U692
【文献标识码】A
【文章编号】1674－4993（2010）08－0101－03
Particle Swarm Optimization Algorithm for Port Berth Scheduling Problem
□LIU Zhi －xiong
1，2
（1．College of Machinery and Automation ，Wuhan University of Science and Technology Wuhan 430081；
2．Tianjin Port （Group ）Co．，LTD Postdoctoral Research Center ，Tianjin 300461，China ）
【Abstract 】Berth planning and scheduling has an important effect on making harbor of the vessels and particle swarm optimization algorithm is employed to optimize the berth scheduling problem．The model of berth scheduling problem is made and the two －dimension particle encoding method based on the vessel and the particle position rounding is introduced according to the character of the berth scheduling problem．To assure that the generated berth schedule solution after decoding is feasible ，a kind of revising approach for the particle encoding is presented．Particle swarm optimization algorithm is applied to the practical data of the port operation and compared with the practical berth schedule solution．Computational results show that particle swarm optimization algorithm can effectively optimize the berth scheduling problem．
【Key words 】port ；berth scheduling ；modeling ；particle swarm optimization ；particle encoding
1
引言
港口是水陆运输的枢纽，是水运货物的集散地和远洋运输的起点和终点，世界贸易的90%是通过海运方式完成。近年来，随着水路运输业的发展，我国港口吞吐量大幅度增长。港口市场在不断开放的同时，对港口的要求也更高，港口间的竞争更加激烈。为了吸引更多的船舶靠港，港口需要提高其服务质量和服务水平，提高港口的生产作业效率，缩短船舶在港停留时间。港口管理者一方面提高港口的硬件设备设施水平，另一方面，则需要提高港口的生产组织管理水平，其中，对港口设备设施的有效计划和组织调度则是其重要手段。
泊位作为港口的主要生产资源和设施之一，对于一个码头来说，
当其泊位岸线长度和泊位水深一定时，对泊位进行有效的计划和调度则直接影响着船舶的及时进港靠泊。近年来，
泊位的计划和调度问题越来越受到一些学者的重视。Brown 等［1］以最小化船舶在港总效益为目标进行泊位指派；Imai 等［2］以最小化船舶等待时间为目标，采用非线性整数规
划模型模拟静态泊位调度（SBAP ）。李平等［3］
将遗传算法和
混合优化策略GATS 用于求解集装箱港口的泊位调度问题。
粒子群算法（Particle Swarm Optimization ，简称PSO ）是一种基于群体智能的进化类算法
［4］
，一经提出便得到较为广泛
的应用，特别是在连续函数优化问题领域，粒子群算法显示了其有效的优化性能。同时，通过对粒子群算法实施相应的编码和解码方法，以及对粒子群模型进行改进，粒子群算法也被应用于组合优化问题，
如调度问题［5－7］
。本文采用粒子群算
法来求解港口泊位调度问题，以船舶在港停留时间最短为目标，建立港口泊位调度模型，提出一种基于船舶和粒子位置取整的粒子编码方法。并以某港口的实际船舶作业数据为例，采用粒子群算法进行了优化，优化结果说明了粒子群算法的有效性。2
泊位调度问题的描述
泊位调度（也称泊位指派问题或泊位配置，Berth －Allocation ）就是对到港船舶分配合理的停靠泊位，使在一定时间内所有来港船舶的总的在港时间最短，以提高港口营运效率，从而吸引较多船舶挂靠。
物流工程与管理第32卷
在港口，船舶首先到达港口锚地，如果港口有空闲泊位，
船舶就进入泊位进行货物的装卸，货物装卸完毕后离港。本
文在研究港口泊位调度问题时，为了简化问题，将船舶进入泊
位进行货物装卸前的准备时间、装卸作业时间、离港前的准备
时间等合并为船舶的装卸作业时间进行计算。
在港口，当考虑几个泊位的靠泊条件相同时，即到港船舶
均能靠泊这几个泊位，并且每个泊位一次只能停靠一艘船舶，
此时的泊位调度问题属于并行机调度问题。
假设港口有m个泊位，有n艘船舶需要进港进行装卸作
业，对于第i个泊位上的第j艘船舶，假设该船舶的到港时间
为S ij，装卸作业时间为T ij，离港时间为C ij，n艘船舶中分配到
泊位i上进行装卸作业的船舶数量为N i，用f i表示泊位i上所
有船舶的在港停留时间总和，用F表示n艘船舶的在港停留
时间总和，假设每个泊位一次只能靠泊一艘船舶，那么泊位优
化调度的目标可以表示为：
Min F=Min∑m
i=1f
i
（1）
=Min∑m
i=1∑
N i
j=1
（C
ij
－S
ij
）
s．t．∑m
i=1N
i
=n（2）
S ij ＜=S
i（j+1）
（3）
C
ij －S
ij
＜=T
ij
（4）
i=1，2，…，m，j=1，2，…，N
i
；
公式（1）表示泊位优化调度的目标是使得所有到港船舶的在港停留时间最短，公式（2）表示分配到m个泊位上的船舶总数等于n，公式（3）表示分配到每个泊位上的船舶遵循先到先服务的原则，公式（4）表示每艘船舶必须在到达港口以后才能被服务。
3粒子群算法设计
3．1粒子群算法
在粒子群算法中，所有粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定它们搜索的方向和距离，所有粒子通过追随当前的最优粒子（个体最优粒子和全局最优粒子）在解空间中进行搜索。假设粒子群中的第i个粒子在n维空间中的位置表示为一个n维向量x i=（x i1，x i2，
…，x
ij ， (x)
in
），速度v
i
=（v
i1
，v
i2
，…，v
ij
， (v)
in
）决定了粒子在
搜索空间单次迭代的位移。当前粒子群中的个体最优粒子表示为p i=（p i1，p i2，…，p ij，…p in），全局最优粒子表示为g=
（g
1，g
2
，…，g
j
，…g
n
），粒子群中的所有粒子根据公式（5）和
（6）来更新其速度和位置。
v ij =ωv
ij
+c
r
andom（）（P
ij
－x
ij
）+c
2
random（）（g
j
－x
ij
）（5）
x ij =x
ij
+v
ij
（6）
公式（3）中，random（）为（0，1）之间的随机数，c1和c2为学习因子，一般取c1=c2=2，ω为惯性权重，ω取较大值粒子群算法具有较强的全局搜索能力，ω取较小值粒子群算法倾向于局部搜索，一般的做法是将ω的初始值设置为0．9，然后按照迭代次数线性递减到0．4。速度v i可以设定在v max和v min 之间，当超过这个区间时，就取对应的上下限值。x i位置也可设定在一定的x min max区间范围内3．2粒子编码与解码方法
由于不能直接用粒子位置表示泊位调度问题的解，因此，需要采用一定的粒子编码方法来间接生成泊位调度的解。本文设计了一种基于船舶和粒子位置取整的二维粒子编码方法，如表1所示。
表1基于船舶和粒子位置的粒子编码
船舶123…j…n
位置x i1x i2x i3…x ij…x in
其中，粒子位置x ij∈［1，m+1］。对粒子的第二维即粒子位置xij进行取整操作，用INT（x ij）表示，由于x ij∈［1，m］，因此，取整后，INT（x ij）即表示船舶j所对应的泊位。通过上述方式，将所有船舶分配到不同的泊位上，进而可以得到各泊位上的船舶靠泊序列，即得到泊位调度方案。
这里以10艘船舶、3个泊位的调度情况对粒子表示和解码过程进行说明。以自然数1，2，…，10表示船舶，以1、2、3表示三个泊位，假设某个粒子可以表示如表2所示。
表2粒子编码举例
船舶12345678910
粒子位置1．33．52．42．81．43．13．72．52．11．9
对该粒子中的粒子位置进行取整操作，可以得到各船舶的泊位分配情况，如表3所示。
表3解码后每艘船舶的泊位分配
船舶12345678910泊位1322133221
于是，就可以得到每个泊位上的船舶作业顺序，即如表4所示。
表4泊位分配结果
泊位船舶
11，5，10
23，4，8，9
32，6，7
然后根据每艘船舶的到港时间和装卸作业时间，按照公式计算所有船舶的在港停留时间总和，即该粒子的适应值。3．3粒子编码存在的问题和修正方法
对于上述基于船舶和粒子位置取整的粒子编码，在粒子的初始化阶段，粒子位置是x ij在［1，m+1）之间随机取值，然后通过对粒子位置x ij的取整操作INT（x ij）来表示该船舶所对应的泊位，从而生成调度方案，由于INT（x ij）实质上是在［1，m］之间取随机整数，因此就可能造成有些机器编号没有被分配给工件的结果。另外，在粒子位置的更新阶段，粒子的位置被限制在［1，m+1）之间，粒子的位置如果超出范围就分别取其范围的上下限值，这也可能造成上述不可行调度方案的生成。因此，本文采用如下方法对算法进行改进。
201
第8期刘志雄：港口泊位调度问题的粒子群优化研究
①在粒子的初始化阶段，如果生成的粒子所对应的调度方案为不可行调度，即重新初始化该粒子，从而保证初始化粒子种群的可行性。
②在粒子位置的更新阶段，采用一种变异算子，即如果粒子位置超出了其限制范围［1，m +1］，不是将该粒子位置赋予上下限值，
而是在［1，m +1］之间随机取值。③采用一种惩罚的方法，即在计算过程中，如果某个粒子所生成的调度方案为不可行调度方案，将该粒子的适应值设定为一个较大的值。
上述改进在一定程度上，至少是在粒子的初始化阶段，避免了不可行调度方案的生成，而惩罚方法则在进化过程中减少了对应不可行调度方案的粒子被“选择”的机会，同时，变异算子的加入可以增加生成的调度方案的多样性。4
计算结果
以某港口4个泊位的实际船舶作业数据为例，本文利用粒子算法对泊位调度问题进行计算。在某港口的实际船舶作业调度数据中，随机选取连续20艘到港船舶的作业调度数据，具体的船舶到港时间间隔（为方便计算，以第一艘船舶的到港时间为基准，取值为0）和船舶作业时间如表5所示。表5船舶到港时间间隔与装卸作业时间（单位：小时）船舶12345
6
7
8
910到港时间间隔
13．5
8
5
2．50．50．51．5
5
装卸作
业时间12．9111．688．6719．742211．59．7510．8410．839．75
船舶11
12
13
1415
16
1718
19
20
到港时间间隔
148．757．255
1．513．56
3．271．731．5
装卸作
业时间
9．669．751112．514．6710．756．8311．251010．34
（注：到港船舶时间间隔是指连续两艘船舶的时间间隔，如船舶1和2之间的时间间隔为13．5小时，船舶2和3的时间间隔为8小时。
）上述20艘船舶在港实际停留时间总和为304．4小时，采用惯性权重线性递减PSO 模型，设定最大迭代次数为100次，连续优化10次得到的结果如表6所示。
表6
泊位调度优化结果（单位：小时）
优化次数最优值（即所有船舶在港停留时间的总和）
最小值257．25最大值262．01平均值
258．1
从上述计算结果看，通过粒子群算法对上述20艘船舶进行泊位优化调度后，
10次优化计算的结果均好于实际生产调
度的结果；与实际生产结果相比，通过粒子群算法计算后的最
优调度所对应的20艘船舶在港停留时间总和要少47．15小时。可见，通过粒子群算法对港口泊位调度问题进行优化，能够得到一个较好的泊位调度方案。
最优计算结果即所有船舶在港停留时间总和为257．25小时时所对应的最优泊位调度方案如图1所示。
图1
基于PSO 的泊位最优调度示图
5
结束语
将粒子群算法用于求解港口泊位调度优化问题，建立泊位调度模型，提出了一种基于船舶和粒子位置取整的粒子编码方法。针对港口实际作业数据，
采用粒子群算法对泊位调度问题进行了计算。计算结果指出，基于粒子群算法的泊位调度方法能够取得较好的泊位调度结果。
［参考文献］
［1］Brown G G ，Cormican K J ，Lawphongpanich S ，Widdis D
B．
Optimizing submarine berthing with a persistence incentive ［J ］．Research Logistics ，1997，（44）：301－318．［2］Imai A ，Nagaiwa K．Efficient planning of berth allocation for
container terminals in Asia ［J ］．Journal of advanced
Transportation ，
1997，31（1）：75－94．［3］李平，孙俊清，韩梅．泊位调度问题的GATS 混合优化策
略［
J ］．天津理工大学学报．2006，22（4）：58－61．［4］Eberhart R C ，Shi Y H．Particle Swarm Optimization ：
Development ，Applications and Resources．Proceedings of 2001Congress on Evolutionary Computation ，Seoul ，korea ，2001［C ］，81－86
［5］Jerald．J ，Asokan．P ，Prabaharan．G ，et al．Scheduling
Optimization of Flexible Manufacturing Systems Using Particle Swarm Optimization Algorithm ［J ］．Advanced
Manufacturing Technology．2004，
213－220．［6］雷秀娟，史忠科，付阿利．改进的粒子群优化算法求解车
辆调度问题［J ］．计算机应用研究．2008，25，（9）：2674－2676．
［7］虞斌能，焦斌，顾幸生．改进协同粒子群优化算法及其在
Flow Shop 调度中的应用［J ］．华东理工大学学报（自然科学版），
2009，35，（6）：468－474．3
01
改进的粒子群优化算法
第37卷第4期河北工业大学学报2008年8月V ol.37No.4JOURNAL OF HEBEI UNIVERSITY OF TECHNOLOGY August2008 文章编号：1008-2373(2008)04-0055-05 改进的粒子群优化算法 宋洁，董永峰，侯向丹，杨彦卿 （河北工业大学计算机科学与软件学院，天津300401） 摘要粒子群优化算法是一种基于群体的自适应搜索优化算法，存在后期收敛慢、搜索精度低、容易陷入局部极 小等缺点，为此提出了一种改进的粒子群优化算法，从初始解和搜索精度两个方面进行了改进，提高了算法的计 算精度，改善了算法收敛性，很大程度上避免了算法陷入局部极小．对经典函数测试计算，验证了算法的有效性． 关键词粒子群优化算法；均匀化；变量搜索；初始解；搜索精度 中图分类号TP391文献标识码A A Modified Particle Swarm Optimization Algorithm SONG Jie,DONG Yong-feng,HOU Xiang-dan,Y ANG Yan-qing (School of Computer Science and Engineering,Hebei University of Technology,Tianjin300401,China) Abstract Particle Swarm Optimization Algorithm is a kind of auto-adapted search optimization based on community. But the standard particle swarm optimization is used resulting in slow after convergence,low search precision and easily leading to local minimum.A new Particle Swarm Optimization algorithm is proposed to improve from the initial solution and the search precision.The obtained results showed the algorithm computation precision and the astringency are im- proved,and local minimum is avoided.The experimental results of classic functions show that the improved PSO is ef- ficient and feasible. Key words PSO；average；variable search；initial solution；search accuracy 0引言 粒子群优化（Particle Swarm Optimization，PSO）算法是一种基于群体的随机优化技术，最早在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart[1]共同提出，基本思想源于对鸟群觅食行为的研究．PSO将每个可能产生的解都表述为群中的一个微粒，每个微粒都具有自己的位置向量和速度向量，和一个由目标函数决定的适应度，通过类似梯度下降算法使各粒子向适应度函数值最高的方向群游．该算法控制参数少、程序相对简单，因此在应用领域表现出了很大的优越性．由于PSO算法容易理解、易于实现，所以PSO算法发展很快．目前，多种PSO改进算法已广泛应用于函数优化、神经网络训练、模式识别、模糊系统控制以及其他的应用领域． 许多学者对PSO算法进行研究，发现其容易出现早熟、最优解附近收敛慢等现象，并提出了一些改进方案，例如自适应PSO算法、混合PSO算法、杂交PSO算法等[2-4]．因此，本文从初始解和收敛精度两个角度出发对PSO算法进行了改进，提高了算法的计算精度，有效的改善了算法的优化性能． 1基本PSO算法 PSO算法是一种基于群体的随机优化技术，基本思想源于对鸟群觅食行为的研究．通过对鸟群飞行时经常会突然改变方向、散开、聚集，但整体总保持一致性，个体与个体间鸟群好像在一个中心的控制 收稿日期：2008-04-17 基金项目：河北省自然科学基金（F2006000109） 作者简介：宋洁（1967-），女（汉族），副教授．
基于粒子群优化算法的图像分割
安康学院 学年论文（设计） 题目_____________________________________________ 学生姓名_______________ 学号_____________________________ 所在院（系）_______________________________________ 专业班级__________________________________________________ 指导教师_____________________________________________ 年月曰
基于粒子群优化算法的图像分割 （作者：） （） 指导教师： 【摘要】本文通过对粒子群优化算法的研究，采用Java编程，设计出一套用于图像分割的系统。 基于粒子群优化算法的图像分割系统，可以将一幅给定的图像进行分割，然后将分割结果保存。图像分割的目的是将感兴趣的区域从图像中分割出来，从而为计算机视觉的后续处理提供依据。图像分割的方法有多种，阈值法因其实现简单而成为一种有效的图像分割方法。而粒子群优化（PSO）算法是一类随机全局优化技术，它通过粒子间的相互作用发现复杂搜索空间中的最优区域缩短寻找阈值的时间。因此，基于粒子群优化算法的图像分割以粒子群优化算法为寻优工具，建立具有自适应和鲁棒性的分割方法。从而可以在最短的时间内，准确地确定分割阈值。 关键词：粒子群优化（PSO，图像分割，阈值法，鲁棒性 Abstract T his paper based on the particle swarm optimizati on algorithm, desig ns a set of system for image segme ntati on using Java program min g. Image segme ntati on system based on particle swarm optimizati on algorithm, the image can be a given segmentation, and then the segmentation results would be saved. Image segmentation is the purpose of the interested area from the image, thus providing the basis for the subsequent processing of computer vision. There are many methods of image segmentation, threshold method since its simple realization, becomes a kind of effective method in image segmentation. Particle swarm optimization （PSO） algorithm is a stochastic global optimization technique; it finds optimal regions of complex search spaces for threshold time shorte ned through the in teractio n betwee n particles. Therefore, particle swarm optimization algorithm of image segmentation based on particle swarm optimization algorithm based on optimizati on tools; establish segme ntati on method with adaptive and robust. Therefore, it is possible for us in the shortest possible time to accurately determ ine the segme ntati on threshold. Key word s: PSO, image segmentation, threshold method, robust. 1引言 1.1研究的背景和意义 技术的不断向前发展，人们越来越多地利用计算机来获取和处理视觉图像信息。据统计，人类
粒子群优化算法综述
粒子群优化算法综述 摘要：本文围绕粒子群优化算法的原理、特点、改进与应用等方面进行全面综述。侧重于粒子群的改进算法，简短介绍了粒子群算法在典型理论问题和实际工业对象中的应用，并给出了粒子群算三个重要的网址，最后对粒子群算做了进一步展望。 关键词；粒子群算法；应用；电子资源；综述 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）由船公司或其代理部门向港务局业务处报送（外贸船必须由其代理申报，内贸船由天津港货运公司或中海船代公司申报）船舶72小时、48小时、24小时抵港预确报，并注明船名、船舶性质、船舶规范（船长、船宽、吃水等）、进出口货类、数量、是否申请引水等。从事内贸计划外运输的船舶办妥各项手续后，货运公司还应向业务处递交船舶进出港申报单。 （2）进出港务局所辖码头的船舶由港务局业务处指定作业公司。 （3）船舶要求进出港口时，由船舶停靠码头单位的调度室，在每天10点30分前向港务局业务处申报当日18时至次日18时的船舶进出港计划，申报内容包括：船名、船长、船宽、吃水、是否申请引水、动态时间、动态的地点，所载货物是否属于危险品等。 （4）各单位动态计划上报后，有业务处汇总，平衡核定动态船舶进出港计划时间安排，于每日14时前通知各有关单位执行。 如何申报船舶航道计划 凡按规定进出港口需申请使用航道的船舶，必须在每日10时30分前向港务局业务处申报下一昼夜（即当日18时至次日18时）的船舶计划，每日14时由局业务处将平衡核定的船舶航道计划通知有关部门和单位执行。 如何申报船舶过闸计划 < 凡按规定向港务局业务处申报过闸计划的船舶（即生产性船舶及需占用主航道的船舶），应在每日10时30分前申报下一昼夜（即当日18时至次日18时）的船舶过闸计划，由港务局业务处平衡核定后通知有关部门和船闸执行。 60米以下非生产性船舶及不需使用主航道的非生产性船舶可直接向船闸申报过闸计划。 进出企业专用码头船舶如何申报计划 进出企业专用码头的船舶，由该码头调度在每日10时30分前向港务局业务处申报当日18时至次日18时的动态计划。申报内容包括：船名、船长、船宽、吃水，是否申请引水、拖轮，动态时间等。 港务局业务处汇总平衡并通知有关单位执行。 沿海运输船舶在企业码头作业，申请进港动态前，企业专用码头单位应按规定到天津港货运公司办理船舶进出港手续，手续合格后，由货运公司向局业务处递交船舶进港申报单后方可安排动态计划。 船舶代理应向局调度室报告哪些内容 — 船舶代理应在所代理船舶抵港前72小时、48小时、24小时向港务局业务处报告（通过传真）船舶抵港预报和确报时间，并及时汇报变更时间。船舶预确报的内容有：船名、国籍、性质、抵港时间、艏艉吃水、进出口货名、数量、船舶规范、装卸设备状况及特殊货物装卸情况和要求等。 为什么船舶代理应及时准确地向局调度室报告船舶到港预报、确报时间 船方与代理公司的代理关系一经建立，代理人句应按照委托人的要求，在授权范围内，执行代理职责。以维护委托人的合法利益为原则，诚恳、忠实、勤勉地进行代理工作。船舶预确报抵港时间的反馈，关系到船方的切身利益，也便于港方及时做出科学合理安排，对缩短船舶在港时间，降低运输成本具有十分重要的意义。 船舶必须具备哪些条件才能安排作业 （1）进口，包括船图、舱单及卸货有关部门资料必须齐备；具有港口主管部门批准的危险货物作业通知书；货物流向及接卸方案已做出详细安排；超高、超宽、重大件设备具体资料预先摸清，特种车做好具体安排。 （2）出口，包括信用证、商品检验、海关手续办理完毕，备齐货物，做出配载图及货物积载图，能连
粒子群算法综述
粒子群算法综述 【摘要】：粒子群算法(pso)是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已得到广泛研究和应用。为了进一步推广应用粒子群算法并为深入研究该算法提供相关资料，本文对目前国内外研究现状进行了全面分析，在论述粒子群算法基本思想的基础上，围绕pso的运算过程、特点、改进方式与应用等方面进行了全面综述，并给出了未来的研究方向展望。 【关键词】：粒子群算法优化综述 优化理论的研究一直是一个非常活跃的研究领域。它所研究的问题是在多方案中寻求最优方案。人们关于优化问题的研究工作，随着历史的发展不断深入，对人类的发展起到了重要的推动作用。但是，任何科学的进步都受到历史条件的限制，直到二十世纪中期，由于高速数字计算机日益广泛应用，使优化技术不仅成为迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。这些优化技术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、生产调度等。随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，常规优化法如牛顿法、车辆梯度法、模式搜索法、单纯形法等已经无法处理人们所面的复杂问题，因此高效的
优化算法成为科学工作者的研究目标之一。 1.粒子群算法的背景 粒子群算法(particle swarm optimization，pso)是一种新兴的演化算法。该算法是由j.kennedy和r.c.eberhart于1995年提出的一种基于群智能的随机优化算法。这类算法的仿生基点是：群集动物(如蚂蚁、鸟、鱼等)通过群聚而有效的觅食和逃避追捕。在这类群体的动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。如在蚁群中，当每个个体发现食物之后，它将通过接触或化学信号来招募同伴，使整个群落找到食源；在鸟群的飞行中，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，但随着时间推移，这些初始处于随机状态的鸟通过相互学习(相互跟踪)组织的聚集成一个个小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集在同一位置──食源。这些群集动物所表现的智能常称为“群体智能”，它可表述为：一组相互之间可以进行直接通讯或间接通讯(通过改变局部环境)的主体，能够通过合作对问题进行分布求解。换言之，一组无智能的主体通过合作表现出智能行为特征。粒子群算法就是以模拟鸟的群集智能为特征，以求解连续变量优化问题为背景的一种优化算法。因其概念简单、参数较少、易于实现等特点，自提出以来已经受到国内外研究者的高度重视并被广泛应用于许多领域。
基于MATLAB的粒子群优化算法的应用示例
对于函数f=x*sin(x)*cos(2*x)-2*x*sin(3*x)，求其在区间[0,20]上该函数的最大值。 ?初始化种群 已知位置限制[0,20],由于一维问题较为简单，因此可以取初始种群N 为50，迭代次数为100,当然空间维数d 也就是1。 位置和速度的初始化即在位置和速度限制内随机生成一个N×d 的矩阵，对于此题，位置初始化也就是在0~20内随机生成一个50×1的数据矩阵，而对于速度则不用考虑约束，一般直接在0~1内随机生成一个50×1的数据矩阵。 此处的位置约束也可以理解为位置限制，而速度限制是保证粒子步长不超限制的，一般设置速度限制为[-1,1]。 粒子群的另一个特点就是记录每个个体的历史最优和种群的历史最优，因此而二者对应的最优位置和最优值也需要初始化。其中每个个体的历史最优位置可以先初始化为当前位置,而种群的历史最优位置则可初始化为原点。对于最优值，如果求最大值则初始化为负无穷，相反地初始化为正无穷。 每次搜寻都需要将当前的适应度和最优解同历史的记录值进行对比，如果超过历史最优值，则更新个体和种群的历史最优位置和最优解。 ?速度与位置的更新
速度和位置更新是粒子群算法的核心，其原理表达式和更新方式如下: 每次更新完速度和位置都需要考虑速度和位置的限制，需要将其限制在规定范围内，此处仅举出一个常规方法，即将超约束的数据约束到边界（当位置或者速度超出初始化限制时，将其拉回靠近的边界处）。当然，你不用担心他会停住不动，因为每个粒子还有惯性和其他两个参数的影响。 代码如下： clc;clear;close all; %% 初始化种群 f= @(x)x .* sin(x) .* cos(2 * x) - 2 * x .* sin(3 * x); % 函数表达式figure(1);ezplot(f,[0,0.01,20]); N = 50; % 初始种群个数 d = 1; % 空间维数 ger = 100; % 最大迭代次数 limit = [0, 20]; % 设置位置参数限制 vlimit = [-1, 1]; % 设置速度限制 w = 0.8; % 惯性权重 c1 = 0.5; % 自我学习因子 c2 = 0.5; % 群体学习因子 for i = 1:d
粒子群优化算法介绍及matlab程序
粒子群优化算法(1)—粒子群优化算法简介 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0, 4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0, 4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物。 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化 第一次更新位置
第二次更新位置 第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。
粒子群优化算法(2)—标准粒子群优化算法 在上一节的叙述中，唯一没有给大家介绍的就是函数的这些随机的点（粒子）是如何运动的，只是说按照一定的公式更新。这个公式就是粒子群算法中的位置速度更新公式。下面就介绍这个公式是什么。在上一节中我们求取函数y=1-cos(3*x)*exp(-x)的在[0, 4]最大值。并在[0,4]之间放置了两个随机的点，这些点的坐标假设为x1=1.5，x2=2.5；这里的点是一个标量，但是我们经常遇到的问题可能是更一般的情况—x 为一个矢量的情况，比如二维z=2*x1+3*x22的情况。这个时候我们的每个粒子均为二维，记粒子P1＝(x11,x12),P2=(x21,x22),P3=(x31,x32)，......Pn=(xn1,xn2)。这里n 为粒子群群体的规模，也就是这个群中粒子的个数，每个粒子的维数为2。更一般的是粒子的维数为q ，这样在这个种群中有n 个粒子，每个粒子为q 维。 由n 个粒子组成的群体对Q 维（就是每个粒子的维数）空间进行搜索。每个粒子表示为：x i ＝（x i1,x i2,x i3,...,x iQ ），每个粒子对应的速度可以表示为v i =(v i1,v i2,v i3,....,v iQ )，每个粒子在搜索时要考虑两个因素： 1. 自己搜索到的历史最优值 p i ，p i =(p i1,p i2,....,p iQ )，i=1,2,3,....,n ； 2. 全部粒子搜索到的最优值p g ，p g =(p g1,p g2,....,p gQ )，注意这里的p g 只有一个。 下面给出粒子群算法的位置速度更新公式： 112()()()()k k k k i i i i v v c rand pbest x c rand gbest x ω+=+??-+??-, 11k k k i i i x x av ++=+. 这里有几个重要的参数需要大家记忆，因为在以后的讲解中将会经常用到，它们是： ω是保持原来速度的系数，所以叫做惯性权重。1c 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。2c 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。()rand 是[0,1]区间内均匀分布的随机数。a 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设置为1。这样一个标准的粒子群算法就介绍结束了。下图是对整个基本的粒子群的过程给一个简单的图形表示。 判断终止条件可是设置适应值到达一定的数值或者循环一定的次数。 注意：这里的粒子是同时跟踪自己的历史最优值与全局（群体）最优值来改变自己的位置预速度的，所以又叫做全局版本的标准粒子群优化算法。
粒子群算法解决函数优化问题
粒子群算法解决函数优化问题 1、群智能算法研究背景 粒子群优化算法（Particle Swarm Optimization，PSO）是由Kennedy 和Eberhart 在研究鸟类和鱼类的群体行为基础上于1995 年提出的一种群智能算法，其思想来源于人工生命和演化计算理论，模仿鸟群飞行觅食行为，通过鸟集体协作使群体达到优。 PSO算法作为一种新的群智能算法，可用于解决大量非线性、不可微和多峰值的复杂函数优化问题，并已广泛应用于科学和工程领域，如函数优化、神经网络训练、经济调度、模式识别与分类、结构设计、电磁场和任务调度等工程优化问题等。 PSO算法从提出到进一步发展，仅仅经历了十几年的时间，算法的理论基础还很薄弱，自身也存在着收敛速度慢和早熟的缺陷。如何加快粒子群算法的收敛速度和避免出现早熟收敛，一直是大多数研究者关注的重点。因此，对粒子群算法的分析改进不仅具有理论意义，而且具有一定的实际应用价值。 2、国内外研究现状 对PSO算法中惯性权重的改进：Poli等人在速度更新公式中引入惯性权重来更好的控制收敛和探索，形成了当前的标准PSO算法。 研究人员进行了大量的研究工作，先后提出了线性递减权值( LDIW)策略、模糊惯性权值( FIW) 策略和随机惯性权值( RIW) 策略。其中，FIW 策略需要专家知识建立模糊规则，实现难度较大，RIW 策略被用于求解动态系统，LDIW策略相对简单且收敛速度快， 任子晖，王坚于2009 年，又提出了基于聚焦距离变化率的自适应惯性权重PSO算法。 郑春颖和郑全弟等人，提出了基于试探的变步长自适应粒子群算
法。这些改进的PSO算法既保持了搜索速度快的特点, 又提高了全局搜索的能力。 对PSO算法的行为和收敛性的分析：1999 年采用代数方法对几种典型PSO算法的运行轨迹进行了分析，给出了保证收敛的参数选择范围。在收敛性方面Fransvan den Bergh引用Solis和Wets关于随机性算法的收敛准则，证明了标准PSO算法不能收敛于全局优解，甚至于局部优解；证明了保证收敛的PSO算法能够收敛于局部优解，而不能保证收敛于全局优解。 国内的学者：2006 年，刘洪波和王秀坤等人对粒子群优化算法的收敛性进行分析，指出它在满足收敛性的前提下种群多样性趋于减小，粒子将会因速度降低而失去继续搜索可行解的能力，提出混沌粒子群优化算法。 2008 年，黄翀鹏和熊伟丽等人分析惯性权值因子大小对PSO算法收敛性所带来的影响，对粒子群算法进行了改进。2009 年，高浩和冷文浩等人，分析了速度因子对微粒群算法影响，提出了一种基于Gaussian 变异全局收敛的粒子群算法。并证明了它能以概率 1 收敛到全局优解。 2010 年，为提高粒子群算法的收敛性,提出了基于动力系统的稳定性理论，对惯性权重粒子群模型的收敛性进行了分析，提出了使得在算法模型群模型收敛条件下的惯性权重和加速系数的参数约束关系，使算法在收敛性方面具有显著优越性。在PSO算法中嵌入别的算法的思想和技术。 1997年，李兵和蒋慰孙提出混沌优化方法； 1998年，Angeline在PSO算法中引入遗传算法中的选择算子，该算法虽然加快了算法的收敛速度，但同时也使算法陷入局部优的概率大增，特别是在优化Griewank 基准函数的优值时得到的结果不理想； 2004 年，高鹰和谢胜利将混沌寻优思想引入到粒子群优化算法中，首先对当前群体中的优粒子进行混沌寻优, 再用混沌寻优的结果随机替换群体中的一个粒子，这样提出另一种混沌粒子群优化算法。
粒子群优化算法及其应用研究【精品文档】(完整版)
摘要 在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，由于其几乎不存在对问题的约束，因此，粒子群优化算法在各种优化问题中得到广泛应用。 本文首先描述了基本粒子群优化算法及其改进算法的基本原理,对比分析粒子群优化算法与其他优化算法的优缺点，并对基本粒子群优化算法参数进行了简要分析。根据分析结果,研究了一种基于量子的粒子群优化算法。在标准测试函数的优化上粒子群优化算法与改进算法进行了比较,实验结果表明改进的算法在优化性能明显要优于其它算法。本文算法应用于支持向量机参数选择的优化问题上也获得了较好的性能。最后,对本文进行了简单的总结和展望。 关键词：粒子群优化算法最小二乘支持向量机参数优化适应度
目录 摘要...................................................................... 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)
港口拖轮调度系统
岚山港港口拖轮调度系统的功能 项目背景 日照岚山港位于黄海海州湾北岸，地处日照市岚山区佛手湾，岚山港水域较宽阔，水深条件较好，2万吨级泊位前沿自然水深可达10米。港区可利用自然岸线约6公里。陆域有发展余地，可填滩造陆。在这样得天独厚的自然条件下，发展日新月异，现年吞吐能力超过2000万吨。随着企业的发展进入瓶颈，信息化便成为各大企业必走之路。岚山港港务公司以及拖轮公司各部门相关领导历时近5年的时间，走访国内各大港口进行信息化建设的考察和调研，经过多方面的考察和同行业内的口碑相传，通过招标最终决定由大连君方科技有限公司承接此次岚山港拖轮公司信息化建设项目。 功能概述 本系统是大连君方科技有限公司为山东日照岚山港拖轮公司量身打造的一款功能强大的生产调度管理软件。该系统分为生产调度计划、生产调度计费、拖轮每日情况报告、报表查看以及系统管理五大功能模块。客户只需操作这五个模块就可以将实际业务很好的实现，使以调度为核心的安调室的日常办公更加简单、便捷、高效，体验名副其实的办公自动化。 生产调度计划：本系统的核心业务，由安调员将每日总调下发的调度计划，提交给安调室主任审批，审批通过后，安调员将计划安排给相应拖轮，拖轮确定安排后，方可执行。所有流程都在系统中进行，减少了沟通和审批时间；执行任务中的船舶可通过系统记录作业过程中的如备车、引水上下船、系解缆等工作的时间，确保了时间的准确性，方便计费。 生产调度计划功能包含：
●生产调度与计划 ●本日生产调度计划 ●调度计划审批 ●调度计划执行 ●生产调度历史综合查询 ●单船作业明细查询 生产调度计费：系统的特色功能模块，针对作业大船的船长、内外贸别等属性，根据港口各项计费标准来进行作业费用的计算，包含生产费用、海员出海补贴、附加费等。全部费用一键核算，安心，省心，更放心。 生产调度计费功能包含： ●生产费用核算 ●生产计费历史 ●海员出海补贴费用 拖轮每日情况报告：由各船每日填写船舶及在船人员情况，提交至安调室，只需一个画面便将整个大局尽收眼底，以便调度根据船舶情况，迅速调整计划安排，保证生产顺利进行，将时间延误降到最低，企业生产，时间就是金钱。 拖轮每日情况报告功能包含： ●拖轮每日情况报告 ●拖轮每日情况报告审批 ●拖轮每日情况报告历史 ●拖轮停航申请报告 ●拖轮停航申请审批
粒子群算法(1)----粒子群算法简介
粒子群算法(1)----粒子群算法简介 二、粒子群算法的具体表述 上面罗嗦了半天，那些都是科研工作者写论文的语气，不过，PSO的历史就像上面说的那样。下面通俗的解释PSO算法。 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO.中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0，4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0，4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的一定公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化
第一次更新位置 第二次更新位置
第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。
港口拖轮调度系统
xx港的功能 项目背景 日照岚山港位于黄海海州湾北岸，地处日照市岚山区佛手湾，岚山港水域较宽阔，水深条件较好，2万吨级泊位前沿自然水深可达10米。港区可利用自然岸线约6公里。陆域有发展余地，可填滩造陆。在这样得天独厚的自然条件下，发展日新月异，现年吞吐能力超过2000万吨。随着企业的发展进入瓶颈，信息化便成为各大企业必走之路。岚山港港务公司以及拖轮公司各部门相关领导历时近5年的时间，走访国内各大港口进行信息化建设的考察和调研，经过多方面的考察和同行业内的口碑相传，通过招标最终决定由大连君方科技有限公司承接此次岚山港拖轮公司信息化建设项目。 功能概述 本系统是大连君方科技有限公司为山东日照岚山港拖轮公司量身打造的一款功能强大的生产调度管理软件。该系统分为生产调度计划、生产调度计费、拖轮每日情况报告、报表查看以及系统管理五大功能模块。客户只需操作这五个模块就可以将实际业务很好的实现，使以调度为核心的安调室的日常办公更加简单、便捷、高效，体验名副其实的办公自动化。 生产调度计划： 本系统的核心业务，由安调员将每日总调下发的调度计划，提交给安调室主任审批，审批通过后，安调员将计划安排给相应拖轮，拖轮确定安排后，方可执行。所有流程都在系统中进行，减少了沟通和审批时间；执行任务中的船舶可通过系统记录作业过程中的如备车、引水上下船、系解缆等工作的时间，确保了时间的准确性，方便计费。 生产调度计划功能包含： 生产调度与计划 本日生产调度计划 调度计划审批
调度计划执行 生产调度历史综合查询 单船作业明细查询 生产调度计费： 系统的特色功能模块，针对作业大船的船长、内外贸别等属性，根据港口各项计费标准来进行作业费用的计算，包含生产费用、海员出海补贴、附加费等。全部费用一键核算，安心，省心，更放心。 生产调度计费功能包含： 生产费用核算 生产计费历史 海员出海补贴费用 拖轮每日情况报告： 由各船每日填写船舶及在船人员情况，提交至安调室，只需一个画面便将整个大局尽收眼底，以便调度根据船舶情况，迅速调整计划安排，保证生产顺利进行，将时间延误降到最低，企业生产，时间就是金钱。 拖轮每日情况报告功能包含： 拖轮每日情况报告 拖轮每日情况报告审批 拖轮每日情况报告历史 拖轮停航申请报告 拖轮停航申请审批 报表查看：
启发式优化算法综述【精品文档】(完整版)
启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题
时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。
基于粒子群优化算法的神经网络在
基于粒子群优化算法的神经网络在农药定量构效关系建模中的应用 张丽平 俞欢军3 陈德钊 胡上序 (浙江大学化工系,杭州310027) 摘 要 神经网络模型能有效模拟非线性输入输出关系,但其常规训练算法为BP 或其它梯度算法,导致训练时间较长且易陷入局部极小点。本实验探讨用粒子群优化算法训练神经网络,并应用到苯乙酰胺类农药的定量构效关系建模中,对未知化合物的活性进行预测来指导新药的设计和合成。仿真结果表明,粒子群优化算法训练的神经网络不仅收敛速度明显加快,而且其预报精度也得到了较大的提高。关键词 粒子群优化算法,神经网络,定量构效关系 2004201204收稿;2004207225接受 本文系国家自然科学基金资助项目(N o.20276063) 1 引 言 药物定量构效关系(QS AR )是研究药物生理活性和药物分子结构参数间的量变规律并建立相应的 数学模型,进而研究药物的作用机理,从而用于预测未知化合物的生物活性,探讨药物的作用机理,指导新药的设计和合成,在药物和农药的研究与设计中已经显示出广阔的应用前景1。以往QS AR 的建模方法大多基于统计原理,局限于线性模型,只进行简单的非线性处理,由此所建立的模型很难契合实际构效关系,并且其处理过程都比较繁琐2。神经网络通过学习将构效关系知识隐式分布在网络之中,适用于高度非线性体系。 在药物QS AR 中采用神经网络(NN )始于20世纪80年代末3,此后得到迅速的发展,目前已发展为除多重线性回归和多元数据分析之外的第3种方法4。通常多层前传网络采用BP 算法,通过误差反传,按梯度下降的方向调整权值。其缺点是可能陷入局部极小点,且对高维输入收敛速度非常缓慢。 粒子群优化算法(particle swarm optimization ,PS O )是K ennedy 等5源于对鸟群、鱼群和人类社会行为的研究而发展的一种新的进化型寻优技术。PS O 已成为进化寻优算法研究的热点,其最主要特点是简单、收敛速度快,且所需领域知识少。本实验拟将该方法初始化前传神经网络为苯乙酰胺类农药建立良好适用的QS AR 模型。 2 苯乙酰胺类农药的Q SAR 问题 苯乙酰胺类化合物是除草农药,其除草活性与其分子结构密切相关。所有的N 2(12甲基212苯乙基)苯乙酰胺都可用相应的羧酸酰胺通过霍夫曼反应生成。N 2(12甲基212苯乙基)苯乙酰胺的基本结构式为 : 其中X 为Me 、F 、Cl 、OMe 、CF 3和Br 等,Y 为Me 、Cl 、F 和Br 等,由不同的X 和Y 取代基可构成不同的化合物。常用以下7个理化参数描述化合物的分子组成和结构:log P 、log 2P (疏水性参数及其平方项)、 σ(电性效应参数)、E s (T aft 立体参数)、MR (摩尔折射度),1χ、2 χ(分子连接性指数)。于是这类化合物的QS AR 就转化为上述理化参数与除草活性间的关系。为研究这种关系,选用具有代表性的50个化合物, 他们的活性值取自文献1,见表1。 第32卷2004年12月分析化学(FE NXI H UAX UE ) 研究报告Chinese Journal of Analytical Chemistry 第12期1590～1594