摘要翻译：
近年来，遗传算法已成为启发式求解复杂离散优化问题的有效工具。特别是，人们对使用它们来处理日程安排和时间表方面出现的问题很感兴趣。然而，传统的遗传算法不能很好地处理约束条件，为了克服这一缺点，成功的实现通常需要某种修改来使搜索能够利用问题特定的知识。本文是关于一个遗传算法家族的发展，以解决一个护士名册问题，在英国的一个主要医院。这家医院由多达30名护士组成的病房组成。每个病房都有自己的护士小组，他们的轮班必须每周安排。除了满足每天三个轮班以上的工作人员的最低需求之外，护士的愿望和资格也必须考虑在内。时间表也必须被视为公平的，因为不受欢迎的轮班必须在所有护士中平均分配，其他限制，如团队护理和高级员工的特殊条件，必须得到满足。遗传算法家族的基础是由n点交叉、单比特变异和基于秩的选择组成的经典遗传算法。解决方案空间包括每个护士工作所需班次的所有时间表，但剩余的限制，无论是硬的还是软的，都在适应度函数中放松和惩罚。讲座将首先详细描述问题和初步实施情况，然后着重指出这种方法在平衡可行性的关键因素方面的缺点，即涵盖需求和工作规定，以及以护士的偏好衡量的质量。接下来将概述一系列涉及参数自适应、小生境、智能权重、delta编码、局部爬山、迁移和特殊选择规则的实验，并展示一系列这些增强是如何消除这些困难的。基于几个月的真实数据的结果将被用来衡量每个修改的影响，并表明最终算法能够与医院目前使用的禁忌搜索方法竞争。在结束发言时，我们将对解决这一问题和类似问题的这种方法的总体质量提出一些看法。
---
英文标题：
《Nurse Rostering with Genetic Algorithms》
---
作者：
Uwe Aickelin
---
最新提交年份：
2010
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Neural and Evolutionary Computing        神经与进化计算
分类描述：Covers neural networks, connectionism, genetic algorithms, artificial life, adaptive behavior. Roughly includes some material in ACM Subject Class C.1.3, I.2.6, I.5.
涵盖神经网络，连接主义，遗传算法，人工生命，自适应行为。大致包括ACM学科类C.1.3、I.2.6、I.5中的一些材料。
--

---
英文摘要：
  In recent years genetic algorithms have emerged as a useful tool for the heuristic solution of complex discrete optimisation problems. In particular there has been considerable interest in their use in tackling problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle constraints and successful implementations usually require some sort of modification to enable the search to exploit problem specific knowledge in order to overcome this shortcoming. This paper is concerned with the development of a family of genetic algorithms for the solution of a nurse rostering problem at a major UK hospital. The hospital is made up of wards of up to 30 nurses. Each ward has its own group of nurses whose shifts have to be scheduled on a weekly basis. In addition to fulfilling the minimum demand for staff over three daily shifts, nurses' wishes and qualifications have to be taken into account. The schedules must also be seen to be fair, in that unpopular shifts have to be spread evenly amongst all nurses, and other restrictions, such as team nursing and special conditions for senior staff, have to be satisfied. The basis of the family of genetic algorithms is a classical genetic algorithm consisting of n-point crossover, single-bit mutation and a rank-based selection. The solution space consists of all schedules in which each nurse works the required number of shifts, but the remaining constraints, both hard and soft, are relaxed and penalised in the fitness function. The talk will start with a detailed description of the problem and the initial implementation and will go on to highlight the shortcomings of such an approach, in terms of the key element of balancing feasibility, i.e. covering the demand and work regulations, and quality, as measured by the nurses' preferences. A series of experiments involving parameter adaptation, niching, intelligent weights, delta coding, local hill climbing, migration and special selection rules will then be outlined and it will be shown how a series of these enhancements were able to eradicate these difficulties. Results based on several months' real data will be used to measure the impact of each modification, and to show that the final algorithm is able to compete with a tabu search approach currently employed at the hospital. The talk will conclude with some observations as to the overall quality of this approach to this and similar problems.
---
PDF链接：
https://arxiv.org/pdf/1004.2870