首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
大学考试时间表是一个多约束条件下的优化问题。传统遗传算法寻优的计算量是指数级的规模,而寻优的操作有可能会破坏时间表的硬约束条件,从而最终得到的解并不一定理想甚至不可行。该文从某高校的实际应用出发,对用图着色模型得到的已经满足了硬约束条件的初始考试时间表,用改进的分组遗传算法在既不破坏硬约束条件也不延长考试周的条件下扩大并平均分配了学生的复习时间,并且还大大减少了寻优的计算量。  相似文献   

2.
时间表问题是将有限的时间资源分配给多个对象的资源分配问题,它是一类具有多约束条件的组合优化问题。时间表问题已经被证明是一个NP完全问题。大学考试时间安排问题是时间表问题的一个应用,利用改进的图着色算法来处理大学考试的时间安排问题能够最大程度上使考试时间安排得更加人性化、合理化。实验测试表明,基于所给出的算法实现的考试时间安排系统具有良好的可行性、实用性和优越性。  相似文献   

3.
基于GENET的时间表问题自动求解算法   总被引:2,自引:0,他引:2  
构造大学考试时间表自动生成系统是一个知名的问题.本文用约束满足问题模型来描述大学考试时间表问题,并提出了一个基于GENET的局部搜索算法来解该问题.该算法采用一些问题相关的策略来提高局部搜索效率.实验结果表明,将“强约束违反”转化为“弱约束违反”的方法能大大地提高算法性能,使该算法优于GENET和演化算法。  相似文献   

4.
分析大学课程时间表问题的特征,结合已有蚁群算法的求解策略,构建了新的问题求解模型,提出了一种基于蚁群算法和改进过程的求解算法,并在不同规模的问题实例上进行实验。结果表明,算法在目标函数解的质量上有明显改进。  相似文献   

5.
混合算法在大学课程表问题中的应用研究   总被引:2,自引:0,他引:2  
大学课程袁问题是时间表问题之一,也是一个多因素的优化决策问题.文章提出的混合算法,基于动态规划的思想,对大学课程表问题进行分阶段求解,分别采用遗传算法分配时间,采用最佳适应算法分配场地.实验结果表明,这种方法既保证了课表的质量,又有利于工程上实现和扩展.  相似文献   

6.
说明: 1.自2002年起,高等教育自学考试4月和10月开考课程由全国统一安排,各地考生也参加全国统考。 2.在全国统考课程安排的基础上,各地自考办自行安排1月和7月的小自考开考课程,以衔接前后两次全国统考的原则来具体安排开考课程,从而为考生多提供一次考试机会。2002年自学考试(计算机相关专业)全国统考课程考试时间表  相似文献   

7.
1.高等教育自学考试设立的四类证书 高等教育自学考试目前设立的证书有:专科毕业证书、本科毕业证书、专业证书、单科合格证书。 2.取得高教自考毕业证书的条件 高等教育自学考试应考者符合下列三项规定,可以取得毕业证书: (1)考完专业考试计划规定的全部课程,并取得合格成绩; (2)完成规定的毕业论文(设计)或其它教学实践任务; (3)思想品德鉴定合格。 3.申请办理自考毕业证书的程序 考生按专业考试计划规定的全部课程(包括实践环节)考试合格后,应在规定的时间内,到当地自学考试办公室申请办理毕业证书。 具体程…  相似文献   

8.
粒子群优化算法是近年来发展起来的一种元启发式的搜索算法,是目前解决组合优化问题的最有效的算法之一.针对考试时间表问题(ETP),通过基于时间序列的粒子编码方式和新的更新算子,建立ETP问题的粒子群求解模型,并结合简化邻域搜索算法给出了改进策略.仿真实验结果表明所提算法及策略的有效性.  相似文献   

9.
针对大学课程时间表问题,提出一种基于改进迭代局部搜索的并行多视图搜索算法进行求解。依据课程时间表问题特性设计包含八种基础邻域的多邻域集,并根据提升速度比制定基邻域选择概率设置规则。在迭代局部搜索过程中,运用多视图学习策略对多个局部搜索步骤进行视图共享,及时调整搜索方向以提升搜索效率。通过并行计算思想对算法优化,提升多视图搜索的收敛速度。实验结果表明,提出的算法求解精度更佳,且具有优异的扩展性和并行效率。  相似文献   

10.
基于遗传算法的排课系统的设计与实现   总被引:2,自引:0,他引:2  
滕姿  邓辉文  杨久俊 《计算机应用》2007,27(Z2):199-201
排课问题是典型的组合优化和不确定性调度问题,并且是NP完全问题.将遗传算法应用于求解课表问题,并将一天分为十二节课,对排课问题中的课时分配及时间安排进行了灵活分配以适应大学上课的需要.在进行课表初始化、课程安排和冲突处理时采用了时间片重叠法,即在每次安排课程时,根据班级课程表,授课教师时间表以及教师意愿表找出其中符合课时需要的重叠有空的时间单元安排课程,如果没有找到符合条件的时间单元,则优先选择教师有空的时间单元安排课程.实验表明,这种方法有较好的效果.  相似文献   

