用遗传算法求最小生成树

朱彦廷

(河池职业学院 计算机系,广西 河池 547000)

用遗传算法求最小生成树

朱彦廷

(河池职业学院 计算机系,广西 河池 547000)

以图论和遗传算法为基础,给出了一个改进的求最小生成树的算法,提出了“无性生殖”的方式,舍弃了逆转算子,改进了换位算子,调整了选择算子,更简单,因而编程更容易,效率更高 .使用该算法可以在较短的时间内以较高的概率获得一组最小或次小生成树,而传统算法一般只能得到一个最小生成树 .

最小生成树;遗传算法;优化

1 基本原理

遗传算法借助于生物进化机制与遗传学原理,先随机产生一些个体,然后进行选择、交叉和变异操作,模拟自然界中生物的进化过程,使个体的性能不断提高,逼近问题的最优解 .它用于求解组合优化问题非常有效,寻找最小生成树实际也是组合优化问题,因此可以考虑使用遗传算法 .

2 算法设计

2.1 编码

设一无向图共有ND个顶点,NP条边,对边进行编号 .一个个体是一个二进制代码,长为NP,代表图的一个子图,若某位为 1,表示它所对应的边是子图的边;若为 0,表示它所对应的边不是子图的边 .

2.2 适应度函数

2.3 遗传算子

交叉算子以某一概率随机交换 2个个体的部分位,得到 2个新个体 .变异算子以某一概率随机改变个体的某些位,得到 1个新个体 .对于本问题,它们极可能破坏个体的可行性,即得到的新个体不是只有ND-1位为 1,根本不代表一个生成树,没有意义,因此不能直接用这 2个算子 .

已有人对此做过研究,概括起来,他们[2-4]提出了换位算子和逆转算子,相当于舍弃了交叉算子,对变异算子做了修改 .如果说一般遗传算法采用的是“有性生殖”(使用交叉算子,1个新个体由 2个个体得到),那么这里的遗传算法采用的就是“无性生殖”(舍弃交叉算子,1个新个体由 1个个体得到).生物进化了几十亿年,无性生殖仍广泛存在于自然界中,说明它有存在的价值,遗传算法要更好地模拟生物进化过程,也应包括这种方式 .

换位算子:随机产生 2个换位位,对其进行换位 .以个体 011100为例,若换位位为 0、2,换位后为110100.文献[2,4]提出换位次数随机产生,不固定是 1,假设换位次数为 2,对 110100再次换位,可能得到的个体不如它,但它却被丢弃了,因此应固定是 1.而若换位位为 1、2,对应的数值相同,或换位位为 1、1,换位没有价值 .

逆转算子:先随机产生逆转起始位,再随机产生逆转位数,如果要逆转的部分含“1”的个数和“0”的个数相等(文献[3]说含“1”的个数为偶数,是不准确的,其它文献大多叙述含糊,对这个关键的地方只字不提),对其进行逆转,以个体 011100为例,若逆转起始位是 2,逆转位数是 4,则要逆转的部分是 1100,含“1”的个数和“0”的个数相等,逆转后为 010011.

假设个体有n位,逆转起始位只能为 0,1,…,n-1,逆转位数应为偶数,最小是 2,加上相应的逆转起始位又不大于n,编程很麻烦 .而如果要逆转的部分含“1”的个数和“0”的个数不相等,不能进行逆转(那将破坏个体的可行性).

各位被逆转的概率其实是不同的 .为简单起见,假设个体有 4位,那么逆转起始位只能为 0、1、2,若逆转起始位为 0,逆转位数只能为 2、4;若逆转起始位为 1,逆转位数只能为 2;若逆转起始位为 2,逆转位数只能为 2,再假设要逆转的部分含“1”的个数和“0”的个数相等,可以算出各位被逆转的概率分别是 1/3,2/3,5/6,1/2,这样可能有的位如果被逆转能得到更好的个体,但被逆转的概率很小;有的位如果被保留能得到更好的个体,但被逆转的概率很大,很不合理 .

