CASIA OpenIR  > 毕业生  > 硕士学位论文
遗传算法在分布式调度中的应用及DNA计算
张焱
学位类型工学硕士
导师裘聿皇
2002-05-01
学位授予单位中国科学院研究生院
学位授予地点中国科学院自动化研究所
学位专业控制理论与控制工程
关键词遗传算法 复数编码 分布式任务调度 启发式算法 Dna计算 Genetic Algorithms Complex-valued Encoding Distributed Task Scheduling Hcuristic Algorithms Dna Computing
摘要遗传算法是一种借鉴了生物界自然选择机制的随机搜索算法,其主要特点是 群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度等辅助信息。它 可以广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域, 尤其适用于处理传统搜索方法难于解决的复杂和非线性问题。 本文首先简单介绍了遗传算法的基本概念、原理和发展现状,分析了遗传算 法的收敛性。在总结了以往编码方法的基础上,我们提出了一种基于复数编码的 遗传算法,用复数来表达双倍体,并规定了具体的遗传操作。与传统的基于实数 编码的遗传算法相比,该算法扩展了表达空间的维数,仿真结果证明了该算法的 有效性。 近年来,由于微处理器技术和网络技术突飞猛进的发展,计算机体系结构在 设计上产生了明显的倾向性变化,研究分布式计算机系统成为未来计算机技术发 展的一个重要方向,而提高分布式计算机系统效率和实现实时分布式系统的一个 关键问题是就是分布式的任务调度问题。 本文对一类具有优先约束的同等处理器上的分布式任务调度问题进行了研 究,该类问题已被证明属于NP难题,无法找到多项式时间的最优算法,以往的 研究成果都是使用启发式算法解决该类问题。我们在前人工作的基础上提出了一 种新的启发式算法,并与已有的两种启发式算法进行了比较。结果说明,我们的 算法即可以得到较好的性能,又可以保证一定的实时性。 使用遗传算法解决调度问题的研究成果已有很多,但是对于具有优先约束的 分布式调度问题尚无应用的先例。我们首次使用遗传算法解决了两种情况下的具 有优先约束的分布式调度问题。根据同等处理器上的非抢先调度的特点,我们使 用了一个一维向量来表示任务间的树状优先关系。对候选解进行编码时,我们设 计了一种独特的方法,每个个体由代表任务序列和处理机序列的两个子串组成, 不仅简化了适应度的评估过程,而且可以分别对两个子串实行不同的遗传操作。 与启发式算法往往只能得到次优解相比,我们的算法总能够得到问题的最优解。 作为一种新型的计算技术,DNA计算利用DNA分子来进行计算,具有传统 计算机所不可比拟的优点,引起了人们的极大兴趣。同时,作为一种生物计算技 术,DNA计算与遗传算法有着许多共同之处。本文对近年来有关DNA计算的研 究成果进行了综述,重点介绍了DNA计算与遗传算法的结合。指出了目前DNA 计算技术存在的主要问题,并对其未来发展进行了展望。
其他摘要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
馆藏号XWLW634
其他标识符634
语种中文
文献类型学位论文
条目标识符http://ir.ia.ac.cn/handle/173211/6868
专题毕业生_硕士学位论文
推荐引用方式
GB/T 7714
张焱. 遗传算法在分布式调度中的应用及DNA计算[D]. 中国科学院自动化研究所. 中国科学院研究生院,2002.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
硕士生学位论文-634.pdf(9205KB) 暂不开放CC BY-NC-SA请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[张焱]的文章
百度学术
百度学术中相似的文章
[张焱]的文章
必应学术
必应学术中相似的文章
[张焱]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。