基于共同进化计算模型的基因连锁问题求解

针对传统单种群进化类算法(conventional evolutionary algorithms,简称CEAs)求解基因连锁问题的不足,基于生物界共同进化机制提出求解NK基因连锁问题的合作式共同进化算法(Coevolutionary algorithm,简称CoEA),探讨其子种群的合作方式与个体适应值的计算方法,并从数学上分析该算法的性能,指出共同进化算法中高于平均适应值模式的递增指数高于传统单种群进化算法.仿真结果证实了理论分析.结果表明,共同进化算法比传统单种群进化算法对求解基因连锁问题的效力和效     

国防科大计算机学院工学博士学位论文 摘要

虚拟环境中碰撞检测问题 的研究 作者：魏迎梅(2000.10) 导师：吴泉源教授 　　本文以虚拟手术仿真为应用背景,着重论述了一个基于固定方向凸包包围 盒层次的碰撞检测方法。固定方向凸包是一种特殊类型的凸包,它的所有面方向都来自一个 固定的方向集合,它克服了以往包围盒类型的缺点,在紧密性和简单性之间达到了一定的折 衷。本文在充分研究了固定方向凸包的固有特性的基础上,开发并证明了它适用于复杂环境 中软体碰撞检测的性质,并着重解决了包围盒间的相交测试、对象运动后包围盒的更新、对 象变形后包围盒树的更新等问题。 　　文中提出并证明了一种快速区间测试法以解决两个固定方向凸包包围盒间的相交测试问题, 通过查找两个包围盒在由固定方向集合所定义的方向轴上的范围区间是否存在不重叠的情况 ,来判断它们是否不相交。通过这种简单的区间测试法,两个包围盒间的相交测试最多只需 要k次比较运算(k为固定方向集合的大小)。 　　对象运动后包围盒的更新是层次包围盒方法中的一个重要问题。根据固定方向凸包的定义和 性质,文中提出了一种基于线性规划的更新算法,不需要在构造包围盒层次时增加任何额外 的计算量和存储量,在对象运动后可以仅通过3k次乘法得到更新后的包围盒。 　　对象变形后的处理是碰撞检测问题的一个难点。本文在对几种变形情况进行分析的基础上, 分别提出了相应的解决方法,并着重提出了一种自底向上的包围盒树快速更新算法,通过k 次比较运算由子结点的包围盒得到父结点的包围盒,以解决拉压变形和拓扑变化后包围盒树 的更新问题。 　　此外,在充分开发和利用虚拟环境中对象运动的时空相关性的基础上,提出了加速对象间碰 撞检测速度的遍历跟踪策略。这是一个启发式的策略,通过跟踪上一时间采样点对包围盒树 的遍历过程,确定当前时间采样点的遍历路径,从而有效地减少了遍历过程中包围盒相交测 试的次数,提高了算法效率,同时通过对跟踪表的维护,保证了碰撞检测的正确性和有效性 。 　　实验结果和具体应用表明,基于固定方向凸包包围盒层次的碰撞检测方法不仅能 很好地解决刚体间的碰撞检测,而且为解决和处理软体对象环境中的碰撞检测问题提供了一 种可靠而有效的途径。本文的研究成果,对大规模复杂环境中的碰撞检测有重要的理论价值 和实际意义。 网络计算中任务分配与调度的 遗传算法研究 作者：钟求喜(2000.10) 导师：陈火旺院士 　　任务分配与调度是网络计算中的一项关键技术,直接影响到整 个系统的计算性能。任务分配与调度问题是一类NP问题,经典调度理论一般仅能获得问题的 近似最优解。尽管已有用于任务分配与调度的遗传算法求解质量优于传统方法,但传统单种 群遗传算法的效率随任务数增多而下降。本文采用理论分析与仿真实验相结合的方法,研究 网络计算中单任务和独立多任务分配与调度的遗传算法。 　　本文首先针对同构系统 中任务分配与调度问题提出一个通用的遗传算法。算法直接采用任务列表编码结构,在此基 础上设计出三个专门的遗传算子,即改进的交叉算子、内部交叉算子和具有变异功能的迁移 算子。种群初始化技术采用均衡水平分割法,以保证初始个体的有效性和质量。算法主要控 制参数的取值通过仿真实验确定。 　　针对传统单种群遗传算法求解独立多任务分配与调度问题的伸缩性差的缺点,本文基于多物 种共同进化的生物学背景,从理论上探讨合作式共同进化计算模型的机理。数学分析表明, 对于独立多问题,共同进化算法采用按比例选择策略时,高于平均适应值的模式的逐代递增 指数高于传统单种群遗传算法,说明共同进化算法的效率高于传统的单种群遗传算法。对于 不可作独立子问题分解的问题,则以基因连锁一般模型-NK模型进行了实例研究。 　　将合作式共同进化计算模型应用于同构系统中的独立多任务分配与调度问题,提出一个独立 多任务分配与调度的共同进化遗传算法,包括子种群中子分配与调度实例组合成总分配与调 度实例的启发式合并方法,以及子种群个体的适应值计算方法等。 　　针对网络导构计算的简化模型和一般模型分别提出任务与调度的遗传算法。一般模型中任务 分配与调度受到系统多种因素的影响,如任务间的数据逻辑关系、各处理机的计算速度、网 络拓扑结构、节点间通信机制以及通信波特率、数据流量大小等等。在考虑上述影响因素的 基础上,分别提出单任务分配与调度的遗传算法和独立多任务分配与调度的共同进化算法。 　　从同构系统到异构计算环境,从单任务到独立多任务,本文提出了针对不同系统环境下任务 分配与调度的遗传算法。理论分析与仿真实验均表明,本文所提算法的问题求解性能优于传 统调度方法和已有用于任务分配与调度的遗传算法。     