本算法舍弃了逆转算子,对换位算子加以改进,随机产生 1个换位位,如果该位原为 0,变为 1,为了保证新个体只有ND-1位为 1,然后向后寻找第 1个为 1的位,变为 0,如果没找到,再从最前面寻找(一定能找到,否则意味着个体的各位全是 0,这是不可能的);如果该位原为 1,变为 0,然后向后寻找第 1个为 0的位,变为 1,如果没找到,再从最前面寻找[一定能找到,否则意味着个体的各位全是 1(说明无向图已是树,那就没必要求了),这是不可能的],这样换位肯定有价值 .以个体 011100为例,如果产生的换位位是 1,则换位后为 001110;如果换位位是 4,换位后为 001110.

选择算子从群体中选择较好的个体,用来进行交叉、变异 .一般用个体的适应度与群体中个体的适应度的总和的比值作为其被选择的概率,个体的适应度越高,被选择的概率越大,对于本问题,较好的个体不一定产生较好的新个体,二者没有什么关系,因此不用这种做法 .因为新个体可能不如原个体好,为更多地保存较好的个体,以便最后得到更多的最小或次小生成树,将新群体与原群体混合,按适应度高低降序排序,选出最好的不重复的个体(约占群体数目的 80%),这充分体现了优胜劣汰的原则,再随机产生少量新个体(约占群体数目的 20%),合起来组成下一代群体,这可以弥补舍弃逆转算子(它改变个体的幅度大,因而对解空间的搜索能力强)带来的不足,保持了群体的多样性,以免出现早熟现象(进化过早停滞).

2.4 算法流程

(1)设置群体大小M、最大进化代数T;

(2)随机生成M个个体作为初始群体,计算各个个体的适应度;

(3)如果进化代数t=T,转到(7);

(4)变异,计算各个个体的适应度;

(5)选择,得到下一代群体;

(6)t=t+1,转到(3);

(7)输出最终群体 .

3 实例

现有 10个雷达站,23条可能的光缆,如图 1所示(括号内为光缆长度),想建立一雷达网,拟求一组光缆总长度最短或次短的方案 .采用图论中的经典算法一般只能得到一个权为 60的最小生成树 .应用本文算法,参数设置如下:M=10,T=200,结果如表 1所示,可获得 8个(1～7号个体)最小或次小生成树(权为60～62(F0为 99),9、10号个体是随机产生的,不代表生成树),可以结合其它因素进一步确定选择哪一个 .

表 1 最终群体

图 1 雷达网初步连接图

4 结语

本文提出了“无性生殖”的方式,丰富了遗传算法的概念 .和已有的算法比,本文算法叙述清晰,舍弃了逆转算子 (可能耗费了时间,却不能进行逆转),改进了换位算子 (可能耗费了时间,却不能有效进行换位),调整了选择算子 (可以弥补舍弃逆转算子的缺点),更简单,因而编程更容易,效率更高 (因为舍弃了逆转算子,改进了换位算子,使其肯定能有效进行).应用时可以每隔几代 (如 5、10代)计算一次选出的最好的不重复的个体的平均适应度,并和上次比较,如小于某个阈值,可以考虑停止进化,这样更省时间 .

[1]唐策善,李龙澍,黄刘生.数据结构[M].北京:高等教育出版社,1992,137-142.

[2]周荣敏,买文宁,雷延峰.基于遗传算法的最小生成树算法[J].郑州大学学报 (工学版),2002,23(1):45-48.

[3]刘志成,钱建刚.基于改进遗传算法的最小生成树算法[J].计算机工程与设计,2004,25(9):1620-1622.

[4]张强,李晓莉.交通选线优化算法的设计与实现[J].计算机工程与应用,2009,45(8):226-228.

A Genetic Algorithm to Determ ine theM in imum Spann ing Tree

ZHU Yan-ting

(Department of Computer Science,Hechi Vocational College,Hechi Guangxi547000,China)

Based on graphic theory and genetic algorithm,an improved algorithm to deter mine the minimum spanning tree is given,the“asexual reproduction”method introduced,the transposition operator abandoned,the transposition operator improved,and the selection operator adjusted,which makes program easier and more efficient.Using the algorithm,we can obtain a group ofminimum or less spanning trees in a shorter time and with a higher probability,while using the traditional algorithms,we can only get a minimum spanning tree.

minimum spanning tree;genetic algorithm;optimization

TP3

A

1672-9021(2010)02-0062-04

朱彦廷 (1976—),男,辽宁建昌人,河池职业学院计算机系助教,硕士,主要研究方向:遗传算法等.

2009-12-25

[责任编辑阳崇波 ]