确定一组日期的事件重复模式?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (26)

我正在寻找一种模式,算法或库,它们将采用一组日期,并返回一个退出的描述,即退出集合[11-01-2010,11-08-2010,11-15-2010 ,11-22-2010,11-29-2010]会产生类似于“11月的每个星期一”的内容。

有没有人以前看过类似的东西,或者对实现它有什么好的建议?

提问于
用户回答回答于

语法进化(GE)适用于这类问题,因为您正在寻找符合某种语言的答案。语法演变也用于节目制作,音乐创作,设计等等。

我会这样处理任务:

用语法来构造问题空间

构建可表示所有期望的重现模式的无上下文语法。考虑像这样的生产规则:

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

这些规则产生的模式的一个例子是:“2010年和2011年每个星期二的每个月的第二和第三个星期三”

实现这种语法的一种方法是通过类层次结构,稍后您将通过反思进行操作,正如我在下面的示例中所做的那样。

将此语言映射到一组日期

你应该创建一个函数,它接受你的语言中的一个子句并递归地返回它所涵盖的所有日期的集合。这使您可以将您的答案与输入进行比较。

以语法为指导,寻找潜在的解决方案

您可以使用遗传算法或模拟退火来将日期与语法进行匹配,使用动态编程来尝试运气,或者使用强制枚举所有可能的子句开始简单。

如果你使用遗传算法,你的变异概念应该包括用一个生产规则的应用来代替另一个表达式。

评估每个解决方案

适应函数可以考虑解决方案的文本长度,不止一次生成的日期数量,错过的日期数量以及生成的错误日期数量。

示例代码

根据要求,并且由于这是一个有趣的挑战,我已经写了一个基本的算法实现来帮助你开始。虽然它的工作原理尚未完成,但设计应该明确地思考一下,一旦你从这个例子中收集了基本的东西,我建议你考虑使用上面提到的库。

  /// <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;
      }
    }
  }

希望这会让你走上正轨。请务必在某处分享你的实际解决方案; 我认为这会在很多场景中非常有用。

用户回答回答于

如果你的目的是要为您的“11月的每个星期一”生成模式的可读描述,那么你可能首先要列举可能的描述。描述可以分解为频率和范围,例如,

频率:

  • 每天 ...
  • 每隔一天/第三/第四天...
  • 平日/周末......
  • 每逢星期一 ...
  • 交替星期一...
  • 第一个/第二个/最后一个星期一......
  • ...

边界:

  • ... 在一月
  • ...... 3月25日至10月25日

扫码关注云+社区