求解0—1背包问题的共同进化遗传算法

0-1背包问题是一类组合优化问题,迄今已有40多年的研究历史,可广泛应用于碎片收集、作业调度、资金预算和货物装箱等领域。0-1背包问题是一类NP问题,所以传统方法如持续松弛法、分枝-界限法、动态规划法和一些近似算法等等,一般仅能获得问题的近似最优解。近年来,不少学者将稳健的遗传算法应用于0-1背包问题的求解,在问题求解质量方面收到了较好的效果。但是,由于传统的单种群遗传算法中一个染色体编码结构代表了问题的一个完整可行解,因此可能导致对解的较好部分的利用可能被其它较差的部分所掩盖,且问题求解效率随着问题规模的增大而下降。针对上述不足,本文基于合作式共同进化计算模型,将共同进化计算用于求解,提出一种求解0-1背包问题的共同进化遗传算法,以进一步提高问题的求解质量和算法效率。     

网络计算中任务分配与调度的遗传算法研究

任务分配与调度是网络计算中的一项关键技术 ,直接影响到整个系统的计算性能。任务分配与调度问题是一类NP问题 ,经典调度理论一般仅能获得问题的近似最优解。尽管已有用于任务分配与调度的遗传算法求解质量优于传统方法 ,但传统单种群遗传算法的效率随任务数增多而下降。本文采用理论分析与仿真实验相结合的方法 ,研究网络计算中单任务和独立多任务分配与调度的遗传算法。本文首先针对同构系统中任务分配与调度问题提出一个通用的遗传算法。算法直接采用任务列表编码结构 ,在此基础上设计出三个专门的遗传算子 ,即改进的交叉算子、内部交…     

多空间协同进化的自然计算方法

在自然计算方法中,种群规模大,计算复杂度高;种群规模小,容易陷入局部最优.本文提出多空间协同进化(Multispace Coevolution,简称MSC)的自然计算方法,该方法适用于各种基于种群进化的优化算法,不依赖于算法进化的具体步骤,具有普适性.在传统的生物种群进化的基础上,将大种群分解为个数有限的小种群,部分小种群组成进化空间,另一部分构成指导空间,两个空间拥有不同的功能,指导空间通过特定的信息传递方式将经验概括信息传递到进化空间,从而使整个种群协同进化.将该策略分别应用到粒子群优化算法(PSO)和遗传算法(GA)中,并与标准粒子群算法、遗传算法以及目前主流的针对大规模问题进行优化的7个算法对比,在高维测试函数中,结果表明,寻优性能方面新的种群进化算法相比其他算法提高80%左右,具有普适性.     

基于协同进化算法的TS模糊模型设计

提出一种基于协同进化算法的TS模糊模型设计方法．该方法由以下两步组成：（1）采用模糊聚类算法辨识初始的模糊模型；（2）利用协同进化算法对所获得的初始模糊模型进行结构和参数的优化．协同进化算法由两类种群组成：规则前件种群和隶属函数参数种群；其适应度函数同时考虑模型的精确性和解释性，采用两种群合作计算的策略；为提高模型的解释性，在协同进化算法中利用基于相似性的模型简化方法对模型进行约简．最后，利用该方法对Mackey-Glass系统进行辨识，仿真结果验证了方法的有效性．     

基于量子进化规划核聚类算法的图像分割

基于量子计算的并行性、进化计算简单、通用性好等优点,采用量子编码构造进化算法的染色体种群,再将二者引入到核聚类中来,提出了一种基于量子进化规划的核聚类算法.该算法充分利用了量子态的叠加性以及量子比特的概率表示,能够表示出许多可能的线性叠加状态,具有更好的种群多样性,因此将其用于解决核聚类算法中目标函数的优化问题,可以有效克服传统进化算法收敛速度慢以及早熟等问题.对Brodatz纹理图像及SAR图像进行分割,仿真实验结果表明该算法可以较好地改善图像分割效果.     

