作业车间调度问题求解框架：遗传算法¶

发布于：2024-04-13 | 分类：optimization , mathematics

本文根据作业车间调度问题的析取图描述，基于遗传算法工具箱Geatpy，实现 jsp_framework 的遗传算法求解器。

编码方式¶

染色体编码采用文献¹中的描述方式：

染色体长度为所有作业的总工序数，每个基因表示作业编号（因此基因数值可能重复）；因此不同值的基因表征作业的先后顺序，相同值的基因表征同一作业内工序的顺序。

每个作业的工序都是先后依次调度的，因此这种编码方式保证了每一个解都是可行的，进而不必考虑交叉、变异等操作带来不可行解的问题。

以3作业x2工序为例，染色体编码 1 2 3 3 2 1 中第一个 1 和最后一个 1 分别表示作业 1 的第1个和第2个工序。完整的调度顺序为：

作业1工序1 -> 作业2工序1 -> 作业3工序1 -> 作业3工序2 -> 作业2工序2 -> 作业1工序2

以上方式本质是按作业编号编码，然后解码为天然满足可行解的工序编号。为了 方便使用全排列方式生成染色体，本文进一步将上述按作业编码方式改为按工序编码。此时，虽然某个染色体可能是非法解，但解码过程先按工序所属作业将其映射回作业编号，再按前述方式映射回满足可行解的工序编号。

还是3作业x2工序的例子，假设所有工序依次编号，即 1-6 分别表示作业1工序1，作业1工序2，作业2工序1，作业2工序2，... 那么某个染色体，例如 2 3 5 6 4 1，

直接调度是非法的，因为工序2不可能在工序1尚未完成的情况下开始；
应该先根据作业从属关系先解码为作业编号即 1 2 3 3 2 1，接下来和前述相同的逻辑解码为最终的工序顺序。

Geatpy 建模¶

Geatpy（The Genetic and Evolutionary Algorithm Toolbox for Python with high performance）是一个高性能实用型进化算法工具箱，提供高度模块化、耦合度低的面向对象的进化算法框架。利用“定义问题类 + 调用算法模板”的模式，优化求解单目标优化、多目标优化、复杂约束优化、组合优化、混合编码进化优化等各类问题²。

（1）定义问题类¶

根据 Geatpy 用法介绍，我们先定义一个普通的 Geatpy 问题类，

提供变量信息如维度、类型（连续、离散）、上下界等，以及
目标函数 evalVars()——根据前述染色体编码计算目标函数即整个加工周期。

import geatpy as ea

class GeatpyProblem(ea.Problem):
    '''Geatpy problem.'''

    def __init__(self,
                 name:str,
                 var_type:int,
                 dim:int,
                 lb:List[float],
                 ub:List[float],
                 solver:"IGeatpySolver") -> None:
        '''Geatpy problem.

        Args:
            name (str): problem name.
            var_type (int): variable type, 0-continuous, 1-integer.
            dim (int): variables dimension.
            lb (float): low bounds
            ub (float): upper bounds.
            solver (JSSolver): solver.
        '''
        self.__solver = solver
        super().__init__(name=name,
                         M=1, # number of objectives
                         maxormins=[1],  # 1：minimize, -1-maximize
                         Dim=dim,
                         varTypes=[var_type]*dim, # 0-continuous, 1-integer
                         lb=lb,
                         ub=ub,
                         lbin=[1]*dim,
                         ubin=[1]*dim)


    def evalVars(self, inputs:np.ndarray):
        '''Objective function.'''
        solutions =  [self.__solver.decode(x=x) for x in inputs]
        cost = np.array([p.makespan for p in solutions])
        return cost.reshape((-1,1)) # shape: (m,n)

（2）定义遗传算法求解器基类¶

从上面代码可以看到，为了计算目标函数，我们引入了基于 Geatpy 的遗传算法求解器基类 IGeatpySolver 及其根据染色体生成相应 JSSolution 的方法 decode(x)。

根据前文自定义求解器的描述，我们重点实现 do_solve() 即可，也就是在这里调用 Geatpy 的算法模板，例如 ea.soea_SEGA_templet() 。Geatpy 算法模板的第一个参数即为前一步定义的问题实例，为了保留灵活性（例如使用不同编码求解这个问题），这里选择定义一个虚函数 init_problem() 来创建问题实例。

综上，do_solve() 的基本步骤：

虚函数 init_problem() 定义问题类，提供变量信息如维度、类型、上下界；
调用 Geatpy 算法模板求解，提供种群信息例如 编码方式 和种群大小；
虚函数 decode() 根据最优个体计算得到 JSSolution 实例；
update_solution() 显式更新最优解。

Geatpy 支持的染色体编码方式：

'BG'：二进制/格雷编码；
'RI'：实整数编码，即实数和整数的混合编码；
'P'：排列编码。

from abc import (ABC, abstractmethod)
from ..model.solver import JSSolver

