Python: 为遗传算法排序列表中的部分元素

Question

我想使用遗传算法解决作业车间调度问题，代码将在 Python 中编写。

目前，我将个人呈现为 [job, operation, machine, operation] 的列表。例如，这里是一条染色体的例子：

jobs = [ [1,3,3,2], [3,3,1,3], [1,1,1,4], [2,2,1,4], [2,3,3,4], [3,1,3,3], [2,1,2,1], [1,2,2,3], [3,2,2,2]  ]

列表必须满足每个作业的操作优先级约束，例如列表中作业 1 的正确顺序是

[1,1,1,4], [1,2,2,3], [1,3,3,2]

换句话说，我必须仅在其他作业保留在其位置时对作业 1（索引 0、索引 2 和索引 7）进行排序。正确的结果将是：

jobs = [ [1,1,1,4], [3,3,1,3], [1,2,2,3], [2,2,1,4], [2,3,3,4], [3,1,3,3], [2,1,2,1], [1,3,3,2], [3,2,2,2]  ]

我目前的尝试：

Determine/filter 包含作业 1 的所有行：

[row[:][:] for row in jobs if row[0]==1]

输出

[[1, 1, 1, 4], [1, 2, 2, 3], [1, 3, 3, 2]]

Answer 1

执行此操作的直接方法是制作一个具有所需作业编号的临时作业列表，然后对该临时列表进行排序。然后您需要将原始项目替换为已排序的项目，并且要正确执行此操作，您需要跟踪它们在工作列表中的位置。

j0 = [[1,3,3,2], [3,3,1,3], [1,1,1,4], [2,2,1,4], [2,3,3,4], 
    [3,1,3,3], [2,1,2,1], [1,2,2,3], [3,2,2,2]]
print(j0)

j1 = [[1,1,1,4], [3,3,1,3], [1,2,2,3], [2,2,1,4], [2,3,3,4], 
    [3,1,3,3], [2,1,2,1], [1,3,3,2], [3,2,2,2]]
print(j1)

def sortjob(alljobs, jobnum):
    #get jobs with this jobnum
    indices = []
    jobs = []
    for i, v in enumerate(alljobs):
        if v[0] == jobnum:
            indices.append(i)
            jobs.append(v)

    jobs.sort()
    #put the sorted jobs back into the correct locations
    for i, v in zip(indices, jobs):
        alljobs[i] = v

sortjob(j0, 1)
print(j0)

输出

[[1, 3, 3, 2], [3, 3, 1, 3], [1, 1, 1, 4], [2, 2, 1, 4], [2, 3, 3, 4], [3, 1, 3, 3], [2, 1, 2, 1], [1, 2, 2, 3], [3, 2, 2, 2]]
[[1, 1, 1, 4], [3, 3, 1, 3], [1, 2, 2, 3], [2, 2, 1, 4], [2, 3, 3, 4], [3, 1, 3, 3], [2, 1, 2, 1], [1, 3, 3, 2], [3, 2, 2, 2]]
[[1, 1, 1, 4], [3, 3, 1, 3], [1, 2, 2, 3], [2, 2, 1, 4], [2, 3, 3, 4], [3, 1, 3, 3], [2, 1, 2, 1], [1, 3, 3, 2], [3, 2, 2, 2]]

请注意，sortjob 会修改您传递给它的列表，就像 list.sort 方法所做的那样，并与此类函数的 Python 约定保持一致 sortjob returns None.

Python: 为遗传算法排序列表中的部分元素

Python: Ordering partial elements in List for Genetic Algorithm

python

list

partial-ordering