logoChat01.ai

PMX交叉法解析

创建于：2024年12月10日

使用 O1 回答 Chat01

问题

针对两个染色体：135246和243561，自左向右依次对应任务1-6，采用部分匹配交叉法，交叉点是第3位和第5位，写出交叉后的一对染色体。要求：如果染色体中出现重复任务，则按照交叉区域内的位置映射关系进行交换 请你以老师的角度对此问题进行详细解答

思考

Examining cross points

I’m working through applying Partially Mapped Crossover (PMX) to chromosomes 135246 and 243561. The crossover points are at positions 3 and 5, focusing on segments from positions 3 to 5.

Copying segments

I’m working on PMX by copying segments from parent chromosomes P1 and P2, then sequentially inserting non-duplicate elements from P1 into the offspring's remaining positions.

Inserting and checking

I’m placing tasks from the leftover set of P1 into offspring O1, completing the blank spaces. Next, I’ll confirm no conflicts arise by checking the mapping relationship in the crossover segment.

Ensuring alignment

I’m piecing together the PMX process, ensuring the gene mapping between parent and offspring segments remains consistent and conflicts are resolved by sequencing tasks from P2 to fill gaps.

Clarifying PMX steps

I’m detailing the standard PMX procedure: copying a segment from parent P1 to offspring, mapping genes from parent P2 to offspring while resolving conflicts by finding free spots, and ensuring no duplicates.

Transcribing and integrating

I’m copying a segment from parent P1 to offspring O1, then sequentially analyzing parent P2's genes to fill in gaps, avoiding duplicates and ensuring alignment with P1's mapped relationships.

Mapping genes

I’m ensuring each gene from parent P2 is positioned correctly in offspring O1, aligning with the mapping from parent segments and filling in gaps to avoid duplicates.

Mapping genes

I’m working through mapping genes from the selected segments of parents P1 and P2, resolving conflicts, and carefully filling offspring O1's remaining positions without introducing duplicates.

Resolving conflicts

I’m figuring out how to handle '2' from P2, which conflicts with '2' already in O1. By PMX rules, I’ll map '2' to its corresponding element from P1's segment.

Tracing gene movements

I’m showing how '2' is mapped to '5', which then maps to '3'. This chain mapping ensures the gene is placed in offspring O1 without causing duplicates or conflicts.

Placing genes

First, I place '4' in O1 by mapping it to '6'. Then, I put '1' directly into position 6, completing offspring O1 without any conflicts.

Inserting genes

I'm placing '1' in O2's first position, '3' in its second spot, and '6' in the sixth, avoiding duplicates by aligning each gene with its mapped counterpart.

Piecing it together

I’m mapping gene '3' to '5', then from '5' to '2', and further from '2' to '5'. This confirms the symmetrical mapping ties up the sequence nicely.

Clarifying gene mapping

OK, let me see. The mapping pairs, like (5,3), (2,5), and (4,6), align genes from each parent's segment. Now, I realize these pairs ensure precise gene placement in the offspring.

Mapping gene conflicts

OK, let me see. If a leftover gene from P1 causes a duplicate in O2, I’ll replace it with its mapped counterpart from either P1 or P2’s segment pairs.

Mapping gene flow

I’m digging into a PMX example: if '3' is a duplicate in O2, I’ll locate its pair, like (5,3), and insert '5' instead, ensuring each gene finds a unique spot.

Tracking the mapping

I’m ensuring each leftover gene from P1 uniquely slots into O2 by tracing the mapping pairs, like (5,3) and (2,5), preventing duplicates and aligning with PMX principles.

Placing genes

I'm placing '2' in O2 at position 2, avoiding conflicts with existing genes. Next, I'll map '6' to '4' and check for duplicates in O2, ensuring a unique fit.

Mapping genes

I’m thinking through copying P1's segment to O1, then addressing conflicts with P2's genes using PMX pairs, ensuring each gene's unique placement.

Navigating conflicts

I’m diving into PMX procedures to manage conflicts, iteratively testing each parent gene's mapping until finding a unique placement for P2's gene, ensuring no duplicates in O1.

Balancing the equation

I’m thinking through the bidirectional gene mapping pairs and iteratively adjusting PMX instructions to prevent duplicates in O1. Each step involves swapping genes across pairs to streamline conflict resolution.

Mapping gene swaps

I’m working through PMX by alternating gene swaps between P1 and P2 pairs to resolve conflicts and find a free gene for O1. This approach ensures a unique and conflict-free placement.

Piecing together PMX steps

I’m piecing together the PMX process: copying a middle segment from P1 to O1, then meticulously placing P2's genes to align with P1's mapping, ensuring no duplicates or conflicts.

Integrating a formal approach

I’m detailing the PMX steps to ensure a precise and conflict-free gene mapping for O1 by carefully placing P2's genes to align with P1's mapping, even if it means alternating placements to avoid duplicates.

Mapping gene positions

I’m figuring out where to place '3' in O1, which replaced '5' in P1. It should go at '5's' spot in P2. PMX rules guide this gene mapping carefully.

Mapping out gene distribution

I'm pulling together the key steps of the PMX process: copying segments, mapping genes, and filling gaps with non-duplicate genes from P2, ensuring a unique and conflict-free arrangement in O1.

Placing and adjusting

I’m placing P2 genes into O1's empty slots, addressing duplicates using PMX pairs. For instance, '2' from P2 swaps with '5', aligning '5' and '3' in P1.

Completing offspring patterns

OK, let's finalize offspring O1 and O2 by aligning P1 and P2 genes, checking for duplicates, and ensuring diversity and consistency in their respective gene arrangements.

Thought about 部分匹配交叉法，持续 1m 11s

