平面图着色的遗传算法

四色问题的相关文献,可用。

第16卷第4期

1999年 11月贵州大学学报(自然科学版)JournalofGuizhouUniversity(NaturalScience)Vol.16.No.4Nov.1999

平面图着色的遗传算法

洪 斌

(贵州虹山轴承(集团)有限公司,安顺 561000)

摘 要 基于遗传算法的思想,建立了一个用四种不同颜色对平面图结点进行

着色的快速算法.

关键词 平面图,图着色,快速算法

中图分类号 T301.6

1 引言

1976年,美国数学家阿佩尔(K.Appel)和哈肯(W.Haken)与计算机科学家科赫(J.Koch)合作,用计算机证明了著名 四色猜想 ,曾经轰动一时.但是,在当时的计算条件下,这个证明的计算用时达1260小时,其正确性人工无法验证,即 四色猜想 至今尚未找到一个严格的数学证明.尽管如此,人们似乎已经默人这一著名猜想是对的.即任意一个平图都可以用至多四种不同颜色对其平面区域进行正常着色.由图论知识知道,该结论可以转化为任意一个平图都可以至多四种不同颜色对其结点进行正常着色(相邻结点不能着相同颜色).

我们现在所考虑的问题不是 四色猜想 本身,而是对于任意一个平面图,如何给出一个用四种不同颜色对其结点进行正常着色的着色方案.如果用通常的逐步搜索方法进行着色,对于具有n个结点的平面图,我们可以用构造一棵高度为n的完满四叉树来表示整个搜索过程,并可求出所有着色方案,其中一个着色方案对应着该四叉树上一条从根结点到叶结点的路径.不难看出:找到一个着色方案的最坏时间是指数时间.可以证明,寻求一个平面图的四色着色方案是一3个NPC问题.

近年来迅速发展起来的遗传算法,是一种全局优化方法,该方法依照生物学中的 优胜劣汰,适者生存 的原理,提供了一种强大的快速搜索能力,能够快速搜索到问题的最优解或近似最优解.从理论上讲,对于我们所考虑的问题,其最优解是存在的.问题是:如何快速地确定出最优解.这是本文的主要目的和结果.

2 遗传算法的基本原理

遗传算法的思想是,将一组初始方案(如所有可能解)人工模拟为一组群体,一种方案对应一个个体.通常采用二进制编码将一个方案描述一个0、1字符串.假定不同个体

四色问题的相关文献,可用。

# 298 # 贵州大学学报(自然科学版) 第16卷的字符长度相同.确定一个评价方案的指标(称为该方案的适应度).模拟生物遗传产生下一代群体,直到得到满意的个体为止.具体作法如下:

2.1 确定一个初始群体

选定初始群体S0:s1,s2,!,sN作为第一代群体,|si|=l(i=1,2,!,N).其生成方式有如下两种:

(1) 随机生成适当个数的个体;

(2) 选择所有可能的个体.

2.2 确定一个个体适应度函数

在个体上定义一个函数f,称为适应度函数.对每个s1,f(si)称为si的适应度.一般取f为一个非负函数.

2.3 确定一种个体随机选择的方法

一般采用赌盘选择法,具体操作如下:

设有群体S:s1,s2,!,sN,每个个体对应的适度分别为:

f(s1),f(s2),!,f(sN),令A=f(s1)+f(s2)+!+f(sN),在0与A之间随机产生B,令C=0,Pi=f(si)/A(i=1,2,!,N),依概率P1,P2,!,PN在1到N之间随机产生一个个体编号m,将f(sm)累加进C中(即C C+f(sm)),直到C>B时将sm作为被选个体.

2.4 依概率随机选择方法

设P1,P2,!,PN分别为随机选择n个对象O1,O2,!,ON中某一个时,各自所依赖的概率,P1+P2+!+PN=1.即选中对象Oi的概率为Pi(i=1,2,!,N).

i

在具体实现时,可以采取如下方法:令ai=j Pj(i=1,2,!,N),将[0,1]区间=1

分为N个互不相交的小区间:

I1=[0,a1],I2=[a1,a2],!,IN-1=[aN-2,aN-1],IN=[aN-1,1]

在[0,1]上随机产生一个数a,若a落入区间Im,则对象Om被选中.

2.5 当代群体上所施行的三种运算

