基于免疫球蛋白理论的算法设计及其在复杂系统中的组合优化研究

Recently, Artificial Immune System (AIS) is a popular algorithm due to its high performance. AIS can solve most of complex combination optimization problems i.e. scheduling, capacity planning and inventory. However, most of AISs are not so flexible and have a blind side in search ability. A new immunoglobulin AIS (IAIS) is proposed in this research. Somatic recombination and isotype switching are taken into account in the proposed IAIS. Somatic recombination is to increase diversity of antibodies and isotype switching is to strength the search ability. These features are first proposed and can enhance efficiency of IAIS. Besides, to evaluate IAIS, we use other algorithms as comparisons by simulation. This research can help to intensify IAIS and then import it to the practice.

近年來，人工免疫系统已成为国内外专家学者研究的热点。作为人工智能领域内先进的高效分布式并行信息处理系统，该系统可以处理复杂程度较高的组合优化问题，如生产排程、产能规划以及存货等。但是，现有人工免疫系统的架构理论性较强，存在搜寻盲点，而且实用性较差。本项目力求在已有研究的基础上提出一种全新的人工免疫系统并在实践中进行验证。本算法的创新之处在于：(1)体细胞重组，增加抗体的多样性；(2)类型转换过程，加强抵抗病毒的能力。此两特性是首次提出的理论，基于真实免疫系统中的免疫球蛋白来做为算法的依据，且可以帮助人工免疫系统克服搜寻盲点。我们拟将该算法用于混合流水车间调度与越库作业等的组合优化问题中，并找出不同编码方式来求解这两个复杂的问题。此外，使用仿真模拟等方法对该算法进行比选分析。本项目的研究将有助于我国学者把握国际前沿理论，深化我国生产调度理论的研究，实现有限资源的优化配置。

人工免疫系统研究对大型复杂企业各类生产调度问题的求解具有实际意义，但这种方法的架构理论性较强，且存在部分搜寻盲点。项目研究对真实人类免疫系统深入探究并借鉴已有的文献成果，提出一种新的符合生产实际的人工免疫算法（IAIS），并以生产调度与越库作业等较为复杂的组合优化问题为例，针对实际问题做仿真模拟，为相关研究提供研究范例。. 基于真实人类免疫系统，IAIS算法创新性的在遇到病原前引入体细胞重组，增加了抗体的多样性；在遇到病原后，类型转换过程的提出加强了抵抗病毒的能力。这是与传统AIS算法的不同之处。. 在混合流水车间调度问题研究中，采用Carlier和Néron提出的著名基准问题测试IAIS算法，结果表明，IAIS优于除AIS外的其他算法。新基准问题下，用偏差百分比评估IAIS和AIS间的差距，表明IAIS算法能有效地产生更好的解，且鲁棒性好。. 在越库作业问题研究中，为了使出货口卡车的总延迟最小化，提出一种IS-AIS算法，以相同的概率从IgA，IgE和IgG三种不同的搜索方法中选一种进行局部搜索，以产生较优解。试验证明，与SA和TaBu算法相比，IS-AIS在运行时间和目标函数的实现方法上均具有一定的优越性。. 为了进一步验证IAIS算法的通用性、快速性，研究提出多种改进算法，以现有的人工免疫系统与其它现代启发式算法作为验证依据，建立仿真模型并设计模拟实验，获得一系列成果如下：. 通过调整IAIS算法结构得到的PST算法和考虑一种特殊记忆B细胞的二次免疫响应过程形成的B-IAIS算法能较好地应用于生产与运输两阶段供应链调度问题；为更好地适应人类免疫系统，加入B细胞库更新特殊过程而产生的M-IAIS算法在置换流水车间调度问题求解中有很好的鲁棒性，且收敛速度快；将IgD作为第四种种型转换而得到的SIAIS算法，在有限缓冲区的流水车间调度问题中表现出较好的搜索能力；采用不同编码与解码方式，提出基于序列的SBIAIS算法和基于批次的BBIAIS算法，应用于带有等待时间约束的两阶段混合流水车间分批调度问题中，引用方差分析，证明这些算法较PSO算法及VNS算法是稳定有效的。