class IGeatpySolver(JSSolver, ABC):
    '''Genetic Algorithm solver with geatpy.'''

    def __init__(self,
                 name:str=None,
                 problem:JSProblem=None,
                 encoding:str='P',
                 pop_size:int=32,
                 epoch:int=None,
                 max_time:int=None) -> None:
        '''GA solver with geatpy.

        Args:
            name (str, optional): solver name. Defaults to None.
            problem (JSProblem, optional): problem to solve. Defaults to None.
            encoding (str, optional): geatpy GA encoding.
            pop_size (int, optional): population size. Defaults to 32.
            epoch (int, optional): max generation. Defaults to 10.
            max_time (int, optional): Max solving time in seconds. Defaults to None, i.e., no limit.
        '''
        JSSolver.__init__(self, name=name, problem=problem, max_time=max_time)
        self.__pop_size = pop_size
        self.__epoch = epoch
        self.__encoding = encoding
        self.__best = None

    ...

    @abstractmethod
    def init_problem(self) -> GeatpyProblem:
        '''Initialize problem in geatpy framework.'''


    @abstractmethod
    def decode(self, x:List[int]) -> JSSolution:
        '''Convert encode to JSSolution instance.

        Args:
            x (List[int]): encode scheme for GA.
        '''

    def do_solve(self):
        # create geatpy problem to solve
        problem = self.init_problem()

        # algorithm
        algorithm = ea.soea_SEGA_templet(problem,
                ea.Population(Encoding=self.__encoding, NIND=self.__pop_size),
                MAXGEN=self.__epoch, # stop when reaching the max generation or max time
                MAXTIME=self.max_time,
                outFunc=self.check_better_solution,
                logTras=1,
                verbose=False,
                drawing=0)

        # solve
        self.__best, _pop = algorithm.run()
        solution = self.decode(self.best_phenotype)
        self.update_solution(solution)

（3）最终实现¶

最后，定义遗传算法求解器类 GAGeatpySolver，实现本文开头描述的编码方式。

class GAGeatpySolver(IGeatpySolver):
    '''General encode method for JSSP.'''

    def init_problem(self) -> None:
        dim = len(self.problem.ops)
        return GeatpyProblem(name=self.name,
                             var_type=1, # 0-continuous, 1-integer
                             dim=dim,
                             lb=[0]*dim,
                             ub=[dim-1]*dim,
                             solver=self)


    def decode(self, x:List[int]) -> JSSolution:
        '''Convert permutation code to JSSolution instance.

        Args:
            x (List[int]): permutation of operation index.
        '''
        solution = self.init_solution(direct_mode=False)

        # group operation with job id
        job_ops = defaultdict(list) # type: List[OperationStep]
        for op in solution.ops:
            job_ops[op.source.job.id].append(op)

        # convert operation sequence to job sequence to
        # avoid unavailable permutation
        ops = self.problem.ops
        job_sequence = [ops[i].job.id for i in x]

        # dispatch
        ops = [job_ops[i].pop(0) for i in job_sequence]
        solution.dispatch(ops=ops)
        return solution

计算实例¶

最后，求解几个标准问题。与前面几类求解器一样，求解时间上限设定为300秒。

# benchmark.py
from jsp import (JSProblem, BenchMark)
from jsp.solver import GAGeatpySolver

# problems
names = ['ft06', 'la01', 'ft10', 'swv01', 'la38', \
        'ta31', 'swv12', 'ta42', 'ta54', 'ta70']
problems = [JSProblem(benchmark=name) for name in names]

# solver
solvers = [GAGeatpySolver(pop_size=64, epoch=20, max_time=300)]

# solve
benchmark = BenchMark(problems=problems, solvers=solvers, num_threads=5)
benchmark.run(show_info=True)

结果如下表所示。从结果来看，当总工序数超过100后，效果就不是很理想了。猜测和当前编码方式有关，定制针对此类问题的编码方式和遗传算子或许可以改善这个问题。

+----+---------+----------------+---------------+--------------+----------+---------+-------+
| ID | Problem |     Solver     | job x machine |   Optimum    | Solution | Error % |  Time |
+----+---------+----------------+---------------+--------------+----------+---------+-------+
| 1  |   ft06  | GAGeatpySolver |     6 x 6     |      55      |   55.0   |   0.0   |  43.5 |
| 2  |   la01  | GAGeatpySolver |     10 x 5    |     666      |  668.0   |   0.3   |  53.9 |
| 3  |   ft10  | GAGeatpySolver |    10 x 10    |     930      |  1065.0  |   14.5  |  67.9 |       
| 4  |  swv01  | GAGeatpySolver |    20 x 10    |     1407     |  1966.0  |   39.7  | 130.3 |       
| 5  |   la38  | GAGeatpySolver |    15 x 15    |     1196     |  1526.0  |   27.6  | 154.0 |       
| 6  |   ta31  | GAGeatpySolver |    30 x 15    |     1764     |  2429.0  |   37.7  | 302.0 |       
| 7  |  swv12  | GAGeatpySolver |    50 x 10    | (2972, 3003) |  4722.0  |   58.1  | 301.5 |       
| 8  |   ta42  | GAGeatpySolver |    30 x 20    | (1867, 1956) |  2941.0  |   53.9  | 301.6 |       
| 9  |   ta54  | GAGeatpySolver |    50 x 15    |     2839     |  3672.0  |   29.3  | 300.9 |       
| 10 |   ta70  | GAGeatpySolver |    50 x 20    |     2995     |  4337.0  |   44.8  | 300.8 |       
+----+---------+----------------+---------------+--------------+----------+---------+-------+

Guoyong Shi, H. Iima and N. Sannomiya, "A new encoding scheme for solving job shop problems by genetic algorithm," Proceedings of 35^th IEEE Conference on Decision and Control, Kobe, Japan, 1996, pp. 4395-4400 vol.4, doi: 10.1109/CDC.1996.577484. ↩
https://github.com/geatpy-dev/geatpy ↩

Keys	Action
`?`	Open this help
`n`	Next page
`p`	Previous page
`s`	Search