交叉 (遗传算法)

✍ dations ◷ 2025-04-04 09:23:50 #算法,遗传算法,最优化算法

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

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

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

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

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

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

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

相关

  • 工程技术工程技术可指:
  • 木聚糖木聚糖是植物细胞中主要的半纤维素成分,占植物细胞干重的35%,是一种丰富的生物质资源,是自然界中除纤维素之外含量最丰富的多糖。然而自然界中很大一部分木聚糖未被有效利用,造
  • 法语国家及地区国际组织法语国家及地区国际组织(法语:Organisation internationale de la Francophonie,简称OIF),简称法语国家组织,也有译名为法语圈国际组织,是以法语作为第一语言、或受法国文化显著影
  • 纳瓦族纳瓦人,又称纳瓦特尔人(纳瓦特尔语:Nahuatlacah;西班牙语:Nahuas)指的是位在墨西哥中部使用阿兹特克方言—纳瓦特尔语的族群。其为墨西哥最大的美洲原住民族群(1990统计人数为1,197
  • 原台北酒厂华山1914文化创意产业园区(又名华山1914文创园区或华山1914,英语:Huashan 1914 Creative Park),园区前身为“台北酒厂”,为台湾台北市市定古迹。在1999年后,成为提供给艺文界、非营
  • 台湾水库台湾境内之河川由于地势陡峻,河床比降极大,遇雨则山洪暴涨,泛滥成灾,逢旱则干涸见底,用水缺乏,唯一治本之道为兴筑水库水坝,以达到有效治理河川,蓄水,增加灌溉、发电、工业及公共给水
  • 美国世界社会党美国世界社会党(英语:World Socialist Party of the United States)是美国的一个极左翼政党。该党成立于1916年7月7日,分裂自美国社会党。该党的意识形态是不可能主义、社会主义
  • 法兰西岛快速有轨电车11号线法兰西岛快速有轨电车11号线(法语:Ligne 11 Express du tramway d'Île-de-France), 简称电车11号线, 是法国巴黎北郊的一条有轨电车线路, 属于法兰西岛远郊铁路Transilien, 将
  • 春日局春日局(1579年-1643年10月26日),本名斋藤福,父亲是明智光秀的家臣斋藤利三,母亲是稻叶一铁(良通)之女。后来成为江户幕府三代将军德川家光的乳母,奉命前往皇宫觐见后水尾天皇,得到天皇
  • 托马斯·科斯基托马斯·科斯基(斯洛伐克语:Tomáš Košický;1986年3月11日-)是一位斯洛伐克足球运动员。在场上的位置是守门员。他现在效力于希腊足球超级联赛球队阿斯特拉斯特里波利斯。他也