复杂模糊分类系统的协同进化设计方法

提出一种基于协同进化算法的复杂模糊分类系统的设计方法．该方法由以下3步组成:1)利用Simba算法进行特征变量选择;2)采用模糊聚类算法辨识初始的模糊模型;3)利用协同进化算法对所获得的初始模糊模型进行结构和参数的优化．协同进化算法由三类种群组成;规则数种群,规则前件种群和隶属函数种群;其适应度函数同时考虑模型的精确性和解释性,采用三类种群合作计算的策略．利用该方法对多个典型问题进行分类,仿真结果验证了方法的有效性．     

多群体混合进化算法求解IPPS问题

针对工艺规划与调度集成（Integration of Process Planning and Scheduling, IPPS）问题求解复杂性,为提高求解效率,设计了包含探索种群,寻优种群和最优种群的多群体混合进化算法,通过运用混合遗传算法和基于聚类淘汰机制的差分进化算法分别更新探索种群中工艺链和加工顺序链,保持可行解多样性和差异性。然后利用克隆领域搜索算法完成寻优种群中可行解的克隆和领域搜索,进一步提高种群质量。最后按照精英保留策略更新最优种群获得全局最优解。并通过实例计算对比,结果显示算法搜索效率和求解质量均有明显改善,且稳定性较好,表明该算法求解IPPS问题的可行性及优越性。     

混合性能指标优化问题的大种群规模进化算法

混合性能指标优化问题可结合传统遗传算法和交互式遗传算法求解, 而种群规模和人机评价任务分配是影响算法性能的关键. 针对该问题, 本文提出一种新的进化优化算法. 首先, 采用大规模种群, 扩大搜索范围, 以增强算法的探索能力; 然后, 根据计算机和用户完成任务耗时的比值, 确定每代用户评价的个体数, 以提高计算机的使用效率; 接着, 采用K–均值聚类方法和基于相似度的估计策略, 以减轻用户疲劳; 最后, 采用Pareto占优比较不同个体的优劣, 使得最优解有较好的显式性能指标值和隐式性能指标值. 将本文算法应用于室内布局这一混合性能指标优化问题, 结果验证了所提算法的有效性.     

基于杂交遗传算法的多处理器硬实时容错调度算法

传统的硬实时容错调度算法获得了较好的容错性能,但其任务拒绝率、处理器分配偏差比例以及最早完成时间等性能参数不佳,对此提出一种基于杂交遗传算法的优化方案,并对传统的硬实时容错算法进行优化。采用了中心型调度模型,并采用了任务备份方案来实现容错能力。将任务拒绝率、处理器分配偏差比例以及最早完成时间三个优化参数作为遗传算法适应度目标函数的三个带权分量,对其进行优化,通过遗传算法的杂交与迭代计算获得了优化的结果。最终使用不同的任务数量与处理器数量的组合对本算法与传统算法进行对比试验,结果可看出本算法的3个优化参数明显优于传统算法,且总适应度值亦比传统算法有明显改进。     

柔性作业车间调度问题的集成启发式算法

柔性作业车间调度问题,包括路径分配和加工排序2大子问题,是组合优化理论和实际生产管理的重要研究方向。作为传统作业车间调度的扩展,柔性作业车间调度问题的内在复杂性(强NP-Hard)使得传统的最优化方法难以有效求解。文章针对以多目标权重和最优为目标的柔性作业车间调度问题,提出基于过滤定向搜索的集成启发式算法,设计改进了节点分枝策略和局部/全局评价函数,能同时解决2大子问题。通过实例仿真,对算法性能进行比较分析和评价,结果表明了算法的可行性和有效性。     

Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach

In general, distributed scheduling problem focuses on simultaneously solving two issues: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production scheduling in each factory. The objective of this approach is to maximize the system efficiency by finding an optimal planning for a better collaboration among various processes. This makes distributed scheduling problems more complicated than classical production scheduling ones. With the addition of alternative production routing, the problems are even more complicated. Conventionally, machines are usually assumed to be available without interruption during the production scheduling. Maintenance is not considered. However, every machine requires maintenance, and the maintenance policy directly affects the machine's availability. Consequently, it influences the production scheduling. In this connection, maintenance should be considered in distributed scheduling. The objective of this paper is to propose a genetic algorithm with dominant genes (GADG) approach to deal with distributed flexible manufacturing system (FMS) scheduling problems subject to machine maintenance constraint. The optimization performance of the proposed GADG will be compared with other existing approaches, such as simple genetic algorithms to demonstrate its reliability. The significance and benefits of considering maintenance in distributed scheduling will also be demonstrated by simulation runs on a sample problem.     