2.5.1 复制运算

在当代群体中用赌盘方法将部分个体复制到一个拳的群体,允许相同个体重复出现,视为 克隆 现象.复制运算并不产生新的个体.

2.5.2 交叉运算

随机选定两个个体进行交配.即在某一确定段上(或某些代码位置上),对等交换代码,产生两个下一代个体.

2.5.3 变异运算

随机选定一个个体,将其两个指定位置的代码对调(或在某一位置上转换),以产生一个新的下一代个体.

为了尽量消除人为因素,让其自然选择.对上述三种运算,我们仅从概率上加以控制:比如作复制、交叉、变异运算的概率分别为Pr,Pc,Pm.一般来讲Pm的值很小,,,

四色问题的相关文献,可用。

第4期 洪 斌:平面图着色的遗传算法 #299#生一个新个体.而且有可能后一代的适应度小于父代的适度.但是,对于着色问题,变异运算的作用不小.从而Pm值不能取得很小.

值得注意的是:(1)为保证 优胜劣汰,适者生存 的自然选择规律,上述三种运算中在选定个体时是随机的,其随机性适应度有关.一般来说:对于复制运算,适应度较高的个体每次选择时,被选到的可能性更大,可能被多次重复选到.在此意义下,实质上是某些适应度低的个体被适应度高的个体所代换后形成下一代.对于交叉运算,也是选择适应度较高的进行交配.(2)初始群体中,个体一般来说互不相同,但从第二代开始,个别个体可能重复.(3)若上述三种运算采用串行处理,则运算顺序为,复制、交叉、变异.此时,若当代群体S有n个个体,则可用n次复制运算产生一个中间群体(俗称交配池),交叉运算和变异运算产生下一代个体.其中变异运算产生的新个体要加入到下一代群体中,这时个体总数可能增加.(4)若上述三种运算采用并行处理,则每次依概率Pr,Pc,Pm确定选择复制、交叉、变异三种运算中的一种.此时,三种运算的结果都统称为下一代.

2.6 确定算法终止条件

算法总是要求终止的,在遗传算法中我们可以采用多种形式的条件来终止算法的执行,同时又总是希望得到满意的解.常用的方法是用如下两个条件进行限制:

(1)当代群体中最大适应度与最小适应度之差小于某个预先给定的误差(也称信度) .即在 水平下个体差异已经趋于稳定.此时可以停机.

(2)控制最大遗传代数M.即给定一正整数M,最多遗传到第M代时,必须停机.可以看出:条件(1)、(2)下算法必然会终止.停机后,在产生的当代群体中选择适应度最大的一个个体作为问题的解.

可以证明:上一代与下一代的平均适应度是单调上升的.这就保证:从整个群体而言,遗传运算保证 一代更比一代好 .

对于着色问题:由于最优解存在,我们应该将M取得适当大,以保证问题最终能有答案.

3 平面图结点着色算法

3.1 平面图的四色(结点)着色问题描述

给定无向平图面G=(V,E)(不失一般性,可设为简单无向连通平面图),V={v1,v2,!,vn}为具有n个结点的结点集,现用四种不同颜色对其所有结点进行着色,使得相互邻接的任意两个结点不能着相同颜色.

问:如何确定一个着色方案?

恰好,我们可以用00、01、10、11表示四种不同颜色,于是,一个合理的着色方案刚好对一个长为2n的0、1字符串.

对于任一个长为2n的字符串s=q1q2!q2n表示.确定一个函数f.f(s)称为s的适应度.(为了叙述方便,本文中适度f(s)理解为着色方案s的冲突程度)求解问题:minf(s)对应s.

四色问题的相关文献,可用。

# 300 # 贵州大学学报(自然科学版) 第16卷

定义f(s)如下:

对任一个 i

i=1V={ 1, 2,!, n},记di=deg( i)为 i的度,结点度数和 = ndeg( i), i=di.给定s=q1,q2!q2n,令xi=q2i-1q2i,g(xi)为与 i相邻的结点中同i=1着xi色的结点.(i=1,2,!,n).令f(s)=

f(s)=0时,对应的s为一个合理着色方案. ng(xi),可见,f(s)%0,且f(s)为偶数,当

