摘要
为了高效地获得地图的四作色方案,首先将地图转化为平面图,并给出了四作色问题在遗传算法求解中的编码规则。为了克服算法容易陷入局部解的缺陷,杂交算子采用了双点杂交方式,并引入了较高概率的变异算子。在传统单适应度评估函数的基础上,引入了评价个体基因好坏的基因评估函数,并增加了对最差基因以概率为1的变异算子。数值试验表明,该方法能极大提高算法的收敛速度,对图的四作色问题求解具有较高的效率。
In order to effictively obtain four-coloring map solutions,first,the map was turned into a plan to give coding rules genetic algorithm for solving the four-coloring map problems.To avoid the algorithm being stuck into local solutions,crossover operator was used for a dual-point crossover and introduction of a high probability mutation operator.It adds gene fitness function based on single fitness function,and increases worst gene mutation operator to probability equal to 1.Test show that the method can greatly improve the speed of algorithm and it is higher efficiency for four-coloring map problems.
出处
《长江大学学报（自科版）（上旬）》
CAS
2010年第1期6-10,共5页
JOURNAL OF YANGTZE UNIVERSITY (NATURAL SCIENCE EDITION) SCI ＆ ENG
基金
广东省科技计划项目(2008B080701018)
关键词
四色问题
遗传算法
地图
邻接表
four-coloring map problems
genetic algorithm
map
adjacent table