基于改进的蝙蝠算法在云计算中的资源分配

云计算中的资源分配一直都是研究的重点, 提出了一种基于改进的蝙蝠算法的云计算资源分配方法. 在蝙蝠算法中引入差分遗传算法, 通过变异, 交叉和选择等操作避免个体陷入局部最优, 以及过早产生最优解的可能,改进后的蝙蝠算法能够有效的提高收敛速度和精度. 仿真实验表明, 本文算法不但有效提高了算法性能, 还优化了云计算系统中的资源调度能力, 提高了云计算资源的利用率.     

基于自适应惩罚函数的云工作流调度协同进化遗传算法

云计算为大规模科学工作流应用的执行提供了更高效的运行环境。为了解决云环境中科学工作流调度的代价优化问题,提出了一种基于协同进化的工作流调度遗传算法CGAA。该算法将自适应惩罚函数引入严格约束的遗传算法中,通过协同进化的方法,自适应地调整种群个体的交叉与变异概率,以加速算法收敛并防止种群早熟。通过4种科学工作流的仿真实验结果表明,CGAA算法得到的调度方案在满足工作流调度截止时间约束与降低任务执行代价的综合性能方面优于同类型算法。     

基于CRQP的多小区OFDMA系统联合资源分配算法

针对OFDMA多小区系统中相邻小区同频干扰下的吞吐量最大化问题,在系统功率的约束条件下,基于协同量子粒子群算法提出一种子载波和功率联合分配的协同随机量子粒子群算法（CRQP）。分别利用粒子群算法独立优化子载波的功率分配,并利用改进的量子遗传算法独立优化用户的子载波分配。在独立优化的同时,通过随机协同策略避免陷入局部最优解,达到全局最优。仿真结果表明,与传统的分步求解算法相比,CRQP算法能获得更多的系统吞吐量和更高的资源利用率。     

项目优化调度的病毒协同进化遗传算法

针对次序约束和资源约束的多模式项目调度问题提出了一种病毒协同进化遗传算法,并提出了解的编码、选择、交叉、变异和病毒感染操作等.算法用于求解项目活动的一个最优调度顺序和资源模式以使项目的成本最低,其操作特点是既可以通过遗传操作在父子代群体之间纵向传播进化基因进行全局搜索,又可以通过病毒感染操作在同一代群体内横向传播进化基因进行局部搜索.利用模板理论对算法的性能进行了分析.理论分析和实验结果表明,算法的搜索性能优于一般的遗传算法.算法对于不同优化目标的多模式项目调度问题可以同时求得一个满足次序约束的项目活动的最优调度顺序和满足资源约束的最优资源模式.     

带有交货期的比例流水车间调度问题的合作博弈

针对具有多个客户订单的比例流水车间调度问题,在考虑有交货期及提前和拖期惩罚下,以客户支出成本为优化指标,在客户通过合作结成联盟的方式下,以联盟内成员进行重新调度所获得的最大成本节省为联盟的价值,建立合作博弈模型.该合作博弈是具有无外部性的平衡博弈,从而有非空核.考虑到客户对提前加工和延迟加工的迫切程度不同,提出基于提前及拖期惩罚的β规则分配方法,该方法能得到带有交货期的比例流水车间调度合作博弈的一个核分配.通过混合差分进化算法求解最优调度顺序,实验结果验证了基于合作博弈模型的调度方法及成本分配方法的有效性.     

基于动态双向优先级的任务分配与调度算法

提出了一种基于动态双向优先级的任务分配与调度算法,称作动态双向优先级(DDDP)算法。该算法综合考虑了实时任务的优先级和子机的优先级,构造了动态双向优先级任务分配模型,实现了数据传输中主机/子机模式的任务动态分配与调度。在模拟实验中,通过使用正常负载和过载情况下的典型数据对算法进行仿真研究表明,这种算法比单纯考虑截止期的EDF算法在性能方面有明显的改进和提高。     

Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm

This paper deals with a scheduling problem for reentrant hybrid flowshop with serial stages where each stage consists of identical parallel machines. In a reentrant flowshop, a job may revisit any stage several times. Local-search based Pareto genetic algorithms with Minkowski distance-based crossover operator is proposed to approximate the Pareto optimal solutions for the minimization of makespan and total tardiness in a reentrant hybrid flowshop. The Pareto genetic algorithms are compared with existing multi-objective genetic algorithm, NSGA-II in terms of the convergence to optimal solution, the diversity of solution and the dominance of solution. Experimental results show that the proposed crossover operator and local search are effective and the proposed algorithm outperforms NSGA-II by statistical analysis.