混合遗传-免疫算法解决流水车间调度问题

需积分: 10 155 浏览量更新于2024-10-21 收藏 324KB PDF 举报

"本文提出了一种混合遗传-免疫算法(HGIA)，用于解决流动车间调度问题，该算法在第一阶段采用常规遗传算法快速进化，当过程收敛到预定义的迭代次数后，第二阶段引入人工免疫系统(AIS)与遗传算法(GA)进行混合，通过协同进化过程持续搜索最优解。在协同进化过程中，GA负责搜索适应度函数，而AIS则以抗原的形式激发抗体的抵抗。在对抗过程中，抗体将进化以抵抗抗原。此外，还提出了一种改进的生命周期生存策略，以延长抗体的生命周期，从而使选择的抗体能留在系统中更长时间，提高搜索效率和解决问题的能力。" 流动车间调度问题是一个经典的优化问题，涉及到如何在多台机器上安排一系列作业，以最小化总完成时间或满足其他特定目标。传统的遗传算法(GA)是一种基于生物进化理论的全局优化方法，通过模拟自然选择、交叉和变异等机制来搜索解决方案空间。然而，遗传算法在局部搜索能力和避免早熟收敛方面可能存在局限。人工免疫系统(AIS)是受到生物免疫系统启发的计算模型，它具有学习、记忆和适应性等特点。在解决调度问题时，AIS可以提供更复杂的搜索策略，例如模拟抗体和抗原之间的相互作用，有助于跳出GA可能陷入的局部最优。混合遗传-免疫算法(HGIA)结合了GA和AIS的优势，通过GA在初始阶段快速探索大范围解决方案，然后AIS深入挖掘局部最优，增强算法的全局搜索性能。在HGIA中，抗原(来自GA的个体)激发抗体的生成，抗体代表潜在的解决方案。随着算法的进行，抗体不断进化以适应和抵抗抗原，这有助于找到更优解。此外，改进的生命周期策略是HGIA的一个关键组成部分。通常，遗传算法中的选择压力可能导致早期优良解的丢失，而延长抗体的生命周期可以防止这种现象，确保算法在搜索过程中保持多样性和长期记忆，从而提高找到全局最优解的可能性。 "Hybrid Genetic-Immune Algorithm with Improved Offsprings and Elitist Antigen for Flow-Shop Scheduling Problems" 这篇文章提出了一种创新的混合优化算法，旨在有效解决流动车间调度问题，通过结合遗传算法和人工免疫系统的特性，提高了搜索效率和问题解决能力。这种方法不仅对调度领域有重要的应用价值，也为其他复杂的优化问题提供了一种可能的解决方案框架。

A Hybrid Genetic-Immune Algorithm with Improved Offsprings and

Elitist Antigen for Flow-shop Scheduling Problems

Pei-Chann Chang, Wei-Hsiu Huang, Ching-Jung Ting, Ling-Chun Wu, Chih-Ming Lai



Abstract—In this paper, a Hybrid Genetic-Immune algorithm

(HGIA) is developed to solve the flow-shop scheduling

problems. The regular genetic algorithm is applied in the

first-stage to rapidly evolve and when the processes are

converged up to a pre-defined iteration then the Artificial

Immune System (AIS) is introduced to hybridize Genetic

Algorithm (GA) in the second stage. Therefore, HGIA

continues to search optimal solution via co-evolutional

process. In the co-evolutionary process, GA and AIS

cooperate with each other to search optimal solution by

searching different objective functions. One is named fitness

in GA section and another one is named antigen which will

evoke the withstanding of antibodies. In the process of

fighting, the antibodies will evolve till they can resist the

antigen. An improved survival strategy of lifespan is also

proposed to extend the lifespan of the antibodies as a result

the selected antibodies will stay in system longer. The hybrid

of GA and AIS can simultaneously contain two objectives.

Hence, larger searching space and escaping from local

optimal solution will be the superiority for hybridizing GA

and AIS. In the research, a set of flow-shop scheduling

problems are applied for validating the efficiency. The

intensive experimental results show the effectiveness of the

proposed approach for Flow-shop problems in Production

Scheduling.

NTRODUCTION

ombinatorial optimization problems (COPs) are usually

problems with high complexity, numerous algorithms

were proposed for applying to this specific problem. Tsai et al.

[3] and Chun et al. [2] had mentioned the algorithms for

global optimization problems are of increasing importance in

modern engineering design and systems operation in various

