蚁群优化（精选8篇）
蚁群优化 篇1
1引言
蚁群算法源于1992年一篇博士论文提出的模拟蚂蚁寻找食物所选路径的概率型找寻最优解的方案,这种算法本质是基于一定规则的随机运行来寻找最优方案,模仿蚂蚁寻找和搬运食物时释放信息素的机理,不断优化行走路线,在算法实现中执行时间越长,所获得的路径就越可能接近最优路径。
蚁群优化算法已应用于许多组合优化问题,例如二次分配问题,还有很多实变量动力学问题、随机问题、多目标并行的实现等方面,但在实际算法中需要避免的一个问题是过早收敛的问题,算法在执行中很快陷入到了局部最优解的搜索,难以实现广度搜索。因此,在标准算法基础上出现了优化算法,这些优化算法主体通过对于信息素的调节,防止过早收敛问题。在优化算法中核心在于平衡广度搜索与深度搜索, 保证算法的执行效率、有效性。本文通过对目前常见的蚁群优化算法进行综合分析与比较, 较为清晰的梳理出常见优化算法的特点,有助于在解决实际问题中选择合适方法以及算法优化。
2常见蚁群算法的优化算法
标准蚁群算法存在收敛慢、易停滞、运算时间长等缺陷,后续对其做了一系列的改进,以解决该算法存在的问题,产生了许多改进型算法。下面将介绍三种最典型的改进算法:蚁群系统算法(ACS)、最大最小蚁群系统算法(MMAS)、具有变异特征的蚁群算法。
2.1蚁群系统算法
蚁群系统算法(ACS)是对蚁群算法(AC)的改进,这些改进包括:蚂蚁选择的状态转移规则;全局最优更新规则仅运用于属于最优解路径上的信息素;对所有的路径的信 息量进行 局部更新 规则 (Local UpdatingRule)。在ACS中 ,全局更新只是运用在每一次循环中走最优解路径的蚂蚁,而不再运用与所有的蚂蚁。在所有的蚂蚁搜完成了一次循环后,全局更新才会执行。
2.2最大最小蚁群系统算法
最大最小 蚁群系统 算法 (Max-Min Ant System,MMAS) 是解决TSP、QAP等问题的经典蚁群优化算法之一,其结果要优于一般的蚁群算法。MMAS与ACS一样都只允许在每次迭代中表现最好的蚂蚁更新其路径上的信息素, 这样做可以防止算法过早的出现停滞现象。而MMAS与ACS相比不同的地方在于防止这种停滞现象的方法。MMAS的做法为:限定信息素浓度允许值的上下限,并且采用平滑机制。在算法启动时,MMAS将所有路径上的信息素浓度初始化为最大值。在每次循环之后, 只有在最佳路线上的蚂蚁进行信息素的更新,并将其保持在一个高的水平上,其他之路上的信息素将会按照信息素残留度降低浓度。
2.3与变异结合的蚁群算法
吴庆洪等人提出了一种优化蚁群算法———具有变异特征的蚁群算法。其核心思想为采用逆转变异方式,随机地进行变异,以增大进化时所需的信息量,从而克服传统蚁群算法收敛较慢的问题。这种变异机制之所以会具有较快的收敛速度,是因为它充分利用了2-OPT交换法简洁高效的特点。
3蚁群算法优化的新策略
对蚁群算 法所作的 优化是在 已有的改 进型算法———ACS算法的基础上进行的,下文即将描述的优化途径也都是在前人所做改良(即ACS已有的改良途径)的基础上作的更进一步的改进。
3.1路径选择机制的改良
在ACS的路径选择策略中, 我们需要对ij边上已有的信息进行有效的利用,而对于变量q的设定,存在着很大的偶然性使得我们不能很有效地利用已有信息。对此,为了进一步对已有知识加以充分利用,新变量(∑ijk)/m被引入用以替代变量q,其中∑ijk表示上一次循环中选择路径ij的蚂蚁个体的总数。在q0确定的情况下,∑ijk将伴随着算法的运行而随之增大,从而使蚂蚁个体能在下一次路径选择中优先利用已有的信息来选择将要前往的城市,进一步地提高了算法的搜索性能。
3.2全局信息素更新机制的改进
对于信息素的全局更新,我们不仅仅要运用在每一次循环中走最优解路径的蚂蚁,还要运用与每一次循环中最差的蚂蚁使用。但是对于最差蚂蚁的全局更新规则与走最优解路径蚂蚁的规则不同,其更新规则采用如下的公式
τij(t)←(1-ε)×τij(t)+ε×△τij(t) ;
其中,ε为区间(0,1)上的参数;而△τij(t)则用如下的公式计算:
△τij(t)= Q/L - Q/L’若ij路径是算法已求出的最差路径的一部分
或 = 0若ij路径不是已求出的最差路径的一部分 ;
在ACS算法的基础上, 增加对最差的蚂蚁采用以上的更新机制,能更有效地模拟蚂蚁在自然界的觅食过程中分泌的信息素,能准确得出路径长度与时间之间的关系,可使得更多的已有知识被利用,同时在后续的循环中能够增加好的路径被选择的概率并减少差的路径被选择的概率,这样算法的性能可以大大提高。
3.3增加最小信息素浓度设置
MMAS给每一条支路都设置了一个最小信息素浓度,在算法运行过程中,各个支路的信息素浓度不会降到τmin以下。这样保证了即使没有任何一只蚂蚁选择走某条路径,在再一次的循环中这条路径依然有一定的概率被选中,从而避免了一些可能存在的好的路径被过载地抛弃,同时也避免了算法过早地收敛。设置了一个最小信息素浓度τmin,它的计算公式为:
τmin = 1/[2n?(1-ρ)?L] ;
n表示当前问题的城市节点数 ,ρ为信息素残留度 ,L为算法运算到当前为止,已求出的最优路径的长度 ;为了保证所有路径上的信息素浓度不低于τmin,每当一次循环中的信息素局部及全局更新完成后,就需要比较τij和τmin,如果τij<τmin,则将τij强行设置为τmin。
3.4杂交算子的引入
遗传算法具有良好的搜索能力,引入了杂交算子来对现有的所有解进行重组,这样可以发现潜在的更好的解。我们现在尝试一种新的增强解的方法:杂交算子被引入到ACS算法中, 以对在算法运行过程中产生的新的解进行杂交, 并充分利用当前所知的所有路径信息,两者结合可以发现更好的解,从而对最终我们希望得到的结起了增强作用。
4结束语
蚁群算法作为组合优化的经典算法,在实际问题的应用中仍然存在一些问题,这些问题需要进一步研究。
(1)正反馈机制的建立 ,启发函数的定义 ,求解问题增式的进行,以及最优解与问题定义中的现实世界的况相对应等问题需要考虑。
(2)在开始运行蚁群算法求解问题时 ,需要对大量的变量进行初始化,这些变量的初始值会对算法的性能产生较大的影响。然而这些变量初始值的选取方法和原则在目前还没有一个理论上的依据,只能在多次实验中积累经验从而选择比较好的值。因此在初始化变量的最佳值设置问题上还有待进一步的研究。
摘要：对于求解TSP问题,新型的启发式算法——蚁群算法,是成功解决此类问题核心的算法之一。本文简要介绍了几种启发式算法并引出蚁群算法,并对蚁群算法基本原理、常用算法进行了深入的研究,并介绍了一种新的优化策略。
关键词：TSP问题,蚁群算法,优化策略
蚁群优化 篇2
1引言：
入侵检测系统（intrusion detection system，IDS）作为防火墙之后的第二道安全闸门，能够发现网络入侵行为，因此网络入侵检测已成为网络安全领域的研究热点[1]。网络入侵检测分为误用检测（misuse intrusion detection，MID）和异常检测（anomaly intrusion detection，AID）两类[2]。误用检测技术只可以检测已知入侵行为，不能对未知或变入侵行为进行检测，而异常检测可以较好对未知入侵行为进行检测，成为入侵检测中的主要研究方向[3]。传统网络入侵异常检测算法有：模式匹配算法、BM算法、QS算法等，这些算法均属于单模式的网络入侵检测算法，难以适应现代大规模网络安全检测要求[4]。近年来，随着人工智能技术的发展，出现了隐马尔可夫模型、支持向量机和神经网络等入侵检测模型，其中支持向量机（support vector machine，SVM）较好的克服了神经网络等传统机器学习算法的过拟合、泛化推广能力差等缺陷，对于高维、小样本的网络入侵检测具有明显优势[5-7]。大量实验表明，基于SVM的网络入侵检测模型性能与其参数：惩罚因子C和核函数参数等直接相关。为了获得较优SVM参数，学者们提出采用遗传算法（GA）、粒子群算法（PSO），在一定程度上优化了SVM的入侵检测性能[8-10]。蚁群算法（ant colony optimization algorithm，ACO）是一种源于大自然中生物世界的新仿生类算法，吸收了蚂蚁的行为特性，通过其内在的搜索机制，易于与其他启发式方法相结合[11，12]。
为了提高网络入侵检测率，提出一种变异蚁群算法（mutation ant colony optimization algorithm，MACO优化支持向量机的网络入侵检测模型（MACO-SVM），并通过仿真实验对其有效性进行检验。
变异蚁群算法
蚁群算法是由意大利学者M Dorigo等人在1991年受到蚂蚁搜索食物过程中依据同伴遗留下的信息激素进行最短路径选择的启发而提出的一种新的仿生优化计算方法，具有正反馈、分布式计算和贪婪启发式搜索等特点，但是基本蚁群算法存在过早收敛以及局部聚集等问题，为此，本文探路过程中，对蚂蚁进行高斯变异，打破蚁群严重聚集的情况（局部极值），产生一种变异蚁群算法（MACO），以便探索新的路径，提高问题求解的效率。
MACO算法优化SVM参数原理
采用MACO算法对SVM的参数C和σ优化过程，节点值表示C和σ，以入侵检测率作为目标函数，激素物质遗留在蚂蚁所走过的每个节点上，MACO算法所搜索出的最终路径表示最优网络入侵模型参数。SVM 参数优化的蚁群系统根据目标函数值来更新信息素的浓度，目标函数中包含各蚂蚁所爬行过的全部节点信息以及所建模型的网络入侵检测率。待优化的变量为SVM的参数C和σ，程序终止时，从蚁群的最优化路径中得到相对应的SVM的参数C和σ值，原理如图1所示。
MACO算法优化SVM参数过程
1）设蚁群规模为m，每只蚂蚁k均有一维数组pathk。其中依次存放第k只蚂蚁经过n个节点的纵坐标，n为所优化参数的总有效位，这些纵坐标连接在一起组成该蚂蚁的爬行路径。
2）全部蚂蚁置于起始点O，循环次数N=0，时间计数器t=0，最大迭代次数为：Nmax，初始化节点上信息量△τ（xi，yi，j，0），并设Δτ（xi，yi，j）=0。
3）设置变量i=1。
4）根据式（7）计算蚂蚁的转移概率，在线段Li上，根据概率以赌轮算法选择每只蚂蚁下一个转移节点，并将蚂蚁转移到相应节点上，并将该节点的纵坐标存入pathk的第i个元素中。
5）i=i+1，如果i>n，跳转到步骤6），不然跳转到步骤4）继续爬行。
6）根据数组pathk计算该路径对应的C和σ。
7）将训练集平均分成k个子集S1，S2，…，Sk。
8）SVM根据获得的{C，σ}对训练集进行学习，计算kfold交叉验证的检测率。
9）以kfold交叉验证中最优检测率作为适应度值，检测率最高对应路径作为本次循环的最优路径。
10）N=N+1，t=t+n，更新每个节点上的信息浓度，pathk中的全部元素置零。
11）对蚂蚁进行高斯变异，打破蚁群严重聚集的情况（局部极值），以便探索新的路径，并将新的路径与原有路径进行比较，选出最优蚂蚁。
12）如果迭代次数大于最大迭代数，则表示算法结束，并计算输出最优路径对应的SVM参数C和σ值。
13）SVM根据最优C和σ值对训练集重新学习，建立最优的网络入侵检测模型。
网络入侵检测多分类器构建
网络入侵检测实质上一个多分类问题，但SVM只能求解两分类问题，必须通过组合策略构建网络入侵检测器，本文采用有向无环图将两分类的SVM组合在一起，构造的网络入侵检测器如图2所示。
在CPU 2.8 GHz，RAM 1 GB 环境上，采用Libsvm 2，98实现仿真实验。按照一般的做法，实验采用KDD CUP 99数据集中的10%的数据（约10万条记录）中随机抽取的的正常连接记录作为训练样本。MACO算法的参数为：蚂蚁数m=10，最大迭代次数Nmax=100，Q=100，α=2，β=4。
为了使MACO-SVM模型检测更具说服力，在相同条件下，采用遗传算法优化SVM（GA-SVM）和基本蚁群算优化SVM（ACO-SVM）作为对比实验。模型性能评价指标为：检测率、误报率和运行速度。检测率和误报率定义如下：
检测结果对比
GA、ACO、MACO算法对SVM参数选择的结果见表3。然后采用表3的参数建立相应的网络入侵检测模型，GASVM、ACOSVM和MACOSVM的检测结果见表3。从表3可知，相对于对比模型GASVM、ACOSVM，MACOSVM的中支持向量数更少，但检测结果最佳，这表明 MACO算法比GA、ACO在SVM参数优化方面具有更好的较强的全局搜索能力，获得更优的SVM参数C，σ，可以降低网络入侵检测误报率，有效提高了网络入侵检测率。
运行速度对比
为了检测模型的运行速度，采用模型对验证集的检测时间（秒，s）作为衡量指标，各模型的检测时间见图3。从图3可知，相对于GASVM、ACOSVM，MACOSVM检测速度大幅度提高，主要由于MACOSVM减少了支持向量点数量，收敛速度加快，满足了现代网络入侵检测系统的实时性要求。
蚁群优化算法应用研究 篇3
蚁群算法本质是一个复杂的智能搜索算法,具有较强的鲁棒性、良好的正反馈性能、优良的分布式计算机制、易于与其他优化算法相结合等特点。如今,该算法已经成为智能优化算法中的研究热点,对它的研究已经渗入到多种不同的应用领域。
1 基本蚁群算法原理
在自然界中,单个的蚂蚁个体行为极为简单,但由多个蚂蚁所组成的群体却成功地在搜寻食物等方面表现出复杂的行为。研究发现,蚂蚁总能找到巢穴与食源之间最短路径。蚁群算法就是借鉴和吸取现实世界中蚂蚁这种集体寻径行为来寻求函数的最优解。
蚂蚁个体之间通过一种称为信息素的物质进行信息传递,蚂蚁在移动过程中通过感知遗留在路径上的该种物质来指导自己的运动方向,并在自己经过的路径上留下该类物质。这样,大量蚂蚁所组成的群体便构成了一种信息正反馈,从而成功地实现了食物搜索,最短路径选择等行为。为了具体说明蚁群算法的原理,举出人工蚁群路径搜索的例子。
如图1所示,路径AB、ED、DH、HB长度分别为1,BC和BD长度分别为0.5。如图1(a)所示,在t=0时刻,有30只蚂蚁分别在A点和B点,蚂蚁单位时间内行程为1并留下1个浓度的信息素。如图1(b)所示,在t=1时刻,A点和E点的蚂蚁同时到达B点和E点,由于此前路径上没有信息素,它们随机选取路径,在DH、HB、BC、DC上将各有15只蚂蚁。如图1(c)所示,在t=2时刻,将有30只蚂蚁到达H点,而有15只蚂蚁分别到达B点和D点,在这段时间内,遗留在BC、CD上的信息素将是DH或是HB的两倍。而蚂蚁是根据遗留在路径上信息素的强弱来选择自己前进的方向,信息素强路径的将会吸引更多的蚂蚁,因此在后续的选择中,选择DC或是BC蚂蚁数量将是DH和HB的两倍,所以,20只蚂蚁选择BC,10只选择BH。如此反复进行下去,直至所有的蚂蚁都选择最短的路径BCD或是DCB。通过上面的例子,可以简单的说明蚁群算法主要的特点:
1)正反馈性。蚂蚁群体行为表现出正反馈过程,通过反馈机制的调整,可对系统的较最优解起到一个自增强的作用,从而使问题的解向着全局最优的方向演变,最终能有效的获得全局最优解。
2)并行性。蚁群算法是一个本质并行的算法,个体之间不断的进行信息的交流与传递,相互协作,有利于最优解的发现,从而在很大程度上减少了陷于局部最优的可能。
2 算法描述[1]
蚁群算法首次提出是用于解决TSP问题,因此我们就以求解n个城市的TSP问题为例来说明基本蚁群算法的求解过程。
TSP问题是一个典型的离散优化问题。其定义是:给定n个城市,TSP等价于寻找一条只经过各个城市一次且长度最短的闭合路径。令dij为城市i和j之间的距离,在欧式空间中,。。
假设蚁群数量为m,τkij(t)表示t时刻在ij上遗留的信息素。在初始时刻,各条路径上的信息素是相等的,τij(0)=C(C为常数),蚂蚁k(k=1,2,,m)在运动的过程中根据各条路径上遗留的信息素决定移动方向。pkij(t)表示t时刻蚂蚁k由城市i选择城市j的转移概率
allowedk={0,1,………,n-1}表示蚂蚁k下一步允许选择的城市,α和β分别反映了蚂蚁在运动的过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性,ηij为由城市i转移到城市j的期望程度,在TSP问题中取ηij=1/dij。建立禁忌表tabuF(F=1,2,……n)记录在t时刻蚂蚁已经走过的城市,不允许该蚂蚁在本次循环中再经过这些城市。当本次循环结束以后,禁忌表将被用来计算改蚂蚁当前所经过的路径长度。之后,禁忌表将被清空,用以准备下一次循环。经过n个时刻,蚂蚁完成一次循环,各条路径上的信息素根据下式调整:
用△τkij表示第k只蚂蚁在本次循环中留在路上的信息素,则,ρ为信息素残留系数,1-ρ表示信息素的消逝程度。
根据具体的算法的不同,△τij、△kij和pkij(t)表达形式也有所不同,可根据具体问题而定。M.Dorigo曾给出三种不同的模型,分别是蚁周系统、蚁量系统、蚁密系统。经过一系列标准测试问题的测试,蚁周系统的性能要优于其他两种算法,故常用的就是蚁周系统更新模式:
其中,Lk为第k只蚂蚁在本次循环中所走的路径长度。
3 蚁群算法的改进[2,3,4,5,6,7]
基本蚁群算法具有很强的全局搜索能力,但是也存在一些问题,例如:搜索时间过长,执行过程中容易出现停滞现象,当问题规模较大时存在陷入局部最优解的可能。因此,很多学者对蚁群算法进行了改进。
3.1 基于优化排序的蚂蚁系统
蚁群算法和遗传算法一样,都有一个共同的缺陷就是容易陷入局部最优解。当路径差别不大,解元素之间的差异减少,致使选择概率的差异也随之减少,从而阻止了对最优解进一步的搜索。借用遗传算法中适应度排序法,将每次循环以后生成的路径进行排序,依照序列的顺序进行信息素加权更新。
3.2 最大最小蚂蚁系统
为了防止过早的算法停滞现象,德国学者T.Stuetzle和H.Hoos提出了最大最小蚂蚁系统(Max-Min Ant System,MMAS),其特点是在算法中引入了信息素最大值和最小值限制。当某条路径上的信息素大于上限,就强制为上限值;小于则为下限值,通过设定信息素的上下限。这样一方面避免了某条路径上的信息素远大于其他路径的信息素浓度,从而有效的降低了过早停滞的可能;另一方面,不会因为某条路径的信息素浓度过低而丧失发现新路径的可能。
有实验表明,MMAS算法较传统的蚁群算法相比,在寻优的有效性方面和防止算法的过早停滞方面具有更好的效果,但是,仅采用最大最小信息素的限制还不足在较长的时间里持久消除停滞现象,因此,可以对其进行进一步改进,如在算法中引入信息素平滑机制等。
3.3 自适应蚁群算法
为了既能保持蚁群算法全局搜索能力,又能提高搜索速度,王颖等人提出了自适应蚁群算法。该算法能在进行过程中自适应的改变ρ值,ρ的初始值取ρ(t0),当算法求得的最优解在固定的N次循环内没有明显得改进时候,对ρ值作出适当的调整。
式中,ρmin为ρ的最小值,可以防止ρ过小而降低算法的全局搜索能力。通过多种实验表明,该算法比一般的算法具有更好的收敛速度和稳定性,更适合于求解大规模的TSP。
4 结论
蚁群算法是一种新的仿生进化计算方法,已经在TSP、图与组合优化、Job-shop等问题上取得了成功的应用,并具有其独特的优越性。但由于蚁群算法还是一种新型的优化算法,其研究刚刚开始,还没像遗传算法和模拟退火算法等那样形成系统的分析方法和坚实的数学基础,因此算法中一些参数的确定目前还没理论上的依据,以公布的实验结果都是针对特定问题而言。
总之,蚁群算法作为一种新兴的研究领域,将会得到不断深入的研究,其模型将会更加丰富,也将相应的得到更加广泛的应用。
摘要：蚁群算法是一种新型的进化算法,在离散函数和连续函数优化中都有着广泛的应用前景。该文简要对算法的研究现状做以概述,介绍该算法的基本原理、算法的模型和若干改进算法。
关键词：蚁群算法,基本原理,改进算法
参考文献
[1]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
[2]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245.
[3]段海滨,王道波.蚁群算法的全局收敛性研究及改进[J].系统工程与电子技术,2004,26(10).
[4]邵晓巍,邵长胜,赵长安.利用信息量留存的蚁群遗传算法[J].控制与决策,2004,19(10).
[5]段海滨,王道波.一种快速全局优化的改进蚁群算法及仿真[J].信息与控制,2004,33(2).
[6]张纪会,徐心和.一种新的进化算法——蚁群算法[J].系统工程理论与实践,1999(3).
改进蚁群算法及参数优化研究 篇4
1问题提出
本节分析蚁群算法优缺点,探讨不足之原因,蚁群算法利用特有的正反馈特性,使得算法具有较高的自组织能力。然后系统内部成员之间分布式运行,成为一个统一体。正反馈机制使虽然能强化较好解,但却使算法出现停滞现象,即只取得了局部最优解就停止,而未达到全局最优解。
易早熟,求解问题解的时候过早的陷入局部最优解。正反馈的存在,算法运行到一定程度,信息素的贫富加剧,使得算法在局部区域摇摆,不向其他方向搜索,全局搜索能力降低。全局收敛速度慢,随机性发挥着较大作用。算法的效果和参数设置敏感,算法参数相互影响,在设置相关系数的时候要注意相互的耦合关系。针对算法上面这些不足,本文对算法本身提出改进,同时结合具体的优化问题,结合微粒子群算法对算法主要参数的进行调优。
2优化蚁群算法
2.1引入“赏罚”机制
蚂蚁个体依据信息素浓度进行路径选择。算法的正反馈性,无论搜索到的解如何,所有被搜索到的路径上的信息素都会在一定程度上得到增强,所以存在不公平竞争。本文引入“赏罚”机制,即奖励表现好的路径,惩罚不好的路径。每当蚂蚁所有任务点完成一次遍历后的路径与之前的最优路径相比较,若此路径更优则在该路径上增加一定浓度的信息素,该路径暂时最优,以增加下次遍历时选择该路径的概率;反之,若路径不是最优则要在该路径上减少一定浓度的信息素,以减小下次被选中的概率。
2.2最大最小蚁群系统
2.3信息素更新策略的改进
2.3.1信息素全局更新策略的改进
在每次迭代构建解空间后,记录所有蚂蚁构建的可行解的路径长度,然后与当前最优解的路径长度进行比较。若长度小于当前最优解的长度,则该路径上的蚂蚁在其经过的路径上释放相应的信息素,反之,不释放信息素。这样保持了算法的朝向是持续优化,而又防止算法过早地陷入局部最优解。节点Ci到节点Cj之间路径上的信息素量更新公式:
2.3.2信息素局部更新策略的改进
依据前文讲述的赏罚机制,蚂蚁在构建解的过程中对经过的路径上的信息素进行局部更新,去除掉该路径上的一些信息素,以有利于后面的蚂蚁探索其他路径解,提高其探索的概率,避免进入停滞或者局部最优解。对于某蚂蚁个体,当其经过一条路径(i,j)时,立即对此路径上的信息素进行更新。
2.4引入状态转移控制参数
2.5小结
在最大最小蚁群系统基础之上引入“赏罚”机制,然后从全局和局部优化算法信息素浓度的更新策略,加入不同状态变化概率对算法进行优化和改进。
3调优算法参数
算法关键参数:浓度消逝速度ρ、信息素因子φ、启发因子γ、蚂蚁的数量规模M以及信息素总量Q,参数相互耦合,需要结合具体问题,对其进行调优。本节采用公交调度优化问题,以某市27路的实际数据,利用微粒子群算法调优关键参数。信息素因子启发因子
3.1粒子群优化
本文所选用调优参数的算法是粒子群(PSO)算法。作为基于种群的随机全局优化算法,其每一次的迭代过程中,微粒个体i通过其自己所构建到的个体最优解Pi_best和目前整个种群范围内找到的全局最优解Gbest,按式(3-1)来进行更新迭代处理。其中,vi表示微粒个体的速度向量;Xi表示微粒现在的位置;学习因子C1、C2是常数;r1,r2是在[0,1]上均匀分布的随机数;w是惯性权重。
3.2参数调优实验
将目标参数组合作为优化对象(微粒的位置),在每轮迭代过程中,使用微粒的现在所处的位置来运行改进的蚁群算法,求解标准优化问题,同时结合适应度评价函数对刚刚求解的性能进行评价,最终指引各微粒朝适应值高的方向行进。流程如下:
图1:各时段客流统计分布
(1)在一定范围内选取C1、C2和权重w的值,同时随机选取各微粒的初始位置和速度;
(2)利用每个微粒个体所在的位置信息执行蚁群优化算法,进行一次求解,同时依据适应值评价函数对刚刚求解结果进行评价分析,从而获取各个微粒个体的适应度值;
(3)针对各微粒个体,通过对其当前位置适应度值和Pi_best的适应值进行比较,若较优,那么就需要用当前位置来更新个体最优解Pi_best;
(4)用每个微粒个体最优解Pi_best的适应值与全局最优解Gbest的适应值比较,若较优,则更新全局最优解Gbest;
(5)然后依据式(5)更新每个微粒个体的速度和位置;
(6)对终止条件进行判断,若满足条件,就输出全局最优解Gbest,否则跳转步骤2。
依据上文提出的参数优化算法仿真过程,蚁群算法采用本文改进的算法,参数ρ、φ、γ、M、Q为调优对象,其参数取值范围如表1所示。经过对比分析,总结出适合该公交调度模型的优化参数组合,最终得到算法的调优关键参数见表2。
4公交优化调度的仿真实例分析
4.1优化蚁群的调度求解步骤
前文我们已经分别对算法本身和关键参数进行了改进和调优,本章将利用经典的公交调度优化问题,来验证其有效性。
为了能够根据实际的客流数据,更好地解决公交调度问题,从而满足乘客的需求,将全天运营时间进一步细分为早平峰[6:00,7:00]、早高峰[7:00,9:00]、上平峰[9:00,11:30]、午高峰[11:30,14:00]、午平峰[14:00,16:30]、晚高峰[16:30,19:00]、晚低峰[19:00,21:30]七个时段优化。本文实证分析以某市27路公交,通过调整优化在各个时段内公交车的发车间隔,兼顾公交公司盈利和公众满意,以此来实现对调度问题的优化。该趟公交线路拥有33个站点,图1是27路某工作日全天各时段内客流统计分布图。如图2所示为某工作日一天运营时段内的客流。
4.2算法仿真求解比较
从表4说明了本文优化算法的合理性,公交公司如果将全天的运营时段划分的越多,虽然公众坐车会很方便,但是那么势必会增加车辆的发车次数,从而增加了其运营成本。对图3、表4进行分析,可以看出当如果将把全天的运营时间划分为七个时段,可以使得发车量更符合公众出行的需求,当客流偏少时,就通过提高公交发车间隔,来降低公交的发车次数,这样就能够满足公众的需求,保证服务水平,同时兼顾公交公司的成本花费,做到了共赢。
5结论
本文首先对算法本身进行优化调整,对信息素变更机制进行完善,引入“赏罚”机制,并借鉴改进的最大最小蚁群系统,将信息素的浓度限制在一定范围内,避免轻易出现停滞状态,以及对节点的选择进行调整等等。然后针对参数取值问题,利用微粒子群优化算法对组合参数ρ、φ、γ、M和Q进行调优。最后利用优化的算法和调优参数对公交调度优化问题进行求解,仿真对比结果表明本文改进的蚁群搜索速度得到加快,搜索效率得到提高。说明本文的改进能有效地改善蚁群算法的性能,是可行的。
参考文献
[1]Tropical cyclone spiral band extraction and center locating by binary ant colony optimization[J].Science China(Earth Sciences),2012,02:332-346.
[2]A Multi-pipe Path Planning by Modified Ant Colony Optimization[J].Computer Aided Drafting,Design and Manufacturing,2011,01:1-7.
[3]Munan Li.Efficiency improvement of ant colony optimization in solving the moderate LTSP[J].Journal of Systems Engineering and Electronics,2015,06:1301-1309.
[4]赵航.基于机会约束的公交调度研究[J].数学的实践与认识,2005,35.
[5]张聪.基于并行计算的公交车调度优化研究[D].合肥:安徽理工大学,2014.
基于改进蚁群算法的无功优化研究 篇5
1 无功优化模型
采取考虑有功网损最小的无功优化模型, 目标函数如下:
式中:n为系统的支路数;Gk为线路的电导;V为电压的幅值;θ为对应的相角。
等式约束条件:
式中:i∈N;Pi、Qi分别为注入节点i的有功功率和无功功率;PGi、PLi是发电机节点和负荷节点的有功功率;QGi、QLi是发电机节点和负荷节点的无功功率;QCi是无功补偿的容量;V是节点电压;Gij、Bij是节点i、j之间的电导和电纳。
不等式约束条件:
控制变量的约束方程为
式中:NG、SC、ST分别为发电机台数、无功补偿节点数和变压器台数。
状态变量的约束方程为
式中:NG、ND分别为发电机台数、负荷节点数。
2 蚁群算法及其改进方案
2.1 蚁群算法模型
蚁群优化算法最早应用于求解著名的旅行商问题, 目前该算法已经应用于多个研究领域, 如函数优化、网络路由和系统辨识等, 具有广阔的发展前景[1,2,3]。
蚂蚁k在移动过程中通过可选路径上信息素的多少来判断转移方向, 蚂蚁k在城市i选择城市j的状态转移概率定义为
式中:pkij (t) 表示t时刻蚂蚁k在城市i选择下一城市j的转移概率;τij (t) 表示t时刻残留在城市i、j连线上的信息素量;ηij (t) 用来表示启发函数;α和β分别反映蚂蚁在移动过程中所积累的信息素和启发信息在路径选择策略上的相对重要性。
蚂蚁k的搜索路径就是TSP问题的一个可行解, 在经过n个城市的遍历后, 蚂蚁就完成了一次搜索, 各段路径上的信息素量根据以下公式进行调整:
式中:ρ表示信息素的挥发系数; (1-ρ) 则表示信息素的残留因子。
对于Δτkij (t) 的提出了3种不同的实现方法, 也是目前常用的3种蚂蚁系统模型[4]:
1) ant-cycle system模型:
2) ant-density system模型:
3) ant-quantity system模型:
式中:Q是常数, 表示的是蚂蚁进行搜索一周所释放的信息素总量;Lk表示第k只蚂蚁在本次循环中所走路径的总长度。
对于计算Δτkij (t) 的3个模型, 文献[5]的实验证明了蚁周模型要比其余2种模型优秀, 蚁周模型的更新策略是当所有蚂蚁每完成一次循环才进行信息素的全局调整。
2.2 蚁群算法步骤
1) 初始化:将m只蚂蚁随机分布在n个城市并初始化信息素及蚁群算法参数等。
2) 构造可行解:对每只蚂蚁用状态转移概率在可供选择城市中选择要到达的下一个城市, 并将所选城市放入禁忌表中;当蚂蚁遍历完所有城市, 计算所选路径长度, 所选路径即为所求问题的一个可行解。
3) 信息素的更新:当所有蚂蚁都完成一次搜索之后, 通过信息素更新规则对各边上的信息素进行更新;比较所有的遍历长度, 找出最短路径;将禁忌表清空, 返回到上一步。
4) 不断进行迭代直至满足最大迭代次数或满足所求问题的精度要求为止。
2.3 蚁群算法的改进
2.3.1 参数改进
定义一个自适应系数μ, 令μ=Lwa/Lk, 针对公式 (4) , 根据本文提出的改进方法调整为
这样做可以增强短路径的信息素强度, 减弱长路径的信息素强度, 提高收敛速度, 从而缩短获得最优解的时间。
2.3.2 应用微分进化算法改进
微分进化 (differential evolution, DE) 是一种高效率的智能优化计算方法。DE算法来自遗传算法, 是一种极具潜力的跨学科优化算法[6]。
在蚁群算法中引入发散项可以增加随机扰动来帮助算法跳出局部最优。
式中:F为属于[0, 1]的微分进化发散因子;p, q∈{1, 2, …, m}。因此信息素更新公式变为
通过加入微分进化算法的发散项, 对蚁群算法信息素的更新引入了一个微小扰动量, 使得随机性增加, 有利于减小算法过早陷入局部最优的可能性。
3 基于改进蚁群算法的无功优化
改进算法在无功优化中的流程如图1所示。改进算法在无功优化中的具体步骤为
1) 对每一个支路和节点的原始数据进行读取。
2) 初始化, 将系统的控制变量进行离散化处理, 在可行域里随机产生m个个体, 然后进行参数的设置, 形成初始蚁群。
3) 依据公式 (1) 让蚁群k进行搜索, 并且记录每一个控制变量的大小, 从而依据节点和支路信息来计算潮流、网损和适应值。
4) 进行适应值的比对, 若Xk比当前最优解Xbest更优, 则更新最优解Xbest;否则就向当前最优解的方向前进一步, 然后再根据节点和支路信息计算潮流、网损和适应值。
5) 当一次迭代完成后根据式 (2) 、式 (3) 、式 (5) 进行信息素的更新。
6) 满足迭代次数或计算精度, 计算出最优潮流和最小网损, 然后输出最优潮流、最优解。否则回转步骤3) 继续进行搜索。
4 电力系统算例分析
4.1 IEEE-30节点系统数据
本文所采用算例系统的参数均采用标幺值表示, 电压相角单位是弧度, 基准功率为100 MVA, 所用的优化计算程序采用MATLAB7.0编程实现。
对于标准测试系统IEEE-30节点系统[7]的参数如下:
6台发电机 (其中平衡节点号为1, PV节点号为2、5、8、11、13) ;有4台可调变压器分布在支路 (6-9、6-10、4-12、27-28) 上;有2台并联无功补偿装置补偿点 (节点10、24) ;21条负荷母线及41条支路。IEEE-30节点系统结构如图2所示, IEEE-30节点系统控制变量约束条件如表1所示, IEEE-30节点系统状态变量约束条件如表2所示。功率数据都是以100 MVA为基准功率的标幺值, IEEE-30系统的初始网损为0.0694。
4.2 计算结果分析
除平衡节点外, 有5个发电机、4个可调变压器、2个无功补偿节点, 所以控制变量总数为11个。通过改进蚁群算法来确定最佳控制方案。
参数设置:蚂蚁数目m=50, 信息素挥发系数ρ=0.3, 信息素启发因子α=1, 期望值启发因子β=2, 初始信息素为0.1, 总信息量Q=100;移动步长STEP为0.005;F为属于[0, 1]的微分进化发散因子;p, q∈{1, 2, …, m};算法终止条件为相邻的两次最优解的差别小于10-6或达到最大迭代次数200次。
为了验证本文所用算法的有效性, 通过50次的计算结果来取平均值。将改进蚁群算法与现今常用的遗传算法[8]、蚁群算法、多智能体粒子群算法[9]、免疫蚁群算法[10]的优化结果进行比较, 结果如表3—表6所示。
由表3结果可知, 改进蚁群算法比遗传算法、蚁群算法、多智能体粒子群算法、免疫蚁群算法的网络损耗更小, 其计算精度也更高, 全局寻优能力更强, 达到了降低有功网损的目的。
由表4—表6结果可以看出, 发电机的无功处出力、变压器变比和无功补偿容量均在允许范围内, 可以正常运行。
对IEEE-30节点系统采用遗传算法、蚁群算法和本文提出的改进蚁群算法分别进行50次优化计算, 有功网损最小值的统计分布如图3所示。
从图3可以看出, 对电力系统进行无功优化, 采用遗传算法进行的优化计算表现出稳定性较差的特点, 而改进蚁群算法 (IACO) 无论是在算法的初期还是后期, 收敛情况都要强于蚁群算法 (ACO) 。通过改进方案使得IACO算法在收敛速度和寻优结果上都有所提高, 可见IACO算法的稳定性及搜索全局最优解的能力要比遗传算法和蚁群算法优秀很多。
5 结语
以发电机端电压、变压器变比和无功补偿容量作为控制变量, 以网损最小作为目标函数, 建立无功优化数学模型。在分析大量智能算法优缺点的基础上, 选择蚁群算法作为优化算法, 并针对其缺点进行了相应改进。将电压稳定引入无功优化形成多目标无功优化, 并将多目标转化为了单目标无功优化问题, 最后采用IEEE-30节点系统作为测试系统进行优化计算, 验证了本文所采用算法的可行性和合理性。
摘要：建立了网损最小的数学模型, 对蚁群算法的缺陷进行改进, 包括对蚁群搜索到的路径进行排序, 自适应调节路径上释放的信息素。同时又在信息素更新机制里引入微分进化算法的发散项, 提高算法的收敛速度和全局寻优能力。通过IEEE-30节点的仿真计算, 验证了改进蚁群算法在电力系统无功优化领域的可行性和有效性。
关键词：电力系统,无功优化,蚁群算法,改进蚁群算法
参考文献
[1]MARTINEZ C, CASTILLO O, MONTIEL O.Comparison between ant colony and genetic algorithms for fuzzy system optimization[J].Soft Computing for Hybrid Intelligent Systems, 2008, 165 (10) :71-86.
[2]陈敬宁, 何桂贤.带杂交变异因子的自适应蚁群算法在电力系统无功优化中的应用[J].继电器, 2003, 31 (11) :36-39.
[3]胡小兵, 黄席樾.基于混合行为蚁群算法的研究[J].控制与决策, 2005, 20 (001) :69-72.
[4]DORIGO M, MANIEZZO V, COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems, Man, and Cybernetics-Part B, 2002, 26 (1) :29-41.
[5]STUTZLE T, HOOS H.MAX-MIN ant system[J].Future Generation Computer Systems, 2000, 16 (8) :889-914.
[6]刘自发, 闫景信, 张建华, 等.基于改进微分进化算法的电力系统无功优化[J].电网技术, 2007, 31 (18) :68-72.
[7]寸巧萍.基于量子遗传算法的电力系统无功优化[D].成都:西南交通大学, 2004.
[8]LAI L L, 杨以涵.遗传算法在电力系统无功优化中的应用[J].中国电机工程学报, 1995, 15 (5) :347-353.
[9]赵波, 曹一家.电力系统无功优化的多智能体粒子群优化算法[J].中国电机工程学报, 2005, 25 (5) :1-7.
一种蚁群算法疏散模型优化的方法 篇6
最短路径算法是智能疏散系统中疏散模型的核心算法,目前常见的最短路径算法有Dijkstra算法、模拟退火算法、遗传算法等。这些算法 运算效率 低,计算过程 复杂,花费时间长。意大利学者Dorigo等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径的行为,提出的一种基于种群启发式仿生进化系统的蚁群算法,具有分布式计算、信息正反馈和启发式搜索的特征,有较强的鲁棒性、优良的分布式计算机制等优点。
笔者模拟楼层拓扑结构,建立楼层疏散节点地图,用蚁群算法计算出各个节点到出口的最短路径。提出一种最短最大的节点预处理方法,对节点进行排序,优化蚁群算法处理节点的顺序,减少疏散模型求解最短路径的时间,通过实验对比表明该方法的有效性。
1疏散模型分析
用蚁群算法求出某个节点到安全出口的最短路径。 首先建立有多个安全出口的楼层拓扑节点的蚁群算法疏散模型,其次提出最短最大的方法对模型进行优化。
1.1楼层拓扑结构构建
模拟某一楼层的拓扑结构,在中间节点、拐弯点和安全出口等处建立若干节点,将各个节点依次编号并设置节点间的连通关系。节点号集为V={1,2,…,n},连通关系为边集E={e1,e2,…,el},建立节点 间关系图G= (V,E),设置安全出口节点,节点以二维坐标存储。
1.2多出口的蚁群算法
蚁群算法是启发式算法的局部更新的自适应算法, 算法迭代的次数和循环次数越多,计算所得的最短路径越准确。
假设禁忌表Tabuk(k=1,2,…,n)记录蚂蚁k当前所走过的节点,蚂蚁数量为m;α、β分别表示蚂蚁积累的信息及启发式因子在选择路径中所起作用的程度;Tauij(t)表示t时刻在节点i、j之间残留的信息量;启发式因子ηij(t)=1/dij,dij表示节点i和j之间的权值;Pikj(t)表示在t时刻蚂蚁k由位置i转移到位置j的概率,如式 (1)所示。
式中:alowedk={0,1,2,…,n-1}-Tabuk为蚂蚁k允许选择的节点;Taui,j(t),ηij(t)与Pikj成正比。
蚂蚁k通过Pikj(t)来确定下一步节点,如果仅依据转移概率确定下一步的节点,会有较快的收敛速度,可能导致局部最优的产生。此时,用0~1的随机数r,如果r< Pikj(t),则选择该节点,扩大搜索范围,较好地避免了局部最优化。集合Tabuk随着进化过程作动态调整,已经走过的节点放在Tabuk中,不再作为 下一步判 断的节点。 每只蚂蚁k在寻找到出口或达到最大循环次数时结束循环,同时把路径保存起来。在某代循环结束时找到到达出口的最短路径,通过式(2)更新该路径上的信息素。
式中:ρ为信息素蒸发的系数;ΔTauij为每代循环中到达出口的蚂蚁在节点i,j上的信息量的增量,当第k只蚂蚁在某次循环中得到最短的路径,用Ant-cycle模型策略更新最短路径信息素,如式(3)所示。
式中:Q为常数,其值为每次释放信息素的总量;Tauikj为第k只蚂蚁在一次循环中到达出口留在路径i、j上的信息量;Lk为第k只蚂蚁在本次循环所走路径的长度。
1.3疏散模型的优化
蚁群算法的时间复杂度较高,智能疏散模型的运算时间主要由蚁群算法的运算时间决定。疏散模型调用蚁群算法每次只能求出若干个节点到出口的最短路径,需要多次调用蚁群算法,又因蚁群算法比较成熟,疏散模型优化的关键是减少蚁群算法的调用次数。最短最大方法是按照到出口最远的距离对节点进行排序,增加蚁群算法每次经过节点的数量,经过的节点不再进行计算,以达到减少蚁群算法计算的次数的目的。
在发生火灾的应急条件下,将楼层的拓扑结构图中节点的坐标值、连通关系和出口的标号值作为数据用于蚁群算法计算节点到出口的最短路径。疏散模型的流程图如图1所示。
2疏散模型实验分析
在如图2的楼层中设置24个节点V={1,2,…,24},连通关系为边集E={e1,e2,…,e32},节点号2、23是安全出口,左右节点连通权值是10,上下连通权值为15,安全出口是2、23,如图2所示。
通过多次仿真计算设置参数值为α=0.1,β=0.1,ρ =0.1,Q=1,初始化信息素矩阵值Tauij(0)=c=1,m= 100,循环次数Nc=100,实验平台是HPZ820工作站。
假设节点3和4之间发生火灾,收到火灾报警信息, 设置节点3和4之间距离为无穷大。在相同的实验条件下,实验1是从节点值1开始计算,未预处理节点的某次运算得到的疏散路径顺序,如表1所示。实验2用最小最大方法预处理,某次运算得到的疏散路径顺序,见表2所示。
两个实验得到了相同的疏散路径,如图3所示。
由图3可知,两次实验结果得出的指示路径是相同的,其中表1经过12次运算,所有节点运算结束,表2运算9次即可,说明经过节点预处理后,每次蚁群算法得到最短路径的节点数增加,疏散模型调用蚁群算法的次数较少。对实验1和2分别进行50次实验,进行优化前和优化后蚁群执行次数和疏散模型运算时间进行对比,如图4、图5所示。
在重复实验时,虽然实验1和实验2的结果有时不完全相同,但得到的疏散路径是等效的,即各个节点到出口的疏散路径长度相等。由图4和图5可知,优化后疏散模型调用蚁群算法的次数减少,运算时间减少。通过计算可知,调用的次数减少了18.53%,运算时间减少了10.52%。此外,改变图2中楼层的拓扑结构后对优化前后进行50次实验对比,结果同样表明,优化后调用蚁群算法次数和运行时间减少。
3结论
通过蚁群算法建立疏散模型,在火灾应急的条件下计算各个节点到出口的最短路径。根据节点的坐标计算节点到出口的欧式距离,提出最小最大算法对节点的进行排序,优化蚁群算法调用节点的顺序,减少了蚁群算法的运算次数,缩短了运 行的时间,提高了疏 散模型的 效率。未来可以考虑烟气的减光性、毒害性、高温等因素, 将楼道的长度改为当量长度,随着楼道环境不断的变化更新其通行能力。
摘要：针对智能疏散系统中运算时间复杂度高的问题,提出一种预处理方法优化疏散模型。建立楼层蚁群算法疏散模型,用该方法对拓扑节点进行排序,使得模型每次调用蚁群算法求最短疏散路径时尽可能地经过多个节点,减少调用蚁群算法的次数,缩短模型的运算时间,通过对优化前后的实验对比表明该方法的有效性。
多目标优化的生长竞争蚁群算法 篇7
多目标优化问题的目标往往是互相冲突的, 能满足所有约束条件且使所有目标函数都能达到全局最优的解往往不存在, 而只是存在一组Pareto最优解或非劣解。近年来, 智能优化方法在解决多目标优化问题已取得一些成果。很多学者使用遗传算法[1,2,3]、 粒子群算法[4]、 蚁群算法[5,6]等对求解多目标问题的Pareto最优解进行了有益的探讨。
蚁群算法是一种源于大自然生物世界的仿生类算法[7]。蚁群算法已在一系列困难的组合优化问题求解中已取得了成效。基于植物生长向光性和竞争性机理, 本文提出了一种求解多目标连续系统优化问题的生长竞争蚁群算法及其数学描述, 并对部分典型多目标连续函数优化问题进行了测试和验证。
2 多目标优化的生长竞争蚁群算法
2.1 多目标优化
在实际应用领域中, 存在大量的多目标优化问题。如何在多个目标中寻找折中最优解是一个比较复杂的问题。多目标优化的数学描述如下:
其中, F (x) 为多目标优化问题的目标函数, 其分量fi (x) , i=1, 2, …, k均越小越优, 对x*∈X, 若在X中不存在x使fi (x) ≤fi (x*) , i=1, 2, …, k, 且至少对一个i严格不等式成立, 则称x*为多目标优化问题的Pareto最优解或非劣解。
常用的优化技术本身并不能直接处理多目标优化问题, 往往将其转化为比较容易处理的单目标问题, 典型的方法有:主要目标法、线性加权法、平均和加权法、理想点法、乘除法和几何平均法等[8]。这些优化技术一般每次都只得到Pareto解集中的一个, 或是相对于Pareto最优解的一个折中解。
2.2 生长竞争机制
自然界中的竞争是在一定竞争规则下, 在竞争者的实力、竞争者和环境间的关系、竞争者之间的实力的差距等多种因素的作用下, 经过多次竞争, 使不同的竞争者分别占有一定的资源而达到一种新的竞争状态, 只要新的竞争状态优于旧竞争状态, 就会达到优化的目的。
生物学实验已经证明, 植物生长过程中, 当植物有1个以上的节时, 具体哪个节能生长出新枝取决于其形态素浓度, 形态素浓度大的节获得长出新枝的机会比浓度小的节大[9]。而形态素的浓度取决于对光资源的获取。在此我们引入如下的定义:
植物的n个节点为n个竞争者集合, m个可能长出新枝的机会构成m个资源集合, 第i个节点的状态s (i) , 即该生长点的生长素浓度。
n个节点的竞争力函数pk (i) 定义为:
其中, snew (i) 为第i个节点长出新枝后的生长素浓度。pk (i) 的含义是在当前状态下, 第i个竞争者占用资源后, 获得生长素的能力, 若pk (i) <rank (1) , 则该节点退化, 无竞争能力, 将不可能长出新枝。
2.3 多目标生长竞争蚁群算法的描述
一个孤立的蚂蚁随机移动时, 能检测到其它同伴所释放的信息素, 并沿着该路线移动, 同时又释放自身的信息素, 从而增强了该路线上的信息素数量。蚁群个体之间就是通过这种信息的交流达到搜索食物的目的。
一个典型的带约束函数优化问题可以使用常规的罚函数法将所有约束方程转入目标函数中。这样, 在算法的具体搜索过程中就不必考虑约束是否满足的问题, 而直接考虑目标函数优化。
对于连续函数fi (x1, x2, …, xn) , i=1, 2, …, k, 其定义域集合为n维欧氏空间, 可将其的定义区域等分作为搜索区域, 蚂蚁在搜索区域内按基于生长竞争机制进行局部优化, 并按不同情况释放不同的信息素, 而这些信息素可以被整个定义域空间中其它蚂蚁所感知。
定义1 多目标优化生长竞争机制
(1) 破土而出的茎杆有n个节点可能长出m个新枝;
(2) 每个生长点的生长素浓度s (i) = (f1 (x (i) ) , f2 (x (i) ) , …, fk (x (i) ) ) ;snew (i) = (fnew1 (x (i) ) , fnew2 (x (i) ) , …, fnewk (x (i) ) ) 为第i个节点长出新枝后的生长素浓度;
(3) 对于多目标问题, 为了保持pk (i) 大于等于零, 要求每个目标项的差值大于零。为此对竞争力函数pk (i) 作适当修改, 具体如下:
(4) 若pk (i) >rank (1) , 共有k个。 若k>m, 按pk (i) 从大到小取前m个节点长出新枝。 若k<m, 取k个节点长出新枝;
(5) 若k=0或新枝越出规定的范围, 生长结束。
定义2 信息素释放规则
(1) 初试化区域初试最佳值Ziopt和全局初试最佳值Zopt
(2) 选取区域Ni按生长竞争机制获得最好解Zi,
①若Zi≥Ziopt, 不释放信息素;
②若Zi<Ziopt, 替换区域的最佳值;
若Zi<Zopt, 替换空间最优值, 释放信息素Q;若Zi与Zopt无法比较, 将其作为新的最优值保存, 释放信息素Q;若Zi≥Zopt, 释放信息素Q/2;
③若Zi与Ziopt无法比较
若Zi<Zopt, 替换空间最优值, 释放信息素Q;若Zi 与Zopt无法比较, 将其作为新的最优值保存, 释放信息素Q;若Zi≥Zopt, 释放信息素Q/2。
蚂蚁的寻优方向与空间中其他区域的信息素浓度以及它们之间的目标函数的平均差异程度有关。
定义3 蚂蚁的邻域的转移概率定义为
其中, τj为区域j的信息素强度, ηij为为目标函数平均差异程度, 即为:
α为邻域吸引强度的相对重要性 (α≥0) ;β为目标函数平均差异的相对重要性 (β≥0) 。
定义4 信息素强度更新方程为:
这里, Δτkj的值为第k个蚂蚁在区域Nj每迭代一次所释放的信息素, ρ体现强度的持久性。
算法主要流程:
随着蚂蚁在区域内的信息素的释放, 依据蚂蚁的转移概率, 蚂蚁将集中于非劣解较多的区域, 获取更多的非劣解;同时蚂蚁在不同的区域内搜索, 使得所得的解有一定的分布度。
由算法实现的描述可知, 生长竞争机制区域搜索的时间和空间复杂度和新枝的长度及新枝中节点数有关, 实际计算过程中新枝的长度一般取区域半径的1/100～1/10, 而对应新枝中节点数为10～100。搜索过程超出区域, 则停止。因此, 整个算法的时间和空间复杂度主要和区域划分数、区域中的蚂蚁个数及非劣解的数量有关。假设区域的数量为k, 区域中的蚂蚁也为k, 非劣解的数量为s, nc为运算迭代次数, 则算法整个过程的时间复杂度为O (nck2s) , 空间复杂度为O (ks) 。应用上, 这个复杂度是可接受的。
3 实例验证
为了验证方法的有效性, 本文采用了如表1所示的3组测试函数[1,5]来测试算法的性能。在每个测试实例中, 以图形化的方式给出了此方法生成的Pareto前沿, 并对解的分布性能及散布范围[10]进行比较。
定义5 间距评估
其中:
n为算法获得的Pareto前沿上向量的个数, 当所获得的解越接近均匀散布时, 间距S的值越小。
定义6 最大散布范围评估
其定义了两个极值解的距离, 其值越大, 表明算法的解散布范围越广。
算法用MATLAB编程实现并进行了计算测试。测试中所用的参数为α=β=1, ρ=0. 7, Q=1。区域分割数为10, 则每个实例为100个区域。生长竞争机制中n=10, m=1。
表2给出第1组测试函数迭代200次后的求得的间距, 所有解绘制的Pareto曲线如图2;表3给出文献[1]和文献[6]中算法的间距。两者比较本文算法好于其它算法。
表4给出编号2测试函数迭代10次后的求解结果, 图3给出第5次所得的Pareto曲线图;表5给出文献[5]、文献[6]的结果。两者比较本文算法其结果优于文献[5]、文献[6]的结果, 很好地逼近了Pareto前沿。
表6给出编号3测试函数迭代100次后的求解结果, 第2次求得的解绘制的Pareto曲线如图4; 表7给出文献[5]、文献[6]的结果。本文算法其结果优于文献[5]、文献[6]的结果。
4 结束语
本文基于生长竞争机制, 提出了用于求解多目标优化的生长竞争蚁群算法。通过将生长竞争与信息素释放相结合, 引导蚂蚁的行走方向。通过算例求解与测试, 效果良好, 可以很好地逼近Pareto前沿, 同时有一定的散布广度。算法的收敛性的理论分析是今后研究的重点。
摘要：提出一种求解多目标优化的生长竞争蚁群算法。该方法将生长竞争规则引入蚁群算法, 给出了在连续空间多目标函数优化的算法描述, 定义了生长竞争规则及蚁群邻域的转移概率, 并提出了实现算法的具体步骤。算法在MATLAB环境下, 对一些典型的测试函数进行了求解和验证, 实验结果表明该方法具有向真实的Pareto前沿逼近的效果, 是一种求解多目标优化的有效方法。
关键词：蚁群算法,生长竞争,多目标优化
参考文献
[1]Coello C A, et al.Multiobjective optimization usinga micro-genetic algorithm[C]//Proceedings of theGenetic and Evolutionary Computation Conference (GECCO2001) .San Francisco:Morgan KaufmannPublishers, 2001:274~282.
[2]Mu S J, et al.An efficient evolutionary multi-objective optimization algorithm[C]//Proceedingsof the IEEE Congress on EvolutionaryComputation (CEC2003) .Canberra:IEEE Press, 2003:914~920.
[3]王跃宣等.处理带约束的多目标优化进化算法[J].清华大学学报 (自然科学版) , 2005, 45 (1) :103~106.
[4]张利彪等.求解多目标优化问题的一种多子群体进化算法[J].控制与决策, 2007, 22 (11) :1313~1316, 1320.
[5]张勇德, 黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策, 2005, 20 (2) :170~173.
[6]朱刚, 马良.多目标函数优化的生长竞争蚁群算法[J].控制与决策, 2007, 22 (11) :1317~1320.
[7]Colorni A, Dorigo M, Maniezzo V.Distributedoptimization by ant colonies[C]//Proc.of the FirstEuropean Conf.on Artificial Life.Paris:ElsevierPublishing, 1991:134~142.
[8]《运筹学》教材编写组.运筹学[M].北京:清华大学出版社, 2005:440~447.
[9]李彤等.求解整数规划的一种仿生类全局优化算法[J].系统工程理论与实践, 2005, 25 (1) :76~85.
基于蚁群优化的协作学习模式研究 篇8
蚁群优化是继遗传算法和人工神经网络算法后发展起来的新颖的仿生型的智能优化算法之一, 且有正反馈、分布计算和启发性搜索等特点。该优化算法在求解组合优化的问题上有较好的优越性, 成功地解决了一些离散性的复杂问题求解。如TSP问题求解、网络路由、资源调度等著名的NP完全问题。但是也存在搜索范围广、搜索时间长, 受外界影响大且易陷局部最优的缺点。文献[2] 提出了一种基于协同合作的蚁群优化算法, 采用随机扰动机制实现蚁群间的协作来加速全局的优化。文献[3]采用池管理和使用大量优先级规则的方法来提升了算法的性能和搜索的速度。文献[4]将蚁群系统 (ACS) 纳入文化算法框架, 避免了传统的计算模式下通过算法的内部状态, 较好地实现了一种新的高效文化蚁群优化算法。岳凤等人的多态蚁群算法研究较好地体现了蚂蚁群体之间的合作效果, 提高了局部的收敛性。
本文根据蚁群优化算法求解离散性问题和组合优化问题的特性, 结合协作学习模式的特点提出了一种改进型的基于蚁群优化的协作学习模式。该学习模式是基于蚁群间通过信息素传递机制来协作完成某项知识学习的过程, 在信息的传递过程中加入了外在的干扰机制 (即教师的外加信息素) , 使学习小组的分组更加灵活性和合理性, 克服了传统机械分组后而不能够合理地形成成员之间的团结合作的学习模式, 从而达不到全局最优的结果。本模式能在充分体现学生的学习个性的同时, 更好地发挥学生主动性、提升对未知知识的探究能力。实验结果表明, 在这种模式中形成的小组协作学习模式, 能较好地实现合理的分组与成员间的优化组合, 达到全局最优的学习效果。
1 基本的蚁群算法
1.1 蚁群算法的基本模型
蚁群算法最初是在求解TSP (旅行商问题) 时提出的。蚂蚁k (k=1, 2, …., m) 在运动过程中, 根据各条路径上的信息量及路径的启发信息来计算状态转移概率。Pundefined (t) 表示在t时刻蚂蚁k由元素 (城市) i转移到元素 (城市) j的状态转移概率:
undefined
式中α为信息启发因子, 表示轨迹的相对重要性;β为期望启发因子, 表示能见度的相对重要性;ηji (t) 为启发函数, 其表达式如下:
undefined
式中dij表示相邻2个城市之间的距离。该启发函数表示蚂蚁从元素i 转移到元素j 的期望程度。
经过n个时刻, 蚂蚁完成一次循环, 各路径上信息素量根据下式调整:
undefined
式中p表示信息挥发因子, (1-p) 为信息轨迹的衰减系数, Δτij (t) 表示本次循环中路径 (i , j) 上的信息素增量, Δτundefined (t) 表示第k只蚂蚁在本次循环中留在路径 (i, j) 上的信息量。
1.2 蚁群算法与组合优化融合
蚁群算法主要思想都是生成一定数量的蚂蚁, 通过每只蚂蚁搜索路径建立可行解。先将蚂蚁随机放置在若干节点上, 每只蚂蚁从初始节点出发, 根据路径上信息素浓度和启发信息以某种概率策略选择下一个节点, 直到建立可行解。每只蚂蚁根据解的优劣程度, 更新路径上的信息素。如此周而复始, 直到蚁群找到最优解。但是蚂蚁在搜索过程中收敛速度慢, 为了加快该算法的收敛速度, 本文将一定数量的蚂蚁通过组合成小数量的团体, 在搜索的路径上通过自身释放的信息素传递信息来进行相互协作活动, 以达到实现最短路径、最少耗时地找到食物的来源点。
2 协作学习模式概述
协作学习 (Co11aborative Learning) 是一种通过小组或团队的形式组织学生进行学习的一种策略。小组成员的协同工作是实现班级学习目标的有机组成部分。小组协作活动中的个体 (学生) 可以将其在学习过程中探索、发现的信息和学习材料与小组中的其它成员共享, 甚至可以同其它组或全班同学共享。在此过程中, 学生之间为了达到小组学习目标, 个体之间可以采用对话、商讨、争论等形式对问题进行充分论证, 以期获得达到学习目标的最佳途径。学生学习中的协作活动有利于发展学生个体的思维能力、增强学生个体之间的沟通能力以及对学生个体之间差异的包容能力。此外, 协作学习对提高学生的学习业绩、形成学生的批判性思维与创新性思维、对待学习内容与学校的乐观态度、小组个体之间及其与社会成员的交流沟通能力、自尊心与个体间相互尊重关系的处理等都有明显的积极作用。在协作学习的过程中, 势必要将一个在的集体分成若干个小的团队, 由于成员的各种素质和能力不同, 那么如何分才能达到最优的效果呢?①小组内部的成员有相近的性格;②组员间能形成很好的合作效果;③组间能形成良性的竞争环境;④成员能主动的发挥自身的积极性且相互扮演或转换不同的角色;⑤整个集体能最大限度的提升学习的效率。
3 基于蚁群优化的协作学习模型
在一个集体学习中, 由于每一个学生的阅历和知识结构不同, 所以学生之间存在着差异, 但在同一位教师的教导下, 对同一类知识, 我们要求是每个学生都能掌握, 但由于学生各自的特点, 很难出现整齐划一的情况, 针对以上的5点要求, 本文引进蚁群优化算法进行分组优化来达到整个集体的最优的成绩效果。
3.1 模型的建立
在这个集体中, 我们可以把每一个学生看成是一只只的小蚂蚁k, 把未知的知识为食物源, 用dij 表现他们现有知识i与将要掌握知识j的距离。Δτundefined (t) 表示在t时刻知识i与已认知j过程中残留的信息量。那么在进行对学生分组合作时, 我们可以动态的进行组合, 让学生自身去组合, 而教师在他们的组合中, 给予适当的引导 (适当的释放或散发一些信息素) , 即在蚂蚁的行进中加入环境中的动态调节机制λ (0<λ<2) , 在公式 (2) 中用λΔτij (t) 代替Δτij (t) 实现信息素的外在更新。这样教师可以在整个过行中进行动态的调节, 从而防止早熟或停滞。
3.2 模型的实现
在蚁群系统中, 位于知识点i的学生k, 根据伪随机比例规则选择知识点j作为下一要求解的识。伪随机比例规则由下式给出:
undefined
其中q是均习分布在区间[0, 1]中的一个随机变量, q0 (0≤q0≤1) 是一个参数, J是根据公式 (1) 给出的概率分布产生出来的一个随机变量 (其中a=1) 。学生选择当前可能的最优的与某同学协作方式的概率q0。这种最优的给合方式是根据信息素和启发式信息值示出的 (在这种情况下, 学生可以通过与学生协作的过程继续开发已知的知识) 。同时, 学生以 (1-q0) 的概率有偏向性地探索新知的各边。通过学生合协和教师的引导来调整参数q0, 并控制学生讨论的深度来决定寻求的最佳解路经附近的区域, 实现快速成收敛以达到全局最优解。
3.3 实验的结果
通过几年的数据显示, 采用传统的教学方式 (教师主重讲授, 学生机械的接收方式) 和采用本协作方式学习的效率进行对照, 见表1:
表1是近年来几个班级中随机抽调的110名学生的实验班与非实验班在几次考试中统计的数据。从数据上看, 基于蚁群协作学习模式的学生, 其学习能力较强, 整体的学习水平比较高。
通过图1、表1可以看出, 采用蚁群算法的协作学习模式, 能使整体达到最优的效果, 且学生的学生主动性有了较大的提升, 因而用蚁群优化能快速实现全局最优解。
4结束语
本文在协作学习的模式上, 利用蚂蚁的自身的搜索能力和在外加的干扰机制的作用下, 提出了一种基于蚁群优化的协作学习模式, 很好地解决了优化分组和成员间动态合作的协调问题。实验表明在有外在的扰动机制 (环境信息素) 下能较好地实现全局的最优化。实验数据证明本学习模式能让学生以最快的速度发现问题, 实现从未知到已知的收敛, 较好实现了全局最优解, 在综合性能上优于单纯的协作模式的学习方法。
参考文献
[1][意]Ant Colony Opti mization Marco dorigo, [德]Thomas Stut-zle.蚁群优化[M].张军, 译.北京:清华大学出版社, 2007.
[2]庞思睿, 孙文生.基于协同合作的蚁群优化算法[M].北京:北京邮电大学出版社, 2009.
[3]彭武良.一种求解多模式资源受限项目调度问题的蚁群算法[J].信息系统学报, 2009 (3) .
[4]刘升, 王行愚, 游晓明.求解TSP问题的文化蚁群优化算法[J].华东理工大学学报 (自然科学版) , 2009 (4) .
[5]岳凤.多态蚁群算法研究及其应用[D].济南:山东师范大学, 2009.
[6]张恩宜.张勉, 杨明花.基于学习者特征的一种协作学习模式[J].中国成人教育, 2003 (5) .
[7]CHORASM.Human Identification Based on Image Analysis[A].proc of Int IEEE Workshop on Signal Processing[C].2003:111-116.
[8]COLORNIA, DORIGO M.Heuristicsfromnaturefor hardcombi-natorial ti mization problems[J].International Trans OperationalResearch, 1996.3 (1) :1-21.
[9]DORIGO M, GAMBARDELLA L M.Ant colony system:Aco-operativelearningapproachtothetravelingsalesman problem[J].IEEE Trans Evolutionary Computation, 1997, 1 (1) :53-66.
[10]郝继红.分组协作自主学习课堂教学模式实践研究[J].河南农业, 2010 (7) .
[11]李建华, 李克东.协作学习及协作学习模式[J].中国电化教育, 2000 (10) .