交叉 (遗传算法)

✍ dations ◷ 2025-11-30 21:59:27 #算法,遗传算法,最优化算法

交叉(crossover)是遗传算法中由遗传学中染色体交叉互换、生物杂交等现象发展来的一个算法过程。

在自然环境中,基因重组对生物的进化起到非常关键的作用,同理,杂交操作也是遗传算法的核心部分。

杂交操作就是将两个父本染色体上的基因进行重新组合分配,从而产生下一代个体的过程,通过杂交可能会将两个父本的优势基因组合在一起,产生适应度更高、更接近最优解的新个体。通常杂交算法和基因的编码方式有关,当前采用最多的是二进制编码方式,二进制编码的主要杂交算法有:

这种杂交方式是当前使用最多的杂交算法。单点杂交的主要过程是:首先在染色体上随机选择一个交换点;然后确定是在交换点前面部分或者后面部分的基因进行交换;最后根据前面的原则将两父本的染色体基因进行交换重组,从而形成了新的个体,即下一代个体。如有两个父本染色体序列10010|111和00101|010,其中“|”表示交换点,按照父本染色体的交换点前部分交换的原则,产生的新得下一代个体的染色体分别是00101|111和10010|010。

多点杂交算法就是指定了多个交换点用于父本的基因交换重组,具体的执行过程与单点杂交算法类似。

上述的两种杂交算法存在杂交的染色体中某些部分的基因会被过早地舍弃,这是由于在交换前它们必须确定交换父本染色体交换位前面还是后面的基因,从而对于那些无关的基因段在交换前就已经收敛了。均匀杂交算法(Uniform Crossover)就可以解决上述算法的这种局限性,该算法的主要过程如下:首先随机选择染色体上的交换位;然后随机确定交换的基因是父本染色体上交换位的前部分基因还是后部分基因;最后对父本染色体的基因进行重组从而产生新的下一代个体。

该杂交算法的最大特点是通常将染色体的中点作为基因的交换点,即从每个父本中取它们一般的基因重组成新的个体。另外针对于实值编码方式,还有离散杂交、中间杂交、线性杂交和扩展线性杂交等算法。

相关

  • 普遍文法普遍文法(英语:universal grammar,缩写为 UG),又译为普遍语法,一种语言学理论,最有名的提倡者为乔姆斯基。这个理论认为在人类能够学习到各种文法的普遍能力,是被内建在大脑中的。它
  • 鬼神在中国传统中,鬼神泛指超自然的存在,他们能够影响人世。这个思想起源于多神论。中国上古时期,鬼,指已经过世的人,是在世者的祖先;而神,可分为天神与地祇,是控制天地山川社稷的神灵。
  • 豪尔赫·冈萨雷斯豪尔赫·冈萨雷斯(西班牙语:Jorge González,1966年1月30日-2010年9月22日),出生于阿根廷,是世界摔角娱乐(WWF)旗下职业摔角选手,也曾因其身材条件上的优势,在NBA被亚特兰大老鹰队选秀
  • 左心耳血栓心房(拉丁语:Atrium)旧称䆝,是构成心脏腔室的一种。心脏分心房与心室,分别负责接收 左心房则可根据胚胎来源被分为左心耳和左心房窦。和原始静脉窦右角发展而来的腔静脉窦。在右
  • 德菲因·塞里格黛芬·赛赫意(法语:Delphine Seyrig,1932年4月10日-1990年10月15日)是法国演员。1963年,她因演出《穆里爱》而于第24届威尼斯影展获得最佳女演员。
  • 酸度酸(英语:acid有时用“HA”表示)的传统定义是当溶解在水中时,溶液中氢离子的浓度大于纯水中氢离子浓度的化合物。换句话说,酸性溶液的pH值小于水的pH值(25℃时为水的pH值是7)。酸一
  • 体育局体育局(葡文:Instituto do Desporto,葡文缩写:ID),前称:体育发展局,是澳门特别行政区政府社会文化司辖下的行政自治部门,前身为澳葡政府在1993年成立的澳门体育总署,该署署长最后一任
  • 南大西洋异常区南大西洋异常区(South Atlantic Anomaly)是地球上一片地磁最弱的区域,覆盖范围遍及南美洲南部及南大西洋海域。由于该区的地磁较其他地区弱,阻挡太阳粒子的范艾伦辐射带在该区
  • 张卫平 (1962年)张卫平(1962年6月-),现任华东师范大学终身教授、上海交通大学致远讲席教授。1983年毕业于安徽师范大学物理系获学士学位,1986年和1989年分别获中国科学院上海光学精密机械研究所
  • 西村直己西村直己(1905年10月8日-1980年7月28日),东京府人,昭和时期政治家、众议院议员。毕业于东京户山高等学校(日语:東京都立戸山高等学校)、旧制第一高等学校、东京大学法学部后,进入内务