人工鱼群范文
人工鱼群范文（精选8篇）
人工鱼群 第1篇
(1) 觅食行为:鱼一般会呆在食物较多的地方。一般在水里游的鱼, 当它发现食物时, 会向其游去。
(2) 聚群行为:鱼在水中大多是群聚在一起, 这样是为了能够更好的在水中生存, 观察鱼群不难发现, 鱼群中每条鱼之间都保持有一定的距离, 而且它们会尽量保持方向一致, 而外围的鱼也都是不断像中心的位置靠近。
(3) 追尾行为:在鱼群中, 当一条鱼或者几条鱼发现食物时, 其它的鱼也会尾随其快速的游到食物分布较多的地方。
1. 人工鱼群算法原理
1.1 人工鱼群算法具的特点
(1) 收敛速度较快, 可以用来解决有实时性要求的问题;
(2) 针对一些精度要求不高的情况, 可以用来快速的得到一个可行解;
(3) 不需要问题的严格机理模型, 甚至不需要问题的精确描述, 这使得它的应用范围得以扩展。
1.2 人工鱼群算法常用终止条件
(1) 判断连续多次所得的均方差小于允许的误差。 (2) 判断一些区域的人工鱼群的数量达到某个比率。 (3) 连续多次所获取的值均不得超过已寻找的极值。 (4) 迭代次数到达设定的最大次数
1.3 人工鱼群算法的基本流程
人工鱼群算法演化到具体计算技术, 具体流程如下:
两个体之间的距离个体的当前位置, visual一只鱼的感知距离。@拥挤度因子。
(1) 觅食人工鱼当前位置为Xi, 在可见域内随机选择一个位置Xj (d (ij) <=visual) , 如xj优于xi向xj前进一步, 否则随机移动一步。如出现不满足约束则剪去。不变, else=随机 (0, 1) }。
(2) 聚群:xi可见域内共有nf1条鱼。形成集和KJi,
当Xik=X (center, k) 时, Xik=随机 (0, 1) ,
当Xik!=X (center, k) 时, 若:FCc/nf1<@FCi则:进行觅食。
(3) 追尾在visual范围内, 某一个体食物浓度最大则称为X m a x, 若:F C m a x>@F C i, 则向其移动:X (i+1, k) =当X (i, k) =X (max, k) 时, X (i, k) 不变, 当X (i, k) !=X (max, k) 时, X (i, k) =随机 (0, 1) 。
(4) 公告板在运算过程中, 用于记录下最优Fci
2. 人工鱼群算法在各领域的应用
(1) 电力系统规划中的应用。电力系统规划的重要组成部分是输电网规划, 其目的是根据规划期间的负荷增长及电源规划方案构建相应的最佳电网结构, 来满足经济可靠地输送电能的要求。目前, 人工智能算法的快速发展为解决输电网规划问题提供了新的方法。人工智能算法适于求解组合优化问题或者目标函数与一些约束条件不可微的优化问题。人工鱼群算法通过引入禁忌搜索 (Tabu) 和对人工鱼部分行为的改进, 使人工鱼在探寻过程中具有记忆能力, 对探索过的位置设为禁区, 从而避免重复搜索;同时记录禁区中的一些优良状态, 保证搜索的高效性和多样性, 进而通过人工鱼群算法解决输电网规划问题的速度和效率。
(2) 多级梯阶物流中转运输系统优化问题。在关于此问题的优化模型中, 需要同时考虑变量的约束条件和求解精度, 将所需要求解的空间离散化, 把变量空间转变为合适大小的网格, 每一级中转站的最优位置将在限定区域内的某些已知点上选取, 该问题向量维数很高, 用人工鱼群算法建立各级中转站与网格点关系矩阵和相邻两级中转站间的关系矩阵来消除约束条件和压缩变量数, 通过对算法的一些改进使其更适合于该问题的优化, 应用结果表明该算法在处理多级梯阶物流中转运输系统优化问题效果显著。
3. 结论
通过人工鱼群算法的不断改进, 该算法已经适用于许多不同领域, 其他的典型应用包括, 在参数估计、边坡稳定、非线形方程组求解等方面。
摘要：人工鱼群算法是一种基于行为的人工智能思想, 通过鱼在水里的行为方式模拟构建了一种鱼群模式, 用来解决寻优问题, 从而产生了一种新型的智能算法。本文首先通过介绍人工鱼群算法的原理来阐述其在各领域的运用。
关键词：人工鱼群算法,寻优问题,智能算法
参考文献
[1]冈萨雷斯, 数字图像处理, 北京:电子工业出版社, 2003.
[2]李晓磊.一种新型的智能优化方法-人工鱼群算法[D].杭州:浙江大学, 2003.
[3]王西邓.人工鱼群算法的改进研究[D].西安:西安建筑科技大学, 2007.
寒冰下的鱼群 第2篇
一方的声音认为资本正在进入寒冬，中国互联网的三座大山——百度、阿里、腾讯都相继合上了招聘大门。烧钱从不手软的BAT，眼下却纷纷偃旗息鼓，停止招人，大有要收缩业务准备过冬的意思。
另一方则认为，资本泡沫正在被“吹大”。到9月末，广义货币M2余额135.98万亿元，同比增长13.1%，仍高于年初设定的12%的增速目标，整体货币的投放环境仍然是宽松的。
似乎没有越辩越明的真理，只有越发看不清的乱象，我们最终掉落到了观点的深井之中，被各种意见绑架。
如果我们腾空俯瞰，或者俯身细观，资本为何如此纠结，倒也能理清一二。
从宏观来看，日前央行以MLF方式向11家央行注入1100亿元的流动性资金；中国版QE也在朋友圈里刷屏，这可能会释放高达几万亿元流动性资金；在10月23日霜降前选择“双降”，当二十四节气进入冬季时放出利好。宽松的货币政策会将相当一部分热钱引向投资者，资本并不会放弃寻找好项目。尽管经济放缓，投资者会变得谨慎；但资金增加，投资机会反倒增多。在我们面前的，仍是少见的货币宽松大牛市，泡沫依然存在。
而那些细琐的“寒冬”里的“哀嚎”，只要侧耳倾听，就会发现声音要么来自初创企业，要么来自互联网企业。
前阵子的创业浪潮太热，但凡有点创意，再穿上“互联网+”的马甲，就能轻轻松松圈到钱。而真正能在2015年上市的，称得上创业有成的企业，十根手指一遍就能数完。赔了钱的投资者自然要开始捂紧钱袋，谨慎投资。初创企业圈和互联网企业们喊缺钱，也是再正常不过了。
这是一个行业的因果，并非是全行业的困境。
所谓的“创业资本寒冬”，不过是投资人对“创业潮”的一次集体纠偏，对喧嚣的初创企业一次优胜劣汰。大众创业、万众创新仍是未来5年的主旋律，但是如果还是以前那种玩法——广播种，炒“互联网+”概念，把初创公司市值抬高，击鼓传花给下一位接棒者——愿意接盘的傻子们会越来越少，这种玩法显然是玩不下去了。当当网、拉手网、1号店网、凡客网、人人网等，他们都有过傲人的每周用户增长率（当然，很多是因为烧钱补贴的原因），市值越做越大，但是模式并不成功，不知搭进了多少天使投资人。
令人目眩的泡沫过后，主流投资机构在未来的投资节奏会慢下来，寻找真正有价值的企业。对真正好的创业项目并没有太大影响，反而因为资金更加专注，使得真正创新的项目得到更加充分的资源扶持。
红杉资本的沈南鹏有个观点很玩味：“红杉的世界里没有‘冬天’，优秀的企业常常藏在所谓的冬天。”
使用混合人工鱼群算法求解装箱问题 第3篇
关键词：装箱问题,CF近似算法,人工鱼群算法
0 引 言
装箱问题在现实生活中具有广泛的应用,如多处理器的任务调度、内存分配、资源管理、运输计划等,特别在现代的物流中,很多问题都可以抽象化为装箱问题或装箱问题的变形,如车辆如何装车,才能充分使用车辆;资金(资源)如何分配才能得到最大的回报等等。因此,找到一个高效快速的算法具有重要的现实意义。从计算复杂性理论来讲装箱问题属于NP完全问题,由于目前NP完全问题不存在有效时间内求得精确解的算法,目前的求解方法主要是一些近似算法,如近似算法NF(Next Fit)、近似算法FF(First Fit)、近似算法FFD(First Fit Decreasing)、近似算法BF(Best Fit)、近似算法BFD(Best Fit Decreasing)[1]及CF近似算法[2]等。近似算法的求解结果与物品的体积等数据有较大的关系,甚至在某些极端的情况下,其求解结果很不理想。本文提出了类CF算法与人工鱼群算法相结合的混合算法对装箱问题进行了求解。
1 问题的描述
装箱问题的一般描述为:给定n个物品的序列Ln=(x1,x2,,xn),物品xi(1in)的大小s(xi)∈(0,1], 要求将这些物品装入单位容量的箱子B1,B2,,Bm(mn)中, 使得每个箱子中的物品大小之和不超过1,并使所用的箱子数目M最小。装箱问题的数学表示如下:
s.t
Bi=0或1 i∈N
αij=0或1 i∈N j∈N′
其中Bi=1表示箱子i被放入物品,反之则表示箱子i空着;αij=1表示物品j放入箱子i,反之表示物品j未放入箱子i;s(xj)为第j个物品的体积。
2 人工鱼群算法
人工鱼群算法AFSA(Artificial Fish-Swarm Algorithm)是李晓磊等[3,4]在前人对群体智能行为研究的基础上提出的一种新型仿生优化算法。在一片水域中,鱼往往能自行或尾随其它鱼,找到营养物质多的地方,因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方。人工鱼群算法根据这一特点,通过构造人工鱼来模仿鱼群的觅食、聚群、追尾及随机行为,从而实现寻优。以下是鱼类的几种典型行为:
1) 觅食行为
一般情况下鱼在水中随机、自由地游动,当发现附近有食物时,则会向着食物逐渐增多的方向游去。
2) 聚群行为
为了保证生存和躲避危害,鱼会自然地聚集成群。鱼聚群时所遵守的规则有三条:① 分隔规则,尽量避免与临近伙伴过于拥挤;② 对准规则,尽量与临近伙伴的平均方向一致;③ 内聚规则,尽量朝临近伙伴的中心移动。
3) 追尾行为
当某条鱼发现食物时,其他鱼会尾随其临近的伙伴快速到达食物点。
4) 随机行为
当闲暇无事时,鱼在水中随机、自由地游动寻找食物。
3 算法的设计
设搜索空间的维数为n,鱼群的规模为N。每条人工鱼可表示为一个n维的向量Xi=(xi1,xi2,,xin)(i=1,2,,N);适值函数Y=f(X)表示人工鱼当前状态的食物浓度;di,j=d(Xi,Xj)(i,j=1,2,,N)表示人工鱼Xi与人工鱼Xj之间的距离;δ表示拥挤度因子;TryNumber表示人工鱼每次移动的最大试探次数;Visual表示人工鱼的视野范围。
3.1 初始种群的产生
本文采用随机的方式产生鱼群的初始状态,设要装箱的物品个数为n,则一条人工鱼的初始状态为以下随机序列(x1,x2,,xn),其中xi∈{1,2,,n},i=1,2,,n,∀i≠j,xi≠xj。如有8个物品要装箱,可能的人工鱼初始状态有(3,5,7,2,6,8,1,4)、(3,4,7,1,8,6,2,1)等。用这种编码没有把箱子编入染色体中,染色体的结构仅和物品有关[5]。
3.2 适值计算
适值函数的作用是将人工鱼的状态X=(x1,x2,,xn)转换成一种装箱方案并返回所需的箱子数量m,表示为m=f(X)。本文采用一种类CF算法来实现这种转换,具体描述如下:
首先把x1放入箱子B1中,然后从最右端开始,依次把物件xn,xn-1,放入B1,直到下一个物件不能再放入箱子为止,开启新的箱子B2;设在第i步循环时,打开第i个箱子,此时把物件xi放入Bi中,再从最右端开始从右往左把物件依次放入Bi中,假设第i-1个箱子Bi-1中最后一个放入的物件为xk,则在第i步循环时最右端的物件为xk-1,那么当s(xi)+s(xk-1)++s(xl)1且s(xi)+s(xk-1)++s(xl)+s(xl-1)>1时,把xk-1, xk-2,,xl放入Bi 中,开启新的箱子Bi+1。直到把物件x1,x2,,xn 放入m个箱子;最后输出m[2]。
例如有5个物品分别重0.1、0.2、0.3、0.4、0.5,一条人工鱼的状态为(1、5、2、4、3),根据类CF算法可行装箱方案为:B1(0.1、0.3、0.4、0.2)、B2(0.5),m=2。
3.3 觅 食
设人工鱼当前状态为Xi,在其视野范围内随机选择一个状态Xj,如果Yi<Yj , 则向该方向前进一步;反之,再重新随机选择状态Xj,判断是否满足前进条件;试探TryNumber次后,如果仍不满足前进条件,则执行其他行为(如随机移动行为)。
3.4 追 尾
设人工鱼当前状态为Xi,探索其邻域内状态最优的邻居XMAX,如果Yi<YMAX,并且XMAX的邻域内伙伴的数目nf满足nf/N<δ,(0<δ<1) ,表明XMAX的附近有较多的食物并且不太拥挤,则向XMAX的位置前进一步;否则执行觅食行为。
3.5 聚 群
设人工鱼当前状态为Xi,探索其邻域的伙伴数目nf,如果nf/N<δ,(0<δ<1),则表明伙伴中心有较多的食物并且不太拥挤,如果此时Yi<YC,则人工鱼向中心位置XC 前进一步;否则执行觅食行为。
3.6 拥挤度因子δ
拥挤度因子用来限制人工鱼群聚集的规模,在较优状态的领域内希望聚集较多的人工鱼,而次优状态的领域内希望聚集较少的人工鱼或不聚集人工鱼。本文的选取规则如下:
δ=αnmax
式中α(0<α<1)为极值接近水平,nmax为期望在该邻域内聚集的最大人工鱼数目。例如,如果希望在接近极值90%水平的领域内不会超过10个人工鱼聚集,那么取δ=0.910=9。
4 算法描述
Step1 初始化;
Step2 计算适值;
Step3 对每条人工鱼i(i=1,2,,N);
Step3.1 追尾,判断追尾后的状态是否好于原状态,若是,则更新当前状态及适值,并转Step4,否则转Step3.2;
Step3.2 聚群,判断聚群后的状态是否好于原状态,若是,则更新当前状态及适值,并转Step4,否则转Step3.3;
Step3.3 觅食,判断觅食后的状态是否好于原状态,若是,则更新当前状态及适值,并转Step4,否则转Step3.4;
Step3.4 随机移动,更新当前状态及适值,并转Step4;
Step4 更新当前最好值;
Step5 更新鱼群距离di,j(i,j=1,2,,N);
Step6 若已到最大进化代数,退出,否则,转Step3。
5 实验和结果
设人工鱼X=(x1,x2,,xn),Y=(y1,y2,,yn),则X和Y之间的距离表示如下:
其中:
k-距离邻域可以表示为:
N(X,k)={X′|d(X′,X)<k,X′∈D}
人工鱼X1,X2,,XN的中心表示如下:
其中Most操作符表示取其中多数共有或最相近的值。
为了更好地测试本文算法的有效性,笔者将本文算法与遗传算法用相同的算例及测试平台进行了一组对比实验。使用算例为:
xi=((i-1)mod5+1)/10 i=1,2,,n
运算过程中取鱼群算法的Visual=n/2,δ=0.618,TryNumber=100,种群规模为25,最大迭代次数为100。遗传算法取交叉率为0.6,变异率为0.3,种群规模为100,最大迭代次数为1000。运行平台为WindowsXP/VC++6.0/Intel Celeron® 2.4G/512M DDR。每个算例使用两种算法各连续计算5次,所得结果如表1所示。
从表1的实验结果可以看出,对大部份算例而言,AFSA在计算时间及计算精度方面均要优于GA;且当物品规模增加时,所需计算时间并不会大幅度增长。
6 结 论
本文分析了装箱问题,并针对装箱问题不定长解决方案的特点,提出使用类CF与人工鱼群混合算法求解该问题。与遗传算法的对比实验表明,本文提出的混合算法在计算速度及精度方面均要优于GA,具有较好的应用前景。
参考文献
[1]汤岩.遗传算法在装箱问题中的应用[D].大连海事大学,2005.
[2]孙春玲,等.装箱问题的一种新的近似算法[J].云南大学学报:自然科学版,2004,26(5):392-396.
[3]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002(11):32-38.
[4]李晓磊,路飞,田国会,等.组合优化问题的人工鱼群算法应用[J].山东大学学报,2004,34(5):64-67.
基于人工鱼群算法的PSS参数优化 第4篇
关键词：电力系统分析综合程序,小干扰线性化平台,电力系统稳定器,人工鱼群算法,优化
电力系统稳定器(PSS)是抑制电力系统低频振荡的最有效、最经济的方法。从数学上看PSS的参数优化[1,2,3,4,5,6,7,8,9,10,11,12]是一个有约束条件、多峰值的非线性优化问题,传统的优化算法难以解决。本文以电力系统分析综合程序PSASP的小干扰线性化平台作为参数优化的数据基础,以新英格兰系统为例使用人工鱼群算法[13,14,15]进行了参数寻优。优化结果表明了该算法对于PSS参数优化的有效性。
1 小干扰线性化数据平台
PSASP是一套功能强大、使用方便的电力系统分析程序。基于电网基础数据库、固定模型库以及用户自定义模型库的支持,PSASP可进行电力系统(输电、供电和配电系统)的各种计算分析。
PSASP小干扰稳定计算程序不仅提供了多种特征值计算和小干扰分析方法,还为用户提供了小干扰线性化平台。小干扰线性化平台提供了友好的应用分析环境,除各种分析计算外,还配有固定格式报表、Excel报表和各种形式的曲线等分析手段。其平台数据开放友好,对用户透明,用户可直接编辑修改。用户可按需要读取平台矩阵子块、增广矩阵和状态矩阵,并可在此基础上编写程序,进一步开发小干扰稳定、控制系统参数优化等计算程序。
对于PSS,PSASP考虑3种输入信号(Δω、ΔPg、ΔUt),其结构如图1所示,其中环节通常选取K=0使该环节作为隔直环节,其余2个环节则为相位补偿环节。与通常所用的PSS模块相比,隔直环节s/(1+sτq)少乘了τq,因此对应的增益Kq也要相应增大τq倍才能取得相同的效果。
在PSASP内部对PSS进行具体处理时加入了一个时间常数为τ6=0.02 s的惯性环节。以ΔUin代表输入信号,将其写为传递函数的形式,如图2所示。其中ΔU1、ΔU2、ΔU3是中间变量,ΔUs是PSS的输出信号,这4个作为状态变量。
根据图2可以写出PSS的线性化方程:
[dΔU1/dt dΔU2/dt dΔU3/dt dΔUs/dt]T=
在小干扰线性化平台中,ΔU1、ΔU2、ΔU3和ΔUs这些和PSS相关的状态变量包含在ΔXc(发电机调节器包括AVR、GOV和PSS的状态变量子向量)中,ΔUc为发电机调节器输入控制变量子向量,对应的线性化微分方程如式(2)所示:
对于某个PSS,其对应A1c矩阵的一个44的子阵和B1c中的一个43的子阵(分别对应3个不同的输入信号Δω、ΔPg和ΔUt)。本文仅考虑一个输入信号Δω,则对应ΔPg和ΔUt的4行2列这8个元素均为零,仅有对应Δω的41的子阵为非零元素。当PSS参数变化时,对增广矩阵的影响仅限于44和41的这2个子阵,进行很小的修改即可生成对应更新PSS参数的增广矩阵。
因此,在PSS参数优化前,通过小干扰线性化平台对系统方程和动态元件进行线性化,得到全系统的增广矩阵;通过对PSS所在发电机的准确定位,找到其对应A1c的44子阵和B1c的41子阵的位置。在优化过程中得到PSS参数后根据式(2)更新增广矩阵(即A1c和B1c)中的相关元素,生成新的增广矩阵,为PSS参数优化提供了一个简便而有效的数据处理对象。
小干扰线性化平台为PSS参数优化提供了一个很好的数据平台,在此平台上进行PSS参数优化可以使用PSASP丰富的元件模型;也省去了进行线性化这一步骤,稍加修改即可更新增广矩阵进行特征值计算操作;还可以使用PSASP的暂态稳定计算功能进行时域仿真校验。因此,在进行PSS参数优化时,能够充分利用现有工具,将主要精力集中在优化方法上;所设计的参数优化程序能够适用于PSASP的各种模型,还可以直接使用已有的PSASP数据,因而具有广泛的实用性。
2 问题描述
安装PSS的目的是在复平面上让机电振荡模式相应的特征根向左移动。装设了PSS后的闭环系统的特征值决定了全系统的稳定状况,对于表征振荡模态的共轭特征根,定义阻尼比为
其中,σ和ω分别代表特征值的实部和虚部。在电力系统中一般要求阻尼比不小于0.05,以保证系统有较好的动态特性。因此,将阻尼比作为PSS参数优化的目标,目标函数描述如下:
式中ξi,j为第j种运行方式下第i个机电振荡模态
的阻尼比;S为机电振荡模态集合;k为优化过
程中考虑的运行方式的个数。
优化的目的是使多种运行方式下所有机电振荡模态中的最小阻尼比最大化,考虑到PSS的参数约束,PSS参数优化可以表述为如下带约束的优化问题:
时间常数τ6、τq、τ2e和τ4e分别取为固定值0.02、5、0.05和0.05 s。
3 人工鱼群算法
在水域中营养物质最多的地方会聚集较多的鱼;而营养物质较少的地方,鱼会越来越少。因此鱼生存数量最多的地方一般就是该水域中营养物质最丰富的地方。人工鱼群算法基于此构造了人工鱼模拟鱼群寻找食物的行为,通过各人工鱼个体的局部寻优最终实现群体中全局最优值突现的目的[13]。
在一个n维的目标搜索空间中,构造m条人工鱼组成一个鱼群,第i条人工鱼的位置可以用向量xi=[xi1 xi2xin]表示,其在当前位置的食物浓度即适应度函数Yi=f(xi)。
人工鱼个体间的距离表示为di,j=‖xi-xj‖,人工鱼的感知距离即视野用V表示,人工鱼在运动过程中感知其视野范围内其他鱼的状况从而决定自己的行为选择。人工鱼每次移动的最大步长用λ表示,拥挤度因子用δ描述,代表在某个位置附近的拥挤程度。人工鱼的典型行为有觅食、聚群和追尾,以下对其行为进行简要介绍。
a.觅食行为。设人工鱼的当前位置为xi,该位置的食物浓度为Yi。在其视野范围内(即di,j
b.聚群行为。设人工鱼的当前位置为xi,该位置的食物浓度为Yi。探索当前人工鱼xi视野范围内的鱼的个数nf并计算其中心位置xc,中心位置xc的食物浓度为Yc。如果Yc/nf>δYi,即表明中心位置有较多的食物并且不太拥挤,则朝中心位置xc方向前进一步;否则执行觅食行为。
c.追尾行为。设人工鱼的当前位置为xi,该位置的食物浓度为Yi。探索其视野范围内食物浓度最大的人工鱼位置为xmax,其食物浓度为Ymax。以xmax为中心探索xmax视野范围内(即dmax,j
在鱼群算法中,设置一个公告板,用以记录当前搜索到的最佳位置及该位置的食物浓度。各人工鱼每次行动完毕后,将最新位置的食物浓度与公告板中的食物浓度进行比较,如果该位置的食物浓度大于公告板中的食物浓度,则用该位置及其食物浓度代替公告板中的相应值,以使公告板能够记录搜索到的最优位置及该位置的食物浓度。
根据所要解决的问题性质,对人工鱼当前所处的环境进行评价,从而选择一种行为执行。如较常用的评价方法就是选择各行为中使得向最优方向前进最大的行为,也就是各行为中使得人工鱼的下一个状态最优的行为,如果没有能使下一状态优于当前状态的行为,则采取随机行为。
对于人工鱼群中的适应度函数值最小的人工鱼,可以以一定的概率p重新初始化或者赋予公告板中的目标函数最大的人工鱼的参数,以加快算法的搜索效率和收敛速度。变异概率p在迭代初期应足够小,不影响鱼群的寻优活动;而在迭代中后期应变大,丰富鱼群的多样性,加快寻优和收敛速度。可以采用线性变换的方法,如p=i/imax,其中i是当前迭代次数,imax是最大迭代次数。
4 算例
以新英格兰10机39节点系统为例,验证人工鱼群算法优化PSS参数的有效性。其参数如文献[3]所示,其中发电机39代表了美国-加拿大互联系统的等值机。在计算中,发电机39采用电势恒定的2阶模型(1型),其余发电机采用考虑转子励磁绕组动态过程的变化的3阶模型(2型),励磁系统均采用自并励静止励磁系统(2型励磁),其参数为:Kr=1,τr=0.01 s,K2=1,τ1=τ2=0.05 s,τ3=-1 s,τ4=10 s,Ka=200,τa=0.01 s。
将上述运行方式作为运行方式1,以此为基础,在方式2中21-22支路停运,方式3中14-15支路停运。未安装PSS时,3种运行方式下的机电振荡模态如表1所示。从表1可以看出,3种运行方式下的阻尼均不足,每种运行方式都出现多个负阻尼的机电振荡模态,这将导致系统在遭受扰动的条件下增幅振荡而失稳。发电机39是等值机,因此在发电机30～38装设PSS,PSS参数的取值范围为Kq∈[0 75],τ1e∈[0.05 1.0]s,τ3e∈[0.05 1.0]s。
同时考虑3种运行方式对27个参数进行优化。人工鱼的条数取为20,每条人工鱼的维数是27,其感知距离V=0.5,每次移动的步长λ=0,05,拥挤度因子δ=0.618,觅食最大尝试次数Ntry=3,最大迭代次数Nmax=50。
使用人工鱼群算法优化PSS参数的结果如表2所示,按该结果配置PSS参数后,3种运行方式下的机电振荡模态如表3所示。
由表3可以看出,按人工鱼群算法优化的结果配置PSS参数后,系统阻尼有了明显的提高,3种运行方式下的最小阻尼比为15.862 8%,能够很好地适应运行方式变化的情况,保证了系统的安全稳定运行。
5 结语
基于双混沌映射改进的人工鱼群算法 第5篇
人工鱼群算法AFSA[1]是由李晓磊等人在2002年提出的一种模拟鱼群在自然环境中的生态行为的随机搜索优化算法。人工鱼群是一种高智能的集群智能算法,具有良好的求取全局极值能力,并具有对初值和参数选择不敏感、鲁棒性强、简单、易实现等优点,但随着人工鱼群算法应用的不断拓广,人们发现其中也存在着一些不足[2,3]:(1)当寻优的域是平坦的区域时收敛于全局的最优解速度减慢,容易陷入局部最优;(2)由于参数取固定值,算法一般在优化初期收敛速度快,后期却往往收敛速度减慢。众多学者提出了不同的改进算法,文献[4]提出了基于遗传算法的人工鱼群优化算法,克服了人工鱼漫无目的的随机游动或在非全局极值点的大量聚集的问题,但实现起来比较复杂。文献[5]提出了一种改进的人工鱼群算法,在觅食行为中让人工鱼直接移动到较优位置并动态调整人工鱼的视野和步长,在一定程度上平衡了全局搜索能力和局部搜索能力,但随着函数维数和群体规模的增加,其运行时间明显变长。文献[6]提出了一种人工鱼群算法与采用捕鱼策略的优化算法相结合的混合算法,在优化初期使用人工鱼群算法搜索局部最优域,而在优化后期则使用捕鱼策略进一步搜索最优解,但该方法存在搜索精度不高的问题。文献[7]提出了基于Logistic映射的混沌人工鱼群优化算法,利用Logisitic混沌映射来初始化鱼群,但由于Logisitic映射的分布呈现两头高,中间低的特点,当最优值落在中间位置时,需要多次迭代才能得到最优解。这很大程度上降低了算法的搜索速度和效率。
本文针对人工鱼群算法的不足提出了一种基于双混沌映射的人工鱼群算法。该算法采用分布均匀的Tent混沌映射来初始化鱼群,获得高质量的分布均匀的解空间;同时对鱼群施加混沌扰动,这时利用局部分布均匀的Logistic映射生成混沌变异算子,并将其引入部分优秀个体的变异操作中。两种不同规则的混沌映射使得种群具有足够的多样性,并在鱼群陷入局部最优时施加混沌扰动,使得鱼群摆脱局部极值,驱使鱼群向全局最优位置移动。
1 基本人工鱼群算法和混沌理论
1.1 人工鱼群算法基本理论和算法
人工鱼群有以下几个主要优点:具有较快的收敛速度,适用于解决实时性要求较高的问题;具备并行处理和全局寻优的能力;算法对初值和目标函数的要求不高;算法应用广泛,对问题的机理模型要求不高,甚至不需要问题的精确描述;对于一些精度要求不高的场合,可以快速得到一个可行解。
为便于下文表述,对一些符号的定义做出如下说明:人工鱼个体的状态用变量X=(x1,x2,,xn)表示,其中xi(i=1,2,,n)代表需要寻优的变量;适应值函数Y=f(X)表示人工鱼当前状态的食物浓度;人工鱼个体Xi与Xj之间的距离用di,j=Dis(Xi,Xj)来表示;δ表示拥挤度因子;trynumber表示人工鱼每次移动时最大的试探次数;AF_Visual表示人工鱼的感知范围;AF_Step表示人工鱼移动的步长;AF_Number表示参与寻优的人工鱼的数目。
人工鱼群算法的行为描述可以分为以下五种:
(1)觅食行为
假设人工鱼的状态可表示为X=(x1,x2,,xn),当前位置的食物浓度为Y=(y1,y2,,yn),人工鱼个体之间的距离为di,j=‖Xi-Xj‖,设人工鱼当前状态为Xi,在其感知范围内随机选择一个范围Xj,如果Yi<Yj,则向该方向进一步,若不满足条件,则随机移动一步,Xinext=Xi+rs。其中r表示(0,1)之间的随机数,s表示移动的最大步长。
(2)聚群行为
人工鱼在觅食过程中自然聚集成群,当在其感知范围内搜索其他集群的伙伴数目nf和中心位置Xc时,若则表明伙伴中心有很多食物且不拥挤,则向伙伴中心移动否则,执行觅食行为。式中δ为拥挤度因子。
(3)追尾行为
当一条鱼发现食物后,其他人工鱼会尾随它向食物游去。搜索当前领域中食物浓度最大的人工鱼所在位置Ymax,当
(4)公告板
算法中定义了公告板,用来记录最优人工鱼个体的状态。每条人工鱼在在寻优过程中,行动完毕将自身的当前状态与公告板的状态进行比较,如果优于公告板状态,就用自身状态更新公告板的状态,否则公告板的状态保持不变,这样当整个算法迭代结束后,公告板中记录的状态就是最优个体的状态。
(5)移动策略
根据所要解决的问题性质,对人工鱼当前所处的环境进行评价,从而选择一种合适的行为策略。可以按照进步最快的原则或者进步即可的原则来选择。如对于求取最大值的问题,可以先执行追尾行为,若行动执行后的值比上一步的值小,则表明没有进步,若行动执行后的值比上一步的值大,就表明有进步。根据行动执行后值的大小来评判进步的快慢。进步最快的原则是指分别模拟执行聚群、追尾等行为,然后评价行动后的值,选择其中的最大者来实际执行;而进步即可的原则是指选择一种执行行为(如追尾行为)后,只要执行后的值比上一步值大,就选择这种执行行为。若比执行前的值小,则选择另外一种执行行为。默认的行为是觅食行为。
以下给出人工鱼群算法的步骤:
Step 1初始化人工鱼群规模AF_number、每条人工鱼的初始位置、视野AF_visual和步长AF_step、拥挤度因子δ、最大试探次数trynumber、最大迭代次数Iter_max等参数。
Step 2计算每条人工鱼的适应度,并与公告板的状态进行比较,若较好,则更新公告板状态。
Step 3计算视野AF_visual和步长AF_step。
Step 4每条人工鱼个体通过觅食、聚群、追尾和随机行为更新自己的位置。
Step 5若达到迭代次数或预设的精度值,则终止算法,输出最优解;否则转Step 2。
1.2 混沌理论
混沌(Chaos)[8]是自然界广泛存在的一种非线性现象,是一种貌似无规则的运动,是非线性动力学系统所特有的一种运动形式,它广泛地存在于自然界,诸如物理、化学、生物学、地质学,以及技术科学、社会科学等多种学科领域。混沌优化算法是一种充分利用混沌的这些特性进行优化搜索的优化算法,它可以很好地解决复杂函数的优化问题,具有很高的寻优效率。
目前比较常用的混沌模型有Logistic映射模型和Tent映射模型[9]:
(1)Logistic映射
Logistic映射是应用非常广泛且形式非常简单的一维混沌映射,Logistic映射系统定义式如下:
式中,u是控制参数,且u∈[0,4],x∈[0,1]。这个系统看起来好像很简单,但它有非常复杂的动力学行为。它包括了非线性理论中的周期、混沌、分岔图等。当3.5699456<u4时,Logistic映射呈现混沌状态,当u=4时,这个系统是一个完全混沌系统。此时,混沌序列的初值为0.501。
(2)Tent映射
Tent映射方程:
当0<a<1,0x01时,系统处于混沌状态,混沌序列的均值为0.5。
仿真实验在Matlab R2010a上进行,比较了Logistic映射和Tent映射的性能。图1是Logistic映射在[0,1]范围内迭代30000次的分布图,初值取0.2。由图可知在[0,0.1]和[0.9,1]区间取值概率较高,概率最高点可达1917次,而在[0.1,0.9]平均取到223次,[0,1]整个区间上平均取值概率为300次;图2是Tent映射在[0,1]范围内迭代30000次的分布图,初值取0.1,a取值0.501。从图中可以看出最大取值概率为330次,最小为280次,平均在302次左右,明显比Logistic映射概率分布均匀。
本文利用这两种混沌映射的分布特性来维持鱼群的多样性。首先,利用Tent映射的均匀分布性产生混沌初始鱼群;然后,利用Logistic映射生成的混沌变量在[0.9,1]分布点较多的特性,对人工鱼的聚群和追尾行为进行混沌扰动。
2 基于双混沌映射改进的人工鱼群算法
基本的人工鱼群算法虽然具有较好的全局寻优特性,但是面对复杂的问题,易陷入局部最优。针对这种情况,本文引入混沌动力学的思想,提出了基于两种混沌映射的人工鱼群算法。该算法从以下两个方面进行了改进:
(1)由Tent映射产生初始种群。利用Tent映射的遍历性产生分布均匀的混沌变量,得到质量较好的初始解群,提高了计算效率。具体过程如下:
设原始空间的维数为n,对式(2)中的xk分别赋予n个有微小差异的初始值x01,x02,,x0n,迭代k次产生k个混沌变量,每个混沌变量代表一个混沌人工鱼。
(2)由Logistic映射对人工鱼的聚群和追尾行为进行混沌搜索。随着人工鱼群迭代的进行,调用Logistic映射对群体中适应度较高的部分个体(一般取10%左右)进行微小的混沌变异。混沌变异有可能产生比变异前更好的优秀个体,从而可以有效地避免基本人工鱼群算法易陷入局部最优的问题。本文设计的局部混沌变异利用了Logistic映射在[0.9,1]区间出现概率比较大的特性,具体过程如下:
设迭代过程中第i代群体中的优秀个体为Xi=xi1,xi2,,xin,执行聚群行为和追尾行为后得到相应的Xinext,然后对Xinext的每个分量进行一次[-Visual,Visual]内的混沌搜索CX=Xinext+Visualγ,γ为每次迭代产生的混沌变量。如果CX的位置的食物浓度大于Xinext且不太拥挤,则人工鱼朝着CX的方向移动。否则朝着Xinext的方向移动。
基于双混沌映射改进的人工鱼群算法流程图如图3所示。
3 仿真实验结果及分析
本文实验软件平台为Mtalab R2010a和Windows XP;实验硬件平台采用Intel Core2 CPU,主频为2.10GHz,内存2GB。三个测试函数[10]如下:
(1)Rastrigin函数其中,xi∈[-5.12,5.12],在x*=(0,0,,0)处取得全局最小值f1(x*)=0,是一种典型的非线性多模态函数,峰形呈高低起伏不定跳跃性的出现,所以很难优化查找到全局最优值,被认为是优化算法很难处理的一个复杂多峰问题。主要用来考察算法的全局寻优能力。5
人工鱼群规模为50,觅食行为中重复次数trynumber=10。表1列出了AFSA,模拟退火算法SA(Simulated Annealing),基于Logistic映射的人工鱼群算法LAFSA(Artificial Fish School Algorithm Based on Logistic Map)和CAFSA求解函数所得的寻优结果。
函数f1和函数f3的最小值为0,在迭代曲线中,为了更清晰地表达寻优结果,我们对适应值取以10为底的对数,当适应值为0时,则规定对数值为-20。
由表1可知,对于测试函数f1和f2,本文算法无论是在最优值还是均值方面都比其他算法的精度更高且性能更优;对于测试函数f3,本文算法取得了较好的最优值,但没有LAFSA算法的平均值好。从图4可以看出,本文算法的收敛速度更快,且不易陷入局部最优。当算法出现停滞时,本文改进算法可以在迭代数次后跳出局部最优,向全局最优位置移动,取得较高精度的最优值,SA算法也取得了全局最优值,但收敛速度较慢。从图5可知,AFSA,SA和LAFSA三个算法的性能相当,而本文算法可以快速收敛到全局最优值,且最优值的精度也较高。从图6可知,四种算法都得到了全局最优值0,LAFSA算法取得了较好的均值,但没有本文算法收敛速度较快。由以上可知,AFSA算法无论是在搜索精度和收敛速度方面,都没有另外三种算法性能好。本文算法相对于SA和LAFSA算法来说,虽没有SA或LAFSA算法的均值好,但收敛速度是最快的且搜索精度较高。
4 结语
本文针对基本人工鱼群易陷入局部极值的问题,提出了基于Logstic映射和Tent映射的混沌人工鱼群算法,利用混沌搜索的遍历性和初值敏感性,使得陷入局部极值的人工鱼跳出局部极值,向全局最优移动。通过3个测试函数进行仿真对比实验,结果表明改进的CAFSA比其他算法求解精度更高且性能更优。如何减少由于加入混沌初始化和混沌变异操作所带来的时间消耗,是今后进一步的研究方向。
摘要：针对人工鱼群算法(AFSA)易陷入局部最优的问题,提出一种基于双混沌映射的人工鱼群算法(CAFSA)。该方法利用Tent映射的均匀分布性产生混沌初始鱼群,增加搜索的多样性;其次在人工鱼群演化陷入局部最优时,利用局部分布均匀的Logistic映射生成混沌变异算子对其产生扰动,使其跳出局部最优值,向全局最优值靠近。仿真实验表明,改进后的算法比基本人工鱼群算法的全局寻优能力更强,搜索精度更高。
关键词：人工鱼群算法,混沌映射,局部最优,混沌变异
参考文献
[1]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.
[2]Cai Y.Artificial fish school algorithm applied in a combinatorial opti-mization problem[J].Intelligent Systems and Applications,2010,2(1):37-43.
[3]Zhou Y Q,Xie Z C.Improved artificial fish-school swarm algorithm forsolving TSP[J].Systems Engineering and Electronics,2009,31:1458-1461.
[4]刘白,周永权.基于遗传算法的人工鱼群优化算法[J].计算机工程与设计,2008,29(22):5827-5829.
[5]王联国,洪毅,赵付清.一种改进的人工鱼群算法[J].计算机工程,2008,34(19):192-194.
[6]陈建荣,王勇.一种人工鱼算法与捕鱼算法相结合的优化方法[J].计算机应用与软件,2011,28(4):196-199.
[7]曲良东,何登旭.一种混沌人工鱼群优化算法[J].计算机工程与应用,2010,46(22):40-42.
[8]周茜.混沌理论及应用若干问题的研究[D].南开大学,2010.
[9]Alatas B,Akin E,Ozer A B.Chaos embedded particle swarm optimi-zation algorithms[J].Chaos,Solitons&Fractals,2009,40(4):1715-1734.
人工鱼群 第6篇
随着电网规模不断发展,建设具有坚强、灵活的特高压电网结构体系是当前电网发展的重要战略方向[1,2]。输电网扩展规划作为建设坚强电网的重要组成部分可以合理的调节电网结构,有利于电网经济、安全、可靠运行[3,4]。因此,在当前电网发展背景下研究大规模输电网络的扩展规划问题具有重要意义。
近年来,众多学者对相关问题进行了分析报道。文献[5]建立考虑N - 1 安全准则的输电网规划模型,利用改进量子遗传算法对问题进行求解。文献[6]建立考虑线路建立投资的经济评估模型,利用生物地球学进化算法研究输电网的规划问题。文献[7]对比分析了不同输电网扩展规划模型,提出一种综合考虑火电机组和风电机组运行的经济规划模型,利用基于粒子布朗运动的优化算法研究含风电场的输电网扩展规划问题。以上文献主要从线路投资的经济性能进行网架扩展规划评估,很少综合考虑投资运行、网损及过负荷对扩展规划所产生的影响。
另一方面,人工鱼群算法在处理非线性函数优化问题方面具有很好的实用性能[8],但在处理大规模、高维工程应用问题时其收敛性能需要进一步改进和提高。文献[9]采用变异算子策略,利用自适应步长的方法提高人工鱼群算法的全局寻优能力。文献[10]对人工鱼群算法的觅食、群聚、追尾等关键寻优步骤进行分析,引入自适应移动步长的方法以提高算法的全局寻优性能,并通过典型测试函数进行验证。
针对以上问题,本文建立了考虑投资运行、网络损耗及过负荷费用的多目标输电网扩展规划数学模型。针对传统鱼群算法初始化复杂、收敛速度慢和收敛精度较低的问题,在其觅食、追尾过程中引入自适应变步长策略以提高算法的寻优性能。利用改进的人工鱼群算法对Garver - 6 节点和18 节点系统进行仿真计算,验证所提算法的高效可行性。
1 输电网络扩展规划数学模型
基于简易直流潮流计算方法[11],从输电线路投资运行、年网络损耗及系统运行过负荷的角度建立输电网扩展规划数学模型:
式中Z为系统所需扩展线路集合; Ω 为过负荷线路集合; ci为第i条扩展线路每千米的投资费用; xi和li为支路扩展线路数和其对应长度; K为网损经济评估系数; ri和pi为扩展后支路对应电阻和流动功率; pmax为支路允许流过最大功率; Pex和C为系统总过负荷量和相应惩罚系数。
约束条件包括直流潮流约束和线路投资约束:
式中P为节点注入功率; B为电网节点导纳矩阵虚部; θ 为节点电压相角向量; Bl为支路导纳对角矩阵; A为系统关联矩阵;ximin和ximax为支路线路增加下、上限。
2 改进人工鱼群算法
2. 1 人工鱼群算法
人工鱼群算法( artificial fish algorithm,AFA) 是一种通过模拟鱼群觅食行为的随机智能优化算法,其基本原理如下:
( 1) 鱼群初始化
设置鱼群规模为N的人工鱼在D维搜索空间游动,采用随机变量函数randint() 进行初始化,其对应的位置状态向量X =( x1,x2,…,xi,…,xD) ,其对应的食物浓度为Y = f( X) 。
( 2) 觅食过程
当前人工鱼i在其感知范围内向人工鱼j游动,若其食物浓度Yi< Yj,则人工鱼i向人工鱼j移动,否则人工鱼i随机进行移动,其对应的觅食过程为:
( 3) 聚群过程
搜索当前人工鱼i范围内总人工鱼数目nf及其对应的中心位置,若有Yc/ nf> βYi,其中 β 为拥挤度因子,则当前人工鱼向中心位置移动,否则,继续执行觅食过程,聚群过程为:
( 4) 追尾过程
搜索当前人工鱼i范围内食物浓度最优人工鱼个体Xm,若有Ym/ nf> βYi,则向最优鱼移动,否则,执行觅食过程,追尾过程为:
( 5) 公告板设置
人工鱼群优化过程中公告板主要用于记录当前迭代次数下最优鱼群位置及浓度,以方便下次迭代更新。
2. 2 改进人工鱼群算法
本文介绍了一种改进的人工鱼群算法( improved artificial fish algorithm,IAFA) ,其主要从人工鱼群算法初始化、觅食及追尾过程进行改进处理,从而提高算法在处理高纬复杂非线性优化问题的性能,具体改进如下几个方面。
( 1) 人工初始化鱼群
首先随机生成初始可行人工鱼X1,其位置状态为: X1= xi min+ rand( ) × ( ximax- ximin) ,判断X1是否满足约束条件,若是,则按上述方法生成X2,否则,X2= X1+ r0× ( X2- X1) ,其中r0为在区间[0,1]中的常数,若X2任然不满足约束条件则将r0按指数规律减少,直达满足要求为止。依据上述方法可以随机生成种群规模为N的初始人工鱼群。
( 2) 觅食过程改进( 以极小值计算为例)
根据当前人工鱼i的位置状态Xi计算其浓度函数为Yi,在其感知范围内随机选取人工鱼j,其对应的位置状态和浓度函数分别为Xj和Yj,若对应浓度偏差Y = Yj- Yi小于零,则接受新解,若Y≥0&&M* K* exp Y < α,任然接受新解,否则重新寻找较优状态直至达到最大尝试次数。
( 3) 自适应变步长策略
在人工鱼寻优过程中设置其自适应变步长[12]为:
式中Xi为当前人工鱼状态; Xj为当前状态的感知范围类的随机状态。
2. 3 基于IAFA的输电网扩展规划步骤
基于改进AFA的输电网扩展规划基本步骤如下:
( 1) 输入系统初始数据: 包括节点注入功率、线路参数及扩展规划水平参数。
( 2) AFA算法初始化: 包括人工鱼数、迭代次数、拥挤度因子、视野、最大尝试次数等参数。
( 3) 采用实数编码方法,利用本文的方法对人工鱼进行初始化,每个人工鱼代表一个初始规划方案,对应的每个组成元素代表当前支路的待建线路数,根据公式( 1) 计算当前个体的食物浓度( 1 /F) ,并将最优位置状态和食物浓度记录在公告板上。
( 4) 采用本文方法对人工鱼进行觅食、追尾尝试操作,若觅食操作后所得食物浓度大于追尾操作,则执行觅食操作,否则执行追尾操作。
( 5) 将新的位置状态及食物浓度与公告板保存局部最优值进行比较,选取较优的结果并继续保存在公告板上。
( 6) 判断是否达到最大迭代次数,是则输出最优扩展规划方案,否则转至步骤( 4) 。
3 算例分析
选取Garver - 6 节点和18 节点输电网[13]为例进行仿真分析,系统基准功率为100 MW,其中6 节点输电网可扩展线路数为15 条,18 节点输电网可扩展线路数为32 条。改进人工鱼群算法参数设置如下: 人工鱼规模为30; 最大迭代次数为40; 拥挤度因子取0. 621; 觅食视野为3; 最大尝试次数为30。输电网络扩展规划参数设置如下: ci= 0. 132 5; K = 6 000; C = 108。
3. 1 扩展规划结果分析
基于MATLAB 7. 0 软件进行仿真计算,不同算例下不同算法的规划结果见表1。
由表1 可知,不同算例不同算法下的具体最优扩展规划方案各不相同,采用改进的人工鱼群算法结果明显优于基本人工鱼群算法。对于Garver - 6 节点测试系统,基于改进人工鱼群优化算法计算的最优经济评估目标函数值为4 364. 5 万元,其中线路投资费用为3 021. 2 万元,网络年网损费用为1 357. 9 万元,过负荷费用为0 万元,与基本人工鱼群算法相比,总费用减少了14. 6 万元。对于18 节点测试系统,采用改进人工鱼群优化算法计算的最优经济评估目标函数值为13 894. 6 万元,与基本人工鱼群算法相比,总费用减少了62. 5 万元。出现此情况的原因是采用AFA算法时由于没充分考虑系统运行的N - 1 运行准则,以至出现过负荷的情况,最终造成规划结果不同; 另一方面,当考虑过负荷运行时,系统线路投资成本升高,但系统年网络损耗明显下降,且系统安全运行水平提高。
注: 表中新建线路表达式为: 节点i - 节点j ( 新建线路数)
图1 和图2 分别为采用改进人工鱼群优化算法下Garver - 6节点测试系统和18 节点测试系统的具体规划结果系统结构图,其中实线表示现有输电线路,虚线为扩建输电线路。
3. 2 算法性能对比
以Garver - 6 节点和18 节点测试系统为例研究本文所提改进人工鱼群算法的搜索性能,并与基本人工鱼群算法下的性能进行比较,不同算例下不同算法的收敛性能曲线如图3 所示。
由图3 和图4 可知,改进人工鱼群算法具有更好的收敛精度。原因是在人工鱼群初始化过程中对变量进行人工干预、利用自适应变步长策略改进人工鱼的觅食、追尾行为的寻优步长,加快了算法的收敛速度,很好的提高了算法的收敛性能。
4 结束语
利用改进人工鱼群算法研究输电网络扩展规划问题,结论如下:
( 1) 从线路投资运行、网损及过负荷的角度建立输电网扩展规划经济评估模型对大规模电网安全运行提供有效指导,考虑N - 1 安全准则进行线路规划更加符合实际运行要求。
人工鱼群 第7篇
关键词：文本分类,人工鱼群算法,数据挖掘,分类规则
文本分类是当前流行的文本信息自动处理技术，也是机器学习、信息检索领域及自然语言处理的研究热点之一，其任务是把一些相似的文档分成一类，对海量信息进行高效地组织和整理，以便于实现信息的准确分流和定位，从而提高用户查询和检索的效率。它是一种动态的分类方法，根据样本自身的内容分成若干类，使得类内样本的相似性尽可能大、类间样本的相似性尽可能小。近年来，随着智能技术的迅猛发展，遗传算法，粒子群算法，蚁群算法已经应用到分类规则挖掘之中，并取得一系列较好的成果。但是这些算法也都各有缺陷，人工鱼群算法具有很好的克服局部极值，获得全局极值的能力，对初值和参数要求不高，而且对启发式函数的要求并不敏感。本文将人工鱼群算法引入到文本分类之中，很大的提高了规则的适应度和简洁性。
1 人工鱼群算法简介
人工鱼群算法(artificial fish-swarm algorithm,AFSA)是近几年提出的一种新型智能优化算法，它通过模拟鱼群的觅食，聚群和追尾等行为活动来实现全局寻优功能。人工鱼群算法采用是自下而上的设计方法，首先构造人工鱼个体，然后个体在寻优过程中自适应的选择觅食，聚群，追尾等合适行为，最后使全局最优结果突现出来。人工鱼群的相关定义和行为描述如下：
人工鱼个体状态可以用向量的形式来表示：X=(x1,x2,,xm),其中xi(i=1m)是寻优变量，人工鱼之间的距离可以定义为dij=‖XiXj‖，表示Xi与Xj之间不同分量的个数，人工鱼当前所在位置的食物浓度即目标函数值可以定义为：Y=f(X)，Visual表示人工鱼每次搜索的视野范围，STEP表示人工鱼每次的移动步长，δ为拥挤度因子，表示一定范围内鱼群的拥挤程度。
1)觅食行为：设人工鱼当前状态为Xi,在其视野范围内随机选择一个状态Xj,然后比较当前状态和新状态之间的食物浓度大小，若Yi
2)追尾行为：设人工鱼当前状态为Xi,探索其邻域范围内食物浓度函数值Yi为最大的一个伙伴Xmax,如果在其邻域范围内Xmax位置的食物浓度大于当前状态的食物浓度，且其视野范围内的伙伴数目nf满足nf/N<δ,即表明Xmax位置附近有较多的食物并且不太拥挤,那么向Xmax位置前进一步;否则执行觅食行为.
3)聚群行为：设人工鱼当前状态为Xi,探索当前领域视野范围内的伙伴数目为nf,中心位置为Xc，计算中心位置Xc处的食物浓度，如果中心位置的食物浓度大于当前状态的食物浓度，且在此区域范围内拥挤度因子δ>nf/N,即表明伙伴中心位置不太拥挤,则人工鱼向中心位置Xc移动一步;否则执行觅食行为.
4)随机行为：指从当前状态随机选择为另一状态，有利于扩大搜索范围,跳出局部极值，随机选择行为其实是觅食行为的缺省行为。
5)公告板：公告板其实用以记录最优人工鱼个体状态，每条人工鱼在进行自适应选择活动之后，将自身的食物浓度与公告板进行比较，如果由于公告板，则取代公告板的状态。
6)约束行为：在人工鱼进行随机行为，聚群行为等操作时,不可避免的将会出现不可行解的情况,这时若使它们由无效状态变为可行解，需要加入相应的约束条件来调整。
7)移动策略：人工鱼进行觅食，追尾，聚群等行为方式是按照有进步就行的原则进行的，即只要任何一种行为方式能够取得更高的食物浓度，得到更优的解，则选择这种行为方式。
2 人工鱼群算法在文本分类中的应用
2.1 应用模型
人工鱼群分类规则提取算法在文本分类中的一个应用模型如图1所示。
第一个是训练过程：首先对已知类别的文本训练集进行文本预处理，同时建立一个特征词库;按着进行特征选择，缩减特征词数量;最后使用人工鱼群规则提取算法可以得到一个分类规则集，用于对文本进行类别判断。
第二过程是自动分类过程：首先获取待分类的文本Di，对Di进行文本预处理，获得文本Di的向量空间模型(VSM)表示;然后根据特征词库进行特征选择，减少Di的向量空间的维数，得到使用特征词和词频的文本Di的表示;最后就可以使用分类规则集进行类别判断，可以得到文本Di的类别。
2.2 文本预处理
在进行文本分类之前，首先对文本进行预处理，将文本用向量空间模型(VSM)来表示，以向量来表示文本，向量中的一个分量代表着每一个特征词条，例如(w1,w2,wn)，其中wi为第i个特征对应的权重。将文本表示为向量空间模型，而后进行特征选择，最后生成特征词库，其具体过程如下所示：
1)对训练集合中的文档用N-Gram算法进行分词处理;
2)去除在分词处理过程中产生的停用词和低频词，从而降低数据噪音对文本分类产生的负面影响;
3)以特征词在文档中的统计词频为依据进行特征选择，进一步降低特征空间的维数，形成最佳特征子集;
4)去除在每一类文档中都出现的特征词，然后合并所有其它的特征词集，最后得到的特征词集就是我们所需要的特征词库。
2.3 基于人工鱼群算法的分类规则提取算法
2.3.1 分类规则描述及编码设计
分类规则挖掘尽量简洁明了，因为这样使用户更容易理解挖掘出来的规则，在本文中，分类规则的形式如下：
我们采用了IF<规则前件>THEN<规则后件>的形式，其中Term1,Term2...表示的是某一个特征属性的取值，Cj代表的是文本所属的类别。
在该算法中，我们采用Michigan编码方法，即最后产生的结果是一条人工鱼代表一条单独的分类规则。为了提高编码效率，我们之对分类规则的前件进行固定长度的编码方法，且每次参与优化的群体属于同一个类别，如果一个训练集中有F个特征属性，则人工鱼编码长度为2F，编码结构如图2所示。
其中Ai(1iF)表示第i个特征属性，Ai L、Ai H分别表示Ai的上下界
2.3.2 分类规则适应值函数
人工鱼群算法对初值和参数要求不高，对启发式函数的要求也并不敏感，在全局寻优过程中不需要其它外部信息，仅以适应值函数来评估个体的优劣，同时适应值的大小也是人工鱼进行行为选择的依据，这使得适应值函数的设计至关重要。
由于在本文中对分类规则采用的定长编码方式，规模在优化过程中保持不变，我们着重考虑分类规则质量Q(quality)与分类变量α范围两个因素，尽量使最终得到的规则具有最高分类规则质量，最小分类变化范围，分类规则适应值函数计算公式设计如下：
其中，λ为调整适应值函数中分类规则质量和分类变量范围的权重系数。分类变量α范围定义如下：
在文本训练过程中，我们应该尽量降低分类变量的变化范围，从而避免非同类规则之间的相互交叉。
其中Q代表分类规则的质量高低，其取值越大，表明规则与训练集中数据实例的匹配程度越高，这样的规则也具有较高的分类性能。我们将规则的质量Q定义如下：
其中TN为正确拒绝实例数，即为不符合规则前件也不符合规则后件的实例数;TP为正确分类的实例数，即规则前件后件都符合的实例数;FP为错误分类实例数，即符合规则前件，不符合规则后件的实例数;FN为错误拒绝的实例数，即为不符合规则前件符合规则后件的实例数。
2.3.3 基于人工鱼群算法的分类规则生成
鉴于人工鱼编码方式和适应值函数的确定，可以将人工鱼群算法引入分类规则挖掘之中，分类规则的挖掘是文本分类模型的关键，能否挖掘出高效简洁的分类规则集合决定了分类模型的性能好坏，我们用人工鱼群算法来解决分类规则提取问题，是利用人工鱼的几种行为方式，最终能在规则空间中实现优化选择。假设基于人工鱼群算法生成第i类规则，其具体过程如下所示：
1)人工鱼群初始化：首先我们在分类变量的有效范围内，给人工鱼的前件部分的各特征属性赋初值，确定其上下界。从而生成M条均属于同一类别i的人工鱼，代表M条不同规则，完成规则集初始化。
2)公告板赋值：在初始化鱼群中，利用适应值函数计算每条人工鱼当前的适应值，选取最优者赋值给公告板。
3)行为方式的选择：各人工鱼按照进步就行的原则进行行为方式的选择，模拟聚群，追尾行为，适应值比当前状态更优的行为即可被选择，如果没有更好的选择，则进行觅食行为或随机行为来扩大搜索范围。
4)公告板更新：人工鱼的选择每一次行为活动之后，都要将自身当前状态适应值与公告板记录的适应值作比较，若由于公告板的记录，则取而代之，更新公告板。
5)算法终止判断：设置最大迭代次数为try-number，若达到设置的最大迭代次数，则转向下一步骤，否则，返回上述第三步继续执行。
6)规则生成：算法达到最大迭代次数时，即可停止执行，此时公告板中的记录即为优化生成的第i类最优分类规则。
2.3.4 规则的剪枝与训练集修改
规则剪枝的主要目的是以最少的属性集合，形成用户容易接受和理解的最简洁的规则形式，规则剪枝有利于提高分类器的性能，规则剪枝的基本思想是在保持其质量不降低的前提下选择尽可能少的属性。若一条规则Rj有F个属性，可以依次尝试去除每一个属性，然后判断去除之后规则质量是否下降，如果规则质量下降，则不能去除，若并无下降，则去除该属性，以此需重复执行F次，获得剪枝后的规则。
规则Rj的剪枝操作具体过程如图3所示。
一条规则经过剪枝之后，将其加入到规则集中，并对训练集进行相应的修改，将该规则所正确覆盖的训练样本从训练集中移除，这样就得到一个新的训练集。然后在新训练集的基础上再次挖掘出新的分类规则，如此不断循环重复，直到训练集中剩下的训练样本数在允许的范围之内，这样就可以得到一组分类规则集。
2.3.5 整体算法流程描述
基于人工鱼群算法的分类规则提取算法，实质上是一种序列覆盖算法，人工鱼群算法在运行过程中，每生成一条规则，就移去该规则所正确覆盖的样例，直到最后剩下的样例数在允许范围之内，训练算法才结束。算法开始时训练集为所有训练样本，分类规则集为空，然后利用基于AFSA的分类规则生成算法形成规则，之后进行规则剪枝，再对训练集进行相应的修改，其大致过程如图4示。
3 算法仿真实验
前文在理论上探讨了人工鱼群算法在文本分类中的研究，可以用仿真实验验证其有效性，数据采用500篇文本文档进行实验，人工分为5个类：经济，政治，文化，科技，军事。每一类的训练样本数量都是70，测试样本数量都是30。采用C4.5算法和人工鱼群算法分别对数据集进行仿真实验。实验中人工鱼群算法的初始化参数如下：人工鱼群体规模N=20，移动步长Step=0.22，视野范围Visual=0.36，拥挤度因子σ=3.782，最大迭代次数为50，λ=0.85，实验结果如表1所示：
实验结果表明人工鱼群算法发现的分类规则集在准确率上有较大的提高，发现的规则简洁，规则数量少，分类精度高。
4 结论
本文首次将人工鱼群算法引入文本分类之中，实验结果表明，基于人工鱼群算法的分类规则挖掘能产生简洁，易于理解的规则集，具有很好的分类性能，仿真实验说明此方法是可行、有效的。由于人工鱼群算法在数据分类方面的研究还处在起步阶段，还有许多工作要做，本文将其引入文本分类之中算是一个尝试和应用，还有很大的研究空间。
参考文献
[1]陈俊清,朱文兴.基于人工鱼群算法的分类规则发现[J].福州大学学报,2007(2):1923.
[2]李晓磊.一种新型的智能优化方法——人工鱼群算法[D].浙江大学,2003.
[3]苏锦旗,吴慧欣.基于人工鱼群算法的聚类挖掘[J].计算机仿真,2009,26(2):147-150.
[4]修春波,张雨虹.基于蚁群与鱼群的混合优化算法[J].计算机工程,2008,34(14):206-207.
[5]苏金树,张博峰.基于机器学习的文本分类技术研究进展[J].软件学报,2006,17(9):1848.
[6]张银奎.数据挖掘原理[M].北京:机械工业出版社,2003.
[7]Chang Chin-chang.Lin Chi-hjen.LIBSVM:a Library for support vector machines[J/OL].
[8]Denis F R,Gilleron M.Text classification from positive and unlabeled examples.IPMU,2002.
[9]Dwi H,Widyantoro,John Yen.A Fuzzy Similarity Approach in Text Classification Task.IEEE,2000.
人工鱼群 第8篇
电网建设项目物资需求影响因素 (如设计方案、工程实际情况等) 复杂多变, 所需物资的种类繁多, 物资需求呈现明显的随机性和非线性特征, 而支持向量机模型能够在此类问题中表现出较强的优势。在现有利用支持向量机进行预测分析的研究中, 鲍永胜和吴振升应用支持向量机对短期风速进行了预测计算, 沈梁玉和于欣针对夏季电力负荷采用支持向量机进行了预测分析, 祝金荣, 何永秀和Furong Li结合混沌理论和支持向量机提出了一个新的电价预测模型。本文则基于支持向量机模型, 结合加入混沌搜索因子的人工鱼群算法, 提出用于电网建设项目物资需求的预测模型, 并通过实例数据测试模型性能。
一、理论基础
1. 支持向量机。
支持向量机 (support vector machines, SVM) 是由Vapnik提出的一个机器学习算法[9], 以统计学习理论为基础, 数学基础完善, 几何解释直观, 在分类问题、回归分析、图象识别等领域有着广泛应用。其核心思想是将数据实现非线性变换, 映射到特征空间, 寻找支持向量, 确定最优分离超平面 (如图1) 。
支持向量机通过将函数集的子集按照一定规则排列, 使得在相同的置信范围子集中, 实现风险的最小化。现有的SVM通常有C-支持向量分类机、υ-支持向量分类机、ε-支持向量回归机、υ-支持向量回归机。其中υ-支持向量回归机的数学形式为:
而能否较好地求解问题, 支持向量机的关键在于满足维数限制的前提下采用合适的核函数, 不同的核函数对于不同的SVM算法。常用的SVM的非线性核函数有三种:
(1) 多项式函数
(2) Gauss函数
(3) Sigmoid函数
2. 人工鱼群算法。
人工鱼群算法是我国学者李晓磊等提出的一种群智能优化算法, 该算法具有并行搜索、收敛速度快、能够跳出局部最优、对初值不敏感、鲁棒性强等优点, 在参数计算、数据拟合、组合问题和优化调度等领域得到了良好应用。
人工鱼群算法以自然界鱼群的行为学研究为基础, 提出人工鱼的概念, 定义了人工鱼的四种行为:觅食行为、聚群行为、追尾行为和随机行为, 其中随机行为是前三种行为的缺省行为。人工鱼个体对四种行为方式所引起的求解函数值的变化进行分析, 择优执行。通过不断模拟和迭代计算, 人工鱼群体能够表现出对函数优化的群体智慧, 从而使问题得到优化。
二、预测模型构建
1. 问题特性分析。
电网建设项目以输变电工程、配网工程为主。对于各个不同的电网建设项目而言, 物资需求有其个体性和共性。有因工程自身特殊情况而进行的个别设计, 也有按照设计规范可以采用的标准设计图集。共性因素作用下的物资需求, 可以通过区分不同工程类别, 构建恰当的预测模型和算法, 取得满意的预测结果。个体性因素作用下的物资需求, 往往单体预测模型无法满足精度要求, 需采用多项目汇总的方式, 控制总体预测误差, 使预测结果满足实际使用要求。
由于工程建设的特殊性、设计方案的灵活性, 电网建设项目的物资需求非线性明显。物资种类繁多, 样本数据矩阵呈现的稀疏性特征, 预测难度较大。因此建立的预测模型不仅要适用, 而且要通过对比真实值和预测值的差异, 逐步修正预测模型参数, 才能提高预测质量。
2. 模型构建思路。
对于单体工程预测, 选取在非线性问题预测中性能变现良好的υ-支持向量回归机模型。因为选取不同的核函数或设定不同的参数取值, 都会影响预测精度, 所以需要借助寻优算法优化核函数的选取和支持向量机参数的设置。本文利用对初值不敏感、收敛速度快并且全局搜索能力强的人工鱼群算法进行模型优化。先利用较低精度的预测计算, 逐步优化核函数选取和参数设置, 结果满意后再进行高精度的正式预测。同时针对预测中不确定性因素较多, 核函数选择和参数设置规律性差的特点, 在基本的人工鱼群算法中, 增加混沌搜索算子, 利用其随机不重复遍历的特点, 提高算法的搜索性能。采用的混沌搜索算子为:
当μ=4时, 系统将处于完全的混沌状态。
3. 模型代码描述。
以增加了混沌搜索算子的人工鱼群算法, 优化υ-支持向量回归机, 所构建的电网建设项目物资需求预测模型, 用C++语言伪代码描述如下。
三、预测效果分析
1. 测试数据整理。
测试数据采用河南省电力公司自2010年1月至2012年8月间ERP系统中的全部物资需用数据记录。共约42万条, 包括224种物资小类, 涵盖10k V以上级输变电项目、技改项目和配网项目。按照项目个体对原始数据进行整理和分析, 采用数据完整、项目代表性强的数据样本, 从中随机抽取训练集数据和测试集数据, 检验模型预测性能。
2. 结果分析。
以控制电缆和钢芯铝绞线两类物资为例对模型预测结果进行说明, 见图2、图3所示。图中横轴代表电网建设项目的项目样本编号, 纵轴表示物资的需求量。若需求量为0, 则表示该项目不使用此项物资。对比预测值和真实值可以看出, 在多数情况下, 预测值较为准确, 但也有个别点预测值与真实值相差较大, 如图2中的项目7、项目12, 图3中的项目22和项目27。
分析其产生的原因, 由于工程建设项目的个体性和设计方案的灵活性, 使得是否使用此类物资成为影响预测精度的首要问题。然而在项目施工图最终完稿前, 依靠主要工程建设指标对物资需求预测, 此问题又是无法回避的。因此使用模型进行需求预测时, 必须通过增加预测项目数量, 控制总体预测误差的办法, 减小物资使用的随机性, 提高预测判断的准确性。
电网建设项目的物资需求预测实践结果表明, 除个别特定条件下才使用的少数物资不具备预测条件外, 大多数物资可以得到满足使用要求的预测值, 且所预测物资的总值占到项目实际所需物资总价值的80%以上。
(见图2、3)
四、结论
通过整理分析现有ERP系统中与电网建设项目物资需求相关的数据, 构建了基于支持向量机和人工鱼群算法的物资需求预测模型, 测试结果表明模型有效适用, 预测结果能够满足物资需求管理所需的精度要求。虽然模型预测性能仍需进一步完善和提高, 但对于优化物资管理, 降低物资成本具有积极意义, 同时为完善物资需求信息, 改进物资需求管理模式, 提供借鉴和参考。
参考文献
[1]邬斌!, 张玉鑫.基于双向协同的物资需求计划管理在电网工程中的应用研究[J].华东电力, 2012, 40 (5) :913-914.
[2]张斌, 陈建国, 吴金生, 等.台风灾害应急物资需求预测模型[J].清华大学学报 (自然科学版) , 2012, 52 (7) :891-895.
[3]傅志妍, 陈坚.灾害应急物资需求预测模型研究[J].物流科技.2009 (10) :11-13.F蔡开龙, 姚武文, 孙云帆, 等.飞机战伤抢修备件需求预测方法研究[J].电光与控制, 2010:17 (12) :60-63.
[4]张晓磊, 杨西龙, 展丽潇.基于模糊相似推理的应急物资需求预测模型研究[J].军事物流, 2012, 31 (5) :229-231.
[5]鲍永胜, 吴振升.基于SVM的时间序列短期风速预测[J].中国电力, 2011, 44 (9) :61-64.
[6]沈梁玉, 于欣.基于支持向量机的夏季电力负荷短期预测方法[J].华东电力, 2009, 37 (11) :1844-1847.
[7]祝金荣, 何永秀, Furong Li.基于混沌理论和支持向量机的电价预测[J].华东电力, 2008, 36 (5) :16-19.
[8]VAPNIK VN.The natureof statistical learningtheory[M].NY:Springer-Verlag, 1996.
人工鱼群范文
声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
