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.
I.
I
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].
C
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
978-0-7695-3738-2/09 $25.00 © 2009 IEEE
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.
资源评论
