基于图的蚁群算法求解一类0-1规划问题

张玉兰

【摘 要】基于图的蚁群算法求解一类0-1规划问题.此算法将0-1规划问题抽象为一个有向图,模拟蚂蚁的觅食行为,由一组蚂蚁反复地在图上运动搜索,最终得到最优解.在给出算法的具体步骤后,用3个具体算例对算法进行测试.结果表明该算法具有良好的收敛性和稳定性.

【期刊名称】《湘南学院学报》 【年(卷),期】2018(039)002 【总页数】5页(P8-11,16)

【关键词】0-1规划问题;蚁群算法;算例;收敛性;稳定性 【作 者】张玉兰

【作者单位】南京铁道职业技术学院 社科部,江苏 南京210031 【正文语种】中 文 【中图分类】O221.4 1 引言

0-1规划是整数规划的特例[1]. 0-1规划在物流运输、调度计划、项目选择、卫星发射等方面有着广泛的应用[1-2]. 一般地，采用隐枚举法和分枝定界法对其进行求解. 对于特殊的0-1规划问题—指派问题，有匈牙利法. 但这些方法随着0-1规划问题的规模(即决策变量数)的增多，计算量急剧增加.随着智能优化算法的兴起，越

来越多的学者也将遗传算法、蚁群算法等智能优化算法应用于求解函数优化问题和0-1规划问题[2-4].

蚁群算法(ACO)是一种广泛应用于解决NP-Hard组合优化问题的仿生算法，是模拟蚂蚁的觅食行为而产生的，是一种随机搜索算法,通过选解组成群体的进化过程寻求最优解和最优值. 其基本原理是：蚂蚁在觅食过程中会在路径上留下一种化学物质—信息素，并能感知它的存在，而且倾向于朝信息素量大的方向移动，从而形成了一种信息正反馈现象[1-6].

本文采用基于图的蚁群算法. 首先将待求解的0-1规划问题抽象为有向图，然后由一组蚂蚁反复地在该图上运动搜索，从而最终找到最优解，求出最优值. 该算法有效地增强了搜索能力的同时，算法的收敛速度也有所提高. 2 基于图的蚁群算法 2.1 问题描述

所求解的一类0-1规划问题为： (Ⅰ)

其中C=(c1,c2,...,cn)为价值向量，X=(x1,x2,...,xn)T为决策变量，为m个约束条件的系数矩阵，b=(b1,b2,...,bm)T为资源向量.

定义1 设0-1规划问题的决策变量X=(v1,v2,...,vn)T，其中vi∈{0,1},i=1,2,...,n，任意选择一点(记为Vs)为起始点，构造一个有向图G=(V,L)，其中V为节点集合(其个数为2n+1)，L为边集(其条数为4n-2)，分别代表0，1，j=1,2,..., 图1是n=4(即4个决策变量的0-1规划问题)的示例，箭头表示蚂蚁的运动方向. 图1 n=4的构造图

定义2 如果ωi满足下列条件①～③，则称ωi为有向图G=(V,L)中的一条路径，对应着0-1规划问题的一个解X：①ωi从V中的起始点(Vs)出发；②ωi至少包含

V中的一个节点一次；③ωi最后一个点在V中没有后继节点.路径的长度为0-1规划问题的规模即决策变量数，i=1,2,...,代表某一次循环. 2.2 算法及其步骤

先根据2.1的方法构造一个有向图，再由一组(ant只)蚂蚁反复在图上运动，从而找到最优解，求出最优值，具体步骤如下：

Step1 初始化，置迭代次数即蚂蚁搜索次数t=1；图中每天边上的信息素量为0-1规划的规模；

Step2 ∀t∈[1,5m](m为设置的蚂蚁的搜索总次数)，每只蚂蚁按(Ⅲ)式提供的转移概率从当前节点k转移到下一节点 (Ⅱ)

其中：ωt=(Vs,vt1,vt2,...,vt(q-1)=k)指第t次循环(迭代)中蚂蚁在第q步之前经过的路径，vti∈V,i=1,2,...,q-1；τkv(t)为第t次循环边(k,v)上的信息素量； Step3 当所有蚂蚁都完成第t次循环后，按(Ⅲ)式进行全局信息素量的更新： τkv(t+1)=(1-ρ)τkv(t)+ρ△τkv， (Ⅲ)

式中ρ为信息素的蒸发因子，△τkv由(Ⅳ)，(Ⅴ)计算得到： (Ⅳ) (Ⅴ)

z(Xt)为第t次循环中所有过边(k,v)的路径对应的0-1规划问题的可行解的函数值中最小值，ant是蚂蚁的数量；

Step4 计算第t次循环的目标函数值(即第t次循环的最优值)，找出最优解； Step5 t=t+1，重复Step2～ Step4，直到t=5m，输出当前的最优解和最优值

(全局最优解和最优值). 3 数值实验

为了测试算法的可行性和有效性，分别采用基本蚁群算法和基于图的蚁群算法求解了3个相关的算例，算法的收敛性和稳定性得到了验证.

在Windows XP下用matlab 6.5编写程序进行计算. 程序中的参数取值如下：ρ=0.2，ant=50，5m=50. 例1

基本蚁群算法和基于图的蚁群算法都能收敛到最小值z*=42，最优解为X*=(1,0,0,1)T，其收敛过程见图2和图3. 图2 基本蚁群算法的收敛过程.

图3 基于图的蚁群算法的收敛过程 例2

两种算法都能收敛到最优值z*=10，最优解为和收敛过程见图4和图5. 图4 基本蚁群算法的收敛过程

图5 基于图的蚁群算法的收敛过程 例3

两种算法均能收敛到最优值z*=4，对应的最优解为X*=(0,0,1,0,0,0,1,0,0,0)T，其收敛过程见图6和图7. 图6 基本蚁群算法的收敛过程

图7 基于图的蚁群算法的收敛过 4 结语

例1～例3的实验结果表明：基于图的蚁群算法具有一定的通用性，而且收敛性和稳定性较好，具有较强的搜索最优解和最优值的能力，虽然耗时相对于基本蚁群算法而言稍微长一些，具体结果见表1. 由表1知，这个时间是可以接受的. 表1 基本蚁群算法和基于图的蚁群算法的耗时表 基本蚁群算法(ACO)基于图的蚁群算法算例10．09730．382算例20．08440．6060．09460．625算例30．10030．294 参考文献：

[1] 王雷震.物流运筹学[M].上海：上海交通大学出版社, 2008.

[2] 管屏，朱刚，马良，等.求解0-1规划的生长竞争蚁群算法[J].计算机工程与科学, 2012，34(3)：128-131.

[3] 张玉兰，朱庆保.求解连续函数最大值的蚂蚁优化算法[J].南京师范大学学报(工程技术版),2005，5(3)：61-63.

[4] 余胜威.MATLAB优化算法案例分析与应用(进阶篇)[M].北京：清华大学出版社,2015：409-418.

[5] 张玉兰.机器人路径规划蚂蚁算法及其收敛性分析[J].苏州科技学院学报(工程技术版),2010，23(3)：72-77.

[6] 张玉兰，龚建荣.函数优化问题的遗传算法和蚂蚁算法混合算法的研究[J].科技信息,2010：369.