确定一组日期的事件复现模式 [英] Determine Event Recurrence Pattern for a set of dates
问题描述
我正在寻找一个模式，算法或库，它将采取一组日期，并返回一个退出的描述，如果一个退出，即集[11-01-2010,11-08-2010,11- 15-2010，11-22-2010，11-29-2010]将产生像11月的每个星期一。
有没有人看到过这样的东西，有什么建议最好的方式来实现吗？
语法演化（GE）适合于这种问题，因为您正在寻找一种坚持某种语言的答案。语法演化也用于节目制作，音乐制作，设计等等。
我会按照这样做的任务：
使用语法构造问题空间。
构造一个无上下文的语法，可以表示所有期望的重现模式。考虑这些生产规则：
datepattern - > datepattern'和'datepattern
datepattern - >频率边界
频率 - > ''
频率的每个序数工作日> 每个工作日
ordinal - >序号'和'序数
ordinal - > 第一| 第二| 'third'
bounds - > '年度
这些规则生成的模式的一个例子是： 2010年每月第二和第三个星期三和2011年的每一个星期二'
实现这样一种语法的一种方法是通过您将通过反思来操作课堂层次结构，就像我在下面的示例中所做的那样。
将该语言映射到一组日期
您应该创建一个从您的语言接受一个子句的函数，并递归地返回其所涵盖的所有日期的集合。
引导语法，搜索潜在的解决方案
您可以使用遗传算法或模拟退火来将日期与语法进行匹配，使用动态编程来尝试运气，或者用强力枚举所有可能的子句启动简单。如果您使用遗传算法，您的突变概念应该包括根据您的一个生产规则的应用代替另一个表达式。
查看以下GE相关网站的代码和信息：
http://www.bangor.ac.uk/~eep201/jge/
http://nohejl.name/age/
http://www.geneticprogramming.us/Home_Page.html
评估每个解决方案
适应度函数可以考虑解决方案的文本长度，生成的日期数多于一次，错过的日期数以及数量生成错误的日期。
示例代码
根据请求，因为它是这样一个有趣的挑战，我写了一个基本的实现的算法，让你开始。虽然它的工作原理绝对没有完成，但设计应该明确地得到一些更多的思考，一旦你收集了这个例子的基本想法，我建议你考虑使用上面提到的一个库。
///< summary>
///这是一个用于在一组日期中形成复发模式的语法演化算法的非常基本的示例实现。
///它需要大量的扩展和优化才能在生产环境中使用。
///< / summary>
static class Program
{
#region将层次结构编入语法
class DatePattern
{
public频率;
public Bounds bounds;
public override string ToString（）{return+ frequency ++ bounds; }
public IEnumerable< DateTime>日期（）
{
返回频率== null？ new DateTime [] {}：frequency.FilterDates（bounds.GetDates（））;
}
}
抽象类Bounds
{
public abstract IEnumerable< DateTime> GetDates（）;
}
class YearBounds：Bounds
{
/ *在一年.. * /
public int year;
public override string ToString（）{返回年+年; }
public override IEnumerable< DateTime> GetDates（）
{
var firstDayOfYear = new DateTime（year，1，1）;
return Enumerable.Range（0，new DateTime（year，12，31）.DayOfYear）
.Select（dayOfYear => firstDayOfYear.AddDays（dayOfYear））;
}
}
抽象类频率
{
public abstract IEnumerable< DateTime> FilterDates（IEnumerable< DateTime> Dates）;
}
class WeeklyFrequency：frequency
{
/ *每.. * /
public DayOfWeek dayOfWeek;
public override string ToString（）{returnevery+ dayOfWeek; }
public override IEnumerable< DateTime> FilterDates（IEnumerable< DateTime> Dates）
{
return Dates.Where（date =>（date.DayOfWeek == dayOfWeek））;
}
}
class月度频率：频率
{
/ *每个.. * /
公共秩序
public DayOfWeek dayOfWeek;
/ * ..月份* /
public override string ToString（）{returnevery+ ordinal ++ dayOfWeek +of the month; }
public override IEnumerable< DateTime> FilterDates（IEnumerable< DateTime> Dates）
{
return Dates.Where（date =>（date.DayOfWeek == dayOfWeek）&&（int）ordinal ==（date.Day - 1 ）/ 7）;
}
}
枚数有序{第一，第二，第三，第四，第五}
#endregion
static Random random = new Random（）;
const double MUTATION_RATE = 0.3;
static Dictionary< Type，Type []> subtypes = new Dictionary< Type，Type []>（）;
static void Main（）
{
//输入表示2010年每月第一个星期四的重复：
var input = new DateTime [] {new DateTime（2010,12,2），new DateTime（2010,11,4），new DateTime（2010,10,7），new DateTime（2010,9,2），
new DateTime（2010,8,5），new DateTime（2010,7,1），new DateTime（2010,6,3），new DateTime（2010,5,6），
new DateTime（2010,4 ，1），new DateTime（2010,3,4），new DateTime（2010,2,4），new DateTime（2010,1,7）};
for（int cTests = 0; cTests< 20; cTests ++）
{
//初始化一个随机总数
int treesize = 0 ;
var population = new DatePattern [] {（DatePattern）Generate（typeof（DatePattern），ref treesize），（DatePattern）Generate（typeof（DatePattern），ref treesize），（DatePattern）Generate（typeof（DatePattern） ref treesize）};
运行（input，new List< DatePattern>（population））;
}
}
private static void Run（DateTime [] input，List&DatePattern> population）
{
var strongest = population [0] ;
int strongestFitness = int.MinValue;
int bestTry = int.MaxValue;
for（int cGenerations = 0; cGenerations< 300&& strongestFitness< -100; cGenerations ++）
{
//选择最好的个人来生存：
var幸存者=人口
。选择（个人=>新{Fitness = Fitness（输入，个人），个人}）
.OrderByDescending（pair => pair.Fitness）
.Take 5）
。选择（pair => pair.individual）
.ToArray（）;
population.Clear（）;
//幸存者是下一代的基础：
foreach（幸存者中的var parent）
{
for（int cChildren = 0; cChildren< 3; cChildren ++）
{
int treeSize = 1;
DatePattern child =（DatePattern）Mutate（parent，ref treeSize）; // NB：生殖也可以通过交叉进行。
population.Add（（DatePattern）child）;
var childFitness = Fitness（input，child）;
if（childFitness> strongestFitness）
{
bestTry = cGenerations;
strongestFitness = childFitness;
strongest = child;
}
}
}
}
Trace.WriteLine（找到最适合健身+健身（输入，最强）+之后 + bestTry +代：+最强）
}
private static object Mutate（object original，ref int treeSize）
{
treeSize = 0;
对象替换=构造（original.GetType（））;
foreach（original.GetType（）中的var field。GetFields（））
{
object newFieldValue = field.GetValue（original）;
int subtreeSize;
if（field.FieldType.IsEnum）
{
subtreeSize = 1;
if（random.NextDouble（）< = MUTATION_RATE）
newFieldValue = ConstructRandomEnumValue（field.FieldType）;
}
else if（field.FieldType == typeof（int））
{
subtreeSize = 1;
if（random.NextDouble（）< = MUTATION_RATE）
newFieldValue =（random.Next（2）== 0
？Math.Min（int.MaxValue - 1，（int） newFieldValue）+ 1
：Math.Max（int.MinValue + 1，（int）newFieldValue） - 1）;
}
else
{
subtreeSize = 0;
newFieldValue = Mutate（field.GetValue（original），ref subtreeSize）; //成熟前突变以找出subtreeSize
if（random.NextDouble（）< = MUTATION_RATE / subtreeSize）//使高级别节点变得更少。
{
subtreeSize = 0; // init，所以我们可以很快跟踪子树的大小。
newFieldValue = Generate（field.FieldType，ref subtreeSize）;
}
}
field.SetValue（replacement，newFieldValue）;
treeSize + = subtreeSize;
}
返回替换;
}
private static object ConstructRandomEnumValue（Type type）
{
var vals = type.GetEnumValues（）;
return vals.GetValue（random.Next（vals.Length））;
private static object Construct（Type type）
{
return type.GetConstructor（new Type [] {}）。Invoke（new object [ }）;
私有静态对象生成（Type type，ref int treesize）
{
if（type.IsEnum）
{
return ConstructRandomEnumValue（type）;
}
else if（typeof（int）== type）
{
return random.Next（10）+ 2005;
}
else
{
if（type.IsAbstract）
{
//选择一个具体的子类型：
var subtypes = GetConcreteSubtypes（type）;
type = subtypes [random.Next（subtypes.Length）];
}
对象newobj =构造（类型）;
foreach（type.GetFields（）中的var字段）
{
treesize ++;
field.SetValue（newobj，Generate（field.FieldType，ref treesize））;
}
return newobj;
}
}
private static int Fitness（DateTime [] input，DatePattern个人）
{
var output = individual.Dates （）.ToArray（）;
var avgDateDiff = Math.Abs（（output.Average（d => d.Ticks /（24.0 * 60 * 60 * 10000000）） - input.Average（d => d.Ticks /（24.0 * 60 * 60 * 10000000））））;
return
-individual.ToString（）。长度//简洁模式是首选。
- input.Except（output）.Count（）* 300 //忘记一些日期是不好的。
- output.Except（input）.Count（）* 3000 //伪造的日期会给用户带来更多的混乱。
- （int）（avgDateDiff）* 30000; //平均日期的差异是最重要的指导。
}
private static Type [] GetConcreteSubtypes（Type supertype）
{
if（subtypes.ContainsKey（supertype））
{
返回亚型[supertype];
}
else
{
var types = AppDomain.CurrentDomain.GetAssemblies（）。ToList（）
.SelectMany（s => s。 GetTypes（））
.Where（p => supertype.IsAssignableFrom（p）&！p.IsAbstract）.ToArray（）;
subtypes.Add（超类型，类型）;
返回类型;
}
}
}
希望这能让你在轨道上。确保在某个地方分享您的实际解决方案;我认为这在很多情况下会非常有用。
I am looking for a pattern, algorithm, or library that will take a set of dates and return a description of the recurrence if one exits, i.e. the set [11-01-2010, 11-08-2010, 11-15-2010, 11-22-2010, 11-29-2010] would yield something like "Every Monday in November".
Has anyone seen anything like this before or have any suggestions on the best way to implement it?
Grammatical Evolution (GE) is suitable for this kind of problem, because you are searching for an answer that adheres to a certain language. Grammatical Evolution is also used for program generation, composing music, designing, etcetera.
I'd approach the task like this:
Structure the problem space with a grammar.
Construct a Context-free Grammar that can represent all desired recurrence patterns. Consider production rules like these:
datepattern -> datepattern 'and' datepattern
datepattern -> frequency bounds
frequency -> 'every' ordinal weekday 'of the month'
frequency -> 'every' weekday
ordinal -> ordinal 'and' ordinal
ordinal -> 'first' | 'second' | 'third'
bounds -> 'in the year' year
An example of a pattern generated by these rules is: 'every second and third wednesday of the month in the year 2010 and every tuesday in the year 2011'
One way to implement such a grammar would be through a class hierarchy that you will later operate on through reflection, as I've done in the example below.
Map this language to a set of dates
You should create a function that takes a clause from your language and recursively returns the set of all dates covered by it. This allows you to compare your answers to the input.
Guided by the grammar, search for potential solutions
You could use a Genetic algorithm or Simulated Annealing to match the dates to the grammar, try your luck with Dynamic Programming or start simple with a brute force enumeration of all possible clauses.
Should you go with a Genetic Algorithm, your mutation concept should consist of substituting an expression for another one based on the application of one of your production rules.
Have a look at the following GE-related sites for code and information:
http://www.bangor.ac.uk/~eep201/jge/
http://nohejl.name/age/
http://www.geneticprogramming.us/Home_Page.html
Evaluate each solution
The fitness function could take into account the textual length of the solution, the number of dates generated more than once, the number of dates missed, as well as the number of wrong dates generated.
Example code
By request, and because it's such an interesting challenge, I've written a rudimentary implementation of the algorithm to get you started. Although it works it is by no means finished, the design should definitively get some more thought, and once you have gleaned the fundamental take-aways from this example I recommend you consider using one the libraries I've mentioned above.
/// <summary>
/// This is a very basic example implementation of a grammatical evolution algorithm for formulating a recurrence pattern in a set of dates.
/// It needs significant extensions and optimizations to be useful in a production setting.
/// </summary>
static class Program
{
#region "Class hierarchy that codifies the grammar"
class DatePattern
{
public Frequency frequency;
public Bounds bounds;
public override string ToString() { return "" + frequency + " " + bounds; }
public IEnumerable<DateTime> Dates()
{
return frequency == null ? new DateTime[] { } : frequency.FilterDates(bounds.GetDates());
}
}
abstract class Bounds
{
public abstract IEnumerable<DateTime> GetDates();
}
class YearBounds : Bounds
{
/* in the year .. */
public int year;
public override string ToString() { return "in the year " + year; }
public override IEnumerable<DateTime> GetDates()
{
var firstDayOfYear = new DateTime(year, 1, 1);
return Enumerable.Range(0, new DateTime(year, 12, 31).DayOfYear)
.Select(dayOfYear => firstDayOfYear.AddDays(dayOfYear));
}
}
abstract class Frequency
{
public abstract IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates);
}
class WeeklyFrequency : Frequency
{
/* every .. */
public DayOfWeek dayOfWeek;
public override string ToString() { return "every " + dayOfWeek; }
public override IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates)
{
return Dates.Where(date => (date.DayOfWeek == dayOfWeek));
}
}
class MonthlyFrequency : Frequency
{
/* every .. */
public Ordinal ordinal;
public DayOfWeek dayOfWeek;
/* .. of the month */
public override string ToString() { return "every " + ordinal + " " + dayOfWeek + " of the month"; }
public override IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates)
{
return Dates.Where(date => (date.DayOfWeek == dayOfWeek) && (int)ordinal == (date.Day - 1) / 7);
}
}
enum Ordinal { First, Second, Third, Fourth, Fifth }
#endregion
static Random random = new Random();
const double MUTATION_RATE = 0.3;
static Dictionary<Type, Type[]> subtypes = new Dictionary<Type, Type[]>();
static void Main()
{
// The input signifies the recurrence 'every first thursday of the month in 2010':
var input = new DateTime[] {new DateTime(2010,12,2), new DateTime(2010,11,4),new DateTime(2010,10,7),new DateTime(2010,9,2),
new DateTime(2010,8,5),new DateTime(2010,7,1),new DateTime(2010,6,3),new DateTime(2010,5,6),
new DateTime(2010,4,1),new DateTime(2010,3,4),new DateTime(2010,2,4),new DateTime(2010,1,7) };
for (int cTests = 0; cTests < 20; cTests++)
{
// Initialize with a random population
int treesize = 0;
var population = new DatePattern[] { (DatePattern)Generate(typeof(DatePattern), ref treesize), (DatePattern)Generate(typeof(DatePattern), ref treesize), (DatePattern)Generate(typeof(DatePattern), ref treesize) };
Run(input, new List<DatePattern>(population));
}
}
private static void Run(DateTime[] input, List<DatePattern> population)
{
var strongest = population[0];
int strongestFitness = int.MinValue;
int bestTry = int.MaxValue;
for (int cGenerations = 0; cGenerations < 300 && strongestFitness < -100; cGenerations++)
{
// Select the best individuals to survive:
var survivers = population
.Select(individual => new { Fitness = Fitness(input, individual), individual })
.OrderByDescending(pair => pair.Fitness)
.Take(5)
.Select(pair => pair.individual)
.ToArray();
population.Clear();
// The survivers are the foundation for the next generation:
foreach (var parent in survivers)
{
for (int cChildren = 0; cChildren < 3; cChildren++)
{
int treeSize = 1;
DatePattern child = (DatePattern)Mutate(parent, ref treeSize); // NB: procreation may also be done through crossover.
population.Add((DatePattern)child);
var childFitness = Fitness(input, child);
if (childFitness > strongestFitness)
{
bestTry = cGenerations;
strongestFitness = childFitness;
strongest = child;
}
}
}
}
Trace.WriteLine("Found best match with fitness " + Fitness(input, strongest) + " after " + bestTry + " generations: " + strongest);
}
private static object Mutate(object original, ref int treeSize)
{
treeSize = 0;
object replacement = Construct(original.GetType());
foreach (var field in original.GetType().GetFields())
{
object newFieldValue = field.GetValue(original);
int subtreeSize;
if (field.FieldType.IsEnum)
{
subtreeSize = 1;
if (random.NextDouble() <= MUTATION_RATE)
newFieldValue = ConstructRandomEnumValue(field.FieldType);
}
else if (field.FieldType == typeof(int))
{
subtreeSize = 1;
if (random.NextDouble() <= MUTATION_RATE)
newFieldValue = (random.Next(2) == 0
? Math.Min(int.MaxValue - 1, (int)newFieldValue) + 1
: Math.Max(int.MinValue + 1, (int)newFieldValue) - 1);
}
else
{
subtreeSize = 0;
newFieldValue = Mutate(field.GetValue(original), ref subtreeSize); // mutate pre-maturely to find out subtreeSize
if (random.NextDouble() <= MUTATION_RATE / subtreeSize) // makes high-level nodes mutate less.
{
subtreeSize = 0; // init so we can track the size of the subtree soon to be made.
newFieldValue = Generate(field.FieldType, ref subtreeSize);
}
}
field.SetValue(replacement, newFieldValue);
treeSize += subtreeSize;
}
return replacement;
}
private static object ConstructRandomEnumValue(Type type)
{
var vals = type.GetEnumValues();
return vals.GetValue(random.Next(vals.Length));
}
private static object Construct(Type type)
{
return type.GetConstructor(new Type[] { }).Invoke(new object[] { });
}
private static object Generate(Type type, ref int treesize)
{
if (type.IsEnum)
{
return ConstructRandomEnumValue(type);
}
else if (typeof(int) == type)
{
return random.Next(10) + 2005;
}
else
{
if (type.IsAbstract)
{
// pick one of the concrete subtypes:
var subtypes = GetConcreteSubtypes(type);
type = subtypes[random.Next(subtypes.Length)];
}
object newobj = Construct(type);
foreach (var field in type.GetFields())
{
treesize++;
field.SetValue(newobj, Generate(field.FieldType, ref treesize));
}
return newobj;
}
}
private static int Fitness(DateTime[] input, DatePattern individual)
{
var output = individual.Dates().ToArray();
var avgDateDiff = Math.Abs((output.Average(d => d.Ticks / (24.0 * 60 * 60 * 10000000)) - input.Average(d => d.Ticks / (24.0 * 60 * 60 * 10000000))));
return
-individual.ToString().Length // succinct patterns are preferred.
- input.Except(output).Count() * 300 // Forgetting some of the dates is bad.
- output.Except(input).Count() * 3000 // Spurious dates cause even more confusion to the user.
- (int)(avgDateDiff) * 30000; // The difference in average date is the most important guide.
}
private static Type[] GetConcreteSubtypes(Type supertype)
{
if (subtypes.ContainsKey(supertype))
{
return subtypes[supertype];
}
else
{
var types = AppDomain.CurrentDomain.GetAssemblies().ToList()
.SelectMany(s => s.GetTypes())
.Where(p => supertype.IsAssignableFrom(p) && !p.IsAbstract).ToArray();
subtypes.Add(supertype, types);
return types;
}
}
}
Hope this gets you on track. Be sure to share your actual solution somewhere; I think it will be quite useful in lots of scenarios.
这篇关于确定一组日期的事件复现模式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