回答

下面给出详细的解题步骤和讲解。为便于说明，我们将染色体的位置编号为1至6，对应题中所述的任务1-6。在部分匹配交叉（Partially Mapped Crossover, PMX）中，我们需要按照指定的交叉点，对两个父代染色体进行部分基因片段的互换，同时利用映射规则来处理重复出现的任务。

题中给定条件：
父代染色体为：
P1 = 1 3 5 2 4 6
P2 = 2 4 3 5 6 1

交叉点为第3位和第5位，这意味着我们选定位置3到位置5作为交叉片段。
染色体位置标记：
位置: 1 2 |3 4 5| 6
P1: 1 3 |5 2 4| 6
P2: 2 4 |3 5 6| 1

划线处为交叉片段区域。
P1的交叉片段（位置3到5）为：[5, 2, 4]
P2的交叉片段（位置3到5）为：[3, 5, 6]

PMX的基本步骤：

  1. 从父代P1中将交叉片段(第3至5位)直接复制到子代O1的对应位置。

  2. 从父代P2中将交叉片段(第3至5位)直接复制到子代O2的对应位置。

  3. 利用该片段在P1与P2之间建立映射关系。对于位置3到5的三个基因，两条染色体形成以下映射对：(P1基因 ↔ P2基因)

    • 第3位：5 ↔ 3
    • 第4位：2 ↔ 5
    • 第5位：4 ↔ 6

    因此映射关系有三对：
    5 ↔ 3
    2 ↔ 5
    4 ↔ 6

    此映射是双向的，即需要时可以从P1侧或P2侧进行替换。

  4. 将非交叉片段位置用另一个父代中对应的元素填充，如果出现重复任务(即该任务已在子代中出现)，则根据映射关系寻找合适的替代基因，直到找到不冲突的基因为止。

为子代O1构造：

  • 第一步：将P1的交叉片段[5,2,4]直接放入O1的3-5位。
    O1初始为： [?, ?, 5, 2, 4, ?]

  • O1中还需填充的位置是1, 2, 6位。
    我们使用P2来填充这些位置（除去P2已用于交叉片段的基因）。
    P2原序列为：2 4 3 5 6 1
    已用的交叉片段是[3,5,6]，剩余可用于填充的有2、4、1（按P2原来从左到右的顺序尝试填入）。

    填充O1的第1位：
    尝试放入P2的首个剩余基因——2。
    检查O1中是否已有2？O1中已有2（在第4位）。冲突！
    根据映射寻找替代：2与谁映射？
    映射对中有(2 ↔ 5)。2在P1侧对应5在P2侧，这意味着当2冲突时，我们尝试用它的映射对象5来替代。
    检查5是否在O1中？O1中已有5（第3位）。仍冲突！
    继续根据映射找5的对应：5 ↔ 3。
    检查3是否在O1中？目前O1为[?, ?, 5,2,4, ?]并无3。
    因此我们最终在第1位放入3。
    O1变为：[3, ?, 5, 2, 4, ?]

    填充O1的第2位：
    下一个P2剩余基因为4。
    检查O1中是否已有4？已有（第5位）。冲突！
    找映射：4 ↔ 6。
    检查6是否在O1中？目前O1没有6。
    因此在第2位放入6。
    O1变为：[3, 6, 5, 2, 4, ?]

    填充O1的第6位：
    最后一个剩余可用的P2基因为1。
    检查O1中是否已有1？没有。
    直接放入第6位。
    O1变为：[3, 6, 5, 2, 4, 1]

thus O1 = 3 6 5 2 4 1

为子代O2构造：

  • 首先将P2的交叉片段[3,5,6]放入O2的3-5位。
    O2初始为：[?, ?, 3, 5, 6, ?]

  • O2需要填充的位置是1, 2, 6位。
    这次用P1除交叉片段外的基因来填。
    P1原序列：1 3 5 2 4 6
    已用交叉段是[5,2,4]，剩余可用有1、3、6按照P1的顺序用于填补O2空位。

    填充O2的第1位：
    尝试放入1。
    检查O2是否已有1？O2中有[3,5,6]，没有1。
    直接放入：O2 = [1, ?, 3,5,6, ?]

    填充O2的第2位：
    尝试放入3。
    O2中已有3（第3位）。冲突！
    找映射：3 ↔ 5（因为5 ↔ 3成对）。
    检查5是否在O2中？已有5（第4位）。再次冲突！
    再次映射5 ↔ 2。
    检查2是否在O2中？O2目前为[1, ?, 3,5,6, ?]，无2。
    可用2来代替3。
    在第2位放入2：O2 = [1, 2, 3,5,6, ?]

    填充O2的第6位：
    最后尝试放入剩余的6（来自P1的剩余基因顺序中下一个是6）。
    O2已有6（第5位）。冲突！
    找6的映射：6 ↔ 4。
    检查O2是否有4？无。
    可放4在第6位。
    O2 = [1, 2, 3,5,6,4]

thus O2 = 1 2 3 5 6 4

结果检验：
O1 = [3, 6, 5, 2, 4, 1]
O2 = [1, 2, 3, 5, 6, 4]

两条子代染色体各包含1至6的所有任务且无重复，这是有效的交叉结果。

总结：
通过上述步骤，我们利用PMX在指定的交叉点对父代染色体进行部分片段交换，并通过建立交叉片段内部的映射关系来解决重复基因冲突问题，最终得到的子代染色体为：

  • 子代1（O1）：3 6 5 2 4 1
  • 子代2（O2）：1 2 3 5 6 4

这便是应用部分匹配交叉法（PMX）后的一对新染色体解答流程及最终答案。

分享这个问答