areas. In solving global optimization problems, the particular

challenge is that an algorithm may be trapped in the local

optima of the objective function when the dimension is high

and there are numerous local optima. Genetic algorithms,

powerful tools based on biological mechanisms and natural

selection theory, have received considerable attention

regarding its potential as an optimization technique for

complex problems and have been successfully applied in

various areas. The main specific feature of the GAs as an

optimization method is their implicit parallelism, which is a

result of the evolution and the hereditary-like process. But

GAs have two main drawbacks. One is lack of the local

search ability and another is the premature convergence.

Therefore, more algorithms were proposed for solving the

phenomenon, initially, the improvements in the GAs have

been sought in the optimal proportion and adaptation of the

main parameters, namely probability of mutation, probability

of crossover, population size, and crossover operator.

Therefore, some researchers have proposed several

GA-based approaches to solve the phenomenon, one of these

proposed GA-based algorithm is hybrid Genetic Algorithm

and Immune System. The organisms named antibodies in the

immune system which are responsible for protecting the body

to against harmful organisms named antigen. Campelo [1]

mentioned the immune system is able to detect a huge number

of antigens using a fairly limited repertory of gene

combinations. To carry out this recognition task, segments of

genes are combined to accomplish the specificity of almost all

the invader antigens known. A self-recognition task keeps the

immune system from attacking itself, because immune cells

are capable of recognizing themselves. All these features of

the immune system provide, in consequence, great robustness,

fault tolerance, dynamism, and adaptability. These are

precisely the properties of the immune system that encourage

researchers to try to emulate it in a computer, proposed by

Coello [7].

Deng et al. [9] had proposed an approach for establishing

optimization model for Immune System (IS). IS has an

important characteristic which is name Lifespan which will

keep better chromosomes live longer than others with worse

specific lifespan. This idea helps chromosomes with different

objective function stay longer, that is, the chromosomes

would not be kept just by one objective, it is also possible to

consider the second objective which is relative or not to the

main objective. Therefore, the hybrid of GA and AIS can

simultaneously contain two objectives. Hence, larger

searching space and escaping from local optimal solution will

be the superiority for hybridizing GA and AIS.

Pei-Chann Chang is with the Department of Information Management,

Yuan Ze University, Taoyuan 32026, Taiwan, R.O.C.

(Corresponding Author’s E-mail: iepchang@saturn.yzu.edu.tw).

Wei-Hsiu Huang is with the Department of Industrial Engineering and

Management, Yuan Ze University, Taoyuan 32026, Taiwan, R.O.C.

Ching-Jung Ting is with the Department of Industrial Engineering and

Management, Yuan Ze University, Taoyuan 32026, Taiwan, R.O.C.

For taking advantage of the characteristics of hybrid,

HGIA is proposed for solving Production Scheduling

problems. The proposed approach contains some special

characteristics. Firstly, a two-phase evolving architecture is

Ling-Chun Wu is with the Department of Industrial Engineering and

Management, Yuan Ze University, Taoyuan 32026, Taiwan, R.O.C.

Chih-Ming Lai is with the Department of Information Management, Yuan

Ze University, Taoyuan 32026, Taiwan, R.O.C.

2009 11th IEEE International Conference on High Performance Computing and Communications

DOI 10.1109/HPCC.2009.68

591

Authorized licensed use limited to: The University of Hong Kong. Downloaded on February 18,2010 at 02:46:32 EST from IEEE Xplore. Restrictions apply.

下载后可阅读完整内容，剩余5页未读，立即下载

doraclx

粉丝: 1
资源: 2

混合遗传-免疫算法解决流水车间调度问题

[2002--NSGA-II]---A-Fast-and-Elitist-Multiobjective-Genetic-Algorithm---NSGA-II

遗传算法的CPP简单实现_Genetic-Algorithm-with-matlab-and-Cpp.zip

Adaptive Immune-Genetic Algorithm for Fuzzy Job Shop Scheduling Problems

A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem

Elitist-Genetic-Algorithm-master_geneticalgorithm_

Artificial-immune-genetic-algorithm.rar_人工智能/神经网络/深度学习_matlab_

Knight-Tour-Genetic-Algorithm-With-Repair:使用 p5js javascript 库模拟骑士之旅遗传算法

Genetic-Algorithm-with-python:使用python实现GA

2D-Bin-Packing-with-Genetic-Algorithm-master_2dpacking_

immune-genetic-algorithm.rar_genetic VB

最新资源