TY - JOUR

T1 - A pipeline-based genetic algorithm accelerator for time-critical processes in real-time systems

AU - Sheu, Shiann Tsong

AU - Chuang, Yue Ru

N1 - Funding Information:
The authors would like to thank the National Science Council of the Republic of China, Taiwan, for financially supporting this research under Contract No. NSC 94-2213-E-008-044.

PY - 2006/11

Y1 - 2006/11

N2 - The meta-heuristic methods, genetic algorithms (GAs), are frequently used to obtain optimal solutions for some complicated problems. However, due to the characteristic of natural evolution, the methods slowly converge the derived solutions to an optimal solution and are usually used to solve complicated and offline problems. While, in a real-world scenario, there are some complicated but real-time problems that require being solved within a short response time and have to obtain an optimal or near optimal solution due to performance considerations. Thus, the convergence speed of GAs becomes an important issue when it is applied to solve time-critical optimization problems. To address this, this paper presents a novel method, named hyper-generation GA (HG-GA), to improve the convergence speed of GAs. The proposed HG-GA breaks the general rule of generation-based evolution and uses a pipeline operation to accelerate the convergence speed of obtaining an optimal solution. Based on an example of a time-critical scheduling process in an optical network, both analysis and simulation results show that the HG-GA can generate more and better chromosomes than general GAs within the same evolutionary period. The rapid convergence property of the HG-GA increases its potential to solve many complicated problems in real-time systems.

AB - The meta-heuristic methods, genetic algorithms (GAs), are frequently used to obtain optimal solutions for some complicated problems. However, due to the characteristic of natural evolution, the methods slowly converge the derived solutions to an optimal solution and are usually used to solve complicated and offline problems. While, in a real-world scenario, there are some complicated but real-time problems that require being solved within a short response time and have to obtain an optimal or near optimal solution due to performance considerations. Thus, the convergence speed of GAs becomes an important issue when it is applied to solve time-critical optimization problems. To address this, this paper presents a novel method, named hyper-generation GA (HG-GA), to improve the convergence speed of GAs. The proposed HG-GA breaks the general rule of generation-based evolution and uses a pipeline operation to accelerate the convergence speed of obtaining an optimal solution. Based on an example of a time-critical scheduling process in an optical network, both analysis and simulation results show that the HG-GA can generate more and better chromosomes than general GAs within the same evolutionary period. The rapid convergence property of the HG-GA increases its potential to solve many complicated problems in real-time systems.

KW - Evolutionary computing

KW - Genetic algorithms (GAs)

KW - Optimization

KW - Pipeline

KW - Time-critical processes

UR - http://www.scopus.com/inward/record.url?scp=33750107463&partnerID=8YFLogxK

U2 - 10.1109/TC.2006.171

DO - 10.1109/TC.2006.171

M3 - 期刊論文

AN - SCOPUS:33750107463

SN - 0018-9340

VL - 55

SP - 1435

EP - 1448

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 11

ER -