11.
The numerical solution of variational inequality problems in elastostatics is investigated by means of recently proposed equivalent nonlinear equations. Symmetric and nonsymmetric variational inequalities and linear or nonlinear, but monotone, complementarity problems can be solved this way without explicit use of nonsmooth (nondifferentiable) solvers. As a model application, two-dimentional unilateral contact problems with and without friction effects approximated by the boundary element method are formulated as nonsymmetric variational inequalities, or, for the two-dimensional case as linear complementarity problems, and are numerically solved. Performance comparisons using two standard, smooth, general purpose nonlinear equation solvers are included.  相似文献   

12.
Optimization problems with criterion functions and admissible sets symmetric with respect to some transformations are considered. Conditions are studied which guarantee that solutions of these problems exist on a set of points fixed with respect to the initial transformation for continuous problems and on a set of quasifixed points for integer problems.  相似文献   

13.
14.
Almost 2-SAT is fixed-parameter tractable   总被引:1,自引:0,他引:1  
We consider the following problem. Given a 2-cnf formula, is it possible to remove at most k clauses so that the resulting 2-cnf formula is satisfiable? This problem is known to different research communities in theoretical computer science under the names Almost 2-SAT, All-but-k 2-SAT, 2-cnf deletion, and 2-SAT deletion. The status of the fixed-parameter tractability of this problem is a long-standing open question in the area of parameterized complexity. We resolve this open question by proposing an algorithm that solves this problem in O(k15×k×m3) time showing that this problem is fixed-parameter tractable.  相似文献   

15.
Multicriteria/multiobjective path and tree models are useful in many applications. Particularly, in Internet routing problems they seem to lead to promising approaches. In the first part of this paper, we classify and present the main exact approaches dealing with several multicriteria path problems putting in evidence the shortest path problem. In the second part, we review exact algorithms dedicated to some multicriteria tree problems, namely the minimum spanning tree and the minimum cost/minimum label spanning tree problems. Finally, the application of these models is exemplified.  相似文献   

16.
Differential evolution is primarily designed and used to solve continuous optimization problems. Therefore, it has not been widely considered as applicable for real-world problems that are characterized by permutation-based combinatorial domains. Many algorithms for solving discrete problems using differential evolution have been proposed, some of which have achieved promising results. However, to enhance their performance, they require improvements in many aspects, such as their convergence speeds, computational times and capabilities to solve large discrete problems. In this paper, we present a new mapping method that may be used with differential evolution to solve combinatorial optimization problems. This paper focuses specifically on the mapping component and its effect on the performance of differential evolution. Our method maps continuous variables to discrete ones, while at the same time, it directs the discrete solutions produced towards optimality, by using the best solution in each generation as a guide. To judge its performance, its solutions for instances of well-known discrete problems, namely: 0/1 knapsack, traveling salesman and traveling thief problems, are compared with those obtained by 8 other state-of-the-art mapping techniques. To do this, all mapping techniques are used with the same differential evolution settings. The results demonstrated that our technique significantly outperforms the other mapping methods in terms of the average error from the best-known solution for the traveling salesman problems, and achieves promising results for both the 0/1 knapsack and the traveling thief problems.  相似文献   

17.
The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. In this framework preferences can be associated with tuples of values of the variable domains. Bistarelli et al. [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraint solving and optimization, Journal of the ACM 44 (2) (1997) 201-236] defines a maximal solution to a SCSP as the best set of solution tuples for the variables in the problem. Sometimes this maximal solution may not be good enough, and in this case we want to change the constraints so that we solve a problem that is slightly different from the original problem but has an acceptable solution. We propose a relaxation of a SCSP, and use a semiring to give a measure of the difference between the original SCSP and the relaxed SCSP. We introduce a relaxation scheme but do not address the computational aspects.  相似文献   

18.
19.
Phase change problems are of practical importance and can be found in a wide range of engineering applications. In the present paper, two proposed numerical algorithms are developed; the first one is general for phase change problems, while the second one is for ablation problems. The boundary elements method is used as a mathematical tool in conjunction with the proposed algorithms. Two test examples were solved and the results agree with the physics of the problems.  相似文献   

20.
The Chinese postman problem with time windows (CPPTW) is modelled as a constraint programme and results are reported for a set of test problems with up to 69 edges. Two different formulations are proposed. The first formulation approaches the problem directly and the second transforms the problem to an equivalent vehicle routing problem with time windows. The results demonstrate that optimal solutions can be obtained quickly when the time windows are tight. However, the results also show that as the time windows are made wider and the number of feasible solutions increases, these constraint programming formulations take significantly longer to find a provably optimal solution. The results also demonstrate how the size and density of the graph affects the computing time needed to find an optimal solution.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号