论文部分内容阅读
针对作业车间调度问题(JSP)的非确定性多项式特性与解空间分布的大山谷属性,本文提出一种多智能体遗传算法(MAGA)与自适应模拟退火算法(ASA)的混合优化算法,用于寻找最大完工时间最短的调度。首先,将每个染色体视作独立的智能体并采用工序编码方式随机初始化每个智能体,结合多智能体协作与竞争理论设计了实现智能体之间交互作用的邻居交互算子,进而利用一定数量智能体进行全局搜索,找到多个适应度较高的可行解。其次,为避免算法陷入局部最优,采用ASA对每个智能体开展局部寻优。最后,通过基准测试库中典型实例的计算结果验证了该算法的有效性。
Aiming at the nondeterministic polynomial properties of job shop scheduling problem (JSP) and the properties of big valley with solution space distribution, a hybrid optimization algorithm of multi-agent genetic algorithm (MAGA) and adaptive simulated annealing algorithm (ASA) To find the maximum scheduling time of the shortest. First of all, each chromosome is regarded as an independent agent and each agent is initialized at random by using process coding. The interaction between agents and agents is designed based on the collaboration and competition theory of multi-agents. Then, The number of agents conducts a global search to find more feasible solutions with higher fitness. Secondly, to avoid the algorithm getting into the local optimum, ASA is used to perform local optimization on each agent. Finally, the validity of this algorithm is verified by the results of typical examples in the benchmark test library.