Genetic algorithms (GAs) are a kind of stochastic searching algorithms, which refer to the Natural Selection Mechanism of the nature. The principal characteristics of genetic algorithms include a generation searching strategy, the information interchange between the individuals in each generation and independence of supplementary conditions such as grads. Genetic algorithms can be applied in many areas such as combination optimization, machine learning, self-adaptive control, programming design and artificial life, especially in areas like complex and nonlinear problems that the conventional searching methods can do little about. In this dissertation, we make a brief introduction to the concepts, principles and current research status of GAs, and analyze the convergence of GAs. After summarizing existed encoding methods, we put forward a new method complex-valued encoding. We use one complex number to denote each diploid and define the genetic operators accordingly as well. Compared to the conventional GAs based on real-valued encoding, our algorithm expands the dimensions for denotation greatly. The computation results prove its efficiency. With the development of microprocessor techniques and network techniques, distributed computer systems become an important research filed because of their high speed, while distributed task scheduling is the key to heighten the efficiency of the distributed computer systems and to implement real-time distributed computer systems. We investigate the distributed task scheduling on equivalent processors with precedence constraint, which has been proved to be a NP problem and has no polynomial-time algorithms. Earlier solutions to this problem are mostly heuristic algorithms. On the base of former research, we put forward a new heuristic algorithm. Compared with two other heuristic algorithms, our algorithm can not only get better results, but also guarantee the real-time performance. Many people have used GAs to solve task-scheduling problems, but no one has solved the distributed task scheduling with precedence constraints so far. We firstly solve this problem under two circumstances using GAs. According to the characteristic of non-preemptive scheduling on equivalent processors, we use aone-dimension vector to denote the treelike structure of priority of the tasks. We also design a unique method to encode individuals. Each individual composes of two substrings, which denote the task sequence and processor sequence respectively. This method not only simplifies the fitness-evaluating process, but also makes it possible to execute different genetic operations on the two substrings. Compared with heuristic algorithms, our algorithm can always get the best solution to the schedule problem. As a new computing method, DNA computing makes use of DNA molecules to compute. DNA computing has attracted great interest for its incomparable advantage to conventional compu
修改评论