交叉 (遗传算法)

✍ dations ◷ 2025-07-03 14:40:16 #算法,遗传算法,最优化算法

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

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

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

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

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

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

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

相关

  • 角色角色(拼音:jué sè或jiǎo sè),或称虚构角色。是在叙事艺术作品描绘的人,演员根据剧本演绎的人物或漫画作品中的登场人物往往也被称作人物。故事的载体可以是小说、戏剧、动漫
  • 跖行动物跖行,又称跖行,指的是陆生动物在行走时跗骨、跖骨和趾骨均着地。为哺乳动物三种行走行式之一,其他包括趾行(英语:digitigrade),仅有脚趾着地而脚跟或腕不接触地面,以及蹄行(英语:ungul
  • 恶作剧恶作剧,又称整蛊、整人,是一种借由欺骗、作弄或冒犯他人以得到乐趣的行为。恶作剧最基本的形式即是故意使他人陷入窘境,并在旁观赏他人尴尬、吃惊、惶恐等等寻常难以得见的情绪
  • 各国首次自主发射运载火箭时间表以下列出各国首次自主发射运载火箭时间表,即所有自主发射人造卫星的国家或航天机构的首次成功发射记录。如下国家与机构属于“太空俱乐部”的成员。注意此列表记录人造卫星的
  • 雪邦国际赛道雪邦国际赛道(马来语:Litar Antarabangsa Sepang)是位于马来西亚雪兰莪州雪邦的一座动力运动赛车场,十分临近同样位于雪邦的吉隆坡国际机场。雪邦国际赛道承办的主要赛事包括从1
  • 正果正果可以指:
  • Seyferth–Gilbert增碳反应Seyferth–Gilbert增碳反应(Seyferth-Gilbert homologation),又称Seyferth-Gilbert同系化反应芳酮(或醛)与重氮甲基膦酸二甲酯(Seyferth-Gilbert试剂)在叔丁醇钾存在下反应生成取代
  • 韩伟韩伟(1928年12月12日-1984年8月4日),江苏铜山人,台湾学者,曾任中原大学校长。父亲是韩时俊(1901-1978年),母亲范忠恕(1900-1961年)。在国防医学院借读时曾是运动校队球员,担任排球捶手、篮
  • 杨培东杨培东(1971年8月-),江苏苏州人。美籍华裔化学家、材料科学家。现为加州大学伯克利分校化学和材料科学双聘教授。美国文理科学院院士、美国国家科学院院士。1971年出生在苏州相
  • 巴西 (传说岛屿)巴西(爱尔兰语:Brasil)是爱尔兰传说(英语:Irish mythology)中的岛屿,位在爱尔兰西方。这座岛平时被浓雾所遮盖着,每七年中的一天浓雾才会散去。中世纪的许多古地图都记载了巴西。也