交叉 (遗传算法)

✍ dations ◷ 2025-06-08 16:37:07 #算法,遗传算法,最优化算法

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

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

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

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

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

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

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

相关

  • 炭疽炭疽病(英语:anthrax)是由炭疽杆菌感染造成的疾病,感染途径包括皮肤接触、呼吸道、消化道以及注射等四种,通常在感染一天至两个月后开始出现症状,经由皮肤接触的感染起初会出现小
  • 三头政治三头同盟(triumvirate,源于拉丁语“triumvirātus”),指由三个有权之人占主导地位的政治体制,三位都是其中一名“三执政”(英语:triumvir)。这项安排可以是正式的或非正式的,通常三人
  • 交通宁静化交通宁静化(英语:traffic calming),又称交通稳静化、交通静稳化、交通安定化、交通镇静化或交通稳化等,是采用物理设计和其他措施来提高驾驶者、行人和骑行者(英语:Bicycle-friendl
  • 北美空防司令部坐标:38°42′00″N 104°48′00″W / 38.70000°N 104.80000°W / 38.70000; -104.80000北美空防司令部(英语:North American Aerospace Defense Command,简称NORAD)是一个由美
  • 化合化合反应是一类化学反应的总称(通常是指无机反应),是指两个或多个反应物经过化学反应生成一种产物。例如,氢气和氧气燃烧生成水就是化合反应。通常化合反应都是放热反应。
  • 拉宾伊扎克·拉宾(希伯来语:.mw-parser-output .script-hebrew,.mw-parser-output .script-Hebr{font-size:1.15em;font-family:"Ezra SIL","Ezra SIL SR","Keter Aram Tsova","Ta
  • 原台湾总督府专卖局台南支局安平分室坐标:23°00′09″N 120°09′23″E / 23.002513°N 120.156379°E / 23.002513; 120.156379假日 10:00 - 21:00 平日 11:00 - 20:00原台湾总督府专卖局台南支局安平分室位于台
  • 吕建 (学者)吕建(1960年3月31日-),男,籍贯山东荣成,生于江苏南京,中国软件科学家,中国科学院院士,南京大学校长,无党派人士。主要从事软件方法学研究。1982年,毕业于南京大学计算机系。1984年,于南
  • 高山植物高山植物是指能在林线以上的高山带生长的植物。在年平均温度低于10℃的高山地带,树木不易生长,在森林所能到达的最高海拔,称为林线。高山地区由于常年低温、地形陡峭、表面土壤
  • 侧棘齿鳉侧棘齿鳉,为辐鳍鱼纲鲤齿目鲤齿亚目谷鳉科的其中一种,为热带淡水鱼,被IUCN列为濒危保育类动物,分布于中美洲墨西哥Durango淡水流域,体长可达4公分,栖息在植被生长、水质清澈的涌泉