资源描述：
《单亲遗传算法与传统遗传算法的比较研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第19卷第1期(总第103期)系统工程Vol.19,No.12001年1月SystemsEngineeringJan.,2001文章编号:100124098(2001)0120061205X单亲遗传算法与传统遗传算法的比较研究123李茂军,朱陶业,童调生(1.长沙电力学院电力工程系,湖南长沙410077;2.长沙电力学院现代教育技术中心,湖南长沙410077;3.湖南大学电气与信息工程学院,湖南长沙410082)摘要:通过对单亲遗传算法(PGA)和传统遗传算法(TGA)的编码方式、遗传算子、运行过程和适值计算等方面的比较分析,指出尽管PGA
2、采用单亲繁殖方式,其遗传操作与TGA有着本质的区别,但PGA的基因重组算子隐含了序号编码TGA的交叉算子的功能,PGA的子代个体保留了父代个体的大部分遗传特征。因此PGA仍属于遗传算法的范畴。关键词:单亲遗传算法;传统遗传算法;遗传算子;比较中图分类号:O23文献标识码:A[1]由于遗传算法(GA)在求解各类复杂问题时表现出的鲁棒性、全局最优性和隐含并行性而深受实际工作者的喜爱。GA的编码方式有非序号编码和序号编码两大类。非序号编码GA[2-4]的理论研究较为成熟,实际应用相当广泛。在用GA求解组合优化问题时,使用序号编码比非序号编码更方便
3、、更直接。但传统序号编码GA的遗传操作是模仿非序号编码GA的,主要遗传算子仍为交叉算子,而序号编码GA的染色体不能在任意位置进行交叉,随意交叉后的[5]染色体很可能不再代表原问题的一个解,必须使用PMX、OX和CX等特殊的交叉算子,这些交叉算子遗传操作过程复杂,计算效率不高,且缺乏理论基础,这极大地限制了序号编码GA[6]的推广应用。作者在文献中提出了一种新颖的序号编码GA——单亲遗传算法(PGA)。PGA取消了传统序号编码GA的交叉算子,代之以仅在一条染色体上操作的基因重组等遗传算子,简化了遗传操作,提高了计算效率,并且不要求初始群体的多
4、样性,也不存在“早熟收敛”问题。[7][8]文献对PGA的全局收敛性进行了研究;文献对PGA的图式定理进行了初步研究,并指出[9]了PGA也具有与TGA类似的隐含并行性;文献对PGA的计算效率作了定性分析。以上工[6,10-12]作构成了PGA的基本理论体系。文献分别给出了PGA求解列车占线问题、模式聚类问题、车辆路径问题和物流配送问题的仿真实验结果,表明PGA在求解组合优化问题时明显优于传统遗传算法(TGA)。由于PGA采用单亲繁殖方式,不像TGA那样模拟自然界绝大部分生物的双亲繁殖方X收稿日期:2000211225基金项目:教育部博士点
5、基金资助项目;长沙电力学院科技基金资助项目作者简介:李茂军,男,长沙电力学院电力工程系,博士。62系统工程2001年式,使得不少学者对于PGA是否属于遗传算法的范畴表示怀疑。本文拟将PGA和TGA进行比较分析,指出PGA的基因重组算子隐含了序号编码TGA的交叉算子的功能,TGA的子代个体保留了父代个体的大部分遗传特征,即PGA具有与TGA类似的进化机制,因此PGA仍属于遗传算法的范畴。1编码方式的比较TGA的编码方式比较灵活,可以有序号编码和非序号编码,非序号编码又有二进制编码和实数编码等。PGA是专门针对组合优化问题而提出来的,它采用序号
6、编码方式,但不使用序号编码TGA的交叉算子,而代之以仅在一条染色体上操作的基因换位等遗传算子,即PGA采用单亲繁殖方式。因此,PGA的编码方式比较简单,主要采用序号编码,其功能也主要限于求解组合优化问题。2遗传算子的比较TGA的遗传算子有选择、交叉和变异等。选择算子反映了自然界优胜劣汰的进化机制。PGA的遗传操作以在两条染色体上操作的交叉算子为主,在一条染色体上操作的变异算子为辅。[6、7]PGA的遗传算子有选择、基因重组(包括基因换位、基因移位和基因倒位等调整序号[7]基因在染色体中相对位置的遗传算子)和基因突变等。PGA的选择算子与TG
7、A的完全一样。PGA的遗传操作全部在一条染色体上进行。在TGA中,交叉算子在遗传操作过程中起着重要的作用,而在PGA中,为了遗传操作的方便,取消了交叉算子,那么PGA是如何进化的呢?事实上,PGA的基因重组算子隐含了序号编码TGA的交叉算子的功能。下面以CX算子为例论证基因重组算子是如何隐含序号编码TGA的交叉算子功能的。定义1如果个体A经遗传算子O1的一次作用后生成个体B,而A经遗传算子O2一次或几次作用后也生成个体B的概率p>0,则称O2对O1是可及的。如果遗传算子O2对O1是可及的,则O1的遗传操作功能可以通过O2来实现,或者说O2隐
8、含了O1的功能。遗传算子O1、O2、O3之间的可及关系具有以下性质:(1)自反性,即O1对O1是可及的;(2)传递性,即若O1对O2是可及的,O2对O3是可及的,则O1对O3也是
