收稿日期:2009-06-16;修回日期:2009-07-20 基金项目:国家“863”计划资助项目(2006A A 040308)
作者简介:杜祜康(1983-),男,江苏睢宁人,硕士研究生,主要研究方向为混杂系统建模、控制、优化(d u h u k a n g @126.c o m );赵英凯(1943-),男,江苏镇江人,教授,博导,主要研究方向为智能控制、先进控制.
整数规划问题智能求解算法综述
＊
杜祜康,赵英凯
(南京工业大学自动化与电气工程学院,南京210009)
摘 要:为了对大规模整数规划问题的求解方法提供参考,对基于智能算法求解整数规划问题的研究进行了分析和评述。鉴于现有算法的缺陷与不足,讨论了应用智能算法求解整数规划问题未来可能的研究方向。
关键词:整数规划;遗传算法;分布估计算法;粒子群算法;蚁群算法;D N A 计算;问题求解中图分类号:T P 301 文献标志码:A 文章编号:1001-3695(2010)02-0408-05d o i :10.3969/j .i s s n .1001-3695.2010.02.003
S u r v e y o n i n t e l l i g e n t o p t i m i z a t i o n a l g o r i t h m s f o r s o l v i n g
i n t e g e r p r o g r a m m i n g p r o b l e m s
D UH u -k a n g ,Z H A OY i n g -k a i
(S c h o o l o f A u t o m a t i o n ＆E l e c t r i c a l E n g i n e e r i n g ,N a n j i n gU n i v e r s i t y o f T e c h n o l o g y ,N a n j i n g 210009,C h i n a )
A b s t r a c t :I n o r d e r t o p r o v i d e r e f e r e n c e o f w a y s f o r s o l v i n g l a r g e -s c a l e i n t e g e r p r o g r a m m i n g p r o b l e m s ,t h e p a p e r m a d e a n a n a l y -s i s a n dc o m m e n t o n r e s e a r c h o f s o l v i n g i n t e g e r p r o g r a m m i n g p r o b l e m s b a s e d o n i n t e l l i g e n t a l g o r i t h m s .I n v i e wo f t h e s h o r t c o m -i n g s o f c u r r e n t a l g o r i t h m s ,d i s c u s s e d s o m e p o s s i b l e f u t u r e r e s e a r c h d i r e c t i o n s a b o u t i n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s f o r s o l -v i n g i n t e g e r p r o g r a m m i n g p r o b l e m .
K e y w o r d s :i n t e g e r p r o g r a m m i n g (I P );g e n e t i c a l g o r i t h m s (G A );e s t i m a t i o no f d i s t r i b u t i o na l g o r i t h m s ;p a r t i c l e s w a r mo p t i -m i z a t i o n ;a n t c o l o n y o p t i m i z a t i o n ;D N Ac o m p u t i n g ;p r o b l e m -s o l v i n g
引言
整数规划(I P )和混合整数规划(m i x e d i n t e g e r p r o g r a m m i n g ,M I P )问题是运筹学领域里的一个重要分支,机械、化工、计算机、经济、生物、军事、社会等各个学科领域里的许多优化问题均可归结为I P 或M I P 问题,且大多数的组合优化问题都可以写成一个I P 或M I P 问题,如背包、旅行商、最短路、选址、分配和生产与存储计划问题等。因此如何求解I P 或M I P 问题是一个重要的研究领域。虽然整数规划问题的解空间在结构上比连续问题好确定,但其解的计算却十分困难。尽管持续不断的理论研究已有几十年时间,加之计算机速度和功能的惊人增加,整数规划求解算法的研究还是没能达到令人十分满意的结果。由于整数规划问题的可行解区域为离散点,故一般不能用连续区域的求解算法,只能用特殊方法求解,应用较多的传统方法是分支定界法[1](b r a n c h a n db o u n dm e t h o d )、割平面法[2](c u t t i n g p l a n ea l g o r i t h m )和分解算法[3～5](d e c o m p o s i t i o na l g o -r i t h m ),其他常规方法有图论法[6]、交集及交集余集解法[7]、罚函数法[8]、群论法[9]等。
传统的整数规划问题的求解算法是一种确定性算法,即从一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系,其结果得到的是一个惟一最优解,对小规模整数规划问题求解效果较佳;而当求解问题的规模较大时,其计算量相当可观,计算时间将极大地增加,甚至无法求解问题。与之相对应的智能优化算法大多采用并行搜索技术,克服了传统整数规
划解法的单点搜索效率低的问题,在实际优化问题应用中具有较大的灵活性,对大规模的整数规划问题的求解较为有效。本文主要对智能优化算法在求解整数规划问题中的应用进行分析总结,以期对大规模整数规划问题的求解提供方法参考,并在文章最后给出了关于整数规划问题求解的思考与展望。
整数规划问题求解的群体智能优化算法
群体智能优化算法是一类从生物群体的角度对智能进行模拟的随机搜索算法,主要包括遗传、分布估计、粒子群和蚁群算法等。它不依赖于梯度信息的群体搜索策略及群体中个体之间信息交换的特点,可以用来解决许多传统搜索方法解决不了的复杂问题,对求解可行解区域为离散点的大规模整数规划问题十分有效。
. 基于遗传算法的整数规划问题求解
遗传算法[10,11](G A )是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化的概率算法。在遗传算法中,用种群表示优化问题的一组候选解,种群中的每个个体都有相应的适应值,然后反复进行选择、交叉和变异等模拟自然进化的操作,对问题进行求解。G A 基于模式定理产生群体中的最优个体,故其对目标函数和约束条件的要求比较低,特别是对于纯整数规划问题,由于存在有限的可行解空间,采用适当的遗传算法可以较快地得到全局最优解或最优近似解[12,13]。此外,由于它是一种概率算法,还有可能得到一系列
第27卷第2期2010年2月 计算机应用研究A p p l i c a t i o n R e s e a r c h o f C o m p u t e r s V o l .27N o .2
F e b .2010
的最优调度策略。
为了提高遗传算法在求解整数规划问题时的寻优收敛速度和求解效率,在决策变量和约束条件很多时,大部分文献对遗传算法的编码和算子进行了改进。刘树安等人[14]提出一种新的位串编码结构,采用一种新的加速变异算子,并为保持种群多样性引入分散型淘汰法;文献[15]采用二进制映射模式可变长度染色体编码,在进化过程逐渐缩小编码的搜索空间,可以在加快收敛速度的同时改善迭代精度;文献[16]采用基于参考解更新的双字符串扩展遗传算法,在进化过程提高整数规划松弛问题优化解的搜索效率;混合染色体编码方式[17]也是一种有效编码的方法。为了弥补遗传算法的缺陷,常将遗传算法与其他算法相结合来求解整数规划问题,主要有遗传算法与混沌的结合[18],遗传算法与罚函数的结合[19],遗传算法、线性规划与序优化方法相结合[20],遗传算法与分支定界法相结合[21]。对于大规模整数规划问题,采用变分组技术[22,23]从减小搜索空间维数入手,也不失为一种有效方法。当然,遗传算法对于多目标整数规划[24,25]、0-1规划[26]等特殊整数规划问题的求解已有较深入的应用。
在求解整数规划问题的应用中,G A具有计算速度快且易与其他算法相结合的优点,其多种编码方式和各种改进的算子克服了遗传算法的部分缺陷。但在计算过程中遗传算法会出现早熟问题,特别是对于全局最优解被最差解包围的大海捞针问题,隔断了模式的重组过程,使得G A搜索长期陷入局部极值点。
. 基于分布估计算法的整数规划问题求解
分布估计算法[27～29](e s t i m a t i o no f d i s t r i b u t i o na l g o r i t h m s, E D A s)是最近几年在进化计算领域兴起的一类新型的进化算法,这种算法可以显式地表示变量之间的关系,能快速、准确、可靠地解决传统算法束手无策的一类优化问题。与遗传算法相比,分布估计算法提出了一种全新的进化模式,没有交叉、变异等遗传操作,取而代之的是概率模型的学习和采样。分布估计算法通过一个概率模型描述候选解在空间的分布,然后采用统计学习手段从群体的角度建立一个描述解空间分布的概率模型,再对概率模型随机采样产生新的种群,如此反复,实现种群的进化。
分布估计算法提出较晚,目前还鲜有应用于求解一般整数规划问题,大多数文献只是将其应用于求解一些特殊的整数规划问题。文献[30]较为全面地介绍了分布估计算法在求解整数规划问题中的应用,如0-1背包问题、旅行商问题和J o b-S h o p 调度问题等;P a u l等人[31]讨论了E D A s在子集和问题、O n e M a x 函数、n-Q u e e n问题中的应用;此外,文献[32]采用贝叶斯优化算法求解帕累托解集和多维0-1背包问题;文献[33]用来求解最大团和复杂数据结构问题;文献[34]用来求解欺骗问题。在算法的改进方面主要有文献[35]对分布估计算法进行了改进并将其应用到多维背包问题;文献[36]应用带变异分布估计算法求解非线性整数规划问题,但其对求解问题的决策变量进行了范围限制。
较之遗传算法,分布估计算法是在群体宏观层面上的数学建模,在搜索能力和效率上具有很大优势。概率模型的选择与学习是分布估计算法的核心,但基于有限样本的复杂模型学习本身是一个相当复杂的问题,而且概率模型的学习或多或少存在着对先验知识的依赖,因此如何设计更为有效的模型学习方法是提高E D A s求解整数规划问题计算效率的难点之一。
. 基于粒子群算法的整数规划问题求解
粒子群算法[37,38](p a r t i c l e s w a r m o p t i m i z a t i o n,P S O)最早由美国科学家K e n n e d y和E b e r h a r t在1995年提出,它是模拟鸟类的觅食行为受到生物群体模型启发而设计的一种智能算法。P S O算法与其他进化算法相类似,采用群体探索问题的解空间,所不同的是群体中的每一个体按照一定的自适应速度在解空间随机搜索,同时每一个体记忆自己所搜索解空间的最好位置,并以一定的加速度向自己所经历的最好位置和群体中所有个体所经历的最好位置飞行。
如何将P S O算法应用于整数规划问题求解,文献[39,40]较早地对这个问题进行了研究。在对基本P S O算法进行分析的基础上,文献[41]提出了一种保证微粒群在进化过程中始终控制在整数空间内的直接进行进化计算的P S O算法,避免了不必要的实数域搜索,提高了寻优效率。量子粒子群优化算法[42](q u a n t u m-b e h a v e dP S O)用于求解整数规划问题的优势是引入了量子行为来增强粒子的全局收敛能力。K i t a y a m a等人[43]提出离散变量处理技术,将离散决策变量看做一个罚函数来求解混合整数规划问题;文献[44]使用两种变异粒子群即基本要素粒子群(b a r e b o n e s p a r t i c l e s w a r m)和扩展基本要素粒子群(e x p l o i t i n g b a r e b o n e s p a r t i c l e s w a r m)来求解整数规划也是有效的。此外,整数资源配置的优化问题[45]、任务分配问题[46]也都涉及到使用粒子群优化算法来求解整数规划问题。
使用P S O来求解整数规划问题,其优点是算法容易实现、控制参数少,因每次计算迭代结果应为整数,所以应用P S O求解整数规划的关键是如何处理每次迭代后的数值,且应用P S O 计算也会出现解的早熟问题。
. 基于蚁群算法的整数规划问题求解
蚁群算法[47,48](a n t c o l o n y o p t i m i z a t i o n,A C O)是意大利学者D o r i g o受自然界中真实蚁群集体行为的启发于1991年提出的一种新型优化算法,并成功地用于求解旅行商问题。蚂蚁在运动过程中,在它所经过的路径上留下信息素,并感知信息素的存在及其强度,朝着强度高的方向移动。因此,由大量蚂蚁组成的蚁群集体行为表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,后来的蚂蚁选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流进行路径的最优选择,从而达到搜索食物的目的。蚁群算法正是充分利用了这样的优化机制,即通过个体之间的信息交流与相互协作最终找到满意解。
鉴于蚁群算法具有很强的发现最优解的能力,很多学者纷纷将其应用于整数规划问题的求解。文献[49]应用蚁群算法解决了典型的无约束整数规划问题;文献[50]将蚁群算法中基于信息素的正反馈方法引入到求解整数规划演化算法之中,实现了每一个体等位基因的优化,使算法稳定地收敛到全局最优解;文献[51]正是通过蚂蚁之间的信息交流进行路径的最优选择来解决机组组合优化问题。林锦等人[52]将蚁群算法作适当改进,用于解凸整数规划问题;S c h lǜt e r等人[53]则将蚁群
·
409
·
第2期杜祜康,等:整数规划问题智能求解算法综述
算法改进后成功用于求解非凸整数规划问题。对于背包问题这类特殊的整数规划问题的求解,文献[54]给予了较详尽的介绍;S e c k i n e r 等人[55]提出两种改进蚁群算法较好地解决了岗位轮换调度中的整数规划问题;文献[56]采用改进蚁群算法来解决分批交货的车辆路径问题的整数规划模型;文献[57]使用蚁群系统(A C S )结合A S R a n k 和M M A S 蚁群算法的信息素更新策略来解决逆向物流车辆路径问题的混合整数规划模型。
蚁群算法的生物学背景决定了它适合于求解离散空间中的组合优化问题,采用分布式并行运算机制,易于与其他算法相结合,具有很强的鲁棒性和适应性。该算法的搜索时间过长,大部分计算时间被用于解的构造,在执行过程中容易出现停滞现象,当求解整数规划问题规模较大时还可能陷入局部最优解,这也是目前大部分应用A C O 求解整数规划问题的文献大多对基本蚁群算法进行改进的原因。
计算求解整数规划问题
D N A 计算[58,59]是一种模拟生物分子D N A 的结构并借助
于分子生物技术进行计算的新方法。其基本思想是:利用D N A 特殊的双螺旋结构和碱基互补配对原则对问题进行编码,把要运算的对象映射成D N A 分子链,在D N A 溶液的试管里,在生物酶的作用下生成各种数据池;然后按照一定的规则将原始问题的数据运算高度并行地映射成D N A 分子链可控的生化过程;最后,利用分子生物技术获得运算结果。
在求解整数规划问题中很多学者将目光投向了具有特殊优势的D N A 计算。文献[60]采用荧光标记的策略,提出了一种基于D N A 计算的将决策变量的取值限定在[-1,0,1]之中的特殊整数规划问题求解算法;文献[61]提出了约束方程变量分解的概念,通过将约束方程进行分解和增加约束补链的方法将决策变量取值扩展到了[-T i ,T i ]。Y i nZ h i -x i a n g 等人[62]同样采用基于表面的D N A 计算荧光标记策略,解决了正整数线性规划问题;WA N GS h i -y i n g 等人[63]详细讨论了D N A 算法对于整数规划的求解,但其面向的整数规划问题要么是正整数线性规划,要么是决策变量取值限定在[0,1],或是对整数规划问题的系数附加特殊要求。而采用荧光分子信标杂交后的互补D N A 来求解整数线性规划问题[64],具有解读、编码简单、计算时间短和错误率低等优势;此外,D N A 计算在0-1整数线性规划
[65,66]
、0-1背包问题
[67]
等特殊的整数规划中的应
用已十分广泛。
D N A 计算的高度并行性和海量的信息存储能力在求解整数规划问题中,一方面有助于提高群体中个体的多样性,从而使获取最优解的可能性大大增加;另一方面D N A 计算的显式并行性,运算速度快,群体规模的增大并不会明显导致计算时间的增加,对求解属于N P 问题的组合优化具有天生的优势。但从目前文献来看,D N A 计算还没有完全应用到一般整数规划问题的求解。当然,现有的生化技术目前还难以应付计算中各种复杂的适应度函数,生化反应的不完备性可能会导致各种不可预测的错误结果。
整数规划问题求解的其他智能算法
对于求解整数规划问题,除了上面所提到的智能计算方法
外,文献[68]采用改进进化规划求解线性约束的整数规划和混合整数规划问题,其高速精确的性能取得了较满意的求解结果;文献[69]应用差分进化的两个变体,即自适应差分进化与使用环邻域拓扑的差分进化来求解整数规划问题,且其求解结果要优于标准差分进化和粒子群优化算法。李彤等人[70]针对整数规划全局优化问题首次提出模拟植物生长算法,该算法从植物的向光性特点出发,将整数规划的可行域作为植物的生长环境,根据各可行解目标函数的变化情况确定植物的生长信息(形态素浓度),进而模拟出向光源(全局最优解)迅速生长的植物生长动力学模型。文献[71]提出混合进化算法用于求解混合整数规划问题,在进化算法中采用一种混合启发式变异算子,将正交试验设计作为杂交算子,并引入一种迁移算子增加种群的多样性。文献[72]提出了基于相似性学习的自适应演化算法,从而使得变异算子具有了很强的导向性,避免了传统达尔文演化策略的半盲目性。其他的还有分散搜索算法[73]、禁忌搜索算法[74]和膜计算[75]等;此外,使用混合算法求解整数规划问题也较为广泛,如蚁群算法与粒子群算法的混合[76]、神经网络与遗传算法的混合[77]和混沌神经网络[78]。
结束语
以上对整数规划问题的智能求解算法进行了较为全面的分析与总结。虽然进化计算(G A 、E D A s 、P S O 、A C O )和D N A 计算是从生物群体、生物分子不同的层次对智能的模拟进行问题求解,但它们都是对问题的整个参数空间给出编码方案,都采用并行搜索技术,在搜索中用到的都是随机变换规则。此外,由于混合整数规划问题计算复杂度是随整数变量增加而增加的,对于求解整数规划问题的智能算法只要稍作修改,对混合整数规划问题求解同样适用。
整数规划问题的智能求解算法研究至今方兴未艾,还有许多有价值的问题有待进一步的深入研究:
a )对求解整数规划问题智能算法的结构、参数及操作算子进行改进研究。虽然很多学者对此已展开了研究,但这方面仍旧有很大的研究空间。
b )目前很多智能算法只是用来求解一些特殊的整数规划问题,还应对其完全求解一般整数规划问题进行扩展研究。
c )智能算法不是传统的确定性的计算工具,对整数规划问题的求解不是确定性的,应展开问题解的评价标准研究。
d )发展各种可能的求解整数规划问题的高效并行或分布式混合优化算法,如D N A 计算与进化计算的集成研究。构造更有效的混合智能优化算法还有很多工作可以做,其发展空间很大,期待更好算法的出现。参考文献:
[1]
S H E R A L I HD ,D R I S C O L LPJ .E v o l u t i o na n ds t a t e -o f -t h e -a r t i n i n -t e g e r p r o g r a m m i n g [J ].J o u r n a l o fC o mp u t a t i o n a l a n d A p p l i e d M a t h e ma t i c s ,2000,124(1-2):319-340.[2]
G O M O R YRE .O u t l i n eo f a na l g o r i t h mf o r i n t e g e r s o l u t i o n s t o l i n e a r p r o b l e m[J ].B u l l e t i n o f t h eA me r i c a n M a t h e ma t i c a l S o c i e t y ,1958,64(5):275-278.[3]
B E L LDE ,S H A P I R O J F .Ac o n v e r g e n t d u a l i t yt h e o r yf o r i n t e g e r p r o g r a m m i n g [J ].O p e r a t i o n sR e s e a r c h ,1977,25(3):419-443.
·410·计算机应用研究 第27卷
[4]F I S H E RM L.T h eL a g r a n g i a nr e l a x a t i o nm e t h o df o r s o l v i n gi n t e g e r
p r o g r a m m i n gp r o b l e m s[J].M a n a g e m e n tS c i e n c e,2004,50
(12):1861-1874.
[5]G U I G N A R DM.O ns o l v i n gs t r u c t u r e di n t e g e r p r o g r a m m i n g p r o b l e m s
w i t hL a g r a n g i a n r e l a x a t i o na n d/o r d e c o m p o s i t i o n[C]//P r o co f I E E E
C o n f e r e n c e o n
D e c i s i o na n dC o n t r o l.P i s c a t a w a y:I
E E EP r e s s,1989:
1136-1141.
[6]谭尚旺,张德龙.一类整数规划的图论解法[J].石油大学学报:自
然科学版,2003,27(2):124-129.
[7]冯振笑,柯越华.整数规划的交集及交集余集解法[J].石油大学
学报:自然科学版,2001,25(2):122-125.
[8]孟志青,胡奇英,杨晓琪.一种求解整数规划与混合整数规划非线
性罚函数方法[J].控制与决策,2002,17(3):310-314.
[9]黎青松,周双贵,杜文.用群论方法求解整数规划问题的初步探讨
[J].西南交通大学学报,2000,35(4):417-420.
[10]H O L L A N D J H.A d a p t a t i o ni nn a t u r a l a n da r t i f i c i a l s y s t e m s[M].
C a m b r i d g e:M I TP r e s s,1992:1-20.
[11]G O L D B E R GD E.G e n e t i ca l g o r i t h m s i ns e a r c h,o p t i m i z a t i o n,a n d
m a c h i n e l e a r n i n g[M].B o s t o n:A d d i s o n-We s l e y,1989:1-217. [12]R E N D E R SJ M,F L A S S ESP.H y b r i dm e t h o d s u s i n gg e n e t i ca l g o-
r i t h m s f o r g l o b a l o p t i m i z a t i o n[J].I E E ET r a n so nS y s t e m,Ma n,
a n dC y
b e r n e t i
c s,P a r t B:C y b e r n e t i c s,1996,26(2):243-258.
[13]M A L A S R I S,M A R T I NJ R,M E D I N ARA,e t a l.S o l v i n g m a t h e m a-
t i c a l p r o g r a m m i n g p r o b l e m s u s i n g g e n e t i c a l g o r i t h m s[C]//P r o c o f t h e 3r dC o n f e r e n c e o nC o m p u t i n g i nC i v i l E n g i n e e r i n g.1996:233-239.
[14]刘树安,郑秉霖,王梦光.基于G A s求解整数规划问题的算法设
计[J].东北大学学报:自然科学版,1998,19(2):198-200. [15]丰建荣,刘志河,刘正和.混合整数规划问题遗传算法的研究及仿
真实现[J].系统仿真学报,2004,16(4):845-848.
[16]S A K A WA M,K A T O K.I n t e g e r p r o g r a m m i n gt h r o u g hg e n e t i ca l g o-
r i t h m s w i t h d o u b l e s t r i n g s b a s e d o nr e f e r e n c e s o l u t i o n u p d a t i n g[C]//
P r o c o f t h e26t h A n n u a l C o n f e r e n c e o nI n d u s t r i a l E l e c t r o n i c s S o c i e t y.
2000:2744-2749.
[17]L I N Y C,H WA N G K S,WA N G F e n g-s h e n g.A m i x e d-c o d i n g
s c h e m eo f e v o l u t i o n a r ya l g o r i t h m st os o l v em i x e d-i n t e g e rn o n l i n e a r p r o g r a m m i n gp r o b l e m s[J].C o m p u t e r s a n dM a t h e m a t i c sw i t hA p-p l i c a t i o n s,2004,47(8-9):1295-1307.
[18]宁伟华,陈绍顺,王凤山.求解整数规划的混合遗传算法[J].空
军工程大学学报:自然科学版,2004,5(6):80-83.
[19]L I Y i n-x i u,G E NM.N o n l i n e a r m i x e di n t e g e r p r o g r a m m i n g p r o b l e m s
u s i n g g e n e t i c a l g o r i t h ma n d p e n a l t y f u n c t i o n[C]//P r o c o f I E E EI n t e r-n a t i o n a l C o n f e r e n c eo nS y s t e m s,M a na n dC y b e r n e t i c s.P i s c a t a w a y:
I E E EP r e s s,1996:2677-2682.
[20]L U OY C,C H E NCH,G U I G N A R DM.A ne f f i c i e n t a p p r o a c hi n-
t e g r a t i n g g e n e t i c a l g o r i t h m,l i n e a r p r o g r a m m i n g,a n d o r d i n a l o p t i m i z a-t i o n f o r l i n e a r m i x e d-i n t e g e r p r o g r a m m i n g p r o b l e m s[J].I n t e r n a t i o n a l J o u r n a l o f S ma r t E n g i n e e r i n gS y s t e m D e s i g n,2001,3(4): 279-287.
[21]F R E N C H AP,R O B I N S O NAC,WI L S O NJ M.U s i n g ah y b r i d g e-
n e t i c-a l g o r i t h m/b r a n c ha n db o u n da p p r o a c ht os o l v ef e a s i b i l i t ya n d o p t i m i z a t i o ni n t e g e r p r o g r a m m i n gp r o b l e m s[J].J o u r n a l o f H e u r i s-t i c s,2001,7(6):551-564.
[22]H U AZ h o n g-s h e n g,H U A N GF e i-h u a.Av a r i a b l e-g r o u p i n g b a s e d g e-
n e t i ca l g o r i t h mf o r l a r g e-s c a l ei n t e g e r p r o g r a m m i n g[J].I n f o r ma t i o n S c i e n c e s,2006,176(19):2869-2885.[23]H U AZ h o n g-s h e n g,H U A N GF e i-h u a.A ne f f e c t i v eg e n e t i ca l g o r i t h m
a p p r o a c ht o l a r g e s c a l e m i x e di n t e g e r p r o g r a m m i n g p r o
b l e m s[J].A p-
p l i e dM a t h e ma t i c s a n dC o m p u t a t i o n,2006,174(2):897-909.
[24]H A D J-A L O U A N EAB,B E A NJ C.G e n e t i ca l g o r i t h m f o r t h em u l t i-
p l e-c h o i c ei n t e g e r p r o g r a m[J].O p e r a t i o n sR e s e a r c h,1997,45
(1):92-101.
[25]黄樟灿.多目标整数规划中的遗传算法[J].武汉大学学报:自然
科学版,1999,45(5B):755-757.
[26]Y A N OH,S A K A WAM,S H I B A N OT.F u z z y m u l t i o b j e c t i v e0-1p r o-
g r a m m i n g t h r o u g hr e v i s e d g e n e t i c a l g o r i t h m s[C]//P r o c o f t h e2n d I n-
t e r n a t i o n a l C o n f e r e n c e o nK n o w l e d g e-b a s e d I n t e l l i g e n t E l e c t r o n i c S y s-
t e m s.1998:101-108.
[27]周树德,孙增圻.分布估计算法综述[J].自动化学报,2007,33
(2):113-124.
[28]Z H A N GQ i n g-f u,S U NJ i a n-y o n g,T S A N GE,e t a l.H y b r i de s t i m a-
t i o n o f d i s t r i b u t i o na l g o r i t h mf o r g l o b a l o p t i m i z a t i o n[J].E n g i n e e r i n g
C o m p u t a t i o n s,2004,21(1):91-107.
[29]P E L I K A NM,G O L D B E R GDE,e t a l.As u r v e yo f o p t i m i z a t i o nb y
b u i l d i n g a n du s i n g p r o b a b i l i s t i cm o d e l s[J].C o m p u t a t i o n a l O p t i mi-
z a t i o na n dA p p l i c a t i o n s,2002,21(1):5-20.
[30]L A R R A A G AP,L O Z A N O J A.E s t i m a t i o no f d i s t r i b u t i o na l g o r i t h-
m s:a n e wt o o l f o r e v o l u t i o n a r y c o m p u t a t i o n[M].S a nF r a n c i s c o:K l u-
w e r A c a d e m i cP u b l i s h e r s,2002:1-30.
[31]P A U LTK,I B A H.L i n e a r a n dc o m b i n a t o r i a l o p t i m i z a t i o n s b ye s t i-
m a t i o n o f d i s t r i b u t i o n a l g o r i t h m s[C]//P r o c o f t h e9t hM P SS y m p o s i-
u mo n E v o l u t i o n a r yC o m p u t a t i o n.2002:1-8.
[32]S C H WA R ZJ,O C E N E K J.M u l t i o b j e c t i v eB a y e s i a no p t i m i z a t i o n
a l g o r i t h mf o r c o m
b i n a t o r i a l p r o b l e m s:t h e o r y a n d p r a
c t i c e[J].N e u r a l
N e t w o r kWo r l d,2001,11(5):423-441.
[33]Z H A N G Q i n g-f u,S U N J i a n-y o n g,T S A N GE.C o m b i n a t i o n s o f e s t i-
m a t i o n o f d i s t r i b u t i o na l g o r i t h m s a n do t h e r t e c h n i q u e s[J].I n t e r n a-
t i o n a l J o u r n a l o f A u t o m a t i o na n dC o mp u t i n g,2007,4(3):273-
280.
[34]丁才昌,殷晓东,卢露,等.基于概率模型的分布估计算法求解欺
骗问题[J].长江大学学报:自然科学版,2008,5(4):350-352. [35]杨广益,欧阳智敏,全惠云.松驰互补的分布估计算法求解多维背
包问题[J].计算机工程与应用,2007,43(12):77-80.
[36]刘明芳.基于分布估计算法的整数规划研究[D].武汉:武汉理工
大学,2008.
[37]K E N N E D Y J,E B E R H A R TR.P a r t i c l es w a r m o p t i m i z a t i o n[C]//
P r o co f I E E E I n t e r n a t i o n a l C o n f e r e n c eo nN e u r a l N e t w o r k s.P i s c a-t a w a y:I E E EP r e s s,1995:1942-1948.
[38]S H I Y u-h u i,E B E R H A R TR.P a r a m e t e r s e l e c t i o ni np a r t i c l es w a r m
o p t i m i z a t i o n[C]//P r o c o f t h e7t hI n t e r n a t i o n a l C o n f e r e n c e o nE v o l u-
t i o n a r yP r o g r a m m i n g.[S.l.]:S p r i n g e r-V e r l a g,1998:591-600. [39]P A R S O P O U L O S K,V R A H A T I SM.R e c e n t a p p r o a c h e s t o g l o b a l o p-
t i m i z a t i o np r o b l e m s t h r o u g hp a r t i c l e s w a r m o p t i m i z a t i o n[J].N a t u r a l
C o m p u t i n g,2002,1(2-3):235-306.
[40]L A S K A R I E,P A R S O P O U L O S K,V R A H A T I SM.P a r t i c l e s w a r mo p-
t i m i z a t i o nf o r i n t e g e r p r o g r a m m i n g[C]//P r o co f C o n g r e s s o nE v o l u-
t i o n a r y C o m p u t a t i o n.Wa s h i n g t o n D C:I E E EC o m p u t e r S o c i e t y,2002: 1582-1587.
[41]谭瑛,高慧敏,曾建潮.求解整数规划问题的微粒群算法[J].系
统工程理论与实践,2004,24(5):126-129.
[42]刘静,须文波,孙俊.基于量子粒子群算法求解整数规划[J].计
算机应用研究,2007,24(3):79-81.
·
411
·
第2期杜祜康,等:整数规划问题智能求解算法综述
[43]K I T A Y A M A S,Y A S U D A K.Am e t h o df o r m i x e di n t e g e r p r o g r a m-
m i n gp r o b l e m s b yp a r t i c l es w a r m o p t i m i z a t i o n[J].E l e c t r i c a l E n g i-n e e r i n gi nJ a p a n,2006,157(2):40-49.
[44]O M R A NM GH,E N G E L B R E C H TA,S A L M A NA.B a r e b o n e s p a r t i-
c l es w a r m f o ri n t e g e rp r o g r a m m i n gp r o b l e m s[C]//P r o co fI E E E
S w a r mI n t e l l i g e n c eS y m p o s i u m.2007:170-175.
[45]Q I UQ i-r o n g,Z H A N GY o n g-f a n g.P a r t i c l e s w a r m o p t i m i z a t i o nf o r i n-
t e g e r r e s o u r c ea l l o c a t i o np r o b l e m[C]//P r o co f I n t e r n a t i o n a l C o n f e-r e n c eo nR i s k M a n a g e m e n t a n d E n g i n e e r i n gM a n a g e m e n t.2008:141-144.
[46]S A L MA NA,A H M A D I,A L-M A D A N I S.P a r t i c l es w a r m o p t i m i z a-
t i o n f o r t a s ka s s i g n m e n t p r o b l e m[J].Mi c r o p r o c e s s o r sa n dM i c r-o s y s t e ms,2002,26(8):363-371.
[47]段海滨,王道波,朱家强,等.蚁群算法理论及应用研究的进展
[J].控制与决策,2004,19(12):1321-1326.
[48]D O R I G OM,B I R A T T A R I M,S T T Z L ET.A n t c o l o n yo p t i m i z a t i o n
a r t i f i c i a l a n t sa sac o m p u t a t i o n a l i n t e l l i g e n c et e c h n i q u e[J].I E E E
C o m p u t a t i o n a l I n t e l l i g e n c eM a g a z i n e,2006,1(4):28-39.
[49]高尚,杨静宇.非线性整数规划的蚁群算法[J].南京理工大学学
报,2005,29(增刊):120-123.
[50]黄樟灿,吴方才,胡晓林.基于信息素的整数规划的演化求解
[J].计算机应用研究,2001,18(7):27-29.
[51]S I M O NS P,P A D H YNP,A N A N DR S.A na n t c o l o n ys y s t e m a p-
p r o a c hf o r u n i t c o m m i t m e n t p r o b l e m[J].I n t e r n a t i o n a l J o u r n a l o f
E l e c t r i c a l P o w e r a n dE n e r g y S y s t e m s,2006,28(5):315-323.
[52]林锦,朱文兴.凸整数规划问题的混合蚁群算法[J].福州大学学
报:自然科学版,1999,27(6):5-9.
[53]S C H L T E RM,E G E AJ A,B A N G AJ.E x t e n d e da n t c o l o n y o p t i m i-
z a t i o nf o rn o n-c o n v e xm i x e d i n t e g e rn o n l i n e a rp r o g r a m m i n g[J].
C o m p u t e r sa n d O p e r a t i o n s R e s e a r c h,2009,36(7):2217-
2229.
[54]S H I H a n-x i a o.S o l u t i o n t o0/1k n a p s a c kp r o b l e m b a s e do ni m p r o v e d
a n t c o l o n ya l g o r i t h m[C]//P r o co f I E E EI n t e r n a t i o n a l C o n f e r e n c eo n
I n f o r m a t i o nA c q u i s i t i o n.2006:1062-1066.
[55]S E C K I N E RSU,K U R TM.A n t c o l o n y o p t i m i z a t i o n f o r t h e j o br o t a-
t i o n s c h e d u l i n g p r o b l e m[J].A p p l i e dM a t h e ma t i c sa n dC o m p u t a-t i o n,2008,201(1-2):149-160.
[56]S U I L u-s i,T A N GJ i a-f u,P A NZ h e n-d o n g,e t a l.A n t c o l o n y o p t i m i-
z a t i o na l g o r i t h mt o s o l v e s p l i t d e l i v e r yv e h i c l er o u t i n g p r o b l e m[C]//
P r o c o f C h i n e s e C o n t r o l a n dD e c i s i o nC o n f e r e n c e.2008:997-1001.
[57]Z H A N G T a o,T I A N W e n-x i n,Z H A N G Y u e-j i e,e t a l.R L C A C S:
a ni m p r o v e da n t c o l o n y a l g o r i t h m f o r V R P S D P[C]//P r o co f t h e6t h
I n t e r n a t i o n a lC o n f e r e n c e o n M a c h i n e L e a r n i n g a n d C y b e r n e t i c s.
2007:978-983.
[58]A D L E M A NL.M o l e c u l a r c o m p u t a t i o n o f s o l u t i o n t o c o m b i n a t o r i a l p r o b-
l e m s[J].S c i e n c e,1994,266(11):1021-1024.
[59]L I P T O NRJ.D N As o l u t i o n o f h a r dc o m p u t a t i o np r o b l e m s[J].S c i e-
n c e,1995,268(4):542-545.
[60]王雷,林亚平.D N A计算在整数规划问题中的应用[J].电子与
信息学报,2005,27(5):814-818.
[61]胡宇舟,王雷,顾学道.有界整数规划问题的D N A计算[J].计算
机应用,2008,28(Z1):18-23.
[62]Y I NZ h i-x i a n g,C U I J i a n-z h o n g,Y A N G J i n.As u r f a c e-b a s e dD N A
c o m p u t i n g f o r t h ep o s i t i v e i n t e g e r l i n e a r p r o g r a m m i n gp r o b l e m[C]//
P r o co f t h e3r dI n t e r n a t i o n a l C o n f e r e n c eo nI n t e l l i g e n t C o m p u t i n g.
H e i d e l b e r g:S p r i n g e r-V e r l a g,2007:1-9.[63]WA N GS h i-y i n g,Y A N GA i-m i n g.D N As o l u t i o n o f i n t e g e r l i n e a r p r o-
g r a m m i n g[J].A p p l i e dMa t h e m a t i c sa n dC o m p u t a t i o n,2005,
170(1):626-632.
[64]Y I NZ h i-x i a n g,C U I J i a n-z h o n g,Y A N GJ i n,e t a l.D N A c o m p u t i n g
m o d e l o f t h ei n t e g e r l i n e a r p r o g r a m m i n gp r o b l e m b a s e do nm o l e c u l a r
b e a
c o n[C]//P r o c o f I n t e r n a t i o n a l C o n f e r e n c eo nI n t e l l i g e n t C o m p u-
t i n g.B e r l i n:S p r i n g e r:238-247.
[65]Y E H CW,C H UCP,WUKR.M o l e c u l a r s o l u t i o n s t o t h e b i n a r y i n-
t e g e r p r o g r a m m i n g p r o b l e mb a s e do nD N Ac o m p u t a t i o n[J].B i o s y s-t e ms,2006,83(1):56-66.
[66]L I Wa n g-g e n,D I N GY o n g-s h e n g.Am i c r o f l u i d i c s y s t e m s-b a s e dD N A
a l g o r i t h mf o r s o l v i n gs p e c i a l0-1i n t e g e r p r o g r a m m i n gp r o
b l e m[J].
A p p l i e dM a t h e m a t i c sa n dC o m p u t a t i o n,2007,185(2):1160-
1170.
[67]D A R E H M I R A K I M,N E H I MH.M o l e c u l a r s o l u t i o nt o t h e0-1k n a p-
s a c k p r o b l e mb a s e do nD N A c o m p u t i n g[J].A p p l i e dM a t h e m a t i c s
a n dC o mp u t a t i o n,2007,187(2):1033-1037.
[68]R E N Q i n g-s h e n g,Z E N GJ i n,Q I F e i-h u.E v o l u t i o n a r yp r o g r a m m i n g
f o r I P/M I Pp r o b l e m s w i t h l i n e a r c o n s t r a i n t s[J].J o u r n a l o f S y s t e m s
E n g i n e e r i n ga n dE l e c t r o n i c s,2000,11(3):59-64.
[69]O M R A NMGH,E N G E L B R E C H TAP.D i f f e r e n t i a l e v o l u t i o nf o r i n-
t e g e r p r o g r a m m i n gp r o b l e m[C]//P r o co f I E E EC o n g r e s so nE v o l u-t i o n a r yC o m p u t a t i o n.2007:2237-2242.
[70]李彤,王春峰,王文波,等.求解整数规划的一种仿生类全局优化
算法———模拟植物生长算法[J].系统工程理论与实践,2005,25
(1):76-85.
[71]李宏,焦永昌,张莉.一种求解混合整数规划的混合进化算法
[J].控制与决策,2008,23(10):1098-1102.
[72]王卫华,余林琛,成浩,等.基于相似性学习的整数规划问题演化
求解[J].武汉理工大学学报:信息与管理工程版,2004,26(2): 64-67.
[73]D E L L'A M I C OM,I O R I M,M A R T E L L OS.H e u r i s t i c a l g o r i t h m s a n d
s c a t t e r s e a r c h f o rt h ec a r d i n a l i t yc o n s t r a i n e dP C m a xp r o b l e m[J].
J o u r n a l o f H e u r i s t i c s,2004,10(2):169-204.
[74]G L O V E RF.P a r a m e t r i c t a b u-s e a r c hf o r m i x e di n t e g e r p r o g r a m s[J].
C o m p u t e r sa n d O p e r a t i o n sR e s e a r c h,2006,33(9):2449-
2494.
[75]P A NL i n-q i a n g,M A R T N-V I D EC.S o l v i n g m u l t i d i m e n s i o n a l0-1k n a-
p s a c k p r o b l e mb yPs y s t e m sw i t hi n p u t a n da c t i v em e m b r a n e s[J].
J o u r n a l o f P a r a l l e l a n dD i s t r i b u t e dC o m p u t i n g,2005,65(12): 1578-1584.
[76]X I A OG a n g,L I S h o u-z h i,WA N GX u a n-h o n g,e t a l.As o l u t i o nt o
u n i t c o m m i t m e n t p r o b l e m b yA C O a n dP S O h y b r i da l g o r i t h m[C]//
P r o co f t h e6t h Wo r l dC o n g r e s s o nI n t e l l i g e n t C o n t r o l a n d A u t o m a t i o n.
2006:7475-7479.
[77]G E NM,I D A K,K O U B U C H I R,e t a l.H y b r i d i z e dn e u r a l n e t w o r k
a n d g e n e t i c a l g o r i t h m sf o rs o l v i n gn o n l i n e a ri n t e g e rp r o g r a m m i n g
[C]//P r o co f I n t e r n a t i o n a l C o n f e r e n c eo nK n o w l e d g e-b a s e dI n t e l l i-
g e n t E l e c t r o n i cS y s t e m s.B e r l i n:S p r i n g e r,1998:272-277.
[78]WA N G X i u-h o n g,Q I A O Q i n g-l i,WA N G Z h e n-g o u.A q u i c k l y
s e a r c h i n g a l g o r i t h mf o r“0-1”o p t i m i z a t i o n p r o b l e m s b a s e do n c h a o t i c n e u r a l n e t w o r k[C]//P r o c o f t h e7t h I n t e r n a t i o n a l C o n f e r e n c e o nS i g-n a l P r o c e s s i n g.P i s c a t a w a y:I E E EP r e s s,2004:1517-1520.
·
412
·计算机应用研究 第27卷
人工智能算法综述 人工智能算法大概包括五大搜索技术，包括一些早期的搜索技术或用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理，如遗传算法和模拟退火算法等。 1、盲目搜索 盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。包括图搜索策略，宽度优先搜索和深度优先搜素。 1、图搜索（GRAPH SERCH）策略是一种在图中寻找路径的方法。在有关图的表示方法中，节点对应于状态，而连线对应于操作符。 2、如果搜素是以接近其实节点的程度依次扩展节点的，那么这种搜素就叫做宽度优先搜素（breadth-first search 。 3、深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。 二、启发式搜索 盲目搜索的不足之处是效率低，耗费过多的时间和空间。启发信息是进行搜索技术所需要的一些有关具体问题的特性的信息。利用启发信息的搜索方法叫做启发式搜索方法。 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 3、博弈树搜索 诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的"二人零和、全信息、非偶然"博弈，其特征如下： (1 对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局。 (2 在对垒过程中，任何一方都了解当前的格局及过去的历史。
0-1背包动态规划解决问题 一、问题描述： 有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？ 二、总体思路： 根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。 原理： 动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。 过程： a) 把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第i个物品选或不选），V i表示第i个物品的价值，W i表示第i个物品的体积（重量）； b) 建立模型，即求max(V1X1+V2X2+…+VnXn)； c) 约束条件，W1X1+W2X2+…+WnXn
文章编号 2 2 2 一种快速神经网络路径规划算法α 禹建丽? ∏ √ 孙增圻成久洋之 洛阳工学院应用数学系日本冈山理科大学工学部电子工学科 2 清华大学计算机系国家智能技术与系统重点实验室日本冈山理科大学工学部信息工学科 2 摘要本文研究已知障碍物形状和位置环境下的全局路径规划问题给出了一个路径规划算法其能量函数 利用神经网络结构定义根据路径点位于障碍物内外的不同位置选取不同的动态运动方程并针对障碍物的形状设 定各条边的模拟退火初始温度仿真研究表明本文提出的算法计算简单收敛速度快能够避免某些局部极值情 况规划的无碰路径达到了最短无碰路径 关键词全局路径规划能量函数神经网络模拟退火 中图分类号 ×°文献标识码 ΦΑΣΤΑΛΓΟΡΙΤΗΜΦΟΡΠΑΤΗΠΛΑΝΝΙΝΓ ΒΑΣΕΔΟΝΝΕΥΡΑΛΝΕΤ? ΟΡΚ ≠ 2 ? ? ≥ 2 ≥ ∏ ΔεπαρτμεντοφΜατηεματιχσ ΛυοψανγΙνστιτυτεοφΤεχηνολογψ Λυοψανγ
ΔεπαρτμεντοφΕλεχτρονιχΕνγινεερινγ ΦαχυλτψοφΕνγινεερινγ ΟκαψαμαΥνι?ερσιτψοφΣχιενχε 2 Ριδαι2χηο 2 ?απαν ΔεπαρτμεντοφΧομπυτερΣχιενχε Τεχηνολογψ ΣτατεΚεψΛαβοφΙντελλιγεντΤεχηνολογψ Σψστεμσ ΤσινγηυαΥνι?ερσιτψ Βει?ινγ ΔεπαρτμεντοφΙνφορματιον ΧομπυτερΕνγινεερινγ ΦαχυλτψοφΕνγινεερινγ ΟκαψαμαΥνι?ερσιτψοφΣχιενχε 2 Ριδαι2χηο 2 ?απαν Αβστραχτ ∏ √ √ √ × ∏ ∏ ∏ ∏ ∏ ∏ 2 ∏ √ × ∏ ∏ ∏ ∏ √ ∏ Κεψωορδσ ∏ ∏ ∏ 1引言Ιντροδυχτιον 机器人路径规划问题可以分为两种一种是基于环境先验完全信息的全局路径规划≈ 另一种是基于传感器信息的局部路径规划≈ ?后者环境是未知或者部分未知的全局路径规划已提出的典型方法有可视图法 ! 图搜索法≈ ! 人工势场法等可视图法的优点是可以求得最短路径但缺乏灵活性并且存在组合爆炸问题图搜索法比较灵活机器人的起始点和目标点的改变不会造成连通图的重新构造但不是任何时候都可以获得最短路径可视图法和图搜索法适用于多边形障碍物的避障路径规划问题但不适用解决圆形障碍物的避障路径规划问题人工势场法的基本思想是通过寻找路径点的能量函数的极小值点而使路径避开障碍物但存在局部极小值问题且不适于寻求最短路径≈ 文献≈ 给出的神经网络路径规划算法我们称为原算法引入网络结构和模拟退火等方法计算简单能避免某些局部极值情况且具有并行性及易于从二维空间推广到三维空间等优点对人工势场法给予了较大的改进但在此算法中由于路径点的总能量函数是由碰撞罚函数和距离函数两部分的和构成的而路径点 第卷第期年月机器人ΡΟΒΟΤ? α收稿日期
现代智能优化算法课程群智能优化算法综述 学生姓名： 学号： 班级： 2014年6月22日
摘要 工程技术与科学研究中的最优化求解问题十分普遍，在求解过程中，人们创造与发现了许多优秀实用的算法。群智能算法是一种新兴的演化计算技术，已成为越来越多研究者的关注焦点，智能优化算法具有很多优点,如操作简单、收敛速度快、全局收敛性好等。群智能优化是智能优化的一个重要分支，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的联系。群智能优化通过模拟社会性昆虫的各种群体行为，利用群体中个体之间的信息交互和合作实现寻优。本文综述群智能优化算法的原理、主要群智能算法介绍、应用研究及其发展前景。 关键词：群智能；最优化；算法
目录 摘要 (1) 1 概述 (3) 2 定义及原理 (3) 2.1 定义 (3) 2.2 群集智能算法原理 (4) 3 主要群智能算法 (4) 3.1 蚁群算法 (4) 3.2 粒子群算法 (5) 3.3 其他算法 (6) 4 应用研究 (7) 5 发展前景 (7) 6 总结 (8) 参考文献 (9)
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 为约束函数；Ω为设计变量的 可行域。
规划模型求解 指导老师： 组员： 组员分工 实际的内容： 1·简要介绍线性规划的历史 线性规划是运筹学中最基本、应用最广泛的分支。规划模型是一类有着广泛应用的确定性的系统优化模型，1939年，苏联数学家康托洛维奇出版《生产组织和计划中的数学方法》一书. 1947年，美国数学家丹兹格提出了线性规划问题的单纯形求解方法. 1951年，美国经济学家库普曼斯（J.C.Koopmans,1910—1985）出版《生产与配置的活动分析》一书. 1950～1956年，线性规划的对偶理论出现. 1960年，丹兹格与沃尔夫（P.Wolfe）建立大规模线性规划问题的分解算法. 1975年，康托洛维奇与库普曼斯因“最优资源配置理论的贡献”荣获诺贝尔经济学奖. 1978年，苏联数学家哈奇扬（L.G.Khachian）提出求解线性规划问题的多项式时间算法（内点算法），具有重要理论意义. 1984年，在美国贝尔实验室工作的印度裔数学家卡玛卡（N.Karmarkar）提出可以有效求解实际线性规划问题的多项式时间算法——Karmarkar算法.
线性规划的基本点就是在满足一定约束条件下，使预定的目标达到最优. 现在线性规划已不仅仅是一种数学理论和方法，而且成了现代化管理的重要手段，是帮助管理者与经营者做出科学决策的一个有效的数学技术. 历史表明，重要数学概念对数学发展的作用是不可估量的，函数概念对数学发展的影响，可以说是贯穿古今、旷日持久、作用非凡，回顾函数概念的历史发展，看一看 函数概念不断被精炼、深化、丰富的历史过程，是一件十分有益的事情，它不仅有助于我们提高对函数概念来龙去脉认识的清晰度，而且更能帮助我们领悟数学概念 对数学发展，数学学习的巨大作用。 2·线性规划的原理：线性规划是合理利用、调配资源 的一种应用数学方法。它的基本思路就是在满足一定的约束条件下，使预定的目标达到最优。它的研究内容可归纳为两个方面：一是系统的任务已定，如何合理筹划，精细安排，用最少的资源(人力、物力和财力)去实现这个任务；二是资源的数量已定，如何合理利用、调配，使任务完成的最多。前者是求极小，后者是求极大。线性规划是在满足企业内、外部的条件下，实现管理目标和极值(极小值和极大值)问题，就是要以尽少的资源输入来实现更多的社会需要的产品的产出。因此，线性规划是辅助企业“转轨”、“变型”的十分有利的工具，它在辅助企业经营决策、计划优化等方面具有重要的作用。其一般形式为： n n n n n n b x a x a x a b x a x a x a x c x c x c x f =+++=+++→+++= 2 2222121112121112211min )(
遗传算法与机器人路径规划 摘要：机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。 关键词：路径规划；移动机器人；避障；遗传算法 Genetic Algorithm and Robot Path Planning Abstract: Robot path planning research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers（e.g time optimal），and find a best movement path in work space. Robot path planning can be modeled that in the course of robots able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual. Key words: Path planning,mobile robot, avoid the obstacles, genetic algorithm 1路径规划 1.1机器人路径规划分类 （1）根据机器人对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划基本上可分为以下几类： 1，已知环境下的对静态障碍物的路径规划； 2，未知环境下的对静态障碍物的路径规划； 3，已知环境下对动态障碍物的路径规划； 4，未知环境下的对动态障碍物的路径规划。 （2）也可根据对环境信息掌握的程度不同将移动机器人路径规划分为两种类型： 1，基于环境先验完全信息的全局路径规划； 2，基于传感器信息的局部路径规划。 （第二种中的环境是未知或部分未知的，即障碍物的尺寸、形状和位置等信息必须通过传感器获取。） 1.2路径规划步骤 无论机器人路径规划属于哪种类别，采用何种规划算法，基本上都要遵循以下步骤： 1, 建立环境模型，即将现实世界的问题进行抽象后建立相关的模型； 2, 路径搜索方法，即寻找合乎条件的路径的算法。 1.3路径规划方法
物流配送最优路径规划
关于交通运输企业物流配送最优路径规划的 研究现状、存在问题及前景展望 摘要：本文综述了在交通运输企业的物流配送领域最优路径规划的主要研究成果、研究存在问题及研究方向。主要研究成果包括运用各种数学模型和算法在运输网中选取最短或最优路径；从而达到路径、时间最优和费用最优；以及物流配送网络优化、车辆系统化统一调度的发展。今后研究的主要方向包括绿色物流，运输系统及时性和准确性研究等。 关键词：物流配送；最优路径；路径规划 Overview of scheme on Shortest Logistics Distribution Route in Transportation Industry Student: Wan Lu Tutor: Chen Qingchun Abstract: This paper reviewed of the optimal path planning about the main research results, problems and direction in the field of transportation enterprise logistics distribution. Main research results include using various mathematical model and algorithm selection or optimal shortest path in the network. So we can achieve the optimal path, the shortest time and minimum cost. At the same time, logistics distribution network optimization, the vehicle systematic development of unified scheduling are the research issues.The main direction of future research include green logistics, transportation system accurately and timely research and so on. Key words: Logics Distribution; Optimal Path; Path Planning 引言 物流业在我国的新兴经济产业中占据了重要了地位，称为促进经济快速增长的“加速器”。而物流配送作为物流系统的重要环节，影响着物流的整个运作过程以及运输企业的发展趋势和前景。采用科学、合理的方法来进行物流配送路径的优化，是物流配送领域的重要研究内容。近年，国内外均有大量的企业机构、学者对物流配送中最优路径选择的问题，进行了大量深入的研究，从早期车辆路径问题研究，到根据约束模型及条件不断变化的车辆最优路径研究，以及随着计算机学科的发展而推出的针对物流配送路径最优化的模型和算法等方面，都取得丰硕的学术成果。但是对于绿色物流配送的研究仍然不足。鉴于物流配送最优路径研究的重大理论意义和实践价值，为对我国物流配送的效率水平有一个系统的理解和把握，有必要对现有成果进行统计和归纳。本文尝试对我国运输企业物流配送最优路径规划进行探讨，以期为今后做更深人和全面的研究提供一定的线索和分析思路。 1 国内外研究现状 1.1 国内研究现状 1.1.1 主要研究的问题
智能算法在电力系统无功优化中的应用综 述 Revised on November 25, 2020
智能算法在电力系统的无功优化中的应用 1 引言 电力系统的无功优化问题主要包括对电力系统中的电力无功补偿装置投入的地点、容量的确认，以及发电机端电压的配合和载调压变压器分接头的调节等，因此，电力系统中的无功优化问题就是一个带有大量约束条件的非线性规划问题。由于电力系统在社会发展过程中的重要作用，长期以来很多专家和学者都对电力系统中的无功优化问题进行了大量的研究，并且采用很多方法来对电力系统无功优化问题进行求解。自从二十世纪六十年代，J. Carpentier 提出了电力系统最优潮流数学模型之后，对电力系统无功优化问题的研究更是得到了长足的发展。目前，随着各种数学优化方法和信息技术的发展，电力系统的无功优化问题的研究也进入了一个新的领域[1]。目前电力系统无功优化问题的算法主要有经典数学优化方法和人工智能优化方法两种。 绝大多数的学者研究把连接电源点和负荷点或两个负荷点之间的馈线段作为研究对象，把这条线路作为最小的接线单元，用近年来出现的智能算法进行寻优，如遗传算法、免疫算法、禁忌搜索算法、粒子群算法、蚁群算法、模拟退火算法等。 2 无功优化的数学模型 无功优化问题在数学上可以描述为:在给定系统网络结构和参数以及系统负荷的条件下，确定系统的控制变量，满足各种等式、不等式约束，使得描述系统运行效益的某个给定目标函数取极值。其数学模型[2]表示为: min (,) ..(,)0(,)0f u x s t g u x h u x ??=??≤? （） 式中，f 表示目标函数，u 是控制变量，包括发电机的机端电压、有载调压变压器的变比、无功补偿装置的容量;x 是状态变量，通常包括各节点电压和发电机的无功出力。无功优化模型有很多种类，大体有以下几种模型: 1)以系统的有功网损最小为优化的目标函数，在减少系统有功功率损耗的同时改善电压质量: 2(,)(,)min min ()min (2cos )l l ij ji ij i j i j ij i j n i j n f P P G U U U U θ∈∈=+=+-∑∑ 其中:l n 表示所有支路的集合，n 表示系统的总节点数，i U ，j U 分别为节 点i ，j 的电压，ij θ 是节点i ，j 的相角差。 2)以系统的总无功补偿量最小为目标函数，这样能使总的补偿费用达到最小
移动机器人路径规划方法 1.1路径规划方法 路径规划技术是机器人研究领域中的一个重要课题，是机器人导航中最重要的任务之一,国外文献常将其称为Path Planning,Find-PathProblem,Collision-Free,ObstacleAvoidance, MotionPlanning,etc.所谓机器人的最优路径规划问题，就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。 路径规划主要涉及的问题包括：利用获得的移动机器人环境信息建立较为合理的模型，再用某种算法寻找一条从起始状态到目标状态的最优或近似最优的无碰撞路径；能够处理环境模型中的不确定因素和路径跟踪中出现的误差，使外界物体对机器人的影响降到最小；如何利用已知的所有信息来引导机器人的动作，从而得到相对更优的行为决策。这其中的根本问题是世界模型的表达和搜寻策略。障碍物在环境中的不同分布情况当然直接影响到规划的路径，而目标位置的确定则是由更高一级的任务分解模块提供的[8]。 根据机器人对环境信息掌握的程度和障碍物运动状态的不同，移动机器人的路径规划基本上可分为以下四类:①已知环境下的对静态障碍物的路径规划;②未知环境下的对静态障碍物的路径规划;③已
知环境下对动态障碍物的路径规划;④未知环境下对动态障碍物的路径规划。因此根据机器人对环境信息掌握的程度不同，可将机器人的路径规划问题可分为二大类即：基于环境先验信息的全局路径规划问题和基于不确定环境的局部路径规划问题。目前，路径规划研究方法大概可分为两大类即：传统方法和智能方法。 1.2传统路径规划方法 传统的路径规划方法主要包括：可视图法(V-Graph)、自由空间法(Free Space Approach)、人工势场法（Artificial Potential Field）和栅格法(Grids)等。 ⑴可视图法（V-Graph） 可视图法是Nilsson1968年在文献[9]中首次提出。可视图法将移动机器人视为一点，将机器人起始点、目标点和多边形障碍物的各定点组合连接，保证这些直线不与障碍物相交，这就构成了一张无向图称为可视图。由于任意两条直线的定点都是可见的，从起点沿着这些直线到达目标点的路线都是无碰撞的。于是，搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。 这种方法的优点是可以得到最优路径，但缺陷是环境特征的提取比较困难，缺乏灵活性，一般需要机器人停止在障碍物前搜集传感器数据，并且传感器的精度对其影响也较大，尤其在复杂的非规整环境下更加难以实现安全无碰撞的路径规划。 ⑵自由空间法（Free Space Approach）
智能优化算法的统一框架 指导老师：叶晓东教授 姓名：李进阳 学号：2 班级：电磁场与微波技术5班 2011年6月20日
目录 1 概述 (3) 2群体智能优化算法.................................. 错误!未定义书签。 人工鱼群算法 (4) 蚁群算法 (5) 混合蛙跳算法 (9) 3神经网络算法 (10) 神经网络知识点概述 (10) 神经网络在计算机中的应用 (11) 4模拟退火算法 (15) 5遗传算法.......................................... 错误!未定义书签。 遗传算法知识简介 (17) 遗传算法现状 (18) 遗传算法定义 (19) 遗传算法特点和应用 (20) 遗传算法的一般算法 (21) 遗传算法的基本框架 (26) 6总结 (28) 7感谢 (29)
1概述 近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑。众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。智能优化算法就是在这种背景下产生并经实践证明特别有效的算法。 2群体智能优化算法 自然界中群体生活的昆虫、动物,大都表现出惊人的完成复杂行为的能力。人们从中得到启发,参考群体生活的昆虫、动物的社会行为,提出了模拟生物系统中群体生活习性的群体智能优化算法。在群体智能优化算法中每一个个体都是具有经验和智慧的智能体 (Agent) ,个体之间存在互相作用机制,通过相互作用形成强大的群体智慧来解决复杂的问题。自 20世纪 90年代模拟蚂蚁行为的蚁群算法(ACO)提出以来,又产生了模拟鸟类行为的微粒群算法 ( PSO)、模拟鱼类生存习性的人工鱼群算法、模拟青蛙觅食的混合蛙跳算法 ( SFLA)等。这些群体智能优化算法的出现,使原来一些复杂的、难于用常规的优化算法进行处理的问题可以得到解决,大大增强了人们解决和处理优化问题的能力,这些算法不断地用于解决工程实际中的问题,使得人们投入更大的精力对其理论和实际应用进行研究。群体智能优化算法本质上是一种概率搜索,它不需要问题的梯度信息具有以下不同于传统优化算法的特点: ①群体中相互作用的个体是分布式的,不存在直接的中心控制,不会因为个别个体出现故障而影响群体对问题的求解,具有较强的鲁棒性; ②每个个体只能感知局部信息,个体的能力或遵循规则非常简单,所以群体智能的实现简单、方便; ③系统用于通信的开销较少,易于扩充; ④自
启发式优化算法综述 一、启发式算法简介 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），拟人拟物算法，量子算法等。
第25卷第7期V ol.25No.7 控制与决策 Control and Decision 2010年7月 Jul.2010移动机器人路径规划技术综述 文章编号:1001-0920(2010)07-0961-07 朱大奇,颜明重 (上海海事大学水下机器人与智能系统实验室，上海201306) 摘要:智能移动机器人路径规划问题一直是机器人研究的核心内容之一.将移动机器人路径规划方法概括为:基于模版匹配路径规划技术、基于人工势场路径规划技术、基于地图构建路径规划技术和基于人工智能的路径规划技术.分别对这几种方法进行总结与评价,最后展望了移动机器人路径规划的未来研究方向. 关键词:移动机器人；路径规划；人工势场；模板匹配；地图构建；神经网络；智能计算 中图分类号:TP18；TP273文献标识码:A Survey on technology of mobile robot path planning ZHU Da-qi,YAN Ming-zhong (Laboratory of Underwater Vehicles and Intelligent Systems，Shanghai Maritime University，Shanghai201306, China．Correspondent：ZHU Da-qi，E-mail：zdq367@https://www.doczj.com/doc/e02044056.html,) Abstract:The technology of intelligent mobile robot path planning is one of the most important robot research areas.In this paper the methods of path planning are classi?ed into four classes:Template based,arti?cial potential?eld based,map building based and arti?cial intelligent based approaches.First,the basic theories of the path planning methods are introduced brie?y.Then,the advantages and limitations of the methods are pointed out.Finally,the technology development trends of intelligent mobile robot path planning are given. Key words:Mobile robot；Path planning；Arti?cial potential?eld；Template approach；Map building；Neural network; Intelligent computation 1引言 所谓移动机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务.移动机器人路径规划主要解决3个问题:1)使机器人能从初始点运动到目标点;2)用一定的算法使机器人能绕开障碍物,并且经过某些必须经过的点完成相应的作业任务;3)在完成以上任务的前提下,尽量优化机器人运行轨迹.机器人路径规划技术是智能移动机器人研究的核心内容之一,它起始于20世纪70年代,迄今为止,己有大量的研究成果报道.部分学者从机器人对环境感知的角度,将移动机器人路径规划方法分为3种类型[1]:基于环境模型的规划方法、基于事例学习的规划方法和基于行为的路径规划方法;从机器人路径规划的目标范围看,又可分为全局路径规划和局部路径规划;从规划环境是否随时间变化方面看,还可分为静态路径规划和动态路径规划. 本文从移动机器人路径规划的具体算法与策略上,将移动机器人路径规划技术概括为以下4类:模版匹配路径规划技术、人工势场路径规划技术、地图构建路径规划技术和人工智能路径规划技术.分别对这几种方法进行总结与评价,展望了移动机器人路径规划的未来发展方向. 2模版匹配路径规划技术 模版匹配方法是将机器人当前状态与过去经历相比较,找到最接近的状态,修改这一状态下的路径,便可得到一条新的路径[2,3].即首先利用路径规划所用到的或已产生的信息建立一个模版库,库中的任一模版包含每一次规划的环境信息和路径信息,这些模版可通过特定的索引取得;随后将当前规划任务和环境信息与模版库中的模版进行匹配,以寻找出一 收稿日期:2009-08-30；修回日期:2009-11-18. 基金项目:国家自然科学基金项目(50775136)；高校博士点基金项目(20093121110001)；上海市教委科研创新项目(10ZZ97). 作者简介:朱大奇(1964?),男,安徽安庆人,教授,博士生导师,从事水下机器人可靠性与路径规划等研究；颜明重(1977?),男,福建泉州人,博士生,从事水下机器人路径规划的研究.
微电网国内外研究综述 微电网已成为一些发达国家解决电力系统众多问题的一个重要辅助手段，所以分布式发电是21世纪电力行业发展的重要方向。随着电网中分布式发电系统数量的日益增多，尤其是基于可再生能源的并网发电装置在分布式发电系统中应用的日益广泛，随着世界科技的不断进步，当今电网的负荷越来越大，随之而来的是问题不断的增多。解决当今电力系统中存在的诸多问题已经成为研究者们头等的问题。 长期以来，电力系统向大机组、大电网、高电压的方向发展。进入20世纪80 年代，各种分散布置的、小容量的发电技术又开始引起人们的关注，经过20 多年的发展，分布式发电已成为一股影响电力工业未来面貌的重要力量。 1)应对全球能源危机的需要。随着国际油价的不断飙升，能源安全问题日益突出，为了实现可持续发展，人们的目光转向了可再生能源，因此，风力发电、太阳能发电等备受关注，快速发展并开始规模化商业应用，而这些可再生能源的发电大都是小型的、星罗棋布的。 2)保护环境的需要。CO2排放引起的全球气候变暖问题，已引起各国政府的高度重视，并成为当今世界政治的核心议题之一。为保护环境，世界上工业发达国家纷纷立法，扶持可再生能源发电以及其他清洁发电技术(如热电联产微型燃气轮机)，有利地推动了DG的发展。 3)天然气发电技术的发展。对于天然气发电来说，机组容量并不明显影响机组的效率，并且天然气输送成本远远低于电力的传输，因此比较适合采用有小容量特点的DG。
4)免投资风险。由于难以准确地预测远期的电力需求增长情况，为规避风险，电力公司往往不愿意投资大型的发电厂以及长距离超高压输电线路。此外，高压线路走廊的选择也比较困难。这都促使电力公司选择一些投资小、见效快的DG项目来就地解决供电问题。 在国际上，DG 的发展方兴未艾。在美国，1978 年修改了《公共事业法》，以法律的形式要求各电力公司接受用户的小型能源系统，特别是热电机组并网;2000 年，热电联产装机容量已占总装机容量的7%，预计到2010 年将占其总装机容量的14%;2008年，风力发电装机容量达2500万kW;太阳能装机容量达87万kW。欧洲在世界上最早开始应用DG。目前，丹麦、芬兰、挪威等国的DG容量均已接近或超过其总发电装机容量的50%;欧洲DG应用规模最大的德国， 2008年末风电装机容量达到2300万kW，太阳能发电装机容量达 540万kW。我国应用的DG原来主要以小水电为主，风电、光伏发电等起步相对较晚。2003年以来，国家强力推进节能减排，颁布了《可再生能源法》并制定了一系列促进可再生能源利用与提高能效技术发展的政策。到2008年底，我国风力发电装机容量达到1200万kW，跃居世界第三位;光伏发电装机容量达到14万kW。 近年来，各国政府对能源安全与环境问题高度重视。美国、欧盟都提出2020年应用可再生能源占总能源消费的比例超过20%;我国也制定了2020年应用可再生能源占消费总能源的比例达15%的目标。目前，
MATLAB 实现基于蚁群算法的机器人路径规划 1、问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则（如最小能量消耗，最短行走路线，最短行走时间等），在其工作空间中找到一条从起 始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 2 算法理论 蚁群算法（Ant Colony Algorithm ，ACA ），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS ），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士给出改进模型（ACS ），文中改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos 给出了最大-最小蚂蚁系统（MAX-MINAS ），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图2-1 所示，AE 之间有两条路ABCDE 与ABHDE ，其中AB ，DE，HD，HB 的长度为1，BC，CD 长度为0.5，并且，假设路上信息素浓度为0，且各个蚂蚁行进速度相同，单位时间所走的长度为1，每个单位时间内在走过路径上留下的信息素的量也相同。当t=0 时，从A 点，E 点同时各有30 只蚂蚁从该点出发。当t=1，从A 点出发的蚂蚁走到B 点时，由于两条路BH 与BC 上的信息素浓度相同，所以蚂蚁以相同的概率选择BH 与BC ，这样就有15 只蚂蚁选择走BH，有15 只蚂蚁选择走BC 。同样的从E 点出发的蚂蚁走到D 点，分别有15 只蚂蚁选择DH 和DC。当t=2 时，选择BC 与DC 的蚂蚁分别走过了BCD 和DCB ，而选择BH 与DH 的蚂蚁都走到了H 点。所有的蚂蚁都在所走过的路上留下了相同浓度的信息素，那么路径BCD 上的信息素的浓度是路径BHD 上信息素浓度的两倍，这样若再次有蚂蚁选择走BC 和BH 时，或选择走DC 与DH 时，都会以较大的概率选择信息素浓度高的一边。这样的过程反复进行下去，最短的路径上走过的蚂蚁较多，留下的信息素也越多，蚁群这样就可以找到一条较短的路。这就是它们群体智能的体现。 蚁群算法就是模拟蚂蚁觅食过程中可以找到最短的路的行为过程设计的一种仿生算法。在用蚁群算法求解组合优化问题时，首先要将组合优化问题表达成与信息素相关的规范形式，然后各个蚂蚁独立地根据局部的信息素进行决策构造解，并根据解的优劣更新周围的信息素，这样的过程反复的进行即可求出组合优化问题的优化解。 归结蚁群算法有如下特点： （1）分布式计算：各个蚂蚁独立地构造解，当有蚂蚁个体构造的解较差时，并不会影响整体的求解结果。这使得算法具有较强的适应性； （2）自组织性：系统学中自组织性就是系统的组织指令是来自系统的内部。同样的蚁群算法中的各个蚂蚁的决策是根据系统内部信息素的分布进行的。这使得算法具有较强的鲁棒性； （3）正反馈机制与负反馈机制结合：若某部分空间上分布的信息素越多，那么在这个空间上走过的蚂蚁也就越多；走过的蚂蚁越多，在那个空间上留下的信息素也就越多，这就是存在的正反馈机制。但蚁群算法中解的构造是通过计算转移概率实现的，也就是说构造解的时候可以接受退化解，这限制了正反馈机制，