基于遗传算法与贪婪算法的改进潜在时间表.docx

1、基于遗传算法与贪婪算法的改进潜在时间表基于遗传与贪婪算法的进化的潜在时间表摘要： 一个高度约束的组合问题，如时间表，可以用进化方法来解决。在本文中，我们描述了一个基于一个有效解决方案的交替过程，该方案涉及使用适当的遗传算法（GA）和启发式的具体的：贪婪算法。这两种算法被设想为响应约束和时间表问题利用的目标。这项提出的技术保证永远在合理的时间内，通过不能被破解的强密码约束产生一个可行的时间计算。目前的工作是为了证明交替遗传算法的具体勘探技术，是一种利用可行解的全局搜索，和局部最优解的具体技术效率的优势的过程。在应用于NP-Hard类时间表问题时，经典遗传算法并不高效。遗传算法、贪婪算法的交替使用

2、，以优化资源分配，从而，以提高适度价值和时间处理方面的表现。1.导论 在一般的调度问题中，事件必须被安排在同一组时间槽中，以满足一些约束和优化一组目标。调度问题的类型随不同类型的约束和目标而变化。在或严或松的约束条件下的调度是个复杂的任务，有一个NP-完全的复杂度，一般都与依赖属性域相关，并有必要特定的优化算法。这意味着，在有限时间内的可能性空间中，确定的和详尽的搜索技术可能会失败，而受启发式技术限制的搜索空间，不能总是保证得到最优解。一般地，我们区分出三种主要类型的搜索方法： 枚举法：在一个有限的搜索空间，或一个离散的无限的搜索空间，搜索算法开始看着在空间各点的目标函数值，一次一个。动态规划

3、是枚举方案的一个实例。 随机技术：基于进化的过程，目前流行的搜索技术是，模拟退火算法，利用随机过程来帮助引导其搜索最小能量状态的形式。遗传算法是一个搜索程序，采用随机选择作为一种工具来引导一个通过参数空间编码的高度开发的搜索的例子。 在过去的几十年中，在解决问题的系统的进化和传承的原则方面，人们有越来越大的兴趣：这样的系统维持了一个人口的潜在解决方案，其中有一些基于个人的健康的选择过程，和一些遗传算子。如：Koza遗传编程：提供了一种面向所需程序的方法，使自身在进化过程中也进化。Fogel进化规划：是一种通过一个小的有限状态机的空间来搜索的技术。进化策略：为参数优化问题而模拟自然进化的主角的算

4、法。荷兰遗传算法：基于计算的方法：细分为两大类：间接和直接。间接的方法寻找局部极值求解从,设置目标函数的梯度等于零,的方程通常是非线性的设置。迭代的贪婪算法也是一类间接方法。直接的方法是，对通过对方程的期望，和在与局部梯度相关的方向上移动，来寻找局部最优解如：爬山算法。 最近的研究表明，进化算法是一种解决调度问题的可行的、有效的方法。遗传算法（GA）提供了一种解决搜索和优化问题的方法。GA特别擅长在丘陵空间寻找全局最优解；由于这些原因，我们研究了遗传算法的应用。遗传算法解决np_问题的表现证明了它的效率。一些方法应用于遗传算法的杂交技术和一个给定的问题的启发式特性。在本文中，我们提出了一种遗传

5、算法与贪婪算法合并的交替方法，目的在于提高适度价值和时间处理方面的解决方案的搜索系统的表现。该技术是基于一系列的遗传算法和贪婪算法之间的结合，其中遗传引擎搜索负责全局意识和评估最优解的遗传，贪婪算法负责提出的解决方案的局部改良。我们对学习时间表调度的优化充满兴趣，对找到援助过程有用的方法多次尝试。然而，从解决这个问题的不同方法出发，从更经典的运筹学和图论到进化的算法，许多优化算法已经得到了发展，诸如模拟退火算法，禁忌搜索算法，遗传算法这是一个一系列事件的调度问题，必须安排一个人（教授、班级）或资源（教室、实验室）在同一时间占据一个站点。这些硬约束和其他软约束，使一般的时间表问题难以解决。排课问