可以看出:若以s作为一种着色方案,f(s)刻划了此方案中结点着色冲突之累计,g(xi)则刻划了在结点 i发生着色冲突结点数之累计.结点度数起高,绿生冲突的可能性就越大.对应地,修改结点的着色号,降低f(s)值就越快.于是,我们有理由依概率a1,a2,!,an对个体s=q1,q2!q2n确定实施变异运算的代码位置(每次在两个连续相邻代码上进行).另外,由结点着色的特点,交叉运算采用两个体中一长度为偶数的连续代码段作对换.

3.2 遗传算法

Step0:输入平面G的邻接矩阵A.对每一个 i V

{ 1, 2,!, n},计算

di=deg( i), =i=1i), i= deg( ndi. Step1:给定信度 ;最大遗传代数M;初始群体个数N;遗传运算所依概率

Pr,Pc,Pm.

Step2:随机产生初始群体S:s1,s2,!,sN;K=1.

Step3:计算f(s1),f(s2),!,f(sN);

Fmin=min{f(s1),f(s2),,f(sN)}

Fmax=max{f(s1),f(s2),,f(sN)}

若Fmin=0,则转Step5.否则进入Step4.

若Fmax-Fmin< 或k>M,则转Step6.否则进入Step4.

Step4:依概率Pr,Pc,Pm随机选定遗传运算(对应执行子算法).作一次遗传运算产生下一代群体:

S&:s&1,s&2,,s&N.令S S&,N N&,k=k+1.转Step3.

Step5:找一个使Fmin=min{f(s1),f(s2),!,f(sN)}=0的sj,译出sj对应着色方案.停机.

Step6:显示 本次运算未得到着色方案,请调整参数:信度 ;最大遗传代数M;初始群体个数N;遗传运算所依概率Pr,Pc,Pm .停机.

若计算的出口是由Step6导致的,可适当调整一下参数,继续下一轮计算.

很显然,此算法的计算复杂性为O(n2).

3.2.1子算法1 复制(选择)运算为S:1,2,!,sN分计算每的冲f(s1),f(s2,,

四色问题的相关文献,可用。

f(sN),令A0=f(s1)+f(s2)+!+f(sN),A=N*n2-A.(其中:n为结点数),在0与A之间随机产生一个数B,令C=0,对i=1,2,!,N,分别计算Pi=n2-f(si)/A,依概率P1,P2,!,PN在1到N之间随机产生一个个体编号m,将(n2-f(sm))累加进C中(即C C+(n2-f(sm))),直到C>B时将此sm作为被选个体.选择结果保留进入下一代.

3.2.2 子算法2 交叉运算

用子算法1选择出两个个体s&、s(作为交配对象,在1到n之间随机产生两个数,取整后为n0,l0,将s&、s(上从2n0+1至2(n0+l0)+1代码段上的代码对调(若后半部分长度不足,可以循环至头部),产生两个交配后代.

3.2.3 子算法3 变异运算

用子算法1选择出一个个体s&作为变异对象,依概率a1,a2,!,an产生一个结点号n0,对个体s&上2n0-1、2n0两处分别随机产生0、1进行取代.

4 计算例子

给定无向平面G=(V,E)及邻矩阵A如下

:

四色问题的相关文献,可用。

1

0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 2 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 6 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 8 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 3 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 0 5 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 6 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 4 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 51000000000001010000011010 1 2 3 4 5 6 7 8 9 0 1A=23456789012345

运算结果:

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 00 01 10 00 10 11 11 01 00 10 01 00 01 10 11 00 01 01 11 10 00 00 01 11 10

参 考 文 献

1 刘勇,康立山,陈毓屏.非数值并行算法(第二册) 遗传算法.北京:科学出版社,1998

2 周忠辅,数学的陷阱 四色猜想的种种 证明 .自然杂志.1988,14卷5期:379~382

3 田奕,刘涛,李国杰.求解可满足性足性问题的一种高效遗传算法.模式识别与人工智能.1996,9(3):209

~212

GenericAlgorithmofColorPlanarGraph

HongBin

(HongShanAxisCorporationofGuizhou,Anshun 550025)

Abstract Agenericalborithm,coloringplanargraphonlyusingfourcolorsispre

sentedbasedongenericalgorithm.

Keywords planargraph,colorgraph,genericalgorithm

本文来源：https://www.bwwdw.com/article/jv24.html