6、题已被证明是np_hard问题，且充满局部极小值，这使得它特别难以用启发式搜索解决。通常的解决方式是，绘制时间表的初稿，再根据不同的条件改写出最新的拟稿。在本文中，我们描述了如何在一个机制中解决这些问题，通过一种进化算法：遗传算法和启发式的特性：贪心算法两者交替。首先，我们介绍了该问题，再提出遗传和贪婪算法。之后，我们对所给的进程进行细节分析，提出了改进的时间表。最后，我们提出了解释性结果，该结果与所采用的方法在真正的学校课表上的收敛性相关。对经典的遗传算法和交替的遗传算法在时间表问题这个特定实例下进行了比较和评估，我们清楚地说明，这种方法可以在时间处理和适应度价值方面产生非常有益的改进。2.

7、基础的时间表问题 在过去的几年中，多种排课问题已有相关文献，但大部分都是非常特例的，没有考虑到很多因素。 排课问题在这方面是特别的，它通常是基于一个非常大的数据量和不同类型的约束。定义以下问题数据的符号：教授的集合：，每个教授有以下的参数： 自由安排的集合， 教学安排的集合， 固定安排的集合，班级的集合：，一个班有许多学生。我们假定学生已分成各个班级。我们定义，班级是不相交的，其中没有共同的学生。一个班的定义： 课程的集合， 默认的教室，课程的集合：。一节课程的定义： 课程的种类Nature-C(集体的，单人的，并行实践课，集体实践课) 总的时间安排Nb-scheduls。时间段（小时）的集合

8、，教室的集合，把课程称作：单一课程只与一个教授和一个班相关，集体课程一个教授同时给两个或以上班级上课，实践课是一个特殊的课程，学生教室要满足具体的实验需要。学生的再分配取决于仪器的数量，所以我们有并行实践课和集体实践课。选择的测试实例包括优化时间表，其中约束条件必须同时满足。约束条件包括：1.同一时间只有一个教授在一个班级。2.同一时间一个教室只分配给一个班。3.同一时间一个班级只能分配到一个教室。4.教授修改的时间不能改变。5.空闲时间应集中在早晚。 班级的约束1-4可分为硬约束：如果不满足则该时间表不能成立。 约束5称作软约束：它不是强制性的，但如果在不可能的情况下被接受，其结果不是最优解

9、。 我们的目标函数是为了满足如下目标： 选择到满足意愿的课程表的教授数量最多。 学生和教授课程表上的空闲时间最少。3.遗传算法和贪婪算法 尽管在全局优化方面取得了进展，但它并不存在一个过程能够产生令人满意的解决方案。近年来，遗传算法已经证明了它们的效率，不仅在探索搜索空间方面，而且还提高了稳定性。由于时间表的优化，其特征在于由几个约束的数目和复杂性的变化，而不是杂乱的，遗传算法似乎是有前途的。 事实上，为不同的问题寻找最佳的解决方案，遗传算法是非常有效的。当应用到复杂的实际问题时，这种技术运行得特别好，因为它不对传统技术施加限制。有利于遗传算法的稳定性的同样的品质，需要长时间的计算。它们已被用

10、于解决目标函数不具有连续性，可微性等问题。这些算法维持和操纵了解决方案和手段的人数，在寻求更好的解决方案的研究中，这是一种“适者生存”的策略。基础成分就像基因的染色体。自主的个人有对应每一个解决方案的候选人。 在每一代中，一组新的人工生物被是由旧的适合的片段创造的，一个偶然的新的部分是为了良好的措施的尝试。遗传算法有效地利用历史信息来推测新的搜索点与预期的改进性能。 使用一个遗传算法需要确定的六个基本问题：染色体表示，选择功能，遗传算子的复制功能，初始种群，终止标准，和评价函数。 贪婪算法在组合优化中的应用，是高效的局部探索方法。这是一个通过一系列的替代，以实现最佳决策的算法。贪婪算法的方法是

11、，寻找一个最优的解决方案，涉及一个大的，同质的数据结构，从一个最佳的解决方案，到一些组件或小部分的数据结构，延伸到一个最佳的解决方案，通过考虑额外的组件的一个又一个的数据结构到一个最佳的全局解决方案。因此，贪婪算法进行在每一步最新选择。因此，这个选择是明智的，因为它将不能在随后被挑战。 在本文中，我们说明了遗传算法能被尤其适合特别问题的探索技术代替。所以可以设计一个改进的交替算法，利用遗传算法的全局洞察力和局部技术的效率。4.改进的时间表最常用的应用于调度时间表的问题的进化方法是使用一个直接和直观的染色体表示，加上一个适应度罚函数。一个时间表是由一个母体染色体表示的，该染色体由三个特定组合的等

12、位基因组成：教授等位基因（P），课程等位基因（C），和教室等位基因（R）。在一周内可能需要用到一次以上的基因型，在染色体上柱形基因的位置代表一个时段，而线型基因位置则是一个班级。例如，基因类型“022019”代表教授P（ID=02）在教室R（ID=19）上课程C（ID=20）。评价函数是遗传算法的背后驱动力。遗传算法需要它来确定在搜索过程中产生的每个解矩阵的适应度。适应度分数是约束冲突的加权总数和教授-时间段的优先计划的满意度与现实安排(Cost(T)之间的折衷 。遗传算法的方法会尝试尽量减少适应度分数。换句话说，它是对一个潜在的时间表质量的主观衡量。因此，在遗传引擎的每一代，我们试图找到一个

13、最佳的时间表T *，使evalf最小化。措施方面，一个理想的时间表是其适应度价值等于0。 最适合的时间表（T）显然是没有约束冲突的。时间表在一组可能的解决方案的集合（x）中是有差异的，基于不同数量和类型的约束冲突的适应度值。操作者提供了遗传算法的搜索机制，该操作曾创造了新的基于人口的现有解决方案的方案。有2种基本类型的操作符，交叉和变异。交叉算子，传递最理想的一个时间表，以产生良好的质量的解决方案。交叉算子需要2个个体，然后将父类的线分类，以减少所谓的局部适应度函数的值，最好的线被取为基本构件，其余的线是从第二父类取出的。其中使用了两种突变。K阶突变，其中，操作者选择两个K元素中父矩阵的同一行

14、里连续的结果，并替换掉他们。日突变，是前者的一个特殊情况。 选择机制决定了个体在下一代的生存和延续。采用了2种选择机制，基于适应值的选择，采用第一代多样化的基本构件，和比例为基础的选择，应用于上一代，以提高后代。4.1 约束条件4.1.1 硬约束 遗传算子被设想为： 1.维护基因型的资源，使其始终分配在同一个类中， 2.保存硬约束， 3.防止资源域扩展， 4.确保时间表在操作后保持可行性。每个遗传算子的执行后，在教授和教室的冲突中所实现的系统会验证生成的个体有效性。在这样的硬约束冲突的情况下，相应的后代将被其父算子替代。 这种排斥技术避免了系统通过一个不可行的搜索空间，以及在探索的可能性时不浪

15、费时间。因此，该系统会试图操纵可行的搜索空间。4.1.2 软约束 在软约束冲突的情况下，系统会惩罚适应度函数，并计算冲突度。4.2 “上位”现象 上位现象通常在调度领域中出现。我们必须避免这种有害的现象，因为我们已经构建了一个足够的染色体，一个遗传算子的完美适应不仅能够适应选择的数据结构（矩阵代表），也能适应时间表问题的数据域和特定遗传结构的实现。 事实上，一个非线性的、复杂的数据结构的使用，使得同性的元素的矩阵表示和遗传算子应用于一组基因型，有助于消除基因之间的相互作用。另一方面，应用在基因型的遗传算子不能容忍在三个等位基因PCR拼接成的任何遗传中断。4.3 遗传算法的不足经典遗传算法效率不

16、高的问题难以解决。事实上，遗传算法使用随机选择的工具来指导探索局部的搜索空间。遗传算法只使用编码和适应度值来确定新一代可能的尝试。 当它存在时，遗传算法不使用特定的知识。这可以限制算法的性能，在其与专门解决一个问题的具体方法相比时。最现实的问题是由其特定的信息导致的，这是参考了具体的启发式的交替遗传算法嗲来的优势。事实上，在这种情况下，对量化解决方案的评估尺度的限制仍然有所不足。事实上，在最小化（或最大化）的情况下，最好的解决方案并不总是有一个最小（或最大）的适应值。通常，探索方法，如贪心算法，需要处理大量的辅助信息。事实上，对于完成与特征相关的技术的目标，局部探索技术是一种专门针对一类具有交

17、互技术问题的技术。这种交互技术是一种利用辅助信息加快解决方案的开发方法。事实上，在实践中往往模型、约束和/或目标函数并没有准确定义。这是由于数据不准确或模式复杂或目标多变。在此情况下，探索一类的“好”的解决方案往往是更有趣的。 该技术基于一系列遗传算法和贪婪算法的交替。运行遗传算法直到随之产生的收敛水平。此后，对遗传算法的最后一代次级群体应用局部优化程序。这个序列是重复的，交替过程一直延续，直到根据一个决定标准来说它是收敛的。交替的遗传算法的使用让人们能够通过模块化方式认识到这一点。5.实验结果在这一部分中，我们展示了一些经典遗传引擎第一部分中的应用的结果，在第二部分种中交替的遗传算法和贪婪算

18、法使用的是，来自突尼斯工程大学的真实数据。个体适应度整合了一种教授分配的工具一时间表和约束冲突的惩罚措施。分配方法要考虑教授偏好的时间表。适应度价值决定了所提出的方法的收敛性。绝对的最优适应值对应于零。将遗传算法应用于一个初始量为316适应度的时间表。经典遗传算法具有以下参数：人数65人，交叉算子，k阶突变，日突变，以适应度为基础的选择和比例的选择。交叉算子Pc和突变率Pm分别为0.8，0.01。然而，“最好”的遗传算法与经典遗传算法有相同的基本因素，但每个个体的遗传算子发生后，它评估了潜在的解决方案。然后，它采用精英主义，即每一代最好的染色体保证能传递给下一代。5.1遗传引擎经典的遗传算法不

19、能够提高初始时间表的适应度。事实上根据图3，我们注意到，经典遗传算法的1000代的适应值保持不变。然而，“最好”的遗传算法引入精英机制，提高了适应度。这是通过复制每个遗传算子的执行来实施的，精英染色体由此传递到新的人中。这是为了通过遗传算子尽可能避免破坏。 根据图3，我们注意到，由于“最佳”遗传算法，大约一个小时的时间里运行了750代后，时间表的适应度价值已从316降低到150。这一代之后收敛趋于稳定。5.2 遗传算法和贪婪算法的交替5.2.1 交替数的变化。对一群人应用遗传算法直到收敛水平（G代）。然后，贪心算法应用于最优个体。图4显示： 第一个交替遗传算法解决方案，是通过独立地改变遗传算法

20、后代数量提高的。然而，我们注意到，交替适应度价值也独立地根据后代数量收敛，这也意味着交替概念传递给了一代。 对于给定的交替的数量（20）后代数以稳定的方式在不断地提高适应值。 最好的结果为47次交替和200代。 操作时间取决于后代数和交替数。应用遗传算法收敛到10代，在25次交替后达到100的适应度价值，需要15分钟的时间。这个适应度一直在第5次交替达到 ，此时使用了20次遗传算法，然而，大约用了一个小时的时间。 优化计算时间可以通过增加和减少一代人得到改变。5.2.2 人口规模的变化 遗传算法迭代次数已经固定在200，遗传算法和贪婪算法的交替次数为50。 我们表明，更多的人口规模是小的，适应

21、度价值和时间处理是最好的。这说明了根据一个机构中部门的数量来分配个体是最好的。因此，Goldberg的基于遗传算法效率的评估得到满足： “如果一台机器有一个低的并行度，最高的效率会在少量的人数下实现。极限的情况下，并行性为零，则人口应减少到一个单一的个体。” 这种经验使实现系统从最佳适应度改变和时间的减少中受益。5.2.3 贪婪算法处理的个体数变化 交替已应用于一个时间表，初始量为58的适应度价值。在一个10个人的人口规模中应用遗传算法，循环100次迭代直到收敛。然后，对一系列个体应用贪婪算法。遗传算法的迭代和贪婪算法的启发式之间的交替应用50次。检查了两种情况：1.遗传算法和贪心算法交替应用

22、在由最新的遗传算法后代产生的所有个体的人口（第100次遗传算法迭代）2.遗传算法和贪心算法交替应用在由最新的遗传算法后代产生的最好的个体（具有最小的适应度价值）贪婪程序执行在这个最佳个体上之后，我们重复了10次最佳个体的优化资源配置。这种重复，是为了产生一个10人的人口规模，并因此运行遗传引擎。相比之下，在第一种情况下，我们不需要做任何的重复，事实上对两种算法而言，人口规模保持不变。 根据图6，由贪婪算法处理的只有最好的个体，在第19次交替后，我们得到46的适应值。这个分数已经达到在第9次的交替（对所有人口使用贪婪算法）后的值 。这两个实验需要时间约半小时。 一个优化的适应度值可以通过由贪婪算

23、法处理的个体数量的最大化得到。6.总结 研究结果表明，当遗传算法和贪婪算法的交替应用于组合的时间表问题，以获得一个全局最优的时间表时，性能得到改进。本文对交替使用遗传算法和贪婪算法的思想在优化中的起了重要作用，本文的主要发现如下：编码一个遗传算法的时间表，并定义一个承认最佳的时间表的适应度函数，这是可能的。 在面对高度约束的组合问题时，如时间表问题， 经典遗传算法是没有说服力的。 在一个工程大学使用真实的数据时，执行的系统都能找到一个明显比实际人工排课的结果更好的时间表。由于遗传物质（染色体）的最佳选择，合适的遗传算子，和对应特定问题的特定遗传算法结构，提高性能并避免上位现象是可能的。 具体的

24、遗传算子直接表示时间表，确保了最基本的约束从未冲突。它通过一定不会被打破的硬编码约束,保证总是产生一个可行的时间表。交替次数的增加能达到最优适应度价值的最优化，直到观测到静止收敛状态，并使贪婪算法处理的个体数达到最大化。一个更有用的解决方案需包含一个能控制收敛速度的系统。另一方面，遗传算法也需要对参数的精心设置。其表现可以通过实现一个并行程序来改进。 所提出的技术能够解决其他的问题，它可以应用到其他有竞争目标和多个资源的调度中。这样的情况中常见的问题，包括使用可用的空间，和对分配的时间和地点的不满。因此，它可以成功应用于其他组合问题，如旅行商问题，任务评估问题，调度问题等7.参考文献1 Z.

25、Michalewicz, Genetic Algorithms + Data Structures =Evolution Programs, Springer Verlag, 1992.2 R. Piola, “Evolutionary solutions to a highly constrainedcombinatorial problem”, Dipartimento di informatica, Universitdegli di Torino, Italy, 1992.3 K. Hamada, T. Baba, K. Sato et M. Yufu, “Hybridizing aG

26、enetic Algorithm with Rule-Based Reasoning for ProductionPlanning”, IEEE Expert, October 1995, pp. 60-67.4 D. S. Johson, C. R. Aragon, L. A. Mcgeach, and C. Schevon,Optimization by Simulated Annealing : an ExperimentalEvaluation ; Part II, Graph Coloring and Number Partitioning,Operations Research,

27、vol 39, N1, May-June 1991, pp. 378-406.5 P. D. Varhol, Genetic Programming, Dr Dobbs Journal,January 1994, pp. 131-133.6 A. Singleton, Genetic Programming with C+, Dr DobbsJournal, February 1994, pp. 171-176.7 T. Bck, F. Hoffmeister, et H. P. Schewefel “A Survey ofEvolution Startegies”, Proceedings

28、of the Forth InternationalConference on Genetic Algorithms (ICGA), 1991.8 T. Jones et S. Forrest, Genetic Algorithms and HeuristicSearch, International Joint Conference on ArtificialIntelligence, January 1995.9 P. J. Angeline et L. Federal “Evolution Revolution : anintroduction to the special track

29、on genetic and evolutionaryprogramming”, IEEE Expert, June 1995, pp. 6-10.10 P. Ross, D. Corne, et H. L. Fang, Improving EvolutionaryTimetabling with Delta Evaluation and Directed Mutation,Parallel ProblemSolving From Nature III, Springer-Verlag 1994.11 L. Davis, Handbook of Genetic Algorithms, Van

30、NostrandReinhold, 1991.12 A. Roth, “Constraint Programming : a practical solution tocomplex problems”, AI Expert, September 1993.13 D. E. Goldberg, Genetic Algorithms in Search. Optimizationand Machine Learning, Addision-Welley, 1989.14 K. Hamada, et al, Hybridizing a Genetic Algorithm withRule-Base

31、d Reasoning for Production Planning, IEEE Expert,October 1995, pp. 60-67.15 R. Weare, E. Burke, and D. Elliman, “A Hybrid GeneticAlgorithm for highly Constrained Timetabling Problems”,Department of Computer Science, January 1995.16 R. W. Eglese, “Simulated Annealing : a tool for OperationalResearch”, European Journal of Operational Research, North-Holland, Vol. 46, 1990, pp.271-281.17 M. Wright, School Timetabling Using Heuristic Search,Journal of the Operational Research Society, ol. 47, N 3, 1996,pp. 347-357.18 W. F. Nice, “Genetic Algo